Agents need a map of how, not just a transcript of what happened
A new paper proposes the Procedural Graph, a structured, self-evolving representation of an agent's know-how that guides tool use at inference time and repairs itself offline from failed trajectories.
Most production agents I've built or reviewed pick their next action the same way: they generate over an accumulating transcript and hope the model infers, from context alone, what step comes next, in what order, and under which conditions. That works until the trajectory gets long. Then the agent loses track of its own objective, calls a tool out of sequence, or repeats an action that already failed two turns ago. A new paper, Procedural Graphs: Self-Evolving Execution Structures for LLM Agents (Lu, Chen, Wu, and Arık), names this gap precisely: agents have plenty of factual knowledge encoded as retrievable text, but almost no explicit representation of procedural knowledge — the how.
The gap: knowing facts versus knowing procedure
Knowledge graphs solved a version of this problem for facts twenty years ago: instead of leaving "who works where" implicit in a pile of documents, you store it as (entity, relation, entity) triplets and query it directly. This paper applies the same move to procedure. A Procedural Graph (PG) is a directed, attributed graph of (procedure, relation, procedure) triplets. Nodes stand for tool actions, reasoning steps, or states; edges carry three pieces of text — a condition (when this transition applies), guidance (how to execute it), and a pitfall (what tends to go wrong). That's the whole representation: not a policy, not a fixed script, just a map of legal moves and their caveats.
The reason this matters for anyone running agents against real APIs and tool sets: the failure mode you actually see in production isn't usually "the model can't reason." It's "the model forgot that step 4 requires step 2's output to be validated first," or "it retried the same failing call three times because nothing told it that pattern was a dead end." That's exactly the class of error a condition/guidance/pitfall edge is built to prevent.
How the graph steers the agent without dictating it
At inference time, the framework doesn't hand the agent a rigid path. It localizes the agent's current step by matching its most recent action to a node in the graph, pulls the 2-hop neighborhood around that node, and passes that subgraph to a separate guidance LLM, which translates it into natural-language situational advice appended to the solver's prompt. The paper calls this "soft integration": the graph steers, it doesn't command. The solver still generates freely — it's just no longer generating blind.
That design choice is worth sitting with. It's the difference between a finite-state machine that forces transitions and a set of guardrails that inform a still-free-form policy. Ablations in the paper back the choice: localized subgraph guidance with generative translation beat both dumping the raw graph into context and running a full-graph generative pass, gaining 2 to 9 points while cutting token overhead 18–71% versus the alternatives. Precision in what you retrieve matters more than completeness.
Self-evolution: the graph edits itself against a held-out set
The more interesting half is what happens offline. After each batch of training tasks, an LLM refiner contrasts trajectories that failed against ones that succeeded and proposes edits — add or delete a node or edge, revise an edge's condition/guidance/pitfall text. Those candidate edits are then gated: they're only committed if they match or beat the graph's prior performance on a held-out validation set, explicitly not the test set. Anything rejected gets logged in a rejection memory so the refiner doesn't keep re-proposing the same bad idea.
That four-step loop — diagnostic rollout, feedback-driven mutation, validation gating, rejection memory — is a small but disciplined piece of engineering. It's the same instinct as gating a model deploy on held-out eval regression, applied to a graph structure instead of weights. Anyone who has watched a "self-improving" agent system silently degrade because nothing checked its own edits will recognize why that gate exists.
What convinced me this isn't just self-evolution theater: on MultiChallenge, the loop was handed a flawed expert-authored graph and improved success from 58.93% to 92.86%, recovering from a bad human-designed prior. And starting from nothing and evolving from scratch (their "Mode 5") reached 78.79% F1 on HotpotQA, beating the hand-crafted graph outright. Both directions — fixing bad priors and bootstrapping from none — are evidence the mechanism is doing real work, not just overfitting to whatever structure it's handed.
What the numbers actually show
The evaluation spans seven benchmarks: HotpotQA (QA), MultiChallenge (dialogue), GDPval (professional tasks), ALFWorld (embodied control), τ-bench (customer service), BFCL v3 (function calling), and EnterpriseArena (long-horizon financial simulation) — against seven baselines including ReAct, MemoryBank, RAP, ExpeL, AutoGuide, AWM, and KnowAgent. Procedural Graphs ranked first or tied for first in 21 of 24 model-benchmark pairs, with a reported +9.00 points on BFCL v3 with Gemini 3.5 Flash and +7.41 on GDPval, and the aggregate advantage over memory-based baselines held at p = 4.3×10⁻⁴.
The result I'd flag to anyone building long-horizon agents is EnterpriseArena: full-horizon survival went from 44% to 58% with Claude Sonnet, and from 6% to 34% with Gemini 3.1 Pro. That's not a benchmark quirk — a 6-point baseline is a system that almost always collapses under delayed feedback and shocks, and a procedural map more than quintupling that is a genuinely different reliability regime, not a marginal accuracy bump.
Where this sits relative to agent memory
Most of what gets called "agent memory" today — summarization, trajectory retrieval, insight distillation — is memory of episodes: what happened last time. A Procedural Graph is closer to memory of structure: what's generally true about how this task decomposes, independent of any one episode. Both are useful and not mutually exclusive; the paper's baselines (RAP, ExpeL, AWM) are exactly this episodic-memory family, and PG beats them by supplying the piece they don't: an explicit, queryable model of legal and illegal transitions.
The authors are honest about the cost: guidance generation adds token overhead even when it cuts the number of solver steps, and they leave open how well a graph learned against one solver or tool interface transfers to another. For teams running agents against evolving tool sets, that transfer question is the one to watch — a graph tuned to your March API surface may not travel cleanly to your September one. Still, the core claim — that procedural knowledge deserves the same explicit, structured treatment factual knowledge already gets — is the right frame, and the self-correcting validation loop is what makes it credible rather than just another prompt-engineering layer.