Google's Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

Problem: Implicit Procedural Knowledge in LLM Agents

Current LLM agents operate by accumulating a growing context of past actions and observations, then letting the model freely predict the next tool call, order, and conditions. As trajectories lengthen, agents inevitably lose goals, invoke tools out of order, and repeat useless actions. These failures stem from the absence of an explicit representation of procedural knowledge — what to do, in what sequence, and under what conditions.

Solution: Procedural Graphs (PG)

The paper Procedural Graphs: Self-Evolving Execution Structures for LLM Agents (arXiv:2609.09153) proposes Procedural Graphs , a structure analogous to knowledge graphs but for actions. While knowledge graphs use (entity, relation, entity) triplets to answer "what is", procedural graphs use (procedure, relation, procedure) triplets to answer "what to do".

Graph Structure

Nodes : a tool call, a reasoning step, or a task state.

Edges : allowed transitions, each annotated with three text fields: condition — when to traverse this edge. guidance — how to execute the step. pitfalls — what mistakes to avoid.

Example from a financial scenario: an edge (CashFlowForecast, LEADS_TO, FinancingApplication) carries condition "predicted runway below safety buffer", guidance "submit application early due to funding delay", and pitfalls "do not stack a second application while one is in flight".

Online Inference: Locate → Extract → Generate

The graph lives outside model weights, so it can be inspected and edited without retraining. At each step:

Locate : map the agent's last action to a node in the graph.

Extract : retrieve the 2-hop connected neighborhood of that node.

Generate : a guidance model translates the local subgraph into a contextual prompt that biases (not commands) the solver model's next decision, preserving reasoning freedom.

Offline Self-Evolution with Validation Gate and Rejection Memory

The graph evolves through a closed loop:

A refiner proposes edits (add nodes/edges, rewrite fields) based on collected trajectories.

Each candidate graph must pass a validation gate : evaluated on a held-out set; only non-regressing graphs are accepted.

Rejected edits are stored in a rejection memory along with the trajectory and validation result, then fed back to the refiner as negative evidence to prevent repeating the same mistake.

CFO Simulator Case Study: From Empty Graph to 85% Survival

Starting from a skeleton graph with only Start → End, the baseline agent achieved 0% survival (average lifespan 34.8 months). After 10 evolution rounds:

Final graph reached 85% survival on the test set (Fisher exact test p = 2.6×10⁻⁸).

Tool calls per month dropped from 17.23 to 3.08 (81.8% reduction) while scores improved.

Round 3 illustrates the validation gate's necessity: a mutation lowered the cash threshold for triggering financing, which helped on the training set but caused premature equity dilution and cash shortage on the validation set, dropping survival by 15 points. The gate rejected it. The authors note the validation set had only 20 episodes, so accept/reject decisions should be read as traces of the search process rather than formal significance tests.

Main Experimental Results: 7 Benchmarks, 4 LLMs

All models shared the same ReAct solver; only the experience storage and retrieval mechanism varied. PG was tested on 7 benchmarks with 4 LLMs (Claude Sonnet 4.6, Gemini 3.1 Pro, Gemini 3.5 Flash, Grok 4.1 Fast), yielding 24 model–benchmark combinations.

PG achieved 21 first-place or tied-first finishes out of 24.

Against the strongest baseline per setting: 19 wins, 2 ties, 3 losses (sign test p = 4.3×10⁻⁴).

Largest margins: BFCL v3 multi-turn function calling (+9.00) , GDPval professional tasks (+7.41) , τ-bench policy-compliant tool use (+6.96) .

Long-Horizon Resilience: 132-Month Simulation with Three Crises

In an extended EnterpriseArena simulation (132 months, three crises), PG improved or maintained full-horizon survival for all four models:

Claude Sonnet 4.6: 44% → 58%

Gemini 3.1 Pro: 6% → 34%

Grok 4.1 Fast: 26% → 40%

The key behavioral difference was early financing : capital applications take 1–6 months to arrive. The unguided Flash baseline averaged $0 raised, while the PG-guided Flash secured $9.39M .

Paper Reference

Procedural Graphs: Self-Evolving Execution Structures for LLM Agents
https://arxiv.org/abs/2609.09153