Yuxing Lu, Yicheng Chen, Shanchan Wu and Sercan Arik at Google, with Georgia Tech and Peking University, introduce the Procedural Graph, an explicit store of (procedure, relation, procedure) triplets that supplies step-level guidance to an agent and rewrites itself from the difference between failed and successful trajectories.
What the graph stores: A knowledge graph holds facts as entity-relation-entity triplets; a Procedural Graph holds procedures as procedure-relation-procedure triplets, so the agent has a queryable representation of what to do next and in what order rather than leaving that implicit in a growing history.
Guidance is a bias, not a command: At each step the framework localizes the agent's active node and a guidance model turns the surrounding subgraph into situational guidance that shifts the solver's next action without dictating it, which keeps the solver free to deviate when the graph is wrong.
Self-evolution uses a held-out gate: An LLM refiner contrasts failed against successful trajectories and edits the graph's topology and attributes, committing only edits that preserve or improve held-out validation performance and keeping rejected edits on file so the same change is not proposed again.
It repairs bad priors: Starting from a minimal skeleton the loop builds graphs that match or exceed hand-designed ones, and given a flawed expert prior it corrects that prior rather than inheriting it.
Consistent gains over memory baselines: Across multiple datasets, task types and backbone LLMs the Procedural Graph beats memory-based baselines, and self-evolution adds further gain with no manual engineering.
Abstract
Large language models are increasingly deployed as agents that plan over long horizons and act through external tools. Most agents select actions through unconstrained generation over an accumulating history, leaving implicit the procedural knowledge of what to do, in what order, and under which conditions. As trajectories lengthen, agents can lose track of their objectives, invoke tools out of order, and repeat unproductive actions. We introduce the Procedural Graph: just as a knowledge graph organizes factual knowledge into (entity, relation, entity) triplets for what-is questions, a Procedural Graph organizes procedural knowledge into (procedure, relation, procedure) triplets for what-to-do questions. At each decision step, the framework localizes the agent's active node, and a guidance model translates the surrounding subgraph into step-level situational guidance that biases the solver's next action without dictating it. The graph is self-evolving: an LLM refiner contrasts failed trajectories with successful ones and edits the graph's topology and attributes, committing edits that preserve or improve held-out validation performance while retaining rejected ones to discourage repetition. Starting from a minimal skeleton, the loop builds graphs that match or surpass hand-designed ones. It can also repair a flawed expert prior. Across multiple datasets, task types, and LLMs, the Procedural Graph delivers consistent gains over memory-based baselines, and self-evolution further improves performance without manual engineering.