- 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
- The paper addresses a relevant problem: enabling multi-agent systems to adapt during long-horizon task execution.
- Its program-centric graph design provides a clear and unified way to represent computation, dependencies, state, and intermediate artifacts.
- The evaluation is reasonably broad, covering multiple benchmarks, runtime failure tests, ablation studies, and experiments across different backbones.
Critical weaknesses
- 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.
- 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.
- 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.
- 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.
- 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
- 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?
- 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.
- 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
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.
| Controller | Common-5 (%) | Difference from heuristic (pp) | Cost (USD/task) | Tokens/task | Calls/task |
|---|---|---|---|---|---|
| Deterministic heuristic | 76.63 | 0.00 | 0.0107 | 12,680 | 6.07 |
| Uniform feasible | 74.36 | −2.27 | 0.0117 | 13,740 | 6.58 |
| Frozen learned RL | 77.74 | +1.11 | 0.0109 | 12,940 | 6.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.
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 structure | Common-5 (%) | Difference from CHAIN (pp) | Cost (USD/task) | Tokens/task | Calls/task |
|---|---|---|---|---|---|
| CHAIN | 77.74 | 0.00 | 0.0109 | 12,940 | 6.18 |
| TREE | 77.94 | +0.20 | 0.0131 | 15,520 | 7.24 |
| COMPLETE | 77.47 | −0.27 | 0.0114 | 13,780 | 6.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.
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.