Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

The paper proposes the Procedural Graph (PG), an explicit, editable directed graph that stores an LLM agent's procedural knowledge — the same move a knowledge graph makes for factual knowledge, but for the "what to do next" question. Where a knowledge graph stores (entity, relation, entity) triplets, a PG stores (procedure, relation, procedure) triplets: nodes abstract tool calls, reasoning steps, and states, while edges encode admissible transitions, each annotated with three textual attributes — condition, guidance, and pitfalls (when the transition applies, how to proceed, what to avoid).

The graph is used in two phases. Online, the framework localizes the agent's active node from its trajectory, and a guidance model reads the surrounding subgraph (the localized node's neighborhood up to a few hops) and translates its attributes into step-level situational guidance that is appended to the solver's prompt — steering the next action without dictating it. Offline, a self-evolution loop improves the graph itself: an LLM refiner contrasts failed trajectories against successful ones, proposes edits (add/delete nodes and edges, revise attributes), and a validation gate on a held-out set accepts only edits that match or improve performance, while rejected candidates are logged as rejection memory to discourage repeats.

Across seven benchmarks (HotpotQA, MultiChallenge, GDPval, ALFWorld, τ-bench, BFCL v3, EnterpriseArena) and four LLMs (Claude Sonnet 4.6, Gemini 3.1 Pro, Gemini 3.5 Flash, Grok 4.1 Fast), PG ranks first or joint-first in 21 of 24 model–benchmark settings against seven memory-based baselines (Vanilla ReAct, MemoryBank, RAP, ExpeL, AutoGuide, AWM, KnowAgent). Self-evolution from a minimal skeleton produces graphs that match or surpass hand-designed ones, and the loop can also repair a flawed expert prior that initially hurts performance. On EnterpriseArena's long-horizon CFO simulation, the evolved graph teaches anticipatory fundraising — requesting capital months before a liquidity crisis because delivery lags one to six months — raising survival substantially for three of four models. An efficiency study favors localized subgraph guidance over full-graph raw injection or full-graph generative guidance.