- 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 rows with 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 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 ( 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
- 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?
- How do the theoretical results in this paper relate to those in the three papers mentioned above?
- 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?
- Theorem 1 says to fix "the true count ". But how can the optimizer know what (the true number of correct answers for a candidate) is until it has evaluated the candidate?
- 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.
- 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.
- 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?
- In Table 2 it seems that the LP rule is never the best-performing method, so could you speak to this?
- 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?
- 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.
- Is any comparison done with existing early-stopping rules in prompt optimization like CAPO?