Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimality
Authors: Arpan Mukherjee
Marcello Bullo
Debabrota Basu
Deniz Gunduz
Venue: ICLR 2026 Poster (2026)
Keywords: Test-time verification
Coverage
Approximate verifier
ROC
Primary area: foundation or frontier models, including LLMs

Abstract: While test-time scaling with verification has shown promise in improving the performance of large language models (LLMs), role of the verifier and its imperfections remain underexplored. The effect of verification manifests through interactions of three quantities: (i) the generator’s *coverage*, (ii) the verifier’s *region of convergence* (ROC), and (iii) the sampling algorithm’s *sub-optimality*. Though recent studies capture subsets of these factors, a unified framework quantifying the geometry of their interplay is missing. We frame verifiable test-time scaling as a transport problem. This characterizes the interaction of coverage, ROC, and sub-optimality, and uncovers that the sub-optimality-coverage curve exhibits three regimes. A *transport regime* — where sub-optimality increases with coverage, a *policy improvement regime* — where sub-optimality may decrease with coverage, depending on the verifier’s ROC, and a *saturation regime* — where sub-optimality plateaus, unaffected by coverage. We further propose and analyze two classes of sampling algorithms — *sequential* and *batched*, and examine how their computational complexities shape these trade-offs. Empirical results with `Qwen`, `Llama`, and `Gemma` models corroborate our theoretical findings.

Published as a conference paper at ICLR 2026
TEST-TIME VERIFICATION VIA OPTIMAL TRANSPORT: COVERAGE, ROC, & SUB-OPTIMALITY
Arpan Mukherjee', Marcello Bullo', Debabrota Basu", Deniz Günndüz'
IImeeria College London
{a mukherjees m. bul oo21, d. gunduzz ) Imperial .ac.uk "Equipe School, Université de Lille, Inria, CNRS [debabrota.ben basu @inriii..i.i..... a.ff.
ABSTRACT
While test-time scaling with verification has shown promise in improving the per- formance large language models (LLMs), role of the verifier and its imperfec- tions remain underexplored. The effect of verification manifests through interac- tions of three quantities: (i) the generator's coverage, (ii) the verifier's region of convergence (ROC), and (iii) the sampling algorithm's sub-optimality. Though re- cent studies capture subsets of these factors, a unified framework quantifying the geometry of their interplay is missing. We frame verifiable test-time scaling as transport problem. This characterizes the interaction of coverage, ROC, and sub- optimality, and uncovers that the cooptiiaaltyy-overraae regimes. A transport regime where sub-optimality increases with coverage, a policy improvement regime where sub-optimality may decrease with coverage. depending on the verifier's ' ROC, and saturation regime where sub-optimality plateaus, unaffected by coverage. We further propose and analyze two classes of sampling algorithms- sequential and batched, and examine how their computa- tional complexities shape these trade-offs. Empirical results with Qwen, Llama, and Gemma models corroborate our theoretical findings.
curve exhibits three
MOTIVATIONS & CONTRIBUTIONS
Test-time scaling has emerged as a promising axis for improving the performance large language models (LLMs) (Jaech al., 2024). Existing approaches for test-time scaling are generally cate- gorized as verifier-free and verifier-based (details in Appendix A). Verifier-based methods leverage verifiers binary reward mechanisms grounded in de facto correctness criteria (e.g., unit tests, gold solutions). These verifiers have widely shown potential to improve post-training performance while used both training and inference phases (Cobbe al., 2021; Guo al., 2025; Luo et al., 2025; Huang et al., 2025a; Dorner et al., 2025).
Typical verifier-based test-time pipelines consist of a generator (the reference LLM), verifier, and sampling algorithm (e.g., Best-of-N (BoN) (Aminian et al., 2025)). Performance of the generated responses (e.g., accuracy for objective tasks) results from the combined attributes of each of these components. Following rapid empirical progress, efforts have been made to uncover the theoreti- cal underpinnings of test-time verification, specifically its aggregate scaling laws such as passuN performance (Brown et al., 2024) and policy divergence (Beirami et al., 2024). A majority of these studies assume an accurate verifier, a simplifying assumption which seldom satisfied in practice. While recent studies investigate these imperfections (Huang al., 2025a; Dorner et al., 2025), unified perspective that elucidates the interactions between the components' characteristios and ver- ification inaccuracy missing. Motivated by this gap, we ask the following overarching question:
To what extent can verifier-based sampling approximate the induced optimal policy, and how the approximations shaped by verification inaccuracies?
Addressing these questions requires moving beyond the asymptotic scaling curves, and towards a finer-grained analysis that captures the exact dependence of performance the generator, the ver-

---

Published as a conference paper at ICLR 2026
0.68
Pl
S
Sub Sub-optimality
Optimal Tranpont Cosa (OTC)
Ta
Tee
π
0.35
8
1
OTC
SubOpt
f
Coverage (3 - 1)
J
Figure 1: Regimes of test-time verification.
Figure 2: Geometry test-time verification.
ifier, and the sampling algorithm. this paper, we study the interplay between the generator's coverage, the verifier's region of convergence (ROC), and the sampling algorithm's 's sub-optimality through an exact analysis. We formulate test-time verification as sampling problem. Given gen- erative access to proposal distribution μ., we are tasked with sampling from target distribution v². The only access we have to the target distribution is through an approximately correct verifier 7, assuming de facto ground truth r" In this context, make the following contributions:
I. Framework. By recognizing test-time verification as a sampling problem, we study it through the lens of optimal transport. Here, the goal is to transport the proposal distribution μ of the reference LLM to a target distribution v*, defined by the ground-truth verifier r*. Since D² is not directly accessible, we instead rely on discriminative access via imperfect verifier 7 to guide sampling. If the algorithm accepts proposals too generously, the induced distribution remains close to p. leading high sub-optimality. Conversely, it applies an overly stringent rejection policy and discards most proposals, sub-optimality may shrink, albeit at the cost of an excessive compute budget. The key challenge to design a transport plan that balances proposal usage against induced sub-optimality.
II. Geometry of sub-optimality vs. coverage. We decompose sub-optimality into (i) an opti- mal transport cost, capturing the intrinsic difficulty of transporting the proposal distribution μ to the target v², and (ii) policy improvement term, reflecting how the sampling algorithm mitigates this cost. Sampling directly from v" achieves policy improvement exactly matching the transport cost, and yielding optimal sampling scheme. In practice. however, verifier inaccuracies render this ideal infeasible, and sub-optimality is governed jointly by the verifier's is ROC, particularly, its Youden's index, and the generator's is coverage. Our analysis reveals that as coverage constraints relaxed, the sub-optimality -ooeeaa coverage curve exhibits three distinct regimes, as depicted in Figure 1:
1. Transport regime, where the optimal transport cost dominates policy improvement;
2. Policy improvement regime, where the optimal transport cost saturates and a sufficiently accurate verifier enables sub-optimality reduction;
3. Saturation regime, where both terms plateau, leaving sub-optimality constant regardless of further coverage.
III. Algorithms and their properties. We study two protocols: sequential generation protocol, where responses are generated until acceptance, and a batched generation protocol, where a batch of responses is drawn, and the algorithm distills winning response. In the sequential protocol, revisit the naïve accept-if-correct (AiC) strategy analyzed by Dorner et al. (2025)* and show that AiC violates our coverage constraint in the transport regime. To address this limitation, we propose sequential rejection sampling (SRS), a valid transport plan for which we derive exact sub-optimality. In addition, reduce the number of proposals, we introduce sequential maximal coupling (SMC), which minimizes transport cost and achieves the same sub- aub-optimality as SRS. Surprisingly, despite being derived from different principles, SRS and SMC require the same expected number of pro- posals. Table summarizes the properties of AiC, SRS, and SMC. Finally, to account for batched generation schemes such as BoN sampling, we investigate batched variants of SRS and BoN. Our analyses and empirical studies² reveal that rejection sampling-tye algorithms are better suited to low-coverage regimes, whereas BoN-type algorithms are preferable under relaxed coverage.
Dorner et al. (2025) refer to this strategy as rejection sampling. Our analysis, however, distinguishes rejection sampling from AiC, motivating our separate nomenclature. "The code is available at httpp:///// / // thub. com/narcel obul o ottotrreeee resammpppp ing.
2

---

Published as a conference paper at ICLR 2026
Sequential
Batched
Metries
AiC
SRS
SMC
BoN
BRS
Coverage
PI, S
PI,
T, PI, (1Am
PI,
T, PI, S
Computational
(1Am( 1)
N ++1
N +1
complexity
(Thm. 3.2)
(Thm. 3.5)
(Thm. 3.5)
Sub-optimality
OTC (1 (Thm. 3.2)
OTC ou (1hm, 3.6)
OTC (1 (Thm. 3.6)
Thm. O.1
Thm. 0.2
Table I: Complexity and sub-optimality across algorithms. OTC is the optimal transport cost, &ver the generator's mass on the verifier set, m( is the induced optimal policy's mass on that set, is Youden's index, A E (T, SJ, with T= transport, PI = policy improvement, S saturation.
FORMULATION: TEST-TIME VERIFICATION AS A TRANSPORT PLAN
Let X' be the space of prompts. 3 Each prompt E X' admits response E Y generated by a reference LLM with conditional kernel Tyoe( (- x). For generality, we assume y is a Polish space equipped with a Borel o-algebra B()). The induced reference distribution over responses P law(Y X x). Test-time verification assumes existence of ground-truth verifier r" X x xx {0, 1} that assigns a binary reward to each (prompt, response) pair. Specifically, we model verification as set-membership problem, i.e., for each prompt X, there exists set of correct responses S (x) S Y, and the verifier asserts membership via rx(xx) & 1 (x))) (*(x abstracts different verifier designs depending on the task. For example, in coding problem, (*(x) corresponds to all programs that pass the unit tests. For a math problem, it represents all solutions that yield a correct final answer, possibly attained by different reasoning steps or expressed in different yet mathematically equivalent forms. When using LLM-as-a judgeee--ddde. S (x) contains the of responses with scores exceeding a predetermined threshold characterizing the de facto ground truth. Since all notations implicitly depend on the prompt we omit this dependency for brevity whenever unambiguous from the context.
Coverage and optimal policy. Test-time verification is sampling problem, where the goal is to sample from a target distribution that maximizes the average reward obtained from verifier. However, it is unrealistic to define an optimal policy that may arbitrarily deviate from the genera- tor, since responses from such an optimal policy might not be generatable via sampling from the reference policy. Hence, following the state-of-te ofte-offthheart (Huang et al., 2025a), adopt & ty-y coverage constraint on the class optimal policies. Specifically, we constrain the optimal policy to belong of policies, which sufficiently covered by the reference LLM,, i.e.
x) x)
II(B x) A x( A()) | Ex
S 3
(I)
Trof
where A())) denotes the space of Borel probability measures on y. Note that (1) implies that x² (mllv) < B - for any measure (induced by т), where (H(l))) & Jy (
denotes the x2 divvieegee between measures f and vA. We overload the notation II(3 x) to denote both the set of conditional kernels and the set of induced probability measures satisfying the constraint. Hence, the optimal policy is π (- x) E arg argsupxent(3 x) Eywntt (x)) [x) and the corre- sponding measure is 1/* & law (Z X x), where Z ~ x²(- x). Next, leveraging the binary structure of the verifier's reward, we obtain a closed-form expression for the induced optimal policy.
Theorem 2.1 (Analytical Form of Optimal Policy). For any (prompt, response) pair (x,y) X y. let r(x,y) y) A 1 E S,(x) be a verifier, where S,(x) S V. Further, let Vi & arg angsupwentp x) f (xx, (x)) denote the induced optimal measure. The Radon-Nikodym
We use Z, and denote random vector, its realization, and set, respectively.
'Note that the x2 -iveergeeee is more stringent, as it upper bounds several commonly used divergences, in- cluding the order-2 Rényi divergence, the 1-Wasserstein distance, and the Kullback-Leible divergence. Con- sequently, if constraint holds x -iveerggeee,, also holds for each of these divergences.
3

---

Published as a conference paper at ICLR 2026
Y1
prompt
response
prompt
G
x
y
2
X
Z
YN+1
resample
Figure 3: Sequential (left) and batched (right) sampling protocols of test-time verification with generator G and a verifier (light purple box).
derivative of the target measure with respect to the reference μs, denoted by dr
due is dp
ma(e.)
if y E Sr,
(y)
( V
1-ma(se) 1-8r
if y $ S,,
where ma(s) 2 8 8) - 1), and 8, - Ss. rdu.
Sampling as a transport problem. We now cast sampling as a transport problem. Given gener- ative access to jr, the goal of a sampling algorithm is to obtain samples from v² by formalizing a valid transport plan that M(,, v) between the reference and any target as the set of all joint measures on ) x ) such that its projections on the first and second coordinates are μ and v, respectively. For any coupling p(dy, dz) MM,, v). we assign the Hamming cost the price be paid for transporting μ through p. i.e., C(p) & Jyxy 1 * p(dy dz). The average Hamming cost captures the fraction of rejections required sample from the target and hence, comes up natural candidate for the transport cost. A sampling algorithm 2 is characterized by a coupling Pa(dy, dz) such that its projection the first coordinate yields the reference law 14, and define Vg, the projection of p on the second coordinate. In order to capture the efficiency of the sampling algorithm in generating from the optimal policy v*, adopt the notion of sub-optimality that assesses the change in policy performance of RL pre- and post-training (Zhu et al., 2023; Huang et al., 2025a):
coupling between f and v². We define the set of all couplings
SubOpt(21) & / (x(xx)))
) du" (y |
f (x. y) du (y x).
(3)
It immediately follows that any transport plan p(dy, dz) E _M(H, v²) is optimal. The challenge, as depicted Figure 2, is that we do not have access to v*. but only membership access to an approximately correct verifier F y y 1), such that for any response Y Toot(: x) generated for prompt x E X, an approximately correct reward signal f(x,y) = 1 & 8) available to the sampling algorithm for some S C y. The optimal policy, which lies within a x2- ball of radius 3 from Tret, induces the maximal reward the manifold induced by r-. Given access to F, the sampling algorithm's 's distribution Pa should also satisfy the -cnnstrain. Naturally, the approximation quality of the verifier should affect the sampling performance. To formalize this, we define the true positive rate (TPR), false positive rate (FPR), and Youden's index J (Youden, 1950) of the imperfect verifier
TPR A m(Sns), FPR A
1 and J TPR FPR.
1- 8,-
These are the standard quantifiers of the goodness of binary classifiers (Kumari & Srivastava, 2017; Santos et al., 2019), or equivalently, the power of binary hypothesis tests (Li & Tong, 2020).
3 ALGORITHMS & ANALYSIS: SEQUENTIAL AND BATCHED SAMPLING
We study different rest-time verification algorithms as transport plans, and analyze their properties. Depending on how the sampling algorithm interacts with the generator, we study the sequential and batched protocols, as illustrated in Figure and detailed below:
Sequential sampling protocol: Generation is modeled as a sequential decision process. Given a prompt X, each round E N, the generator produces response Y, Teee(: x). The
4

---

Published as a conference paper at ICLR 2026
sampling algorithm 21 observes the history Y - (YI...., Y,) )", and based verifier feedback, issues a decision 6% ) + faccept, reject). If a response is accepted, the algorithm stops and outputs it. Otherwise, it queries the generator for another sample. The instant which ry stops sampling is referred as the stopping time, Ta - inf {n E N (Y*))
accept).
Batched sampling protocol: the batched setting, following Huang et al. (2025a), the generator produces N + 1 independent responses in parallel. The sampling algorithm inspects any N of them, using the verifier to identify candidate. If none are accepted, the algorithm defaults to returning any one of the (N++ + 1) responses.
To evaluate sampling algorithms, we consider two key metrics: the number of proposals (compu- tational efficiency), and the algorithm's sub-optimality (performance efficiency). In the sequential setting, the computational efficiency is measured by the expected number of proposals E[ra]] while the sub-optimality is defined as in Equation (3). There is natural tension between these objectives: drawing more samples may reduce sub-optimality, albeit at the expense larger computation. In the batched setting, the computational budget is fixed at N W+1 samples. Hence, performance is eval- uated solely through sub-optimality. In what follows, we introduce a range of sampling algorithms under both protocols and analyze their performance with respect these metrics.
3.1 SEQUENTIAL SAMPLING ALGORITHMS: AIC, SRS, AND SMC
We present three algorithms for sequential protocol: (1) naïve AiC algorithm asserting membership of the generated response through the approximate verifier, (2) an SRS algorithm which has a mech- anism of accepting a sample even if its set-membership assertion fails, and (3) SMC algorithm derived by optimizing the transport cost. For brevity, we defer the pseudo-codes to Appendix B.
Central to analyzing these algorithms is the optimal (Hamming) transport cost (OTC), which is the minimum probability of rejections required to transport the reference law to the target v², and is defined as OTC - minpeM((p..)) C(p). The following lemma provides a closed-form for OTC.
Lemma 3.1 (Optimal Transport Cost (OTC) for Hamming distance). Given Hamming cost 2) & 1 (y $ 2), the OTC for Hamming distance is OTC(3) = (1 A ma( -ppt.
3.1.1 ACCEPT-IF-CORRECT (AIC)
The AiC algorithm (Algorithm 1). proposed by (Dorner et al., 2025) is an extension of the BoN sam- pling strategy to the sequential setting. Given the (approximate) verifier through the met-memhership oracle S, each time n E N, AiC samples a response Y, ~ μ4, asserts its membership S, and resamples if the assertion fails. Noticeably, AiC ignores the policy coverage bound B, resulting in constraint violation certain coverage regimes. In the following theorem, we characterize the average number of proposals and sub-optimality of AiC.
Theorem 3.2 (Computational complexity and sub-optimality of AiC). Let Sver 2 8, TPR + (1 s, FPR denote the verifier acceptance probability. The expected computational complexity of AiC is E TTCC = 1/swee and its sub-optimality is given by
(TT(3)) (1 OTC(3) (1-
Spp
:J)..)))
-J)
if B 1
SubOOt(AiC)
Ever
1
(1-
J). B
3 1
Theorem 3.2 shows that AiC's sub-optimality depends linearly on (a) the OTC, and (b) Youden's index J. A smaller Youden's ' index, corresponding to verifier closer to random guessing, yields higher sub-optimality. Since AiC ignores the coverage constraint, its sub-optimality not compara- ble uniformly over all coverage regimes. As evident from the next theorem, AiC fails to satisfy the coverage requirement low-coverage regimes, thereby incurring constraint violations.
Theorem 3.3 (Constraint violation of AiC), Given any prompt x E X, AIC policy Ticc( xx) does not satisfy the coverage constraint for 3 < 1/8yer, Le,, TACC x) & TT(3 x) for all B 1/ Sver.
5

---

Published as a conference paper at ICLR 2026
3.1.2 SEQUENTIAL REJECTION SAMPLING (SRS)
To circumvent AiC's lack of coverage, we propose a rejection sampling (RS)-based algorithm (Al- gorithm 2), which is aware of the coverage constraint.
Canonical RS (Forsythe, 1972; Neal, 2003) evaluates a scaled likelihood ratio against a uniform ran- dom variable to determine sample acceptance, essentially flipping Bermoulli coin where the scaling factor, known as the envelope, dictates the acceptance probability. However, our context lacks the tiget-to-proposse likelihood ratio "/,,, since S* is unknown and the sampling algorithm only has access to approximate membership oracle S. We therefore introduce SRS, which substitutes mi, obtained by replacing 8,, in Equation (2) with Sy. While Sp is computable in principle, it may not be accessible at test time. In Section 4, we treat s as tunable hyperparameter with ablations across multiple models. Our theoretical analyses, however, assume that sp, the reference policy's 's proba- bility mass on the verifier's set S, is available to the sampling algorithm. While seemingly strong, this assumption enables a fundamental characterization of how the verifier's ROC influences sub- optimality. Note that by our construction, SRS always satisfies the coverage constraint. Performance analysis of SRS is presented jointly with our next algorithm, SMC, to facilitate direct comparison and maintain brevity.
3.1.3 SEQUENTIAL MAXIMAL COUPLING (SMC)
Maximal coupling (MC) (Algorithm 3) is a canonical technique for constructing optimal transport maps (Den Hollander, 2012). The goal is to find joint distribution p that minimizes the transport cost, i.e., p² E arg min pEMieEM C(p). Under the Hamming cost, this amounts to minimizing the rejection probability, suggesting the potential to improve computational efficiency. The MC algorithm in this setting is well studied: the generator first produces sample, which is evaluated by the sampling algorithm. The algorithm compares the likelihood ratio at this sample against a uniform random draw. If the ratio exceeds the threshold, the sample is accepted. Otherwise, MC samples from residual measure as a correction. Consequently, MC requires at most two proposals to produce a valid sample from the target distribution.
In the test-time setting, however, the sampling algorithm lacks access to samples from the residual measure, making a direct application of MC infeasible. Nevertheless, we identify an alternative representation of the residual that is generatable, as formalized in the following lemma.
Lemma 3.4 (Residual measure). Given a proposal measure p. and a target measure on y induced by a verifiable reward r with a membership oracle S, the residual distribution for MC, defined as
Mrres 2 (v- (W)A)))/11 (D)), can be equivalently characterized as pres = p(- S), where we have defined the conditional measure pl- S) _ p(- (S-))))
Leveraging Lemma 3.4, we now extend canonical MC to sequential protocol, and propose SMC. We start similarly to MC, i.e., drawing a response and a uniform number, and then comparing the likelihood ratio of the obtained sample the uniform random realization. If the ratio exceeds the uniform number, SMC accepts the sample. Otherwise, SMC keeps drawing samples from until the generated sample asserts the set-membership verification rather than sampling from the residual. Evidently, not having access to a residual measure incurs a computational price to mimic sampling from the target measure. the following theorem, we characterize the computational complexities of both SRS and SMC algorithms, and find that they require the same average number of proposals.
Theorem 3.5 (Computational complexity of SRS and SMC). Let M A max {122. 1 A me(scu))) 8ver
(0 V 1=ma((vvr) }} for SRS. For both algorithms A SMC), the computational complexity I-Sver is identical, and given by E[ra]] = 1011111111 A m)g(Sver)
Note that the computational complexity of SRS and SMC improves upon AIC by a factor of M.(Sver). Under liberal coverage constraints, where m = 1, their complexity coincides with that of AiC. In contrast, under more stringent coverage, SRS and SMC achieve a compu- tational speed-up over AiC. Next, we provide SRS and SMC sub-optimality. and find that both sub-optimalities follow a piecewise curve divided into three distinct regimes.
Theorem 3.6 (Sub-optimality of SRS& & SMC). Sub-optimalities of SRS and SMC are expressed as SubOpt(2I) = ОTC(3)- (1- aJ))
where & (SRS, SMC), and a varies depending on the coverage constraint B as follows:

---

Published as a conference paper at ICLR 2026
1. Transport regime 3
<
) we have
Sye (1=pe))
Boer)
2. Policy Improvement regime
we have
Ayer
Sver
1 Sver
Syt (1 (1-
if Sver > 8p 3 E
1
B-1
Sver
8y*
B-1 Svar
Sver 8pa, 3
8,
ovar
3. Saturation regime 8
we have
Ayer"
Theorem 3.6 reveals three distinct regimes. In the transport regime, sub-optimality grows O(v and is fully governed by OTC(3). In the policy improvement regime, if 8ver S. 8,, and Youden's index positive, the policy reduces sub-optimality. By contrast, Sver 2 8,, admits false positives and yields no improvement. In the saturation regime, OTC(3) stabilizes at 1 - Sy*, and hence, sub-optimality remains constant despite increasing coverage.
Theorems 3.5 and 3.6 collectively establish that SMC, despite its design, is no more computationally efficient than SRS, as the lack of residual access offsets potential gains. Thus, SRS and SMC exhibit equivalent performance in both computational complexity and sub-optimality. Theorems 3.2 and 3.3 show that AiC violates constraints the transport regime, while matches SRS and SMC in the saturation regime, supporting their use under liberal coverage. Finally, while Huang et al. (2025a) report sub-optimality scaling with the square root of coverage, our analysis refines this observation: the trade-off between the coverage and the sub-optimality universal but mediated by the verifier's 's ROC.
3.2 BATCHED SAMPLING ALGORITHMS: BON AND BRS
In this section, analyze BoN, characterizing its sub-optimality and identifying the maximal batch size N+1 beyond which constraint violations occur. We then introduce a batched variant of rejection sampling (BRS), and establish that satisfies coverage constraints for all batch sizes. For our analysis, we focus on accurate verifiers; extension to approximately correct verifiers is deferred to Appendix
3.2.1 BEST-OF-N (BoN)
Given prompt E X, BoN obtains independent and identically distributed (iid) responses N+1 A (y1,... .Y++1) from the proposal μ.. Subsequently, it returns response 2(N) e K. A {y E y.V y V S*) uniformly random, where S* denotes the ground-truth membership oracle accessible to BoN. Unlike the sequential protocol, batched sampling with an accurate verifier does not guarantee zero sub-optimality, as the algorithm is restricted to selecting from only N ++1 samples, which may fail to adequately represent the target distribution. Therefore, begin by deriving sufficient condition on the to ensure coverage.
Theorem 3.7 (Maximum admissible batch size of BoN), Let VBON denote the sampling distribution induced by BoN with access to the ground-truth membership oracle St. Then uBoN satisfies the coverage constraint, i.e., MBON E 11(3 x), only if N I [N |max!, where
00
if
B B
(1- sy. 3/5
N max
In
(B 1)8p. (1 8y )-
if
1 E
8 1 (1 - )/S
In(1 - sp*)
We observe that for conservative choices of coverage, BoN admits maximal batch size. On the other hand, beyond necessary minimum coverage, the maximum number of samples an increas- ing function of B, and becomes unbounded (as the -ivdeerree saturates) beyond -- Next, we state the sub-optimality of BoN as a function of N.
Theorem 3.8 (Sub-optimality of BoN). The sub-optimality of the BoN algorithu with access the ground truth membership oracle S* SubOpt (BoN)
8y, N+1 -O -ma(s-)))

---

Published as a conference paper at ICLR 2026
From Theorem 3.8, as N' increases, BoN sub-optimality decreases. However, Theorem 3.7 shows that N cannot grow arbitrarily without inducing constraint violations. For small 3. BoN may even outperform the skyline, whose mass on S* can be strictly less than resulting in negative sub- optimality, albeit at the cost of violating the coverage constraint. More generally, combining Theo- rems 3.7 and 3.8, find that for large [3 the batch size N can be chosen freely, yielding vanishing sub-optimality. In contrast, for intermediate B, restricting N to its maximal admissible value leads to sub-optimality equal to ( 1)8,+ /(1 8y.)
(0 V 1 mg(s,-))
3.2.2 BATCHEE REJECTION SAMPLING (BRS)
Motivated by the infeasibility and constant sub-optimality of BoN in low-coverage regimes, extend our SRS algorithm to the batched setting, which we call BRS (Algorithm 4). BRS follows the same principles as SRS, with the key distinction that generation is truncated after N+1 samples. A batch N drawn in parallel, and rejection sampling is applied to any N of these samples. If none are accepted, the (N + 1)th sample is returned as a fallback. Unlike SRS, however, BRS is not a valid transport plan with respect to a target measure defined by reward r, and thus, incurs sub-optimality even when the tround-truth membership oracle is available. Now, we first show that BRS satisfies the coverage constraint for all N, allowing batch sizes to be chosen freely based on hardware capacity. We then analyze its sub-optimality establishing that it vanishes N increases.
Theorem 3.9 (Batch size BRS). Let VBns be the sampling distribution of the BRS algorithm induced by the ground truth membership oracle St. For any prompt E X and N E N, we have VBRS E [ x).
Theorem 3.10 (Sub-optimality BRS). The sub-optimality of the BRS algorithm with access to the ground truth membership oracle S* is given by
SubOpt(BRS) = OTC(3) (1
1 N M
We observe that the sub-optimality of BRS decays exponentially in the batch size. Furthermore, setting its envelope to its tightest value M OTC(3) N+1 (s, )ー, and it scales exponentially in OTC. This provably shows an improvement in the performance of BRS compared to BoN in the intermediate and low coverage regimes.
m_(s.")) ) we observe that the sub-optimality is
e,*
4 EXPERIMENTAL ANALYSIS
Our empirical study is guided by two central questions:
1. To what extent do the empirical sub-optimality curves align with the three-regimes of theoretical predictions?
How sensitive are the algorithms to misspecification of the coverage parameter Sver used by the algorithms relative to the (unknown) true mass?
We pivot our empirical results on two key performance metrics, sub-optimality and computational complexity. For both metrics, we sweep the coverage budget 3 over grid spanning the three regimes highlighted by the theory (transport, policy improvement, and saturation). Additionally, for the batched setting, we sweep over the batch size N +.. We summarize the key empirical findings in this section, while deferring experimental setup details, construction of ground truth and approximately correct verifiers, and additional results to Appendix P. All curves are averaged over 5,000 episodes, with each algorithm run independently in each episode.
Sub-optimality. In sequential protocol, the sub-optimality curves for SRS and SMC in Figure 4 follow the characteristic three-regime geometry predicted by the analysis. In the small-coverage regime, sub-optimality increases as ((V3) and exhibits little policy improvement. As 3 grows, the curves bend downward in proportion to the informativeness the verifier (larger J), and finally, plateau level determined by s,, and J. In contrast, AiC aligns with the other methods only under the saturation regime, and otherwise, exhibits constraint violations. The three methods converge in the saturation regimes, achieving the same performance. Varying the model scale primarily shifts
8

---

Published as a conference paper at ICLR 2026
Qwen3-1.78
Qwen3-14B
Qwen3-1.78
Qwen3-14B
Algorithm x
SRS
Sub0ptre)
0.20
0.20
Computationa
Comploxity
0.15
0.15
AC
Theory
0.10
0.10
0.05
0.05
2
2
Verifier
0.00
0.00
10
2
2.5
5.0
7.5
B
B
B
Figure 4: Sub-optimality (left) and computational complexity (right) as functions of 8 for Qwen3-1- 7B and Qwen3-14B. Results are shown for SRS. stochastic SMC, and AiC. Solid green lines denote theoretical predictions as stated in Theorem 3.6. Background shading indicates differ- ent coverage regimes, and confidence intervals are shown as shaded bands.
Qwen3-14B
Qwen3-14B
Qwen3-144 twenn-14BBB V²
Qwen3 14B -
1.0
0.1
0.7
SubOp(BRS]
0.4
0.8
Re-ward
0.8
0.3
0.8
0.9
0.6
1.0
0.0
Estimated Theory
0.4
0.4
0.6
AIC
0.2
SMC
2
2
2
Figure 5: Sub-optimality for Qwen3-14h of BRS and BoN with imperfect verifiers (left), and ablation study (sensitivity) for SRS, SMC, and AiC (right).
the saturation level. Larger Qwen models yield higher s,, (stronger base accuracy) and therefore lower residual sub-optimality.
Computational complexity. The premise of our experiments in Figure 4 comprises smaller Sver compared to s, consequently, we observe that the computational complexity with the approximate verifier (saturating at 8 proposals on average for Qwen3-1.. 7B) exceeds the complexity required by the ground truth verifier (saturating at RV 6 proposal on average for 3 In general, computational complexity for SRS and SMC are identical and scale as 0(vB) before saturating, while AiC has constant computational complexity as stated in Theorem 3.2.
In the batched protocol, we present a comparison of the sub-optimality of both BRS and BoN under imperfect verifiers in Figure 5 (left), with additional details provided in Appendix O. The sub- optimality is evaluated as function of across varying batch sizes N S Nmax. Theoretical predictions closely align with empirical results obtained using 3wen3- 3-eBB. As predicted by The- orems 0.1 and O.2, the sub-optimality decreases with increasing N the presence of imperfect verifiers, reflecting the expected improvement with larger batches.
Sensitivity to Sver- Since sver is typically unavailable in real-world settings, we conduct an ablation study by setting Sver reward obtained by the algorithms when a value s selected from the set shown in the legend is used instead of the one induced by the verifier under examination. Each curve corresponds different assumed value of 8, and illustrates how mismatched assumptions about verifier accuracy affect the reward. Interestingly, when is because (i) RS envelope becomes M = 1. Thus, the first check in SMC becomes identical to the SRS acceptance condition. (ii) The Radon-Nikk Madon-Nikodym derivative function becomes (y( 1 e S,} Thus, for s 1, all methods restrict support to S,, and behave identically. as reflected in the overlapping curves that point. Also, an interesting pattern emerges when comparing SRS and SMC across different assumed values of Specifically, the two methods exhibit matching performance when s is aligned with the true verifier accuracy, i.e., at = 0.31 in ground truth case, and x = 0.27 when using the approximate verifier. Notably, SMC underperforms relative to SRS when the assumed s is smaller than the true value (s < 0.31 or s < 0.27), and outperforms SRS 0.27). This crossover behavior illustrates the
for various choices of s. The two rightmost plots in Figure 5 show the
all three algorithms reduce the AiC algorithm. This
when the assumed is greater (s 0.31 sensitivity of SMC to over- or under-esting estimaanti verifier accuracy, and highlights that SMC may be advantageous in high-s regimes, whereas SRS is more robust when verifier confidence is low.

---

Published as a conference paper at ICLR 2026
5 CONCLUSION AND FUTURE WORKS
We cast test-time verification through the lens of optimal transport. By positing it sampling problem, we analyzed how generator's coverage, verifier's s accuracy, and sampling algorithms jointly determine sub-optimality and computational complexity. Our analysis, supported by empirical evi- dence, reveals a Ohree-regime structure in the where sub-optimality is dominated by transport cost; a policy-improvement regime, where sampling can counteract transport cost depending on the verifier's ROC; and a saturation regime, where sub- optimality plateaus at level dictated by the verifier's Youden's 's index. These dynamics are exhibited by both the sequential and batched algorithms studied. Notably, rejection sampling-tyy -type methods are advantageous under low coverage, while best-of-N approaches excel under liberal coverage.
apptimalitt-covereee
tradeoff: a transport regime,
Future Works. Our study also raises several open questions. Analytically, extending from ratio- based to difference-basee based coverage remains unexplored. More broadly, moving beyond verifiable rewards toward general reward models for inference- time alignment is an important next step. Fi- nally, our premise highlights a fundamental open problem in sampling: how can we sample from target distribution given only proposals, when the target-to- porerposl- likelihood ratio is partially or fully unknown and must be estimated from samples? We conjecture that any such algorithm must explicitly balance exploration, i.e., estimating the likelihood ratio with sufficient confidence, against exploitation, i.e., using the estimate to make acceptance or stopping decisions.
ACKNOWLEDGMENTS
This work received funding from the SNS JU project 6G-GOALS under the EU's Horizon program Grant Agreement No. 101 139232; and by the INFORMED-AI Hub under Grant EP/YY22732/11 D. Basu acknowledges the ANR JCJC project REPUBLIC (ANR-22- CE23--003--)), PEPR project FOUNDRY (ANR23-PEIA-0003)) and Inria-ISI Kolkata associate team SeRAI for support.
REFERENCES
Gholamali Aminian, Idan Shenfeld, Amir R Asadi, Ahmad Beirami, and Youssef Mrouch. Best-of-N through the smoothing lens: KI. divergene and regret analysis. arXiv preprint arXiv:2507.05911, 2025.
Ahmad Beirami, Alekh Agarwal, Jonathan Berant, Alexander D' Amour, Jacob Eisenstein, Chirag Nagpal, and Ananda Theertha Suresh. Theoretical guarantees on the best-of-n alignment policy. arXiv preprint arXiv:2401.01873 2024.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787 2024.
Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, fcan-Baptise Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.013/8, 2023.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Rejichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. 14168, 2021.
Frank Den Hollander. Probability theory: The coupling method. Lecture notes available online (http://websites. math. leidenuniv. httprrwwwitttltttteeeee///o/oigp
pdf). 3, 2012.
Florian E. Dorner, Yatong Chen, André F. Cruz, and Fanny Yang. Roc-n-reroll: How verifier imper- org/ abs/2507. 12399.
fection affects test-time scaling, 2025. URL
George E. Forsythe. Von neumann's comparison method for random sampling from the normal and other distributions. Mathematics of Computation, 26(120):8178226 1972. ISSN 00255718, 10886842, URL http:://///etttt jator, org/ /20058
10

---

Published as a conference paper at ICLR 2026
Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman. Stream of search (sos): Learning to search in language. arXiv preprint 17XXi:2400403683,, 2024.
Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Fos- ter. Laurence Golding, Jeffrey Hsu, Alain Le Noac'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. URL https: zenodo. org records
Daya Guo, Dejian Yang. Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv preprint arXiv:2501. 2025.
Chaoqun He, Renjie Luo, Yuzhuo Bai, Shengding Hu, Zhen Thai, Junhao Shen, Jinyi Hu, Xu Han, Yujie Huang, Yuxiang Zhang, et al. Olympiadbench: A challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp- 3828 3828-3850, 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 Thirty-fifth Conference Neural Information Processing Systems Datasets and Benchmarks Track (Round 2).
Cheng-Y Yu Hsieh, Chun-Liang Li, Chih-kuan Yeh, Hootan Nakhost, Yasuhisa Fujii, Alex Ratner, Ranjay Krishna, Cuen-Yu Lee, and Tomas Pfister. Distilling step-by-step! outperforming larger language models with less training data and smaller model sizes. In Anna Rogers, Jordan Boyd- Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics; ACL 2023. pp. 8003-800 8017, Toronto, Canada, July 2023. Association for Computational Linguis- tics. doi: 10. 10.18653/w1/202. findings-acl.507. URL https: http///aaaaaanttaaaaaaaaaa org//023. findings- 507/.
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 in inference-timg alignment. arXiv preprint arXiv:2503.21877 2025a.
Baihe Huang, Shanda Li, Tianhao Wu, Yiming Yang, Ameet Talwalkar, Kannan Ramchandran, Michael I Jordan, and Jiantao Jiao. Sample complexity and representation ability of test-time scaling paradigms. arXiv preprint wrXiv:256.005295 2025b.
Chengsong Huang, Langlin Huang, Jixuan Leng, Jiacheng Liu, and Jiaxin Huang. Efficient test-time scaling via self-calibration. arXiv preprint arXiv:2503.0000 2025c.
OpenAl: Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, et al. OpenAl ol system card, 2024. URL
org/abs/ /2abs//2412.. .1122.1622 16720.
Roshan Kumari and Saurabh Kr Srivastava. Machine learning: review binary classification. International Journal of Computer Applications, 160(7), 2017.
Jingyi Jessica Li and Xin Tong. Statistical hypothesis testing versus machine learning binary classi- fication: Distinctions and guidelines. Patterns, 1(7), 2020.
Baohao Liao, Yuhui Xu, Hanze Dong, Junnan Li, Christof Monz, Silvio Savarese, Doyen Sahoo, and Caiming Xiong. deward-guided speculative decoding for efficient 1lm reasoning, arXiv preprint arXiv:2501. 19324, 2025.
Ruibo Liu, Jerry Wei, Fangyu Liu, Chenglei Si, Yanzhe Zhang, Jinmeng Rao, Steven Zheng, Daiyi Peng, Diyi Yang, Denny Zhou, et al. Best practices and lessons learned on synthetic data for language models. CoRR, 2024.
11

---

Published as a conference paper at ICLR 2026
Zihan Liu, Yang Chen, Mohammad Shoeybi, Bryan Catanzaro, and Wei Ping. Acemath: Advancing frontier math reasoning with post-training and reward modeling. Findings of the Association for Computational Linguistics: ACL 2025, pp. 3993-4015, 2025.
Michael Luo, Sijun Tan, Justin Wong, Xiaoxiang Shi, William Y Tang, Manan Roongta, Colin Cai, Jeffrey Luo, Tianjun Zhang, Li Erran Li, et al. Deepscaler: Surpassing ol -preview with a 1.5 b model by scaling rl. Notion Blog. 2025.
Saumya Malik, Valentina Pyatkin, Sander Land, Jacob Morrison, Noah A. Smith, Hannaneh Ha- jishirzi, and Nathan Lambert. Rewardbench 2: Advancing reward model evaluation. https: / ///ugggingfacc.e..mmm/// cwtee.cc//ppoee wowspacessaapooooocooooooccccaaa
wewpeaaiirewwardd-eeeeeee berch, 2025.
Seungyong Moon, Bumsoo Park, and Hyun Oh Song. Guided stream of search: Learning to better search with language models via optimal path guidance. arXiv preprint arXiv:2410.029%0 2024.
Youssef Mrouch. Information theoretic guarantees for policy alignment in large language models. arXiv preprint 17Xii:2200605883,, 2024.
Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zeutlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling, arXiv preprint arXiv:2201. 190.99330119993, 2025.
Radford M Neal. Slice sampling. The annals of statistics, 31(3):705-761 2003.
Rui Santos, Miguel Felgueiras, Joao Paulo Martins, and Liliana Ferreira Liliana Ferreira. Accuracy measures for binary classification based on quantitative variable. REVSTAT-Staissicc Journal, 17(2):223-2444 2019.
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)? arXiv preprint arXiv:250..17576 2025.
Amrith Setlur, Nived Rajaraman, Sergey Levine, and Aviral Kumar. Scaling test-time compute without verification or rl is suboptimal. arXiv preprint 250. 2025.
Kimi Team, 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 lims. arXiv preprint arXiv:2501. 2025.
Pablo Villalobos, Anson Ho, Jaime Sevilla, Tamay Besiroglu, Lennart Heim, and Marius Hobbhahn. Position: Will run out of data? limits of Ilm scaling based on -emaangeeeerted data. In Forty- first International Conference on Machine Learning, 2024.
Cédric Villani et al. Optimal transport: old and new, volume 338. Springer, 2008
Yiming Wang, Pei Zhang, Siyuan Huang, Baosong Yang, Zhuosheng Zhang, Fei Huang, and Rui Wang. Sampling-efficien test-time scaling: Self-estimating the best-of-n sampling early de- coding. arXiv preprint arXiv:2503.01422, 2025.
William J Youden. Index for rating diagnostic tests. Cancer, 3(1):32-35, 1950.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman. Star: self-taught reasoner bootstrap- ping reasoning with reasoning. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc.
ISBN 1781713871088.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feed- back from pairwise or k-wise comparisons. In International Conference on Machine Learning, pp. 43037-4300 PMLR, 2023.
12

---

Published as a conference paper at ICLR 2026
Appendix
Table of Contents
A Literature Review
14
B Algorithm Pseudo-codes
16
Target-to-proposal Radon-Nikodym Derivative (Proof of Theorem 2.1)
Auxiliary Lemmas
D.1 Optimal Transport Cost (Proof of Lemma 3.1)
18
D.2 BoN Sampling Distribution
18
D.3 BRS Sampling Distribution
20
E Properties of ROC
20
F AiC Properties (Proof Theorem 3.2)
21
G AiC Constraint Violation (Proof of Theorem 3.3)
22
H SMC Residual Measure (Proof of Theorem 3.4)
22
SRS / SMC Computational Complexity (Proof of Theorem 3.5)
23
SRS SMC Sub-optimality (Proof Theorem 3.6)
K BoN Batch Size (Proof of Theorem 3.7)
25
L BoN Sub-optimality (Proof of Theorem 3.8)
26
BRS Batch Size (Proof of Theorem 3.9)
26
BRS Sub-optimality (Proof of Theorem 3.10)
Batched Sampling Algorithms with Approximate Verifiers
27
P Extended Experiments
30
P.1 GSM8K
31
P.2
MATH500 OlympiadBench
31
Q Compute and L.M Usage
13

---

Published as a conference paper at ICLR 2026
A LITERATURE REVIEW
A crucial bottleneck in pre- and post-training pipelines for large language models (LLMs) is the dwindling supply of high-quality training data, constrained by privacy, security, and cost con- cerns (Liu et al., 2024; Villalobos et al., 2024). This trend threatens saturation along the train-time scaling axis. In response to such bottlenecks in scaling laws, OpenAl introduced an alternaee axis test-time scaling- and showcased its potential through the OpenAI-ol release. This shift has delivered substantial gains across diverse benchmarks (Jaech et al., 2024). Ever since, the commu- nity has witnessed a plethora of investigations into attributes including, but not limited to, scaling laws, methodologies, trade-offs, and theoretically- grouudddd understanding of the new scaling axis. Test-time scaling is mostly realized through two approaches- verifier-free and verifier-based (Setlur et al., 2025).
Verifier-free vs. verifier-based methods. Verifier-free methods involve performing supervised fine-tuning (SFT) pre-trained LLMs with expert traces, i... high-quality step-by-step rationales that directly supervise the reasoning process. Expert traces can come from diverse sources, such as human-written or curated solutions (e.g., GSM8K (Cobbe et al., 2021)), distilled chain-of-thought (CoT) from stronger teacher models (Muennighoff et al., 2025), reasoning trajectories obtained via search procedures (Gandhi et al., 2024; Moon al., 2024), seff-hoosstrapped rationales where only correct generations are retained (Zelikman et al., 2022), and rationale distillation techniques for transferring reasoning ability across models (Hsich al., 2023). On the other hand, verifier-based methods deploy verifier, reward-signal apparatus, for guiding the response generation. Verifier assigns a binary (0 / 1) value assessing the generation quality, especially in the objective tasks such as math and coding. A verifier is construed from a domain-specific de facto ground truth, such as constructing unit tests for coding and correct solutions for mathematical tasks. Verification has been leveraged during both training (also known as reinforcement learning with verifiable rewards) (Guo et al., 2025; Luo et al., 2025; Team et al., 2025), and inference (Cobbe et al., 202 This approach has exhibited strong test-time scaling performance. Indeed, Setlur et al. (2025) show that verifier- based methods provably outperform verifier-free methods in test-time scaling.
Sequential vs. parallel compute. A complementary concern for test-time scaling methods is how they spend their test-time compute budget. The reasoning models spend their entire budget se- quentially by refining single trajectory over multiple steps curate longer and more accurate response. The sequential sampling process may be verifier-based, e.g., through process reward mod- els (Liao et al., 2025), or verifier-free (Chen et al., 2023). On the other hand, resampling methods adopt parallel compute mode by dividing its budget to generate multiple responses, and then, distilling a winning response. Popular resampling methods are verifier-based, leveraging verifier (e.g., unit tests, reward models trained on ground truth responses for objective tasks, etc.) to distill a winning response from its generations (Huang et al., 2025a; Beirami et al., 2024; Cobbe et al., 2021). The focus of this investigation is on verifier-based resampling methods. We measure com- putational complexity via the expected number of proposals, which is a hardware-agnostie quantity that arises naturally in our analysis. In practice, however, wall-clock latency also depends GPU parallelism, model size, and verifier overhead. Batched methods can exploit accelerator parallelism to evaluate many candidates simultaneously and may therefore achieve lower latency than sequen- tial methods, even when they use more total proposals. Conversely, sequential methods can continue sampling until a high-quality solution is found and typically achieve better sub-optimality for a given proposal budget, highlighting a practical tradeoff between solution quality and runtime.
Best-of-N (BoN) sampling. The most popular verifier-based test-time scaling method is BoN sam- pling (Brown et al., 2024). BoN generates N independent responses per prompt, and chooses a winner randomly from the set of correct responses deemed by a verifier. Assuming access to an ac- curate verifier, Brown et al. (2024) analyze the pass@N N metric, i.c., the average fraction of prompts with at least one correct response, and observe an approximate power-law scaling with N. Extend- ing this analysis, Schaeffer et al. (2025) establish an exponential per-instance scaling law attributing the aggregate power law to the heavy-tailed distribution over prompts. On a complementary note, Beirami et al. (2024); Mrouch (2024) analyze the deviation of the BoN alignment policy from the reference policy by computing tight
on their KL-ddieegennee Yet another characteris- tic, the sample complexity of BoN to generate correct responses for objective tasks is investigated by Huang et al. (2025b). While such scaling laws and divergence bounds are informative, they do not directly address the central goal of resampling: how well can we approximate the verifier-induced
14

---

Published as a conference paper at ICLR 2026
optimal policy that maximizes expected reward? Variations of BoN, addressing aspects such as N- estimation and adaptivity, and finding altemnte scoring mechanisms have also been explored. For instance, Wang al. (2025) truncates BoN generations based on an estimation budget formed by solving an optimization problem, showcasing computational improvement over BoN. Huang et al. (2025c) preaches why confidence score is preferable compared to reward scores, and thresholds it for "confident" test-time scaling. However, the choice of threshold is ad hoc.
Approximately correct verifiers. Most of the studies on BoN assume access an accurate ver- ifier that rarely holds in practice. For example, unit tests can miss the edge cases, and verifiers for math benchmarks often capture only a subset valid responses. fault GSM8K evaluation in -m--valuatioon-t -aronnnaaasssss (Gao et al., 2024), which extracts the many correct generations that
relevant case is the de-
first match to the pattern "The answer is (-2 thus marked incorrect. These limitations underscore the need to
deviate from this template plicitly account for verifier imperfections the design and analysis test-time scaling methods dimension largely absent from the literature. We are aware of two investigations accounting for verifier (aka reward model) imperfections in sampling algorithms. Aminian et al. (2025) analyze BoN under per-prompt mean squared error (MSE) constraint the verifier. Huang al. (2025a) adopt the same framework to show that BoN's 's average reward may fail to scale with N under lim- ited coverage, motivating a rejection sampling (RS) variant that alleviates this issue. Concurrently, Dorner et al. (2025) study test-time scaling with approximately correct verifiable rewards, charac- terizing how a verifier's region of convergence (ROC) mediates the trade-off between accuracy and compute. Our investigation complements these perspectives by focusing generator coverage and showing how coverage, together with the ROC, determines the exact sub-optimality of a sampling method, rather than only its asymptotic the difference between the average reward obtained from the verifier while using an optimal policy and that of the sampling algorithm.
profile. Here, sub-optimality is defined as
15

---

Published as a conference paper at ICLR 2026
B ALGORITHM PSEUDO-CODES
Algorithm 1: Accceptif--Corre (AiC)
Input: Prompt E X, generator (e x); verifier set S(x)
for 1, 2.... do
Sample Y, Ther( x):
Y, E S(x) then
L return Y, accept if correct
else
continue // resample
Algorithm 2: Sequential Rejection Sampling (SRS)
Input:
Prompt E A'; generator Teer( x); verifier set S(x); envelope M: 2 n(((x))) constraint 3
for 1, 1,2,... do Sample Y, ~ Tiar(: x) and u ~ Unif 1];
Compute 77 ..) by plugging 8 in (2):
Y S(x) then
L return Y, accept if verifies correct
else if 37 M)... 2 then
L return Y, // accept (incorrect) via RS to satisfy coverage
else
continue // reject and resample
Algorithm 3: Sequential Maximal Coupling (SMC)
Input: Prompt E generator Teet (: x); verifier set S(xx) 8 (((())); constraint | do Sample Y, Wzel(- x) and Unif
for
Compute ,,),,) x by plugging 3 in (2);
if if fr((Y,) 2 a then
L return Y, // accept if coverage is satisfied
1/ do not advance n: keep drawing until verified-corred while Y. & S(x) do Sample Yn Trer(- x);
return Y, // first verified-correct draw
Algorithm 4: Batched Rejection Sampling (BRS)
Input: Prompt E X:; generator Tear x); verifier set 8(x); envelope M; 3 A v(((x)): batch size 4- 1; constraint
Sample N-1 (Y....., Y N441 iidd from m.a(( x);
Draw ui...., uN+1 1n]
for 1,.., N do
Compute ?(Y,)) by plugging in (2);
Y E S(x) then
return Y, // accept it verified correct
else 1 NYY)) 2 u then
L return Y, // accept (incorrect) via RS to satisfy coverage
return Yx41 // return the last sample none accepted
16

---

Published as a conference paper at ICLR 2026
C TARGET-TO-PROPOSAL RADON-NIKODYM DERIVATIVE (PROOF OF THEOREM 2.1)
Finding the optimal policy u, is equivalently solving the following constrained optimization prob- lem.
s.t. f np nfdd du S B, and / Idd 1.
(())
max 120
ndu
S.
Let us denote the value of P(3) by m. ic., m - Ss, nr du. Using Cauchy-Schward inequality, we have
(L
2 s tp du
/ Sr
/
du
n dp
du.
S.
Sr
which yields:
f
1 m
Tr
du
(4)
8y
Similarly, from the fact that
( tr dje dr
2
/
/ dp.
n du
$
J3.
J3.
we obtain:
[
1
of dp
2
(1 m)²
(5)
S.
Sr
Combining (4) and (5), we have
B
n2 du
2
m² +
(1 m)²
Sy
1 Sr
Rearranging (6), we obtain:
m < -
Furthermore, since m the mass that the optimal measure puts on the set of correct responses S,, we have
- (1 [5A(5=111 55 -1)
Next, we will show that the upper-bound on m is tight. Specifically, we will construct a valid such that (7) holds with equality, noting that Cauchy-Schward is tight for constant functions. For some E IR and gr- R, let us set
mry)) = [Pr: YES,
(gr, y S
Since v, is a probability measure, we have
/
I 8.
17. du
mr nu
77. dp pr. +q. (1s)))
sr)
(8)
S.
From (8) we have
m
1 m
Pr
and
gr
Sr
Sp
The proof concludes by setting
( 87 1) 8r)-
17

---

Published as a conference paper at ICLR 2026
D AUXILIARY LEMMAS
D.1 OPTIMAL TRANSPORT COST (PROOF OF LEMMA 3.1)
Let define the total variation (TV) distance between measures μ and defined on common measurable space ()', ())) as
Div(ulle) - 1 2 / (ulds)) ((ll)) u(dy))
(9)
We have
/ (y + d
OTC(3)
min pEM(p.
min DEM(KiU
Py # z)
DTv(alle*)
(10)
(J (m(dy) - - / J3. lu(dy) ((
@1
(((1 ((1AAm(()))) -r. + (0VV (0VI-ms(srx)) - (1 -8pm)
(1 ma(Br.)) 8p
(11)
where (10) a well known result, see, for example, (Villani et al., 2008, page 22), and (11) follows by noting that (8,,),) 2 8,- by definition, since ma(s,-) is the mass that the optimal policy puts on St, and must be at least equal to 8p*.
D.2 BON SAMPLING DISTRIBUTION
In this subsection, characterize the BoN sampling distribution, where the BoN algorithm has access to a membership oracle S, such that r r(x [ E S} for any prompt E X and response y y. Note that the analysis for BoN sampling distribution presented in (Beirami al., 2024) does not apply to our setting, since it assumes a strictly monotonic reward function. We have the following result. Let us denote - rd..
(N) Radon-Nikodym derivative). Let UBON denote the sampling distribution in- duced by BoN with batch size N + 1 and access membership oracle S. We have
Lemma D.1 (BoN -
(N) (N)
(1-5)) s) (1-1-(1-5) ()1-))4t). if y yES.
if y S
BoN
(y)
du
Proof. For any set A E y, we have
MBo (A)
(N)
Σ P(Y,. E A, response is selected)
nE[N-1]
(N 11)((Y, A, response is selected)
which follows from the independence of the sampled response (Y,,-.. YN+1). Next, note that
PYY, E A, response is selected)
/ P(Y: E A, response is selected Y, yd)(dy)
= -/P(Y, E.A response is selected, Y, = y) PP(response selected Y, = ((dy)
-/P(XEEAXYI=)) - 1 is selected Yi =y)u(dy)
18

---

Published as a conference paper at ICLR 2026
- / E A} Presponse is selected Y1 p)
which implies that
(N) VoN (A) (N 11) 1(y E A} P(reeponse is selected | Y = y))
Thus, the Radon-Nikodym derivative of (N) BoN with respect to the proposal j is given by
(N)
BoN
(y) (N + 1) (responne is selected Y =y) du
(N + 1) PP (response is selected, YI $ 8 Y
A Ti + (N + 1) PP(espons is selected, Y, E Y1 =)
Th
Expanding Ti, we have
Ti P(Y, $ SVJEEj [N + 1], response is selected Y1 y) P(response is selected Yi y, Y, $ SVjj IN + +1)
x P(,, SA j [N +1| y)=
1
N+1 II F(Y; S Y, y JEIN+1]
N+1 (1 1) f(y {).
(12)
Furthermore, we have
Te = Σ
P (Y,,... Ym) E 50m (Ym+1, .YN11) & S&N-m.
ME(++1)
response 1 is selected Y, = =y)
N+1 N m-
m (1 - 8) m 1221114 {y ES}
m==
n (1 8) 1m fy E ES
(13)
+ 1
m==
Combining (12) and (13), we get:
dv
(N)
(1 s)
if y $ S,
(y)
(14)
du
(N 1)
g (1 (1-s) N)- if yES.
m+1
Furthermore, note that l tm dl m+
Hence, can further simplify (14) as follows.
N
(1 - -s { tt dt
n (1 8) N-
Σ
m
m7
m
N
(st) m (1 N dt
m=0
m
[' (1 - s + st) N
dt
1
(1 8) N+1
N +
which yields the desired result.
19

---

Published as a conference paper at ICLR 2026
D.3 BRS SAMPLING DISTRIBUTION
In this subsection, we characterize the BRS sampling distribution, where we assume BRS' acces to membership oracle S obtainable through verifier r(x,y) [y S} for any prompt x X and response y E y. Denoting _ Is ru, we have the following lemma.
Lemma D.2 (BRS- Radon-Nikodym derivative). Let VBRS denote the sampling distribution in- duced by BRS with batch size N + 1 and access to a membership oracle S. Furthermore, let v denote the optimal policy in ( x) induced by S, i.e,, v f arg max maammaapette PETTE x) Is dp. We have
(N)
B du
(y) = (1- -(1- (1--1-1
N
du (y) + (1 1
de
N
M
M
Proof. Recall that BRS obtains batch of N + samples, which we denote by y & (y N+4)). Denote the target-to-proposal Radon-Nikodym derivative that BRS uses to ac- cept sample y by n For our analysis, this corresponds to (2) induced by S. The conditional probability kernel for the BRS sampling strategy, which we denote by K(y .z). is given by
K Nyy dz)
Σ NE(N]
1
II JKn
(1-
(1
1 =
Sy, (dz)
M p(s.i)) uldz)
II NEN
1
The BRS coupling is then obtained as
PERS
(N)
K(y ((yN+1 .dz) 1 (dy
(15)
Marginalizing (15) with respect y2 obtain
PBRS (dz)
(N)
f p(dy .z)
/ Σ
II (1
1 1
M myyn)
6y.
ME[N]
Jen
(1 1o m(vw))
(dy (dycc)
neN
= Σ
1 du (1-
M du (x,) (x)))((d)))
(
1 do(yn)dy, (dz)
M
NEIN]
jkn
+ p(dz)
II ne(N]
/
(1
M dj (Im) p(dyn)
1 du
1 n-1
M v(dz).
Σ
(1 M uldz)
M
NEI
1
1
(1
1 1)
p(dz) +
p(dz),
M
and the lemma readily follows.
E PROPERTIES OF ROC
In this section, we briefly review the properties of the ROC for completeness and introduce useful definitions that will be leveraged in subsequent analysis. Recall that 8; (s()).
20

---

Published as a conference paper at ICLR 2026
True positives (TP): samples correctly identified by the verifier, i.e., S The reference mass is TP su(S n n*)). False positives (FP): incorrect responses accepted correct, i.e., S\S", with mass FP _ u(S \ (**).
False negatives (FN): correct responses rejected by the verifier, i.e., S*) with mass FN & u(8* ()). True negatives (TN); incorrect responses correctly rejected, i.e., \ (S* US). with mass TN _ p(y) \ (S* U))..
True positive rate (TPR): the fraction of true positives among all ground-truth correct re- sponses:
TP
1 - 14 nS).
TPR
T
Spt
Thus, TP s,- TPR.
False positive rate (FPR): the fraction of false positives among all ground -tuth incorrect responses:
FP
1 8p 1(S)8) 8*).
FPR
FP+ TN
Thus, FP = (1 s4-) FPR.
It follows that
8F 11S** n() p(S)()) S,, TPR (1 Spt) -FP Sver (16)
Likewise,
FN = 8ps - TPRR..
(17)
F AIC PROPERTIES (PROOF OF THEOREM 3.2)
Computational complexity.
For AiC, the acceptance probability is given by P Y Y Tzer(- X)) / u(dy) sp
PAIC
As shown in Appendix E, since 8p
8ver, we have PAiC 1/ Sver- Finally,
E TTTCI]]
PAIC
Σ n- PAIC)
PAIC
Sver
PEN
Sub-optimality.
The mass that the AIC sampling rule assigns to the ground truth set S* is given
by
VSi = (S ) + MAIC(S* ()
1
S,- 11S* nS)
TPR,
(18)
Sver
where (18) follows from Appendix E. Hence, we have VAIC(S") - (((*)) =
$
TPR Sp
Sver
TPR 1 + 8p
Sver
(6))
8,
TPR (8pe TPR (1- (1-R)))FPR) FPR)
+ + -,
Sver
Sr" (Sver FPR)
Syer
- 8," (spp. TPR .FPR) FPR
Sver
21

---

Published as a conference paper at ICLR 2026
1
Spc (1 -gp)) .r.)
(19)
8ver
Next, note that
SubOpt(AiC)
@ v²(8*) VAiC(S*) = V'( m1S*) + (u(*)) (AAi((*))
OTC(3) 1 s,. .J.
(20)
Sver
where (20) follows by noting that v (S*) = (1 A ma(s,))) (using (2)), followed by using Theo- rem 3.1, and finally combining it with (19).
Large coverage 3 :: In this regime, have OTC(3) 1 8,*, and hence, a,*
have:
SubOpt(AiC) OTC(B) (1- Sp
.1)
5ver
Small coverage B 1. : In this regime, the optimal transport cost is increasing in 3, and is given by OTC(3) = V 6p 8,* (3 - 1), and hence, we obtain:
8,,
SubOpt(AiC) OTC(3) (1- 1 (1 Spr ),))..)
8ver
B
G AIC CONSTRAINT VIOLATION (PROOF OF THEOREM 3.3)
Note that
(Azc(dz) uldz S) (16)
pldzn S)
1 1 S}
u(dz).
Sver
8ver
Hence, we have
(dviic)
/ 8ver
(M(lAAC))
du-1=
du
du
Sver
which implies that based on our coverage constraint, we have
Suer
H SMC RESIDUAL MEASURE (PROOF OF THEOREM 3.4)
Let us define the minimum measure À A (μ A v). Furthermore, let us assume that mg(s,) 2 8y5 the complementary case follows analogously. Based on the closed-form expression for the Radon- Nikodym derivative of the aaggt-to-proposaa measures stated in (2), we have m
du du
I
p = plst 1
11 s
(21)
which gives
リー x = (p 1) 11 5 (g 9)14 s ss
(22)
where we have set
1
mz(8r)
1 - 1--m(te) vo)
- A
and
11 8r
8r
8y
Furthermore,
1 - ma(st)
X(3))
21
+
(1 sr)
St
22

---

Published as a conference paper at ICLR 2026
1 (mo(sr) (r)
Sr (( mp((r))
A -
-1)
84
5r
sr 1)
(23)
Finally, we have
(p (p- ())--S
(23)
u(-18).
Mres
I SRS/ / SMC COMPUTATIONAL COMPLEXITY (PROOF OF THEOREM 3.5)
Computational complexity of SRS: We have
(z Y Y Weof(: x))
= P(Z Z = Y Y Teel( x)x Y P(Y P(YEE)
Sver
+ +P(Z = Y Y
Tret xx) Y $ S PPP 5
= Sver +
Y Y Treel x). Y & S M (Y) ,
U, U ~ 1
x P
U~ Un 1| y~ Y $ $
M
+ P
Z = Y
nzotl xx), Y S M (YY < U 1nif(o.1]
x PP
MY) < U, U U Uniflo, 1I Ttor(. xx) Y $ $
(ov 1 - ma
Sver + (1 8ver)
Sver
(1 A mg (Sver)
8ver
Sver
Sver
Sver
(I A ma
Sver
= (1 A ma
Finally, denoting psns & Pl -Y Y Troe(: [x)), we have
PSRS Σ n (1 PSRS) n1 1
(1 (1Amp(Svee)
E [SRS]
PSRS
Sver
nEN
Computational complexity of SMC: First, note that SMC's probability of acceptance for the first proposal given by
-(((() 2 U U U Unif 1I) -(((() > U U ~ Unir 1], Y .P() e $)
+ + 2 U Unif(0, 1], Y & 5) P(Y $ $)
Sver + (ov 1 - m (nver)er)
(16)
(1 Sver)
Sver
-- (0 V mo((vve) Sver)
(24)
23

---

Published as a conference paper at ICLR 2026
We have
E E[TsMC]
TP P(frrst first proposal accepted)
)
+
1+ Σ
nP nn proposal is accepted)
IP Pfffrstt first proposal is rejected)
nEN
nsver (1 Sver)" )
(24)
1 (0 V ma((vvrr) Svee)) + 1 Σ
((1 ms((sver) -Sver)
neN
(LAmeevve)).
Sver
SRS/ / SMC SUB-OPTIMALITY (PROOF OF THEOREM 3.6)
SRS is transport plan in M(, 2) and SMC is designed from the optimal transport plan from μu to 5, where denote the optimal distribution induced by the estimated reward, i.e., 7 - Law(Z x) where 7- x). and we define R- x) & arg max x)en((3 x) By xx) [y,, x)]. Con- sequently, SRS and SMC sample from the same distribution 1/; our sub-optimality analysis will quantify the discrepancy induced as a result of sampling from f7 instead of v". The key in our anal- ysis is decompose the sub-optimality into two terms: an optimal transport cost (OTC) term, and policy improvement (PI) term. This leads to sub-optimality having three distinct regimes, which we discuss next. Note that for 2 SRS, SMC,
SubOpt(21) v²(8)) (a*)
-i(*) =v((S* m(S*) DIS") m(S))
OTC
PI
The mass that assigns on S* can be expanded using the Radon-Nikodym derivative in (2) as follows.
u1S" n + mg((ver) vo) :1(5" (S)
(((S)
Sver
Sver
Sver
m
ma(Sver) vo) FN
TP
8ver
Sver
8ver
ma(Sver)
1 m vo) Sg. (1-PRR). (25)
(77
S,-
TPR +
Sver
Sver
Sver
Pver
A Quer
Furthermore, expanding PI, we have
D(S*) m(S*) (25) 8rr (Piver 1)TPR (gver 1)(1 -I(1-TPR)
8p- ((- Sver
(o(evvrr)
Sver
TPR
8ver
Sver
mi (Sver)
Sver
(1-PPR
(1 - TPR)
Sver
8p
TPR
1 TPR
5,t (mp(Sver) Sver)
Sver
Sver
8p-
(svo) Sver)
TPR
Sver
Sver (1 Sver)
TPR (sp- TPR + (1 8y FPR))
Sp- (m Sver)
Sver (1 S
Sp (1 Sp:) J
= (mo(Sved) -vver)
(26)
Svar (1 8ver)
24

---

Published as a conference paper at ICLR 2026
Next, based on coverage. have the following fours cases.
Transport regime- - B S [ A ): In In this regime, we have OTC(3) / S Sp- (B - 1),
S,,
which combined with (26) gives us
SubOpt(21) = OTC(3) (1-) (
Sy- - Sp-))
Sver (1 Sver)
Policy improvement regime - B E (x 8,e
this regime, we have OTC(3)
=
Vs, (1 s,, s,3 1) and m, (Svor)
Sver
V /Sverl (1 Sver (B 1), and hence, have 1
SubOpt(2I) Vo, (1 - -,.
Sp (1 8p-))
Sver 8ver)
OTC(B) (1 (1-
8, (1 81-) ),.)).)
8ver
3 -
Policy improvement regime- - 3 ",,0
In this regime, OTC(3) 8ys, and hence, we
eavar
have
SubOpt(2() = (1 8,.)) V 8ver (1 - 8yar)
8y (1 8p-))
(1- (1-V 8ver (1 Sver)
= OTT(B)
8p
Saturation regime- - 3 Bune
In this regime, we have OTC(33) 8, and mg (Sver) =
and it can be readily verified that
SubOpt(2() = OTC(3) (1-
Spr
8ver
K BoN BATCH SIZE (PROOF OF THEOREM 3.7)
Let us denote e Sr. Evaluating the x² --divergence between the measure induced by the BoN sampling policy UBoN with batch size N + 1, we have
/ (duBON ( ) du 1 du
[ duBoN du
(dUBoN
) du -
dp +
J
dj
1
1 - (1 18,r)))) 8r+)aa )a. + (1 - Sp )a² -1
(27)
1
1 (1 -, ) - 2(1 - Sp s,-)aa
+ (1 11-sp sssa)aaa
Spt
1 1 8pt
1 - 8, - Sp
a²
2a
8pt
Spt
Syt
1 - 8r-
(a - 1)²
Sp- where (27) follows from Lemma D.I. Hence,
x2 (VBBNN11)) =
1 (1-8p')
Sp
(1- (1 Sp. )r.)
(28)
Syt
Note that x² ((BONNlIA) S (1 (1-8,,)/a S/s and hence we have Nmax = +o0 for any 3 > (1-8,-)/s)
The regime B E (sp- (1 S,,),, 1-8.2] follows from bounding (28) by 3 - 1. The proof completes
8, by noting that x² (VBON(IA) is lower bounded by sy- (1 - 8,*), which is obtained by setting N in (28).
25

---

Published as a conference paper at ICLR 2026
L BON SUB-OPTIMALITY (PROOF OF THEOREM 3.8)
From (3), we have
SubOpt(BoN) v'(8)) (S")
v'(()) - (1 - (1 (1p)))) )
(29)
(1 (g )) 8,, + (1 - 8p- ) + (1 - 8,,) N
(30)
(1 s,,) ) (0 1 m)
where (29) follows from Lemma D.1 and (30) follows from Theorem 2.1.
M BRS BATCH SIZE (PROOF OF THEOREM 3.9)
Let us set a = (1 +
We have
= / (dunRs)
(VBnslll)
dp
du
/ a NN (1--0~))
du-
(y) + a- uldy)) -1
(31)
dp
= / (1 a
- N2²
dv"
dy p(dy) + / 2N m(dy)
a N - a N) du*
+
(((dd -1
du
dv
/ ddv" dp
(1 a
N22
u(dy) +
(1 (1-a-N1²
u(dy)
dp
33.
+
2N 2a
-N (1
-N
1
1² v²(dy) mx((pr)
(1
N2²
N (a -N +2 2a ) -1 (32)
8p
8r.
(ov 1 1=mp((p)) )
+
(1
Ny2.
-p u(dy)
(1 (1-60) a N2.. (1 )) + (1 - NN-
1- sT (OV 1 mp ))
8pa
+ a
N (2 - a ) -1
= (1-a N1²
1
(1 A (m ))² + 1 8,
(0V 1 m
8px
+ +a -a-N - a NN--
A1
= (1- (1-1)2 2t +P)
(1-))
where (31) follows from Lemma D.2 and (32) follows from Theorem 2.1. Next, investigating C, we have the following two cases.
Case A: (1 A m )) m m ): In this case, denoting d A Vap (1 8, )B - 1), we have
C (s,t + +d²
(1 - S,- d)2
Sp-
1
= 1 df
+
8pr
1 8,
26

---

Published as a conference paper at ICLR 2026
1 +
1+ 8p- 8p. 8y. 63 -11)
8r
a+ 1) 8p- + Sp-)
= 3.
Case B: (1 A ma(s.))) 1: In this case, have C 8,* Furthermoremore, leveraging the condition in this case that (*(( 2 1, we find that B 2 I. consequently establishing that C S B. Our proof concludes by noting that (1 --2 I for any N N.
N BRS SUB-OPTIMALITY (PROOF OF THEOREM 3. 10)
From (3) we obtain that
SubOpt(BRS) 1'(8") -BBR((S))
(1 A mp(sr:)) (BBS(
(33)
1
1
(1Amp((rr)) -
8p
(34)
M
M
N
(11- 8p A mp((rr) - -8r))
M
N
OTC(3)
1
(35)
M
where (33) follows from Theorem 2.1, (34) follows from Lemma D.2, and finally, (35) follows from Lemma 3.1.
O BATCHED SAMPLING ALGORITHMS WITH A APPROXIMATE VERIFIERS
In this section, we extend the sub-optimality analyses for the batched sampling algorithms BoN and BRS settings where we only have access an approximate verifier, captured through the set membership oracle S. We begin by analyzing BoN sub-optimality with access to S, and sub- sequently state the same for BRS. We conclude the section discussing the different regimes of the sub-optinality-covrag plot, and which algorithm is preferred each of these regimes. For our analyses, we decompose the sub-optimality into two components, sampling error, and a verifica- rion error. Specifically, for any algorithm 2 E [BoN, BRS), let Dx denote the distribution induced by its sampling mechanism. Accordingly, we have
SubOpt(21)
(*(*)* (0s))
V*(** va vx Da (S*)
(36)
sampling error
ervor
We have the following theorem for BoN sub-optimality.
Theorem 0.1 (BoN - sub-optimality with approximate verifiers). The sub-optimality of the BoN
sampling algorithm with access to an approximate membership oracle & is given by
SubOpt(BoN) = (1- (1-55 sy-))
8r* (1- - {vve)))) (0V1-ma(sp))
8ver
Proof. From (36), observe that it sufficient to evaluate the verification error, since the sampling ervor has already been analyzed in Theorem 3.8. We have
(S*) - DBON (S*)
= "BON((") (DRON(S* S) + OBN \ 5))
( -1 N+1) 11 n
= =(1 - 8p, N++1) 8ver
(37)
27

---

Published as a conference paper at ICLR 2026
+ (1 - 8ver) uOS* ' (5))
(1 (1 8p,) w+1) - 8p- (1 (1 Sver) N TPR
8ver
+ (1 Sver) ) 3p- -TPR)
=(1 (1 8p- s,.) )+1) 8p (1 8ver) )
(1 TPR)
Sver)
TPR
Spt TPR
Sver
Sver
(1 (1 8,- 1+
84 8r- 8ver) N
8ver
TPR
8y. TPR
8ver
8ver
(1 8,-) 1+1
Sy-
((1 Sver) ). (8ver
TPR) + TPR)
Syer
(16)
(1 (1 )..) N+1)
S,*
TPR (1 8p )1 8 .J)
8ver
(16)
(1 11
Sr*
8ver + (1 3p-) (1 - Sver) MM) .J)
Sver
8y (1 8p,)
(1 s,-) ) N+1)
Sver) J
(38)
where (37) follows from Lemma D.1. The claim readily follows by combining (38) with Theo- rem 3.8 using (36).
Next, we state the sub-optimality of the BRS algorithm with access to an approximate oracle S. Theorem O.2. Let us set ON (1 -
34 ). The sub-optimality of the BRS algorithm with access to an approximate membership oracle S is specified through the following coverage regimes.
1. Transport regime: In the transport regime, characterized by the coverage constraint B S we have
(
(ma(Sver)
SubOpt(BRS) OTC(3)(L - aN) aNss.
TPR
8p-
Sver
1 ms((vvr))
(1 -1-TTT TPR))
+
Sver
2. Policy improvement regime: We have two cases. If Sver Sy,, in the policy improvement regime, characterized by the coverage constraint " -
و we have
(m)(sp))
TPR
SubOpt(BRS) (1 aNS
Spt
Sver
Alternatively for 8 E (11 sver we have
(ma(Sver))
SubOpt(BRS) = OTC(3)(1 aN) + ANSPt
TPR
8p+
8ver
1 - --me(Sver)
TPR) ))
Sver
3. Saturation regime: In the saturation regime, characterized by the coverage constraint 3 >
Sver we have
TPR
SubOpt(BRS) = OTC(3)(1 aN) + a.
Sver
28

---

Published as a conference paper at ICLR 2026
Proof. Similarly to Theorem O.1, we will analyze the the verification error for BRS. For clarity in presentation, let us define
p(s) - ( ms(s)
= and g(s) 2 (ov m²(()
(39)
8
Note that
U (8*)) + (S \
(,
= ON p((vvr)) + (1 (N) ( ((())*)) + [NN (((ver)) + (1- SN) u(8* (5)
(40)
= (ONp(Sver) + (1-aw)) aN) S,, TPR + (aNq(Sver) + + - (1-1a)) 8pt -1-
= AN 88 (p(8ver) TPR (( ((ver)) - (1-TPR) + +1 aN )8r)
(41)
where (40) follows from Lemma D.2. Furthermore, can be readily verified that
VBRS (BR)(S") aN 8,. p(( ) (1 aN)s..
(42)
Combining (41) and (42), we have
VBRS(S") - TBRS
= aN s.. p(sr))))))) - -p(sver TPR S,, - -g(sver) ) (1 TPR) 8,
m (Svor)
(39)
(IAmp((s.))) -
A
TPR Sp
Sver
Sver
-ov
1 - -mmmasssne ma((ver) )
(1-TPR)s,
1 Sver
Transport regime: In this regime, since both ma(a;) and ma (8ver)) are less than 1, we have UBRS (S*) (S*)
aN mm)(s))) ma(Sver)
1 - ma TPR) -ppt)
-px
TPR
Sver
Sver
ax8 (mp(rr)
( mma(vvrr)
1 mp(Sver)
(1 TPR) )) (43)
TPR
8x-
Sver
8ver
Finally, the result readily follows by adding the sampling error, OTC aN) proved in Theo- rem 3.10.
be divided into two cases, in which 3 (1/8ver, 1/8,, and the second in which 8 E (1/s/-, In the first regime, the result read- ily follows by replacing m = in (43), and adding the sampling error OTC(3) - ax) )- In the second regime, the result readily follows by replacing mz(sp.) OTC(3) - aN), the sampling error.
Policy improvement regime: This regime
in (43), and adding
Saturation regime: In this regime, both m=(s)-) 1 and my( 1, and the result readily follows by replacing these values in (43) and adding the sampling error OTC(3)(1 aN). This concludes our proof.
Interpreting the results. In Theorem O.1, we note that as N goes to +00, the BoN sampling error decays to (and potentially becomes negative, depending whether the mass put on S* by the skyline policy less than 1). However, the estimation enror saturates at OTC(3)(1 أي J). as we had observed for AiC. This is intuitive, since the verification error is entirely controlled by verifier inaccuracies, and does not depend on the design of the sampling algorithm. Similarly, from Theorem O.2, we observe similar trend - the sampling error is driven down to 0 as the batch size N +o0, while the verification error stagnates OTC( Byper J) under the saturation
regime.
29

---

Published as a conference paper at ICLR 2026
gemma-3-4b-it
-lama-3.1-8B-Isste
ROC
FPR
1.00
0.75
TPR
FPR
FPR Constraint
0.25
0.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
FPR
Threshold
Figure 6: ROC estimated based on generations from (left), and meta-1lama /Llaaalaaaaaa Instrrctt (right). meta- 11 ama / /Ll.ma-m.33. 1- 8B- Instruct has a larger area under the curve (AUC) compared to google weemma3--b---
We observe that
P EXTENDED EXPERIMENTS
In this section, we specify how we construct ground-truth and approximate verifiers, the models used to evaluate our algorithms, and the hyperparameters employed in experiments. The evaluations are conducted on GSM8K (Cobbe et al., 2021), MATH500 (Hendrycks et al.), and OlympiadBench (He et al., 2024).
For GSM8K, prompts are constructed by prefixing each question with five randomly sampled train- ing exemplars. As in (Dorner et al., 2025; Huang al., 2025a), then draw 10,000 responses .eer(. x) at temperature 1, using models from the Owen, Deepseek, Gemma and I.l ama families. Specificallyy, we evaluate: (i) Qwen3-1.7B, (ii) Qwen3-8B, (iii) Qwen3-14B, (iv) google/gemnes 3-4 10-44b-.ttt (v) deepseek aitpeeeseaa//eepeeeeeeeeeeeeeeee math h-ahh-i 7b- mobbinstuuctt and (v) meta-llama. hataa/llaaaaaaaa 1-8B-Instruct, spannin sizes from 1.7B to 14B parameters. Gen- erations are obtained through the 1m-eval-harned framework (Gao et al., 2024). Verifiers are constructed in two modes: an construction mode and reward reward-guided guided mode. For sampling, we bootstrap from the 10,000-response pool with replacement.
Explicit verifier construction. To construct S* we determine the ground-truth correct- ness of each response by extracting the predicted answer via pattern matching with (-? [-3[$09.. 12, (-?[0-9]+), and marking correct if it matches the dataset gold label. The proposal's 's mass on S*, denoted s,,, is estimated empirically by summing the normalized lcgprobs of correct responses. For the approximate verifier S, we adopt an explicit construc- tion designed validate our theoretical analysis. Specifically, we curate subsets of correct and incorrect responses into S such that both the Youden index and the proposal's 's mass 8ver are con- trolled, thereby fixing the verifier's TPR and FPR. This provides direct and interpretable control over the verifier's 's operating characteristics. To ensure determinism, responses are ranked in descending order of their logprobs Candidates are then selected from S* and its complement St, starting responses in each set, and iteratively added until the cumulative mass
with the highest-probabine matches the preset values of J and Sver-
Reward-guided verifier construction. As second mode of verification score the generated responses, we employ reward models Skywork http:///wwwwooowwweeeeeeeee which ranks 1st on the RewardBench leaderboard (Malik state-of-art in math reward models (Liu et al., 2025). We de- rive approximate verifiers by thresholding: for a prompt x X' and response y E V. response included in å if its reward (x, exceeds threshold yy. By varying 7 we obtain a family of verifiers with different receiver operating characteristics (ROCs). In order show that the three-regime structure generalizes across tasks, problems and models, we show the sub-optimality of RS, SMS, and AiC function of for different value of y in the following settings.
ama-3.3.. 1.1aa-311180 1-8B, al., 2025), and
Ividia/AceMath-T//
30

---

Published as a conference paper at ICLR 2026
P.1 GSM8K
In Section 4, we presented results using the Qwen3-1. 7B and Owen3-143 models for ques- tion 2. Here, we supplement these with additional plots for Qwen3-82 under the explicit- verifier setting, along with further analyses illustrating how average reward varies with gener- ator coverage and how sub-optimality scales with computational complexity and Youden's in- dex. Figure 7 and Figure report these results for the Qwen model family under the sequen- tial sampling protocol. Figures 9 and 10 provide the corresponding plots for the batched set- ting, i.e., BoN and BRS. Figure 11 reports analogous plots under reward-guided verifier con- structed with Skywork/ ROCs for google/ gemma 3-4b-it and peeta-llamaLLaaan 1...-11--111. IB-Instruc.. Fig- ures 12 and 13 shows how the sub-optimality regimes change across different & and 7 for both poogle/gemma-3 4b-it and Besta-llama/tlee tively. Moreover, Figures 14, 15, and 16 show the same for questions 11, 14, and 4 when nvidia/ avidia/AceMaths AceMMtteM-a-ee-ea RM-RM----- is used as judge.
1.-8-1. 1-8BB, and Figure shows the
1 instruct, respec-
Qwen3-1.78
Qwen3-8B
Qwen3-14B
1.00
1.00
1.0
Reward
0.75
0.75
0.8
0.50
0.50
0.6
0.25
0.4
2.5
5.0
7.5
2.5
7.5
Computations Complexity
B
B
3
AIC
2
2
2
1
2.5
5.0
7.5
2.5
5.0
7.5
Computationa Complee eleettyy
B
1.00
1.00
1.0
0.75
0.75
0.8
0.50
0.50
0.6
0.25
0.25
0.4
2.5
5.0
7.5
2.5
5.0
Reward
Reward
Reward
Figure 7: Plots for sample of GSM8K dataset using the Qwen family with an explicit verifier: average reward versus 3 (first row), computational complexity versus 3 (second row), and com- putational complexity versus reward (third row). Trends predicted in Theorems 3.2 and 3.5 are observed.
P.2 MATH500 & OLYMPIADBENCH
In order to further demonstrate that the three-regime structure generalizes across tasks, problems, and models, we report the sub-optimality of RS, SMS, and AiC as function of 3 for differ- ent values of y on both the MATH500 and OlympiadBench datasets. For MATH500, we use deepseek- ai
as the generator model for problems 2 and 22). For OlympiadBench, meta--LaamaLLaaaa-33------ sample 14. For both datasets, we use bvidia/AceMath--22 to construct the reward-guides verifier.
(Figures 20 and 21) and meta-ll adopt beeepseek--iideepseeee -etpppppeeeeemttt--------tteenee -b-inthttuhii-tuuutt for
for problem 28 (Fig-
31

---

Published as a conference paper at ICLR 2026
Qwen/Qwen3-1.78
Qwen/Qwen3-8B
Qwen/Qwen3-14B
1.0
1.0
1.0
SRS
SubOpt(()
SMC
... A/C
0.5
B 1.13
B = 6.38
B 8.5
0.0
0.5
0.0 0.5
0.0 0.5
Figure 8: Sub-optimality plotted against Youden's index J for the Qwen model family with an explicit verifier, using 3r, 3PL, Ss to represent the three distinct coverage regimes. 3 values are computed as 3T (0.2 Peat V 1), SPI (Br + B2at)/2, As 1.2 Beat, where Seat
(1/s,+ A vver,, and Beat = (1/s,² V 1/vver))
Qwen3-1.78
Qwen3-8B
Qwen3-14B
SUbDpt(BRS)
0.75
0.50
N
0.25
2
3
SubOpt(BRS)
0.75
6
7
0.50
0.25
Empirical
Theoretical
2.5
5.0
7.5
2.5
5.0
7.5
2.5
5.0
7.5
B
B
Figure 9: BRS plots for the Qwen family with an explicit verifier: ground truth verifier the first row, explicit verifier on the second row. Plots match the theoretical findings in Theorems 3.10 and O.2. Furthermore, N increases, sub-optimality decreases.
Q COMPUTE AND LLM USAGE
All generations are performed in 8x A6000 Nvidia GPUs with 49 gigabytes of VRAM each. LLMs have been used for (1) sharpening the write-up, (2) coding assistant for the experiments, and (3) verifying the correctness some algebra in the proofs of Lemma D.1 and Theorem 3.8.
32

---

Published as a conference paper at ICLR 2026
Qwen3-1.78
Qwen3-8B
Qwen3-14B
SubOpt(BoN)
0.6
N
1.0
0.2
2.0
3.0
4.0
5.0
SubOpt(BoN)
0.6
6.0
0.4
Empirical
0.2
Theoretical
2.5
5.0
7.5
2.5
5.0
7.5
2.5
5.0
7.5
B
B
B
Figure 10: BoN plots for the Owen family with an explicit verifier: ground truth verifier on the first row, explicit verifier the second row. Plots match the theoretical findings in Theorems 3.8 and O.1. Here, we choose N [L(Nmax A })]] as prescribed Theorem 3.7 for feasibility.
gemma-3-4b-it
Llama-3.1-8B-instruuc
1.00
1.00
Reward
0.75
0.75
0.50
0.50
0.25
0.25
2
3
6
Computationa Complexity
2
2
SRS
SMC
B
AIC
1.00
1.00
Theory
Reward
0.75
0.75
0.50
0.50
0.25
0.25
1.0
1.5
2.0
2
Computational Complexity
Computational Complexity
SubOpt(e)
0.4
0.2
0.2
0.0
0.0
8
Figure 11: Reward-guided verifier: verifiers chosen as indicated in the ROC plot in Figure 6. We plot reward versus (first row), computational complexity versus (second row), reward versus computational complexity (third row), and sub-optimality versus 3 (fourth row.)
33

---

Published as a conference paper at ICLR 2026
Task: gsm8k Sample: Model:gemma-3-44
SRS
SMC
AIC
theory
0.4
SubOptii
0.2
RPR=1 060
RPR-0 900
RPR-0.811 TPR-1.000 0.00
RPR=0 736
TPR=1.00 000
TPR-1 000
TPR-1 000
1hr=0.000 000
0hr=0.272
0hr=0.464
1hr=0.408
0.4
Sub0pt8)
0.2
RPR-0 726
-PR-D 483
FPR-0.400
FPR-D 207
TPR- 1. .000
-PR 0.96
TPR-0.99
IPR- 90.3
Thr= 490
0.44
-.550.5335
1h 0.688
0.4
Sub0ptis)
FPR-0 003
FPR - 803
FPR APR-0.000 0.002
TPR 083
TPR - 082
PR 0.082
0--
TR 0--262
The
10
20
30
10
20
30
10
20
30
Figure 12: Reward-guided verifiers for different yt. We plot sub- uub-optimality versus 3 as varying Y (reported as Thr in each plot, together with FPR and TPR) for google 3ttp///mmaaaaaeeeeeee 3-4b-it.
gam8k 2ample:
Model:llama 3.1-88iiriitl
SRS
SMC
AIC
theory
0.8
0.8
9.20pm100
0.4
0.4
0.4
0.4
PRR-1 000
FMt-0 9:5
PPR-0.418
0.2
F9R-0-415
TPR-1 8000
178-0 995
0.1
Th--- 995
0.1
TPR-6 995
Thy
0.0
0.0
0.14
0.12
6.10
0.08
0.10
Su
0.08
0.05
0.4
0.06
PRR-0 0356
Frh-0 517
PeR-C 800
PPRC-C
TPR-0 995
0.07
TFR-0 530
THR-0-882 830
0.1
7 076
Ohr-0.763
ThC-
Th--
0.80
0.00
Figure 13: Reward-guided verifiers for different 7:. We plot sub-optimality ver- sus 3 as varying 7 (reported as Thr in each plot, together with FPR and TPR) for me meta-llaan aallamm/Ila amal333 --nB-Inntt
34

---

Published as a conference paper at ICLR 2026
Sample: ModalLicma--.11 1.1---.------tttttrc
SRS
SMC
A/C
theory
16--6
Sub
[PR-1 .010
FPS-0-225
FPR-0-22 --25-
FPR-0-251
FFR-0-253 Thrw
Thr- 10 625
The .2.0
Thr 8888
Thr 5.312
1.2
1.2
1.2
SubDOptoo
[198-1 (010
[PR-1 0.00
11tt-1 2200
17tt-1 (009 Thi- 1.227
Thr- (01
The- 3,094
Thr- 2.143
1.2
1.0
1.2
1.0
P
Figure 14: Sub-optimality as a function of 3 for varying thresholds of the LLM-as-judge verifier, evaluated on sample 11 of the GSM8K dataset using Ll allam-- -3. 1-8B-instruuct.
Task:: gomak Sample: 14 Model 3.1 38-Instruct
SRS
SMC
AIC
theory
2.0
Sub0ptt81
2.0
FRR=1 0:0
FRR-0.25 256
FP8-0
122
0.5
[[R=-] 000
TPh-1 000
[PR--] 200
1Ph=1 200
TPh 1.000
0.6
1.2
2.0
16-6
SubOpite)
2.5
3.0-
F-R-0-122 Thr-2.675 875
IPP 322
IP2-0 Thr-4.36
1156-0 202 Thre14
0.5
THR-1 0.00
Thin2 547
Thi-3.55 3.516
0.0
1.0
1.0
1.2
100
122
1.0
1.2
Figure 15: Sub-optimality as a function of 3 for varying thresholds of the LLM-as-judge verifier, evaluated on sample 14 of the GSM8K dataset using L Llama- 3. 1 1--1--8---- -B-instruct.
Task: gsmak Sample:
Model.Liama.3 3.1-8 1--8B--rstruct
SRS
SMC
A/C
theory
0.005
SuADpri43
0.004
0.002
FPR
F 200 Thrn- 312
FPR 999
1P
FRR 955
Thr 625
Thr 5.531
Thru-d 1.00-4.900 906
Thr-- 4,312
0.000
1.2
1.2
1.2
1.2
1.2
0.006
5ubDpti4)
0.004
0.002
FPRi-2
TPR-1.000
TPR=1100
1.000 Them-1.110
Thrm-2 969
Thrm-2.177 2.17
Thrm1 077
0.500
1.2
1.2
1.2
1.2
Figure 16: Sub-optimality as function of 3 for varying thresholds of the LLM-as-judge verifier, evaluated on sample 4 of the GSM8K dataset using Llama-3. 1-8B-instruct.
35

---

Published as a conference paper at ICLR 2026
gemma-3-44 3-4b-it
1ama-3.1-8B-Ins...
SubOpt(BRS)
0.4
0.2
N
1.0
0.0
2.0
3.0
4.0
SubOpt(BRS)
0.6
Empirical
0.4
Theoretical
0.2
0.0
7.5
5.0
B
B
Figure 17: BRS plots with a reward-guided verifier: we plot sub-optimality versus 3 with the ground truth verifier on the first row, and approximate verifier on the second row.
gemma-3-4b-4
Llama 3.1--B-B1BBBBB- 88--Insstuut
0.75
SBbOpt(BoNN
0.50
0.25
N
0.00
1.0
2.0
3.0
0.75
4.0
SubOpt(BaN)
0.50
Empirical
0.25
Theoretical
0.00
2.5
5.0
B
Figure 18: BoN plots with a reward-guided verifier: we plot sub-optimality versus 8 with the ground truth verifier on the first row, and approximate verifier on the second row.
Task math500 Sample:
28
Model-Liama. Liamn-3, 1-88-Instruct
SRS
SMC
NC
Uheory
Dusskl
SubOptr8)
0.02
TT1--1
TIR-1 500
1hi 020
TIP--2
Thr- 6.250
Thr-0 395
11r-22200 584
Thr-d 625
Thr-6-375
1.5
1.2
1.4
1.0
1.2
1/4
3.0
1.2
3.4
3.0
1.2
1.4
1.0
1.2
1.4
P
0.08
Subaptt0)
0.02
=PR
FRR 418
FRA - 240 195 KSY
FRR 1P8 2.98
FRRLLO 1iti cus
11 au1
111-00 772
Thre133.250
Thr-06.0000
9
8
Figure 19: Sub-optimality as a function of 3 for varying thresholds the LLM-as-judge verifier, evaluated on sample 28 of the MATH500 dataset using Llama -3. 1-s-8-innstttt
36

---

Published as a conference paper at ICLR 2026
math500 Sample:
SRS
SMC
AIC
theory
0.5
0.4
Subopate))
0.2
FRR-1 003
FFR-0.95 0,954
FPR-0.50
FRR-00.576 0.576
FPR-0.50
0.1
(100
IML-11
Thr-
Thr-1.641
Thr-2
0.0
1.0
2.5
2.0
1.5
0.4
Suh0pn/0s
0.3
926 TFR=1
IFR
IPS. 808 11am 4./81
FRR 335 - 1094
FRR 000
1h-m5.192
Thy 5.575
0.0
1.0
1.5
2.0
2.5
1.5
2.0
2.5
1.0
1.5
2.5
1.0
1.5
2.0
2.5
5
10
Figure 20: Sub-optimality as function of 3 for varying thresholds of the LLM-as-judge verifier, evaluated on sample of the MATH500 dataset using -htesseeee-mtth------e irbb-instuuct.
Task: math500
Sample:
Model math www.ssthhhbiiituaaaaa instruct
theory
SubOptts)
0.4
0.2
= 000
FFR
FPR
FPR.00
FPR
11r- 112-01.20 7230
11100.122
Thr-1, 055
Phr-1.53/
(hr= 094
1.5
2.0
2.5
3.0
1.0
1.5
2.0
25
3.0
1.0
1.5
2.0
2.5
3.0
1.0
1.5
2.0
2.5
3.0
1.0
1.5
2.0
2.5
3.0
0.6
Sub00p00)
0.2-
324
TPR
000
TiR--d 801
TPR - SAB
TRR 241
0.0
2.0
2.5
1.0
2.5
1.5
2.0
2.0
2.5
3.0
10.0 12.5
Figure 21: Sub-optimality as a function of for varying thresholds the LLM-as-judge verifier, evaluated on sample 8 of the MATH500 dataset using deepseek-mathe -a-t-aa-tt-tttee math-7b-insttrce instruct.
Task olympiadbench
Sample:
Model::eersseek-mmtthhh
SRS
SMC ..0i A/C
theory
Sub(pttt)
0.4
PPR-1 000
FPS-0
F98 966
0.2
7PR 000
TPS-1 .60D
TPR-1 000
TRR-1 080
TPR-1 800
0.0
1.0
SukOptiM1
0.8
FP 955
FPS-D 965
FFS-0 9M Thr 2.224
FFN--0112 125
Thre- 1.211
Thr- 0.785
0.720
Try-3. 812
5.0
20.0 32.5
Figure 22: Sub-optimality function of 3 for varying thresholds of the LLM-as-judge verifier, evaluated on sample 14 of the OlympiadBench dataset using deepseek-mat -aakk-mathhh-e 7b- 7b-instrucc
37


Reviews:
[{"review_id": "Kg7rK4ou0u", "reviewer": "Reviewer_CAuT", "summary": "This paper develops a theoretical framework for test-time verification in LLMs using optimal transport theory. The authors characterize how three factors interact: generator coverage, verifier accuracy (region of convergence), and sampling algorithm sub-optimality. The main contribution is identifying three distinct regimes in the sub-optimality–coverage relationship: transport, policy improvement, and saturation. The paper analyzes both sequential (AiC, SRS, SMC) and batched (BoN, BRS) sampling algorithms, deriving exact bounds on computational complexity and sub-optimality. Experiments on GSM8K with Qwen, Llama, and Gemma models validate the theoretical predictions.", "questions": "- How robust is the three-regime structure across different GSM8K problems? Even a small-scale analysis (e.g., 10 problems stratified by difficulty) would be valuable.\n\n- For practical deployment of SRS/SMC, what would you recommend for estimating s_ver? Could one use a small validation set, or are there theoretical estimation guarantees available?\n\n- Does the Polish space formulation matter in practice? LLM outputs are discrete token sequences. Have you verified that discretization doesn't significantly affect the optimal transport characterization?\n\n- How would the analysis change under alternative coverage constraints (KL-divergence, Rényi divergence)? Would the three regimes persist?\n\n- Theorem 3.7 shows BoN violates coverage for β < s_r*(1-s_r*). Should practitioners avoid BoN in such regimes, or might constraint violation be acceptable if it improves empirical performance?\n\n- How does performance vary across different FPR operating points in the reward-guided setting? Is there a principled way to select FPR?\n\n- SMC and SRS achieve identical sub-optimality and complexity (Theorem 3.5). What's the practical advantage of the more complex SMC derivation?\n\n- Could you clarify how your coverage parameter β relates to the sample budget N in prior BoN scaling analyses (Brown et al., 2024)?\n\n- How might the framework extend to continuous reward models rather than binary verifiers? This seems relevant for many practical applications.\n\n- Figure 5 shows SMC outperforming SRS when the assumed s exceeds the true value. Is there theoretical intuition for this crossover?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The optimal transport formulation elegantly unifies the analysis of generator coverage, verifier imperfections, and sampling strategies. This provides a principled way to reason about test-time verification that goes beyond existing asymptotic analyses.\n\n- The paper derives closed-form expressions for sub-optimality (Theorems 3.6, 3.8, 3.10) and computational complexity (Theorems 3.2, 3.5) across multiple algorithms. These exact results are more informative than asymptotic bounds for practical algorithm selection.\n\n- Identifying transport, policy improvement, and saturation regimes is valuable both theoretically and practically. The analysis shows that the relationship between coverage and sub-optimality is non-monotonic and depends critically on verifier quality (Youden's index).\n\n- Explicitly incorporating false positives and false negatives through ROC analysis (TPR, FPR) is important for practical deployment. Most prior work assumes perfect verifiers, which is rarely realistic.\n\n- The paper provides actionable guidance: rejection sampling methods (SRS, BRS) are preferable under tight coverage constraints, while Best-of-N methods work better with relaxed coverage. This addresses a practical question practitioners face.\n\n- Figures 4-5 show close alignment between theoretical predictions and empirical results across different models and parameter regimes, which strengthens confidence in the framework.\n\n- The paper effectively uses figures (especially Figures 1-2), tables, and clear regime-based decomposition to communicate complex mathematical ideas.", "weaknesses": "- All experiments use one GSM8K question (sample 2), following Dorner et al. (2025). While this protocol has precedent, it limits our ability to assess whether the three-regime structure generalizes across problems of varying difficulty and characteristics. Even testing on 5-10 representative problems would strengthen the claims.\n\n- SRS and SMC require knowing s_ver (the reference policy's mass on the verifier set), which may not be available at test time. Section 4 treats it as a hyperparameter, but Figure 5 shows that misspecification substantially degrades performance. The paper would benefit from a practical estimation procedure.\n\n- The ℓ1-type constraint (Equation 1) based on χ²-divergence is mathematically convenient but somewhat restrictive. The authors discuss this limitation briefly but don't explore how alternative divergences (e.g., KL, Wasserstein) might change the regime structure. This seems like an important direction for future work.\n\n- The experimental protocol samples with replacement from a pre-generated pool of 10,000 responses. This doesn't fully capture the parallel generation scenario that motivates batched methods in practice, where responses are generated independently in a single forward pass.\n\n- While the paper analyzes expected number of proposals, wall-clock time depends on GPU parallelization, model size, and verifier overhead. Sequential methods may require fewer total proposals but could be slower than batched methods in practice. This practical tradeoff deserves discussion.\n\n- The main experiments construct verifiers by controlling J and s_ver through probability-ranked selection. Real verifiers (unit tests, reward models) don't work this way. The reward-guided experiments (Appendix) are more realistic but limited to two models with FPR=0.3.\n\n- The paper compares proposed algorithms against each other but not against recent test-time scaling methods like guided stream-of-search (Gandhi et al., 2024; Moon et al., 2024). Such comparisons would help position the work's practical contributions.", "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": "BykjnmsHvz", "reviewer": "Reviewer_hmED", "summary": "This paper studies the test time verification as a sampling problem with a lens of optimal transport. The framework of optimal transport where given a proposal distribution $\\mu$, the goal is to sample from $\\nu ^\\star$ that is defined by $r ^\\star$. The problem here is usually at test time, $r^\\star$ is not available to guide the generation and thus one needs to rely on imperfect reward models. This paper also studies the geometry of sub optimality and coverage by relating the suboptimality to verifier's region of convergence (ROC) and generator's coverage, revealing three different regimes (transport regime, policy improvement regime and saturation regime). The paper analyzes: (a) sequential protocols—Accept-if-Correct (AiC), Sequential Rejection Sampling (SRS), Sequential Maximal Coupling (SMC); and (b) batched protocols—Best-of-N (BoN) and Batched Rejection Sampling (BRS). It proves AiC can violate the coverage constraint in low-coverage regimes and provides closed-form sub-optimality/complexity for SRS/SMC and exponential-in-N decay for BRS. Empirically, the paper focuses on GSM8K with Qwen, Llama and Gemma models and demonstrates their behaviour across different test time compute algorithms.", "questions": "* The acronym OTC and OHC both refer to optimal transport cost, right? Why does the paper use both interchangeably? I recommend sticking with one of them. \n* The explicit verifier is constructed by ranking and selecting responses to hit preset $J$ and $s_{\\text{ver}}$. Can you add experiments with more realistic verifiers (e.g., harness parser variants, unit-test fuzzing, LLM-judge with calibration) and show robustness of your theorems’ qualitative predictions under such noise?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Theoretical decomposition of sub-optimality into OTC is clear and a verifier-driven factor three-regime picture is intuitive and well explained.\n* Precise AiC analysis with explicit coverage violation condition and sub-optimality formulas.\n* SMC construction via maximal coupling with matching complexity to SRS; neatly links transport optimality with compute.\n* BRS exponential improvement with tight envelope; theoretically beats BoN in low/intermediate regimes.\n* Empirical studies match theoretical findings.", "weaknesses": "* GSM-8K is a very limited dataset, and especially as a test-time compute paper, I strongly recommend using a reasoning benchmark. You can either one or multiple of the AIME, OlympiadBench, MATH, GPQA or AMC questions to test the validity of the approaches here.\n* The analysis of hybrid approaches between sequential and batched protocols such as beam search (also called as block-wise Best of N) is required.\n* Actionable insights is not clear. How can the theoretical bounds and observations here help developers obtain state of the art performance across reasoning benchmarks? \n* The narrative repeatedly generalizes that the verifier’s ROC “mediates” the coverage–sub-optimality trade-off, yet controlled experiments are limited to Qwen in the main text (Gemma/Llama only in appendix) and to one prompt. The strength of the claim should be toned down or supported with wider evidence.\n\nNote: I am willing to update my score based on the rebuttal.", "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": "TLPh4QbM0W", "reviewer": "Reviewer_NJAQ", "summary": "This paper provides a framework for understanding test-time verification in LLMs by framing it as an optimal transport problem. The authors identify three components they consider important in the problem of verified generation: \n\n(a) coverage, i.e. the generator's support over the solution space\n(b) verifier ROC, i.e. the region of convergence and selectivity of the verifier\n(c) sub-optimality, i.e. the algorithm's deviation from the optimal policy.\n\nThe authors model these factors as a transport problem and show three distinct \"regimes\": transport, policy improvement, and saturation. Then they analyze sequential and batch sampling algorithms and their computational trade-offs. The overarching goal of this paper is to understand and unify the empirical progress in test-time scaling on the one hand, and a mathematical framework describing how verification quality affects performance, on the other. \n\nThe authors show that verification helps only in certain regions of the coverage-suboptimality space. Concretely, in the policy improvement regime with moderate coverage, the verification yields the largest performance gains where it reduces sub-optimality.  The reason why verification helps is also analyzed.\n\nThat said, the practical implementation and the paper overall is outside of my area of expertise. I've alerted the ACs that I cannot judge this paper and giving it a confidence of 1.", "questions": "See summary.", "limitations": "", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "See summary.", "weaknesses": "See summary.", "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)