Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

Forum topic · 小凯 · 2026-09-10

Summary

This paper introduces Procedural Graphs, a new framework for LLM agents that makes procedural knowledge explicit. Analogous to how knowledge graphs store factual knowledge as (entity, relation, entity) triplets, Procedural Graphs organize procedural knowledge as (procedure, relation, procedure) triplets to answer what-to-do questions. At each decision step, the framework localizes the agent's active node and translates the surrounding subgraph into step-level situational guidance that biases, but does not dictate, the solver's next action. The graph is self-evolving: an LLM refiner contrasts failed trajectories with successful ones, edits graph topology and attributes, and commits only edits that preserve or improve held-out validation performance, while retaining rejected edits to prevent repetition. Starting from a minimal skeleton, the loop builds graphs matching or surpassing hand-designed ones and can repair flawed expert priors. Across multiple datasets, task types, and LLMs, Procedural Graphs consistently outperform memory-based baselines, with self-evolution delivering further gains without manual engineering.

Paper Overview

Research areas: cs.AI, cs.CL, cs.MA Authors: Yuxing Lu, Yicheng Chen, Shanchan Wu, Sercan Ö. Arık Published: 2026-09-08 arXiv: 2609.09153

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.

Key Ideas

Problem: LLM agents choose actions via unconstrained generation over accumulating history, so procedural knowledge (what to do, in what order, under which conditions) stays implicit — leading to lost objectives, out-of-order tool calls, and repeated unproductive actions in long-horizon tasks.
Procedural Graph: organizes procedural knowledge into (procedure, relation, procedure) triplets, the procedural analogue of knowledge graphs' factual (entity, relation, entity) triplets.
Step-level guidance: at each decision step, the agent's active node is localized and a guidance model converts the surrounding subgraph into situational guidance that biases the solver's next action without dictating it.
Self-evolution: an LLM refiner compares failed vs. successful trajectories and edits graph topology/attributes; only edits preserving or improving held-out validation performance are committed, while rejected edits are retained to discourage repetition.
Results: starting from a minimal skeleton, the loop builds graphs matching or exceeding hand-designed ones; it can also repair flawed expert priors. Across multiple datasets, task types, and LLMs, Procedural Graphs consistently beat memory-based baselines, with self-evolution further improving performance without manual engineering.