Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

2609.09153 ↗ · 2026-09-08 · cs.AI, cs.CL, cs.MA

Yuxing Lu, Yicheng Chen, Shanchan Wu, Sercan Ö. Arık

36 pages including references and appendices, 6 figures, 11 tables

The finding

Headline claim

An explicit, self-evolving directed graph of procedural knowledge, used as step-level guidance, improves LLM agent performance over memory-based baselines and can replace hand-designed workflows.

The test

Same ReAct solver with identical training trajectories across methods, evaluated on seven benchmarks (HotpotQA, MultiChallenge, GDPval, ALFWorld, tau-bench, BFCL, EnterpriseArena) with four LLMs (Claude Sonnet 4.6, Gemini 3.1 Pro, Gemini 3.5 Flash, Grok 4.1 Fast), comparing against seven memory/planning baselines.

Effect size & scope

PG ranks first or joint first in 21 of 24 model-benchmark settings; self-evolution from a minimal skeleton matches or surpasses hand-designed graphs and can repair flawed expert priors; full per-task deltas not shown in provided text.

Limitations

Authors concede stochastic validation-gating noise (Section 5.4 examines it); text truncates before detailed numbers; obvious unstated concerns include extra guidance-model latency and token cost, benchmark environments far from production complexity, and reliance on exact node matching for localization.

Counterpoint

Baselines were reimplementations by the same authors under one solver; benchmarks are standard agent evals with known gaming risk; the 21-of-24 first-place count hides margin sizes; no code/results shown in provided excerpt to verify; gains may reflect more in-context scaffolding than genuine procedural learning.

Economy implication

Little or nothing yet for the AI economy in the next 12 to 24 months: this is an agent-architecture result; at most it suggests agentic reliability gains (the B1 input) may come from cheaper scaffolding rather than bigger models, which would modestly favor app-layer differentiation.

Who this matters for

Technical Capability: Agent builders get a blueprint for converting procedural memory into an editable, self-improving structure that outperforms flat trajectory memory across many benchmarks.

Labor & Knowledge Work: If structured scaffolding reliably cuts agent failure loops, it moves multi-step knowledge task automation closer to unattended operation, which is the precondition for any staffing impact.

Bears on (advisory · papers never write evidence)

[1.3] Agentic reliability (multi-step completion without human correction) is improving materially, not just peak single-shot.

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.