Large language models are increasingly used as agents that plan over long horizons and act through external tools. Yet most agents choose 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 grow longer, agents can lose track of objectives, call tools out of order, and repeat unproductive actions.
To address this, researchers 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. This guidance biases the solver's next action without dictating it, keeping the agent on track while preserving flexibility.
The graph is self-evolving: an LLM refiner contrasts failed trajectories with successful ones and edits the graph's topology and attributes. Edits that preserve or improve held-out validation performance are committed, while rejected edits are retained to discourage repetition. Starting from a minimal skeleton, the loop builds graphs that match or surpass hand-designed ones, and it can even repair a flawed expert prior.
Across multiple datasets, task types, and LLMs, the Procedural Graph delivers consistent gains over memory-based baselines, with self-evolution further improving performance without manual engineering.