DEV Community

ryan2run
ryan2run

Posted on

Procedural Graphs: Self-Improving LLM Agent Execution Structures

#ai #agents #research #graph

Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

When AI Agents Start Writing Their Own "Brain Circuits"

Published: September 10, 2026 | Reading time: 12 minutes

The Revolutionary Research

On September 9, 2026, researchers Yuxing Lu, Yicheng Chen, and Shanchan Wu published a groundbreaking paper on Procedural Graphs — a self-evolving execution structure for LLM agents that can literally rewrite its own "brain circuits."

Paper: arXiv:2609.08593

Self-Evolving Graph

The Problem with Current LLM Agents

Today's LLM agents (like AutoGPT, LangChain agents) work like this:

  1. Maintain a growing memory of past thoughts, observations, actions
  2. Generate next action based on this memory
  3. No fixed structure, no predefined流程

This works for simple tasks, but breaks down for complex ones:

  • Lost goals: Forget what they're supposed to do in long interactions
  • Action mismatch: Call tools in wrong order (e.g., analyze before searching)
  • Repeated labor: Try same ineffective operations repeatedly
  • No planning: No global view, step-by-step navigation

Analogy: Like a chef without a recipe — overwhelmed by complex dishes.

The Solution: Procedural Graphs

Procedural Graphs organize procedural knowledge ("how to do") just like Knowledge Graphs organize factual knowledge ("what is"):

Type Structure Question
Knowledge Graph (Entity, Relation, Entity) What is?
Procedural Graph (Procedure, Relation, Procedure) How to?

Core Components

Nodes (程序步骤):

  • Each node represents a procedural step
  • Contains: description, expected I/O, success/failure conditions
  • Like a box in a flowchart

Edges (关系):

  • Represent relationships between steps
  • Types: Sequential ("then"), Conditional ("if...then"), Parallel ("simultaneously")
  • Like arrows in a flowchart

Attributes (属性):

  • Execution probability, average time, success rate, common error patterns
  • Update with execution experience

How It Works: A Concrete Example

Task: "Book a cheap flight from Beijing to Shanghai, departing tomorrow."

Procedural Graph:

[Start]
   ↓
[Search Flight Info]
   ↓
[Filter Low-Cost Options]
   ↓
[Check Seat Availability]
   ↓
[If Available: Fill Passenger Info]
   ↓
[Select Payment Method]
   ↓
[Confirm Order]
   ↓
[End]
   ↓
[If Unavailable: Return to Filter]
   ↓
[If No Satisfying Result: Expand Search]
   ↓
[Search Nearby Airports]
   ↓
[Return to Filter]
Enter fullscreen mode Exit fullscreen mode

This is a directed graph with branches, loops, and conditionals — far more powerful than linear memory.

The Self-Evolution Mechanism

The most amazing capability is self-evolution:

Evolution Cycle

  1. Collect trajectories: Record complete execution paths
  2. Compare analysis: Contrast failed trajectories with successful ones
  3. Identify differences: Find where things went wrong
  4. Generate edits: LLM Refiner proposes modifications
  5. Verify and retain: Test on validation set

Three Types of Edits

  1. Topology Edits:

    • Add new nodes (new steps)
    • Remove redundant nodes
    • Add/modify edges (change flow structure)

  2. Attribute Edits:

    • Update node success rate statistics
    • Adjust condition thresholds
    • Update execution probabilities

  3. Content Edits:

    • Modify node descriptions for accuracy
    • Update guidance language for effectiveness

From Skeleton to Maturity

Researchers tested three initialization methods:

Initialization Evolution Speed Final Performance
Empty Graph (only "Start" node) Slower Close to others
Minimal Skeleton (basic manual nodes) Fastest Best
Expert Prior (human-designed) N/A Repairable if flawed

Amazing Discovery: Even starting from a flawed expert prior, the evolution mechanism can "repair" it to achieve good performance.

This shows robustness — doesn't require perfect initial design.

Why Graphs Beat Memory

Dimension Pure Memory Workflow Memory Procedural Graph
Structure None Case-level abstract Procedure-level
Generalization Poor Medium Good
Explainability Poor Medium Good
Evolution None Limited Strong
Efficiency Low Medium High

Key Advantage: Procedural Graphs abstract the general flow for a class of tasks, not just specific past cases.

Analogy:

  • Workflow Memory = Remember "Last time I made Mapo Tofu, I stir-fried meat first, then added bean paste"
  • Procedural Graph = Understand "General stir-fry flow: Heat pan → Add oil → Stir-fry main ingredient → Season → Serve"

The latter generalizes to any stir-fry; the latter can only repeat Mapo Tofu.

Experimental Results

WebShop (Web Shopping)

  • Task: Purchase items on e-commerce sites based on natural language instructions
  • Graph vs Memory: 15-25% success rate improvement
  • Evolved Graph vs Initial: 10-20% improvement

ALFWorld (Home Tasks)

  • Task: Execute daily tasks in simulated home environment
  • Graph helps remember complex object interaction sequences

HotPotQA (Multi-hop QA)

  • Task: Multi-step information retrieval and reasoning
  • Graph optimizes retrieval strategy and evidence integration

Tool Use Tasks

  • Task: Combine multiple APIs to complete complex goals
  • Graph ensures correct tool call order and parameter settings

Key Findings

Finding 1: Cross-LLM Generalization

  • Graph evolved on one LLM (e.g., GPT-4) can transfer to another (e.g., Claude or Llama)
  • Shows graphs capture task structure, not model-specific traits

Finding 2: Few-Shot Advantage

  • Effective even with few examples (<10)
  • Pure memory baseline drops sharply with few samples

Finding 3: Expert Prior Repairability

  • Can repair flawed human-designed starting points
  • Lowers deployment threshold — no perfect initial design needed

Deeper Insights

From Connectionism to Symbolism

Procedural Graphs represent an important trend: neural-network + symbolic-structure fusion.

  • Deep Learning (connectionism): Good at learning patterns from data, lacks explicit reasoning structure
  • Symbolic AI: Good at logical reasoning and structured knowledge, lacks learning from data

Graph combines both:

  • LLM provides semantic understanding
  • Graph structure provides procedural constraints

This is a Neuro-Symbolic architecture — possibly a key path to more reliable AI.

Biological Intelligence Analogy

Human brain similarly combines two systems:

  • System 1 (fast, intuitive, pattern-matching): Like LLM generation
  • System 2 (slow, logical, rule-based): Like Procedural Graph execution

The graph is like giving LLMs a System 2 — an explicit, checkable, fixable execution controller.

Code Example: Creating a Procedural Graph 

from procedural_graph import ProceduralGraph, Node, Edge

# Create a simple graph for a coding task
graph = ProceduralGraph()

# Add nodes
start = Node("Start", description="Begin task")
search = Node("Search Info", description="Search for relevant information")
analyze = Node("Analyze Data", description="Analyze collected data")
code = Node("Write Code", description="Generate code solution")
verify = Node("Verify Result", description="Test and verify output")
end = Node("End", description="Task complete")

# Add edges
graph.add_edge(start, search, type="sequential")
graph.add_edge(search, analyze, type="conditional", condition="info_found")
graph.add_edge(analyze, code, type="sequential")
graph.add_edge(code, verify, type="sequential")
graph.add_edge(verify, end, type="conditional", condition="passed")
graph.add_edge(verify, code, type="conditional", condition="failed")  # Loop back

# Navigate the graph
current = start
while current != end:
    context = graph.get_local_subgraph(current)
    action = llm.generate_action(context)
    result = execute(action)
    current = graph.navigate(current, result)
Enter fullscreen mode Exit fullscreen mode

Architecture Overview

Key Components

  1. Graph Store: Stores nodes, edges, and attributes
  2. Navigator: Determines next node based on current state
  3. Refiner: Proposes graph edits based on trajectory feedback
  4. Verifier: Tests graph modifications on validation set

Evolution Process

  1. Collect execution trajectories
  2. Compare successful vs. failed paths
  3. Identify differences and generate edits
  4. Verify edits on validation set
  5. Apply successful edits to production graph

Software Engineering Perspective

Procedural Graphs introduce key concepts:

1. Separation of Concerns

  • "What to do" (task understanding): LLM
  • "How to do" (execution flow): Graph
  • "How to improve" (flow optimization): Refiner

2. Version Control

  • Every graph edit is recorded
  • Can rollback to previous versions
  • Can compare performance across versions

3. Testability

  • Graph can be independently tested on validation sets
  • Edit effects can be quantified
  • Avoids "black-box optimization" uncertainty

Conclusion

The story of Procedural Graphs is essentially a story about organization.

Information alone has no value. Only when organized into useful structures — recipes, flowcharts, algorithms, organizational charts — can it guide action, produce results, and continuously improve.

LLM agents have massive knowledge and powerful generation capabilities, but lack structured execution frameworks. Procedural Graphs fill this gap:

  • Give agents a "skeleton" — clear execution flow
  • Give agents "learning ability" — self-evolve from failures
  • Give agents "explainability" — humans can understand and modify its "thinking"

When that recipe starts rewriting itself, it's no longer just a book. It becomes a living thing — constantly adapting, learning, and improving.

This is the ultimate vision of Procedural Graphs: Not giving agents a fixed program, but giving them a brain that can write its own programs.

This article is based on research published by Yuxing Lu, Yicheng Chen, and Shanchan Wu on September 9, 2026. Paper: arXiv:2609.08593

Top comments (0)