Procedural Graphs: Self-Evolving Execution Structures for LLM Agents | AI Paper Digest

TL;DR Highlight

Self-editing procedural graphs guided LLM agents and beat memory-based baselines across datasets and LLMs

Who Should Read

Backend developer whose long-running agent loses its goal or calls tools in the wrong order

Core Mechanics

Procedural knowledge is written as a graph
- Like a knowledge graph's (entity, relation, entity) triplets for what-is questions, this uses (procedure, relation, procedure) for what-to-do questions.
- Normal agents pick actions by free generation over accumulating history, so procedure stays implicit.
Long tasks cause known failures
- As trajectories lengthen, agents lose track of objectives.
- They call tools out of order and repeat unproductive actions.
Each step gets only local guidance
- The framework finds the agent's active node in the graph.
- A guidance model turns the surrounding subgraph into step-level guidance.
- It biases the next action without dictating it.
The graph evolves itself
- An LLM refiner contrasts failed and successful trajectories and edits topology and attributes.
- Edits are committed only if held-out validation performance holds or improves.
- Rejected edits are kept to discourage repetition.

Community Reactions

Opinion that the graph may be a distraction
- One commenter thought the graph is just a data representation and the core idea is durable task lists for structured dynamic planning.
- They noted hierarchical text lists already have named references, mutability, and statuses, and models are familiar with them.
Question about simpler self-modifying harnesses
- A commenter asked whether the paper compared against a simple harness that updates code or skill docs based on results.
Question about how Add nodes are made
- A commenter asked whether an LLM produces each node's name, guidance, and edges, or a bespoke transformer does.
Concern about regressions and auditability
- One commenter said self-editing topology makes regressions harder to localize.
- They suggested reporting graph churn and rollback frequency alongside task success.
- They also saw the explicit structure as a place to attach permissions or provenance to tool calls.

How to Apply

Extract procedures from your agent's failure logs
- Give an LLM 3 failed and 3 successful trajectories from today and ask it to compare step order.
- Get the result as (procedure, relation, procedure) triplets and see where they diverge.
Inject only current-step hints into the system prompt
- Don't force the whole procedure; add short guidance about the previous and next procedures around the current step.
- Keep it a bias like the paper does, not a hard rule.
Commit edits only if held-out tasks pass
- Measure each procedure edit on separate validation tasks.
- Keep it only if performance holds or improves, and log rejected edits.
Log graph churn and rollback counts
- Record node/edge changes and rollbacks for each edit.
- Read them next to success rate to see if the graph is bloating.

Try It

copy & run

# Paste into Claude or ChatGPT (simplified version of the paper's method: build a procedural graph by comparing success and failure trajectories)

You are an agent procedure analyst. Compare the successful and failed trajectories below and build a procedural graph.

[Successful trajectory]
{{successful trajectory}}

[Failed trajectory]
{{failed trajectory}}

Output format:
1. A list of (procedure, relation, procedure) triplets. Keep relations short, like 'next', 'conditional', 'on failure'.
2. The point where the failed trajectory first went wrong, and why.
3. A one-line situational hint for that point (a suggestion, not a forced action).

Next step: put the hint in your system prompt, run {{number of validation tasks}} tasks, and compare the success rate to before.

Terminology

Procedural GraphA map of what to do, in what order and under which conditions, as nodes and relations. It is the procedure version of a knowledge graph.

Knowledge GraphA structure storing facts as (entity, relation, entity) triplets. Think of it as wiki sentences broken into table rows.

TrajectoryThe full record of an agent's thoughts, actions, and results in one task. Like a replay of a game session.

RefinerAn LLM that compares success and failure records and edits the graph. It acts like a reviewer proposing fixes.

Held-out validationMeasuring performance on tasks set aside and not used for edits. It is the exam that shows whether a change really helped.

Related Papers

Related Resources

https://arxiv.org/abs/2609.09153