Introduces the Procedural Graph to explicitly encode procedural knowledge, enabling long-horizon LLM agents to maintain objectives, avoid out-of-order tool calls, and reduce repetitive failures.
The Procedural Graph (PG) is an explicit, editable directed graph that organizes procedural knowledge into (procedure, relation, procedure) triplets to guide LLM agents through what-to-do questions, contrasting with knowledge graphs that handle factual what-is questions. It maintains task-specific procedural knowledge outside model weights, allowing it to be inspected, retrieved at each step, and edited without retraining.
During execution, the agent uses Generative PG Guidance to localize its current node and retrieve a subgraph, which a guidance LLM converts into step-level situational guidance that biases the next action without dictating it. The graph self-evolves via an offline loop where an LLM refiner contrasts failed trajectories with successful ones to propose edits; these edits are committed only if they improve performance on a validation set, effectively repairing flawed priors or building graphs from scratch.
This approach enables agents to maintain long-horizon objectives, prevent out-of-order tool calls, and eliminate repetitive failures by providing a structured prior for admissible transitions. Research indicates that PG consistently outperforms memory-based baselines, with self-evolution producing graphs that match or surpass hand-designed ones while significantly reducing redundant tool invocations and computational costs in complex tasks.
Procedural Graphs: Self-Evolving Execution Structures for LLM Agents proposes a graph-based representation of procedural knowledge for long-horizon LLM agents. Instead of relying solely on prompts, free-form planning, or parametric memory, the approach encodes procedures as an explicit structure in which nodes represent actions, tool calls, checks, or intermediate states, while edges encode ordering constraints, dependencies, preconditions, and recovery paths. The agent uses this graph to keep track of what has been done, what remains to be done, and which next steps are valid, allowing it to preserve high-level objectives across extended interactions.
A central contribution is the “self-evolving” nature of the graph: it is not a static workflow, but a persistent execution structure that can be updated from experience. Successful execution traces can reinforce useful paths, while failures can expose missing constraints, invalid transitions, or recurring error patterns that the graph can then encode to prevent repetition. This separates flexible LLM reasoning—such as interpreting subgoals, filling in parameters, and choosing among alternatives—from a more rigid procedural control layer that enforces task-specific invariants and ordering.
The work matters because many LLM agent failures in long-horizon settings stem from context drift, forgotten constraints, out-of-order tool use, and repeated attempts at already-failed steps. By making procedural knowledge explicit, inspectable, and reusable, Procedural Graphs offer a path toward more reliable, auditable, and composable agent behavior. The approach is especially relevant for tool-using agents and multi-step workflows, where persistent procedural memory can reduce redundant actions, improve task completion, and allow skills to be refined incrementally without retraining the underlying model.