acceptodds
Under review as a conference paper at ICLR 2027

When Is Local Validation Cheaper for a Text-Update Composition?

Abstract

Can evaluations of individual text updates validate their composition more cheaply than direct execution? We study both whether local results determine the full gain and how combining their estimates affects sampling cost, for paired binary outcomes and a fixed composition of updates. Under a degree- mean-interaction model, we derive explicit weights that recover the full gain from average gains over local subsets of each size (shell means). With local prices and full-query price , the minimax expected validation cost is . The lower bound covers adaptive mixtures, task reuse and random stopping; a cost-aware local sampler or direct execution attains the rate. We distinguish mean additivity (gains add in expectation) from taskwise additivity (gains add on each task): their singleton-query factors are and , even with identical mean responses. Without a verified structural identity, we correct cached predictions using sampled full outcomes to obtain an exact finite-pool gain interval. On 13 complete public GEPA quartets, additive proxies overstate every full gain, while a fixed retrospective audit reduces new full-composition queries from 3,400 to 2,780 (18.24%) with either branch or clipped predictions. Across 1,000 paired replays, mean query savings remain 15.52–16.06%. These results identify how execution prices, paired structure and cached predictions govern validation reuse.

Primary area:
learning theory
Keywords:
LLM agents, prompt optimization, composition, evaluation reuse, statistical validation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_e2a8OpenReview ↗
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
  1. 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?

  2. 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.

  3. 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.

1 comment
AuthorsOpenReview ↗

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/4G/4.

For the upper bound, write bF=tb_F=t and bj=(1−t)wjb_j=(1-t)w_j, and use

μ^=∑hbhCˉh−(∑hbh)Bˉ0.\widehat\mu=\sum_h b_h\bar C_h-\left(\sum_h b_h\right)\bar B_0.

Each binary variance is at most 1/41/4, so candidate allocation proportions ∣bh∣/ch|b_h|/\sqrt{c_h} yield variance–cost infimum (∣1−t∣Ac+∣t∣cF)2/4(|1-t|A_c+|t|\sqrt{c_F})^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 tt gives G/4G/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≥36k=3,r=2,c_1=c_2=1,c_F\geq36, the parent coefficient cancels, and 3(Cˉ2−Cˉ1)3(\bar C_2-\bar C_1) attains 9=36/49=36/4 at finite even sample sizes. The pure-local and pure-full infima are Ac2/4A_c^2/4 and cF/4c_F/4, giving the price boundary cF=Ac2c_F=A_c^2. Appendix C.5 establishes GG 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/δ))O(G\epsilon^{-2}\log(1/\delta)). The lower-bound construction bounds the conditional KL of each observation by 16ϵ2price⁡/G16\epsilon^2\operatorname{price}/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/δ))\Theta(G\epsilon^{-2}\log(1/\delta)).

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%26/300\approx8.67\%. Recomputing the first-branch prediction errors gives (E0,E1)=(25,22)(E_0,E_1)=(25,22) and (0,0)(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%4/300\approx1.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.

ThresholdOriginal checks, direct / cachedEvery 20 queries, direct / cachedUnadmitted pools
03,400 / 2,7803,160 / 2,500–2,5600
0.053,760 / 3,5203,660 / 3,400–3,4603
0.103,760 / 3,6803,760 / 3,66011
0.203,900 / 3,760–3,8403,880 / 3,780–3,80012

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.

Reviewer_XncBOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies whether the performance of composed text updates can be validated more efficiently using evaluations of individual updates. The authors derive theoretical bounds on validation costs under different interaction assumptions and propose a cache-assisted residual auditing approach, evaluated on GEPA prompt-merge records.

Critical strengths
  1. The paper provides a reasonably rigorous theoretical analysis, including minimax cost bounds.
  2. The proposed residual auditing approach demonstrates some query savings in the reported experiments.
Critical weaknesses
  1. Limited significance of the research problem. My main concern is that the paper addresses a rather narrow validation scenario whose broader importance is not sufficiently motivated. While reducing the evaluation cost of composed text updates is potentially useful, it is unclear how frequently this specific setting arises in practical agent systems or whether the resulting savings would have a meaningful impact on real-world workflows.
  2. Limited methodological novelty. Much of the analysis builds on established statistical tools, including optimal experimental design and prediction-powered inference. The paper does not clearly demonstrate a sufficiently substantial conceptual advance beyond adapting these techniques to text-update composition.
Questions for authors

See weakness.

2 comments
AuthorsOpenReview ↗

Reviewer XncB

Your question about the conceptual advance brings out a distinction central to the paper: identical average behavior can conceal fundamentally different validation costs. Section 5 constructs two response models with the same mean surface g(S)=sϵ∣S∣/kg(S)=s\epsilon|S|/k, the same candidate-success marginals, and the same full-difference distribution. Their singleton-query costs have factors k2k^2 and kk, respectively, with matching upper and lower bounds. This establishes how task-level candidate–parent dependence determines the value of local evidence, even after the average response of every subset has been specified.

The price-aware result answers the corresponding design question. Under degree-rr mean interactions, Theorem 2 gives minimax cost

Θ ⁣(min⁡{Ac2,cF}ϵ−2log⁡(1/δ)),Ac=∑j∣wj∣cj.\Theta\!\left(\min\{A_c^2,c_F\}\epsilon^{-2}\log(1/\delta)\right),\qquad A_c=\sum_j|w_j|\sqrt{c_j}.

Classical allocation provides an attaining local sampler. The matching lower bound requires a jointly admissible binary response family whose conditional information per unit cost remains bounded after arbitrary query histories. It covers adaptive mixtures of local and full queries, task reuse, and random stopping. Together these results characterize the best worst-case cost available through the query interface. For mean-additive updates, the local factor is k2c1k^2c_1, quantifying the statistical amplification that local execution savings must overcome.

As for how this validation problem arises in practice, the motivating workflow is present in the released GEPA artifact, which records 49 merge attempts across nine merge-enabled runs. Separate prompt branches have been evaluated, and the optimizer must evaluate their combination before accepting it. Our formulation asks exactly what the existing local evidence contributes to that decision. The 13 complete binary quartets provide aligned parent, branch, and merge outcomes for examining it. Every additive proxy overstates the observed full gain, by 1–19.67 percentage points, demonstrating why a validation step matters even when the individual evaluations are available.

Section 6 already cites Angelopoulos et al. (2023) and Fisch et al. (2024) for the prediction-correction principle. The residual audit provides a way to reuse branch results when the interaction identity is unverified. On the recorded pools, correction reduces new full-composition executions from 3,400 to 2,780, and the three cached predictors reduce aggregate queries in every one of the 1,000 paired-order replays. These results measure the benefit of an existing cache in a concrete composition workflow. The broader characterization of when local validation is economical follows from the identification, price-dependent minimax, and paired-structure results.

In practical prompt optimization, merged prompts can often be evaluated at a cost comparable to individual branches. The paper's own theory suggests that direct evaluation is preferable in this scenario. I think paper's method introduces a lot of setting s but the gain is not very good.

Reviewer_EqW8OpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the verification of update compositions based on the evaluations of individual text updates. The authors derive the minimax cost bounds and a residual-audit fallback when structural assumptions are unverified.

Critical strengths
  1. The paper clearly formulates the problem of validating a composition of text updates using local evaluation results.
  2. The theoretical analysis is rigorous, and the main theorem provides insight into when local validation is more cost-effective than directly evaluating the full composition.
Critical weaknesses
  1. Since “when is validation cheaper?” is the central question, a practical cost study including cache acquisition and amortization would strengthen the paper. It also remains unclear whether the query savings translate into practical cost reductions in terms of runtime, token usage, or monetary cost.
  2. The evaluated compositions have positive gains, which do not show how efficiently the method handles compositions with zero, negative, or near-zero gains.
Questions for authors

Please refer to weaknesses.

1 comment
AuthorsOpenReview ↗

Reviewer EqW8

To translate fewer queries into deployment savings, we need to account for how the cache is acquired and reused. The fixed replay saves 620 full-composition executions across 13 merges, reducing new full queries from 3,400 to 2,780. To include cache acquisition and amortization, let CcacheC_{\rm cache} be the incremental cost of acquiring the reusable cache, qD,dq_{D,d} and qA,dq_{A,d} the direct and cache-assisted query counts for decision dd, cF,dc_{F,d} its full-query price, and Caudit,dC_{{\rm audit},d} the added prediction and interval-computation cost. The net saving over RR decisions is

SR=∑d=1R[(qD,d−qA,d)cF,d−Caudit,d]−Ccache.S_R=\sum_{d=1}^{R}\left[(q_{D,d}-q_{A,d})c_{F,d}-C_{{\rm audit},d}\right]-C_{\rm cache}.

Acquisition is amortized when SR>0S_R>0. With a common full-query price, the observed 13-merge comparison gives S13=620cF−∑dCaudit,d−CcacheS_{13}=620c_F-\sum_d C_{{\rm audit},d}-C_{\rm cache}. If search has already produced the branch evaluations, their incremental acquisition cost for validation is zero. If the cache is acquired specifically for later validation, its acquisition cost enters this account once, and accumulated savings determine whether reuse recovers it. Task-dependent prices can be incorporated by summing the execution costs for each method's queried tasks.

The replay supplies the query-count component of this account; it does not measure token, monetary, or wall-clock savings. Token or monetary costs enter through the execution price cF,dc_{F,d}, while elapsed time additionally depends on batching and scheduling. The observed saving of 620 full executions gives the quantity to price and amortize.

We have also evaluated admission thresholds 0.05, 0.10, and 0.20 on the same 13 positive-gain pools. Under the original six checks, the direct-query totals are 3,760, 3,760, and 3,900. The first-branch audit uses 3,520, 3,680, and 3,840, saving 240, 80, and 60 queries. The corresponding numbers of candidates whose gains fail to exceed the threshold are 3, 11, and 12. Every such case incurs the full 300-query census, which is included in the totals. A denser schedule checking every 20 queries also gives positive aggregate savings at each threshold, with 80–260 fewer queries across the three predictors at these higher thresholds.

This analysis measures sensitivity to smaller and nonpositive gain-to-threshold margins within the recorded positive-gain pools. Under the one-sided admission rule, unadmitted candidates run to a census. The reported savings therefore come from earlier certification of qualifying candidates, with the full cost of unsuccessful admission decisions included.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.