Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

Large language models are increasingly used as agents that plan over long horizons and act through external tools, but they often lose track of objectives, invoke tools out of order, or repeat unproductive actions. This paper introduces the Procedural Graph, which organizes procedural knowledge into (procedure, relation, procedure) triplets, analogous to knowledge graphs for factual knowledge. At each decision step, the framework localizes the agent's active node and uses a guidance model to translate the surrounding subgraph into step-level situational guidance. The graph is self-evolving: an LLM refiner contrasts failed trajectories with successful ones, editing the graph's topology and attributes, committing edits that preserve or improve held-out validation performance. Starting from a minimal skeleton, the loop builds graphs that match or surpass hand-designed ones and can repair flawed expert priors. 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.