Procedural Graph gives an LLM agent a queryable graph of “what to do next” nodes and edges, with a guidance model translating the local neighborhood into step-level advice; the graph edits itself by contrasting failed and successful runs against a held-out validation gate.
Say you’ve built an agent that plans monthly finance decisions or navigates a household simulator over dozens of steps. It works for the first ten actions, then it forgets it already checked the cash balance, calls tools out of order, or loops on the same failing action. The standard fix is ReAct: the model reasons, acts, observes, and repeats, with the entire history dumped into context. Every decision asks the LLM to re-derive “which step am I on and what’s admissible next” from a growing log.
Prior work patches this in a few ways. Memory methods store past trajectories or self-critiques as text (Reflexion is the canonical one) and retrieve them. Workflow methods hand-write state machines or flowcharts, which is rigid and labor-intensive. State-conditioned guideline methods retrieve rules like “in state X, do Y” but don’t connect successive steps. The gap the paper targets: an editable procedure representation whose guidance is conditioned on where the agent currently is.
The core analogy is a knowledge graph, but for procedures. A knowledge graph stores (entity, relation, entity) triples for factual questions. A Procedural Graph stores (procedure, relation, procedure) triples for “what to do next.” Nodes are tool calls, reasoning steps, or task states. Edges say node B is admissible after node A, and each edge carries three text fields: condition (when this transition fires), guidance (how to do it), and pitfalls (what to avoid). The graph lives outside model weights, so you can inspect and edit it.
At each step during execution, the framework does three things. First, locate: match the agent’s most recent action to a graph node. Second, extract: pull the 2-hop neighborhood around that node (or the whole graph if matching fails). Third, generate: a guidance LLM reads that subgraph plus the last few trajectory steps and writes a short situational hint. The hint is appended to the solver’s prompt. The solver still chooses freely; the guidance biases without dictating.
The graph is self-evolving offline. After a batch of training tasks, an LLM refiner compares high-scoring and low-scoring trajectories and proposes edits: add missing verification nodes, delete failure-inducing edges, revise edge attributes (implemented as delete-then-re-add). The candidate graph must pass structural checks (valid endpoints, every node reaches a terminal). Then a validation gate runs the candidate on a held-out set; if the score doesn’t match or beat the current graph, the edit is rolled back. Rejected candidates are logged into rejection memory so the refiner sees them as negative evidence next round.
G = initial_graph # can be empty skeleton or expert prior
S_val = evaluate(G, D_val)
rejected = []
for k in range(K):
traces = rollout(G, sample_batch(D_train))
edits = refiner(G, traces, rejected)
G_cand, structural_ok = apply(G, edits)
if not structural_ok:
rejected.append((edits, "structural_fail"))
continue
S_cand = evaluate(G_cand, D_val)
if S_cand >= S_val:
G, S_val = G_cand, S_cand
else:
rejected.append((edits, S_cand))
Across seven benchmarks (HotPotQA, MultiChallenge, GDPval, ALFWorld, \u03c4-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 cells against seven memory/workflow baselines including KnowAgent, AutoGuide, and AWM. Largest reported margins: +9.0 points on BFCL v3 with Gemini 3.5 Flash, +7.41 on GDPval with Gemini 3.1 Pro, +6.96 on tau-bench with the same model. HotpotQA margins are small (-0.9 to +1.3), so the gains are uneven across tasks.
On EnterpriseArena, a 132-month financial simulator with three scheduled crises, the agent must request capital 1-6 months before it runs out. PG raises full-horizon survival from 6% to 34% on Gemini 3.1 Pro and 44% to 58% on Claude Sonnet 4.6. The authors’ proposed explanation: PG-guided agents initiate fundraising during stable months, while unguided Gemini 3.5 Flash raises $0.00M on average versus $9.39M guided. Tool-call volume moves in both directions depending on model. It drops from 18.94 to 12.53 calls/month on Flash (redundant queries removed) but rises from 0.13 to 0.36 on Claude (forecast and market checks added before financing).
The construction ablation is informative. On MultiChallenge, initializing with a deliberately bad hand-crafted expert graph tanks success from 87.5% to 58.9%. A single offline update makes it worse (53.6%). But the full iterative loop recovers to 92.9%, above the unguided baseline. Starting from an empty skeleton with the evolution loop reaches 91.1% on the same task and 78.8% F1 on HotpotQA. So the self-evolution can repair a broken prior, not just refine a good one.
The efficiency ablation isolates two design choices: localized subgraph versus full graph, and generative guidance versus raw graph injection. Localized generative guidance wins on all three tested benchmarks and cuts tokens by 70.9% on ALFWorld versus feeding the full graph to the guidance LLM. Injecting the raw full graph directly into the solver actually hurts ALFWorld (72.6% to 70.3%), suggesting more structure is not always better if it’s undigested.
If you’re running a multi-step agent that loops or forgets which tools it already called, the takeaway is that a small explicit procedure graph (7-17 nodes for most tasks here, 131 for BFCL) plus per-step contextual guidance can meaningfully change behavior without fine-tuning. You’d need to define your node/edge schema and pick a hop radius. The paper uses 2 hops and a trajectory window of 3 recent steps.
The self-evolution loop is worth testing if you have a validation set with a clear score. Its practical value is that it can start from an empty skeleton, so you don’t have to author the procedure by hand. It can also fix a wrong hand-authored graph, which matters because your first guess about task structure is often wrong. Prerequisite: you need enough validation episodes for accept/reject decisions to be meaningful. The paper’s EnterpriseArena runs used only 20 episodes per split, and the authors explicitly caution that individual accept/reject decisions turn on one or two episodes and should be read as a search trace, not a significance test.
Worth testing before deploying: whether the guidance-call overhead is acceptable. Localized guidance still uses 33-55% more total tokens than no-graph on GDPval and ALFWorld even when it cuts solver steps, because you’re paying for an extra LLM call each step. The authors flag reusing or selectively firing guidance as future work.
A few things this paper does not establish. It doesn’t show transfer across solvers or tool interfaces (a graph evolved for one model on one tool set may not carry over). It doesn’t isolate which component of the guidance (condition, guidance, or pitfalls fields) drives the gains. And gains on a benchmark suite are not evidence of general reliability in production agents.
The validation gate depends on having a scorable held-out set; tasks without automatic scoring don’t get the self-correction property. Test-set statistics from the evolution study should be read as one search trace, not a distribution; the authors report the returned graph (85% survival) rather than the best round observed (95%) to avoid selecting on the test set, which is honest but reminds you the variance is real. Baseline rankings vary a lot across benchmarks and models, and HotpotQA margins are within noise, so “PG helps” is a claim about the aggregate pattern, not every setting. Finally, the guidance model and refiner share the underlying LLM with the solver in all experiments, so the paper doesn’t tell you whether a cheap guidance model can steer an expensive solver.