acceptodds
Under review as a conference paper at ICLR 2027

The Price of Test-Time Selection: An Accuracy–Evaluation Frontier

Abstract

Selecting a better model response can make its accuracy harder to measure: the favored responses may be rare among previously labeled outputs. We characterize the accuracy–evaluation tradeoff when selection returns one of candidates and evaluation reuses labels from the base generator. Candidate availability determines exactly which output distributions are reachable. We measure their evaluation difficulty with a bounded audit profile that matches finite-sample minimax error up to universal constants. Optimizing accuracy subject to this profile gives an exact frontier and a selection rule that discounts correctness in regions with poor label coverage. Continuous-score best-of- incurs worst-case risk , so fixed worst-case precision requires labels proportional to the candidate budget. We turn feasible finite approximations into executable selection rules, including on banks with tied scores. Experiments on four frozen reasoning banks test the evaluation law and the resulting selectors. At matched audit-radius budgets, the policies improve accuracy over uniform–BoN mixtures by percentage points on average and closely match fully optimized order-statistic and quadratic baselines. This connects candidate compute, selected accuracy, and the cost of substantiating that accuracy from reusable labels.

Primary area:
learning theory
Keywords:
test-time selection, best-of-N, off-policy evaluation, minimax estimation, sample complexity, constrained optimization, large language models

Reviews

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

Test-time selection improves LLM accuracy by choosing one response across a set NN randomly generated ones. For example, the Best-of-N method assigns a score to each response and selects the highest one as the final prediction. One way to design this score is to train an auxiliary model on labelled data to predict which responses of the original model were correct or not [1]. The current paper argues that, since this labelled bank is generated using the original distribution of LLM responses, the accuracy measurements estimated from it will differ from the operational model accuracy. This is because, during operation, the model chooses one answer over NN, which induces a distributional shift between prompts seen in labelled data and during operation. The paper investigates this distributional shift theoretically and empirically.

[1] Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., ... & Schulman, J. (2021). Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168.

Critical strengths
  • The paper tackles a very novel problem: how choosing answers (possibly using an auxiliary model called a verifier) induces distributional shifts between operational data and labelled data collected previously to estimate answer accuracy. To the best of my knowledge, no prior work has previously observed or adressed this issue.
  • The theoretical results make very loose assumptions about the distributions of selected answers (e.g. Theorem 3.1). Consequently, they hold for many selection approaches: choosing randomly across NN, using Best-of-N with a continuous score etc.
Critical weaknesses

My main concern is that the paper can be hard to follow for reader who are not familiar with measure theory and certain notations. For instance

  • The decreasing rearrangement of a probability density ratio ww is an critical concept to understand Theorem 3.1. It would be beneficial to quickly define and explained this notion in the appendix. For example, you could clarify that the decreasing rearrangement maps [0,1][0, 1] to (0,∞)(0, \infty) and measures the upper quantile of the ratio w(X)w(X) with X∼PX\sim P. w↓(0.1)=2w^{\downarrow}(0.1)=2 loosely implies that for 1010\\% of the probability mass of PP, the new density QQ is at least twice as large. With this interpretation, equation (5) actually makes a lot of sense.
  • Additionally, the symbol ∧\wedge is introduced in complexity analysis (Θ(1∧N/L)\Theta(1 \wedge N/L)) and other times on functions ((w∧τ)(w\wedge \tau) in equation 10 for example). Is it not clear what this symbol represents and why it can be applied over functions and scalars.
  • My other critiques are questions related to specific parts of the paper, which I put in the Questions For Authors section bellow.
Questions for authors
  • Line 164 states that the ratio ww is fixed independently of the LL i.i.d. labelled draws that make up the bank. I assume this bank is then used to train the verifier and that this verifier is used to select one answer over NN. If this is the case, then doesn't the ratio ww depend on the verifier and thus its training data.? Perhaps I am missing something.

  • Equation 8 is not very clear to me.

    • It is the first introduction to A^\widehat{A}, which was never defined beforehand. Is A^\widehat{A} the LLM reponse accuracy on labelled data or the accuracy estimate returned by the verifier? These notions of estimate accuracy have different sources of error: finite sample, performance of the verifier etc. so more details are required.
    • Over what space is the infimum infA^\text{inf}_{\widehat{A}} taken?
    • I am also unsure of what the expectation Eη\mathbb{E}_{\eta} represents. I think only the term A^\widehat{A} is a random variable in (A^−Aw)2(\widehat{A} - A_w)^2 so is it an expectation over all possible labelled subsets? Why is a η\eta subscript necessary?
Reviewer_mfp5OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

In this paper, the authors investigate the "precision" of accuracy measures for best-of-N type inference time selection methods using a fixed number of graded samples. The authors show that any best-of-N rule needs graded samples proportional to N and propose an optimization procedure along the accuracy and precision frontier. They conduct experiments to demonstrate their theoretical results and show that the trade-off occurs in practice within benchmarks.

Critical strengths
  • I can potentially see the theoretical results providing useful and actionable insights
Critical weaknesses

Clarity I found the paper incredibly difficult to read. I found myself decoding what the authors were trying to say.

Consider the first sentence of the abstract:

Selecting a better model response can make its accuracy harder to measure: the favored responses may be rare among previously labeled outputs

This is not a great way to start the abstract. There needs to be more context. Also, the sentence is very vague. Are we talking about the model accuracy or the accuracy of the selection process? What exactly is the favored response? previously labeled outputs?

This is a recurring theme throughout the paper top to bottom. It is filled with vague (or even vacuous) phrases that is unclear and provide little information to the reader. For example, just in the introduction:

  • "labels that adequately cover the selected responses" (line 35)
  • "fresh selected outputs" (line 36)
  • "labeled base responses" (line 38)
  • "evaluation precision" (line 76)
  • "ranking quality" (line 81)

Figure 1 doesn't make much sense to the reader in Section 1. MSE of evaluation? MSE with respect to what?

There is essentially no discussion of experimental results. The authors present facts from tables and figures, but do not elaborate on how relate to the theory in earlier sections nor its consequences.

Significance Most importantly, the authors do not discuss why auditing in this fashion is useful. In fact, I am having a hard time seeing why all the results are useful. What is the motivation behind comparing different selection regimes or budgets? What is the benefit of considering audit MSE when selecting? Why should we be reusing labels?

If the authors could clearly identify a problem in how people treat accuracy in inference-time selection methods like best-of-N and situate their work in that context, that would help make a case for this paper.

Questions for authors
  • Is π{}\pi{} the selector (line 127)?
  • What is a "correctness function"? Is it η{}\eta{} (line 172)?
  • What is "Fresh randomness" (lines 304-305)?
  • What is a "tie-integrated isotonic correctness estimate" (line 324)?
Reviewer_E6zfOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary
  • Studied problem: How to measure accuracy when sampling many times during test-time selection? The authors look at the accuracy-evaluation trade-off when one of N candidates is selected and evaluation reuses L labels from the base generator. For this, different algorithsm can be used (BoN, verifier-based reranking, …), but their value is usually measured with accuracy compared to inference compute and for using multipel verifiers it can also matter how effectively responses are re-used.
  • Submission approach: The authors define a set of responses (reusable base labels) and call an evaluation with them an “audit”. The authors use a bounded audit profile matching finite-sample min-max error up to a universal constant.
  • Approach realization: The work focuses on theoretical contributions to determine optimal selection at a fixed audit radius (Thm 5.2) for the frontier and laws for what is reachable within N candidates. The authors then test the theory empirically with the Monkey Business, GSM8K, MATH, CodeCOntests, and MiniF2F datasets and the Skywork-o1-Open-PRM-Qwen-2.5-1.5B model and more.
  • Claims/Contributions: A derived frontier that let’s evaluators design selection around reusable label coverage
Critical strengths
  • Principled theoretical work that seemingly provides a frontier to measure accuracy during test-time scaling while re-using generated responses. The findings are verified with pre-existing datasets and progress reward models.
Critical weaknesses

The submission suffers from severe writing clarity issues. It is too densely written and I found it extremely hard to follow. I recommend rejection solely on that basis. Specifically:

  • It reads like a dense list of purely technical details and individual results without connecting elements and motivations (Sections 3-5 in particular), even for a theory paper.
  • The paper uses non-standard terminology for the BoN/verifier setting, making it harder to parse (e.g., using “bank” over more standard “pool” or “candidate set”)
  • The paper argumentation is weakened by the authors not stating their contributions and not discussing the limitations of their work.
  • Minor: Monkey Business dataset is attributed to wrong paper (is from Brown et al. not Schaeffer et al.)
Questions for authors
  • To what extend do your results depend on the function class of the verifier and usage strategy of vierifiers?
  • How does label noise (either form random flip rates or from structural, context-specific flips) affect the modeled frontier and accuracy evaluation?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.