Google's Procedural Graphs Give AI Agents an Editable Answer to What To Do Next

Last Updated: 2026-09-10

A Google research team has published a method called the Procedural Graph: an explicit, editable graph of "what to do next" knowledge that steers an AI agent through long tasks, and rewrites itself from the difference between the agent's failures and its successes. In the paper's benchmarks, agents guided by the graph finished first or joint first in 21 of 24 model-and-task settings, beating memory-based alternatives, and the improvement cost nothing in retraining because the procedure lives outside the model.

The Problem: Agents Forget Their Own Procedure

According to the paper, published on arXiv on 8 September 2026 by Yuxing Lu, Yicheng Chen, Shanchan Wu and Sercan Arık of Google with colleagues at Georgia Tech and Peking University, most current agents make decisions through what the authors call unconstrained generation: at every step, the model re-reads a flat, growing log of everything it has done so far and freely generates its next action. Nothing in that log says what should come next, in what order, or under which conditions. The documented consequences are the familiar ones for anyone who has watched an agent work on a long task: the paper lists agents losing track of their objectives, invoking tools out of order, and repeating unproductive actions as trajectories lengthen.

The reason is structural rather than a defect of any particular model. Procedural knowledge, the answer to what-to-do questions, exists in these systems only implicitly, spread across the running conversation. A knowledge graph solved the equivalent problem for facts: it stores what-is knowledge as entity-relation-entity triplets that a system can query instead of re-deriving. The paper's core move is to build the same kind of structure for procedure. A Procedural Graph stores what-to-do knowledge as procedure-relation-procedure triplets: this step leads to that step, under this condition, with this guidance and these known pitfalls attached to the transition.

Two properties of the design matter more than the graph itself. First, the procedure lives outside the model's weights, so it can be inspected, edited and corrected without any retraining, the same way a good runbook sits beside the process it describes rather than inside the heads of the people running it. Second, the guidance it produces is a bias, not a command: at each step, a guidance model reads the relevant corner of the graph and offers the agent situational advice, and the agent remains free to deviate when the graph is wrong.

What the Paper Actually Measured

The evaluation covers six benchmarks and four model families, all driving the same ReAct-style solver: Claude Sonnet 4.6, Gemini 3.1 Pro, Gemini 3.5 Flash and Grok 4.1 Fast. The benchmarks span multi-hop research questions with search tools, instruction retention across long conversations, professional tasks scored against expert rubrics, household tasks with strict action ordering, policy-compliant tool use under live user interaction, and multi-turn function calling. According to the paper, the Procedural Graph ranked first or joint first in 21 of 24 model-benchmark settings, and against the strongest baseline in each setting it recorded 19 wins, two ties and three losses, a result the authors report as statistically significant.

The margins where the graph helps most are the settings where procedure is exactly what is being tested. On BFCL v3, the function-calling benchmark, the graph lifted Gemini 3.5 Flash from 58.00% to 67.00%, a gain of nine points. On GDPval, the professional-tasks benchmark scored against expert rubrics, Gemini 3.1 Pro moved from 71.37 to 78.78 with the graph, and on τ-bench, which tests policy-compliant tool use in live interaction, the same model went from 73.04% to 80.00%. In every case the solver model was unchanged; the only addition was the graph and the guidance drawn from it.

The Self-Evolution Loop: The Graph Learns From Failures

The second half of the paper is what separates this from a well-designed static workflow. After each batch of tasks, an LLM refiner reads the diagnostic traces from both failed and successful runs, finds the repeated error loops in the failures and the shortcuts in the successes, and proposes concrete edits to the graph: adding a missing verification step, deleting a transition that keeps steering runs into failure, or rewriting the guidance attached to an edge.

Crucially, no edit is trusted on its own word. Every proposed graph is a candidate, and a candidate is committed only if it matches or improves performance on a held-out validation set the refiner never trained on. Candidates that fail the gate are not deleted: they are logged in what the paper calls rejection memory, so the refiner does not waste later rounds proposing the same change again. The result is a loop that improves from experience while structurally unable to adopt a change that made things worse on unseen tasks.

The Loop Can Repair a Bad Human Prior

The paper includes a result that anyone who has ever written procedures for a living should sit with. When the evolution loop starts from a deliberately flawed expert-designed graph, it does not preserve the flaw: it corrects it, and in the paper's financial-planning example the first evolution round alone lifted the validation survival rate from 0.0% to 45.0%. Started instead from a minimal skeleton, the loop built graphs that matched or surpassed hand-designed ones. The authors' framing is measured, but the implication for procedure design generally is pointed: an experienced person's idea of the right sequence, written down before any evidence arrives, is a hypothesis, and a loop that tests procedures against execution can out-design the expert it started from.

The Honest Limit Is Cost, Not Capability

The paper is unusually direct about its own trade-off, stating plainly in the conclusion that guidance increases token use even when it reduces solver steps. Reading the guidance, localising the agent in the graph and generating situational advice all consume input tokens on every step, so a run can finish in fewer actions and still burn more tokens than an unguided one. That is not a hidden weakness; it is the standard shape of the trade between reliability and cost in agent design, and it is better stated than glossed. It also means the method's economics are task-dependent: on a benchmark scored by success rate, a nine-point gain justifies extra tokens easily. On a high-volume routine workflow, the arithmetic has to be done per task, and the paper does not pretend otherwise.

What This Signals Beyond the Benchmark Numbers

The interesting line in this paper is not the leaderboard position. It is where the authors chose to put the knowledge: in an inspectable, editable artefact outside the model, checked against measured outcomes before any change to it is accepted, with failed changes kept on record so they are not silently re-proposed. Those are the properties of a controlled process, and they are the same properties that make any workflow, automated or human, trustworthy to someone who did not design it.

For a business owner watching agent capabilities improve month to month, that is the part worth noticing. The direction of travel in agent research is away from improvisation and toward documented, testable procedure: agents that follow a written sequence, log what happened, and change the procedure only when the evidence says the change works. A business that has already written its key processes down, named their owners and recorded what changed is structurally ready for that kind of agent. A business that runs on one person's memory will need the same work done eventually, and the graph will not do it for them.

Sources

• Lu, Y., Chen, Y., Wu, S. & Arık, S. (Google; with Georgia Tech and Peking University), "Procedural Graphs: Self-Evolving Execution Structures for LLM Agents", arXiv:2609.09153, submitted 8 September 2026: https://arxiv.org/abs/2609.09153