ROC-n-reroll: How verifier imperfection affects test-time scaling
Authors: Florian E. Dorner
Yatong Chen
André F Cruz
Fanny Yang
Venue: ICLR 2026 Poster (2026)
Keywords: test-time scaling
inference-time scaling
best of n
theory
data quality
Primary area: learning theory

Abstract: Test-time scaling aims to improve language model performance by leveraging additional compute during inference. 
Many works have empirically studied techniques such as Best-of-N (BoN) and Rejection Sampling (RS) that make use of a verifier to enable test-time scaling. However, to date there is little theoretical understanding of how verifier *imperfection* affects performance — a gap we address in this work. Specifically, we prove that the instance-level accuracy of these methods is precisely characterized by the geometry of the verifier’s ROC curve. Our theory has two important takeaways, confirmed by experiments with Qwen and LLama models on GSM8K and MATH500. First, RS outperforms BoN for fixed compute, while both methods converge to the same accuracy in the infinite-compute limit. Second, it is generally impossible to predict the high-compute performance of either method based on observations in the low-compute regime.

Published as a conference paper at ICLR 2026
ROC-N-REROLAY How VERIFIER IMPERFECTION AFFECTS TEST-TIME SCALING
Florian E. 1.2.. Yatong Chen 33,4, André F. Cruz 3.4 and Fanny Yang'
'ETH Zürich, Max Planck ETH Center for Learning Systems, Max Planck Institute for Intelligent Systems, Tübingen, "Tübingen AI Center
ABSTRACT
Test-time scaling aims to improve language model performance by leveraging ad- ditional compute during inference. Many works have empirically studied tech- niques such as Best-of-N (BoN) and Rejection Sampling (RS) that make use of a verifier to enable test-time scaling. However, to date there is little theoretical un- derstanding of how verifier imperfection affects performance in this work. Specifically, we prove that the instance-leve accuracy of these meth- ods precisely characterized by the geometry of the verifier's 's ROC curve. Our theory has two important takeaways, confirmed by experiments with Qwen and LLama models on GSM8K and MATH500, First, for any query with a concave verifier ROC curve, RS outperforms BoN for fixed compute, while both methods converge to the same accuracy in the infinite-comp comptee limit. Second, it is gener- ally impossible to predict the high-compute performance of either method based on observations in the low-compute regime.
gap we address
INTRODUCTION
Just as further scaling up large language model (LLM) pre-training started to show diminishing returns, OpenAl released ol, vastly improving upon the sate-of-theeart many challenging bench- marks OPeenAl 2024). Instead of spending more compute on pre-training, ol was the first flagship
LLM to prominently improve performance by spending additional compute test-time. Since then,
interest in rest-time scaling has exploded (Muennighoff et al. 2025 Guo et al. 2025 Kimi et al.
2025
Qu al. 2025 Aggarwal and Welleck 2025 Zaremba et al. 2025 Kavukcuoglu 2025).
There are two broad approaches to test-time scaling: resampling and "reasoning". Both approaches typically
verifier scoring mechanism that evaluates the quality or correctness of an L.LM's outputs - but at different stages of the pipeline. Resampling methods employ a verifier at test- time filter or rank candidate responses after they are generated (Cobbe al. 202T) In contrast, reasoning methods employ a verifier to modify how the LLM generates outputs, usually increasing output quality at the cost of increased response length. Most prominently, the verifier can be used as reward for post-training with reinforcement learning (RL) (Guo et al. 2025).
In practice, both test-time scaling approaches have primarily been successful in domains where a reliable oracle verifier can be implemented - e.g., coding using unit tests and math using ground- truth numerical solutions. As such, previous theoretical analysis has focused on the scaling behavior of pass @N, the probability that at least one of the N candidate responses is correct (Brown et al. 2024 Schaefter et al. 2025). In most domains, however, access to perfectly accurate verifier is not realistic. errors may slip through: insecure code can pass static tests (Zhou al., 2024), and flawed reasoning can arrive at the correct numerical answer (Petrov et al.) 2025). More broadly, there has been an increasing interest using another language model verifier (Huang al. [025a Song et al. 2025), an approach that can be applied to any domain, but has been shown to have far from perfect accuracy (Bavaresco et al. 2025 Dorner al. 2025).
Despite growing interest in verifier-based test-time scaling, the relationship between scaling behav- ior and the properties of imperfect verifiers remains poorly understood. This work addresses this
'Equal contribution.
Code: https:: //gi wwwb.choossoo...ooooooooo.oo coom/socia al foundat ons/ cona/rocn--e- reee/rooo---rr111

---

Published as a conference paper at ICLR 2026
Verifier ROC
Rejection Sampling
Best-of-N
1.00
0.8
0.8
True Positive Rate
0.75
Accuracy
0.6
0.6
-+-
0.50
32B
0.4
148
0.25
4B
0.2
0.2
Predicted
0.00
16
False Positive Rate
Number of Generations
Number Generations
Figure I: Empirical performance (markers) of RS (middle) and BoN (right) on GSM8K test question 58, overlaid with theoretical predictions (lines). Different verifiers scale similarly at first, but then diverge. RS matches BoN accuracy, using less average compute. Generator: Qwen3-1.72
gap. We analyze two simple resampling methods for test-time scaling: Rejection Sampling (RS), which resamples answers until the verifier score exceeds predetermined threshold, and Best-of-N (BoN), which samples N answers and returns the highest-scoring one. We provide a series of the- oretical and empirical results that connect the performance and compute costs of both methods to classical concept in machine learning: the Receiver Operating Characteristic (ROC) curve (Peterson al., 1954). For fixed query, the verifier's ROC curve encodes all possible trade-offs between two types of errors: false negatives rejecting correct answers, and false positives - accepting incorrect answers. Specifically, our contributions are as follows:
We prove that for given query, the accuracy of both BoN and RS only depends the gen- erator and verifier via the generator's 's initial accuracy and the verifier's 's ROC curve (Propo- sitions and 4 Accuracy is agnostic implementation details beyond that.
For concave ROC curves, we prove that RS outperforms BoN for fixed compute (Proposi- tion but converges to the same accuracy as compute increases (Proposition ann and Theo- rem
Further, extrapolation based on early scaling is impossible in both cases as seen in Figure [ performance at high numbers of test-time samples can vary widely between verifiers, even if accuracy is identical at small numbers of samples (Propositions and 6).
Using Qwen3 and L.aa models as verifiers, we validate the accuracy of our per-instance performance predictions subset of GSM8K questions (see Figure [ Figure 3 We also confirm our high-level takeaways on the full GSM8K and MATH500 datasets (Figure 4ah.
The rest of this paper structured follows: We begin by discussing related work (Section 2 We then present our formal setup (Section 3). followed by our theoretical results for RS (Section and BoN (Section(5) Lastly, we conclude by presenting our experimental results (Section
2 RELATED WORK
Test-time scaling methods can be broadly divided into two categories: resampling methods that aggregate multiple LLM outputs and "reasoning" methods that modify an LLM to elicit longer re- sponses with "human-like" reasoning steps (see Appendix A.I for additional discussion and /Zhag al.) (2025) for survey). Despite the recent popularity of reasoning methods, resampling is still prominently applied in industry releases: While OpenAl reports majority voting results (Ope-) nAl 2024), and Anthropic's Claude 4 uses BoN in its "high compute" mode (Anthropic) 2025),
DeepMind's AlphaCode (Li et al. (022) uses test cases to filter generated code, and Alphab-
volve (Novikov et al. 2025) uses numeric feedback to iterate on and refine proposed solutions.
Rejection Sampling RS is routinely used to create synthetic data for model training ZZ Zelikman et al. 2024 Yehudai et al.) 2024 Uesato et al. 2022 Zhu et al. 2023 Xiong et al. 2025 Yuan
et al. 2023 Dorner et al., 2023). J mostly in settings with a single canonical verifier. However, as
method for test-time scaling, RS has not received much attention in the literature to date. This
is likely due to two practical disadvantages: Unlike for BoN, the sampling budget can only be controlled indirectly via choosing decision threshold, and parallelization is difficult. Still, Ziegler
2

---

Published as a conference paper at ICLR 2026
et al. 2022 use RS for safety filtering, while et al. (2024) study the interplay between majority voting and LLM- answer filtering. Most similar to our work, [ong et al. (2025) empirically investigate the performance of RS when the generator and the verifier are based on the same LLM, while Stroebl et al. (2024) find that scaling up variant of rejection sampling for a fixed binary unit- test based verifier has limited benefits. Our work precisely characterizes the compute-scalin of RS performance, based on the ROC curve, and show that RS (partially) compensates for its practical disadvantages via improved performance compared to BoN at fixed compute level.
Best-of-N For BoN, theoretical work has analyzed the case of perfect verifiers, in which case BoN performance equivalent to pass@N: Brrwn al. (2024) estimate pass@ N scaling based on per instance closed-form formula for expected accuracy and find aggregate performance to ap- proximately follow a power law. Meanwhile, [Schaeffer et al. (2025) point out that the closed-form solution does not imply power law scaling per instance. The authors reconcile this by hypothesizing that the observed aggregate power-law scaling is caused by a heavy tail the distribution of instance difficulties. That said, BoN only achieve pass @N performance if the verifier is perfect, which not realistic in most practical applications. While Chen et al. (2025) relax the perfect-verifer as- sumption better- -hanne pairwise comparisons, their results require errors to be independent across repetitions, which allows for arbitrarily high verifier accuracy via boosting.
BoN with imperfect proxy scores f(X) has attracted substantial empirical interest (Cobbe et al., 2021 Gao et al., [023] Coste et al.] 2024). However, most theoretical work on BoN has focused on how the number of samples N affects the answer quality as measured by the verifier score f (X) [Beirami et al. 2025 Gui et al. 2024). Instead, our work focuses on how the ground-truth per- formance scales for unreliable verifiers. Most related our work, recent paper by Huang et al. (2025b) provides bounds on BoN performance, based on the mean squared eтror (MSE) between score f(X) and the ground truth reward y(X), Rather than providing bounds, our work uses the ROC curve to fully characterize BoN performance in the context of binary ground truth rewards.
3 FORMAL SETUP
Throughout the rest of this work, we consider a fixed query and a generative model Phose (the generator) that produces responses X X. Let P Pa denote the distribution over X' induced by sampling from Joase (conditioned on the query q). We assume an unknown ground-truth labeling function y : X {0, 1}. where y(X) = 1 iff X is a correct answer the query q. In addition, we have access to verifier score f X' + [0. 1] that is (supposedly) correlated with y. For example, this might be another LLM's assessment of the correctness of the answer X the query q. Based on f. we can then define a binary classifier hT X + {0, 1) by thresholding ht (X) I[f(X) T]. where the indicator function.
We now define key performance quantities of the generative model Obase and a binary classifier h:
π == ACC( = Pa
Stne [y(X) X) = 1] the accuracy of the generative model Ghuse
T(Druse It) P 9hose [h(X]] 1ly( (l) 1]: the true positive rate (TPR) of the classifier
F(geases h) P grea [xx 1ly(X) 0]: the false positive rate (FPR) of the classifier h
Further, for a fixed verifier f. we define H((f)) as the set of all classifiers h", where 7 E [0, 1]. We then refer to the classifier that maximizes true positive rate for a given false positive rate F as
hy
arg max
T(gbase: h).
hEH(f): H)
With this, we can formally describe the ROC curve a verifier f::
Definition (ROC Curve) Given a fixed generator Goase and verifier f. the ROC
curve of f is the function T J0, 1] - [0. defined by: T(F) T(gbaze, hF) max (T(gbare h) H(f)), F(gbose: h) < F).
In words, the ROC curve describes the true positive rate of all optimal classifiers hy and thus the Pareto optimal tradeoffs between F(ghase h) and T T(grue h). Note that ROC curves ()F are (non- strictly) increasing in F. For additional context on ROC curves, Appendix A.2
3

---

Published as a conference paper at ICLR 2026
3.1 Two METHODS FOR TEST-TIME-SCALING
In the following sections, we fix generator and verifier f. and analyze the scaling of rejection sampling and Best-of-N. Both methods induce new generative distribution over outputs X.
Rejection Sampling (RS): We repeatedly draw outputs X ~ Pa Shoae and apply a classifier hp E H(f) to each sample X to determine acceptance. The process halts and returns the first sample X such that (X)) 1. RS thus defines a new generative process grr corresponding to the conditional
distribution of X given (X) = 1, i.e.,
p - =] Pou x (X) 11.
Decreasing the false positive rate F or increasing the threshold T causes RS outputs X to have higher verifier scores ((X at the cost of longer running times due to fewer outputs X being accepted.
Best-of-N (BoN): We draw N independent samples XI.-.. XN ~ Pawee from the generator and return the one with the highest score under f. i.e., arg max f(x;) with ties broken randomly. BoN induces a new generator g'y with outputs distributed as
Pa X = 2
P arg max (XtexeM)
f(X') = xx],
where p&N denotes the joint distribution of N independently sampled X; ~ Pmaee The running Show time of BoN can straightforwardly be adapted by increasing N, improving the average score f(X). For summary of the notation introduced in this section and used throughout the paper, see Table
4 REJECTION SAMPLING
In the following section, we characterize how the ROC curve of a fixed verifier f affects the test- time scaling of the RS in terms of two key quantities: The compute cost of RS, and the accuracy ACC(g")) of the RS distribution P. ggt defined in Equation (2) for hE E H((f). We begin by deriving how the accuracy and compute cost of the generative process g²r vary with the false positive rate F.
Compute cost Let (FF) denote the number of samples X drawn from the base distribution P until hy in Equation (1) accepts, i.e., (x) 1. Then the average compute cost C(F) of RS measured in terms of the number of samples and verification [1 corresponds to (F)). Since N (F) follows geometric distribution with success probability P Panee [XF(X) 1], we have
Sheee
1
C(F) [[)( Poese (xp 1] T(F) . x + 11 (1-r) T
(4)
where = ACC((guse) is the accuracy of the generator Ibuse Note that C(F) 1 for perfect classifier hF = y. while C((F) - oo when the probability of hp accepting an output x tends to zero.
Accuracy R$ is equivalent to the precision positive predictive value Pa [y(X) (X) 1] of the classifier fap. As observed by Song et al. (2025), modifying the decision threshold 7 and thus F and he induces different accuracies for the output distribution ACC(g"r). Combining Equation and Definition as well as the Bayes rule, we can write
T(F) T
(F) ACC(g"²)= T(F) F. (1 (1= 7))
(5)
In particular, Ay(F) = =(9) when (x) is independent of y X), while for क > 0 and a perfect
classifier ht = y. we get (F = 1. Because T(F) increases F, C(F) defined in Equation (4) decreases strictly. Thus, the function C(F) has an inverse F(C). With this, change of variables in Equation (5) yields an expression for accuracy directly in terms of the expected compute C, i.c.,
T(F(C)) x Ay(C) = (F(C)) = T(F(C)) क + F(C) (1-x) = C. T(F(C))
(6)
Note, that due to Wald's equation, the expected number of tokens generated by an L.M (and an M- verifier) during RS is proportional to the expected number of samples. For details, consider Appendix B.
4

---

Published as a conference paper at ICLR 2026
Throughout most of this section, we will drop the subseripts and write A(C) and A(F) respectively. In the next proposition, we derive the slope of the compute- compute-performant performance curve as a function of the slope of the ROC curve T(F) and show that concave ROC curves imply monotonous scaling for RS.
Proposition Let f be a verifier and T [0 + [0,1] be the ROC curve of f. If the derivative (F) exists at F, the derivative of the accuracy- curve ((F) is given by
d.A(C)
T) (T(F) (F) 1 (F) -T
dC
C=C(M)
For (strictly) concave ROC curves,
dA(C) is (stricily) positive whenever (F) exists.
dC
C=C(F)
Proposition iis proven in Appendix
Beyond monotonous scaling for concave ROC curves,
implies that when the ROC curve T(F) is piecewise linear, so is the accuracy A(C).
4.1 LOW-COMPUTE REGIME
We now analyze the performance of RS in the low-compute regime, which corresponds to using classifier with high FPR (e.g., F z 1) that accepts almost all outputs without much filtering. At the extreme of F = at the top-right corner of the ROC curve, the generative process gev induced by the classifier h samples exactly once per accepted output, minimizing compute. As we slightly tighten the classifier by decreasing F from I, compute increases and performance improves at the rate of
dA(CC) dC C=1 π
(π 1)(1 11(1))(((())) T())) (1)
particular, for the minimal possible slope T'(1) 0, accuracy initially grows with compute at
rate of π. On the other extreme, when (1( = there is no improvement with increased compute.
Verifier
Scaing
Verifeer ROC curve
Scaing
1.0
1.0
RS
0.5
0.8
0.5
Accunty
Accurcyy
g
0.4
0.4
Verifer Verifier Chance
0.3
0.4
Veriler Verifier Chance
0.3
0.2
0.2
0.0
0.00
0.25
0.50
0.75
1,00
10
20
30
0.00
0.25
0.50
0.75
1,00
10
20
30
FPR
Number Generations
FPR
Number of Generations
(a) Different small-, large-scale performance
(b) Early scaling reverses large scale Figure 2: Performance of RS (line) and BoN (scatter) with different verifiers (synthetic data).
Figure 2a iillustrates how the top-right corner determines early scaling: We plot two ROC curves that behave differently in the top-right corner, but the same in the bottom-left corner. As predicted by Equation 7 RS scales more quickly when the ROC curve is more "flat" near the top-right corner. Interestingly, the similarity of the ROC curves near the origin appears to coincide with diminishing performance differences in the high-compute limit. the next section, we prove this observation.
4.2 HIGH-COMPUTE REGIME
We now characterize the performance of RS the high-compute regime, which corresponds to using highly selective classifiers on the bottom-left corner of the ROC curve that accept few outputs-ia. -.c., 0. For intuition, consider an ROC that is linear around the origin, i.c. T(F) = oF for F < 1. In that case, Proposition [ implies that the derivative of the performance A(C') with respect to expected compute C is zero for small F meaning that performance eventually plateaus compute increases. More generally, next proposition shows that the large-scale performance of RS is determined by the derivative the ROC curve at the origin whenever T(0)- =
5

---

Published as a conference paper at ICLR 2026
Proposition 2. Let f be verifier and : [0.1] [0, be the ROC curve of f. T(0) 0 and T(F) is continuously differentiable in a neighborhood of F = O. we have
(0)
lim A(C) C-
(8)
(0) (1-
Otherwise (0) O, C(O) finite and A(O) A(C(O)) limc-cco) A(C) =
The proof of Proposition followws directly from Equation 6 using Taylor's theorem and L' L'Hospital (see Appendix (.3). Proposition 2 is in line with the large-scale behavior shown in Figure 2a As both ROC curves have the same slope at the origin, their large-scale performance is the same. The opposite is observed in Figure Here, the ROC curves have different slopes near the origin, but are similar in the top-right corner. As predicted by Proposition 2 RS performs substantially worse in the high-compute limit when the ROC curves have smaller slope near the origin.
4.3 CAN RS PERFORMANCE BE EXTRAPOLATED?
So far we established in Equation 7 and Proposition 2 that the scaling in the low- and high-compute setting is determined by the local geometry of the ROC curve in the top-right vs the bottom-left corner respectively. As the geometry in neither of the corners puts strong constraints on the geometry in the other corner, without priori knowledge of the ROC curve's behavior near the origin, we cannot predict large-scale performance based on small-scale performance. Our next proposition formalizes this intuition.
Proposition 3. Fix a compute budget B supp C(F) = Cmaz with (B) > and suppose the RS accuracy (C') is known for all F with C(F) S B for fixed, unknown verifier f. Then:
1. There exist verifiers fo. f1 consistent with the accuracies observed up to compute B, such that lima f O and limc-+Cmao (c) respectively.
2. Assuming I has a concave ROC curve and the left one-sided derivative of A(C) strictly positive at = B, there are consistent verifiers FA(BY, fi with concave ROC curves such that limc-+Cmax A (C) = (C)=
A(B) and limc--CCas A (C) respectively.
It implies that observing RS performance at small scales, we can usually not distinguish between the two cases i) no further performance gains from scaling and ii) eventual perfect performance. This
We prove Proposition] iin Appendix C.5
be observed empirically in Figure T where both verifiers lead to the same performance at small compute, but performance diverges at high-compute. Figure 2b shows even more extreme case: While RS initially seales substantially faster for the blue ROC curve, performance quickly stagnates. Correspondingly, RS with the orange ROC curve reaches substantially higher performance levels, despite the slower initial scaling.
BEST-OF-N
While the scaling of RS has a clear and simple dependence on the ROC curve, the amount of com- pute used by RS is random, and its expectation only implicitly depends the chosen threshold т. Compared to that, BoN gives users the ability to explicitly specify a deterministic amount of compute N. In this section, switch focus to the scaling behavior of Best-of-N (BoN).
As in the previous section, treat the verifier f fixed and write ON rather than o to denote the output distribution of BoN as defined in (3). The accuracy of BoN is equal to the probability that the highest-scoring sample X among N draws is correct answer, i.e. ACC(gN) P 2a [x((**) +) = 1]. To characterize BoN performance, we make following regularity assumption about the score f(x):
Assumption 1. The distribution of scores s(X) is either discrete absolutely continuous with respect to the Lebesgue measure (i.e. has a density).
This allows us to show that the ROC curve of the verifier f again determines how the accuracy of BoN scales with compute. While RS is governed by the local geometry of the ROC curve, will

---

Published as a conference paper at ICLR 2026
that the scaling behavior of BoN depends the global properties. We begin by defining the probability that BoN produces a correct answer, conditional on p of the samples being correct,
(k. = Shone
arg max f(X,) = (Xihselttp)
Σ ME|M
v(X,) =
then follows that the accuracy of BoN can expressed by
ACC(gN) - B(,,N (N - p. p)]:
where BiT, N) denotes the binomial distribution with success probability and N trials.
We note that (1, 1) equals the area under the ROC curve (AUROC). Inspired by Scherlis (2021), we find that H (k, p) can be written as weighted integral over the ROC curve for any k and p. This allows us cast the BoN accuracy ACC(gN) as an integral over the ROC curve:
Proposition 4. Let f be score with ROC curve T(F) for which Assumption 7 holds. Define (FF)= = (1 (1 F) + (11 - ((-T)(F)), Then for N 2 2, the accuracy of BoN is given by
ACC(gN) = (1- - L. O(D)N-1dD
(10)
(F)) concave, the BoN accuracy ACC(gN) is non non-decreasing in N.
We prove Proposition 4 in Appendix C.6
Note that in the case of perfect verifier y = we have π F). such that Proposition 4 yields the well-known formula 1- (1 - T for P @N. In addition, the proposition implies that when the ground truth y(x) is binary, overoptimization (Gao et al.
T(F) = 1 and thus e = =1
2023) -where actual performance worsens as more samples used- only be problem for BoN when the verifier's ROC curve is non-concave.
5.1 LOW-COMPUTE REGIME
For N = 2, noting that H(0, = H(2 = 0, the expectation in Equation 9 is fully deter- mined by the area under the ROC curve (1, 1) and the original task performance x. In this case, we obtain simple formula for the performance gain going from Best-of-l to Best-of-2 sampling:
ACC(g2) - ACC(g)) = x² 2m (L, -
For random-equivalent verifier, H),, = 0.5 such that the performance gain equals zero, while for the perfect verifier f the gain equals r т). Notably, this maximal possible "slope" of π - т) is substantially below the same slope of . for RS at C' = F = T = 1, suggesting that RS might outperform BoN when controlling for compute. Our next proposition confirms this:
Proposition Let be verifier with concave ROC curve T(F) for which Assumption 7 holds. Ser FN to be the solution to C(Fx) = N and fix any N E for which Fx exists. Then, RS with the verifier hFx outperforms BoN, i.e. ACC(ghrx) 2 ACC(gN).
Interestingly, the advantage of RS vanishes in the limit: In the next subsection, we analyze the large-scale limit of BoN, and show that it matches the perfor- mance of RS we established in Proposition 2
We prove Proposition 5 in Appendix C.9
5.2 HIGH-COMPUTE REGIME
While the integral formula for the performance of BoN from Proposition 4is harder to analyze than the more local formula for the performance of RS from Equation (6). our next theorem shows that both methods still perform the same in the large scale limit.
Theorem 1. In the setting of Proposition f assume that T(F) is continuously differentiable in neighborhood of 0. Then if T(0) > 0, we have lim som ACC(gn) = 1. Otherwise if = O.
T())
lim ACC(gN) T(() - N

---

Published as a conference paper at ICLR 2026
Theorem 1 is proven in Appendix
C.7 Intuitively, for large N, ACC(gN) is mostly determined by the largest values of (FF) = (1
π [ F) + m(1 T())), which correspond to small and
T(F). Thus, the limiting behavior of BoN is determined by behavior of T()) near the origin.
Comparing with Proposition 2 the high-compute limit of BoN performance ACC(gN) ) is equal to the high-compute limit for RS. Combined with Proposition 8 this suggests that Theorem | might point to a more fundamental limit to the performance gains achievable with imperfect verifiers. As RL algorithms are often trained to mimic the resampling distribution (Xiong et al., 2025), such limit might also extend to RL. In Appendix B.3] we further explore this connection, casting the RS distribution as the zero-perr pero-penalty limit of constantra RL.
5.3 CAN BON PERFORMANCE EXTRAPOLATED?
As in Section we investigate whether it is possible to extrapolate BoN performance from observations at low compute without knowing the ROC curve. We again provide a negative result: Despite its smoother scaling, the limiting performance of BoN remains impossible to predict from small-scale observations, especially when the ROC curve cannot be guaranteed to be concave.
Proposition 6. Consider a verifier f satisfying Assumption 1 such that lim ACC(g =
1. Then for any n E N and >> O, there are verifiers So, Ji satisfying Assumption such that |ACC(g)) - ACC(gN)1 ffrr all N S n and i E {0,13. but
lim ACC(g O while lim ACC(g))=11 N+000
N-
If has a concave ROC curve, the verifier Ji can be chosen have concave ROC curve as well.
We prove Proposition 6 in Appendix C.12
Analogously to Proposition 3 it shows that without further assumptions, any early scaling in BoN is compatible with both and perfect performance ACC(gN) in the large N - oc: limit. Even assuming concavity, it remains impossible to derive meaningful upper bounds on large scale performance by extrapolating from smaller scales.
EXPERIMENTS
In this section, we evaluate series of open- weight instruction-tuncls LLMs from the Owen3 (Yang ct al. 2023) and LLama (Grattafiori et al. 2024) families as both generators and verifiers on ques- tions from GSMSK (Cobbe al. 2222) and MATH500 (Hendrycks et al., 2021). To generate an answer 2, we use few-shot prompting with random train examples and temperature t 1. For verification, we prompt models score answer correctness from 0 to 10, after employing chain of thought (Tian et al., 2023 Cruz et al. (024) and normalize the scores to lie in [0, 1J. To increase the resolution the score, we repeat this process five times per answer and use the average of the responses as the final score f(X). Further implementation details are described in Appendix
Verifier ROC
Verifier: Llama-3.2-3B
Verifier: Llama-4-17B-1
1.00
0.22
X
True Positive Rate
0.75
0.20
Accuracy
0.50
0.18
RS
BoN
0.25
0.16
Empirical
Liana 17B--66
Predicted
Liama-3.2-38
0.00
0.14
0.0
0.5
1.0
10
20
30
40
50
False Positive Rate
Number Generations
Number Generations
Figure 3: Empirical performance (x markers) of RS (purple) and BoN (olive) on GSMSK test ques- tion 2, overlaid with theoretical predictions (lines). Dotted: Llamaa3. 2-3B verifier (single 6E as verifier (single COT). Controlling for the number of gener-
COT). Solid: L. 1ama-4-111 ated samples, RS consistently outperforms BoN for both verifiers. Generator: Llama-3 3-2-3B.
In Sections and 5 we rigorously characterized how the per-instance generative accuracy of BoN and RS scales with test-time compute. Correspondingly, now validate the theoretical predictions
8

---

Published as a conference paper at ICLR 2026
for BoN and RS individual queries. For small set of queries, sample and score 1000 sponses using different 3wen and LLama models as both generators and verifiers. These samples used to both i) simulate BoN and RS by resampling and ii) estimate different verifiers' ROC curves. We then use these ROC estimates to predict the accuracies for both RS and BoN using Equation (5) and Equation (TO) respectively. Note, that RS often terminates after small number of samples, even at the maximal threshold of T = 1. To simulate RS for larger numbers of samples, we thus randomly interpolate between the classifier ht and the (always rejecting) classifier h²2 Due to Proposition RS with the resulting classifier uses more samples than h! but is no more accurate.
Across the board, our theory predicts both methods' accuracies with high precision (see results on additional questions in Appendix D Exemplarily. Figure [I] shows the results for Owen3 1 7B generator on GSM8K question i 58, which illustrates the issues discussed in Proposition par- ticularly well. As predicted by Proposition I since the ROC curve plateaus near F = 1 (top-right portion), early RS scaling follows the same linear trend for all verifiers. Similarly BoN performance almost identical up until N = 3, but diverges higher compute. This is in line with Proposition predicting that different ROC slopes at = lead to different performance levels at high compule. Comparing the middle and right panel,
also that RS outperforms BoN for fixed compute.
This can be observed more directly in Figure B which shows results for a Llama-3 3. 3-2-33 2-3B gener- ator GSM8K question = 2 with verifiers using single chain of thought. We plot RS and BoN performance for the same verifier in the same panel and observe a stark difference between both Notably, RS consistently outperforms BoN, de- spite some non-concavity in the ROC curve of Llama- -3 3-2-3. 3B. While the relative prediction error becomes noticeable in the middle panel, the absolute errors remain below one percentage point.
methods' scaling, as predicted by Proposition
MATH500
GSMBK
0.9
Acciracy
0.8
0.8
0.7
Q3 32B (RS, variable T)
Q3 328 (BoN)
0.6
QS 48 (RS, varistle 1)
(BoN)
2
10
10 Average Number of Generations
12
Average Number of Generations
(a) Rejection Sampling heuristic difficulty- based thresholding.
MATH500
GSM6K
0.9
0.9
Accuracy
0.8
0.7
Q3 32B (Capped RS)
Q3 328 (BoN)
0.6
0.7
(Cappad
(B.NN)
2
10
12
10
12
14
Average Number Generations
Average Number Generations
(b) Capped Rejection Sampling. Figure 4: Aggregate accuracy of BoN RS on MATH500 (left) and GSM8K (right). Dotted lines: Bo25 performance. Controlled for compute RS consistently outperforms BoN, Verifiers: Qwen 32B (blue), and 4B (orange). Generator: 3wen3-1. 7B, Error bars: Exact 90% Cls.
Aggregate results Our theoretical results on the predictability of scaling and the dominance of RS over BoN are restricted to fixed queries. However, one might intuitively expect them to also apply on aggregate over a larger dataset D of queries. To test this, we run RS and BoN on each query q in the GSMSK and MATH500 test sets for given thresholds r(g) and numbers of BoN samples N. As mentioned before, choosing good threshold 7 (g)) for given query g can be challenging. However, a separate problem arises when using RS over multiple queries: Using the same threshold threshold for all queries cause large variance in the false positive rates F and compute costs C(F) across queries. In practice, some queries receive high scores f fxx for most answers x and thus require large thresholds s reliably identify correct answers. Meanwhile as shown in Figure E.

---

Published as a conference paper at ICLR 2026
scores f(x) z 1 exceedingly rare for a small set of hard queries q, such that running RS with high constant threshold for the whole dataset may run indefinitely. To address this, we consider two approaches: lifficulty-basee heuristic to adjust the threshold per query, and a "hybrid" approach that starts with RS for a constant r, but reverts to BoN after a fixed number of samples.
First, we implemented simple two-tier heuristic based query difficulty: For t E [0. 1], the threshold T()) = t for "easy" queries where the generator produces correct answers x at least 1% of the time, and the threshold 7(g) for the remaining "hard" queries. Figure 4a plots this method and BoN's average accuracy against their respective average number of generated samples, with error bars indicating 90% confidence intervals for accuracy. The figure replicates several of our key observations from the single-query setting: On both datasets, controlling for compute, RS outperforms BoN, but the gap between the methods vanishes at larger compute levels. Additionally on GSM8K, performance for the Qwen3-4B and Qwen3-32B verifiers is the same at low compute, but a noticeable gap between the verifiers emerges larger compute. This indicates that we cannot rely on extrapolation to predict performance for high levels of test-time compute.
However, difficulty-based thresholds T(q) are challenging to implement in practice, when query dif- ficulty is unknown. A promising alternative are "hybrid" methods that use a threshold r that works well for most queries, while limiting the compute wasted on queries for which that threshold is rarely reached. A simple approach is "Capped Rejection Sampling": We fix the same threshold for every query and sample answers x until either f(xx) 2 т, or we have sampled 25 times. In the latter case, return the answer x: with the highest score f(x) among our samples. Figure 4b shows this works well in practice: In all cases, CRS matches Bo25 performance, but requires substantially fewer sam- ples. Furthermore, Capped RS performs very similar to the variable threshold heuristic proposed in the previous paragraph, while arguably being simpler to implement. Additional experiments on GPQA (STEM reasoning) and HumanEval+ (Code generation) can be found in Appendix
DISCUSSION
Our results precisely quantify the limitations of resampling with imperfect verifiers. Both theoretical and empirical results indicate limited dependence between verifier performance at low and high test- time compute, cautioning against trend extrapolation as a means to predict performance. Our work opens up several new lines of inquiry: On the theoretical side, future work could explore how distributional assumptions - on the per-item accuracies π of the generator Joase and the per-item ROC curves - affect our conclusions regarding extrapolability and the dominance of RS over BoN. On the methodological side, further refinement and analysis of "hybrid" methods a promising avenue. In addition, the dependency of early and later test-time-scaling on different regions of the ROC curve motivates future work on training customized verifiers for different test-time budgets.
Symhol
Description
query or procupt given to the generator generator model (e.g.. LLM)
Po
The distribution induced by generttr response sampled from g. i.e., P's Score function estimating the correctness of
f: 2
00
AT (3))
Classifier accepts f(x) T
H(()
The set of all classifier h induced by thresholding the verifier
g
Best-of-N sampler (for score
Sy
Best N sampler (when score f is clear from context)
g"
Rejection-sumne sampled generator: sample Pg h(x)
X + 1)
Ground-truth label indicating whether a: is correct response
ACC(g)
Accuracy of generator: Pra [p(ar) 1]
Accuracy gC True positive rate of classifier h under /
base generator graw
T(g, A)
Fig, h)
False positive rate classifier under P4
T(-) [0.
[0
ROC given by T(F)) max [T(ghne: h) l 76()), F(ghue, h) F).
by
Classifier with best T. given arg max F(g.))=F T(g,h)
N(F)
Number samples drawn from until accepted by Ay Expected number of samples before acceptance: (FN
C(F)
A(F)
Accurcyy ACC(g FF) viewed as function of F(. Accuracy A(F) viewed function ((F)
A(C)
((F)
Rejection probability
xx1
a(1 (F))
Table 1: Primary Notation
10

---

Published as a conference paper at ICLR 2026
8 REPRODUCIBILITY STATEMENT
We clearly document our experimental setup in Section 6 and Appendix E All code necessary to reproduce experiments is available the following repository: https://githunn com/
reroll
LLM USAGE
We made use of LLMs for general research support. In particular, we used them as a tool to find additional relevant literature for related work, and to help with brainstorming proof ideas. Most relevant to this, GPT-o3 suggested the use of the layer-cake trick to deal with some of the integrals appearing in the BoN analysis, allowing us to substantially simplify some of our proofs. All text, including proofs, was written by the authors.
ACKNOWLEDGMENTS
Florian Dorner is grateful for financial support from the Max Planck ETH Center for Learning Systems (CLS). The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting André Cruz.
REFERENCES
OpenAl.
https://openai.comm http:///ppenaa..mmimmdeeee learni ng- reason wi witt-withhh-tt lms/ September 2024. OpenAl research blog post.
Learning to
reason with 1lms.
Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Fei-Fei, Hannanch Hajishirzi, Luke
Zettlemoerr Percy Liang, Emmanuel Candes, and Tatsunori Hashimoto. sl: Simple test-time scaling. In Workshop on Reasoning and Planning for Large Language Models, 2025.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang. Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in 1lms via reinforcement learning. arXiv preprint arXiv:2501.12948 2025.
Team Kimi, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al. Kimi kl. 5: Scaling reinforcement learning with 1lms. arXiv preprint arXiv:2501. 2025.
Yuxiao Qu, Matthew Y. R. Yang, Amrith Setlur, Lewis Tunstall, Edward Emanuel Beeching, Ruslan Salakhutdinov, and Aviral Kumar. Optimizing test-time compute via meta reinforcement finetun- ing. In International Conference on Machine Learning, 2025.
Pranjal Aggarwal and Sean Welleck. LI: Controlling how long a reasoning model thinks with reinforcement learning. In Conference Language Modeling, 2025.
Wojeiech Zaremba, Evgenia Nitishinskaya, Boaz Barak, Stephanic Lin, Sam Toyer, Yaodong Yu, Rachel Dias, Eric Wallace, Kai Xiao, Johannes Heidecke, et al. Trading inference-time compute for adversarial robustness. arXiv preprint ar (xXvv2250111881 2025.
Koray Kavukcuoglu.
Gemini 2.5:
Our most intelligent ai model.
wawpetteee-aarch-200 /tt.mmi---------in-eee March 2025. Google Deep blog post.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jemy Tworek. Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14166 14168, 2021.
11

---

Published as a conference paper at ICLR 2026
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024.
Rylan Schaeffer, Joshua Kazdan, John Hughes, Jordan Juravsky, Sara Price, Aengus Lynch, Erik Jones, Robert Kirk, Azalia Mirhoseini, and Sanmi Koyejo. How do large language monkeys get their power (laws)? In International Conference on Machine Learning, 2025.
Xin Zhou, Duc-Manh Tran, Thanh Le-Cong, Ting Zhang, Ivana Clairine Irsan, Joshua Sumarlin, Bach Le, and David Lo. Comparison of static application security testing tools and large language models for repo-level vulnerability detection. arXiv preprint arXiv:2407.16235 2024.
Ivo Petrov, Jasper Dekoninck, Lyuben Baltadzhiev, Maria Drencheva, Kristian Minchev, Mislav Balumović, Nikola Jovanović, and Martin Vechev. Proof or bluff? evaluating Ilms on 2025 usa math olympiad. arXiv preprint arXiv:2503.21954 2025.
Audrey Huang, Adam Block, Dylan J Foster, Dhruv Rohatgi, Cyril Zhang, Max Simehowitz, Jor- dan T Ash, and Akshay Krishnamurthy. Self-improvement in language models: The sharpening mechanism. In International Conference on Learning Representations, 2025a.
Yuda Song, Hanlin Zhang. Udaya Ghai, Carson Eisenach, Sham M Kakade, and Dean Foster. Mind the gap: Examining the self-improvement capabilities of large language models. In International Conference on Learning Representations, 2025.
Anna Bavaresco, Raffaella Bernardi, Leonardo Bertolazzi, Desmond Elliott, Raquel Fernández, Al- bert Gatt, Esam Ghaleb, Mario Giulianelli, Michael Hanna, Alexander Koller, Andre Martins, Philipp Mondorf, Vera Neplenbroek. Sandro Pezzelle, Barbara Plank, David Schlangen, Alessan- dro Suglia, Aditya K Surikuchi, Ece Takmaz, and Alberto Testoni. LLMs instead of human judges? large scale empirical study across 20 NL.P evaluation tasks. In Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Pupers), 2025.
Florian E. Domnr,, Vivian Yvonne Nastl, and Moritz Hardt. Limits to scalable evaluation at the frontier: LLM as judge won't beat twice the data. International Conference on Learning Representations, 2025.
WWTG Peterson, T Birdsall, and We Fox. The theory of signal detectability. Transactions of the IRE professional group on information theory, 4(4):171-212, 1954.
Qiyuan Zhang, Fuyuan Lyu, Zexu Sun, Lei Wang, Weixu Zhang, Wenyue Hua, Haolun Wu, Zhihan Guo, Yufei Wang, Niklas Muennighoff, et al. A survey on test-time scaling in large language models: What, how, where, and how well? arXiv preprint arXiv:2503.24233, 2025.
Anthropic. Introducing claude htttps:/www..nthrrppp wtw.:aattrrppcc.cco//e/e/////e/e wtw.//co//////eeee.cc cladee- May
2025. Blog post. Accessed 30 May 2025,
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, al. Competition-Ievel code generation with alphacode. Science, 378(6624):1092-1100 2022.
Alexander Novikov, Ngån Vu, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco JR Ruiz, Abbas Mehrabian, et al. Alphaevolve: A coding agent for scientific and algorithmic discovery. Google DeepMind, 2025.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D Goodman. Star: Self-taught reasoner bootstrap- ping reasoning with reasoning. In Advances in Neural Information Processing Systems, volume 1126, 2024.
Asaf Yehudai, Boaz Carmeli, Yosi Mass, Ofir Arviv, Nathaniel Mills, Eyal Shnarch, and Leshem Choshen. Achieving human parity in content-grounded datasets generation. In International Conference on Learning Representations, 2024.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211. 14275, 2022.
12

---

Published as a conference paper at ICLR 2026
Xinyu Zhu, Junjie Wang, Lin Zhang, Yuxiang Zhang, Yongfeng Huang, Ruyi Gan, Jiaxing Zhang, and Yujuu Yang. Solving math word problems via cooperative reasoning induced language mod- cls. In The 6lst Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4471-4485 2023. doi: 1221866/////2222.aallll aclloog..--
Wei Xiong, Jiarui Yao, Yuhui Xu, Bo Pang, Lei Wang, Doyen Sahoo, Junnan Li, Nan Jiang, Tong Zhang, Caiming Xiong, al. minimalist approach to Ilm reasoning: from rejection sampling to reinforce. arXiv preprint arXiv:2504. 11343, 2025.
Zheng Yuan, Hongyi Yuan, Chengpeng Li, Guanting Dong, Keming Lu, Chuanqi Tan, Chang Zhou, and Jingren Zhou, Scaling relationship on learning mathematical reasoning with large language models. Xiviv preprint arXiv:2308.0188 0125, 2023.
Florian E. Dorner, Momehil Peychev, Nikola Konstantinov, Naman Goel, Elliott Ash, and Mar- tin Vechev. Human-guided fair classification for natural language processing. In International Conference on Learning Representations, 2023.
Daniel Ziegler, Seraphina Nix, Lawrence Chan, Tim Bauman, Peter Schmidt-Nielsen, Tao Lin, Adam Scherlis, Noa Nabeshima, Benjamin Weinstein-Raun, Daniel de Haas, et al. Adversar- ial training for high-stakes reliability. Advances Neural Information Processing Systems, 35:
9274-9286, 2022.
Lingjiao Chen, Jared Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei Zaharia, and James Zou. Are more IIm calls all you need? towards the scaling properties of compound systems. Ad- vances in Neural Information Processing Systems, 37:457677 2024.
Benedikt Stroebl, Sayash Kapoor, and Arvind Narayanan. Inference scaling flaws: The limits of Ilm resampling with imperfect verifiers. arXiv preprint w.Xiv:241..15515 2024.
Yanxi Chen, Xuchen Pan, Yaliang Li, Bolin Ding, and Jingren Zhou. Provable scaling laws for the test-time compute of large language models. In The Thirty-ninth Annual Conference on Neu- ral Information Processing Systems, 2025. URL httpt:tt////.....t.. https:://ppeeeeeieeeee net forum?id
CBM2JLhsR
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pages 10835-10866. PMLR, 2023.
Thomas Coste, Usman Anwar, Robert Kirk, and David Krueger. Reward model ensembles help
mitigate overoptimization. In International Conference on Learning Representations, 2024.
Ahmad Beirami, Alekh Agarwal, Jonathan Berant, Alexander Nicholas D' Amour, Jacob Eisenstein, Chirag Nagpal, and Ananda Theertha Suresh. Theoretical guarantees the best-of-n alignment policy. In International Conference on Machine Learning, 2025.
Lin Gui, Cristina Garbacea, and Victor Veitch. Bonbon alignment for large language models and the sweetness of best-of-n sampling. In Advances in Neural Information Processing Systems, 2024.
Audrey Huang, Adam Block, Qinghua Liu, Nan Jiang, Akshay Krishnamurthy, and Dylan J Foster. Is best-of-n the best of them? coverage, scaling, and optimality inference-time alignment. In International Conference Machine Learning, 2025b.
Adam fiers.
A generalization of roc auc for binary classi- URL https:// scher www//021/12////////c wegeenralleo lization of roc- for calnaiy-classiiiiii
Scherlis. 2021.
Blog post.
An Yang. Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang. Jiaxi Yang. Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang, Keqin Bao, Kexin Yang, Le Yu, Lianghho Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang, Xinyu Zhang, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yuqiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu. Qwen3 technical report. arXiv preprini ar0iv: 09388, 25850988,, 2025.
13

---

Published as a conference paper at ICLR 2026
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXhn:2407.21783, 2024.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song. and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Advances in Neural Information Processing Systems Datasets and Benchmarks Truck (Round 2), 2021.
Katherine Tian, Eric Mitchell, Allan Zhou, Archit Sharma, Rafael Rafailov, Huaxiu Yao, Chelsea Finn, and Christopher D Manning. Just ask for calibration: Strategies for eliciting calibrated confidence scores from language models fine-tuned with human feedback. Conference on Empirical Methods in Natural Language Processing, 2023.
André Cruz, Moritz Hardt, and Celestine Mendler-Dünner. Evaluating language models risk scores, In Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024.
Weihao Zeng, Yuzhen Huang, Qian Liu, Wei Liu, Keqing He, Zejun MA, and Junxian He. SimpleRL-zoo: Investigating and taming reinforcement learning for open base models in the wild. In Conference on Language Modeling, 2025.
NovaSky Team. Sky-tl: Train your own ol preview model within $450. https:/nnovasky aigithubii/ppoxxs/kkyll 2025. Accessed: 2025-01-09.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi. Quoc V Le, Denny Zhou, al. offinnof-thhouht prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-2485 2022.
Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems, volume 35, pages 22199-22213, 2022.
Yuyang Wu, Yifei Wang. Ziyu Ye, Tianqi Du, Stefanie Jegelka, and Yisen Wang. When more is less: Understanding chain-of-ther ofouhutght length in 1lms. arXiv preprint arXiv:2502.07726. 2025.
Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Yang Yue, Shiji Song, and Gao Huang. Does reinforcement learning really incentivize reasoning capacity in LLMs beyond the base model? 2nd Al for Math Workshop @ JCML 2025, 2025.
Tom Fawcett. An introduction to roc analysis. Pattern recognition letters, 27(8):861-88) 874, 2006.
Jesse Davis and Mark Goadrich. The relationship between precision-recall and curves. In International conference on Machine learning, pages 233 333-240, 2006.
Lori E Dodd and Margaret S Pepe. Partial auc estimation and regression. Biometrics, 59(3):614-622 623, 2003.
Wentao Shi, Chenxu Wang, Fuli Feng, Yang Zhang, Wenjie Wang, Junkang Wu, and Xiangnan He. Lower-left partial aue: An effective and efficient optimization metric for recommendation. In ACM Web Conference 2024, pages 3253-3264, 2024.
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems,
2023.
RT Rockafellar, Convex analysis. Princeton Math. Series, 28, 1970.
Guanghui Lan. First-order and stochastic optimization methods for machine learning, volume 1. 2020.
14

---

Published as a conference paper at ICLR 2026
Leo Gao, Jonathan Tow, Baber Abbasi. Stella Biderman, Sid Black, Anthony DiPofi, Charles Fos- ter, Laurence Golding. Jeffrey Hsu, Alain Le Noac'h h. Haonan Li, Kyle McDonell, Niklas Muen- nighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. The language model evaluation harness, 07 2024.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Di- rani, Julian Michael, and Samuel R Bowman. Gpqu: A graduate-level google-proof q&ea bench- mark. First Conference on Language Modeling, 2024.
Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and LINGMING ZHANG. Is your code generated by chatGPT really correct? rigorous evaluation of large language models for code generation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https:
//openrevien wwt. formm? qvx 0Cu7
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer. Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-art natural language processing. In Conference on Empirical Methods Natural Language Processing: System Demonstrations, pages 38 45, 2020.
15

---

Published as a conference paper at ICLR 2026
A ADDITIONAL RELATED WORK
A.1 "REASONING" METHODS
Reasoning models that are post-trained via RL and generally use more test-time compute play
large role industry (OpenAl 2024 Kimi al. 2025 Guo al. 2025 Kavukcuoglu 2025)
While academic efforts to reproduce RL training at smaller scales exist (Zeng et al. 2025 some of the more successful reasoning models from academia are based on model distillation (Muennighoff et al. 2025 Team 2025). These models are trained via supervised fine-tuning on outputs generated copy the larger models' behavior. Rem- prompting (Wei et al. 2022; Kojima al. 2022) designed to
by larger reasoning models with the goal of learning
iniscent of earlier chain-of-thouge make models "think step-by-step' |Muennighoff et al. (2025) show that the performance of distilled models can sometimes be boosted by simple modifications to the generation process: Forcing the model to generate longer answers by repeatedly replacing the "end-of-thinking" token with the word "Wait" noticeably improved their model'ss performance on the AIME 2024 benchmark. In contrast, Wu et al. (2025) provide empirical evidence that too large answer length can be detrimental, as well simple theoretical model to explain this phenomenon.
However, is not clear whether reasoning methods provide a fundamental improvement compared resampling-base baaee scaling methods, or merely allow for inference compute partially amor- tized: Yue et al. (2025) show that while reasoning models initially outperform base models, this trend reverses when resampling methods with perfect verifiers are applied both models at large compute budgets.
A.2 ROC CURVES
Classification algorithms usually operate by learning score (1x that induces of classifiers based on applying different decision thresholds to the score. For given score, the ROC curve represents possible tradeoffs between the induced classifiers' false and true positive rate (consider Fawcett (2006) for a summary of key properties). The area under the ROC curve (AUROC) is common metric for classifier performance, and equals the probability of giving a higher score randomly selected positive instance than to a randomly selected negative one. Davis and Goadrich (2006) note that there is a bijection between ROC curves and precision-recat tradeoffs. While precision is equivalent to the accuracy of rejection sampling in our setting, we focus on the tradeoff between precision and the expected number of samples for rejection sampling, rather than recall.
Noting that certain score ranges usually do not have any clinical meaning, Dodd and Pepe (2003) suggest to consider the partial area under the ROC curve, focusing on a subinterval false positive rates. More recently Shi et al. (2024) propose the lower-left partial area under the ROC curve that additionally caps the true positive rate, and show that this metric can be used to provide bounds on top-k ranking metries. In contrast, results establish that the limiting accuracy of both rejection sampling and BoN are fully determined by the slope of the ROC curve, close to the origin.
B ADDITIONAL RESULTS
B. TAKEN-BASED COMPUTE vs COMPLETION-BASED COMPUTE
Let T; denote the iid number of tokens generated by both the generator and verifier for the i-th sample, and let K be the total number of samples drawn by RS. Since T, is independent of the event {K = i} for j 2 i, Wald's theorem (Mitzenmacher and Upfal 2017 p. 300-301) implies that:
K E[K] E
T
Thus, when compute is measured in terms of expected number of generated tokens rather than samples, RS's compute is simply multiplied by [T()). The same is straightforwardly true for BoN
16

---

Published as a conference paper at ICLR 2026
B.2 A CONCISE FORMULA FOR BON SCALING
We show that for concave ROC curves, we can substantially simplify the integral representation for ACC(gN) from Proposition
Proposition 7. Let f be score with concave ROC curve ((F) for which assumption holds and denote (bF) (1 - (1(1 F) + ( -F)))) Then the best-of-N accuracy can be written as
r()) 4 (a)a 2
ACC(gN) 1 (1 -=)(2=22 N)
(11)
We prove Proposition 7 in Appendix C.8 We note that this is closely related to the expectation of db (a) for 3(N - 1, 1), as the beta distribution B(N - 1, 1) has the density (N 1)aa
is linear in the inverse 4 1 of the reweighed ROC curve (F)). This allows us to focus on computing the BoN accuracy for a "basis" of all possible & and then compute ACC(gN) as linear combination of the "basis" functions' accuracies. In particular, for piece-wise linear as well as concave ROC curves, we obtain a simple representation in the following theorem:
Next, we use that according to Popposition/ACC(()))
Theorem 2. Let f be verifier with piece-wise linear concave ROC curve T(F) for which assump- tion 7 holds. Then there are positive weights w, with D W; 1, I2 S and Eizo W/s such that for all N
1-n
ACC(gN)=11 = -1
w,z; N-1
(12)
1=0
Conversely, for any wi and x; respecting the constraints above, there exists verifier J with concave ROC curve TF)) such that Equation 12)
holds for all N.
We prove Theorem in Appendix C.10 From Equation 12 it is easy to see that ACC(gN) is non-
decreasing for piece-wis wise linear concave ROC curves. Proposition Dis then proven by approximating any concave ROC curve with piece-wise linear ones.
B.3 RS AND REINFORCEMENT LEARNING
Recently, Xiong et al. (0255) have demonstrated that fine-tuning LLM to match its rejection sampling distribution for given reward r is competitive with reinforcement learning (RL) using the same reward. Our next proposition provides theoretical justification for this observation, showing that the optimal KL-regularized RL policy converges to RS, as we let regularization
to zero:
Proposition For answers & in discrete space X, let g" (B) be the optimal solution to the KL- regularized reinforcement learning problem arg max," (3) (Bg-(ee [r(X)] 3D r. I.lPo (1)(( and r(x) [x) T). where Il is the indicator function. Then for any E X.
lim P P 2)
P Shaee X 2 21f(x) 2
We prove Proposition 8 in Appendix C.4 Combined with Xiong al. (2025), it suggests that the
limiting performance of generators trained by RL might be given by Equation 8 8.jjust as for RS.
C PROOFS
C.1 PROOF OF PROPOSITION 1
Proof. Since T(F) increasing, C(F) = T ++-(11--11-)) is a strictly decreasing function and thus
invertible function of Correspondingly. In particular, this means that the performance A(F) can be written as A(F(2)), ie. a function the runtime C(F).
write F(2) well-defined function of C(F).
17

---

Published as a conference paper at ICLR 2026
Symbol
Deseription
Rejection probability (1 =](1 F) + s(1 (F))))
Inverse of rejection prububility 4((a)
Domain-exiended version of vi (zcro when (a) is not defined)
(0)
Hinge function at (used as a "hasis" to approsimate convex x )
AC
Bon accuracy ACC parameterizad by
Table 2: Additional Notation
We compute the derivative
dA(CC) dC
dA(((CC)
C==(FF)
dC C=C(F)
dA(x)) dF(C))
dx x= dC C=C(F)
d.(xz)) dF(C)
dx x=F dC (==(F) d.((z)
dr
(C(x) da
l==F
We calculate
dC(x))
π
TT (z)
dx
(I( 1) TTxx))²
and
dA(x)) a ((TT(x) - x (T - (1T 1)
(I( - - TT (x)))
plug them back into the original derivative, have
dA(C)
((TT(F) - F T)) - T(F)
dC C=C(F)
-- 1-11-TT(P
(F - -
x)-x)) (11-))
π 1 - ~T
(1 π) T(F) (F (1-1)) 7)) (F)
1 (F)
(1 T) (T(F) FT' (F))
π
1+ TT (F) - π
This is positive, if and only (FF > Assuming the ROC curve concave, it has be continuous, while T'(F) is non-increasing
Thus:
T(F) = / F.
which implies:
T(F) - FT) 2 0,
with both inequalities striet for F > 0 the ROC curve is strictly concave.
18

---

Published as a conference paper at ICLR 2026
C.2 PROOF OF EQUATION
Proof. We plug in T = F = into the expression of the derivative of the performance-compure
scaling curve and get:
dA(C))
(F - x)) T (1 1) T(F)
dC'
C=1
(F)
F=T(F)=1
+)) T (1 x
1- (1
- (1) (1)
π (1)
C.3 PROOF PROPOSITION
Proof. We first focus on the case of T(0) 0. Using Taylor's Theorem, we get
F dT
T(F)
F oFF +
dF
where the derivative exists and is continuous in neighborhood of 0, by assumption. Now,
lim A(C) C-000
lim A(F) F-0
T(F)
lim
π T(F) + (1 (1-m)
(O)
(F) x T.T + (1)
lim
F-0 π. (O)F + o(F) (1 π. T) FF
π (0)F
lim
F-0
(OOFF++(fP + (1- .F
π TT)(0))
lim F
(0) + (1 -T
When T(0) > 0, we simply get
A(C) = A(0) = T(O)ACC(( T(O)ACC()")
lim C-C(O)
=1
C.4 PROOF OF PROPOSITION
Proof. Due to Rafailov et al.
(023). g" (B) has to fulfill
P (.) X x
P
X = x expl B gr(x - =x)]
Z
where Z is a normalization constant. We can decompose 7 as follows:
1 [X = ær] expl 1omplgrr0 (())
7
Σ
P ghuso
Σ
Pancel IX = 2) exppl 1
+
Priee X 22] exp(()
x;r(x)=1
z=r(z)=0
exp(
P X = x| +
Prose P X = xc]
Showe
xxr(z)=1
x=r(z)=0
exp( 1
( ) (r(X) 1] + A.P. (r(X) 0].
Srea
19

---

which converges to Published as a conference paper at ICLR 2026
Now for any with r(x) O, we have
P Panea [X = x] ( ymn (r(X)
g (8) = x]
9m.. which goes to zero for B - O. Similarly, for a with r(x:) = 1, we have
P. ghow (r(X) 0]
exp( (Pp( Dosse (X 20)
Po Pg-(0)(X= 2) exp( ( 9m ((X) = + Paiee (r(X) =
P X Ø
Show
P
Sres [X z\r(X)) =
Muse [r (X)
as 3 + 0. Thus, as the KL penalty 33r goes to zero, the probability mass function of the optimal RL
policies g" (3) converge the probability mass of the conditional distribution Pr [xr (x)r(x) 1] in point-wise sense.
C.5 PROOF OF PROPOSITION 3
We first prove a useful lemma that casts the accuracy of rejection sampling as a function of the ratio p.
Lemma 1. Whenever T(F) = aF, the accuracy of the corresponding sampped distribution A(F)
gh is:
ax π
+ n
Proof. Plug in T(F) aF to the expression of A(F), we have:
T(F) n
A(F) T(F) v + F. 17.(111 -T)
aF
aF अt + F. (1 -
a π + (1 (1-m7) TT)
Proof. For the first part of Claim 1, we simply extend the ROC curve T(F') to equal zero for all implies A(F) 0 for these F. Because C(F) is monotonously
F F(B), such that Lemma I falling in F. we get limc++Cmoe ACC(C) = 0.
For the concave case of Claim 1, we extend the ROC curve linearly for F < F(B) using the line connecting the origin to the point (,(B), T(F(B))) This yields a concave ROC curve: If it did not, the slope of the newly added segment had to be too small for concavity hold. We claim that in this case, the known part of the ROC was not extendable to a concave ROC: A slope larger than the proposed one on any sub-segment would have T(F) hit the x axis before the origin. This would have forced the ROC curve to equal zero in an interval around F = 0, precluding concavity because T(1)=
Now, the extended curve has slope (<F(B)) = T((()) around the origin, and applying Proposi- F(B)
tion 2 yields
a aFF(B)) A(B).
lim A(C)
C-C
a(F( (IF(BB)
where the second equality Lemma
For claim 2, we note that F(B)= > because < lim C(F). Meanwhile T(F(B)) > because
A(B) A(F(B)) 0. Thus, simply construct the ROC curve by connecting (F(B), T(F(B)) to (0. T(F())) by horizontal line. The resulting ROC curve thus has T(0) > 0 and by Proposi- tion 2 verifier with this ROC curve achieves limc-oci) ACC) 1.
20

---

Published as a conference paper at ICLR 2026
If we assume the ROC curve to be concave, know that its right-sided derivatives exist and are non- increasing Rockafellar (170)). We then linearly extend the ROC curve from (F(B), T(F(B))) with slope equal the night-sided derivative T+ (F(B)) at F(B) obtain the largest possible concave extension of the ROC curve. There are now three cases: First, this extension hits the x axis before the origin. Because T(0) > O, this does not yield valid ROC curve, showing that the observed scaling has not been compatible with a concave ROC to begin with. Second, we get T(0) > 0. In that case, we obtain lime coo)) A(C)
by Proposition 2
In the last case, we get T()) 0 and
thus limc-cC(o) A(C) 1. We claim that this can only happen if the right one-sided derivative of A vanishes F(B): For T() 0 to happen, we need
T(z) T(F(B)) = (F(B)) = F(B)
T(F(B))
lim F(B)
F(B)
But with this, get
A(x) A(F(B))
lim
F(B)
x F(B)
T(2xx
((FB))
T(m) T(F
lim
x+++((B)
x F(B)
x++F(() (x (--UU)/((()()))+000]]--1))------ x))
lim
lim
z++H((B) (x -
T))
-
(1 π lim
z++F((B) (x (--F)))CCEUU)//=TT-L-)))))/CC ((1-x))
-1 π) lim
T(r)F(B) - T(F(B))
lim
2+++((B)
(6-F(B)
=(1 =11-m)m (T( x))
(B))(())
lim
x-++((B)
(x))
= -11 - + x))
((B)(T())- (x F(B))T(((B)
lim
x+++((B)
(x F(B)
= (1 +)
(LB (x F(B))T(F(B)
lim
x-++((BB
(x-F(B))
(1 +))(T(((B))+++(() - - -TF(BB)
(1 + -
By the calculations at the start of the proof of Proposition | this implies that the left side derivative of ACC(C" has to vanish as well.
C.6 PROOF OF PROPOSITION 4
Proof. We will first prove the integral formula, and prove the monotonicity statement, as
Proposition Let f be a verifier with concave ROC curve T(F) for which Assumption 7 holds. Then BoN accuracy ACC(gN) is non-decreasing in N.
21

---

Published as a conference paper at ICLR 2026
later in Appendix C.11
For the integral formula, we first notice that H (k, p) can be written as an integral involving the ROC curve:
Lemma 2. Let f be verifier for which Assumption holds, and T [0, 1] curve induced by f. Then we have
1] be the ROC
H p) = k lo - (1--(((())))) F) dF if > 0
if =
Proof. We prove the lemma for the case of absolutely continuous scores f(x) with a density func- tion. The extension discrete scores f(x) will be discussed later in Appendix D
Let SN = { ,IN J be set of N iid samples from the generator. We analyze the probability that the selected output under Best-of-N sampling is correct, conditional on exactly p of the N samples being positive (i.e., y(2,) = for values of i). Denote k N the total number of negative samples. Define S ..... St as i.id. draws from the score distribution fæx) conditioned on (zx) 1, and ST ...... Sg analogously for ((x) O.
Then the conditional accuracy given positives is:
E
y arg max f(xs))
Σ u(xx)) = = Pr
max S sElpl
> max Sj jE[K]
NE[N]
To compute this, observe that:
Pr max 5 >2> -P(PS(( S s2), Pr max Sj Sz = PPr(S sz)² jElK]
sElp1
Assuming the density Ps (2) exists, the density of max; ST is:
Pmax s (2) k. Pr(SS S 2)) Ps (2).
Thus the conditional probability becomes:
Pr
max S > max Sj #Elp]
SElk]
Pr (max S+ > 2) Pmax 5- (2) dz
k /
s2)) Pr(S S 2))=-1 .ps (2) dz.
We use the ROC-based expressions:
FNR(2) Pr(S+ S 2), TNR(2) Pr(S S 22), 1 T(F(2)) FNR(2),
and change variables by setting u = TNR(2) = 11 1=F(2). Since du zz variables gives:
= -PF(2), the change of
k $ (L-((TT(F()))))) (1 F(2)) k- ps (2)
k L (1- F dF.
This final integral matches the definition of H(k, p), and averaging over p ~ Bin(N, T) yields the desired result:
ACC(g() = E Bin [ - p.P)].
22

---

Published as a conference paper at ICLR 2026
We now set (FF) (1 - F) TT, b(F) = :(1 T(F)) such that (F) = +(F)) We then simplify
ACC(g,) = Bp-B(r..) (( - p.
(change of variable A = =t- - p)
= Bkx (1-111x) x)) H. (ki, n1 - k:)
11
Σ
σT) n (1 πT [ki n 1--k) k))
n1
(x) (=)-~(11 T f (1- (1-(1-T(F))*))) -1-)-(1 F dF
k
n
(x) n x (1 -² 1 ((1-T(F)) T(F))a= F) dF
nx
k
=xx"" + 1 - nTT
Σ
n
(T) (T)-
nー x (1 - T)* ((1 - -(F))) m (1 - F) R- dF
k
1
11
)m * (1
ग. (a1 T(F))* ddF
k
n
(1 T)
Σ
k.
(x) n))= (1
k
k=1
(1 T)
Σ k
b(F) * (FF)*=
k n2)
(1 T)M
k=1
=1 (1 T)n
n b(F))** dF
(+) = (2=1)
k -
n 6(F) ( dFF)
(1 T)
(binomial expansion: Σxzo
= (a + (a++b)=) b)n-1)
(1 T)n (b(F) (FF))"
(1 T)n / (W(F)))-IaFF dF.
C.7 PROOF OF THEOREM 1
Proof. We divide the proof into two cases: Case 1, when T(0)= > O, and Case 2, when T(0) = 0. while T(7) > 0. This implies that all outputs v with f(x) 2 are true positives (y(x) = 1) and that at least one such has positive probability Pry.egly [y = 2| =: c > This means that whenever our N samples contain one of these I, Best-of-N will return correct answer with y(z) = 1. But the probability that none of N independent samples contains one of these x is at most (1 - c)* which decays to zero exponentially.
Case T(0) > O. In this case, there is a threshold r, such that F(r)
Case 2: T(0) 0. In this case, our objective is to show that the asymptotic performance of the Best-of-N strategy is determined by the slope of the ROC curve T(F) near the origin.
Proofsketch. sketch: Recall that the expected performance is given by (n-nn))-),, where p ~ Bin(n, TT- This expression is difficult to analyze directly due to the randomness of p, so our strategy is to
23

---

Published as a conference paper at ICLR 2026
approximate it using the deterministic surrogate H(/nn pl, Elp)) H(1 n)n, mn) and then
argue the limit (n + oc), these two expressions converge to the same value, namely
T0)
lim E[H(n - p.P)] = lim H(E[n - p), Elp)) = (0) +1 120000
n=000
We now proceed to the complete proof. Recall the expression for H (k, p) as:
H(k = k
(1 T(F))) (1 (1-)) dF
0
= jo (1- dF - k / (1- ( F) dF
-1 / (1 T(F)) F))=1 dF
Now consider H(n P.P) with p ~ Bin(n, T). Since Elp) 2ı7, we have:
HEE - p). E(p)) = n(1 x) S. (1-T(F))"*
T(F))" (1 ())()](
dF.
We first show that when n + oc, the deterministic approximation H (Ein p), Elpl) converges to closed-form expression that depends only on the initial slope of the ROC curve (0) and the class prior n:
Lemma 3. T [0, - 10 denote the true positive rate as a function of the false positive rate (i.e., the ROC curve), and assume T(0)= 0 and that T is differentiable at 0. Then,
(0) +(0)
lim H(Emn E(.)
where T' (0) denotes the derivative of the ROC curve at the origin (i.e., its initial slope), and æ (0,1) is the class prior probability of a positive instance.
Proof. To analyze the limit of (E'nn Elp)), we first perform a change of variables. Let u m(1 - F, so that du n(1 T) dF, and rewrite the integral as:
(EEn - p), Bip)) n01 - π.) [ (1 (1-T(F)) (1-)) dF
(n()-))
(1-T n(1
+11
du
n
We extend the upper limit of the integral to infinity by introducing an indicator function:
H H(E[n p]. Ely))
-1 -1- J.
(1-T(()) n1( (I-T(r((-m))) ))))) RT (1-
n(1 n(1-7)-1
x)
I[u n21 R)) du.
n21 x²)
To justify exchanging the limit and the integral as - apply the Dominated Convergence Theorem. The indicator function bounded above by 1, and the other terms, we use the inequal-
ity - -
nr
n(1 T)) ) $1,
- T
S exp
-nTT
n
T)
-(1-x)-1
(n(1 σ) 1 )uu
S exp
n(1 ---)
n(1 - σ))
24

---

Published as a conference paper at ICLR 2026
The product of the two terms is thus dominated by exponential function with negative exponent, which is integrable over u E [0, oo). Thus, we may take the limit inside the integral:
lim HEEnn - El, = -0
lim 12-00
1 1-T
n21 - x) (1-Tm(1->) (n(1-x))
u
))
(1-
u n(1 T)
n(1-a)-1
du.
We now compute the pointwise limit of the integrand. The key term is:
lim 1 1-T
n(1 - (1-T(((1-m)
Claim 1. Let T be differentiable at O with T(0) = 0. Then:
lim
(1-7
u
exp
Tu
7'(0)
7-000
n21 1 x)
1 1-
Proof. We rewrite using the exponential:
(1 (1-T n11
11
exp log
1 1-
n111 )
Letting = n
1 and applying L'Hôpital's Rule:
li no log (1-T( u n-+00
n2(1 T) ))
π log
1-T T
I-
lim t0
(change of variable / -= )
tu
(m)) (L''ôpital'ss Rule)
lim f00 dt
log
-
1 -
wT tu
lim 2-0
1-
(1 T1(1
T( tu
uT (--7
lim
-T
(1 (1- T
(0)
- (1 (1-T) -
nu ('
- π
The second term converges similarly:
(1 (1-ml n11 T)
u n(1-x)-1
- e
Putting it all together:
lim HEE|n - p). Elp)) = 2+0
E
nu
T'))
1 du
T'()) + +1)a 2 du
exp
(Claim
π
1
I- T +1
+1
T(()
T'() 1
25

---

Published as a conference paper at ICLR 2026
To complete the proof, it remains to show that
lim [ p.p)) lim H Blpl)
We approach this by conditioning on the event that the random variable p Bin(n, concentrates near its expectation. Fix an arbitrary t > 0, and define the high-probabilie event
Elp)
E,
J
which corresponds to the event that the empirical frequency of positive samples deviates from its mean by less than Conditioned on this event, we can decompose the expectation in the following way:
En - p.p]] pPP] = Pr(E.) En - p.p) E.] + Pr(-E:) En - p.p) -Ee]-
To proceed, we use the following lemma, which shows that the success probability H(n p.P) increases with the number of positive samples p:
Lemma 4. For fixed n, H(n p.
(n (n-p)) p) (1- P increases in p.
Proof. For integer values of this follows from the definition of
Hnn p.p) Pr
max S (E(P.
max SJ jEmn-P!
Pr
max ST [E[p+1]
max jEin-p! pl
ST)
Pr
ST
max jE(n-P-1 11
SJ
iE(p+1]
by strict inclusion of the events in the corresponding probabilities.
For non-integer values of p, we define the random variables 5 and S via Pr(S# 2 2) = Pr(S- 2)
and assume them to be independent from the S:F. Then
Pr
mmax S St = 1 - -Pr(st S 22)te,
(E(p)
Pr
max max jE(n-pl
S S =Pr(S 22)m-pte
Assuming the density ps- (2) exists, the density of Sn-pts =: max ST thus equals:
P PInx n Dic (z) (n 1 --)+) Pr(S S
ps (2).
Repeating the steps from Lemma 2 we get
Pr mmaxfmax St+ Stt max kE(r)
max SJ ST.
je(n-p-11
for any positive integer p and & E (0, 1). For any positive integers p, such that p + q < n and & E (0, 1), we then have
H(n q exp+q+e) Pr max max iElptgi
St
max
S7 (T
jEin sEIn-p-q-1 p-
Pr max St (E(p+g]
max jE(n je(n-p-1)
Sj
Pr
max S (EE()
max S7 jEl (((=
H(n p.P):
26

---

Published as a conference paper at ICLR 2026
where the second step uses that can couple Sn-p-g-s and Sn-p-o such that the latter is larger with probability one, due to its CDF being larger at any point. An analogous argument works for p q establishing monotonicity.
Recall the decomposition of the expectation as: (1 p)p [n p. p,p) B.].P(E:) + (n p.p) | P(-Ex). By Hoeffding's inequality, P(E,) -
for any fixed t > 0. Since H(n p. p) E [0. 1],
the second term vanishes in the limit. Hence, for any
lim sup (n p.P)] = lim E H nn - p.p) Ej
n2 000000
a n-000
and
lim inf [E p. p)] lim E| (n p.p) Ed].
n-000
2-000
Now, fix t > 0 and consider the conditional expectation over E; = {| p-n < t}. Since H (n-p.p)) p.p)
monotone increasing in p (by Lemma
4 F, we always have:
11n(11 π + f), n - t)) - (n - p.p) S - t)).
Therefore,
Hmn(1- + (), n(T - 1)) S E[H(n - p.p) E.] S H(n(1 - - 4), +)).
This means that
lim sup [[H(n p.p)] = 1imm E H(H p.P) Ex]] n-000
n++00
I lim lim (nn(1 т t). n( + t))
n-+00
lim H(n(1 - π - n( + ())
T'(0) + t)
T())(TT + + (T + t)
lim inf E(H
p.p)] (pP.p)
lim inf E( p.p) E&]
n-
n-+00
lim H(n(1 т + 1), n((T - 1))
n-+00
lim H(n(1 - π + f), n(T - 1))
T'(0) - t)
T( + (T -
(=) But as +1- (T]
is continuous in и and & was chosen arbitrarily, we get
('))
lim sinsup E(H - P.P)1 < T'(0) + +1 7=000
in P. p)]
n
and thus
T'O)
lim B(H(n p)] T')0) +1-7
C.8 PROOF OF PROPOSITION 7
We make use of the following Lemma.
Lemma 5 (Layer-cake reformulation for N-1), Let [0,1] [0, 1] be a convex and de-
creasing function and N > 2. Set M max (FF). Then:
[-
S/44 M
(1F N-1 dF (N -2) 1)
1b (a) N-2 da.
27

---

Published as a conference paper at ICLR 2026
Proof of Lemma Since d is convex and decreasing, it is continuous (0, 1]. Furthermore, the exact value of (0) does not affect the integral, we can without loss of generality assume that e is continuous the whole interval [0, 1]. This means that the inverse & is continuous function defined on [0. M) We now begin by applying the layer-cake representation to the non-negative function 2/ M- Since (F) is decreasing and bounded in [0, 1], we can write:
S. ((F)N-11 N-1) dF= I P(W(F)N-1 2 a) da
MM-1 P(o(F))-1 2 da f MN-1
P(O(F) 2 al da
(at(((1 da + 0.
The last step uses that for the left term a (FF)N-1 > a is equivalent to F S (a-(NN)) since v decreasing. For the right term, we use that (FF) N- < M with probability one.
Now perform change of variables. Let a ( that w and da (N 1 N -2 du. Then:
M NN
2 (a (a da ( M 2 (w) (N - 111u" N-2 du
(N (N- 1) / w-)(u) u. du.
M
We now prove Proposition Duiin Lemma 5
Proof of Proposition
By Proposition 4 we have
ACC(gN) = 1 T)N L( ((F)N-1aF,
where (FF (1 (1 F) x(1 T(F)) is convex and decreasing with (11 and
(0) = 1- (0). Lemma 5 then gives us
ACC(gN) 1 T)N L'' b(F)N-IdF dF
1 - (1 (1 ((11-))N(N--) - / (007((
vb (a) N-2
C.9 PROOF OF PROPOSITION
Proof. Fix N E N. By definition, have
C(FN) T(FN)+ FN T)
N.
Then the expected accuracy rejection sampling is
ACC(g = म T(FN).
By Proposition 7 due concavity of the ROC, BoN accuracy is given by: 3/ (a)a N do.
1-x((0)
ACC(gN) = - (N N)
28

---

Published as a conference paper at ICLR 2026
where (b(F) (1 F) - -T(F)) is the probability that sample is rejected.
To compare the two accuracies, we rewrite the incquality to shown:
N.w T(Px) 2 1 - (1 x - N) /
(a)a 22
Since we know that:
T(((N) + -1) FN 1
N²
we can rewrite the left-hand side:
N T(FN) = 11 N(1 FN
So it is sufficient to prove:
1 N - 21- (1) -1) (=xT(0)
(a)a"a
which is equivalent proving:
FN
SN (N
1/ (a)a
We rewrite Fy in terms of vb. Recall that
C(FN) T(FN)= + F +
N.
Using the identity (FF) = (T(F) TT F(1 ---) T)). we obtain:
1
N
(bFN) = N
so Fx 1/
N
N
In particular, this implies that xه (x) is defined for 0 < < N-1 N
and it suffices to show:
/-'
(N 1)
(a)a
da.
We observe that the right hand side nearly matches the expected value of (-)(a) under Beta distribution with parameters (N 1, 1):
Lemma 6 (Beta expectation form of layer-cake integral). Let f (0, 1] -> 1] be a function, and let N 2 2. Then:
(N -1) S( f(a) N-2 da Bew-att(N-11) [f(a))
Proof. Recall that the probability density function of the Beta(o, () distribution on [0, 1] is given by
(a(x)) B(a, 3)
(1 x) 3-1 for x E [0,
where B(a, () is the Beta function.
For the case = N - 1 and B = 1, since B(N 1,1) N-T. we have:
1)x: N22 [0,1] (a(x) (N -N
Therefore, the expectation of f(a) under 1 is:
Ea-Beta N 1,1) [f(a)] /'' f(a) (N N)aa da.
29

---

Published as a conference paper at ICLR 2026
Now, since that the ROC curve T is concave, it follows that (F(F) is convex, and hence e is convex on its image. We extend the domain by setting
v (a)
if S M ifa> M
(a)
0
The extended function v-1 remains convex on [0, 1] because d was decreasing with value 0 the right end of its domain.
We can therefore apply Jensen's inequality obtain:
N
N -
8-1
~ (Ba--Bea(N-1.110)
N
I Ba-Beta(N-1.11 [a)] = (N 1) //' ~-) (N
- (N--) 1==T(() 2 (a)aa)a
This concludes the proof.
C.10 PROOF OF THEOREM 2
Proof. We begin by considering alternative equivalent characterizations of concave ROC curves:
Claim 2. Let T [0. 1] 1) be an ROC curve for verifier f. 'Then the following are equivalent:
(a) T is piecewise linear, strictly increasing, and concave with (11 1, for all F E [0, 1].
F S T(F) 1.
(b) The function wo [0, 10,1 [O) with (FF) = -1- piecewise linear, convex, strictly decreasing with (1) = O, and satisfies
is
x) F) s (FF) 1 F for all F [0.11.
10, 1] is piecewise linear, convex, strictly (c) The inverse function v/ [0, =T(O)] - decreasing with & (0) = 1, and satisfies
S の (a) S
for all a E 10,11-77(0))
Proof. Going from a) b) is simple: Since (F) is convex combination of the piece-wise linear, strictly decreasing and convex functions (1 F)) and T(P), it has the same properties. The bounds follow directly from the bounds T(F). The reverse follows from the same argument, again using that (F)) and T(F) are linear transformations of each other. Lastly, it is easy to see that (1) is equivalent T(1)= 1.
For the cquivalence of b) and c), we first note that the inverse of a strictly decreasing piece-wise linear function always exists and piece-wise linear. In addition, v+1) is clearly equivalent to db- (1) = O. Next, we need that the inverse of any convex, decreasing function f is convex and decreasing. We begin with the decreasing part: Consider f(x) > f(y). Then since was decreasing
(f = < <
Now for convexity, we need to show that
(1- < X5 -
for any À [0, We the convexity of f and that f-1 is decreasing calculate:
(-((()))+ (1-))))11))))) < 1- + (1-A)))
Az (1 -1- AAy
=f + (1- (1-1))
30

---

Published as a conference paper at ICLR 2026
It remains to show the equivalence of the bounds. For this, note that the respective bounds for & and 2b (P') are inverse of each other, so it is sufficient to show that for decreasing f. 9. we have f(x) $ g(x) = f (v) $ (v). For this, consider f(x). Then,
(v) = ( (g(()
= g (f(z)) 2 و6 (f(x))) g(z) 2 f(z)
and analogous for 2.
With this, we set 7 == 1 =T(0) E [1- - 1 and extend 2 by zero to
(a) = (5=1(a)
a a [0. r),
(0, a E 1].
By Proposition
ACC 11 11 (N [
J (a)a N2 da.
(13)
The extension preserves convexity and monotonicity, with ( (1) 0, and the pointwise bounds
max
0, - 3 (a) S
(a E [0, 1))
(14)
In particular, -c (gN) is linear and (L1) ccnttinnnsss in f-1 such that whenever we can express
(a) w.bb, (a)
as the L1 -limi of sums of basis functions ,-, we get
ACC.-=108 E W (gN)-
For the basis functions 8 we consider the family of "hinge" functions: Definition 2 (Hinge family), For x E (0, 1}. define the hinge function as
a S x;
8 ( =
x
aE [0.
(15)
0,
2,
With these, we have that
8 (a) = max (0,
a
} 11-10 =1- (a)
(16)
1 1- π
We now claim that 3 fulfills the layed-out conditions if and only if can be written as a con- vex combination -1 Ei wrb- with positive weights w; adding up to one, x; S and E0 W3
Lemma (Characterization of -1), A function $-1 : [0, 1] + J0, 1] satisfies the convexity, mono- tonicity, and slope constraints if and only if it can be written as
3-)
Σ w. (o),
E [0. 1].
where (a)( maxf a/x, 0} are the hinge functions, and the parameters satisfy
w; 2 0,
Σ
wa = 1,
24 S 1,
W4 <
1
0=0
31

---

Published as a conference paper at ICLR 2026
Proof. (=:) We begin by showing that any such convex combination gives us valid ab-1: Since the b-1 are piece-wise linear, decreasing, convex, and fulfill the boundary conditions, the same is true for any convex combination. Similarly, the 8- are point-wise increasing in æ, such that by is an upper bound for any such convex combination. Lastly, any convex combination ại- = E== waby. with Ei=0 We m, I I- has its derivative lower bounded by ---m while being a positive function, such that di- is lower bounded by b
(E:) Now, we want to show that any valid xi- can be written as such a convex combination. We thus fix any piece-wise linear, convex and strictly decreasing si with a/ (0) = 1, as well as
(a) 11-a
for all a E 10,1- (0))
We explicitly construct the sum representation follows, for now ignoring the constraints: Let (In) be enumeration of the pieces of u0-1, ordered from right to left. We build the sum inductively, matching the behavior of أي on the intervals (In)nga at the kth step.
For the base case, we start with the empty sum, matching - on the empty set.
Now for the induction case, assume that
$
Σ
on the intervals (In)sgn. We now simply pick r2+1 = ags where ag is the left endpoint of Ig and pick
Wk+11 1141
2
where 0641 is the slope of -1 on the interval Ix+1 such that
1
0k+1
Wi
1=0
is indeed equal to the slope of the constructed sum w-
Σ k+1
w,bz.' Because b (a) = 0 for
2 x, this does not change the sum's behavior on the previous intervals, so that the sum matches
- all for up +
There thus exists sequences w, and x; such that
3-) Σ w-b-1
where the series converges posnt-wise, and thus L, via dominated convergence (because both the 6-1 and (1) are bounded.
We now claim that the constructed wa and zy fulfill our constraints: By construction, have Ia 1. Furthermore, because d is convex and the slopes ag thus increase (we go from right left!), all wa are positive. Next, if Exe w; * 1, the boundary condition e violated. Lastly, for the sake of contradiction, assume that Di Wi __ Then, we can find
would be
finite & such that Db w --= There then exists an interval such that (a) - for all E 7 and i < k. But that means that for E I
32

---

Published as a conference paper at ICLR 2026
(a)
wib w;bb,110 (a)
i=0
20
Σ
wrbb (a) +
Σ
(a)
i=++1
waby (a) +
Wi
1=0
i=++1
Σ
1i (1
W/s
t=
k=
W
42
π
which contradicts Equation (16).
By Proposition 7 ACC only depends the function + induced by f. By Lemma are verifiers f with concave ROC curves induced by any
there
20 wi b (a) in L. [ 1)),
(a)
Σ
WA 2 0,
Eu;
=
w
Wi 2
x E (0,
π
Now, using linearity, Lt c'-coniinuity, and slightly abusing notation by parameterizing the BoN accu- racy as ACC(gN ), we get
b-11 ACC( # ) - wi ACC
= -1 (1 (0--T))(( N(N 1) Σ
b (a) a N-2 222 do.
IN
i=1
i=1
0
For each hinge Brz (a) = max(1 (1 - a/2x 0} we can write
S :. (a) (a) N22 da = 0
N- N(N 1)
a
Hence the accuracy simplifies to the closed form
ACC(gN -1 T)
Wi x N-1
(17)
Remark 1. The operator norm of AN L' 1]) equals (1 T)N (N 1): therefore, while the passage to the limit above is valid for each fixed N, the convergence need not be uniform in N.
C.11 PROOF PROPOSITION
Consider any 0. Assume, that there is convex combination of hinge functions $-1 wy such that
- T -le,,,,, I 2N(N + 1)'
where - is defined as in Appendix C.10
33

---

Published as a conference paper at ICLR 2026
Repeating the steps from Theorem get
ACC - ACC(gN ') (1 x
w2(2 N-1 v.n) >
1
Since ACC(gN) ACC(gN+)) is 2N + Lipsschit in the L1 norm via the representation from Proposition this means that ACC( 6- + ACC thus have
x "). Because arbitrary,
(gN+1) ACC
remains to show that we can indeed L1 approximate any e by convex combinations of hinge functions. This is established by the following lemma:
Lemma 8. The set of convex combinations of hinge functions is L dense in the set of all decreasing,
convex convex functions & on [0, 1] with the boundary conditions & (0) = 1, (1) 0.
Proof. The key idea is that we can write piecewise linear decreasing convex functions as convex combinations of hinge functions (Step 1), and those are already dense in the space of convex func- tions (Step 2):
1. (Step 1): For any convex piece-wise linear function ق with finitely many pieces and values in [0. 1]. we use the construction from the proof of Lemmal 7 to explicitly write &i as convex combination of hinge functions. Because 1b-1 has hniitlly many pieces, the resulting convex combination is finite.
2. (Step 2): Now, given any convex function &-1 with the boundary conditions, and evaluate Φ on the points K k k NAOS < S n). Then the linear interpolator xb-1 of {a, (a) x E K} is a convex piece-wise linear function with finitely many pieces that fulfills the boundary conditions. In addition,
fix
1 16 (a) -----11- (a)lda
b6b
(a) - + (a)(da
max 1
aE 12
K+1
2L
n
k=0
2L
+
n
where L the (uniform) Lipschitz constant of which exists for convex real functions compact intervals Lan 2020)).
C.12 PROOF PROPOSITION
Proof. We first focus on the non-concave case: There, via Proposition 4
BoN accuracy is given by:
ACC(o()= = (1 T)N J (F( dF.
where (FF) (1 () F) + 7(1 - (F())) is the probability that sample is rejected given FPR F for the verifier ʃ.
For consider f with
(Ty FF> 8
Ty(
0
F
34

---

Published as a conference paper at ICLR 2026
Then by theorem limm- ACC(g))= =
But (F) = 3 for F > 6, such that
-11 M) / 6y(F) N-1 dF- - S/' O9(F)N~1 dF
- -
= =11 T) 2y(F) 10((1) drl
(1 n N
By (F) (F)
= (1 π T)N N < (1 T N8
Jy(F) dF
because y is between zero and one. In particular, this smaller than e whenever < (I-+)M For fixed upper bound N < n., simply choose
Now, consider f' with
(Fy :F> 5 (6) FF56"
Ty. (F)
which leads to lim ACC(gN) according to the second case of Theorem In this case,
ACC( ACC(o() --
(1- =)N ( -0) dFl
= -1-17) -1-
- dF
< (1 - R) N2
from where we proceed as before, this time setting
2 2(1
For the concave case, our argument has two steps: First, we show that there is a convex, decreasing piece-wise linear ف with (0) = 1 and + ( = 0 such that
|ACC(ON ) - ACC( 5 2
for all N < n. Then, show that for any piece-wise linear --1, there is another convex, decreasing piece-wise linear T- with v ( = 1 and J ( = such that lim ACC(g) 1 and
|ACC &11 ACC(ON ) 1
Then by Theorem 2 there verifier with concave ROC that induces T-1, and by the triangle inequality that verifier meets the theorem statement.
The first step directly follows from Bombinee with the (uniform) N ((N- 11 Lips-hipshissnesss L1 of (CC(,) (gx) for & n. We note that the di constructed that way fulfills the linear con- straints from Equation (6). as a linear interpolation of the function xi that fulfills the constraints.
For the second step using Theorem we can write ACC(g) )) = 1-
N-1
E wi b.
where b, e; and the æ; fulfill the constraints from Theorem because & fulfilled Equation 16 Without loss of generality, assume all b; 2 be distinct as well as b 1 and u2 0.
35

---

Published as a conference paper at ICLR 2026
Then we have
c= lim ACC(gN #0
N
N-1
= lim
1 - (1 π
Wi bi
N
80
1 N-1
=1 (1 σ
W
lim
+00
W
where we used 1 N-1
b. + 0 and applied dominated convergence to exchange the sum and limit,
using that wi by
N
< w; which sum up to one. This implies that w1 = I-c 0. Then for
I-T
fixed > 0 and n E N. there is constant 5 > 0, such that N-1 - 11 S Tw.[1-x] and I+6
N-1
N- 1 ( for all N < In particular, because b 1, we can find such 8
by wy in a way that guarantees 62
u2
wy
With this, define b, 6, bo b2
wid and by by for i 2 2, well
With this,
wz
6
(a(b; b.) w1 + w2 W2
8 0,
such that by fulfills the constraints from Theorem
This means there is verifier f with concave
ROC such that ACC (-1 = (1 x == Wi
N-1
b.
Because all b, are strictly larger than one, we have
N-1
lim ACC(g() = 1 (1 - n
lim
= 1.
N N
+00 bi
At the same time for N < n,
|ACC(oN ( ACC(ON 3 ) S (1 - x)wr(
1 N
1
N-1
1 N-1
1) (1 - rT T)
8 ++1
b2
101 8
b2
122
s + 4
D RELAXING ABSOLUTE CONTINUITY
Verbally prompting LLMs for risk score estimates has been shown to effectively produce calibrated and accurate scores (Cruz et al., 2024), but can also lead to limited score resolution (since in practice only few discrete score values generated by the model). However, many of our proofs require the score to be absolutely continuous. Despite this, empirically, our theoretical predictions remain valid across the board. this section, we resolve this discrepancy, showing how our theory extends to discrete scores via a small modification to the definition of the ROC curve?]
Assumption I requires the scores f() be continuous and have a density. However, in practice such as for our experiments in Section 6 the scores f(r are often discrete, taking on values in a finite set S. In this section, we show that small modification of the ROC curve, which results in smoothed version of f which we call f. happens to coincide with how ROC curves are plotted in the popular sk sklearn en package and makes our theoretical results work the discrete case:
TThis modification happens coincide with the way the popular sk earnn package plots ROC curves
36

---

Published as a conference paper at ICLR 2026
Definition (Smoothed Score f). Let f() be discrete scoring function that takes on finitely many values 8 E S, and let e > 0 denote the smallest difference between any two distinct values S. We define the smoothed score as:
- - C -
where each &. Unifl-1, 1] an independent random variable. The resulting function f(x) has density.
We will show that the ROC curve of f achieved by linearly interpolating the points
F. T(F) max h) h H(f),, F(g. h) F)))
exactly as done in sklearn, that b) induces same accuracy for BoN as f, and c) that scaling of rejection sampling for f is the same as the scaling for rejection sampling, allowing for mixtures of adjacent thresholds
interpolates the ROC curve of We now show that the ROC curve induced by f is linear interpolation of the stepwise ROC curve defined by f. For discrete scores, the ROC curve
max (T(g,)) h) H(f), F(g, h) F)
is a step function, since it only increases at values of corresponding to thresholds h² where E S one of the finitely many values taken by (xx)
First, we show that f exactly recovers the endpoints of each step in the ROC curve induced by f. Suppose f(11 < f(2)) are two adjacent values in S. Setting the threshold r f(1) ensures that all with f(x) 2 f(1) are accepted (with probability 1), while all others are rejected. This yields the same T/F point thresholding at f(x1) on the original function f. Similarly, thresholding at f*22) recovers the ROC point corresponding to f(z2). Hence, f retains the same step endpoints as f.
Next, consider any threshold r that lies strictly between f(11) and f(22), namely
T == f(x1) (0 (
)
for some [0, 1).
This threshold induces the following acceptance behavior:
any x' such that f(x') 2 (x22 will be accepted with probability one.
Ii will be accepted if and only if the corresponding noise & exceeds 2q 1, which happens with probability
Thus, using this threshold for equivalent to using the threshold f(11) with probability g and the threshold f(x)) with probability 1 for the original verifier f. which is equivalent to using randomized threshold.
This random threshold behavior leads to the convex combination of ROC points, i.e., linearly inter- polates between them Fawcett 2006).
BoN Accuracy is unchanged with We condition on the event that of N samples æ achieve the (sample) maximum of the score f(r). Then, BoN on f picks one of these uniformly at random. Thus, need to show that BoN on does the same.
By construction of the noise, only samples z; that maximize f(x;) can maximize f(z)) with nonzero probability. Among these, BoN on picks the for which the noise variable & is maximized. But because the &, are IID, this amounts to picking one the z; maximizing f f(;), uniformly at random.
37

---

Published as a conference paper at ICLR 2026
E ADDITIONAL EMPIRICAL RESULTS
This section provides additional empirical evidence to support our theoretical results, using different generator models, different verifier models, and different GSM8K test questions. These questions were chosen by running the Qwen3-L 11. 7B generator on the whole GSM8K test set and selecting the first questions that were answered incorrectly.
Implementation details. Generator model responses are evaluated using the 1m an--evaluation-hare description, the test question, and the generator model's chain-of-thought and answer. For each generator response I, the verifier is prompted to reason over it step-by-step and to output correctness risk score fzz at the end of its response. On MATH500, both generator and verifier models are capped to produce at most 5K output tokens for each answer. Model outputs are uncapped for GSM8K, answers were generally much shorter, hence generation length was issue. In some cases, we sample multiple risk scores (() for the same verifier and average them in order obtain a less noisy score. Prompt templates and examples are shown in Appendix [F
(Gao et al. 2024) package. Verifier models receive the task
For GSM8K, we evaluate (z) via exact match of the bracketed answer. As MATH500 often allows for multiple correct phrasings of the same answer, answers and compare them to the ground truth in order to obtain y(z). On GPQA, we evaluate y(x) exact match with the letter code representing the correct answer. Meanwhile, for humaneval, evaluate using the test suite and environment from the evalp uss package.
the math- aeth-verrffy package to parse
Due an issue with the setting the random seed, our reported aggregate results on GSM8K, MATH500, GPQA and humaneval resampled the few-shot prompts once per question, while the results on individual GSMSK questions resampled them once per generation, potentially leading to more diversity in the responses to each question due different few-shot examples for different generations to the same question.
# Quirtes
10²
10
10
10
10
10
Figure E.1: Histogram number of generations required to achieve (xx 2 r across GSM8K items, capped at 10000. The vast majority of queries require less than ten samples, but 16 queries never meet the threshold. Verifier models: Qwen 32B (bluc) Generator: Qwen3-1.7B
Verifier
Rejection Sampling
X 1.77
0.8
0.9
X
Q48
True Positive
0.6
0.7
Predicted
0.6
0.2
0.5
0.5
0.3
0.5
1.0
2
Number Generations
Number Generations
Figure E.2: Empirical performance (lines) rejection sampling (middle) and BoN (right) on GSM8K test question (i = 2). overlaid with predicted theoretical performance (x markers). Verifi- cation score obtained from single chain of thought. Generator: Qwen3-1.
38

---

Published as a conference paper at ICLR 2026
Verifier
Rejection Sampling
X
1.7B
0.8
True Positive
0.6
0.3
0.2
Predicted
0.2
0.1
0.0
0.5
1.0
2.5
5.0
7.5
10.0
20 40
Generations
Figure E.3: Empirical performance (lines) rejection sampling (middle) and BoN (right) on GSM8K test question (i = 7). overlaid with predicted theoretical performance (x markers). Verifi- cation score obtained from single chain thought. Generator: Qwen3-1.
Verifler ROC
Rejection Sampling
Best-of-1
0.90
0.90
X
Q..78
Positive Rate
0.8
0.85
0.85
32B
0.80
0.80
Predicted
0.2
0.75
0.75
0.0
0.5
1.0
1.0
1.2
1.4
1.6
2
False Positiiee
Number Generations
Number of Generations
Figure E.4: Empirical performance (lines) of rejection sampling (middle) and BoN (right) GSM8K test question = 7), overlaid with predicted theoretical performance (x markers). Verifi- cation score obtained from single chain of thought. Generator: Qwen3-4B.
Verifler ROC
Rejection Sampling
Best-ofvr
1.0
1.00
1.00
Q.7.B
Positive Rate
0.8
Q.4B
Accurecy
0.98
0.98
14B
32B
0.4
0.96
0.96
Predicted
0.94
0.94
0.0
0.0
0.5
1.0
1.0
1.2
1.4
1.6
2
False Posilive Rate
Number of Generations
Number of Generations
Figure E.5:
Empirical performance (lines) of rejection sampling (middle) and BoN (right) on GSM8K test question = 8), overlaid with predicted theoretical performance (x markers). Verifi- cation score obtained from single chain of thought. Generator: Qwen3-4B.
Verifier ROC
Verifier: Llama-3.22-3
Verifier: Llama-4-17B-18
0.10
True Positive Rate
0.8
0.08
Aceuracy
36
0.6
0.06
RS
0.04
BoN
Empirical
0.2
Lama 4-178
0.02
Predicted cted
Lamm--322-08
0.0
0.00
0.0
0.5
1.0
2
10
20
30
40
50
False Positive Rate
Number of Generations
Number of Generations
Figure E.6: A version of Fig. 3 on different test question, i 7. The same trend is observed: rejection sampling uses significantly less average compute than BoN for the same accuracy gain. Verification score obtained from single chain of thought. Generator: Llama-2 3, 2 3B, with 6.7% generation accuracy.
39

---

Published as a conference paper at ICLR 2026
(RS, 7)
(Capped RS)
0.50
0.50
0.45
0.45
Acouracy
0.40
Accuracy
0.40
0.35
0.30
0.30
(RS)
(BoN)
4B (RS)
Q3 4B (BaN)
10
14
10
12
14
Number Generations
Number Generations
Figure E.7: Aggregate accuracy of RS with heuristic variable threshold (left) vs Capped RS (right) on GPQA (Rein al., 2024). Dotted lines show Bo25 performance for the respective verifiers. While within error bar range, both RS with variable threshold and Capped RS appear to outperform BoN. Verifier models: Qwen 32B (blue), Qwen 4B (orange). Generator: 3wen 7B. Error bars: Exact 90% CIs for accuracy.
HumanEval+ (RS)
HumanEval+ (Capped RS cap@25)
HumanEval+ (Capped R$ cap@10 0)
0.8
0.8
0.8
Accuracy
0.7
Accuracy
0.7
Accuracy
0.7
Q3 52B (RS)
0.8
0.8
0.8
Q3 328 (BoN)
(BoN)
Average Number of Generations
Average Number of Generations
Average Number of Generations
Figure E.8: Aggregate accuracy RS with heuristic variable threshold (left) vs Capped RS (middle and right) on HumanEval+ (Liu et al. 2023) with different caps on the sample number. Dotted lines show Bo25 performance for the respective verifiers. While within error bar range, RS with variable threshold appeears to outperform BoN, Constant-threshur RS is sometimes outperformed by BoN when capped at samples, but appears to consistently outperform BoN when capped 10 samples. Verifier models: Swen3-3222 (blue), Qwen3-45 (orange). Generator: Qwen3-1. 7B, Error bars: Exact 90% CIs for accuracy.
40

---

Published as a conference paper at ICLR 2026
F GENERATION AND VERIFICATION PROMPTS
Listing shows boiler-plate Python code used encode GSM8K input document questions with few-shot examples. The output of this function will be tokenized and sent to the LLM gener- ator model. The boxes that follow show the system prompt used for the LLM generator mod- els, and task definition prompt used for the LLM verifier models. We use the HuggingFace trans formers (Wolf et al. 2020) package for LLM completions. Note, that we use the same prompting strategy for Llama and Qwen3 models; in particular, do not make use of Qwen3's "thinking" mode.
def encode with__catt template (
sclf: Cenerator, questicn: str, task: Task, num fewshet: int,
6
str: "*"Encode the input question and few-shot examples using chat template. "*"
conversation: list list/dict/ Il if self.system prompt:
conversation =
("role"; "system", "content"; self.system_promes
14
Add fewshot examples
for fewshet_example in task. www.ffewwwweaneeeeeeeeeeeeeeeeee fewshot, self. rng)
17
Add question as user message canversation.append
18
"role": "user", "content": f"Question: (feushot_examples (o })",
})
22
23
Add answer as assistant message cenversation.apeeddl "role": "assistant", "content"; f"Answer: (fewshot_example) ('awwrr' ))"
26
answer'
27
1)
28
Finally, add the task question user message conversation. (f
31
"role": "user", "content"; f"Question: (question)", 1)
32
33
Apply prompt template. add_ welggeeeationorootteeeooo will add the tokens to signal the start > of the assistant's turn.
36
prompt_up_tee assistant_tura convesseiionccoreesstttton
self.tokenizer..ppl. template
39
40
tokcnize-False, add_geneeaationorrmmttee
41
44
Append the desired prefix for the assistant's response encoded_ return encoded_ prompt
45
"Answer:"
Listing 1: Generator GSM8K chat-template encoding function, using the transformers package.
41

---

Published as a conference paper at ICLR 2026
Generator GSM8K System Prompt
You are helpful assistant that solves math problems. Think step by step. After reasoning, provide your answer separate line using the format: ##### <answer>>
Generator MATHS00 System Prompt
You helpful assistant that solves math problems. Think step by step. After reasoning, provide your answer separate line using the format: (bboxed(answer)
Generator GPQA System Prompt
You are helpful assistant that solves STEM problems. Think step by step. After reasoning, provide your answer in separate line using the format: The correct answer is (insert answer here)
Verifier Score Prompt
You a helpful assistant that verifies the correctness of response question. Think step by step, carefully reasoning over each step of the response. Finally, your assessment should end with a score between and 10 indicating how likely the response is to be correct. Your correctness score must strictly follow the format "[I<number>>> ]]"; for example, "[[O]]" means the response definitely incorrect and "[[10]]" means the response definitely cor- rect.
Generator HumanEval+ System Prompt
You helpful coding assistant. You will be shown python function header and example behaviour: Please responsd with the completed function according to the specification. Keep all explanations constrained comments within the code. Your answer should have the format
"python <code>
Verifier Score Prompt (Code)
You are a helpful assistant that verifies the correctness of python function. Think step by step, carefully reasoning over each line of code. Finally, your assessment should end with a score between 0 and 10 indicating how likely the code is to be correct. Your correctness score must strictly follow the format "[[<numbr>>]]" for example, "[[O]]" means the code is definitely incorrect and "[[10]]" means the code is definitely correct.""
42


Reviews:
[{"review_id": "yTUDv158kM", "reviewer": "Reviewer_dsXu", "summary": "This paper presents a timely study on how imperfections in a verifier affect the performance of test-time scaling, where the goal is to improve accuracy by spending more compute at inference time. The authors analyze two commonly used techniques: rejection sampling (RS) and Best-of-N (BoN). They show that the performance of both methods is fully determined by the geometry of the verifier’s ROC curve. For RS, they prove that performance in the low-compute and high-compute regimes depends on the local geometry of the ROC curve — specifically, how the ROC behaves near the operating points corresponding to large and small false-positive rates (FPR). In the high-compute regime, accuracy is governed by the slope of the ROC near FPR $\\to$ 0. For BoN, performance depends on global ROC properties.\n\nTheir theoretical results, supported by experiments, show that RS is more compute-efficient than BoN in the finite compute regime, while both methods converge to the same asymptotic accuracy as compute goes to infinity. A key insight is that test-time scaling cannot be extrapolated: low-compute performance does not predict high-compute performance unless one knows the ROC geometry.", "questions": "Here are both questions and comments:\n\n- This question might be a bit more abstract: the weakness stated above leads me to wonder whether compute could be defined differently in this setting. In the paper, compute is measured as the total number of generations. However, one could instead measure compute as the total number of tokens generated. If compute were defined in terms of token usage rather than completions, the relative advantage of RS could change. In particular, BoN may appear more favorable under a token-based compute budget, since it generates a fixed number of completions of comparable length, whereas RS may generate highly variable amounts of text before accepting a sample. Have the authors thought about these directions, if this is not sound I am happy to discuss.\n\n- There is an iid assumption on the samples generated for BoN; is this pivotal in the proofs? I'm not sure this can be met in practice so it leaves me wondering if this is a drawback at all, or it doesn't matter and is just a definition.\n\n-  I guess $\\tau$ should be in [0, 1] in line 141\n\n- It feels confusing to me to say \"let the score $f$ to be fixed\"; this sounds like the score is fixed and not the verifier. Perhaps calling it the verifier as done in line 301 is better.\n\n- Does the theory depend at all if $h_F$ is not unique, i.e., there are multiple solutions to Equation (1)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- One of the main strengths of this paper is that the authors present a simple and interpretable mathematical framework for analyzing how verifier imperfections impact the effectiveness of test-time scaling. Their formulation leverages classical concepts from statistical learning theory (e.g., ROC curves, true/false positive rates), providing a clean lens through which to reason about the verifier. This contribution is valuable because it connects modern LLM sampling practices with well-established theoretical tools, which may inspire clearer definitions and analysis in future research.\n\n- Another strength is that the theoretical predictions align well with empirical results. For example, in Figure 3, the experiments on LLaMA models show the expected behavior: RS outperforms BoN under finite compute budgets, consistent with the theoretical claim that RS is more compute-efficient.\n\n- Overall, the paper offers practical guidance on how to deploy test-time scaling methods when compute is constrained. It clarifies when additional sampling is worthwhile, and when verifier limitations make further compute ineffective.", "weaknesses": "- One weakness of this paper is its clarity / organization. I think the clarity can be significantly improved by including a table of notations in the main manuscript. On the first pass, it was difficult to follow the derivations because I had to look back to recall the notation.\n\n- The theory models correctness as a binary variable (either correct or incorrect). This abstraction simplifies analysis, but it may limit applicability in settings where output quality is continuous or graded, e.g., in RL where partial correctness matters. It is unclear how the theoretical results extend to cases with non-binary reward structures or scalar score models, which are common in modern LLM evaluation and verification frameworks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4wPVbfwOWx", "reviewer": "Reviewer_RwZD", "summary": "This paper studies rejection sampling and best-of-N sampling for LLMs with imperfect verifiers. The core idea is that, for a fixed sampling budget, the performance of both methods is determined by the verifier's ROC curve and the generator's base accuracy. The authors show this theoretically and provide empirical validation on math datasets.", "questions": "- Can you verify the results on more diverse benchmarks?\n- How will a hybrid method change your conclusions? Will this hybrid method outperform both RS and BoN? Could you test it empirically?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Interesting problem, clean formalization, and clear scope that focuses on RS and BoN.\n2. The result that RS outperforms BoN with fixed average compute seems useful in practice.\n3. Empirical experiments show consistent results with theory's prediction.", "weaknesses": "1. **Limited evaluation domain**: Can the authors also consider other benchmark categories such as coding or more general QA? This is critical for evaluation whether the conclusion generalizes.\n2. **Compute metric mismatch and missing hybrid method**\n\t- The compute metric for RS is defined as an expectation, while the compute metric for BoN is defined as the deterministic N. The stopping time of  RS creates variance but the analysis optimize only the mean. Also, the experiments on MATH500 and GSM8K has a cap at 25 (line 448), which changes the RS distribution in a way not covered by the theory.\n\t- Taking a step further, it feels natural to consider a hybrid approach where BoN early-stops if a certain score threshold is reached (or RS early stops if a certain N is reached). Although the authors mention this as future work, I believe that this is a baseline much more realistic than RS without stopping.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zI4p9KIaxw", "reviewer": "Reviewer_NcCh", "summary": "This work investigates the performance of two LLM test-time scaling methods in scenarios with an imperfect verifier:  \n- Rejection Sampling (RS): generates responses sequentially until one passes verification.  \n- Best-of-N (BoN): generates N responses in parallel and selects the one with the highest verification score.  \n\nWithin a formal statistical framework, the authors rigorously show that the accuracy of either method for solving a single query under a fixed compute budget is determined precisely by the ROC curve corresponding to the generator and verifier.\n  \nHigh-level takeaways from the analysis include:  \n1. RS outperforms BoN under fixed compute (assuming the ROC curve is concave), although both converge to the same accuracy when compute is unlimited.  \n2. For either method, high-compute accuracy cannot be reliably predicted from low-compute performance.  \n\nTheoretical findings are validated through experiments, lending further support to the results.", "questions": "See \"weaknesses\" above.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper presents a solid and well-executed contribution to the LLM research community, even though it does not introduce new algorithms. The theoretical analysis of RS and BoN is thorough and rigorous, providing fresh insights into their behaviors when given *imperfect verifiers*. The work offers practical takeaways for researchers and practitioners considering repeated sampling approaches.  \n\n*(Disclaimer: Some technical content extends beyond my core expertise, and thus I have not verified the correctness of all proofs in detail.)*", "weaknesses": "I don't see major weaknesses in this work, assuming that the theoretical analyses are correct.\n\n\nSome suggestions:\n\n- The takeaway message \"RS outperforms BoN under fixed compute\" requires the assumption that the ROC curve (for the particular query under consideration) is concave, according to Proposition 5. I think this assumption should be stated more explicitly in the abstract and introduction, otherwise the takeaway message alone could be slightly misleading. \nIn reality, there is no guarantee *a priori* that the ROC curve should be concave.\n\n- The proof for BoN's limit accuracy in Theorem 1 (which equals that of RS in Proposition 2) is quite complicated.\nOn the other hand, we might think of (or approximate) BoN in the infinite-compute limit as (1) generating many samples, (2) keeping the samples whose scores exceed $1 - \\delta$ (with $\\delta \\rightarrow 0$), (3) breaking ties and picking one of the high-score samples randomly.\nIn this case, BoN's accuracy is effectively the posterior probability that a generated sample is correct, conditioned on its score exceeding $1 - \\delta$.\nThis probability can be easily derived by the Bayes rule, and doesn't fundamentally differ from the analysis for RS.\nI wonder how far from rigor this analysis is, and whether it could offer some intuitions about Theorem 1 and the takeaway message that BoN and RS reach the same accuracy with infinite samples.\n\n- Use a notation other than $\\pi$ (Line 137) to avoid confusion with the mathematical constant $\\pi \\approx 3.14$.  \n\n- Line 373, \"Comparing with Proposition 1\": should be \"Proposition 2\".\n\n- Include and discuss more related works, which could situate this paper more clearly in the literature on LLM test-time scaling.\nExamples include [1, 2, 3] that provide theoretical analyses for different test-time scaling methods, and [4] that also investigates the limits of LLM repeated sampling when given imperfect verifiers (albeit more empirically).\n\n[1] Are More LLM Calls All You Need? Towards Scaling Laws of Compound Inference Systems (NeurIPS 2024)\n\n[2] Provable Scaling Laws for the Test-Time Compute of Large Language Models (NeurIPS 2025)\n\n[3] When More is Less: Understanding Chain-of-Thought Length in LLMs (ICLR 2025 Workshop)\n\n[4] Inference Scaling fLaws: The Limits of LLM Resampling with Imperfect Verifiers (arXiv 2024)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qB6xrcKpst", "reviewer": "Reviewer_WUvv", "summary": "This paper provides a theoretical and empirical analysis of how verifier imperfections influence test-time scaling methods such as Best-of-N (BoN) and Rejection Sampling (RS). It shows that the accuracy of these methods is determined by the geometry of the verifier’s ROC curve, rather than by specific implementation details. It proves that RS outperforms BoN for fixed compute budgets and that both converge to the same accuracy as compute increases. The authors validate these findings empirically using Qwen and LLaMA models on GSM8K and MATH500, confirming that high-compute performance cannot be extrapolated from low-compute behavior.", "questions": "See in weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides a theoretical understanding for resampling-based inference-time compute scaling, a timely and important topic in the era.\n2. The analysis connects verifier imperfection to scaling behavior via the ROC curve. The link between ROC geometry and compute-performance scaling provides a unifying lens to reason about imperfect verifiers.\n3. The paper is well-motivated, and the structure is clear.", "weaknesses": "1. The experiments only focus on two mathematical reasoning datasets (GSM8K and MATH500), where numeric ground truths simplify verification. I wonder whether the theoretical insights generalize to other reasoning datasets (e.g., commonsense reasoning) or open-ended generation (e.g., summarization, dialogue) or code generation.\n2. Although the paper briefly discusses connections to RL (Appendix C.1), it doesn’t empirically test and validate these hypotheses. A comparison to small-scale RL fine-tuning (e.g., DPO, PPO) would strengthen the generalization of this argument.\n3. The empirical performance curves in Figure 1 are only shown for a hand-picked example (test question 58).\n4. The paper provides no actionable method to improve verifiers or scaling strategies — it only diagnoses why scaling may fail. Especially, one of the paper's findings in the abstract is that it is \"generally impossible to predict the high-compute performance\" from low-compute observations, which is a negative result without constructive guidance on how to solve this problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)