An editable graph of next steps beats memory for long-horizon agents

When an agent's memory isn't enough

AI agents have a recurring problem. While the task is short, everything looks fine. The model reads the history, picks the next step, calls a tool, moves on. But once the horizon gets long, things start to break: the agent confuses the order of actions, repeats useless steps, forgets what it has already tried, and does too late what it should have done early.

A new paper from Google, Georgia Tech and Peking University offers a practical idea for this: don't keep the procedure in the text of the history alone, but move it out into a separate graph of actions. The authors call it a Procedural Graph; from here on we'll just say procedural graph.

The point is simple. A knowledge graph answers the question "what is this?". A procedural graph answers the question "what do I do next?". For AI agents that distinction is a useful one.

The paper's idea in one picture: a knowledge graph stores facts, a procedural graph stores sequences of actions.

If you build AI agents with tools, long scenarios and multi-step logic, this matters. In systems like these the model doesn't only get the content of the answer wrong. It often gets the order of actions wrong. And that is a problem of procedural organization.

What a procedural graph is

The authors propose storing procedural knowledge as triples. But where a knowledge graph holds something like "Paris — capital of — France", here the triple is different: "procedure — relation — next procedure".

The nodes of the graph are actions, states or reasoning steps. The edges are the transitions allowed between them. And every transition carries text fields:

🟠 condition — when this transition applies

🟠 prompt — what exactly to do

🟠 mistakes — what not to do

In the financial simulator, for instance, the transition from a cash-flow forecast to a funding request can carry a rule like this: if the cash buffer is about to run out, file the application early, because the money won't arrive immediately; don't file a second application while the first is still being processed.

The central claim of the paper: procedural knowledge lives outside the model's weights. You can inspect it, edit it, check it, extend it, even correct it from execution logs. Without fine-tuning the model.

How it works at inference time

While it is solving a task, the agent never receives the whole graph. That would be too noisy and too expensive. Instead the system does three things:

🟣 locates where the agent currently is in the graph

🟣 pulls out the local neighborhood of that node

🟣 asks a separate LLM to turn that slice of the graph into a short situational prompt

The agent is not handed a fixed route. It is given local guidance for the next step. The authors don't build a rigid state machine that forbids every deviation. They leave the model its freedom to reason and add structural scaffolding around it.

The overall scheme: the graph suggests the next step at inference time, then updates itself from execution logs.

In practice it looks like this. If the agent has just called a search tool, the system matches that call to a node in the graph, takes the nearest 2 steps ahead and writes a prompt along the lines of: first check the retrieved passages, then identify the bridging concept, don't submit an answer without verifying it.

Why is a local subgraph better than the full one? Because the full graph carries far too much that is irrelevant. The authors checked this in a separate ablation. Generating the prompt locally came out ahead both on quality and on token cost, compared with generating from the whole graph at once.

The mechanics in short:

🟠 The graph doesn't do the agent's reasoning for it

🟠 The graph sets out the allowed transitions and the typical mistakes

🟠 The prompt is tied to the agent's current progress

🟠 If the step can't be matched to the graph, the system can fall back on the whole graph

The main difference from memory and text rules

Plenty of agents already use memory today. They store past trajectories, short summaries, rules in plain text, sometimes whole pipelines. But nearly all of these methods leave one problem in place: the model still has to reconstruct the structure of the procedure itself out of text.

The procedural graph makes it explicit.

Instead of a list of memories or a set of rules, the system knows:

🟣 which steps usually follow which

🟣 which transitions are allowed

🟣 under what conditions a transition applies

🟣 which mistakes are typical at this particular point

That is especially useful where the point isn't just calling the right tool, but calling it at the right moment.

A graph that corrects itself

The most interesting part of the paper is the graph's self-evolution. After a batch of tasks the system takes the successful and the failed trajectories, compares them and asks an LLM editor to propose changes to the graph.

It can:

🟠 add a missing node

🟠 add a new transition

🟠 delete a transition that often leads to a dead end

🟠 rewrite a transition's attributes: condition, prompt, mistakes

But there is a safety catch here. A change isn't accepted automatically. The new graph is run through a separate validation. If quality hasn't dropped, the edit is kept. If it has, the graph is rolled back.

The system also keeps a memory of rejected edits, so it doesn't propose the same failed changes over and over.

In AI agents there is a lot of talk about "self-improvement" and not much machinery that keeps a system from wrecking itself. Here that machinery exists: the editor proposes, validation decides.

What the experiments showed

The authors tested the approach on seven benchmarks. They cover multi-hop question answering, multi-turn dialogue, function calling, robotics tasks and a financial simulator that runs for 132 months.

The headline result is this: the procedural graph consistently beats memory-based methods.

In the main summary table the method took first or joint first place in 21 of 24 model-and-benchmark combinations. Measured against the best baseline in each case, that comes to 19 wins, 2 ties and 3 losses.

The results in short:

🟣 21 of 24 model-and-benchmark combinations — first or joint first place

🟣 19 wins, 2 ties, 3 losses against the best baseline

🟣 The effect is clearest on tasks where the order of actions matters

The graph's self-evolution across rounds: the agent's lifespan and the capital it raises both climb as the procedures get corrected.

The largest gains were these:

🟣 on BFCL v3 with Gemini 3.5 Flash: 67% versus 58%

🟣 on GDPval with Gemini 3.1 Pro: 78.78 versus 71.37

🟣 on τ-bench with Gemini 3.1 Pro: 80% versus 73.04%

The margin isn't large everywhere. On HotpotQA it hovers within roughly a percentage point. But the overall picture is clear: where sequencing and holding to a procedure matter, the graph helps most.

The results in short:

🟠 The method performs best on tasks with a long procedure

🟠 Ordinary text memory doesn't deliver an effect this consistent

🟠 The same approach works across different LLMs: Claude, Gemini, Grok

🟠 The effect depends on the type of task: in factual retrieval it is more modest

The most revealing experiment: an agent as CFO

The authors test agents separately in EnterpriseArena, a simulator in which the agent plays the role of chief financial officer. It has to manage the company's liquidity for 132 months, survive three macroeconomic crises and avoid going bankrupt. Money from capital raises arrives with a delay of 1 to 6 months. Which makes the key to survival asking for money early.

This is where the procedural graph fits best. The task hangs on a long chain of decisions spread over time.

Over a long horizon the procedural graph helps agents hold on to cash longer and reach the end of the simulation more often.

Survival results:

🟣 Claude Sonnet 4.6: 58% survived with the graph versus 44% without it

🟣 Gemini 3.1 Pro: 34% versus 6%

🟣 Grok 4.1 Fast: 40% versus 26%

🟣 Gemini 3.5 Flash: nobody made it to the finish, but average lifespan rose from 33.58 to 40.62 months

Survival in short:

🟠 Over a long horizon the graph improves the odds of reaching the end of the simulation

🟠 The widest gap here is Gemini 3.1 Pro: 34% versus 6%

🟠 Even when nobody finishes, the agent's average lifespan goes up

What changes in the agent's behavior? Not simply the number of tool calls. What changes is the timing of decisions.

Without the graph the agent can recheck its balance and the market endlessly and still start raising capital too late. With the graph it keeps to the right sequence more often:

🟠 check the cash

🟠 run the forecast

🟠 look at the market

🟠 request funding ahead of time

🟠 wait for it to arrive without breaking the environment's rules

In one example the agent without the prompt files a second funding application while the first is still unprocessed, and is refused. The agent with the procedural graph remembers that constraint and calmly waits out the lag on capital delivery.

Mistakes exactly like these are what sink long scenarios. The cause here is procedural sloppiness.

Can the graph be built from scratch

Yes, and that is another result. The authors compared five ways of building the graph: by hand, with a one-shot update, with staged evolution, and from scratch, out of a `Start → End` skeleton.

Something unexpected turned up. A graph grown from scratch and then improved on trajectories can be better than a hand-built expert graph.

On HotpotQA the best mode was exactly that: start from the skeleton, then evolve. On MultiChallenge the best result came from an expert start plus evolution, but building from scratch was very close behind.

The story of the bad expert graph is more interesting still. On MultiChallenge the hand-built graph initially made quality worse: success fell from 87.5% to 58.93%. A one-shot static update made it worse again — 53.57%. But iterative evolution with validation pushed the result up to 92.86%.

In other words, the system can not only grow a procedure but also repair bad human drafts.

The price: tokens and complexity

Structure has to be paid for. A prompt from the graph means an extra model call and extra tokens. The authors are honest about showing this.

A local procedural graph often cuts the number of agent steps, but total token spend can still go up. On GDPval and ALFWorld, for instance, the step count fell while overall token use stayed higher than in the baseline without the graph.

There is a saving of another kind, though. In the financial simulator, after several rounds of evolution the number of tool calls dropped from 17.23 to roughly 3.1 per month. The agent, in other words, became far more deliberate.

The practical conclusion: a procedural graph trades tokens for reliability and structure in behavior.

The takeaway

The procedural graph is an attempt to give an AI agent explicit procedural knowledge: what to do, in what order and under what conditions. Not as a long history, not as a scattering of text rules, but as an editable graph of transitions.

A few things are worth taking from the paper:

🟠 Long agent tasks run into procedure, not only into the quality of reasoning

🟠 A local structural prompt works better than the full graph or plain memory

🟠 Procedural knowledge can be improved without fine-tuning the model, through execution logs and validation

🟠 A graph assembled from scratch can catch up with and pass a hand-built expert scheme

🟠 In tasks with delays, constraints and a strict order of actions this approach is especially useful

If you build AI agents for real pipelines, there is an applied idea here. It isn't enough for models to remember the past. They need scaffolding that keeps the procedure separate and suggests the next step from the current state. That is exactly the point at which many agent systems fail today.