- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper asks whether existing local evaluations can reduce the cost of validating a composition of text updates. The authors first study when local evaluations identify the gain of the full composition and, under a low-degree mean-interaction assumption, characterize the optimal validation complexity when queries have different costs. They then distinguish mean additivity from taskwise additivity, showing that local-query complexity can differ by a factor related to the number of updates even when the two settings have identical mean gains. When the compositional structure cannot be verified, the paper uses cached predictions and residual correction to audit the full composition. On 13 GEPA merge quartets, the reported average saving in new full-composition queries is approximately 15%–16%.
Critical strengths
I see the paper's main contribution as a fairly complete theoretical characterization of local validation cost. A local execution may be cheaper than running the full composition, but reaching an equally reliable decision may require more samples. The authors go beyond this observation by allowing adaptive queries, task reuse, and early stopping, and deriving matching complexity upper and lower bounds. The result is therefore not limited to a particular sampling scheme: it addresses how much local validation can save in the specified query model. Polynomial extrapolation and optimal sampling allocation are established ideas, but applying them to composition validation and showing that more flexible querying strategies cannot beat the corresponding worst-case cost rate is a meaningful theoretical contribution.
I also find the distinction between mean additivity and taskwise additivity valuable. The paper shows that two response models can have the same mean gains while their local-query complexity has factors of k² and k, respectively. Knowing the average contribution of each update is therefore not enough; the task-level paired structure also determines whether local evaluation is efficient. This is a useful insight and helps explain why updates that appear approximately additive may still require many samples to validate.
Critical weaknesses
I have a concern about the scope of the exact optimality claim in Proposition 3. The main text appears to state an optimal cost over a class of fixed unbiased linear estimators, whereas the proof considers a particular form of weighted paired-difference estimator. If one samples separate fixed numbers of tasks at different subset sizes and combines the candidate-outcome means directly, cancellation of the parent term can in some cases give a different variance–cost tradeoff. It is not clear to me whether the current definition excludes such estimators. This does not undermine the main minimax complexity rate, but it matters for the exact optimality claim in Proposition 3 and the resulting boundary between local and full queries. I would like the authors to state the estimator class more precisely.
My main concern with the experiments is that the current evidence does not tell us how much cached auditing would save in a more general validation setting. All 13 complete quartets come from accepted merges, and all have positive full-composition gains. These records are useful for studying how early a beneficial merge can be certified, but they do not cover unsuccessful candidates or a broader range of near-threshold decisions. The 1,000 paired replays are a good check on variation due to query order, but they do not broaden the types of candidates evaluated. Savings also differ considerably across individual quartets: some are admitted much earlier, while others save almost no queries. I would like to understand whether this variation is mainly driven by prediction quality, the size of the true gain, or the audit protocol. The use of six fixed budget checkpoints and a zero threshold may affect the first-admission query count, so a straightforward sensitivity analysis would make the empirical case stronger.
I would also distinguish the contributions of the paper's two parts more clearly. The theory relies on a specified structure and query model, while the experiments use existing prediction-assisted inference ideas to audit a finite pool without assuming that structure. The latter is a reasonable application, but the statistical correction principle itself is not new. I therefore place more weight on the query-complexity and paired-structure results than on cached auditing as an independent methodological innovation. The experiments illustrate the potential value of an existing cache, but they do not yet show that similar efficiency gains hold across general text-update workflows.
Questions for authors
-
How broad is the class of linear estimators covered by Proposition 3? Would the exact cost bound still hold if one used fixed sample allocations across subset sizes and constructed an estimator directly from the candidate-outcome means? If not, could the paper state the intended restriction more clearly?
-
Query savings vary substantially across the quartets. Could the authors analyze what determines whether a composition is admitted early? For example, how much of the variation is explained by the true composition gain versus errors in the cached predictions? Such an analysis would help explain when the approach is effective, beyond the average saving alone.
-
How stable are the reported savings to changes in the audit budget checkpoints or the admission threshold? In particular, when the gain is close to the threshold or a candidate ultimately fails to qualify, can cached predictions still reduce the number of queries meaningfully? It seems that the existing complete recorded pools could support an initial analysis without rerunning the models.
Reviewer e2a8
You are right that Proposition 3 needs correction: its stated fixed-linear estimator class is broader than the paired-difference design proved in Appendix C.5. We have derived matching bounds for unbiased linear estimators with preassigned sample counts and coefficients, one candidate per independent fresh task, uniform sampling within each local shell, and any finite number of free parent-only observations on additional independent fresh tasks. Over this class, the sharp worst-case variance–cost infimum is G/4.
For the upper bound, write bF=t and bj=(1−t)wj, and use
μ=∑hbhCˉh−(∑hbh)Bˉ0.
Each binary variance is at most 1/4, so candidate allocation proportions ∣bh∣/ch yield variance–cost infimum (∣1−t∣Ac+∣t∣cF)2/4. Increasing the independent free parent sample makes its contribution arbitrarily small. For the lower bound, take the admissible distribution with independent fair parent and candidate bits. Unbiasedness fixes the candidate coefficient sums, and Cauchy–Schwarz yields the same factor. Minimizing over t gives G/4.
The result is an infimum over finite designs, allowing integer allocations to approach the optimal proportions. For k=3,r=2,c1=c2=1,cF≥36, the parent coefficient cancels, and 3(Cˉ2−Cˉ1) attains 9=36/4 at finite even sample sizes. The pure-local and pure-full infima are Ac2/4 and cF/4, giving the price boundary cF=Ac2. Appendix C.5 establishes G for its single-draw importance-weighted paired-difference design. We will revise Proposition 3 and the corresponding design-factor axis in Figure 2 to reflect the broader class.
Theorem 2 follows independently from Appendix C.2–C.4. Its upper bound is O(Gϵ−2log(1/δ)). The lower-bound construction bounds the conditional KL of each observation by 16ϵ2price/G, and the stopped-transcript argument gives the matching lower bound for adaptive choices, task reuse, and random stopping. This proof covers strategies that combine candidate means and establishes minimax cost Θ(Gϵ−2log(1/δ)).
Your question about variation in savings can be examined using the recorded pools. H/Q-3 and H/Q-4 have the same full gain, 26/300≈8.67%. Recomputing the first-branch prediction errors gives (E0,E1)=(25,22) and (0,0), respectively. Their mean query savings across the 1,000 replays are 4.74 and 76.50 (Table 6). Equation (21) connects these errors to audit variance. The role of the gain margin is visible in V/Q-1, whose best-branch prediction has zero residual errors and a gain of 4/300≈1.33%. Under the original six checks, all methods reach the census in every replay for that pool. At a finite sample, the exact interval still accounts for possible errors among unqueried outcomes. Thus residual errors determine audit uncertainty, the gain margin determines the precision needed for admission, and the checkpoints determine when admission can occur.
We have completed the requested sensitivity analysis on the same 13 positive-gain pools, retaining the original sampling order and comparing the original six checks with a check every 20 queries. Each schedule allocates the same global error budget of 0.05 across its 13 pools, four methods, and number of checks. All thresholds use the same simultaneous intervals.
Cached columns give the range over the three predictors. The zero-threshold original replay reproduces all 52 first-admission budgets. The denser schedule saves 600–660 queries with cached predictions. At higher thresholds, aggregate savings become smaller as fewer candidates qualify. Every unadmitted pool contributes its full 300-query census to these totals. These are decisions at different margins on the recorded candidates, and the one-sided gate obtains its savings by admitting qualifying candidates early.
The paper's theoretical contribution is the matching query-complexity characterization and the separation between mean and taskwise structure. Section 6 explicitly builds on prediction correction and uses exact finite-pool intervals to handle unverified composition structure. The replay measures the resulting reuse of an existing cache, with the 1,000 permutations assessing sampling-order variation within the recorded pools.