acceptodds
Under review as a conference paper at ICLR 2027

Graph Program Synthesis: Adaptive Execution and Evolution for Long-Horizon Multi-Agent Systems

Abstract

Large language model-based multi-agent systems increasingly address long-horizon tasks, yet most deploy workflows that remain fixed after construction. This rigidity amplifies cascading failures, redundant information flow, and inefficient resource use as tasks or environments change. We introduce Graph Program Synthesis (GPS), a program-centric framework that represents task solving as an evolving executable graph. GPS couples two capabilities: Program Graph Representation, which unifies computation units, dependencies, local state, tools, and model bindings, and Reinforcement Learning-based Adaptive Program Evolution, which formulates execution and semantic rewrites as a constrained sequential decision process. Transient executors perform bounded computation and commit validated artifacts, while a deterministic compiler activates candidate graphs only after structural, interface, state-transition, and budget checks. Across nine benchmarks spanning reasoning, code generation, multi-hop question answering, and tool use, GPS improves average task performance by 2.34 percentage points, reduces matched-performance cost by 34.8%, and raises final success under controlled runtime failures by 13.53 percentage points. These findings support a shift from static communication topologies toward adaptive executable programs for long-horizon multi-agent computation.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM-based multi-agent systems, agentic systems, adaptive agentic workflows, graph program synthesis, runtime program evolution, reinforcement learning

Reviews

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

This paper presents Graph Program Synthesis (GPS), a program-centric framework for long-horizon multi-agent systems. It targets the limitation that existing multi-agent systems usually rely on fixed agent organizations and cannot easily adapt their computation process during long-horizon execution. GPS represents the task-solving process as an executable program graph and dynamically evolves the graph through graph rewrite operations, while a compiler validates each updated graph before execution. The authors claim that GPS improves task performance, cost efficiency, and robustness across nine benchmarks covering reasoning, code generation, multi-hop question answering, and tool use.

Critical strengths
  1. The paper addresses a relevant problem: enabling multi-agent systems to adapt during long-horizon task execution.
  2. Its program-centric graph design provides a clear and unified way to represent computation, dependencies, state, and intermediate artifacts.
  3. The evaluation is reasonably broad, covering multiple benchmarks, runtime failure tests, ablation studies, and experiments across different backbones.
Critical weaknesses
  1. The contribution of the RL policy is not sufficiently isolated. The paper compares different graph components in the ablation study, but does not compare the learned RL policy with a deterministic or heuristic policy under the same graph representation, evolution operators, and execution framework.
  2. The effect of the initial graph template is not sufficiently evaluated. Although the paper defines CHAIN, TREE, and COMPLETE initial templates, the main evaluation does not clearly show how sensitive the final performance is to these different starting structures.
  3. The state representation used by the evaluated RL policy is highly simplified. Although the paper defines the RL state as st=(Gt,Xt,Ft,Bt)s_t=(G_t,X_t,F_t,B_t), the evaluated policy uses only a compact set of features, such as failure indicators, cost pressure, and target-node degree. These features may not fully capture the program state needed for effective long-horizon graph evolution.
  4. The description of the controller is inconsistent. The introduction states that the evaluated prototype uses a deterministic controller, while Appendix C states that the RQ1–RQ4 results use a learned RL policy. This makes the actual controller used in the main experiments unclear.
  5. The fault probability in RQ3 may not be directly comparable across methods. The paper applies the same per-node failure probability to all methods, but different methods may execute different numbers of nodes. Therefore, their probabilities of experiencing at least one failure can differ even under the same per-node failure rate.
Questions for authors
  1. How much of the performance gain comes from the learned RL policy? Could the authors compare it with a deterministic or heuristic policy under the same graph and execution framework?
  2. Could the authors clarify which controller is used in the main experiments? The introduction describes the prototype as using a deterministic controller, while Appendix C states that RQ1–RQ4 use a learned RL policy.
  3. How sensitive are the results to the initial graph template and the evolution operators? Could the authors report results using different initial graph structures or different operator sets?
7 comments
AuthorsOpenReview ↗

Response to Reviewer n25f

We sincerely thank the reviewer for the time and care devoted to assessing our work and for the constructive suggestions that have helped us improve it. We appreciate the recognition of the importance of adaptation during long task execution, the unified representation of computation and persistent state, and the breadth of the evaluation. The comments also identified where our evidence and explanations needed to be more precise. We have added controller and initialization comparisons and clarified the evaluated policy, its observations, and the interpretation of the fault protocol.

We respond separately to each of the five weaknesses and three questions below. Section and table references refer to the revised manuscript. We distinguish experimental additions from clarifications and retain the limits of the evidence in our conclusions.

AuthorsOpenReview ↗

Responses to the critical weaknesses 1

W1. Isolating the contribution of the RL policy

Thank you for recommending a comparison that holds the execution framework fixed. This helped us recognize that removing graph components does not isolate the effect of learning the operator-selection policy.

We have added the requested controller comparison in Appendix D.8, Table 21. The frozen learned policy, deterministic heuristic, and uniform feasible controller all retain graph evolution. They share the backbone, evaluation tasks, initial graphs, operators, recovery templates, accessible state, feasibility mask, compiler, and resource ceilings. Only the operator-selection mechanism changes. The heuristic rules were fixed using training or validation data before testing. Section 4.4 now directs readers to this comparison explicitly; it remains a Common-5 controller experiment rather than an additional fault-injection result.

The shared ceilings are now numerical rather than implicit. Appendix D.4, Table 13 assigns all three controllers at most 12 request attempts, 24,000 tokens, USD 0.025, and 2,400 seconds per task, with a 120-second request timeout, two additional API retries per logical request, three recovery executions per task, and four rewrite proposals per task. Table 14 specifies how failed attempts, rejected proposals, and recovery branches are counted and what happens when an allowance is exhausted.

ControllerCommon-5 (%)Difference from heuristic (pp)Cost (USD/task)Tokens/taskCalls/task
Deterministic heuristic76.630.000.010712,6806.07
Uniform feasible74.36−2.270.011713,7406.58
Frozen learned RL77.74+1.110.010912,9406.18

The observed RL advantage over the heuristic is 1.11 percentage points, with a 95% confidence interval of [−0.08, +2.30], estimated using 10,000 paired bootstrap resamples stratified by benchmark. Because this interval includes zero, the experiment does not establish a statistically significant advantage over the heuristic at the 95% confidence level. The heuristic remains competitive. The observed difference from uniform selection is 3.38 points; the confidence interval above applies only to the heuristic comparison.

We also report the small increase in realized cost relative to the heuristic: approximately 1.9%, based on the displayed monetary values. Shared resource ceilings do not mean identical realized consumption. Appendix D.8 now interprets this experiment as a comparison of selection strategies, not as evidence that RL accounts for the full improvement of GPS over other systems. We appreciate the suggestion because it allows a more informative and appropriately qualified account of learning's contribution.

AuthorsOpenReview ↗

Responses to the critical weaknesses 2 and 3

W2. Sensitivity to the initial graph template

We thank the reviewer for drawing attention to initialization. Defining the templates alone did not establish how much the results depend on the starting structure.

We have added a comparison of CHAIN, TREE, and COMPLETE in Appendix D.8, Table 22. All three use the same frozen RL checkpoint without retraining for individual templates, alongside the same evaluation tasks, execution components, and resource limits. The added Full-profile footnote in Table 13 explicitly includes all three initializations under the same numerical ceilings reported in W1.

Initial structureCommon-5 (%)Difference from CHAIN (pp)Cost (USD/task)Tokens/taskCalls/task
CHAIN77.740.000.010912,9406.18
TREE77.94+0.200.013115,5207.24
COMPLETE77.47−0.270.011413,7806.37

The macro-average point estimates span 0.47 percentage points. TREE has the highest score but incurs approximately 20.2% greater monetary cost than CHAIN. CHAIN has the lowest measured cost, token consumption, and call count among these configurations. Table 22 also reports individual benchmark scores, initial and final active-node counts, and accepted rewrites.

Appendix B.1 now clarifies that TREE adds a solver branch, whereas COMPLETE adds dependencies. This is therefore a comparison of initialization schemes, not a pure topology comparison with identical node counts. We limit the conclusion to the three evaluated templates: their observed scores are close, but the results do not establish statistical equivalence, independence from initialization, or that evolution alone causes the limited score variation.

W3. Expressiveness of the policy's state representation

Thank you for identifying the distinction between the full program state and the information supplied to the learned scorer. Our earlier presentation did not make that distinction sufficiently clear, and the concern about representational capacity is well taken.

The evaluated policy uses a compact projection of the runtime state, not an encoding of the entire program. Appendix C.4 now explicitly separates the full state, s_t = (G_t, X_t, F_t, B_t), from the scorer input, φ(s_t) = [1, f_t, u_t, d_t]ᵀ. The latter contains a constant bias, a target execution-failure indicator, normalized cost pressure, and normalized target fan-out. The linear operator scorer has 20 trainable parameters.

The full runtime state remains available for computing the feasible action set and validating candidate graphs. Thus, the action distribution depends on both the compact scorer input and the legality mask. This distinction explains why a compact learned scorer does not restrict the compiler to the same four inputs; it does not, however, establish that the scorer captures every distinction useful for selecting an operator.

We added a dedicated “Scope of the policy representation” paragraph in Appendix C.4. It states that the scorer does not directly encode node instructions, artifact contents, global topology, or complete execution history, and that distinct states with the same features and feasible set receive the same action distribution. The revised description thus makes the observation model explicit: learned operator preferences use the compact projection, while feasibility checks and state management use the full runtime state. This defines the evaluated controller's representational scope without assuming that the projection is a sufficient statistic for the full decision process.

The revision also distinguishes this 20-parameter setting from the RQ5 variants in Appendix D.9, Table 25. Policy-only adaptation still updates only the linear operator matrix. Full adaptation and the full-data target reference additionally train a four-parameter nonlinear feature calibrator, for 24 parameters in total, while backbone weights remain frozen. This is a separate adaptation setting, not evidence that the main RQ1–RQ4 scorer encodes the full graph. The manuscript also states that full adaptation uses more trajectories than policy-only adaptation, so that comparison does not isolate feature calibration alone.

Reviewer_DLUEOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The paper proposes Graph Program Synthesis (GPS), a framework that represents multi-agent task solving as a versioned executable graph. Nodes contain computation instructions, local context, tool permissions, model bindings, and execution records, while edges determine readiness and artifact visibility. Transient executors perform individual computations, and a runtime controller applies graph-rewrite operations in response to failures or verifier feedback. Candidate graphs are activated only after structural, interface, lifecycle, and budget checks.

Critical strengths
  • Runtime adaptation while retaining useful intermediate computation is a meaningful challenge.
  • Shared-backbone comparisons, fault injection, cost analysis, and component ablations address complementary questions.
Critical weaknesses
  • The evaluated controller and its relationship to reinforcement learning are described inconsistently.
  • Several claimed benefits of graph evolution are not isolated from template-based retries and additional feedback.
  • Contradictory feedback descriptions and incomplete experimental specifications limit reproducibility and confidence.
Questions for authors
  1. The Introduction states that the evaluated prototype uses “a deterministic rather than learned controller,” and Figure 1 labels its evaluated scope “Per-Sample Reset · No Policy-Learning Claim.” In contrast, Appendix C.4 describes policy-gradient training across trajectories, checkpoint selection, and evaluation of a frozen learned policy, while RQ5 and the Conclusion claim transfer of a learned organization policy. The authors must identify which implementation produced each experiment and distinguish the general formulation, implemented training procedure, and evaluated controller.
  2. Expand replaces a failed node with one recovery node while preserving its predecessor and successor boundary; Rewire similarly replaces the node and redirects the same boundary, with failure-aware context. This conflicts with Figure 5, where Expand inserts an additional verifier between existing nodes rather than replacing a failed node.
  3. Figure 5 explicitly shows a hidden-test failure triggering a debugger-based repair on HumanEval, and Table 5 describes code validation through execution against benchmark tests. Appendix D.1, however, states that evaluation reports failures rather than repairing candidates with hidden tests. These descriptions imply materially different evaluation protocols.
  4. Removing graph evolution also removes template-based recovery paths, while the persistent-state ablation removes mutable failure context and reusable intermediate state together. Consequently, the observed drops may reflect reduced access to diagnostic information or recovery opportunities, rather than the necessity of the proposed graph representation and migration mechanism.
  5. The retry and rewrite budgets should therefore be reported explicitly, along with results stratified by failure type.
  6. Some Common-5 results cannot be reconciled with Table 1 without additional configuration details.
  7. The Abstract claims a 34.8% matched-performance cost reduction, whereas Section 4.3 explicitly describes representative operating points rather than a complete matched-budget grid.
  8. The 16/32-shot adaptation experiments similarly do not specify how examples are selected, whether they overlap with evaluation, or how the “Target Oracle” is constructed.
11 comments
AuthorsOpenReview ↗

Response to Reviewer DLUE

We sincerely thank the reviewer for taking the time to provide a careful and technically detailed assessment. The comments are valuable for helping us improve the clarity, rigor, and reproducibility of the paper. We especially appreciate the recognition that runtime adaptation while preserving useful intermediate computation is a meaningful challenge, and that our comparisons under a shared backbone, fault injection, cost analysis, and component ablations examine complementary aspects of this problem. The review also helped us identify several places where our presentation did not sufficiently separate the general GPS formulation from the evaluated implementation or expose enough protocol detail. We apologize for the resulting ambiguity and are grateful for the opportunity to clarify and improve the manuscript.

Below, we first respond directly to each critical weakness and then address Questions 1--8 in detail. We distinguish clarification from new evidence and state the corresponding revision. Where the available evidence does not isolate a stronger claim, we explicitly narrow that claim rather than infer beyond the experiment.

Summary of the main clarifications and additions

Controller scope. RQ1 to RQ4 use a learned operator-selection policy trained with REINFORCE. Evaluation freezes the source checkpoint selected on validation data and uses deterministic masked argmax. Each task resets the graph, execution state, and budget, not the learned weights. RQ5 transfers and adapts the source policy to the target backbone. The revised textual descriptions distinguish prior policy training, frozen deployment, and deterministic compiler validation. Figure 1's evaluated-policy panel now explicitly states “Frozen Learned Policy,” “Masked Argmax,” and “No Online Updates.”

Learning contribution. Appendix D.8, Table 21 adds a comparison that retains the same GPS framework while replacing the controller. The learned policy achieves 77.74% on Common-5, versus 76.63% for the deterministic heuristic and 74.36% for uniform feasible selection. The RL versus heuristic difference is 1.11 percentage points with a 95% confidence interval of [−0.08, +2.30]. This interval includes zero, so using a learned policy should not be conflated with establishing its statistical superiority over the heuristic.

Matched recovery. We added Fixed Graph + Matched Recovery, which receives the same recovery information and templates while keeping the graph fixed. It obtains 77.12%, compared with 77.74% for full GPS, with closely matched calls, recoveries, tokens, and cost. Table 20 now specifies the fixed-graph implementation of each operator. The observed 0.62-point difference has its own 95% confidence interval of [−0.32, +1.56], so it does not establish a statistically significant advantage.

Common-5 reconciliation. We added the five benchmark scores underlying every RQ2 macro average. This resolves the inconsistent GPTSwarm and GoA aggregates.

Reproducibility. Beyond unique task counts and baseline configurations, the revision adds numerical execution ceilings and exhaustion rules (Tables 13 and 14), an explicit RQ3 checkpoint–fault-seed matrix (Table 8), measured fault-exposure and failure-type statistics (Tables 16 and 17), and RQ5 allocation, sampling, and optimization settings (Tables 23–25). Q5 and Q8 describe their respective scopes.

Claim scope. We remove the unsupported “matched performance” interpretation, distinguish official hidden test scoring from runtime feedback, and limit the robustness conclusion to the synthetic node fault protocol that was evaluated.

AuthorsOpenReview ↗

Response to the Critical Weaknesses 1 and 2

W1. Inconsistent descriptions of the evaluated controller and its relationship to reinforcement learning

We sincerely thank the reviewer for identifying this central presentation inconsistency. The comment helped us recognize that the manuscript did not clearly distinguish learning the policy before evaluation from deterministic action selection during evaluation, which understandably reduced confidence in the experimental description.

RQ1 to RQ4 use a learned operator-selection policy trained with REINFORCE across training trajectories. Formal evaluation loads a source checkpoint selected on validation data, freezes its parameters, and selects the highest-probability feasible operator by masked argmax. Failure detection determines the target, fixed templates instantiate operator parameters, and the deterministic compiler validates candidate graphs. Task initialization resets runtime state and budget, not the learned policy. RQ5 initializes transfer and adaptation from the source checkpoint.

The Introduction, Section 3.2's training and evaluation description, Section 4.1's policy provenance paragraph, Appendix C.4, and the Figure 1 caption now express this distinction consistently. We have also updated the evaluated-policy panel inside Figure 1 to state “Frozen Learned Policy,” “Masked Argmax,” and “No Online Updates.” The clarification distinguishes no online policy update during evaluation from absence of prior learning.

We also distinguish the identity of the evaluated controller from evidence about the benefit of learning. The new controller comparison in Table 21 finds an observed 1.11-point advantage over the heuristic, but its 95% confidence interval [−0.08, +2.30] includes zero. We therefore do not claim that policy learning is necessary or statistically superior to the evaluated heuristic. Appendix C.4 now records the nine checkpoint–fault-seed combinations for applicable GPS fault experiments in Table 8, while Appendix D.9 distinguishes source-initialized few-shot adaptation from the randomly initialized target-trained reference. Please see Q1 and Q8 for these distinctions.

W2. Claimed graph evolution benefits were not isolated from template recovery and additional feedback

We thank the reviewer for pointing out this causal confound. This observation motivated the most important additional experiment in our response.

We added Fixed Graph + Matched Recovery, which receives the same recovery information and the same recovery template as full GPS but cannot revise the graph. It obtains 77.12%, compared with 77.74% for full GPS. Its realized use is also close to full GPS: 6.24 versus 6.18 calls, 0.94 versus 0.87 recoveries, 13,150 versus 12,940 tokens, and $0.0111 versus $0.0109 per task.

This result changes our interpretation. The original 7.96-point “w/o Graph Evolution” drop reflects removal of the composite evolution/recovery pathway, rather than the isolated effect of topology modification. Under matched recovery information, templates, state access, and shared resource ceilings, full GPS shows an observed advantage of 0.62 percentage points over the fixed graph control. We revise the paper accordingly and no longer state that topology evolution alone supplies the dominant gain.

The revision now gives this comparison its own 95% confidence interval, [−0.32, +1.56], in Appendix D.8. It includes zero and neither establishes superiority nor demonstrates equivalence. Table 20 also specifies the control's internal SPLIT branches and its MERGE operation that retains the peer node, making clear that recovery operations are mapped to a fixed graph rather than assumed to have identical structural effects. These additions qualify the point estimate and expose the implementation being compared; details appear in Q4.

We also clarified the persistent state intervention: it jointly changes the diagnostic context and reusable intermediate information available to recovery computations. Appendix D.8 therefore interprets it as a bundled runtime capability removal. Please see Q4 for the results and interpretation.

AuthorsOpenReview ↗

Response to the Critical Weaknesses 3

W3. Contradictory feedback descriptions and incomplete experimental specifications

We appreciate the reviewer for carefully tracing the feedback and evaluation descriptions across Figure 5, Table 5, Appendix D, and the experimental sections. The comment helped us identify both a misleading schematic and several missing reproducibility details.

We address this weakness in four parts:

  1. Hidden test isolation. Official HumanEval hidden tests were used only by the final isolated scorer. They were not exposed to prompts, feedback, rewrite decisions, or recovery nodes. The new “Runtime checks and recovery inputs” paragraph in Appendix D.1 specifies code extraction and requested output-format compliance as the evaluated code runtime checks, and identifies the information supplied to recovery nodes. Figure 5's revised Case 2 description places runtime rejection before final benchmark scoring. See Q3.
  2. Numerical reconciliation. We added the five individual benchmark scores underlying every RQ2 Common-5 result and corrected the stale GPTSwarm and GoA macro averages. See Q6.
  3. Added protocol details. Tables 10 and 12 report unique evaluation task counts and baseline settings. Tables 13 and 14 now add numerical execution ceilings, counting scopes, and exhaustion behavior; Table 20 specifies recovery on the fixed graph, including SPLIT and MERGE.
  4. Repetitions, uncertainty, and adaptation data. Table 8 records the RQ3 checkpoint–fault-seed matrix. Appendix D.8 now reports separate confidence intervals for controller selection and matched recovery. Tables 16 and 17 provide numerical fault-exposure and failure-type results at their stated probabilities and run counts. Tables 23–25 specify the RQ5 sample allocation, nested sampling, evaluation separation, and training settings. See Q5 and Q8.

These additions connect the reported results to their controller, runtime feedback, scoring, and resource-accounting procedures.

We also corrected the robustness summary in the Abstract, Introduction, and contribution statement to 13.59 percentage points: at 30% per-node faults, Figure 4 reports 82.43% for Full GPS and 68.84% for MAS². This is a separate consistency correction from the Common-5 reconciliation in Q6.

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

This paper introduces GPS, a system that models multi-agent workflows as versioned, executable graphs. Key features include persistent artifacts, transient node execution, and compiler-checked runtime rewrites. The authors claim improvements across nine benchmarks, enhanced fault recovery, and effective few-shot transfer of organization policy.

Critical strengths

S1: The program representation is well motivated. Explicit dependencies and committed artifacts give runtime rewrites a clear execution contract, and the compiler separates proposed changes from active graph versions.

S2: Table 1 reports consistent gains under a shared backbone, with the largest improvement on BrowseComp+. The fault study also includes a no-evolution variant that retains retries and state reuse, making it more informative than a comparison only against static systems.

Critical weaknesses

W1: Unclear RL Contribution. The introduction describes a deterministic rather than learned controller, while Appendix C.4 states that RQ1–RQ4 use a learned policy checkpoint. Moreover, removing graph evolution does not isolate the contribution of policy learning from the recovery templates. Without a comparison against a non-learned controller using the same operators and budgets, the benefit of RL remains unclear.

W2: Ambiguity in Graph Evolution Implementation. The implementation of graph evolution is not entirely clear. Figure 5 illustrates adding new computation steps, while Appendix C defines EXPAND as replacing a failed node with a recovery node. It is unclear how these operations correspond in practice, making it difficult to assess the flexibility of the proposed framework.

Questions for authors

Q1: Could you clarify how the graph modifications illustrated in Figure 5 relate to the rewrite operators defined in Appendix C?

Q2: What specific tests are accessible to the code verifier and recovery nodes? Figure 5 shows repair occurring after a hidden-test failure, but the code-evaluation protocol states that hidden tests are not used for repair. This seems contradictory.

6 comments
AuthorsOpenReview ↗

Response to Reviewer TZoa

We sincerely thank the reviewer for the time and care devoted to evaluating GPS and for the concrete suggestions that have helped us improve the paper. We appreciate the recognition that explicit dependencies and committed artifacts provide a meaningful execution contract, and that separating candidate rewrites from active graph versions is valuable. We are also grateful for the positive assessment of the comparisons under a shared backbone and the fault study that retains retries and state reuse in its control.

The review identifies important gaps in how we explained the controller and illustrated recovery. We address each weakness and question separately below. The revision adds a controlled comparison of operator selection policies, clarifies training versus deployment, and specifies the information available during code execution. We have also corrected the evaluation scope annotation in Figure 1 and updated the case headings, descriptions, and operator labels in Figure 5 to emphasize replacement and permitted runtime feedback.

AuthorsOpenReview ↗

Response to the Critical Weaknesses 1

W1. Contribution of reinforcement learning and identity of the evaluated controller

Thank you for asking us to distinguish the contribution of learning from that of the recovery framework. In response, we added a direct controller comparison and clarified the relationship between policy training and deterministic deployment.

The main experiments use a learned operator selection policy with deterministic deployment. As clarified in the Introduction, Section 3.2, Section 4.1, and Appendix C.4, REINFORCE updates policy parameters across training trajectories. Evaluation loads the selected checkpoint, freezes its parameters, and chooses the feasible operator with the highest probability. A new evaluation task resets its graph, execution state, and budget, not the learned policy weights. Target detection and operator parameter templates remain fixed, and the deterministic compiler is a separate validation mechanism. Figure 1 now explicitly identifies the frozen learned policy, masked argmax, and absence of online updates.

We added the requested comparison without removing graph evolution. Appendix D.8 and Table 21 compare the learned policy with a deterministic heuristic and uniform selection over feasible operators. All three use the same backbone, evaluation tasks, initial graphs, operators, recovery templates, accessible state, compiler, and resource ceilings. The heuristic rules were fixed using training or validation data before evaluation. Realized resource consumption is reported rather than assumed to be identical.

The shared limits are now explicit. Appendix D.4, Table 13 assigns all three controllers the Full profile: at most 12 model-request attempts, 24,000 input-plus-output tokens, USD 0.025, and 2,400 seconds per task, with a 120-second request timeout. It permits two additional API retries per logical request, three recovery executions per task, and four rewrite proposals per task. Table 14 defines counting and exhaustion, including rejected rewrite proposals and separately counted recovery branches. These are ceilings, not the average resource measurements below.

ControllerCommon-5 (%)Cost (USD/task)Tokens/taskCalls/task
Deterministic heuristic76.630.010712,6806.07
Uniform feasible selection74.360.011713,7406.58
Frozen learned RL77.740.010912,9406.18

The learned policy's observed advantages are 1.11 percentage points over the heuristic and 3.38 points over uniform selection. The paired bootstrap interval for the difference from the heuristic is [−0.08, 2.30] at 95% confidence, using 10,000 resamples stratified by benchmark. Because this interval includes zero, the result does not establish a statistically significant advantage over the heuristic. The higher point estimate also accompanies slightly greater resource consumption than the heuristic: USD 0.0002, 260 tokens, and 0.11 calls per task. Compared with uniform selection, the learned policy has a higher observed score and lower measured resource use; we do not make a separate significance claim for that comparison.

This experiment measures the incremental effect of controller choice within GPS under shared resource ceilings. We appreciate the reviewer's suggestion, which led to a direct comparison with explicit uncertainty estimates and resource measurements.

We also report a separate comparison of graph revision with matched recovery on a fixed graph. Appendix D.8, Table 20 describes how the same frozen source policy and recovery templates operate inside existing nodes. Full GPS scores 77.74% versus 77.12% for this control. The newly added “Uncertainty of the matched-recovery comparison” paragraph reports a 0.62-point difference with a 95% confidence interval of [−0.32, +1.56]. This interval also includes zero and is distinct from the RL–heuristic interval above. Together, the comparisons distinguish controller selection from graph revision without treating either point estimate as statistically conclusive.

AuthorsOpenReview ↗

Response to the Critical Weaknesses 2

W2. Implementation and flexibility of graph evolution

Thank you for identifying the mismatch between the visual examples and the operator definitions. We understand why the insertion diagrams suggested a different implementation from the one described in Appendix C.

In the evaluated implementation, EXPAND and REWIRE replace a target; they do not insert an extra active node between retained computations. Appendix C.2, Table 6, and Eq. (21) specify the transformation. The original target is retired, a fresh recovery node inherits its incoming and outgoing dependency boundary, and compatible committed artifacts at unaffected nodes remain available. The candidate becomes active only after compiler validation. A single such replacement leaves the number of active nodes unchanged.

The recovery instruction is instantiated from a fixed template using the target instruction and output contract. Model binding and tool permissions are inherited. REWIRE explicitly supplies typed failure metadata to the recovery context; its structural transformation is the same as EXPAND's. These operators therefore provide controlled replacement, not unrestricted insertion of arbitrary new computation. Changes in active graph size are represented by other operators, notably SPLIT and MERGE, subject to their preconditions and compilation checks.

The revised appendix now also specifies the fixed-graph control, rather than leaving its recovery mechanism implicit. Table 20 maps EXPAND and REWIRE to recomputation inside the original node. SPLIT executes internal solver and checker branches, each counted as a separate call and recovery execution; MERGE combines compatible instructions and permitted context in the target invocation while retaining the peer and its original execution obligations. No nodes or dependency edges are removed, and no rewritten graph version is activated. These mappings describe the control, not a redefinition of the Full GPS operators in Appendix C.2.

We have revised the case headings, descriptions, and operator labels in Figure 5 to emphasize target replacement. Section 4.7 now explicitly introduces the examples as schematic illustrations and explains retirement of the original target, preservation of its external dependencies, and reuse of compatible committed artifacts. Appendix C.2 provides the precise transformation used in the evaluated implementation. This explanation separates the supported replacement operation from unrestricted insertion of new computation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.