Last Updated: September 10, 2026
Google researchers just published a fix for one of the most expensive problems in AI agents: they forget what they are doing. The paper, Procedural Graphs: Self-Evolving Execution Structures for LLM Agents (arXiv 2609.09153, September 8, 2026), gives agents an explicit, editable graph of what to do, in what order, and under which conditions, then lets that graph improve itself from real execution results. The results are hard to ignore. The Procedural Graph ranked first or joint first in 21 of 24 benchmark and model combinations. In a long-horizon business simulation, it raised agent survival from 6% to 34% for Gemini 3.1 Pro, and it repaired a flawed expert-designed playbook by 33.93 percentage points. The core idea is one sentence long: treat procedural knowledge like a knowledge graph, but for actions instead of facts.
"If you build memory for long-horizon agents, this one is worth your time," says Omar Sanseviero, the AI researcher whose thread on the paper circulated widely this week. He also flagged the bigger implication: "Really nice to see how knowledge graphs are being explored in creative ways for agents."
The Problem: Today's Agents Wing It
In one paragraph: Most AI agents pick their next action by reading a growing log of everything they have done so far, then improvising. The rules of the task, the order of steps, and the conditions for each move are never written down anywhere. As the log grows, agents lose track of goals, call tools in the wrong order, and repeat actions that already failed. According to the Google research team, these documented failure modes (drift, planning hallucination, and repetitive loops) get worse exactly when tasks get longer and more valuable.
Picture a new employee with amnesia. Every morning they wake up, read their entire email history, and guess what to do next. That is roughly how a standard ReAct agent works: the model sees the query, the tool list, and an accumulating history of actions and observations, then free-form generates the next step. Nothing in that setup says "always check inventory before promising a delivery date" or "never file the compliance form twice."
The industry has three existing patches, and the paper tests all of them as baselines. Memory systems such as Reflexion and ExpeL write down lessons from past runs as free text and retrieve them into context. Guideline systems such as AutoGuide retrieve conditional rules for similar situations. Workflow systems such as AWM induce step-by-step procedures, but usually as rigid linear sequences. Each patch helps, yet each leaves the agent to reconstruct how the advice applies to the exact step it is on right now, and what can validly come after it.
In our own client work at Flowtivity, when we audit failing agent runs for growing businesses, the dominant pattern is exactly what this paper documents: repeated tool calls, out-of-order steps, and objectives that quietly drift as the context grows. We have started structuring repeat-run procedures as explicit transition instructions in agent prompts, and the reliability gain from making procedure explicit rather than implied is the cheapest upgrade we ship. That is why this paper matters beyond the lab: it is a formal, self-improving version of that fix.
The Big Idea: A Knowledge Graph for Actions
In one paragraph: A knowledge graph stores facts as (entity, relation, entity) triplets to answer what-is questions. A Procedural Graph stores know-how as (procedure, relation, procedure) triplets to answer what-to-do questions. Nodes are tool calls, reasoning steps, or task states. Edges say which step can follow which, using relations like LEADS_TO and TRIGGERS, and every edge carries three text fields: condition (when it applies), guidance (how to do it), and pitfalls (what to avoid). The whole graph lives outside the model weights, so you can inspect it, query it, and edit it without retraining anything.
The cleanest way to hold the idea is a two-column table:
| Approach | What it stores | How the agent uses it | Weakness |
|---|---|---|---|
| Vanilla ReAct | Nothing but the raw history | Re-derives everything each step | Drifts, repeats, loses the goal |
| Memory and reflection (Reflexion, ExpeL, MemoryBank) | Free-text lessons from past runs | Retrieves old text into context | Must reconstruct how it applies now |
| Guidelines (AutoGuide) | State-conditioned rules | Retrieves rules for similar states | Rules are not connected as a sequence |
| Workflows (AWM) | Linear step sequences | Follows the induced workflow | Rigid, mostly linear, often manual |
| Procedural Graph | (procedure, relation, procedure) triplets with condition, guidance, pitfalls | Localizes on the graph, reads the 2-hop neighborhood, gets step-level guidance | Guided but still free to reason |
Here is a real edge from the paper, in a financial planning example: (cash_flow_forecast, LEADS_TO, fund_raising_request). Its attributes read like a smart checklist entry. Condition: projected runway falls below the safety buffer. Guidance: submit the request early to allow for the financing delivery delay. Pitfalls: do not stack a second request while one is pending. Multiply that across a task domain and you have an operational playbook the agent can consult.
Notably, these graphs are small. According to the paper's Appendix B.4, every benchmark graph except BFCL v3 has between 7 and 17 nodes and 7 to 27 triplets, with four relation types: LEADS_TO, TRIGGERS, PROVIDES_INPUT_FOR, and CONVERGES_TO. This is not a giant knowledge base. It is a compact procedure map.
How It Works at Run Time: Like GPS, Not Autopilot
In one paragraph: At every decision step the framework runs three operations. Locate: match the agent's most recent action to a node on the graph. Extract: pull the surrounding subgraph, the 2-hop neighborhood of that node. Generate: a guidance model translates that subgraph plus the query and the last few trajectory steps into short situational advice, which is appended to the solver's prompt. The solver stays free to reason. The graph biases the choice, it does not dictate it. When matching fails, the agent sees the full graph instead.
The GPS analogy fits well. GPS tells you the next turn based on where you are right now, and it updates as you move. It does not drive the car. The guidance model does the same: it reads where the agent is on the procedure map, looks two transitions ahead (the paper's h = 2 setting), and writes one short block of advice such as "your immediate goal is to verify the invoice total; avoid re-querying the ledger, you already have the balance in context."
Why the neighborhood and not the whole graph? The ablation is decisive. Injecting the raw full graph helped on structured dialogue tasks but hurt embodied execution: ALFWorld success fell from 72.58 to 70.34, and full-graph generative guidance cratered it to 54.48 while burning more tokens. Localized guidance won everywhere, scoring 89.31 on MultiChallenge, 63.99 on GDPval, and 81.53 on ALFWorld, beating the best alternative in each setting by 2.0, 6.8, and 9.0 points respectively. Localization also cut tokens versus full-graph guidance by 70.9% on ALFWorld, 18.1% on GDPval, and 14.8% on MultiChallenge. Too much structure in context is its own failure mode.
How the Graph Rewrites Itself: A Coach Reviewing Game Film
In one paragraph: After each batch of training tasks, an offline LLM refiner compares failed trajectories with successful ones, finds repeated error loops in failures and useful shortcuts in wins, and proposes edits: add missing nodes or edges, delete ones that cause failures, rewrite edge attributes. Each candidate graph must pass structural validation, then survive a held-out validation set: it is committed only if validation performance holds or improves. Rejected edits go into a rejection memory so the refiner never re-proposes the same failed change. Nothing touches the model weights.
Think of a coach reviewing game film between matches. The coach watches what worked and what collapsed, then updates the playbook. But this coach has a rule: new plays only stick if the team wins a scrimmage on a field the coach did not practice on. That held-out validation set is what stops the loop from overfitting to its own training tasks, and the rejection memory stops the assistant coaches from proposing the same bad play every week.
The evolution trace on the long-horizon benchmark is worth reading like a story. In Round 1, the refiner discovered the sequential backbone, audit cash and forecast runway before any financing decision, and validation survival jumped from 0.0% to 45.0%. In Round 2, it added a recall_notes step to reuse saved notes, lifting survival to 80.0% while cutting tool usage from 17.23 to 3.08 calls per month. Rounds 3 through 6 committed nothing (one candidate failed structural checks before it even ran). Round 7 pruned a failing branch, Round 8 pushed validation survival to 90.0%, and Round 10 was rejected, ending the loop. The returned graph scored 85.0% test survival against a baseline of 0.0%, a result the paper reports with Fisher's exact test at p = 0.000000026.
The Numbers: 21 of 24 First-Place Finishes
In one paragraph: Across seven benchmarks (HotpotQA, MultiChallenge, GDPval, ALFWorld, tau-bench, BFCL v3, EnterpriseArena) and four LLMs (Claude Sonnet 4.6, Gemini 3.1 Pro, Gemini 3.5 Flash, Grok 4.1 Fast), the Procedural Graph ranked first or joint first in 21 of 24 settings: 19 wins, 2 ties, 3 losses against the strongest baseline in each setting, with a binomial sign test at p = 0.00043. The biggest single wins were +9.0 points on BFCL v3 function calling, +7.41 on GDPval professional tasks, and +6.96 on tau-bench customer service tool use.
The headline table from the paper, condensed:
| Task (model) | Best baseline | Procedural Graph | Gain |
|---|---|---|---|
| BFCL v3, function calling (Gemini 3.5 Flash) | 58.00% | 67.00% | +9.00 pts |
| GDPval, professional work tasks (Gemini 3.1 Pro) | 71.37 | 78.78 | +7.41 pts |
| tau-bench, customer service (Gemini 3.1 Pro) | 73.04% | 80.00% | +6.96 pts |
| EnterpriseArena survival (Gemini 3.1 Pro) | 6.0% | 34.0% | +28.0 pts |
| MultiChallenge, expert prior repaired (Claude Sonnet 4.6) | 58.93% | 92.86% | +33.93 pts |
Two honest caveats from the data. First, no single baseline consistently ranked second, which tells you the field is far from settled. Second, HotpotQA margins stayed small, from minus 0.90 to plus 1.30 points, so on straightforward multi-hop search the structure buys you little. The gains concentrate where procedure matters: tool use, ordering constraints, long horizons.
The CFO Test: Why Waiting Until You Are Broke Fails
In one paragraph: In EnterpriseArena, agents act as financial decision makers for up to 132 simulated months under liquidity constraints, with three macroeconomic crises they are not told about. Capital arrives one to six months after it is requested, so survival requires fundraising before cash runs out. Procedural Graph agents learned anticipatory fundraising. The unguided Gemini 3.5 Flash baseline raised $0.00M on average and died; PG-guided Flash raised $9.39M, and PG-guided Grok 4.1 Fast raised $30.11M. Survival rose for every model tested.
This is the experiment to show any executive. Full-horizon survival went 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, where PG also delivered the best average enterprise score at $39.62M.
The mechanism is visible in the traces, and it is not "work harder." Guidance changed which tools got called and when. The unguided Gemini 3.5 Flash spun in place, querying cash and market state 18.94 times per month. The graph-guided version cut that to 12.53 calls per month while scoring better. On Claude and Gemini 3.1 Pro, tool calls actually went up (from 0.13 to 0.36 and from 0.89 to 3.18 per month) because the graph pushed them to run forecasts and market checks before financing decisions. Fewer wasted steps for one model, more necessary preparation for others: the graph was correcting opposite pathologies.
From Scratch Beats Hand-Designed (and Repairs Bad Experts)
In one paragraph: The paper compares five construction modes, from a fixed hand-crafted expert graph to full self-evolution from a minimal skeleton. Evolution from scratch won on HotpotQA with 78.79% answer F1 and 66.30% EM, gains of 7.58 and 7.50 points over the unguided baseline. On MultiChallenge, expert plus evolution scored best at 92.86%, with the from-scratch graph close behind at 91.07%. Most striking: a flawed expert graph dropped success from 87.50% to 58.93%, and the evolution loop recovered it to 92.86%, a 33.93 point repair.
That repair result deserves a moment. The hand-crafted expert graph actively hurt performance (87.50% down to 58.93%). A single one-shot offline update made it worse still (53.57%). Only the iterative loop, fresh execution feedback plus validation gating, climbed back to 92.86%. The lesson for anyone shipping agent playbooks: your expert-written procedure is a hypothesis, not an asset, until execution data has vetted it. The appendix also reports a 45.7% reduction in parsing failures with evolved graphs, which compounds the headline scores.
What This Means If You Build or Buy Business Agents
In one paragraph: Treat procedure as a first-class, versioned artifact. Write your agent's rules of engagement as condition, guidance, and pitfalls on transitions between steps, not as a wall of prose in a system prompt. Log every run with its outcome, mine failures against successes periodically, propose playbook edits, and gate every edit on a held-out sample of real tasks before it goes live. The paper's evidence says this loop is automatable with the same LLM that runs the agent, no retraining required.
Practical translation, in rough order of payoff:
- Externalize the playbook. If your agent's procedure lives in a 4,000-word prompt, start moving it into structured transitions with explicit conditions. Compact graphs (7 to 27 triplets in the paper) were enough to win benchmarks.
- Guide, do not chain. Hard-coded state machines remove the model's judgment. The soft guidance pattern (advice appended to context) beat raw graph injection in every ablation and kept the agent able to reason around novel situations.
- Localize. Give the agent the neighborhood of where it is, not the entire rulebook. The full-graph variants lost up to 18 points on embodied tasks.
- Evolve with a gate. Batch review of failures versus wins, small edit sets, and a holdout set you never train on. Rejected edits go on a do-not-retry list.
- Watch the token bill. Guidance cut solver steps (28.20 to 18.57 on GDPval) but total tokens still rose 33.4% to 55.4% versus the no-graph baseline. Budget for it.
Limitations Worth Knowing Before You Bet the Roadmap
In one paragraph: The Procedural Graph is not free and not universal. Token consumption rose by a third to more than half versus no-graph baselines despite fewer steps. Gains on simple search tasks (HotpotQA) were marginal. Accept and reject decisions during evolution can turn on one or two episodes when validation sets are small, which the authors honestly describe as a search trace rather than significance testing. And transfer, whether a graph learned with one solver or tool interface helps another, remains an open question the paper flags for future work.
The authors also note the natural next step: generating guidance selectively, or reusing one guidance block across several steps, to close the cost gap. If you are evaluating this for production, the honest summary is: strong evidence for procedure-heavy, tool-heavy, long-horizon work; marginal for simple lookups; real but manageable cost overhead.
The Verdict
Every agent framework right now is wrestling with the same trade-off: structure improves reliability but kills adaptability, and free-form generation keeps adaptability but fails repeatably. The Procedural Graph threads that needle by making the structure soft (translated into natural-language guidance at each step), local (2-hop neighborhoods), and improvable (an evolution loop with a validation gate). First or joint first in 21 of 24 settings, CFO survival multiplied several-fold, and bad expert playbooks automatically repaired. For anyone building agents that must run long, multi-step processes with tools, this is one of the most directly applicable papers of the year.
Written by AJ Awan. Former EY management consultant, TOGAF certified enterprise architect, founder of Flowtivity, where we design and ship AI agent systems for growing businesses.
