acceptodds
Under review as a conference paper at ICLR 2027

Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

24 views

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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Model Agents, Procedural Knowledge, Graph-Based Planning, Agent Memory, Self-Evolution

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Y4AfOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces Procedural Graphs (PGs), an explicit representation of procedural knowledge intended to improve action selection in LLM agents. The graph represents actions, reasoning steps, and task states as nodes, with attributed edges encoding transition conditions, guidance, and pitfalls in natural language. During inference, the framework localizes the agent's current state, retrieves a local graph neighbourhood, and uses an LLM to generate situational guidance for the next action.

There is an offline self-evolution mechanism that updates graph nodes, edges, and attributes based on successful and failed execution trajectories. Candidate updates are evaluated on a held-out validation set and accepted if performance does not decrease and rejected modifications are retained as negative feedback.

Evaluated on seven benchmarks and four LLMs. They compare against several memory-based and workflow-based baselines. The results show improvements across many settings including long-horizon decision-making.

Critical strengths
  1. The method is practical for maintaining and improving PGs. Explicit procedural representation, step-level guidance, and feedback-driven refinement are useful contribution. Constructing graphs from a minimal initialization and recovering from poorly designed expert priors reduces dependence on manually specified workflows. The paper also provides useful ablations comparing graph construction strategies and methods of incorporating graph information during inference.

  2. Promising empirical results. Broad evaluations across models, benchmarks and baselines. The results are competitive. The EnterpriseArena runs shows changes are associated with agent behaviour, such as anticipating funding requirements and avoiding redundant tool calls, rather than simply increasing the number of actions.

Critical weaknesses
  1. The contribution of the graph representation is not sufficiently isolated.

The proposed framework combines multiple components: structured procedural knowledge, an additional LLM guidance call at each execution step, and iterative refinement with validation-based selection. The paper does not clearly establish how much of the improvement comes specifically from the graph representation.

A flat collection of conditional guidelines could potentially be refined using the same execution feedback and validation procedure, and then converted into situational guidance using the same LLM. Similarly, an additional planning or reflection step might improve a standard ReAct agent without requiring a procedural graph. The ablations in Table 3 compare graph injection and localization strategies, but do not isolate these alternative explanations. This limits the strength of the paper's central claim that the explicit graph structure is responsible for the observed improvements.

  1. Evidence on reliable self-evolution is a bit limited.

The design choices make their generality difficult to assess. In the EnterpriseArena evolution experiment, candidate graphs are selected using only 20 validation episodes, and the same validation set is consulted repeatedly across rounds. Moreover, the acceptance criterion allows updates with equal measured validation performance, even when the evaluation is noisy.

In Table 11 Round 7 achieves 80% validation survival and 95% test survival, whereas Round 8 achieves 90% validation survival but only 85% test survival. This does not invalidate the method, especially given the small sample sizes, but it raises questions about the reliability of checkpoint selection.

  1. The improvements on EnterpriseArena may partly reflect learning benchmark-specific heuristics rather than generalizable long-horizon planning. The evolved graph mostly learns a simple sequence of checking cash, forecasting liquidity, and requesting funding early. It is unclear whether similar gains could be achieved by providing the baseline agent with explicit instructions about liquidity buffers and fundraising delays. A comparison against such a baseline would help establish whether the proposed framework offers benefits beyond discovering effective domain-specific rules.
Questions for authors
  1. Have the authors considered comparing PG against a flat collection of conditional procedural guidelines that undergoes the same iterative refinement and validation process? Would help establish whether explicit graph connectivity provides an advantage beyond learning and updating natural-language instructions.

  2. Since PG introduces an additional guidance LLM call at each decision step, how would the method compare against a compute-matched ReAct agent that uses an additional planning or reflection step without a graph?

  3. In EnterpriseArena, how much of the improvement can be attributed to discovering relatively simple domain-specific strategies, such as maintaining a liquidity buffer and initiating fundraising early?

1 comment

Thank you for distinguishing the performance of the full system from the contribution of its components. We address the new ablation, validation protocol, and EnterpriseArena interpretation below.


1. Contributions of the graph, localization, and guidance

The new local/raw condition directly supplies the localized subgraph without an auxiliary guidance-model call. It uses the same settings as Table 3.

ComparisonMultiChallengeGDPvalALFWorld
Subgraph/raw minus no-graph baseline+8.60+6.55+6.12
Subgraph/raw minus full-graph/raw+2.27+4.18+8.36
Subgraph/generative minus subgraph/raw+0.44+2.64+2.83

These comparisons show gains without the extra guidance call, benefits from localization, and the incremental benefit of generative guidance, respectively. Table 2 separately evaluates refinement: evolution raises the expert-initialized graph's MultiChallenge success rate from 58.93% to 92.86%.

We will add these results to Table 3. They isolate components within PG, but do not replace a compute-matched, graph-free planning or reflection baseline.

2. Comparison with conditional guidelines

AutoGuide retrieves rules from a condition-indexed pool and is the closest existing baseline to the proposed conditional guidelines. ExpeL stores natural-language insights; KnowAgent represents action and transition rules in text. Table 1 gives the following point-estimate comparisons across 24 model–benchmark settings. These results support PG relative to the evaluated methods.

ComparatorPG higherTiedPG lower
AutoGuide2301
ExpeL2202
KnowAgent2211

3. Validation reuse, equal-score updates, and checkpoint selection

For EnterpriseArena, the selection metric is full-horizon survival rate on a fixed set of 20 validation episodes. Training, validation, and test seed sets are disjoint. We accept candidates whose validation survival improves or ties the retained graph, preferring the newer candidate on a tie.

A fixed validation set keeps evaluation cases consistent, but repeated selection can still adapt to that set. One success changes the rate by five percentage points, limiting the gate's resolution. The tie rule retains revisions based on new training feedback when there is no measured validation drop; it does not establish better expected test performance.

From Round 7 to Round 8, validation survival rises from 80% to 90%, while test survival falls from 95% to 85%. Each change corresponds to two episodes. Sampling variability or adaptation to the validation set could explain this reversal; these rounds alone cannot distinguish them. Repeated selection on finite validation data can overfit the selection criterion (Cawley and Talbot, 2010).

The returned graph is selected by validation survival and the stated tie rule. Its test survival is 85%; the intermediate 95% test peak was not used for selection. We will clarify this protocol and avoid implying that every accepted update improves test performance.

4. EnterpriseArena and domain-specific rules

Learning domain-specific procedures is part of PG's intended role. EnterpriseArena requires applying them over up to 132 months, including crises at months 32, 59, and 112, financing delays of one to six months, changing capital limits, repayments, losses, and operating costs. “Raise funds early” still leaves state-dependent decisions about timing, amount, and financing type. Held-out seeds vary stochastic realizations within this environment; the crisis schedule is shared.

Table 8 reports full-horizon survival:

ModelBaselineRAPMemoryBankPG
Claude Sonnet 4.644%50%56%58%
Gemini 3.1 Pro6%6%22%34%
Gemini 3.5 Flash0%0%0%0%
Grok 4.1 Fast26%28%16%40%

PG improves survival for three models; all methods remain at zero for Gemini 3.5 Flash. These comparisons support gains over the evaluated baselines, but do not determine whether explicitly supplying the same liquidity and fundraising rules would achieve similar results. That control remains untested.

We will frame this evidence as learning useful procedures for long-horizon execution within this environment. The separate contributions of rule content and its organization remain unresolved.


Summary

The new ablation shows gains without an auxiliary guidance call, benefits from localization, and further gains from generative guidance on all three benchmarks. Together with the refinement results in Table 2 and the guideline comparisons in Table 1, these findings support the effectiveness of learning, refining, and locally retrieving procedural knowledge. We also clarify that final graph selection uses validation survival, without selecting on the intermediate test peak.

Reviewer_b1zcOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces the Procedural Graph, an explicit and editable representation of procedural knowledge that provides LLM agents with guidance on what to do next through an additional LLM call. It also allows agents to learn from past failures and evolve the graph to improve their execution strategies. Experiments across seven benchmarks show consistent improvements over the original baseline.

Critical strengths
  • The method is simple and intuitive. It combines external procedural memory with guidance, allowing agents to make use of past experience during task execution.

  • The evaluation covers multiple benchmarks and models.

  • Most of the ablation studies make sense and help support the proposed approach.

Critical weaknesses
  • The generalization ability of the proposed method remains unclear.

  • The method introduces considerable additional inference overhead.

Questions for authors
  • Have the authors tried applying a graph optimized on one task to another task? Could a single graph be shared and evolved across multiple tasks?

  • It would be interesting to include a baseline that generates guidance without access to the graph. This could help better separate the contributions of the guidance itself and the procedural graph.

  • Have the authors considered providing guidance selectively (e.g., every two steps) rather than at every step? I wonder whether this could offer a better trade-off between cost and performance.

2 comments

Thank you for the questions about generalization and inference cost.


1. Transferring a graph and sharing it across tasks

Our benchmarks evaluate held-out instances within each task environment. In preliminary trials of transferring and sharing graphs across heterogeneous tasks, we observed lower performance and less focused guidance. Different tool sets, skill vocabularies, and solution procedures appear to introduce irrelevant or conflicting transitions into the shared graph.

These observations suggest that cross-task sharing requires aligning tools and procedures. We will clarify the scope of our environment-specific evaluation and report these unsuccessful attempts as preliminary observations, rather than a systematic transfer study.

2. Inference overhead and raw injection

We completed the local/raw condition using the same test samples, Gemini 3.5 Flash, underlying PG, and solver settings. Each cell reports score / total tokens per sample, including guidance-model tokens where applicable.

BenchmarkNo-graph baselineSubgraph, raw injectionSubgraph, generative guidance
MultiChallenge80.27 / 6,62988.87 / 9,68489.31 / 12,295
GDPval54.80 / 275,63861.35 / 278,33963.99 / 367,738
ALFWorld72.58 / 18,05578.70 / 19,12281.53 / 28,064

Raw subgraph injection uses 21.2%, 24.3%, and 31.9% fewer tokens than generative subgraph guidance, with score reductions of 0.44, 2.64, and 2.83 points. Against the no-graph baseline, it gains 6.55 and 6.12 points on GDPval and ALFWorld for approximately 1.0% and 5.9% more tokens. Its overhead on MultiChallenge is higher: 46.1%.

Compared with full-graph generative guidance, generative subgraph guidance uses 14.8%, 18.1%, and 70.9% fewer tokens, respectively, and achieves higher scores. We will report both subgraph configurations so that the higher scores of generative guidance can be assessed alongside its additional cost.

3. Guidance without graph access

Subgraph/raw gains 8.60, 6.55, and 6.12 points over the no-graph baseline without an auxiliary guidance call. This shows that the improvement does not depend entirely on that call. It does not answer how well an additional advice-generating call would perform without graph access at matched compute; that control remains untested.

4. Less frequent and multi-step guidance

Guidance every two steps, or one call covering two upcoming steps, could reduce calls. Because guidance uses recent observations, either schedule would need a way to detect when new information makes earlier advice stale. We have not evaluated these schedules and will include selective invocation and multi-step guidance as future work.


Summary

The new experiment identifies an effective lower-cost PG configuration: raw subgraph injection improves scores over the no-graph baseline across the three benchmarks while using 21.2%–31.9% fewer tokens than generative subgraph guidance. These results quantify the performance and token-cost trade-off between direct subgraph injection and generative guidance.

Thanks for the response and additional experiments. I'll maintain my positive score.

Reviewer_LKzTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Procedural Graphs represent procedural knowledge as directed, attributed transitions and generate step-specific advice from a localized graph neighborhood while leaving the solver free to choose its next action. An offline refiner edits graph topology and guidance using execution traces, retains rejected proposals, and commits candidates that do not reduce the cached validation score. The paper reports first or joint-first performance in 21 of 24 main benchmark/model settings and improvements from graph evolution, but extra inference computation, incomplete graph-structure controls, and limited uncertainty analysis constrain the conclusions.

Critical strengths
  • The paper focused on an important proble: preserving procedural knowledge during long agent executions. Agents can repeat mistakes or omit prerequisites when useful procedural knowledge is buried in prose or implicit in past trajectories. The paper addresses how to represent that knowledge explicitly, retrieve the relevant part at each step, and revise it from execution feedback.

  • The proposed methods bring broad gains over the reported memory and procedural baselines.

Critical weaknesses
  • Models and families are not consistent. Section 5.1 calls the experiment four LLM families, but the list contains Claude, Grok, and two Gemini models: four models from three named families. The abstract's broad consistent-gains wording should also be qualified by the three losses in Table 1, including Grok ALFWorld at 39.55 versus ExpeL's 42.54. Please use the precise model/family count and describe the gains as frequent rather than universal.

  • Some related works are missed in discussions or experimental comparisons. AutoManual[1] learns and revises structured environmental rules through interaction, then compiles a manual to guide planning. Its ALFWorld setting makes it a strong comparison for PG's learned procedural knowledge. AFlow[2] searches code-represented workflow graphs with execution feedback. A matched task/tool adaptation would test whether PG's representation and local guidance outperform another way to learn executable procedural structure.

  • Extra reasoning calls are not isolated from graph structure. The PG system adds a guidance-model call before solver decisions, while the main baselines differ in how memory is injected. Table 3 compares full/raw, full/generative, and local/generative guidance but omits local/raw, and there is no same-compute nongraph advice generator or edge-shuffled graph control.

[1] https://arxiv.org/abs/2405.16247 [2] https://arxiv.org/abs/2410.10762

Questions for authors

NA

2 comments

Thank you for the careful review. We address the missing ablation, related methods, and wording below.


1. Additional guidance calls and the missing local/raw condition

We added direct injection of the localized subgraph without a guidance-model call. All five configurations use the same test samples, Gemini 3.5 Flash, solver settings, and, where applicable, underlying PG.

ConfigurationMultiChallengeGDPvalALFWorld
Baseline, no graph80.2754.8072.58
Full graph, raw injection86.6057.1770.34
Full graph, generative guidance87.3556.7554.48
Subgraph, raw injection (new)88.8761.3578.70
Subgraph, generative guidance89.3163.9981.53

Without an auxiliary guidance call, subgraph/raw improves over the no-graph baseline by 8.60, 6.55, and 6.12 points, and over full-graph/raw by 2.27, 4.18, and 8.36 points. Generative guidance adds 0.44, 2.64, and 2.83 points to subgraph/raw.

Thus, gains persist without the extra call, and localization helps under both injection modes. A compute-matched advice generator without graph access remains untested. We will add the new row to Table 3 and distinguish this remaining comparison from the component ablation.

2. AutoManual and AFlow

Both methods are relevant. AutoManual learns structured environmental rules through a code-generating Planner and a rule-updating Builder, then organizes them into a manual. PG explicitly represents procedure-to-procedure transitions, locates the current procedure, and retrieves its graph neighborhood to guide the solver. AutoManual is particularly relevant to ALFWorld; we will add it to Related Work.

AFlow searches executable, code-represented workflows using LLM-generated changes and execution feedback. Its workflow determines the computation used to solve a task. PG provides local procedural advice while the ReAct solver continues to choose its actions. We will expand the related work and discussion accordingly.

3. Model count and performance wording

We will replace “four LLM families” with “four LLMs” and state that PG achieves the best or joint-best result in 21 of 24 model–benchmark settings: 19 wins, two ties, and three losses against the strongest baseline. We will acknowledge exceptions, including Grok–ALFWorld, where PG scores 39.55 versus ExpeL's 42.54.


Summary

The new local/raw experiment completes the full/local and raw/generative ablation and shows that PG's gains do not depend solely on an additional guidance-model call. Across MultiChallenge, GDPval, and ALFWorld, raw subgraph injection improves over the no-graph baseline by 8.60, 6.55, and 6.12 points. Localization improves performance under both injection modes, and generative guidance provides further gains when applied to the localized subgraph. These results directly address the missing ablation and clarify the contributions of localization and guidance.

Dear Reviewer

Thank you again for your suggestions. We have completed the local/raw experiment you requested and would like to outline the changes we will make to the manuscript.

  1. Add the missing ablation to Table 3. Under the original experimental settings, raw subgraph injection improves over the no-graph baseline by 8.60, 6.55, and 6.12 points on MultiChallenge, GDPval, and ALFWorld, respectively, without an auxiliary guidance call. We will add this condition and explain the resulting full/local and raw/generative comparison. Localization improves performance under both injection modes, and generative guidance provides further gains when applied to the localized subgraph.

  2. Correct the model count and performance claims. We will correct the description to four LLMs and replace the broad performance wording with the precise result: best or joint-best performance in 21 of 24 settings, comprising 19 wins, two ties, and three losses against the strongest baseline. The exceptions will be acknowledged explicitly.

  3. Expand the discussion of AutoManual and AFlow. We will add AutoManual to Related Work and expand the existing AFlow discussion. Both are relevant to learning procedural knowledge. We will explain how their manuals and executable workflows differ from PG's local retrieval and step-level guidance.

  4. Add the cost analysis and clarify the evaluation protocol. Raw subgraph injection uses 21.2%–31.9% fewer tokens than generative subgraph guidance across the three benchmarks. We will report both configurations' performance and token costs, including guidance calls. For EnterpriseArena, we will specify selection by full-horizon survival on 20 fixed validation episodes, with ties favoring the newer graph. We will also distinguish evaluation on held-out instances within an environment from cross-environment transfer, and discuss selective or multi-step guidance as future efficiency work.

The new ablation gives a clearer account of what localization and guidance each contribute within PG. We would appreciate your reassessment of the paper in light of this evidence and the revisions outlined above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.