Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

Procedural Graphs. Self-Evolving Execution Structures for LLM Agents. By Yuxing Lu and three others, from Google, the Georgia Institute of Technology, and one other institution. Published on the eighth of September. No code repository is linked to it.

Large language models are increasingly deployed as agents that plan over long horizons and act through external tools. Most of them choose each action by unconstrained generation over a history that keeps growing. The procedural knowledge involved, what to do, in what order, and under which conditions, is left implicit. As trajectories get longer, the cracks show. Agents lose track of their objectives, call tools out of order, and repeat actions that get them nowhere. Nothing in the agent's setup records the structure of the task, so as the history grows, that structure is easy to lose.

The Procedural Graph makes that knowledge explicit. The analogy is the knowledge graph. A knowledge graph organises factual knowledge into triplets of entity, relation and entity, and answers questions about what is. A Procedural Graph organises procedural knowledge into triplets of procedure, relation and procedure, and answers questions about what to do. Where one captures relations between things, the other captures relations between steps.

At each decision step, the framework localises the node the agent is currently at. A guidance model then translates the surrounding subgraph into situational guidance for that step. The guidance biases the solver's next action without dictating it, so the agent is steered by the procedure but not locked into it. Localising the active node is what keeps the guidance relevant: it is drawn from the part of the procedure the agent is actually in, not from the whole graph at once.

The graph also evolves itself. An LLM refiner compares failed trajectories with successful ones and edits the graph's topology and attributes. Edits are committed only if they preserve or improve performance on held-out validation. Rejected edits are kept too, to discourage the refiner from proposing them again. Starting from a minimal skeleton, this loop builds graphs that match or surpass hand-designed ones, and it can also repair an expert prior that was flawed. So the graph need not be written by an expert to begin with, and if an expert has written one with mistakes in it, the refiner can fix them.

Across multiple datasets, task types, and LLMs, the Procedural Graph delivers consistent gains over memory-based baselines. Self-evolution adds further improvement on top, without manual engineering. The gains hold across the breadth of the evaluation rather than on one favourable setting, and the self- evolving loop adds to them on its own.

The contribution is a place to put procedural knowledge that is neither buried in a growing history nor fixed by hand. The graph gives the agent a sense of where it is in a procedure, the guidance keeps it on course without taking away its choices, and the refiner keeps the graph improving from the agent's own successes and failures, holding on to what validation supports and remembering what it did not.