- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper introduces GRAFT, a graph-based automatic prompt optimization (APO) framework that makes realized prompt transformations (including multi-parent crossovers) the fundamental unit of search and credit assignment. GRAFT maintains a prompt derivation graph with Monte Carlo statistics on transformation edges and uses edge-conditioned UCB with progressive widening, adaptive operator selection (mutation vs. crossover), and learned partner selection. It also proposes two transformation-level rewards—mean and coverage—that respectively optimize average performance and per-instance frontier coverage, achieving consistent gains over strong baselines across six benchmarks and two task models under matched budgets.
Critical strengths
1.The shift from candidate-centric to transformation-centric search and credit assignment is a clear conceptual advance; multi-parent hyperedges retain full derivation context and enable persistent, reusable statistics for future decisions.
2.The integration of edge-conditioned UCB, progressive widening, adaptive operator selection with plateau-aware crossover triggers, and principled partner selection is well-designed and cohesive.
3.The coverage reward formulates a complementary utility notion (per-instance frontier attainment), which is well-motivated in sparse and heterogeneous evaluation regimes and distinct from candidate-level Pareto selection used in prior wor
Critical weaknesses
1.Ablations are reported on two tasks only; it would be valuable to show broader coverage (especially where crossover contributes vs. not) and to quantify crossover invocation rates and partner diversity by task.
2.Token accounting appears to focus on task-model tokens; it is unclear whether reflection-model tokens are included in Table 2, making cost comparisons potentially incomplete.
3.Sensitivity analyses for key hyperparameters (UCB/PW coefficients, plateau bonus, partner-score weights, coverage tolerance) are omitted; fixed settings across tasks are laudable but mask potential brittleness.
Questions for authors
1.How are QΔ(e, o) (operator advantages) and Q_partner (historical partner utility) initialized, updated, and decayed? Do they back up gated failures and neutral steps, and are there smoothing/prior mechanisms to avoid early overconfidence?
2.The coverage frontier changes over time, making rewards non-stationary. Did you observe instability in UCB estimates or premature convergence? Any empirical mitigation (e.g., reward smoothing, delayed frontier refresh) or theoretical guarantees?
3.Do the token-cost numbers in Table 2 include reflection-model (Gemini) tokens, prompt-construction overhead, and gate minibatches? If not, can you report end-to-end tokens and wall-clock for parity with GEPA?
4 comments
Q1: Updating Operator and Partner Statistics
Thank you for requesting these details. and track immediate score improvements, separately from the downstream edge value .
(i) Initialization and updates. Both estimates and their respective counts are initialized to zero. After evaluating a proposal, each relevant estimate and its own count are updated as
Here, is the selection-split improvement when available, otherwise the gate improvement averaged over gate examples. Mutation compares the child with its parent; crossover compares it with the better of its two parents on the same evaluation set. Every evaluated proposal updates the source's operator statistics; a realized crossover also updates the selected partner's statistics.
(ii) Failed and neutral proposals. Gate failures contribute their normalized gate deltas to these local statistics, while leaving downstream unchanged. Fully evaluated proposals contribute their selection-split deltas regardless of graph admission, so rejected regressions and neutral steps are also recorded. If crossover falls back before forming a child, only its operator count is incremented, with its advantage estimate unchanged; no partner outcome is recorded.
(iii) History and exploration. We use incremental averaging with a update step, without time-based decay or an additional Bayesian prior. The operator UCB bonus (Eq. 5) and partner exploration term (Eq. 6) encourage under-explored choices. Historical partner utility is one component of the partner score, with default weight . Recency is handled separately by the plateau detector's window of five full-evaluation deltas.
Q2: Handling Non-stationary Coverage Rewards
Thank you for this question. GRAFT explicitly handles the changing coverage frontier by refreshing both transformation rewards and historical edge statistics, as described in Section 3.4.
(i) Credit under the current frontier. Each evaluated artifact retains its per-instance score vector. When the frontier advances, GRAFT recomputes , reevaluates coverage rewards from the stored scores, and refreshes the affected running value estimates, as described in Section 3.4. This keeps the credit used by UCB aligned with the current frontier without additional model evaluations.
(ii) Empirical robustness. The sensitivity results in W3 show limited performance variation across the tested UCB/PW settings and coverage tolerances on HotpotQA, IFBench, and PUPA, supporting robust performance under the evaluated budgets.
(iii) Structured reward drift. With fixed score vectors and a growing accepted set, each per-instance frontier value is non-decreasing. Consequently, the coverage reward of a fixed transformation is bounded in and can only stay constant or decrease as the frontier advances. The refresh keeps historical credit aligned with this moving reference. We do not claim a formal UCB regret bound or global convergence guarantee.
Dear Reviewer 13W8,
Thank you again for your constructive suggestions. We extended the crossover ablation to all three multi-module benchmarks, showing gains on each, and reported crossover invocation rates and partner diversity. We also added sensitivity analyses for the key search hyperparameters, with strong performance across the tested settings. Our response further clarifies operator and partner updates, coverage-statistics refresh, and the cost breakdown including reflection-model tokens and total optimization time.
We would greatly appreciate it if you could let us know whether these additions address your concerns.
Best regards, The Authors
Dear Reviewer 13W8,
Thank you once more for your time and valuable comments. We would be grateful to know whether our response has resolved your concerns, or whether there are any points we could clarify further.
Best regards, The Authors
W1: Broader Ablations and Crossover Behavior
Thank you for this question.
(i) Broader ablations. GRAFT's crossover recombines corresponding module instructions from two parent programs. It creates no new module combinations on single-module GPQA, AIME-2025, and LiveBench-Math. We therefore extend the crossover ablation to all three multi-module benchmarks: HotpotQA, IFBench, and PUPA.
The following results use Qwen3-8B with coverage reward and report mean ± SD over three seeds. The ablation disables crossover while keeping the remaining settings and rollout budgets unchanged.
Crossover improves all three multi-module benchmarks, demonstrating its effectiveness. The core transformation-level credit ablation also covers all six Qwen3-8B benchmarks; see our response to W2 of Reviewer MKCu.
(ii) Crossover invocation and partner diversity. Results are averaged over three runs per benchmark. Invocation rate is the fraction of iterations that construct and gate-evaluate a crossover child; partner diversity counts distinct partner edges per run; pair reuse measures repeated selections of the same ordered source-partner pair.
These results show that GRAFT explores multiple partner edges while revisiting selected source-partner pairs. HotpotQA exhibits the highest crossover usage and partner diversity, together with the largest performance gain from crossover (+4.78 points).
We will include the expanded ablations and crossover behavior statistics in the revision.
W2 & Q3: End-to-End Optimization Cost
Thank you for requesting this clarification. Table 2 includes task-model tokens spent on reflection-trace collection, gate minibatches, and full Dval evaluations, including costs incurred by rejected proposals. Reflection-model tokens were excluded from Table 2; we add them and total optimization time below. LLM-based prompt construction counts toward reflection-model tokens; local prompt assembly counts toward wall-clock time.
The table reports the six-benchmark average cost per run for GEPA and GRAFT-coverage. Including reflection-model tokens, GRAFT maintains lower total token usage and shorter optimization time than GEPA on both task models. We will clarify the accounting scope and include this expanded cost breakdown in the revision.
W3: Hyperparameter Robustness
Thank you for this suggestion. Our sensitivity analysis shows that GRAFT maintains strong performance across variations in its key search hyperparameters.
We vary the search hyperparameters listed below on Qwen3-8B across HotpotQA, IFBench, and PUPA. Each sweep changes the indicated parameter or weight configuration while keeping the remaining settings, data splits, and rollout budgets fixed. Partner-weight sweeps vary their relative contributions. Ranges span the default configuration and tested alternatives, using means over three seeds.
Across all tested settings, the largest performance drop from the default is only 1.11 points on HotpotQA, 0.56 on IFBench, and 0.70 on PUPA. This robustness across search-allocation parameters and partner weights supports GRAFT's shared configuration across tasks.