Procedural Graphs: Self-Evolving Execution Structures That Let LLM Agents Rewrite Their Own Playbooks

Forum topic · 小凯 · 2026-09-09

Summary

This forum post introduces the paper "Procedural Graphs: Self-Evolving Execution Structures for LLM Agents" (arXiv:2609.09153) by Yuxing Lu, Yicheng Chen, and Shanchan Wu. The paper proposes organizing procedural knowledge for LLM agents as a graph of (procedure, relation, procedure) triples—analogous to how knowledge graphs organize factual knowledge—where nodes represent execution steps (with descriptions, success conditions, and statistics) and edges encode sequential, conditional, or parallel relations. At decision time, the agent navigates a local subgraph and receives soft natural-language guidance that biases, but does not override, LLM generation. Crucially, the graph self-evolves: an LLM-based Refiner contrasts failed with successful trajectories, proposes topology, attribute, or content edits, and accepts edits only if validation performance improves or holds. Experiments on WebShop, ALFWorld, HotPotQA, and tool-use tasks show 15-25% success-rate gains over memory baselines, robust evolution even from empty or flawed expert priors, cross-LLM transferability, and effectiveness with fewer than 10 examples. The post frames this as a neuro-symbolic hybrid—a "System 2" controller for LLMs—offering interpretability, version control, and testability.

Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

Paper: Procedural Graphs: Self-Evolving Execution Structures for LLM Agents
Authors: Yuxing Lu, Yicheng Chen, Shanchan Wu
arXiv: 2609.09153

Key points

The problem: Today's LLM agents (AutoGPT-style, LangChain agents) improvise from a growing memory of thoughts, observations, and actions. On long, complex tasks this leads to goal drift, mistimed tool calls, repeated failed actions, and no global planning. What's missing is procedural knowledge—structured "how to do it," not "what it is."
Core idea: Just as knowledge graphs organize facts as (entity, relation, entity) triples, a Procedural Graph organizes procedural knowledge as (procedure, relation, procedure) triples. Nodes are procedure steps with descriptions, expected inputs/outputs, and success/failure conditions; edges encode sequencing, conditionals, parallelism; attributes track execution probability, average time, success rate, and common error patterns.
Soft guidance at decision time: At each step, the system locates the current node, extracts a local subgraph, translates it into natural-language situational guidance, and injects it into the prompt. Guidance biases the LLM without removing its autonomy—"a coach who advises but doesn't play for you."
Self-evolution loop: The agent's trajectories are collected; failed trajectories are contrasted with successful ones; an LLM Refiner proposes edits; edits are accepted only if validation performance improves or stays flat, otherwise rejected with a record to avoid retries. Three edit types:

Topology edits

Attribute edits

Content edits

Initialization robustness: Tested three starting points—empty graph, minimal skeleton, expert-designed prior. Empty graphs need more iterations but converge to comparable performance; minimal skeletons evolve most efficiently and perform best; even flawed expert priors get repaired by evolution.
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 |

Workflow memory recalls "how I did it last time"; Procedural Graph abstracts "the general recipe for this task class"—like knowing the general stir-fry sequence versus one specific dish. Structured navigation also avoids the bloated-context problem of growing memory logs.

Experimental results: On WebShop, ALFWorld, HotPotQA, and tool-use benchmarks, Procedural Graphs beat memory baselines by 15–25% success rate, and self-evolved graphs beat initial graphs by 10–20%. Notably:
Graphs evolved on one LLM (e.g., GPT-4) transfer to other LLMs (Claude, Llama), suggesting they capture task structure, not model quirks.
Evolution works with fewer than 10 examples, where memory baselines collapse.

Deeper implications

Neuro-symbolic fusion: LLMs contribute semantic understanding; the graph contributes explicit procedural constraints—a hybrid echoing the connectionist/symbolist blend.
A "System 2" for LLMs: like human fast intuition (System 1) plus slow rule-based reasoning (System 2), the graph acts as an explicit, inspectable, correctable execution controller.
Software-engineering discipline: separation of concerns (LLM decides *what*, graph defines *how*, Refiner optimizes *improvement*), version control with rollback, and testability on validation sets.

Conclusion

The post's closing metaphor: a recipe book that edits itself is no longer just a book—it's alive. Procedural Graphs give agents a skeleton (clear execution flow), a learning mechanism (self-evolution from failure), and interpretability (humans can read and modify its "thinking"). The vision: not handing 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*.

> Note: the original post lists two arXiv IDs for the paper (2609.09153 in the header, 2609.08593 in the references); both are preserved as in the source.