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

LLM agents often leave procedural order implicit in growing action histories, putting procedural coherence on unconstrained generation. Procedural Graphs make procedures editable and provide progress-conditioned guidance, ranking first or joint first in 21 of 24 model–benchmark settings.

  • Problem

    Agents often leave procedural order and conditions implicit in flat histories, putting procedural coherence on free-form generation; progress-conditioned guidance over editable procedures remains a gap.

    Source: §1 · p. 1

  • Method

    Procedural Graphs represent procedural knowledge as editable directed graphs; online guidance uses the agent’s current progress, while an LLM refiner revises graph structure and attributes from execution feedback.

    Source: §1 · p. 2

  • 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 in each setting.

    Source: §5.1 · p. 7

  • Takeaways & Limitations

    The findings support learning and revising procedural knowledge from execution feedback without updating model weights.

    Source: §6 · p. 11

    Guidance increases token use even when it reduces solver steps.

    Source: §6 · p. 11

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

Long-horizon LLM agents can lose objectives, use tools out of order, and repeat unproductive actions when procedural coherence is left to free-form generation over a growing history. The paper introduces the Procedural Graph, an editable procedure representation that provides progress-conditioned guidance and can evolve from execution feedback.

Introduction

  • Existing approaches trade off procedural explicitness and adaptability: textual memories require the solver to reconstruct how experience applies, state-conditioned guidelines do not connect successive steps, and workflows often require manual design.Automated workflow search reduces manual design effort but optimizes structure offline; the remaining challenge is editable procedures with guidance conditioned on current progress.Source: §1 · p. 1
  • The design aims to steer agents away from invalid behavior while preserving reasoning freedom, responding to progress, and improving from experience.The introduction motivates these requirements before presenting the graph and its online and offline mechanisms.Source: §1 · pp. 1–2
  • A Procedural Graph represents procedures as directed (procedure, relation, procedure) triplets, with nodes for actions, reasoning steps, and states and annotated edges for permissible transitions.Its procedural knowledge remains outside model weights, where it can be inspected, retrieved, and edited without retraining.Source: §1 · p. 2, Figure 1 · p. 2
  • Online, the framework localizes the active node from the trajectory and converts its surrounding subgraph and edge attributes into situational guidance for the next step.The guidance steers execution without dictating the agent’s reasoning.Source: §1 · p. 2
  • Offline, an LLM refiner contrasts failed and successful trajectories to propose graph edits, adopting structurally valid candidates that match or improve held-out validation performance and retaining rejected edits as negative constraints.Edits can add missing nodes and edges, prune failure-inducing ones, or revise edge attributes.Source: §1 · p. 2
  • Across tasks and LLMs, Procedural Graphs consistently outperform memory baselines; self-evolution from scratch matches or surpasses hand-designed graphs and can repair flawed expert priors.These claims are stated as contributions; no numerical results are provided in the supplied passages.Source: §1 · p. 2

2. Related Work

Related work spans free-form action selection, explicit planning structures, and reusable knowledge distilled from trajectories. Procedural Graph combines editable procedure transitions with context-local retrieval and refinement from execution feedback.

LLM Agents and Action Selection

  • Free-form agent loops such as ReAct leave valid action transitions implicit and can suffer planning hallucination, drift, and repetitive loops (Yao et al., 2023b; Xiao et al., 2024; Zhu et al., 2025).Successors add self-critique, branching search, or richer action spaces (Qin et al., 2024; Shinn et al., 2023; Wang et al., 2024a; Yao et al., 2023a).Source: §2 · p. 3

Structured Priors for Agent Planning

Self-Improving Agents from Trajectories

  • Trajectory-derived knowledge includes self-critiques, insights, guidelines, workflows, and procedural memories, while PG connects procedure steps in an editable graph with typed, attributed edges for local retrieval and feedback-driven refinement (Shinn et al., 2023; Zhao et al., 2024; Fu et al., 2024; Wang et al., 2025b; Fang et al., 2025; Zhong et al., 2024).Appendix A provides an extended survey and an eight-dimension comparison of 24 methods.Source: §2 · p. 3

3. The Procedural Graph Framework

The Procedural Graph makes procedural knowledge explicit to guide agent execution online, while an offline feedback loop iteratively adapts the graph’s topology and attributes.

3. The Procedural Graph Framework

  • The framework separates frozen-graph online inference, which generates situational guidance, from offline LLM refinement based on diagnostic traces.The refiner modifies graph topology and attributes after batches of training tasks.Source: §3 · p. 3

3.1. Formal Representation of Procedural Graphs

  • A Procedural Graph represents abstract procedures as nodes and admissible directed transitions as attributed edges, with fields for conditions, guidance, and pitfalls.Nodes may represent tool functions, skills, reasoning steps, or task statuses.Source: §3.1 · pp. 3–4

3.2. Generative Guidance at Inference Time

  • At each step, an exact match to the latest procedure locates the agent; a guidance LLM uses its connected outgoing neighborhood and recent trajectory to guide the solver.If matching fails, guidance uses the full graph; the solver receives guidance alongside the query and trajectory, preserving flexible reasoning.Source: §3.2 · pp. 4–5

3.3. Self-Evolution of Procedural Graphs

  • The refiner contrasts high- and low-scoring traces to identify failure loops and successful shortcuts, then adds or deletes nodes and edges or revises edge attributes.For binary outcomes, the comparison reduces to successes versus failures.Source: §3.3 · p. 5
  • Structurally valid candidates are retained only if their independent validation score matches or exceeds the current graph’s; rejected edits and outcomes inform later proposals.The rejection history helps the refiner avoid previously unsuccessful edits.Source: §3.3 · pp. 5–6

4. Experimental Setup

The evaluation spans seven procedural-reasoning benchmarks and compares procedural-memory approaches under a shared ReAct solver across four LLMs.

Benchmarks

  • Seven benchmarks span multi-hop QA, multi-turn instruction retention, professional tasks, embodied actions, policy-compliant tool use, function calling, and long-horizon financial decisions.The benchmarks are HotpotQA, MultiChallenge, GDPval, ALFWorld, τ-bench, BFCL, and EnterpriseArena.Source: §4 · p. 6

Baselines

  • Methods share the ReAct solver (Yao et al., 2023b), differing in how they store and reuse procedural experience; learning-based baselines use the same training trajectories as self-evolution.Baselines range from no memory and summarized experience to retrieved exemplars, natural-language insights, guidelines, workflows, and textual action-transition rules.Source: §4 · p. 6

Models

  • The study evaluates Claude Sonnet 4.6, Gemini 3.1 Pro, Gemini 3.5 Flash, and Grok 4.1 Fast, using greedy decoding at temperature 0.The guidance model and offline refiner share the solver’s underlying LLM.Source: §4 · p. 6

Procedural Graph Configuration

  • Online guidance uses a 2-hop neighborhood around the localized node and a recent trajectory window of 3; guidance and refinement use the solver’s LLM.Graph construction strategies are compared in Section 5.3.Source: §4 · p. 6

5. Results

Across benchmarks, the Procedural Graph performs strongly across model families, while construction and self-evolution can improve or repair graphs. Localized generative guidance also improves benchmark scores and reduces token use relative to full-graph guidance.

5.1. Main Results across Benchmarks and Models

  • PG ranks first or joint first in 21 of 24 model–benchmark settings, with 19 wins, two ties, and three losses versus the strongest baseline (p=4.3 × 10−4).On GDPval and BFCL v3, PG outperforms every baseline under all four LLMs; on HotpotQA, margins over the strongest baseline range from −0.90 to +1.30 points.Source: Table 1 · p. 7, §5.1 · p. 7

5.2. Long-Horizon Decision Making and Resilience

  • PG achieves the highest or joint-highest full-horizon survival and longest average lifespan across all four LLMs in EnterpriseArena.For Claude Sonnet 4.6, survival rises from 44.0% to 58.0%; for Gemini 3.1 Pro, from 6.0% to 34.0%; and for Grok 4.1 Fast, from 26.0% to 40.0%, with a $39.62M average enterprise score. Gemini 3.5 Flash tool calls fall from 18.94 to 12.53 per month as its score improves, while fundraising rises from $0.00M for baseline Flash to $9.39M for PG-guided Flash and $30.11M for PG-guided Grok 4.1 Fast.Source: §5.2 · p. 8

5.3. Procedural Graph Construction Strategies

  • On HotpotQA, Mode 5 scores 78.79% Ans F1 and 66.30% Ans EM; on MultiChallenge, Mode 5 reaches 91.07% Overall Success Rate and Mode 3 reaches 92.86%.Mode 5 gains 7.58 F1 points and 7.50 EM points over the unguided baseline; it is Scratch + Online Evolution, while Mode 3 is Expert + Online Evolution.Source: §5.3 · p. 9, Table 2 · p. 9
  • On MultiChallenge, iterative Mode 3 recovers performance from a flawed expert prior, reaching 92.86% success after Mode 1 falls to 58.93% and Mode 2 to 53.57%.Mode 3 gains 33.93 points over the expert initialization, combining fresh execution feedback with validation gating.Source: §5.3 · p. 9

5.4. Procedural Graph Self-Evolution

  • Validation survival rises from 0.0% for the unguided baseline to 45.0% in Round 1, 80.0% in Round 2, and 90.0% in Round 8, remaining there in Round 9.Round 1 adds a sequence to audit cash and forecast runway before financing; Round 2 adds recall_notes and reduces tool use from 17.23 to 3.08 calls per month versus baseline. Rounds 3–6 yield no committed update, and Round 10 is rejected.Source: Figure 4 · p. 9, §5.4 · p. 10
  • The returned evolved graph reaches 85.0% test survival versus 0.0% for baseline (Fisher’s exact p=2.6 × 10−8), while the best intermediate round reaches 95.0%.The paper reports the returned graph’s result rather than the best intermediate round to avoid selecting on the test set; decisions from 20 episodes per split are described as a search trace, not significance tests.Source: Figure 4 · p. 9, §5.4 · p. 10

5.5. Efficiency Analysis

  • Localized generative guidance scores 89.31 on MultiChallenge, 63.99 on GDPval, and 81.53 on ALFWorld, exceeding the best alternative by 2.0, 6.8, and 9.0 points, respectively.Raw full-graph injection raises MultiChallenge from 80.27 to 86.60 but lowers ALFWorld from 72.58 to 70.34; full-graph generative guidance reduces ALFWorld to 54.48 while increasing token consumption.Source: Table 3 · p. 10, §5.5 · p. 10
  • Localization reduces tokens versus full-graph generative guidance by 70.9% on ALFWorld, 18.1% on GDPval, and 14.8% on MultiChallenge.On GDPval and ALFWorld, solver steps fall from 28.20 to 18.57 and from 21.84 to 18.80, respectively, while token consumption remains 33.4% and 55.4% higher than the no-graph baseline.Source: Table 3 · p. 10, §5.5 · p. 10

6. Conclusion … A.4. Self-Improving Agents from Trajectories

The paper presents Procedural Graphs as explicit, editable procedural memory for LLM agents, connecting progress to relevant transitions and execution advice. Across tasks and model families, they improve over memory-based baselines, while self-evolution builds useful graphs from minimal starts and repairs expert priors that initially hinder performance.

6. Conclusion

  • PG makes procedural knowledge explicit and editable, delivers consistent gains over memory-based baselines, and self-evolution builds effective graphs from minimal starts and repairs harmful expert priors.The conclusion notes that guidance increases token use even when it reduces solver steps; future work could reuse guidance across steps or generate it selectively, and evaluate transfer across solvers and tool interfaces.Source: §6 · p. 11

A. Extended Related Work and Comparison

  • The related-work appendix surveys procedural memory, action selection, structured planning, and trajectory-based self-improvement, situating PG's procedural-memory role within an eight-dimension comparison.It expands the paper's Section 2 and compares approaches in Appendix A.5.Source: A. Extended Related Work and Comparison · p. 16, §A.1 · p. 16

A.1. Procedural Graphs as Procedural Memory: A CoALA View

  • In CoALA (Sumers et al., 2023), procedural memory is comparatively under-treated; PG implements that module by storing state-conditioned action transitions for retrieval and updating.CoALA distinguishes procedural memory from working, episodic, and semantic memory; procedural knowledge otherwise remains largely implicit in model weights or scattered across artifacts.Source: §A.1 · p. 16

A.2. LLM Agents and Action Selection

  • Existing agent methods generally leave admissible transitions implicit, contributing to planning hallucination, long-horizon drift, and repetitive loops when execution feedback is ambiguous.These failure modes motivate explicit structural priors for planning.Source: §A.2 · p. 16

A.3. Structured Priors for Agent Planning

  • PG connects tool calls and reasoning steps, adds condition, guidance, and pitfall attributes to transitions, localizes the current procedure, and supports explicit topology and attribute edits.Unlike tool-selection, workflow, and agent-communication graphs, PG retrieves connected transitions and makes their structure and attributes editable.Source: §A.3 · p. 17

A.4. Self-Improving Agents from Trajectories

  • Prior trajectory-learning systems use episodic reflection, contrastive insights, conditional guidelines, or reusable skills and workflows; AutoGuide is closest, while PG adds connected editable transitions.MemP shares a focus on procedural-memory lifecycle operations but stores trajectories and script-like abstractions without an explicit procedure graph.Source: §A.4 · pp. 17–18

A.5. Detailed Comparison Table · B. Experimental Details

Table 4 compares PG with 24 representative methods across eight design dimensions, while Appendix B describes the experimental materials and procedures. The comparison distinguishes representations, access modes, and update targets, including PG’s attributed transitions and graph refinement.

A.5. Detailed Comparison Table

  • Methods differ in what they store and how they access it: examples include KnowAgent’s prompt text, FlowBench’s conditional flowcharts, and AFlow’s code-represented workflows.Tool graphs support navigation through tool catalogs; PG retrieves a neighborhood around the current procedure.Source: §A.5 · p. 18
  • PG stores transitions between tool calls and reasoning steps, attaching conditions, guidance, and pitfalls to edges and retrieving the current procedure’s neighborhood.Its contribution combines attributed transitions, localized guidance, and structural refinement, rather than graph structure or conditional knowledge alone.Source: §A.5 · pp. 18–19
  • Methods also differ in their improvement targets: ToolNet derives tool transitions from trajectories, SkillGraph updates skill banks with query-conditioned agent communication, and PG edits its procedure graph.Other methods revise insights, skills, or workflows.Source: §A.5 · p. 18
  • The comparison dimensions define representation form, stored-knowledge granularity, structure source, trajectory-based updatability, retrieval mode, edge meaning, and intended deployment scope.“Graph” distinguishes explicit workflow, tool, or communication graphs from text-encoded auxiliary structures and representations without explicit graph organization.Source: §A.5 · pp. 18–19
  • Table 4 compares PG with 24 representative methods across eight design dimensions; baseline configurations are specified separately in Appendix B.3.The table summarizes representations and access mechanisms described in the cited work.Source: §A.5 · p. 18, Table 4 · p. 19

B. Experimental Details

  • Appendix B provides dataset splits, evaluation metrics, baseline implementation details, prompt templates, and the full self-evolution algorithm in Appendix B.6.Source: B. Experimental Details · p. 19

B.1. Datasets and Splits … C.1. EnterpriseArena Mechanics and Crisis Schedule

The appendices document the benchmark splits, evaluation metrics, baseline and graph implementations, prompts, and self-evolution procedure. They also specify EnterpriseArena’s long-horizon simulation mechanics and evaluation measures.

B.1. Datasets and Splits

  • EnterpriseArena runs 50 training and 50 test episodes per configuration; its validation set has 20 episodes, while HotpotQA and MultiChallenge validation sets contain 1,000 and 100 samples.Table 5 summarizes sample counts and splits; self-evolution processes training data in strides of 100 samples for HotpotQA and 20 for MultiChallenge.Source: §B.1 · pp. 19–20, Table 5 · p. 20

B.2. Evaluation Metrics

  • Evaluation metrics vary by benchmark, covering judged answer accuracy, rubric or task success, function-call accuracy, and EnterpriseArena survival, lifespan, score, and capital raised.HotpotQA also uses strict Exact Match and word-level F1 in the construction study; MultiChallenge scores overall success and four named axes, while τ-bench reports Pass@1.Source: §B.2 · p. 20

B.3. Baseline Implementation Details

  • Baselines compare six memory mechanisms: MemoryBank summaries, RAP trajectory retrieval, ExpeL insights, AutoGuide guidelines, AWM workflows, and KnowAgent action rules.These methods differ in the artifact distilled from trajectories and how it is organized or injected at inference.Source: §B.3 · pp. 20–21

B.4. Procedural Graph Statistics

  • Main-experiment graphs use four relation types; excluding BFCL v3’s 131-node graph, they contain 7–17 nodes and 7–27 triplets, with guidance the most consistently populated edge attribute.Most edges carry condition, guidance, and pitfalls attributes.Source: §B.4 · p. 21, Table 7 · p. 21

B.5. Prompt Templates

  • Shared benchmark prompts govern ReAct execution, translate local or full graph context into actionable guidance, and direct offline graph refinement.Guidance uses edge conditions, guidance, and pitfalls to advise next actions and recovery; refiner instructions cover pruning or adding graph structure based on trajectories.Source: §B.5 · pp. 21–23

B.6. Self-Evolution Algorithm

  • The self-evolution algorithm holds the graph fixed during each episode and validates candidate edits only after structural checks, retaining diagnostics for failed candidates.Checks include valid endpoints and a directed path from every node to a terminal node; when cycles are disallowed, detected cycle-closing edges are removed before validation.Source: §B.6 · p. 24

C. Long-Horizon Analysis on EnterpriseArena

  • The EnterpriseArena appendix describes the simulator, its evaluation metrics, survival and cash trajectories, and trace comparisons among baseline, memory-summarization, and graph-guided agents.Source: C. Long-Horizon Analysis on… · p. 24

C.1. EnterpriseArena Mechanics and Crisis Schedule

  • EnterpriseArena simulates a microfinance lender for up to 132 months, with delayed and capped fundraising, bankruptcy upon negative cash, and three scheduled crises.Crises occur at months 32, 59, and 112, with worsening repayment rates and increasingly severe economic or liquidity shocks. Metrics include full-horizon survival, average months, information-tool calls per month, financing received, and a time-averaged score that may remain positive after bankruptcy.Source: §C.1 · pp. 25–26

C.2. Results and Survival Analysis

On four planning configurations, the Procedural Graph improves full-horizon survival for three solvers and mean lifespan for all four, with gains varying by solver. Gemini 3.5 Flash shows a lifespan improvement but no full-horizon survival improvement.

C.2. Results and Survival Analysis

  • PG raises full-horizon survival to 58.0% for Claude Sonnet 4.6, 34.0% for Gemini 3.1 Pro, and 40.0% for Grok 4.1 Fast; Flash remains at 0.0%.Against the unguided baseline, survival rises from 44.0% to 58.0% for Claude, 6.0% to 34.0% for Gemini 3.1 Pro, and 26.0% to 40.0% for Grok. For Flash, mean lifespan rises from 33.58 to 40.62 months, although no evaluated configuration survives the full horizon; PG improves mean lifespan for all four solvers.Source: Table 8 · p. 26, §C.2 · pp. 26–27
  • Figure 3 shows survival curves above individual cash paths, their mean, and 95% confidence intervals for four planning configurations across four solvers.Survival gains vary across the solvers.Source: §C.2 · p. 26
  • PG’s final mean cash is $76.03M for Claude, $22.99M for Gemini 3.1 Pro, and $30.20M for Grok, versus $2.18M and $23.62M baselines for the latter two.Claude’s mean cash trajectory stays above the $5.0M liquidity warning threshold; Grok’s baseline final mean cash is $23.62M.Source: §C.2 · p. 27
  • PG exceeds both MemoryBank and RAP in full-horizon survival on Claude Sonnet 4.6, Gemini 3.1 Pro, and Grok 4.1 Fast; all methods tie at 0.0% on Flash.MemoryBank exceeds RAP on Gemini 3.1 Pro (22.0% vs. 6.0%) and Claude Sonnet 4.6 (56.0% vs. 50.0%).Source: Table 8 · p. 26, §C.2 · p. 27

C.3. Case Study: Three Agents Facing the First Crisis · D. Procedural Graph Construction: Supplementary Results

On one crisis-transition task instance, the Procedural Graph-guided agent tracks pending funding and runway, obeys constraints, and survives to Month 132, while baseline and memory-summary agents make invalid requests; these traces illustrate behaviors but not their frequency across runs. The appendix also reports supplementary construction results, failure-mode case studies, strategy formulations, and experimental configurations.

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

  • The traces compare Grok 4.1 Fast agents on the same Seed 14 instance during Months 29–33, with condensed logs and editorial annotations.The comparison examines a critical transition into the first macroeconomic crisis.Source: §C.3 · p. 27
  • The baseline agent initially denied bankruptcy risk despite falling cash, then submitted debt funding while an equity request was pending and was rejected.The trace reports cash falling to $683K and runway below one month before the rejection.Source: §C.3 · p. 27
  • The memory-summary agent recognized an eroding runway but repeatedly submitted requests while funding was pending and used amounts inconsistent with its stated millions.It reasoned about $18M and $20M raises but submitted amounts of 18 and 20.Source: §C.3 · p. 28
  • The Procedural Graph agent raised equity ahead of the contraction, forecast cash flow, and waited through the delivery lag while adhering to funding constraints.An earlier equity request delivered $28.8M after the market-capacity cap; the agent then submitted a further equity request and forecast runway.Source: §C.3 · p. 28
  • The PG-guided agent tracked pending funding, checked runway, and advanced months while awaiting delivery, surviving to Month 132; the other traces show invalid requests, but not their frequency across runs.The case study concerns one identical task instance, not comparative behavior frequency across runs.Source: §C.3 · pp. 28–29

D. Procedural Graph Construction: Supplementary Results

  • The supplementary-results appendix covers quantitative construction results, construction failure-mode case studies, five strategy formulations, and detailed experimental configurations.The supplied passage lists these appendix contents but gives no quantitative result values.Source: D. Procedural Graph Construction:… · p. 29

D.1. Efficiency and Robustness Statistics … E.2. Candidate Screening: Three Cases

Across the construction modes and EnterpriseArena evolution, the appendix reports resource and robustness tradeoffs, reduced tool use, and validation or structural checks that reject some candidate graph updates. It also specifies how the five modes and experimental setup differ.

D.1. Efficiency and Robustness Statistics

  • On MultiChallenge, Mode 5 used 5.05 steps and 92.81 seconds per sample versus Mode 4’s 8.02 steps and 166.57 seconds; Mode 3 had the highest success rate at 92.86%.Mode 2 had the lowest step count (4.32) and latency (65.93 seconds), but also the lowest success rate (53.57%). On HotpotQA, Mode 5 had the lowest latency among PG configurations at 31.53 seconds. Mode 5 token use was 7,984.50 on MultiChallenge versus Mode 4’s 14,859.80, but on HotpotQA it was 10,115.89 versus Mode 4’s 6,396.90; total tokens reflect interaction length and outputs, not graph compactness alone.Source: Table 10 · p. 29, §D.1 · pp. 29–30, Table 9 · p. 29
  • On HotpotQA, expert-initialized Modes 1–3 had fewer parsing failures than scratch-initialized Modes 4–5, while MultiChallenge Mode 5 had fewer than Mode 4.HotpotQA failures per sample were 0.005 for Mode 2, 0.007 for Mode 1, 0.009 for Mode 3, and 0.016 for each of Modes 4 and 5; MultiChallenge values were 0.57 for Mode 5 and 1.07 for Mode 4. The initialization association differs by task and does not establish that a particular schema caused the reduction.Source: §D.1 · pp. 29–30, Table 9 · p. 29, Table 10 · p. 29

D.2. Graph Construction Modes

  • The five construction modes vary by expert or skeleton initialization, offline or incremental refinement, and whether validation safeguards restore a previous best graph.Mode 1 is static and hand-crafted; Modes 2 and 4 make one-time offline updates without validation safeguards. Modes 3 and 5 refine incrementally and restore the previous best graph if validation performance declines; online evolution occurs between training batches, not within episodes or test evaluation.Source: §D.2 · pp. 30–31

D.3. Experimental Setup

  • Construction-strategy experiments used frozen Gemini 3.5 Flash with greedy decoding; HotpotQA used 1,000/1,000/1,000 train/validation/test samples, and MultiChallenge used 100/100/56.HotpotQA was evaluated by strict Exact Match and word-level F1; MultiChallenge used a Gemini 3.1 Pro judge for overall success and four challenge axes.Source: §D.3 · p. 31

E. Round-by-Round Self-Evolution on EnterpriseArena

  • Table 11 tracks ten EnterpriseArena evolution rounds, with deltas relative to the previous best validation checkpoint and gray rows marking rounds without a committed update.The appendix’s round-by-round discussion points to tool use and candidate screening as related analyses.Source: E. Round-by-Round Self-Evolution on… · p. 31, Table 11 · p. 32

E.1. Computational Efficiency

  • Validation-split tool invocations fell 81.8%, from 17.23 per month at baseline to 3.08 in Round 2, stabilizing at 3.13 by Round 8.The evolved graph guides the agent to query cash balances and market metrics once per cycle, rather than repeatedly within a turn.Source: §E.1 · p. 32, Table 11 · p. 32

E.2. Candidate Screening: Three Cases

  • Validation screening rejected candidates for performance decline, structural failure, or a training–validation gap, retaining the Round 9 graph after Round 10.Round 3’s fundraising-threshold change reduced validation survival by 15.0 points and lifespan by 10.45 months; Round 5 failed structural verification, so validation was skipped. In Round 10, 90.0% training survival contrasted with 85.0% validation survival (−5.0 points), and validation enterprise score decreased by $0.184M.Source: §E.2 · p. 33

E.3. Step-by-Step Topological Analysis … F. Additional Execution Cases

Procedural Graphs evolve their topology to provide task-specific guidance, including memory and branch control, and can improve from scratch or repair an unsuitable prior. The cases also show that shorter solver trajectories do not necessarily reduce token use.

E.3. Step-by-Step Topological Analysis

  • With only Start →End at initialization, the agent had to infer action sequences from its trajectory, causing redundant tool calls, high computational cost, and missed tasks such as cash forecasts.Source: §E.3 · p. 33
  • Evolution added a cash-audit and forecasting backbone, inserted recall_notes for cross-month memory, pruned pass_action, and later bypassed book_closing after fundraising requests.The bypass was retained through Round 10 because the environment adapter already advances the month after a fundraising request; the graph instead directs reassessment in the new month.Source: Figure 5 · p. 34, §E.3 · p. 34

E.4. Self-Evolution on HotpotQA and MultiChallenge

  • The HotpotQA and MultiChallenge studies compare Mode 3, evolved from an expert-designed prior, with Mode 5, evolved from scratch.Figure 6 shows the resulting trajectories for the two tasks.Source: §E.4 · p. 35, Figure 6 · p. 35

E.4.2. MultiChallenge: Prior Correction and Recovery

  • 54.0% initial MultiChallenge validation accuracy rose to 93.9% after prior repair, approaching scratch-built Mode 5 at 94.9%.The repair pruned mismatched edges, reducing the graph from 13 to 10 edges by Generation 5, then restructured control flow to fit task constraints.Source: Figure 6 · p. 35, §E.4.2 · p. 35

E.4.1. HotpotQA: Emergent Simplicity

  • Mode 5 rose from F1 77.59% to a peak validation F1 of 83.31% at Generation 10, surpassing Mode 3.In this HotpotQA study, evolution from a minimal skeleton yielded more effective guidance than evolution from the hand-designed prior used here.Source: Figure 6 · p. 35, §E.4.1 · p. 35
  • Mode 5 used fewer solver steps than expert-initialized modes on HotpotQA, but its total token use remained higher than in Modes 1, 2, and 4.Shorter trajectories therefore did not imply lower token cost.Source: §E.4.1 · p. 35

F. Additional Execution Cases

  • The additional Gemini 3.5 Flash cases examine BFCL stopping decisions and MultiChallenge graph revision, using solver-trace or saved-attribute quotations.Source: F. Additional Execution Cases · p. 35

F.1. BFCL: Stopping After a Requested Quote · F.2. MultiChallenge: Correcting the Response Objective

The examples show the Procedural Graph guiding agents to stop after a requested quote and revising a path that evaluates a dialogue instead of answering the user. In both cases, the graph’s guidance changes the agent’s actions and outcome.

F.1. BFCL: Stopping After a Requested Quote

  • For the same airfare request, both agents retrieved a $220 quote, but PG stopped because booking was not requested while the baseline continued into payment and booking.The PG solver explicitly reasoned that it should not proceed to book_flight.Source: §F.1 · p. 36
  • PG reported the $220 fare and advanced to the next instruction successfully, while the baseline changed the budget limit, booked after an unsuccessful attempt, and failed with a state mismatch.The baseline failed on the first turn after taking actions beyond the requested quote.Source: §F.1 · p. 36

F.2. MultiChallenge: Correcting the Response Objective

  • In validation sample 059, Generation 2 and 3 candidates received the same query and dialogue history, with an earlier passive-voice constraint and a target question about passive construction.The user request was for a joke about renewable energy or Sheffield.Source: §F.2 · p. 36
  • Generation 2 used ParseHistory →AnalyzeTargetQuestion →Finish and answered the target question by evaluating whether passive construction was consistent.Its candidate attribute called for a direct finish on simple evaluations without drafting.Source: §F.2 · p. 36
  • Generation 3 removed the direct edge to Finish and instructed ExtractConstraints →Finish not to write a meta-evaluation or answer the target question directly.Source: §F.2 · p. 36
  • Generation 3 added ExtractConstraints before Finish, responded with a joke in passive voice, and changed the saved success indicator from 0 to 1, shifting from evaluation to answering the user.The response began, “A joke about renewable energy is being shared.”Source: §F.2 · p. 36

Related papers

Loading 2609.09153v1…