- Rating
- 3(+2)
- Confidence
- 2
- Informativeness
- 2(+1)
- Presentation
- 2(+1)
- Soundness
- 2
Read review
Paper summary
The paper tackles the question of whether a few candidate evaluations per prompt predict Best-of-K success at larger budgets. The paper provides many theoretical and empirical investigations, yet lacks a clear motivation and explanation of the problems at hand. As such, following the arguments is difficult, and the exact impact of each theoretical result is not clearly articulated. I find the current paper's write-up unsuitable for this venue, as a clear communication of what problem is addressed, why it is addressed, and how it is addressed is difficult to understand from the current manuscript.
Critical strengths
[S1] Appears Theoreticaly Rigorous: The main theoretical write-up, whilst complicated to follow, does appear very rigorous. Yet I do not have the expertise of verifying those, as I am not from this particular field, and the presentation and write-up make it hard to follow the arguments (see weaknesses).
Critical weaknesses
Summary: As stated in my confidence, I am not a specialist in this particular research field, yet I believe a paper should still be understandable and motivating for researchers willing to delve into these topics. The overall assessment and my verdict of „clear reject“ are based on the missing motivation, unclear statement of contributions, what practical takeaways exist, how the theory is linked to the experiments, and the overall presentation. As such I find the paper At its current state, it is not acceptable. [Update: After the first response, I have updated my score to "weak reject". See my comment for details] [Update2: After the second response, my core problems have been resolved.]
[W1] Motivation of Contributions: The paper does not clearly indicate which problem is tackled. The abstract seems to present the theoretical investigation, but does not specify the settings in which it is used. A motivation for the problem at hand is lacking, and the reader who is not deeply immersed in the topic quickly becomes lost. The paper simply starts with a question, which is not clearly motivated at all. Also, the question at the beginning of the paper cannot be clearly understood: what does „evaluations with a few candidates per prompt“ have to do with „large budgets“, as the latter does not seem to be motivated. A revision should make it clearer exactly what is being tackled and why the problem is interesting to study.
[W2] Theory and Notation: Within the first page of theory, more than 20 different symbols for notations are introduced alongside various concepts. For example, the term „Chebyshev“ polynomials is introduced without clearly stating exactly why they might be needed or what their motivation is. Theorem 3.1 then directly shows an equality for those polynomials, so at least an explanation of that would be necessary. Also, the results are not put into context but are simply stated, and then the paper moves on. Overall, this makes it difficult to follow the theoretical storyline. A clear revision, alongside a consistent storyline, is necessary to make the understanding clear.
[W3] Experimental Evidence: The experimental section is currently built solely from paragraphs describing the main results of a figure in the appendix. That put aside, it is not clear to what extent the theoretical insights drive empirical gains. Datasets and setup are not discussed in the main sections at all, and are hard to understand from the paper's appendix paragraph. The experiments seem to be run on small-scale models, and I could not find a discussion of exactly why. Overall, the experimental paragraphs do not clearly explain which insights from the theory they support or investigate.
[W4] Experimental Setup: In Appendix D, it is stated that the experimental setup can be understood. There, the ranking models are listed, but details such as exact protocols are not stated. No code is available to check for protocols, further hindering understanding of exactly what has been run. This does not increase the trust in the experimental findings.
[W5] Writeup and Storyline: In my opinion, the paper lacks a clear storyline and requires substantial rewriting. The problem at hand, „Best-of-K prediction, “ is not well motivated, but simply used as a setting for investigation. Core concepts such as „shallow evidence“ are not introduced at the beginning, but assumed to be known throughout. Theoretical results are not put into context, and their implications are not clearly stated.
Questions for authors
[Q1] What specifically are the contributions of this work? What implications do the theoretical results have, and how have they been addressed empirically? Could you give a brief context of what setting the papers are in, which problems exist, how this paper tackles them, and how the theory and experiments relate to this?
[Q2] What is the answer to the stated question, „Can evaluations with few candidates per prompt predict Best-of-K success at larger budgets? Which theoretical and empirical evidence support the answer?
[Q3] What exactly is Figure 1 showing us? Can you give a brief explanation of what belongs to what?
[Q4] Could you explain the following concepts briefly and put them into context of this work: fibres; shallow evaluations; joint information; joint pattern and larger budgets
6 comments
Response to Reviewer pjt8 (2/2): Q3, Q4 and W2-W4
Q3: Figure 1
The figure has one worked example (top left and centre); the other panels are separate results under their own assumptions, not steps of one method.
- Top left. Per prompt, three candidates are sampled, sorted by score and labeled (filled = correct): 8 possible patterns ("words"), each with the same probability under the blue and the red system.
- Centre. Best-of-12 accuracy weights each score percentile by the winner density . The blue system places its correct answers where this weight is large and reaches 85.07%; the red system reaches 14.93%. The 70.14-point gap is the largest possible for Best-of-12 at depth three (Theorem 3.1).
- Right column. Numerical scores do not help in the worst case (Section 3); at depth three a linear target is identifiable only for a quadratic weight (), a slope cap shrinks ambiguity to order , and smooth monotonicity alone still allows a 96-point gap as (Section 4).
- Left column and bottom. One joint statistic restores recovery for monotone cubics (Section 4.2); a shared score distribution makes pooling unbiased (Section 5.1); under approximate sharing, a paid pilot and same-prompt comparisons correct the bias up to an order that finite data support, and designs with the same horizon can differ in precision (Sections 5.2–5.4).
The caption now has this guide.
Q4: concepts
- Shallow evaluation. An evaluation that samples, scores and labels only a few candidates per prompt, of them ( for pairwise accuracy).
- Larger budgets. The value used in deployment (Best-of-).
- Joint pattern (word). For one prompt, the correctness labels of its candidates from lowest to highest score, e.g. (wrong, right, right).
- Joint information. The full distribution over these patterns: all the label information of a shallow evaluation, more than per-rank accuracies.
- Fibre. The set of all systems that produce the same joint information. A shallow evaluation cannot tell them apart, so the spread of Best-of- accuracy across a fibre is what it leaves undetermined; Theorem 3.1 computes the largest spread.
W2: notation and Chebyshev polynomials
Shallow records determine a weighted average of the response across a whole response class only when the weight is a polynomial of degree below (Theorem 4.1). Best-of- uses the weight , which for is not such a polynomial, so the undetermined part is set by how far is from them (Theorem 3.1). The error of the best approximation changes sign where a Chebyshev polynomial does, and that sign pattern gives the worst-case pair: two systems with identical shallow records, whose Best-of- accuracies differ most. The revision says this before Theorem 3.1, opens Section 3 with the worked example and moves the measure-theoretic setup and proof-only symbols to the appendix.
W3 / W4: experiments, models, protocols, code
The experiments test the theory's mechanisms and assumptions, and two of its outputs pay off directly. The label-free test of Section 5.1 rules out sharing in every natural bank we examined, and pooling over-predicts in most of them. The order of Theorem 5.2, computable before sampling, says when to correct: in 2,880 new simulated cells fixed in advance, no correction beat pooling at , and correcting only at cut the mean error by 14%. Table 2 (Section 6) gives each study's claim, data and models, estimator, budget and outcome.
- Data and models. The public Best-of- sets of Frick et al. (2025): four domains, 32 labeled candidates per prompt from GPT-4o mini, Claude 3 Haiku, Llama-3-8B or Gemma-2-9B, scored by 17 reward models (0.6B–8B). MATH-500 banks from Qwen2.5-7B-Instruct and Mistral-7B-Instruct-v0.3, scored by nine 3B–8B reward models.
- Scale. Model scale is not what we study, and the conclusions do not depend on it. On all 164 public-set banks (GPT-4o mini, Claude 3 Haiku included), the label-free test rules out sharing, and rank-based extrapolation from four candidates tracks Best-of-16 within a median .04 (pooling: .09). New sealed prospective runs with Qwen2.5-32B-Instruct and Mistral-Small-24B-Instruct repeat the 7B result under both scorers: pooling over-predicts by .15–.21; plateau and inverse-budget extrapolation stay within .04 (App. F.4, F.6).
- Protocols. Tables 4–5 give decoding settings, scorer input format, labeling rule, estimator, budget, repetitions and seeds.
- Code. The anonymized package linked from the supplementary material holds the certificate scripts and recomputes the numbers we quote from App. D.2.4–D.2.6, D.3.5, D.3.7 and F.
Your questions gave the revision its outline: the introduction now follows Q1 and Q2, and Figure 1 has the reading guide Q3 asked for. We are glad to clarify any passage that remains hard to follow.
Thank you for the detailed response. The revision helped me understand the problem, and I now see it as a refinement of previous work (Dorner et al., 2026). That makes it harder for me to judge its significance. I still have concerns about presentation and experiments.
Summary The revision makes a real effort to address the points I raised, and I recognize the time spent making the paper accessible to readers outside the subfield. As the authors have put effort into addressing my main concerns with the presentation, I have increased my score from 1 to 2. However, I remain unconvinced that the paper is in an acceptable state. I would only be willing to change my assessment if other reviewers found that the theoretical insights outweigh the empirical findings, which I do not currently see.
Presentation [RW1] The revised abstract is dense with technical detail, and I found the answers in the rebuttal much easier to follow. I would suggest aligning the abstract with the core findings, in one or two sentences each:
- Best-of-K is widely used in practice.
- Evaluating at the deployed K is expensive, so systems are often evaluated with only B < K candidates per prompt.
- The question is how far such shallow evaluations can be extrapolated.
- The theory finds …
- The experiments show …
This would convey the paper’s whole message much more clearly.
I still find Figure 1 too confusing and would argue against keeping it in its current form. As the reading guide itself shows, it combines many separate results in a single figure. The storyline is hard to follow and requires constant switching between figure and caption. An overview of the different assumptions is reasonable. But I think it matters more to state clearly which theorems change the result, and in which direction, than to depict the theory with schematic curves.
Empirical evidence [RW2]
The new Table 2 mostly summarizes information already in the appendix, and I do not find it suitable as an experiment section. A reader cannot tell which findings are central and which are details. All rows except the last two are simulated studies that check the theory under its own assumptions. The last two rows use natural scores and come closest to the motivating problem. There, the recovery methods derived from the theory perform worst, while simple extrapolation rules perform best. Reviewer f9TX raised a similar point. I would ask the authors to clarify what practitioners should take from these results. I would rely on reviewer f9TX’s judgment as to whether these findings are of sufficient interest to the community. To me, they suggest that the paper is better framed as purely theoretical work, which I am not in the best position to assess.
Response to Reviewer pjt8 (1/2): Q1, Q2, W1 and W5
Thank you for a frank and constructive review. We agree that the submitted version was written for specialists. Your review names five issues, and the revised PDF (changes in blue) addresses each:
Q1 / W1 / W5: setting, problem, contributions
Setting. Best-of-K is a standard way to use a reward model or verifier at inference time. Sample K answers to a prompt from a language model, score each with the verifier, and return the highest-scoring one. A deployment cares about its accuracy θK, the probability that the returned answer is correct. Depending on the scorer, θK can rise or fall as K grows, so it must be judged at the K actually deployed.
Problem. Measuring θK directly requires generating and scoring K candidates per evaluation prompt: K/B times the generation and scoring of a shallow evaluation with B labeled candidates per prompt. Reward-model benchmarks often report pairwise accuracy (B=2). We ask when extrapolating from such shallow evaluations is justified: what does a cheap evaluation with B candidates per prompt tell us about Best-of-K accuracy at a larger K?
The key point. The obstacle is not sampling noise. As K grows, Best-of-K accuracy depends increasingly on how often the very highest-scored answers are correct, and even exact knowledge of every shallow correctness pattern leaves this undetermined; joint patterns leave the same worst-case gap as per-rank accuracies alone.
Contributions.
Practical takeaway. Before extrapolating a shallow evaluation, check which of these assumptions the system can justify. If none can, evaluate at the target budget directly, or report the range of Best-of-K accuracy that the observed per-rank accuracies allow (App. D.1), whose width Theorem 3.1 bounds.
Q2: the answer to the opening question
In general, no: shallow records alone leave a worst-case gap, which we compute exactly (Theorem 3.1). Under specific added structure, yes. With B=3, two systems with identical records, including every joint pattern, have Best-of-12 accuracy 85.1% and 14.9% (Figure 1, centre). With B=4, the worst-case gap is 60 points at K=16 and 99.7 points at K=64. The empirical evidence: