Large language models deployed as agents face a structural problem. They plan over long horizons and act through external tools, but they select actions through unconstrained generation over an accumulating history. The procedural knowledge of what to do, in what order, and under which conditions remains implicit. As trajectories get longer, agents lose track of their objectives, invoke tools out of order, and repeat actions that do not help. A new paper from researchers at Google, Georgia Tech, and Peking University proposes a fix: organize procedural knowledge into a graph, the same way knowledge graphs organize facts.
From What-Is to What-To-Do
A knowledge graph stores factual information as triplets: entity, relation, entity. It answers questions about what something is. A Procedural Graph stores task procedures the same way: procedure, relation, procedure. It answers questions about what to do next. The graph's nodes represent tool actions, reasoning steps, or task states. Its edges encode permissible transitions, each annotated with textual attributes describing the condition under which the transition applies, how to proceed, and what pitfalls to avoid.
Consider a financial planning task. An edge from cash flow forecast to fund raising request might carry the condition "projected runway falls below safety buffer," the guidance "submit early to allow for financing delivery delay," and the pitfall "do not stack a second request while one is pending." The graph lives outside the model weights, where it can be inspected, retrieved at each step, and edited without retraining.
How the Framework Works
The framework operates in two phases. During online inference, the graph is frozen. At each decision step, the system localizes the agent's active node by matching its most recent action to a node in the graph. It then extracts the two-hop neighborhood around that node and passes it, along with a recent window of trajectory steps, to a guidance language model. The guidance model translates the surrounding subgraph's attributes into step-level situational guidance that biases the solver's next action without dictating it.
The key insight is that retrieving connected neighborhoods beats retrieving isolated edges. If you retrieve guidance for a "submit" action without the preceding "check answer" transition, you miss the verification step that makes submission appropriate. The connected subgraph exposes both the action and its procedural prerequisites.
During offline self-evolution, an LLM refiner analyzes execution feedback. It compares failed trajectories with successful ones, identifies repeated error loops and multi-step reasoning shortcuts, and proposes edits to the graph's topology and attributes: adding missing nodes and edges, pruning ones that cause failure, and revising edge attributes. A validation gate checks whether the edited graph matches or improves performance on a held-out set. Rejected candidates are logged in a rejection memory that discourages the refiner from proposing equivalent unsuccessful edits in future rounds.
The loop starts from a minimal skeleton and builds graphs that match or surpass hand-designed ones. It can also repair a flawed expert prior, recovering from an initialization that initially reduces performance.
Results Across Seven Benchmarks
The paper evaluates Procedural Graphs on seven benchmarks: HotpotQA for multi-hop question answering, MultiChallenge for instruction retention across turns, GDPval for professional tasks scored against expert rubrics, ALFWorld for embodied household tasks, tau-bench for policy-compliant tool use, BFCL for function calling, and EnterpriseArena for long-horizon financial decision-making. Four LLMs were tested: Claude Sonnet 4.6, Gemini 3.1 Pro, Gemini 3.5 Flash, and Grok 4.1 Fast.
Procedural Graphs ranked first or tied for first in 21 of 24 model-benchmark settings. Compared to the strongest baseline in each setting, the framework recorded 19 wins, two ties, and three losses. The largest margins appeared on BFCL v3 with Gemini 3.5 Flash (67 percent versus 58 percent), GDPval with Gemini 3.1 Pro (78.78 versus 71.37), and tau-bench with the same model (80 percent versus 73.04 percent).
The baselines included Vanilla ReAct, MemoryBank, RAP, ExpeL, AutoGuide, AWM, and KnowAgent, all sharing the same ReAct solver and differing only in how procedural experience was stored and reused. No single baseline consistently placed second, suggesting that the combination of conditional guidance, reusable action sequences, and explicit transitions in a connected graph works across diverse settings.
Long-Horizon Survival
EnterpriseArena tests whether agents can manage company liquidity through 132 months of simulation with three undisclosed macroeconomic crises. The unguided Gemini 3.5 Flash baseline achieves zero percent full-horizon survival. Procedural Graph-guided Flash reaches 34 percent. On Claude Sonnet 4.6, survival rises from 44 percent to 58 percent. On Gemini 3.1 Pro, from 6 percent to 34 percent.
The mechanism is anticipatory fundraising. Because capital arrives one to six months after a request, surviving a crisis requires asking well before liquidity runs out. The unguided Flash baseline does not initiate fundraising early enough. PG-guided agents start requests during stable months. Average capital raised is zero for the unguided Flash baseline versus 9.39 million for PG-guided Flash and 30.11 million for PG-guided Grok 4.1 Fast.
Self-Evolution in Practice
Ten rounds of self-evolution on EnterpriseArena show how the graph improves incrementally. Round 1 discovers the sequential backbone: audit cash, forecast runway, then decide on financing. Validation survival jumps from zero to 45 percent. Round 2 adds a recall mechanism that reuses saved notes, lifting survival to 80 percent. Rounds 3 through 6 produce no committed update. Round 7 prunes a branch that causes failure. Round 8 introduces an administrative bypass. Validation survival reaches 90 percent in Round 8.
The test set distinguishes the returned graph from intermediate candidates. The returned graph achieves 85 percent test survival against the baseline's zero percent. The best single round during search reached 95 percent, but the authors report the former since quoting the latter would amount to selecting on the test set.
What This Means for Agent Builders
The paper addresses a practical problem that every team building LLM agents encounters: long-horizon tasks degrade as context grows. Memory-based approaches help but leave the solver to reconstruct how retrieved experience applies to the current step. Procedural Graphs make the transitions explicit and condition them on the agent's current position in the trajectory.
The self-evolution loop is the more interesting contribution for teams that do not want to hand-design procedural knowledge. Starting from a minimal skeleton, the system builds a graph that matches or exceeds what an expert would write. It can also repair a flawed expert prior, which matters because human-authored workflows often contain assumptions that do not hold in practice.
The guidance does increase token usage even when it reduces solver steps. On ALFWorld, localized guidance cuts the average number of solver steps from 21.84 to 18.80, but total token consumption remains 55.4 percent higher than the no-graph baseline. For teams optimizing cost per task, that tradeoff matters. The paper suggests future work on reusing guidance across steps or generating it selectively.
For developers building tool-using agents, the Procedural Graph is a concrete alternative to the current default of dumping everything into the context window and hoping the model figures it out. The code, graphs, and experimental results are available alongside the paper. The approach is straightforward to implement: define your procedures as triplets, build the guidance retrieval pipeline, and let the self-evolution loop handle the rest.