Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

AI summary

Overview

Research area: LLM agent architectures, specifically the representation and reuse of procedural knowledge (how to act, in what order, under what conditions) for long-horizon tool-using agents.

Technical level: Intermediate. The paper assumes familiarity with ReAct-style agent loops, in-context memory, and graph representations, but the core idea is explainable without deep mathematics.

Scope: The paper proposes the Procedural Graph, an editable directed graph of attributed procedural triplets that supplies step-level guidance to an LLM agent during execution and rewrites itself offline from execution feedback, evaluated across seven benchmarks and four LLM families.

What This Paper Is About

Most LLM agents decide their next action by free-form generation over a growing log of past actions and observations, which leaves the procedural knowledge of what to do next implicit and makes agents prone to losing objectives, calling tools out of order, or looping unproductively as trajectories lengthen. The authors introduce the Procedural Graph (PG), a directed graph whose (procedure, relation, procedure) triplets mirror the (entity, relation, entity) structure of a knowledge graph, but answer what-to-do questions instead of what-is questions. The goal is a procedure representation that constrains invalid behavior while preserving reasoning freedom, adapts to the agent's current progress, and improves itself from experience without retraining model weights.

Key Contributions

1. The Procedural Graph representation. An explicit, editable, directed attributed graph where nodes abstract tool calls, skills, reasoning steps, or task states, and edges encode admissible transitions annotated with textual attributes (condition, guidance, pitfalls). The graph lives outside model weights, so it can be inspected, retrieved, and edited.

2. Generative PG Guidance. An online inference mechanism with three operations — locate, extract, generate. It matches the agent's most recent action to a graph node, extracts the two-hop neighborhood, and uses a guidance LLM to translate static edge attributes into situational, step-level guidance that biases but does not dictate the solver's next action.

3. A self-evolution loop. An offline process in which an LLM refiner contrasts failed with successful trajectories, proposes topology edits (adding missing verification nodes or edges, deleting failure-inducing ones) and attribute revisions, and commits candidates only when a held-out validation score does not decrease. Rejected candidates enter a rejection memory that discourages repeated unsuccessful proposals.

4. Empirical validation across construction strategies. Demonstrations that evolution from a minimal skeleton matches or surpasses hand-designed graphs, and that the loop can repair a flawed expert prior that initially degrades performance.

Main Findings

• Consistent benchmark gains. PG ranks first or joint first in 21 of 24 model–benchmark settings. Against the strongest baseline in each setting it records 19 wins, 2 ties, and 3 losses (one-sided exact binomial sign test excluding ties, p = 4.3 × 10⁻⁴). Largest margins: BFCL v3 with Gemini 3.5 Flash (67.00% vs 58.00%), GDPval with Gemini 3.1 Pro (78.78 vs 71.37 rubric score), and τ-bench with Gemini 3.1 Pro (80.00% vs 73.04% Pass@1).

• Task-dependent gain magnitude. HotpotQA margins over the strongest baseline range from −0.90 to +1.30 points, while GDPval and BFCL v3 show gains across all four LLMs. No single baseline consistently places second.

• Long-horizon survival in EnterpriseArena. PG achieves the highest or joint-highest full-horizon survival across all four LLMs, raising survival from 44.0% to 58.0% for Claude Sonnet 4.6, from 6.0% to 34.0% for Gemini 3.1 Pro, and from 26.0% to 40.0% for Grok 4.1 Fast.

• Behavioral change, not just volume change. Guidance alters which tools are called and when. Gemini 3.5 Flash reduced calls from 18.94 to 12.53 per month while improving enterprise score; Claude Sonnet 4.6 and Gemini 3.1 Pro increased calls from 0.13 to 0.36 and 0.89 to 3.18 per month respectively. Across all four models, the behavior that tracks survival is anticipatory fundraising — requesting capital months before liquidity runs out. Average capital raised was $0.00M for the unguided Flash baseline versus $9.39M for PG-guided Flash.

• Evolution from scratch beats expert priors. On HotpotQA, "Scratch + Online Evolution" achieved the best result (78.79% Ans F1, 66.30% Ans EM, gains of 7.58 and 7.50 points over unguided). On MultiChallenge, "Expert + Online Evolution" reached 92.86% overall.

• Repair of a harmful expert prior. On MultiChallenge, a hand-crafted expert graph lowered success from 87.50% to 58.93%; a single static update lowered it further to 53.57%; the iterative configuration recovered to 92.86% — a 33.93-point gain over the expert initialization.

• Self-evolution dynamics. Over ten rounds on EnterpriseArena, validation survival went from 0.0% to 90.0%. Round 1 discovered the sequential backbone (audit cash, forecast runway, then finance), producing the largest single jump (0.0% to 45.0%). Round 2 added recall_notes, lifting survival to 80.0% and cutting tool usage from 17.23 to 3.08 calls per month. Rounds 3–6 committed no update. The returned graph reached 85.0% test survival versus 0.0% for the baseline (Fisher's exact p = 2.6 × 10⁻⁸); the best single observed round reached 95.0%, but the authors report the former to avoid selecting on the test set.

• Localized subgraph guidance wins on efficiency. Given the same graph, localized generative guidance achieved the highest performance on MultiChallenge (89.31), GDPval (63.99), and ALFWorld (81.53), exceeding the best alternative in each setting by 2.0, 6.8, and 9.0 points. It reduced tokens relative to full-graph generative guidance by 70.9% on ALFWorld, 18.1% on GDPval, and 14.8% on MultiChallenge, and shortened average solver steps on GDPval (28.20 to 18.57) and ALFWorld (21.84 to 18.80).

• Raw graph injection is not enough. Injecting the raw full graph helped MultiChallenge (80.27 to 86.60) but hurt ALFWorld (72.58 to 70.34). Full-graph generative guidance dropped ALFWorld to 54.48 while consuming more tokens — evidence that topological context matters more than graph size.

• Token overhead persists. The extra guidance call leaves total token consumption 33.4% higher on GDPval and 55.4% higher on ALFWorld than the no-graph baseline, even where solver steps fall.

Methodology in Plain English

The authors separate an agent's procedural knowledge from its model weights and store it in a graph. Each node is an abstract action or state — a tool call, a reasoning step, a task status. Each directed edge means "this node is admissible after that node," and carries three text fields describing when the transition applies, how to proceed, and what to avoid. A worked example from financial planning: the edge from cash_flow_forecast to fund_raising_request carries the condition "projected runway falls below the 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."

At each decision step during solving, the graph is frozen. The system matches the agent's most recent action to a node, pulls the two-hop neighborhood around that node (falling back to the full graph if matching fails), and passes that neighborhood plus the last three trajectory steps to a guidance LLM. That model converts the static edge attributes into concrete advice for the current situation, which is appended to the solver's prompt. The solver remains free to choose — guidance biases rather than dictates.

Offline, after each batch of training tasks, an LLM refiner compares high-scoring and low-scoring trajectories, looking for repeated error loops in failures and multi-step shortcuts in successes. It proposes structured edits: add missing nodes or edges, delete ones that steer trajectories into failure, or delete-and-re-add an edge with revised attributes. The candidate graph is applied to a copy, structurally checked, and evaluated on a held-out validation set. It is committed only if the validation score matches or exceeds the current graph's cached score. Rejected candidates, their edits, and the associated trajectories are logged as negative evidence for the next round, so the refiner avoids resubmitting failed ideas.

The experiments hold the solver fixed — an identical ReAct loop — and vary only how procedural experience is stored and reused, comparing against seven baselines ranging from no memory to textual rules and induced workflows.

Why This Matters

Impact on research. The paper makes an argument that procedural memory — the quadrant of the CoALA taxonomy (working, episodic, semantic, procedural) that has received the least explicit treatment — deserves its own structured, editable representation. It connects the knowledge-graph idiom to agent planning and shows that procedural structure can be learned and revised from execution feedback without gradient updates, positioning graph editing as an alternative to fine-tuning. The demonstration that a flawed expert prior can be repaired by the same loop is a useful data point for anyone assuming human-authored procedures are a safe starting point.

Real-world applications:

• Financial operations and treasury management. The EnterpriseArena results center on anticipatory fundraising under delayed capital arrival and undisclosed macroeconomic shocks. The same pattern — a graph that forces runway forecasting and early financing requests — applies to corporate cash management and lending workflows.

• Customer-facing tool-use agents. τ-bench and BFCL v3 measure policy-compliant tool use and multi-turn function calling, the exact setting of support bots and account-management assistants where out-of-order tool calls create compliance problems.

• Multi-turn instruction-following systems. MultiChallenge tests retention of constraints across conversation turns, relevant to any assistant that must hold several user requirements simultaneously over a long dialogue.

• Embodied and robotic task execution. ALFWorld's strict action ordering resembles household or warehouse robotics, where calling a manipulation step before a verification step corrupts the task.

Industry relevance. The graph is cheap to inspect, edit, and version without retraining, which suits organizations that need auditable agent behavior and regulatory review of decision sequences. The self-evolution loop reduces dependence on scarce expert procedure authors. The caution is cost: guidance calls add 33–55% token overhead on two benchmarks, so production deployment requires deciding when procedural guidance is worth the extra inference.

Future Directions

• Reducing guidance cost. The paper acknowledges that guidance increases token use even when it reduces solver steps. Reusing guidance across consecutive steps or generating it selectively — only at procedurally ambiguous decision points — is the obvious next lever.

• Cross-solver and cross-tool transfer. Whether a graph evolved with one solver transfers to another, or to a different tool interface, is untested. Reusable procedures would be far more valuable than solver-specific ones.

• Statistical rigor in the evolution loop. With roughly 20 episodes per split, individual accept/reject decisions turn on one or two episodes. Larger validation sets, or a gate that accounts for evaluation noise, would make the search trace more trustworthy.

• Graph scope and generalization beyond the training distribution. The benchmarks are bounded task domains with defined tool sets. How the representation scales to open-ended domains with thousands of tools, and whether it degrades gracefully when the graph is sparse or the match step fails, remain open.

Target Audience

Researchers and engineers building LLM agent systems who need reliable multi-step tool orchestration beyond flat memory and prompt-based guidelines. The paper is most useful to practitioners evaluating whether explicit procedural structure is worth the inference overhead, and to researchers working on agent memory taxonomies, self-improving agents, and the boundary between learned weights and editable external knowledge. Readers without prior exposure to ReAct loops and memory baselines should start with the related-work section first.

Authors’ abstract

Large language models are increasingly deployed as agents that plan over long horizons and act through external tools. Most agents select actions through unconstrained generation over an accumulating history, leaving implicit the procedural knowledge of what to do, in what order, and under which conditions. As trajectories lengthen, agents can lose track of their objectives, invoke tools out of order, and repeat unproductive actions. We introduce the Procedural Graph: just as a knowledge graph organizes factual knowledge into (entity, relation, entity) triplets for what-is questions, a Procedural Graph organizes procedural knowledge into (procedure, relation, procedure) triplets for what-to-do questions. At each decision step, the framework localizes the agent's active node, and a guidance model translates the surrounding subgraph into step-level situational guidance that biases the solver's next action without dictating it. The graph is self-evolving: an LLM refiner contrasts failed trajectories with successful ones and edits the graph's topology and attributes, committing edits that preserve or improve held-out validation performance while retaining rejected ones to discourage repetition. Starting from a minimal skeleton, the loop builds graphs that match or surpass hand-designed ones. It can also repair a flawed expert prior. Across multiple datasets, task types, and LLMs, the Procedural Graph delivers consistent gains over memory-based baselines, and self-evolution further improves performance without manual engineering.