PaperlayerView exact revision on arXiv

Source-linked AI summary

Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

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

arXiv:2609.09153v1cs.AIcs.CLcs.MA

TL;DR

Long-horizon LLM agents often leave procedural knowledge implicit while selecting tools from an accumulating history, risking incoherent or repetitive execution. The paper introduces a self-evolving Procedural Graph that provides step-level guidance from explicit procedure transitions and refines those transitions using execution feedback. Across datasets, task types, and LLM families, it reports consistent gains over memory-based baselines, while self-evolution builds effective graphs from minimal initializations and repairs flawed expert priors.

  • Problem

    Long-horizon agents select actions through unconstrained generation over growing histories, leaving procedural ordering and conditions implicit.

  • Method

    The Procedural Graph represents procedures as editable transitions, supplies localized situational guidance during inference, and evolves graph topology and attributes from failed and successful trajectories.

  • Results

    Across six benchmarks and four LLM families, PG ranks first or joint first in 21 of 24 model–benchmark settings and records 19 wins, two ties, and three losses against the strongest baselines.

  • Takeaways & Limitations

    Self-evolution builds effective graphs from minimal initializations and repairs expert priors that initially hinder performance without updating model weights.

Abstract

from arXiv · show

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.

1. Introduction

The paper introduces the Procedural Graph to make procedural knowledge explicit, editable, and responsive to an agent’s current progress. It combines graph-based guidance with self-evolution from execution feedback to improve long-horizon tool use.

  • Long-horizon agents rely on unconstrained generation over growing action histories, which can cause lost objectives, invalid tool order, and repeated unproductive actions.
  • Existing textual memories preserve experience but leave the solver to reconstruct its relevance and downstream procedural constraints.State-conditioned guidelines are more targeted but do not explicitly connect successive procedural steps; explicit workflows often require manual design.
  • A Procedural Graph organizes procedures as (procedure, relation, procedure) triplets for what-to-do questions, with nodes for actions, reasoning steps, and states.Edges encode permissible transitions and carry textual attributes describing how and when each transition should be taken.
  • During inference, the framework localizes the active node and translates its surrounding subgraph and edge attributes into situational guidance for the next step.The guidance steers execution while preserving reasoning flexibility rather than dictating a fixed action.
  • During self-evolution, an LLM refiner contrasts failed and successful trajectories, proposes graph edits, and adopts candidates that match or improve held-out validation performance.Rejected candidates are retained as negative constraints, while the loop can add nodes and edges, prune failure-inducing structures, and revise edge attributes.

2. Related Work

Related work addresses agent action selection, structured planning priors, and trajectory-derived reusable knowledge. The Procedural Graph combines explicit attributed transitions with local retrieval and execution guidance.

  • Free-form action-selection methods rely on LLMs to choose valid next actions from in-context information, leaving admissible transitions implicit.
  • Structured-prior methods represent procedures as rules, workflows, searched graphs, or tool catalogs, while the Procedural Graph combines attributed procedure transitions with local retrieval.
  • Self-improving agents distill reusable knowledge from trajectories as critiques, insights, guidelines, workflows, or procedural memories.These artifacts preserve different forms of structure, including conditional rules and ordered workflow steps.

3. The Procedural Graph Framework

The Procedural Graph framework represents procedural knowledge as an editable directed graph, retrieves context around the agent’s current procedure, and turns it into flexible step-level guidance. An offline refiner proposes graph edits from execution feedback and retains only structurally valid candidates whose validation performance does not decrease.

  • 3.2. Generative Guidance at Inference Time: At inference time, the framework combines the agent trajectory with the graph to generate dynamic situational guidance while keeping the graph fixed.The solver receives guidance appended to its prompt and retains flexibility in selecting the next action.
  • 3.1. Formal Representation of Procedural Graphs: The Procedural Graph is a directed, attributed graph whose nodes represent procedures or states and whose edges encode permissible transitions with textual attributes.The implementation uses condition, guidance, and pitfalls fields to describe when and how transitions should be taken and what to avoid.
  • 3.2. Generative Guidance at Inference Time: The guidance process locates the latest procedure, retrieves its connected neighborhood, and translates surrounding edge attributes into advice for the next step.The neighborhood exposes procedural context up to multiple transitions ahead, rather than retrieving transition attributes independently.
  • 3.3. Self-Evolution of Procedural Graphs: Offline evolution contrasts high- and low-scoring execution traces, then proposes additions, deletions, or attribute revisions to the graph.Proposed edits can add missing verification structure or remove nodes and edges associated with repeated failures or stalled progress.
  • 3.3. Self-Evolution of Procedural Graphs: Candidate graphs are evaluated on an independent validation set, and the retained graph is updated only when a structurally valid candidate matches or exceeds the current validation score.Rejected candidates remain in rejection memory so later proposals can avoid previously unsuccessful edits.

4. Experimental Setup

The experiments evaluate procedural reasoning across seven benchmarks using a shared ReAct solver and compare progressively structured memory and workflow baselines. They test four LLMs, with graph guidance using a 2-hop neighborhood and a three-step recent trajectory window.

  • Benchmarks: The benchmark suite covers question answering, multi-turn instruction retention, professional tasks, embodied household tasks, and policy-compliant tool use.The setup spans seven procedural-reasoning benchmarks.
  • Baselines: All methods use the same ReAct solver and differ in how procedural experience is stored and reused.Learning-based baselines consume the same training trajectories as the self-evolution loop.
  • Baselines: The baselines range from no memory and summarized experience to retrieved trajectories, natural-language insights, state-conditioned guidelines, linear workflows, and textual action-transition rules.This comparison orders methods by increasing procedural structure.
  • Models: The study evaluates four LLMs, using the same underlying model for the solver, guidance model, and offline refiner.All calls use greedy decoding with temperature 0 for reproducibility.
  • Procedural Graph Configuration: Online guidance uses a 2-hop neighborhood around the localized node and a recent trajectory window of 3 steps.The paper also compares different graph construction strategies.

5. Results

Across benchmarks, LLMs, and long-horizon financial decisions, Procedural Graphs generally outperform memory-based or unguided baselines. Construction and usage analyses show gains from self-evolution, localized guidance, and explicit procedural structure.

  • Main results: PG ranks first or joint first in 21 of 24 model–benchmark settings, with 19 wins, two ties, and three losses against the strongest baseline.The one-sided exact binomial sign test excluding ties gives p=4.3 × 10−4.
  • Main results: PG outperforms every baseline on GDPval and BFCL v3 under all four LLMs, while gains on HotpotQA range from −0.90 to +1.30 points.On MultiChallenge, PG ranks first or joint first across all four models, but gain magnitudes vary substantially by benchmark.
  • Long-horizon resilience: PG achieves the highest or joint-highest full-horizon survival and longest average lifespan across four LLMs in EnterpriseArena.Survival rises from 44.0% to 58.0% for Claude Sonnet 4.6, from 6.0% to 34.0% for Gemini 3.1 Pro, and from 26.0% to 40.0% for Grok 4.1 Fast.
  • Construction strategies: Mode 5 achieves 91.07% Overall Success Rate on MultiChallenge without a human prior, while Mode 3 reaches 92.86% with an expert prior and online evolution.Across configurations, the best HotpotQA results are 78.79% Ans F1 and 66.30% Ans EM, gains of 7.58 and 7.50 points over the unguided baseline.
  • Construction strategies: Iterative evolution recovers flawed expert initialization on MultiChallenge, raising success from 58.93% after the expert graph to 92.86% with validation-gated updates.A single offline update lowers success further to 53.57%, whereas the iterative configuration gains 33.93 points over expert initialization.
  • Usage and efficiency: Localized generative guidance achieves the highest performance across three benchmarks, while reducing total tokens relative to full-graph generative guidance.Localization reduces total tokens by 70.9% on ALFWorld, 18.1% on GDPval, and 14.8% on MultiChallenge; it also shortens solver steps on GDPval and ALFWorld.

6. Conclusion

The paper concludes that Procedural Graphs provide editable procedural knowledge and localized guidance for LLM agents, while self-evolution improves graphs from execution feedback. Across tasks and model families, PG consistently improves over memory-based baselines without updating model weights.

  • 6. Conclusion: Procedural Graphs give LLM agents a queryable representation of what to do next while preserving reasoning flexibility.The graph connects current progress with relevant transitions and execution advice.
  • 6. Conclusion: PG consistently improves performance over memory-based baselines across tasks and model families.The conclusion reports consistent gains rather than a result tied to one benchmark or model.
  • 6. Conclusion: Self-evolution builds effective graphs from minimal initializations and repairs expert priors that initially hinder performance.The loop revises procedural knowledge from execution feedback without updating model weights.
  • Related work: Procedural memory remains less explicitly treated than semantic and episodic memory in prior agent architectures.The related-work discussion places procedural memory largely in model weights or ad hoc artifacts, while PG stores state-conditioned action transitions that can be retrieved and updated.
  • Related work: Prior agents use diverse execution, tool-selection, workflow, and trajectory-memory mechanisms, but many leave admissible transitions implicit.These approaches include interleaved reasoning and acting, planning and execution separation, tool catalogs, explicit workflows, and reflective memories.
  • Related work: PG differs from nearby approaches by combining typed graph transitions, localized structural retrieval, and refinement through graph edits.AutoGuide is identified as the closest approach, while other methods provide conditional guidelines, workflows, tool graphs, or trajectory-derived artifacts without the same combination.

A.5. Detailed Comparison Table

The comparison table distinguishes methods by representation, access, updateability, edge semantics, and deployment scope. PG’s distinctive contribution is updating the procedure graph itself while combining attributed transitions with localized guidance.

  • Comparison scope: Table 4 compares 24 representative methods across eight design dimensions, while experiment-specific baseline configurations are documented separately.The dimensions summarize representations and access mechanisms from cited work.
  • Design dimensions: Methods differ in what they store, how they access it, and what can be updated.The comparison spans textual rules, code libraries, workflows, explicit graphs, trajectory memories, and other procedural artifacts.
  • PG representation: PG stores transitions between tool calls and reasoning steps with conditions, guidance, and pitfalls as edge attributes.Its graph supports local structural retrieval and inspection of procedural dependencies.
  • Update target: PG updates the procedure graph through node and edge edits, unlike methods that revise insights, skills, workflows, or tool transitions.The comparison frames this update target as part of PG’s contribution.
  • Distinctive contribution: PG’s contribution is the combination of attributed transitions, localized guidance, and structural refinement rather than graph structure or conditional knowledge alone.This distinguishes the method from related graph and rule-based representations.
  • Baseline families: The compared baselines span episodic summaries, trajectory retrieval, insight distillation, conditional guidelines, workflow induction, and textual transition rules.Named examples include MemoryBank, RAP, ExpeL, AutoGuide, AWM, and KnowAgent.

B.1. Datasets and Splits

The appendix documents dataset statistics, held-out validation splits, and benchmark-specific episode allocations used in the experiments.

  • Dataset statistics: Table 5 summarizes the sample counts and splits used across all experiments.The table is the appendix’s central dataset-statistics reference.
  • Validation splits: The held-out validation set is separate from both training and test data and is consumed by the acceptance gate.Its size is 1,000 for HotpotQA and 100 for MultiChallenge.
  • EnterpriseArena: EnterpriseArena uses 20 validation episodes, while each configuration runs 50 training and 50 test episodes.The appendix separately specifies the environment mechanics for EnterpriseArena.
  • Self-evolution splits: Self-evolution processes training data in sequential strides of 100 samples on HotpotQA and 20 on MultiChallenge.These stride sizes determine how training tasks are batched during evolution.

B.2. Evaluation Metrics

The appendix defines benchmark metrics, baseline injection mechanisms, graph sizes, prompt variants, and structural checks used to evaluate and implement PG. It also separates frozen online inference from offline graph evolution.

  • Evaluation metrics: HotpotQA uses LLM-judged answer accuracy, with strict Exact Match and word-level F1 additionally reported in the construction study.The judge receives the question, gold answer, and agent answer and returns a binary equivalence verdict.
  • Evaluation metrics: MultiChallenge reports Overall Success Rate together with Inference Memory, Instruction Retention, Reliable Versioned Editing, and Self ...The supplied metric description lists four evaluation axes alongside the overall score.
  • Baseline control: All baselines share the same ReAct solver, tool interface, decoding configuration, and training split as PG.They differ in the artifact distilled from trajectories and how it is injected at inference time.
  • Baseline mechanisms: MemoryBank retrieves experience summaries, RAP retrieves similar trajectories, ExpeL injects distilled insights, AutoGuide retrieves state-conditioned guidelines, AWM retains workflows, and KnowAgent uses static action rules.These mechanisms represent the main memory and procedural baselines compared with PG.
  • Graph sizes: The main experimental graphs contain 7–17 nodes and 7–27 triplets outside BFCL v3, whose 131 nodes mirror its large function catalog.The relation vocabulary contains LEADS_TO, TRIGGERS, PROVIDES_INPUT_FOR, and CONVERGES_TO.
  • Prompt templates: At each step, guidance prompts combine graph context, the current observation, and recent trajectory information to generate actionable next-step advice.The prompt uses edge conditions, guidance, and pitfalls, while solver prompts preserve the ReAct Thought/Action format.
  • Prompt variants: The full-graph and local-subgraph guidance variants use the same prompt wording and differ only in graph scope.The appendix states that the two ablation rows therefore differ in graph context rather than requested output length.
  • Evolution and validation: During online inference the graph is frozen, whereas offline self-evolution modifies graph topology and attributes from execution feedback.Candidate preparation validates edits, endpoints, and reachability to a terminal node.

C.2. Results and Survival Analysis

EnterpriseArena results show that Procedural Graph guidance improves survival or lifespan across the evaluated solvers, outperforming memory baselines on most compared models.

  • 58.0% survival on Claude Sonnet 4.6 is a 14.0-point gain over the baseline.
  • 34.0% survival on Gemini 3.1 Pro rises from 6.0%, while final mean cash increases from $2.18M to $22.99M.
  • 40.0% survival on Grok 4.1 Fast rises from 26.0%, with final mean cash increasing from $23.62M to $30.20M.
  • PG exceeds MemoryBank and RAP on Gemini 3.1 Pro, Claude Sonnet 4.6, and Grok 4.1 Fast, while all methods tie at 0.0% on Gemini 3.5 Flash.

C.3. Case Study: Three Agents Facing the First Crisis

The crisis case study contrasts agents that repeatedly violate fundraising constraints with a Procedural Graph agent that tracks pending funding, runway, and delivery timing to survive the simulated crisis.

  • The baseline agent submits fundraising requests while earlier requests remain pending, causing rejections under the single-pending-request constraint.
  • The memory summarization agent recognizes shrinking runway but submits inconsistent amounts and repeats requests while earlier funding remains pending.
  • The PG-guided agent initiates fundraising early, tracks pending funding, checks projected runway, and advances months while awaiting delivery.
  • The PG-guided trace adheres to delivery-lag and single-pending constraints and survives to Month 132.
  • These traces illustrate behaviors on one matched instance and do not establish how frequently they occur across runs.

D.1. Efficiency and Robustness Statistics

Efficiency and robustness results show trade-offs among construction modes: iterative evolution can achieve high success with moderate resources, while formatting and token-use patterns vary by task.

  • 92.86% success is achieved by Mode 3 on MultiChallenge using 6.73 steps and 128.50 seconds per sample.
  • Mode 5 uses 5.05 steps and 92.81 seconds per MultiChallenge sample, compared with 8.02 steps and 166.57 seconds for Mode 4.
  • Mode 5 reduces MultiChallenge latency and steps relative to the hand-crafted Mode 1 graph and has the lowest PG latency on HotpotQA at 31.53 seconds.
  • The association between initialization and formatting differs across tasks and does not establish that a graph schema causes fewer parsing failures.
  • Mode 5 uses 7,984.50 MultiChallenge tokens versus 14,859.80 for Mode 4, but its HotpotQA token use exceeds Mode 4’s.
  • 17.23 to 3.08 tool invocations per simulation month is an 81.8% reduction after evolution, stabilizing at 3.13 by Round 8.

E.3. Step-by-Step Topological Analysis

Topological analysis shows self-evolution progressively adds procedural structure, working-memory transitions, and task-specific corrections, enabling strong validation performance from scratch or after repairing a flawed prior.

  • The minimal Start →End baseline lacks intermediate procedural guidance, leaving the agent to infer action sequences from its trajectory.
  • Generation A adds a backbone from cash auditing through runway forecasting, note saving, market checking, and capital decisions.
  • Mode 5 rises from 77.59% to a peak validation F1 of 83.31% at Generation 10 on HotpotQA.
  • On MultiChallenge, pruning reduces the mismatched graph from 13 to 10 edges by Generation 5 before restructuring raises validation accuracy to 93.9%.
  • The repaired prior ultimately approaches the scratch-built Mode 5 at 94.9%, showing recovery from an unsuitable human-designed initialization.

F.1. BFCL: Stopping After a Requested Quote

The Procedural Graph helps agents stop after satisfying a requested airfare quote instead of continuing into unrequested booking actions. A graph revision similarly shifts behavior from evaluating a dialogue to answering the user while preserving the required passive-voice constraint.

  • BFCL: Stopping After a Requested Quote: The PG agent stopped after reporting the $220 airfare quote, whereas the baseline continued into payment and booking operations.Both agents retrieved the same $220 quote; the PG run ended the turn after reporting the price.
  • BFCL: Stopping After a Requested Quote: The PG rationale explicitly treated the absence of a booking request as a reason not to call book_flight.Its final response reported the economy fare from Rivermist to Stonebrook on October 6, 2024, as $220.00.
  • BFCL: Stopping After a Requested Quote: The baseline’s extra authentication, card, and booking actions led to an unsuccessful attempt, a budget-limit change, and a state mismatch at turn 0.The PG run advanced to the next user instruction and eventually succeeded, while the baseline failed on the first turn after exceeding the requested quote.
  • MultiChallenge: Graph Revision and Observed Responses: Generation 2 directly finished after analyzing the target question and answered whether passive sentence construction was consistent, rather than answering the user’s joke request.The recorded path was ParseHistory → AnalyzeTargetQuestion → Finish, and its response was a meta-evaluation.
  • MultiChallenge: Graph Revision and Observed Responses: Generation 3 removed the direct Finish edge and added guidance against meta-evaluation, producing a passive-voice joke instead.Its path added ExtractConstraints before Finish, and the saved success indicator changed from 0 to 1.
Loading 2609.09153v1…