Procedural Graphs: When LLM Agents Rewrite Their Own Execution Playbooks

This post introduces and discusses the paper "Procedural Graphs: Self-Evolving Execution Structures for LLM Agents" by Yuxing Lu, Yicheng Chen, and Shanchan Wu (arXiv:2609.09153).

> Core idea: Just as knowledge graphs organize factual knowledge via (entity, relation, entity) triples to answer "what" questions, Procedural Graphs organize procedural knowledge via (procedure, relation, procedure) triples to answer "how" questions—giving an LLM agent's execution playbook the ability to evolve itself.

Why Agents Need Structure

Today's LLM agents (AutoGPT-style, LangChain agents) typically maintain a growing memory of thoughts, observations, and actions, improvising each next step. On long, complex tasks this leads to:

• Goal drift: forgetting the original objective over long interactions
• Action misordering: calling tools in the wrong sequence
• Repetition: retrying the same ineffective operations
• No global planning: myopic, step-by-step behavior

Humans rely on procedural knowledge—recipes, diagnostic flowcharts, algorithms—that specifies what to do, in what order, and under what conditions. Current agents have memory but no process.

Anatomy of a Procedural Graph

• Nodes: program steps (e.g., "search for information", "call API"), each with descriptions, expected inputs/outputs, and success/failure conditions
• Edges: relations between steps—sequential ("then"), conditional ("if...then"), parallel
• Attributes: execution probability, average duration, success rate, common error patterns—updated with experience

Example: booking a flight produces a directed graph with branching, loops, and condition checks rather than a linear transcript.

At decision time, the system: (1) locates the current node, (2) extracts the local subgraph as context, (3) translates it into natural-language situational guidance, and (4) applies it as a soft bias in the prompt—influencing the LLM without removing its autonomy. As the author puts it: a good coach advises, but doesn't play for you.

Self-Evolution: How the Graph Comes Alive

The evolution loop:

1. Collect trajectories of completed tasks 2. Compare failed trajectories against successful ones 3. Identify divergences (wrong order, bad condition, missing step) 4. Generate edits via an LLM Refiner 5. Validate on a held-out set: accept edits that improve or preserve performance; reject and log those that degrade it

Three edit types:

• Topology: add/remove nodes, restructure edges (e.g., inserting a "check user preferences" step between search and filtering)
• Attributes: update success statistics, conditional thresholds, execution probabilities
• Content: refine node descriptions and guidance text

Initialization findings: starting from an empty graph needs more iterations; a minimal skeleton evolves most efficiently and performs best; even a flawed expert-designed prior gets repaired by evolution—robustness that lowers deployment barriers.

Procedural Graph vs. Memory Baselines

| Dimension | Vanilla Memory | Workflow Memory | Procedural Graph | |---|---|---|---| | Structure | None | Case-level | Abstract procedure-level | | Generalization | Poor | Medium | Good | | Interpretability | Poor | Medium | Good | | Evolvability | None | Limited | Strong | | Efficiency | Low | Medium | High |

The key advantage is abstraction level: workflow memory recalls "how I did mapo tofu last time"; a procedural graph captures "the general stir-fry process" and generalizes to any dish. Structured navigation also confines decision-time context to the local subgraph, mitigating long-context attention dilution.

Experimental Results

Evaluated on WebShop (web shopping, 15-25% success-rate gain over memory baselines; 10-20% gain from self-evolution), ALFWorld (household tasks), HotPotQA (multi-hop QA), and multi-API tool-use tasks.

Key findings:

• Cross-LLM transfer: graphs evolved on one LLM (e.g., GPT-4) transfer to others, suggesting they capture task structure rather than model idiosyncrasies
• Few-shot advantage: effective evolution with fewer than 10 examples, where memory baselines degrade sharply
• Repairability: flawed human-designed workflows are progressively fixed

Deeper Implications

• Neuro-symbolic fusion: the LLM supplies semantic understanding; the graph supplies procedural constraints—a hybrid architecture for more reliable AI
• Dual-system analogy: the graph acts as a "System 2" controller (explicit, inspectable, correctable) atop the LLM's "System 1" generative ability
• Software-engineering principles: separation of concerns (what/how/improve), version control of every graph edit with rollback, and testability against validation sets

Conclusion

Information only creates value when organized into useful structure. Procedural Graphs give LLM agents a skeleton (clear execution flow), a learning capability (self-evolution from failure), and interpretability (humans can read and modify the agent's "thinking"). The vision: not to give agents a fixed program, but a brain that can write its own programs.

References

• Lu, Y., Chen, Y., & Wu, S. (2026). *Procedural Graphs: Self-Evolving Execution Structures for LLM Agents*. arXiv:2609.08593.
• Wang, Z. Z., et al. (2025). Agent Workflow Memory. *ICML*.
• Wei, T., et al. (2026). Evo-Memory: Benchmarking LLM Agent Test-Time Learning with Self-Evolving Memory. arXiv:2511.20857.
• Fang, R., et al. (2026). Memp: Exploring Agent Procedural Memory. *ACL 2026 Findings*.