This forum post explains Procedural Graphs: Self-Evolving Execution Structures for LLM Agents (arXiv:2609.09153) by Yuxing Lu, Yicheng Chen, and Shanchan Wu.
The Problem
Current LLM agents (AutoGPT, LangChain-style agents) rely on a growing memory of thoughts, observations, and actions with no predefined structure. As tasks grow long and complex, this leads to:
- Losing track of the original goal
- Disordered tool calls (e.g., analyzing before searching)
- Repeating ineffective actions
- Lack of global planning
- Nodes: execution steps with descriptions, expected inputs/outputs, success/failure conditions
- Edges: relationships like sequence, conditional branching, parallelism
- Attributes: execution probabilities, average duration, success rates, common error patterns—updated with experience
- WebShop: 15-25% success-rate improvement over memory baselines; evolution adds 10-20% over the initial graph
- ALFWorld: helps track complex object-interaction sequences
- HotPotQA: optimizes retrieval and evidence-integration flows
- Tool use: enforces correct call ordering and parameters
- 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*.
The post argues agents lack procedural knowledge—knowing *what to do, in what order, under what conditions*—as opposed to factual knowledge.
The Core Idea
Just as knowledge graphs organize facts with (entity, relation, entity) triples, a Procedural Graph organizes procedural knowledge with (procedure, relation, procedure) triples:
At each decision, the system locates the current node, extracts a local subgraph, translates it into natural-language context guidance, and applies it as a soft bias—influencing the LLM without removing its autonomy.
Self-Evolution Mechanism
An evolution loop:
1. Collect execution trajectories 2. Compare failed vs. successful trajectories 3. Identify where failures diverged 4. An LLM Refiner proposes graph edits 5. Accept edits only if validation performance is maintained or improved; rejected edits are logged to avoid repetition
Three edit types: topology (add/remove nodes and edges), attributes (success rates, thresholds, probabilities), and content (refine descriptions and guidance).
Notably, graphs can start from an empty graph, a minimal skeleton ("start→execute→end"), or expert-designed priors. The minimal skeleton proved most efficient; even flawed expert priors get repaired by evolution.
Why Graphs Beat Memory
| Dimension | Vanilla memory | Workflow memory | Procedural graph | |---|---|---|---| | Structure | None | Case-level | Abstract procedural | | Generalization | Poor | Medium | Good | | Interpretability | Poor | Medium | Good | | Evolvability | None | Limited | Strong | | Efficiency | Low | Medium | High |
Workflow memory recalls "how I did it last time"; procedural graphs abstract "the general workflow for this task type"—enabling generalization and keeping the decision-time context small via local subgraph navigation.
Experimental Results
Key findings: graphs evolved on one LLM (e.g., GPT-4) transfer to other LLMs (Claude, Llama); evolution works with few examples (<10) where memory baselines degrade sharply; and flawed human designs are self-repairable.
Interpretation
The post frames this as a neuro-symbolic fusion: the LLM provides semantic understanding (a fast "System 1"), while the graph provides explicit, inspectable, correctable execution structure (a "System 2"). From a software-engineering view, it enables separation of concerns, version control of the graph, and testable, quantifiable edits.
The takeaway: rather than giving agents a fixed program, Procedural Graphs give them a structure that writes and improves its own program.