acceptodds
Under review as a conference paper at ICLR 2027

Certified Early Rejection: Prompt Optimizers Can Skip a Third of Their Validation Rows

Abstract

Prompt optimizers such as GEPA, MIPROv2 and SIMBA spend most of their task-model calls scoring candidate prompts on every row of a validation set: in our GEPA runs these full evaluations take 97.9% of the calls, and four in five of the candidates scored end below the incumbent and are never returned. Stopping such an evaluation early is only safe if it is certified: under every possible outcome of the unseen rows, the chance of discarding a candidate that would have won must stay below a stated level. For a candidate evaluated on n rows in a random order, the largest expected saving of any admissible adaptive randomised score-blind rule is the value of an explicit linear programme, which we bracket in rational arithmetic; the same programme with a different error event governs screening a pool of discards. For each fixed recorded candidate stream, fresh level-alpha audits against the retained incumbent preserve the best presented recorded count with probability at least 1-alpha, without a multiplicity penalty. On 162 optimizer runs we executed (54 each of GEPA, SIMBA and MIPROv2; three task models, three benchmarks, 1,187 fully evaluated candidates), certified rejection at a 1% error budget, computed exactly on the runs' per-row evaluation records, skips 35.9%, 24.5% and 12.5% of the audited validation rows. A calibrated finite-population likelihood-ratio rule skips 37.2% of GEPA's rows, 97% of the certified per-candidate ceiling on the candidates below their incumbent. Run live inside the optimizers against paired controls, the certificate skips 28.7%, 11.9% and 10.5% of GEPA's, MIPROv2's and SIMBA's audited rows; on GEPA this is about two points below the exact replay expectation on the paired control streams, and it cuts task-model calls by 25.5%. The same theory explains the opposite regime: on a pre-registered cohort of generated programs, at the evaluated nomination budget and measured cost model, no admissible certificate screening the nominated pool could break even in expectation, even with perfect pool selection, and we compute how large, and how clean, the pool would have had to be.

Primary area:
learning theory
Keywords:
prompt optimization, certified early stopping, sequential testing, sampling without replacement, linear programming, evaluation cost

Reviews

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

This paper provides a way to adapt the idea of sequential hypothesis testing (and early stopping) to prompt optimization, specifically to querying less rows in some validation set when deciding which prompt is best for a given task. The authors develop a linear program to find the max number of rows that can be skipped with controlling the false rejection rate. They also prove that their method can preserve performance when the sequence of candidate prompts is fixed. They then evaluate their method on some prompt optimizers and datasets and find that their rule leads to savings in the number of rows that have to be evaluated before the best prompt is found. The paper also provides some results on screening pools of generated programs.

Critical strengths

The motivation of the paper is a strong one: prompt optimization is used by many and being able to spend less resources doing it would be valuable. The theoretical analysis seems to be rigorous throughout. The empirical evaluation also seems to have been done carefully.

Critical weaknesses

This paper is very difficult to read.

The abstract is difficult to parse and at times uses many adjectives strung together (like "fixed recorded candidate stream" and "admissible adaptive randomised score-blind rule"). The big idea of the paper is simple (and powerful!) but is lost in the many details that are provided in the abstract. For example, instead of "Stopping such an evaluation early is only safe if it is certified: under every possible outcome of the unseen rows, the chance of discarding a candidate that would have won must stay below a stated level", one could say something like "An evaluation can be stopped early so long as we can guarantee that chance of a falsely rejecting a good candidate is less than some threshold, such as 5%." This is much easier to understand and conveys the point of the paper. There is no need to introduce the term "certified" there. Similar comments apply to the rest of the abstract.

The rest of the paper could benefit from clearer writing. Some examples are detailed below.

In the introduction, "scores the survivors on every row" in line 45 and "the prompt it returns is the one with the best count" in line 46 could be made more clear, as one has to infer what the 'survivors' and 'count' refer to. In saying " Stopping such an evaluation after a weak prefix," it is not clear what a "weak prefix" is. Saying "The answer is a ceiling, and it is exact" reads a lot rhetoric common in AI-written text, and it's not clear what a 'ceiling' is or means, and saying 'it is exact' doesn't mean much at this point (there's no explanation for why referring to 'exactness' is relevant). The phrase "enclosed by rational primal and dual bounds with the reported gap" is very dense for an introduction where the objective is just to say that the answer is bounded above and below by some constant.

The list of contributions seems to be what is maybe a list of all the results in the paper rather than what the paper contributes to the literature. None of the headings (eg "one budget per run" or "A negative result that is a theorem about the instance") really represent contributions. Similar comments about clarity of language as above apply here: "score-blind certificate" and "rational dual certificates" are not clear, the explanation of "one budget per run" is especially cryptic, etc.

The "practical takeaways" paragraph also uses phrases that seem to work against the "practical" nature of the paragraph, like "fresh random row order" or "retained incumbent" or "admissible score-blind rule" (could be replaced with simpler phrases).

In the related works section, it is hard to tell how this paper is novel. For example, while comparing to Anthony & Salehzadeh Nobari (2026), the authors write "our retained-incumbent result applies a related single-witness principle to a fixed, not necessarily nested, optimizer stream with history-dependent thresholds, and our LP contribution is an instancewise expected-savings envelope over admissible stopping rules." This is an extremely dense sentence with a lot of hyphenated nouns and many adjectives strung together, so it makes it difficult for a reader to understand what this paper is adding to the existing literature. In the "cheaper prompt optimization" paragraph in lines 120-128, it is still unclear what exactly this paper is contributing to the literature.

Additionally, it seems that there are some relevant references that the paper has not cited:

  • For sequential inference, Fauss and Zubir (2015) at https://arxiv.org/abs/1501.05870 write about an LP approach to sequential hypothesis testing that seems to be very close to the motivation for Theorem 1. Ham, Jasin, and Zhao (2026) at https://arxiv.org/abs/2605.03406 is another one that seems relevant. I think there are some differences but it seems relevant enough that the paper should spend some time situating itself relative to these.
  • For prompt optimization, Pryzant et al (2023) at https://aclanthology.org/2023.emnlp-main.494/ seems to be relevant.

In Section 3, the opening is "A candidate has a fixed 0/1 vector on nn rows with TT ones" with no additional context. Up till now the paper was discussing prompts and it abruptly switches to vectors. Some intuition (eg "the length of the vector is the number of validation rows, and each entry is a 1 if a prompt correctly classifies an example else it is 0") would be necessary! In the next sentence, "A certificate audits the candidate’s rows...", the word "certificate" is undefined. Is it just an early stopping rule? Then three possible thresholds τ\tau are introduced without much explanation. In "screening a pool," it is not clear what or why we are screening. Additionally, it seems like the meaning of "candidate" has changed? In Theorem 1, it seems that the actual LP isn't presented (it only appears in Appendix J), and perhaps the text should at least display the LP and briefly explain the variables. There are also many stopping rules introduced in the "certified rules" paragraph without much motivation or reason.

The title of Section 3.3 is uninformative. The explanation of Thm 3 is also very opaque. Section 3.4 seems to deal with screening programs generated by a language model instead of optimizing prompts, and I am confused as to what relation it has to the rest of the paper. Eg the same framework applies but it has nothing to do with optimizing prompts? There seems to be a negative result presented here but it's not clear why this is important.

Theorem 4 introduces several variables (N,V,M,T,K,h(V),S∗,S0∗N, V, M, T, K, h(V), S^*, S_0^* without much explanation, and this makes for a very confusing read. Some intuition would be helpful.

In Section 4, the benchmarks that are used are all classification tasks with binary correct/incorrect. Prompt optimization is often used for things like code generation, reasoning, and other tasks where the outcomes are not binary, and the empirical results might look different for these. Given that one major contribution of this paper seems to be applying to early stopping in sequential hypothesis testing idea to prompt optimization, it might be useful to see broader applications. The experiments use only 3 seeds, which is not enough to assess variability.

Section 5.2 is very dense and a table might convey the results more simply. It is unclear how Section 5.3 relates to prompt optimization and why it is in the paper.

Overall, the paper suffers from a lack of clarity in writing and a big overhaul in the writing style would be necessary to make it accessible and easier to evaluate. A secondary concern is the lack of situating itself clearly amidst related work.

Questions for authors
  1. The practical takeaway paragraph seems to recommend using the early stopping procedure in a "live" setting where prompts are generated adaptively; the guarantee from the paper is for the situation where all the prompts are fixed in advance. Though I think the paper does provide a way to extend this guarantee for the live/adaptive case, I don't think it is tested in the experiments (which is where the "save a third of your prompts" claim comes from). Could you comment on this, eg would it better supported if it was tested in the experiments?
  2. How do the theoretical results in this paper relate to those in the three papers mentioned above?
  3. Can you clarify the meaning of "candidate" as used in the two paragraphs of Section 3.1? Does the term refer to different things in each?
  4. Theorem 1 says to fix "the true count TT". But how can the optimizer know what TT (the true number of correct answers for a candidate) is until it has evaluated the candidate?
  5. In Section 4, why is the LP rule only used for datasets up to 800 rows? I can imagine that prompt optimization validation sets could have a lot more. Does it not scale well with size? If so, this should be characterized more carefully.
  6. Why was the error-sending variant of Section 3.3 not run in the experiments? It could be useful to compare to the existing results, because it seems like the existing results were run using a method that wasn't proven in the theorems.
  7. The 'live' experiments are much smaller in sample size than the 'replay' experiments; why is this? It seems like it might be of concern given that these are the most relevant ones to the paper's realistic applications?
  8. In Table 2 it seems that the LP rule is never the best-performing method, so could you speak to this?
  9. Line 367 says that "the decision to evaluate and emphasise [the calibrated threshold] was made after the earlier comparisons, on the same streams," so it seems that this rule should also be evaluated on held-out data to see whether it generalized?
  10. Table 3 is mildly concerning in that the methods save validation rows but potentially degrade test accuracy? I realize that the CIs all contain zero, but since all the point estimates are negative it seems that this should be run with more data to reduce the uncertainty.
  11. Is any comparison done with existing early-stopping rules in prompt optimization like CAPO?
Reviewer_rvviOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes certified early rejection for reducing the validation cost of prompt optimization. The main idea is to evaluate candidate prompts on validation examples in a uniformly random order and terminate an evaluation early when a sequential statistical test indicates that the candidate is unlikely to outperform the current incumbent. Experiments include exact replay analyses of 162 optimizer runs and live evaluations with GEPA, MIPROv2, and SIMBA. The results show substantial savings in validation rows, although the improvements in end-to-end optimization time are smaller and the effects on final prompt quality remain uncertain.

Critical strengths

1. Mathematically grounded statistical guarantees.

The paper provides a principled finite-population formulation of early rejection and characterizes the optimal expected savings through a linear program. The main theoretical results are carefully scoped, and the use of rational primal-dual bounds provides stronger numerical evidence than ordinary floating-point optimization alone.

2. Useful empirical evaluation.

The study includes both exact replay analyses and live experiments across three prompt optimizers. The comparison between theoretical savings ceilings and realized evaluation costs provides useful insights into when certified early rejection is practically beneficial.

Critical weaknesses

1. Limited applicability of the theoretical guarantees.

The main theoretical guarantee applies to a fixed candidate stream, whereas practical prompt optimizers generate candidates adaptively based on previous evaluation outcomes. Early rejection can change subsequent proposals and eliminate potentially valuable search branches, even when the local rejection is statistically valid. Moreover, the live experiments do not implement the proposed adaptive error-spending scheme. Consequently, the central certification results do not establish guarantees for the end-to-end optimization process, substantially limiting their practical significance.

2. Insufficient methodological contribution and practical impact.

The approach builds heavily on established finite-population sequential testing and early-stopping principles. Although the exact LP formulation provides a useful characterization, its contribution is specialized to fixed binary evaluation vectors. The practical improvements are also relatively limited: GEPA achieves only an 11% reduction in total optimization time, while all three optimizers show negative point estimates in final test-accuracy changes. The experiments do not establish non-inferiority or a compelling efficiency-quality trade-off. Overall, I find the methodological novelty and demonstrated practical value insufficient for ICLR.

Questions for authors

Q1. What guarantees apply to the actual adaptive optimization process?

The main guarantee assumes a fixed candidate stream, but early rejection in practical prompt optimizers can alter future proposals and eliminate useful search branches. What meaningful end-to-end optimization guarantee can be established beyond controlling local false-rejection probabilities?

Q2. What is the practical benefit after accounting for optimization quality?

The live experiments show modest end-to-end speedups, while all three optimizers exhibit negative point estimates in final test-accuracy changes. Can the authors provide stronger evidence that the saved evaluation cost justifies the potential degradation in optimization quality? In particular, does the benefit persist when adaptive error spending is implemented?

Q3. How robust is certification to nondeterministic task-model evaluations?

The theoretical analysis assumes a fixed binary score vector for every candidate, but the paper reports that repeated scoring at temperature zero changes a median of three out of 300 outcomes. Under what conditions can this randomness be coupled to a fixed outcome vector independently of the audit permutation? Could the authors clarify whether the nominal error guarantee remains valid in the actual serving environment?

Q4. Can the authors establish practical non-inferiority and complete numerical certification?

The live experiments show reduced evaluation costs but do not establish that final prompt quality is preserved. Could the authors provide more extensive paired evaluations or a formal non-inferiority analysis? Additionally, for pools larger than 800 rows, can the implemented stopping boundaries be certified with rigorous numerical error bounds rather than floating-point checks alone?

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

The topic of the paper is a form of “certified early rejection analysis” for sequential evaluation, without replacement. The motivation for this problem, the authors state, comes from skipping validation rows during candidate scoring in prompt optimizers. Though it is conceivable that the problem has broader applications than this specific one. The problem is reminiscent of secretary-type and other optimal stopping problems.

The modeling itself is straightforward - each candidate prompt performance on say n examples is an n-bit vector. Suppose the candidates are in uniform order. The goal is to understand the maximum expected number of skipped rows under some true count with probability at most alpha - this is modeled as a natural LP. In this formulation, the paper shows a few probability results and designs a few “rules”, most of them based on LP formulations.

Experimental evaluations study the fraction of skipped rows for practical prompt optimizers.

Critical strengths
  • Tight benchmarks and theoretical guarantees
  • Natural problem to consider
  • Reasonable practical motivation
Critical weaknesses
  • The paper is very difficult to read. It fails to provide proper context and reads in a needlessly succinct manner rather than a carefully written scientific manuscript. Many terms are introduced without any definition and the reader is expected to fill in the missing details.
  • Seems to assume non-adaptive settings.
Questions for authors
  • How much do the results hold for adaptive prompt optimization settings (which are more practical)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.