LLM agents that plan over long horizons tend to lose track of their objectives, invoke tools out of order, and repeat unproductive actions. A team from Google, Georgia Tech, and Peking University proposes a fix: store procedural knowledge explicitly as a graph, and let the agent query it at each step instead of relying on an ever-growing history to carry forward what to do next.
From Facts to Procedures
A knowledge graph organizes factual knowledge as entity-relation-entity triplets: "Paris is the capital of France." A Procedural Graph does the same for procedural knowledge, storing procedure-relation-procedure triplets that describe what to do and in what order. The difference is the query the graph answers. Knowledge graphs answer "what is" questions. Procedural Graphs answer "what to do next" questions.
At each decision step, the framework localizes the agent's active node and a guidance model translates the surrounding subgraph into situational guidance. This guidance biases the solver's next action without dictating it, which keeps the solver free to deviate when the graph is wrong. The guidance is a recommendation, not a constraint.
Self-Evolution Through Held-Out Validation
The graph improves itself by contrasting failed trajectories with successful ones. An LLM refiner edits the graph's topology and attributes, but commits only changes that preserve or improve performance on held-out validation tasks. Rejected edits are kept on file so the same change is not proposed again.
This held-out gate prevents the graph from overfitting to the specific trajectories that triggered the edit. The refiner sees what went wrong, proposes a structural fix, and the validation set decides whether the fix generalizes. Over multiple rounds, the graph accumulates procedural knowledge that transfers across tasks.
Starting from Scratch or Repairing a Prior
The system can begin from a minimal skeleton and build up a graph that matches or exceeds hand-designed ones through iterative self-evolution. It can also take a flawed expert prior as input and correct it rather than inheriting its mistakes. This is a useful property for teams that have invested in manual procedure design but suspect those procedures contain errors or gaps.
The self-evolution loop adds further gain on top of whatever the initial graph provides, with no manual engineering required. Across multiple datasets, task types, and backbone LLMs, the Procedural Graph consistently beats memory-based baselines. Memory-based approaches store past actions and observations but leave the procedural structure implicit. The Procedural Graph makes that structure explicit, queryable, and editable.
Why This Matters for Agent Design
Most agents select actions through unconstrained generation over an accumulating history. As trajectories lengthen, that history becomes a noisy signal. The procedural knowledge of what to do, in what order, and under which conditions stays buried in earlier tokens. The Procedural Graph pulls that knowledge out of the history and into a structure the agent can reason about at each step.
The bias-not-command design is a deliberate choice. A rigid procedure would break when the agent encounters a situation the graph does not cover. A pure memory approach would leave the agent without guidance. The subgraph-based guidance occupies a middle ground: it suggests a direction based on what has worked before, but lets the agent override it when the current situation demands something different.
The approach also sidesteps a common failure mode in self-improving systems. Without the held-out gate, edits to the graph would optimize for the trajectories that triggered them, leading to overfitting. The validation check ensures that every committed change generalizes beyond the specific failure that prompted it. Rejected edits persist as a record of what was tried and found wanting, which prevents the refiner from cycling through the same failed proposals.
For teams building agents that need to handle multi-step workflows, the Procedural Graph offers a concrete path: start with what you know, let the agent learn from its failures, and keep the procedural knowledge in a form that both the agent and the developer can inspect.