Skip to content

Back to the catalog

Procedural Graphs: Self-Evolving Execution Structures for LLM Agents
arxiv.orgpaper

Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

Introduces the Procedural Graph, a structure that organizes procedural knowledge as (procedure, relation, procedure) triplets analogous to how knowledge graphs organize facts, giving LLM agents explicit step-level guidance rather than relying on unconstrained generation over accumulating history. The graph is self-evolving: an LLM refiner contrasts failed and successful trajectories to edit the graph's topology, committing edits that improve held-out validation performance while retaining rejected edits to avoid repeating mistakes. Across multiple datasets and LLMs, it outperforms memory-based baselines and can even repair flawed hand-designed expert priors.

TL;DR A self-evolving graph structure that gives LLM agents explicit, editable procedural knowledge to guide long-horizon planning, beating memory-based baselines.
Open original ↗
Document

What it claims

The paper separates the runtime use of a Procedural Graph from the evolution of it — a distinction the summary collapses. At inference, the framework does not just consult the graph as memory: at each decision step it localizes the agent's currently 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." So there are effectively two models at play besides the solver — a guidance model (runtime) and a refiner (offline evolution). The target problems are named concretely: agents that lose track of objectives over long horizons, invoke tools out of order, and repeat unproductive actions.

How it works

The graph starts from a minimal skeleton, not a hand-built structure — the self-evolution loop grows it to match or surpass hand-designed graphs. The runtime loop and the evolution loop are distinct:

flowchart TD
    A[Agent state / history] --> B[Localize active node]
    B --> C[Guidance model reads subgraph]
    C --> D[Step-level guidance biases next action]
    D --> E[Solver acts]
    E -->|trajectory| F[Refiner: contrast failed vs successful]
    F -->|edit passes held-out validation| G[Commit topology/attribute edit]
    F -->|edit fails| H[Retain as rejected, discourage repetition]
    G --> B

The refiner edits both topology and node attributes, gated on preserving or improving held-out validation performance; rejected edits are kept explicitly so the loop does not re-propose them.

Limits

This is an abstract-only capture. It names no datasets, no metrics, no numbers, no model sizes, and no baselines beyond the category "memory-based baselines." Every performance claim ("consistent gains," "match or surpass hand-designed ones," "repair a flawed expert prior") is stated without figures — you cannot judge magnitude or which task types benefit from this page alone. There is no mention of the compute cost of running two extra LLM calls (guidance + refiner) per decision step, which the "biases without dictating" runtime clearly incurs. Read the PDF for the results tables before adopting.

Techniques named here

  • Procedural Graph
  • Self-evolution loop for Procedural Graphs

Related in agents