ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignment Yanxiao Liu1,⋆ , Sicheng Wan2,⋆ , and Deniz Gündüz1
arXiv:2609.21899v1 [cs.LG] 18 Sep 2026
1
Imperial College London, 2 University of Washington, ⋆ equal contribution
Abstract Best-of-n (BoN) sampling is a simple yet effective inferencetime alignment method, but hard maximization provides only coarse control over the trade-off between reward and distribution shift. Soft Best-of-n (Verdun et al. 2025) provides smoother control and converges to the optimal distribution associated with KL-regularized reward maximization. In this paper, we introduce ExpBoN, an alternative soft BoN method based on the exponential-noise report-noisy-max mechanism. It admits an exact finite-n decomposition, which yields exponentially fast convergence in total variation, expected reward, and both directions of KL divergence. We provide comprehensive theoretical analyses of its convergence and regret behavior. We further integrate ExpBoN into the guided speculative inference (GSI) framework (Geuter, Mroueh, and AlvarezMelis 2025), resulting in ExpGSI, for efficient reward-guided LLM alignment. ExpGSI yields substantial reductions in computational cost while maintaining comparable accuracy. Experiments on MATH500, MMLU-STEM, and Minerva Math with the Qwen2.5-Math and Qwen3 model families show that ExpGSI reduces estimated computation by 14%-39% across candidate budgets for Qwen2.5-Math and by up to 45% at n = 16 for Qwen3. Overall, our results provide a theoretical and algorithmic foundation for exponential-noise BoN and efficient test-time LLM alignment.
1
Introduction
Large language models (LLMs) are usually trained to predict the next token rather than to directly optimize human preferences. As a result, a pretrained model may generate responses that are inconsistent with the intended behavior (Bender et al. 2021; Bommasani et al. 2021). Alignment methods seek to modify the model distribution so that high-quality responses receive more probability while the aligned distribution remains close to the reference model. Training-time and posttraining alignment methods include Reinforcement Learning from Human Feedback (RLHF) (Christiano et al. 2017; Ouyang et al. 2022), SLiC (Zhao et al. 2022), and Direct Preference Optimization (Rafailov et al. 2023). In contrast, inference-time alignment is attractive because it can be applied without updating the base-model parameters and is often easier to deploy; examples include controlled decoding (Mudgal et al. 2024) and Best-of-n (BoN) sampling (Stiennon et al. 2020; Beirami et al. 2024). BoN sampling is a simple inference-time alignment
method that draws n candidates from a reference distribution P and returns the one with the largest reward. BoN requires no fine-tuning and often gives substantial reward improvements. Its performance has been shown to be empirically competitive with or superior to that of RLHF and other alignment schemes in terms of the reward-KL divergence tradeoff (Mudgal et al. 2024), and it asymptotically approximates the solution of the KL-regularized reward optimization problem (Yang et al. 2024b). Its theoretical properties, coverage, and optimality have been studied extensively (Beirami et al. 2024; Gui, Gârbacea, and Veitch 2024; Mroueh and Nitsure 2025; Amini et al. 2025; Huang et al. 2025; Sriraman and Block 2026), and it has been further applied to different scenarios (Sun et al. 2024; Raman, Asi, and Kale 2025; Jinnai et al. 2025; Kalayci, Raman, and Dughmi 2025; Ichihara et al. 2025; Kang, Zhao, and Song 2025; Kobayashi 2026; Mukherjee et al. 2026; Hsu, Lei, and Chen 2026). Nevertheless, vanilla BoN, which is usually called the hard BoN, has two limitations. First, the number of candidates n provides only coarse control: increasing n simultaneously increases reward optimization and distribution shift. Second, hard maximization can exploit errors in a learned proxy reward model. As the candidate pool becomes larger, the selected response may have a high proxy reward but a lower true reward, a phenomenon commonly known as reward hacking or overoptimization (Gao, Schulman, and Hilton 2023; Khalaf et al. 2025; Bu et al. 2025; Aminian et al. 2026). Soft Best-of-n (SBoN) was introduced to provide finer control over this trade-off (Verdun et al. 2025). Given samples iid X1 , . . . , Xn ∼ P , SBoN returns Xi with probability proporr(Xi )/λ tional to e , and hence interpolates between sampling from P and hard BoN. For every temperature λ, the output distribution of SBoN converges to the optimal target distribution (Csiszár 1975) as n grows. It was further analyzed by Aminian et al. (2026), who studied its KL divergence from the reference policy and its true-reward regret under proxy-reward misspecification. See also recent applications of SBoN on reward hacking (Khalaf et al. 2025), diffusion language models (Bu et al. 2026), and guided speculative inference (GSI) (Geuter, Mroueh, and Alvarez-Melis 2025). In this paper, we introduce an alternative soft BoN mechanism, called ExpBoN, that is more sample-efficient, converges to the optimal distribution geometrically, whereas the SBoN guarantees are polynomial. While SBoN can be shown
to be equivalent to report-noisy-max with Gumbel noise, our ExpBoN instead relies on report-noisy-max with exponential noise. The use of exponential noise is well known in differential privacy (McSherry and Talwar 2007; Dwork and Roth 2014), where it admits desirable stability and utility properties, and has recently been used in LLM decoding to achieve Pareto optimality in the stability-perplexity trade-off (Zhao, Li, and Wang 2025). SBoN is closely related to the Poisson functional representation (Li and El Gamal 2018), which is widely used in information theory (Liu and Li 2025; Liu, Advary, and Li 2026; Liu and Li 2024), and its connection to differential privacy has also been studied (Liu et al. 2024; Flamich et al. 2026). It was shown by Ding et al. (2021) to be equivalent to the permute-and-flip scheme (McKenna and Sheldon 2020). Here, we bring this idea to test-time LLM alignment, provide comprehensive theoretic analyses, and show that it has desirable properties for BoN sampling. In turn, it can be naturally integrated into the GSI framework (Geuter, Mroueh, and Alvarez-Melis 2025), making alignment and decoding even more efficient. In summary, our main contributions are as follows. • We introduce ExpBoN, a BoN mechanism that utilizes exponential-noise report-noisy-max, a simple yet powerful idea with various desirable properties. • We provide a comprehensive theoretical analysis of ExpBoN, including an exact decomposition property, exponentially fast convergence in both TV and KL divergences, and regret guarantees. • To further accelerate LLM test-time alignment and decoding, we integrate ExpBoN into the GSI framework (Geuter, Mroueh, and Alvarez-Melis 2025), a natural combination that yields substantial reductions in computational cost while achieving comparable accuracy.
2
BoN with Exponential Noise
Let a reference distribution P over finite X denote the distribution of an LLM’s responses to a prompt, and r : X → R denote a reward function that is nonconstant on XP := {x ∈ X : P (x) > 0} and serves as a scoring guide to evaluate the alignment of LLM’s responses with desired human values. The alignment problem aims to find a distribution P ⋆ that remains close to P to preserve model quality, while maximizing the expected reward to align with human preferences: max EP ⋆ [r(X)]
P ⋆ ∈∆(X )
subject to DKL (P ⋆ ∥P ) ≤ ϵ. This is equivalent to an information projection problem (Csiszár and Matus 2003), whose solution is known to be an exponentially tilted distribution (Csiszár 1975) that assigns greater weight to high-reward responses by tilting P . The optimal tilted distribution is Pλ⋆ (x) :=
P (x)er(x)/λ , EP [er(X)/λ ]
where λ > 0 is the temperature parameter that interpolates reward maximization and distribution divergence. See (Verdun et al. 2025) for more details.
However, in general we have neither access to an analytical expression for P nor to r(·), and therefore, we are unable to compute P ⋆ directly. We can only sample from P and evaluate r(X) for these samples. Accordingly, one simple yet effective test-time alignment scheme is BoN sampling (Stiennon et al. 2020), which draws n samples from P and selects the one with the highest reward. The BoN consists of: 1. Draw X1 , . . . , Xn i.i.d. from P ; 2. Compute rewards r(X1 ), . . . , r(Xn ); 3. Return Y = XK where K = arg maxk=1,...,n r(Xk ). In (Verdun et al. 2025), a more general framework, called soft BoN (SBoN), is proposed to provide a smoother approach that interpolates between reward maximization and distribution divergence. SBoN consists of: 1. Draw X1 , . . . , Xn i.i.d. from P ; 2. Compute rewards r(X1 ), . . . , r(Xn ); 3. Draw K from {1, . . . , n} with respect to er(Xi )/λ Pr(K = i) = Pn , r(Xj )/λ j=1 e
(1)
and return Y = XK . We can see that SBoN recovers BoN as λ → 0. It can be shown that (Appendix 7.6) the last step above, which samples according to (1), is equivalent to report-noisy-max with Gumbel noise (Gumbel 1954; Huijben et al. 2022; Li and El Gamal 2018), i.e., taking Y = XK , where r(Xk ) + Gk , K = arg max k=1,...,n λ and Gk ∼ Gumbel(0, 1) are independent of each other. We introduce an alternative soft version of BoN sampling that utilizes exponential noise rather than Gumbel noise: Exponential-Noise Best-of-n (ExpBoN) 1. Draw X1 , . . . , Xn i.i.d. from P ; 2. Compute rewards r(X1 ), . . . , r(Xn ); 3. Draw E1 , . . . , En i.i.d. from Exp(1), independently; 4. Return Y = XK , where r(Xk ) K = arg max + Ek . k=1,...,n λ The scheme has the same candidate-generation and reward-evaluation procedure as BoN and SBoN, and the same limiting behavior: when n = 1 or λ → ∞, the output follows P ; when λ ↓ 0, it approaches hard BoN; and, for every fixed λ > 0, it converges to the tilted target Pλ⋆ as n → ∞. The difference is that utilizing the exponential noise creates an exact tilted component at finite n, which in turn provides advantages in both theoretic foundation and experiments.
3
Theoretic Guarantees
We provide comprehensive theoretical analyses of ExpBoN, and compare to BoN and SBoN (Verdun et al. 2025) baselines. We derive an exact finite-n decomposition representation of ExpBoN, which shows an exponential convergence to the optimal distribution, rather than O(1/n) rate by SBoN.
3.1
Exact Decomposition and Convergence
Theorem 3.3 (Reward convergence). For n ≥ 1 and λ > 0, 0 ≤ EPλ⋆ [r(X)] − EPen,λ [r(X)] ≤ ∆r ρnλ where ∆r := rmax − rmin . For every λ > 0, EPen,λ [r(X)] is nondecreasing in n, and converges to EPλ⋆ [r(X)] as n → ∞. Define the centered reward r(x) := r(x) − rmin , we have: Corollary 3.4. For every n ≥ 1 and λ > 0,
For k = 1, . . . , n and Ek ∼ Exp(1), we denote Mn := max Tk k=1,...,n
where
The following exact decomposition of the ExpBoN distribution serves as the basis for most of the subsequent results. Theorem 3.1. For every n ≥ 1, λ > 0, there exists a distribution Qn,λ on XP such that the ExpBoN output distribution Pen,λ = (1 − ρnλ ) Pλ⋆ + ρnλ Qn,λ , where ρλ := 1−EP e(r(X)−rmax )/λ , rmax := maxx r(x). In comparison, SBoN only admits finite-sample approximation bounds (Verdun et al. 2025, Lemma 1). We call αn,λ := 1 − ρnλ as the tilted-hit probability. It is the probability of the coupling event Mn ≥ smax , conditional on which the ExpBoN output law is exactly Pλ⋆ . For a fixed temperature λ, increasing n increases the weight of the exact tilted component. The exact decomposition leads to tight TV and KL guarantees for ExpBoN. Unlike Verdun et al. (2025), we provide results for both the forward and reverse KL divergences. Theorem 3.2. For every n ≥ 1 and λ > 0, assuming r is not constant on XP , we have qλ ρnλ ≤ TV Pλ⋆ , Pen,λ ≤ ρnλ , −1 ⋆ 2n e 2qλ2 ρ2n , λ ≤ DKL Pn,λ ∥Pλ ≤ log 1 + pmin,λ − 1 ρλ n ⋆ e 2qλ2 ρ2n − log αn,λ , λ ≤ DKL Pλ ∥Pn,λ ≤ min o 2n p−1 − 1 ρ α , n,λ λ min,λ where qλ := Pλ⋆ ({x : r(x) = rmax }) and pmin,λ := minx∈XP Pλ⋆ (x); and therefore, we have, as n → ∞, TV Pλ⋆ , Pen,λ = Θ(ρnλ ), DKL Pλ⋆ ∥Pen,λ = Θ(ρ2n λ ), 2n ⋆ DKL Pen,λ ∥Pλ = Θ(ρλ ). S Compared to SBoN, which only has DKL (Pλ⋆ ∥Pn,λ ) = O(1/n) (Verdun et al. 2025), for every finite (P, r, λ), ExpBoN improves these polynomial convergence rates.
3.2
0≤
Tk := r(Xk )/λ + Ek .
Reward and KL Convergence
We then study how finite-n ExpBoN approaches the tilted target in expected reward and in the KL-regularized objective. We provide a one-sided reward guarantee and show that the expected reward improves monotonically with samples.
EPλ⋆ [r(X)] − EPen,λ [r(X)] EPλ⋆ [r(X)]
≤ ρnλ .
Compared to Verdun et al. (2025, Theorem 3), which provided an O(1/n) relative-reward guarantee for SBoN, Corollary 3.4 gives an exponential O(ρnλ ) guarantee. The following result shows that the policy-to-reference KL of finite-n ExpBoN approaches that of the ideal tilted policy. Corollary 3.5. For every n ≥ 1 and λ > 0, ∆r n DKL Pλ⋆ ∥P − ρλ ≤ DKL Pen,λ ∥P λ 2n ≤ DKL Pλ⋆ ∥P + log 1 + (p−1 min,λ − 1)ρλ . This shows that ExpBoN approaches the reward and reference-KL coordinates of the optimal tilted policy exponentially fast; we can also derive a distribution-free form DKL Pen,λ ∥P ≤ min log n, ∆2r /(2λ2 ) , which has the correct quadratic order near the reference regime, whereas Aminian et al. (2026, Lemma 4.1) is linear in the inverse temperature.
3.3
Results via Permute-and-Flip
As discussed previously, report-noisy-max with exponential noise is equivalent to permute-and-flip (McKenna and Sheldon 2020; Ding et al. 2021), which enjoys desirable properties. Here, we utilize them to establish the following result. Theorem 3.6 (Utility Dominance). For every n ≥ 1, λ > 0, and candidates x1:n = (x1 , . . . , xn ), let KE and KS denote the indices selected by ExpBoN and SBoN, respectively. Then E [r(XKE ) | X1:n = x1:n ] ≥ E [r(XKS ) | X1:n = x1:n ] . Consequently, SBoN [r(X)]. EPen,λ [r(X)] ≥ EPn,λ
ExpBoN inherits the Pareto-optimality of permute-andflip (McKenna and Sheldon 2020): within the equally stable candidate-level schemes, no one can uniformly improve the expected selection reward of ExpBoN over all reward vectors.
3.4
Regret Analysis
While the preceding results characterize how accurately finite-n ExpBoN approaches a prescribed distribution, this target may be defined using an imperfect proxy reward. Faster convergence does not by itself guarantee better true-reward performance and may amplify reward over-optimization. We therefore study the true-reward regret of ExpBoN, in parallel with the regret analysis of SBoN by Aminian et al. (2026).
(a) Target KL, λ = 0.5
(b) Relative reward, λ = 0.5
10−4 10−6 10−8 10−10
ExpBoN: exact SBoN: exact
10−12
ExpBoN upper bound ExpBoN lower bound
10−14
SBoN upper bound 0
10
100
10−1 10−2 10−3 10−4 10−5
ExpBoN: exact SBoN: exact
10−6
ExpBoN bound ρλn
50
0
10
10−2 10−4 10−6 10−8 10−10 −12
10−14
20 30 40 Candidate number n
ExpBoN: exact finite-n loss SBoN: exact finite-n loss
10
SBoN bound
10−7
20 30 40 Candidate number n
Finite-n regret contribution
Relative centered-reward gap
10−2
DKL(Pλ⋆ ‖Pn, λ)
(c) Coverage terms, C∞, p = 20
100
100
50
ExpBoN coverage term SBoN certificate term 10
20
30 40 50 Candidate number n
60
70
Figure 1: Finite-n comparison of ExpBoN and SBoN on the example P = (0.75, 0.20, 0.05). Panels (a) and (b) use r = (0.016, 0.164, 0.820) and λ = 0.5. Panel (a) compares the KL divergences with the ExpBoN bounds in Theorem 3.2 and the O(1/n) SBoN bound. Panel (b) compares the relative centered-reward gaps with the ExpBoN bound ρnλ from Corollary 3.4 and the corresponding O(1/n) SBoN bound. Panel (c) uses r as the true reward and rp = r + 0.1(1, 0, −1) as the proxy reward at λ = 0.5, and compares the exact finite-n true-reward losses from the common proxy-tilted limit with the ExpBoN bound in Theorem 3.9 and the SBoN bound. The results show the exponential rates of ExpBoN in contrast to SBoN’s polynomial bounds. Suppose the proxy reward and the true reward are rp and u rt , respectively. For u ∈ {p, t}, let Pen,λ be the ExpBoN output distribution when ru is used, and define ⋆ Pλ,u (x) :=
P (x)eru (x)/λ . EP [eru (X)/λ ]
Let d(x) := rt (x) − rp (x) and define the centered rewarderror quantity ωd := maxx∈XP d(x) − minx∈XP d(x). Theorem 3.7 (Proxy-Reward Stability). The ExpBoN policies induced by the true and proxy rewards satisfy n o p p t t max DKL Pen,λ ∥Pen,λ , DKL Pen,λ ∥Pen,λ ω o n (n − 1) Var (d(X)) ω d d P , tanh ≤ min , λ2 λ 2λ and also the TV guarantee p t , Pen,λ TV Pen,λ (r ) ω (n − 1) VarP (d(X)) d ≤ min , tanh ,1 . 2λ2 2λ In comparison, Aminian et al. (2026, Lemma 4.2) analyzed the true-versus-proxy SBoN policy using an uncentered exponential mean-square error. Theorem 3.7 can be sharper for small centered errors, though there is no uniform dominance. We then provide guarantees for the regret of ExpBoN. We first define ∆t := maxx∈XP rt (x) − minx∈XP rt (x) and Regn,λ := rt,max − EPep [rt (X)]. n,λ
Theorem 3.8 (Direct Regret Bound). For every n ≥ 1 and λ > 0, i h ω d n + ρλ,p , Regn,λ ≤ Bt (λ) + ∆t tanh 4λ ⋆ [rt (X)] is the softening bias of where Bt (λ) := rt,max −EPλ,t the true tilted policy and ρλ,u := 1−EP e(ru (X)−ru,max )/λ is the tilted-hit failure probability associated with reward ru .
Theorem 3.8 separates the total regret into softening bias, proxy-target mismatch, and a finite-n target-approximation term. The last term is advantageous when the proxy-tilted target is trustworthy; under severe proxy misspecification, faster target approximation need not imply better true reward. Aminian et al. (2026) studied the special scenario where 0 ≤ rt (x), rp (x) ≤ Rmax for all x ∈ XP . Here we define: (d(X) − c)2 ελ := inf λ log EP exp , c∈R λ which measures the proxy-reward error, and we have: Theorem 3.9 (Coverage-Based Regret Bound). For every n ≥ 1 and λ > 0, p √ p C∞,t + C∞,p + λ log C∞,t Regn,λ ≤ ελ n 1 + Rmax 1 − . C∞,p where C∞,u := P ({x ∈ XP : ru (x) = ru,max })−1 . Aminian et al. (2026, Theorem 5.2) gives the same rewardmodel-error and regularization-bias structure, but its displayed finite-n term is O(n−1/2 ) for fixed coverage, whereas n
1 the corresponding ExpBoN term is Rmax 1 − C∞,p . Therefore, making the finite-n term at most η needs n = O C∞,p log Rmax for ExpBoN, compared with n = η 2 Rmax (C∞,p −1) O for the SBoN (Aminian et al. 2026). η2
Numerical Example We use the example same in Verdun et al. (2025, Figure 1) to verify our theorems. Consider P = (0.75, 0.20, 0.05),
r = (0.016, 0.164, 0.820).
At λ = 0.5, we obtain the parameter ρλ = 0.745928 and Pλ⋆ = (0.591233, 0.211972, 0.196795). For every n, we compute and compare the finite-n SBoN and ExpBoN
marginal distributions. For example, at n = 10, we have DKL Pλ⋆ ∥Pe10,λ = 3.58 × 10−4 , SBoN DKL Pλ⋆ ∥P10,λ = 6.16 × 10−3 , and the relative centered reward gaps are 0.0423 and 0.1706, respectively. The theoretical results are compared in Figure 1. The same separation holds on empirical candidate pools generated by the draft model in the experiments of Section 5, both for reward-only scores and for the clipped score used by ExpGSI (Appendix 7.8, Figure 3).
4
ExpBoN with GSI
GSI (Geuter, Mroueh, and Alvarez-Melis 2025) accelerates test-time alignment with SBoN by using a small draft model πS to propose candidate reasoning steps and a large base model πB , together with a likelihood-ratio-corrected reward, to verify and select among them, thereby reducing the cost of generating every candidate autoregressively with πB . In this section, we show that ExpBoN, which admits an exact finite-n decomposition and the resulting desirable properties, is a natural replacement for the SBoN component in the GSI pipeline. It preserves the same optimal tilted target distribution while offering geometrically faster finitecandidate convergence and an exact, distribution-preserving early-stopping implementation based on truncated rejection sampling. Our experiments demonstrate substantial computational savings without sacrificing answer accuracy. We first briefly review the GSI pipeline (Geuter, Mroueh, and Alvarez-Melis 2025). At each reasoning state h, with draft model πS (· | h) and base model πB (· | h), the original GSI applies SBoN to a modified score r(h, y) + d(h, y)/β (y|h) where d(h, y) := log ππBS (y|h) and β > 0 is a parameter that trades off maximizing the reward versus fidelity to πB . We then explain our strategy. We replace the SBoN component by ExpBoN and consider a clipped reward: sC (h, y) := βr(h, y) + min{d(h, y), C}, with a fixed C > 0. The clipping trick solves the issue that the likelihood-ratio d(h, y) may not have a finite upper bound, and has also been used in (Sriraman and Block 2026) for analyzing BoN schemes. If r(h, y) ≤ R, then sC (h, y) ≤ UC := βR + C provides an envelope for the ExpBoN. Clipping generally changes the original limiting tilted target, but its effect can be separated from the finite-candidate approximation error and provably bounded by Theorem 4.1, as will be elaborated later. We note that the clipping technique can also be employed in the original GSI framework with SBoN; what makes it special here is its natural connection to ExpBoN, whose exact decomposition yields both geometric finite-candidate approximation and a distributionpreserving early-exit implementation, as elaborated below. ⋆ Denoting the target tilted distribution by πβ,C (y | h), the ExpBoN exact decomposition property to the clipped score sC (h, y) gives an output distribution π en,β,C (· | h) as ⋆ (1 − ρβ,C (h)n ) πβ,C (· | h) + ρβ,C (h)n Qn,β,C (· | h) where ρβ,C (h) := 1−EπS esC (h,Y )−UC and Qn,β,C (· | h) is some residual distribution. The hit branch has a rejectionsampling representation: draw a draft candidate Y ∼ πS (· |
Algorithm 1: ExpBoN-based GSI Input: State h; draft policy πS ; base policy πB ; reward model r; candidate count n; first-batch size b; inverse temperature β; clipping level C; reward upper bound R; GSI threshold u Output: Selected reasoning step iid
1: Sample y1 , . . . , yn ∼ πS (· | h) and record ℓS,i ←
log πS (yi | h) 2: Sample an independent random permutation σ of
{1, . . . , n} and independent Ei ∼ Exp(1) 3: UC ← βR + C 4: Form batches B1 ← the first b indices of the permuted
order, B2 ← the remaining n − b 5: for j = 1, 2 do 6: Evaluate, in parallel for i ∈ Bj ,
ri ← r(h, yi ),
ℓB,i ← log πB (yi | h)
7: di ← ℓB,i − ℓS,i and sC,i ← βri + min{di , C} 8: Hj ← {i ∈ Bj : sC,i + Ei ≥ UC } 9: if Hj ̸= ∅ then 10: i⋆ ← arg mini∈Hj σ −1 (i) 11: go to Line 15 12: end if 13: end for 14: i⋆ ← arg maxi=1,...,n {sC,i + Ei } 15: rei⋆ ← ri⋆ + di⋆ /β 16: if rei⋆ ≥ u then 17: return yi⋆ 18: else 19: Run the configured base-model GSI fallback 20: end if
h) and accept it with probability esC (h,Y )−UC ; conditional on ⋆ acceptance, Y is an exact sample from πβ,C (· | h). Moreover, by exponential memorylessness, conditional on crossing the threshold, the overshoot sC (h, Y )+E −UC is Exp(1) and is independent of Y ; therefore, selecting the largest overshoot, as full ExpBoN does, and selecting the first accepted proposal in an independent random order induce the same hit-branch law. Thus, clipped ExpBoN can be implemented as a truncated rejection sampler: return the first accepted proposal in an independent random order if any of the n proposals is accepted, and otherwise evaluate all candidates and return the exponential-noise maximizer. Overall, it is provably an exact finite-n clipped ExpBoN sampler. By contrast, under Gumbel noise the analogous fixed-threshold crossing probability 1 − exp −esi −U is not proportional to esi , so the same first-crossing construction would not exactly preserve the SBoN sampling (Verdun et al. 2025). Recall the optimal distribution and the output law of ⋆ clipped ExpBoN are denoted by πβ,C (· | h) and π en,β,C (· | h), respectively. We give the following theoretical guarantee: Theorem 4.1. For every n ≥ 1, ⋆ TV π en,β,C (· | h), πβ,B (· | h) ≤ ρβ,C (h)n + τC (h) (2) C−d(h,y) ⋆ where τC (h) := Eπβ,B . Con(·|h) 1 − min 1, e
Figure 2: Compute–accuracy planes at each candidate budget n (Qwen2.5-Math; macro average over MATH500, MMLUSTEM, and Minerva Math; 3-seed means). Arrows mark the GSI → ExpGSI reduction in estimated compute. ExpGSI maintains accuracy comparable to GSI at every n while its compute saving widens monotonically with n, from 14% at n=2 to 39% at n=16; full metrics for both model families are reported in Table 1. sequently, for every bounded function g, ⋆ Eπen,β,C (·|h) [g(Y )] − Eπβ,B (·|h) [g(Y )] ≤ sup g(y) − inf g(y) (ρβ,C (h)n + τC (h)) . (3)
y
y
Theorem 4.1 separates the geometric finite-candidate error ρβ,C (h)n from the nonvanishing clipping bias τC (h). Increasing n reduces only the former, while increasing C is required to reduce the distortion of the original GSI target.
5
Experiments
Models and benchmarks. We evaluate ExpGSI on two draft–target pairs: the math-specialized Qwen2.5-Math family (Yang et al. 2024a) (1.5B-Instruct draft, 7B-Instruct target) and the general-purpose Qwen3 family (Yang et al. 2025) (1.7B draft, 14B target, thinking mode disabled), both with Qwen2.5-Math-PRM-7B as the process reward model (r ∈ [0, 1]) and both matching the configurations of GSI’s evaluation (Geuter, Mroueh, and Alvarez-Melis 2025). The three benchmarks span complementary domains, answer formats, and difficulty: MATH500 (Lightman et al. 2024) (indomain competition math), MMLU-STEM (Hendrycks et al. 2020) (multiple-choice STEM, outside the PRM’s training domain), and Minerva Math (Lewkowycz et al. 2022) (harder university-level problems). We fix 400-problem subsets for the first two and use Minerva’s full 272 problems; identical problems and seeds across methods and budgets enable paired comparisons. Baselines. We compare against GSI (Geuter, Mroueh, and Alvarez-Melis 2025) and the three baselines of its primary evaluation: S-BoN(πS ) and S-BoN(πB ), stepwise soft bestof-n over candidates generated entirely by the draft or the target policy (the cost floor and the quality reference, respectively), and RSD (Liao et al. 2025), which keeps a draft step if its reward clears a binary threshold and otherwise resamples from πB . Since original RSD is not defined for the shared n-candidate protocol, we adopt the instantiation from GSI’s
evaluation. All methods share the same PRM, candidate budgets, evaluation subsets, and generation settings. Default settings and metrics. All models are served as vLLM (Kwon et al. 2023) instances on NVIDIA A100 GPUs. We report final-answer accuracy, wall-clock time per reasoning step, acceptance (the fraction of steps resolved with a draft candidate rather than a target-policy fallback), and estimated TFLOPs per problem under the FLOPs accounting of RSD (Liao et al. 2025): 2× parameters per processed token, summed over the forward passes actually executed. All methods share the decoding hyperparameters of GSI; the only hyperparameter ExpGSI adds, the clipping level C, is calibrated once and held fixed across all benchmarks, budgets, and both model families. Full implementation details are given in Appendix 7.7.
5.1
Main Results
ExpGSI is consistently cheaper than GSI, and the margin grows with n. Figure 2 summarizes our main result on the compute–accuracy plane, one panel per candidate budget: at every budget, ExpGSI reaches GSI’s accuracy at strictly lower compute. The gap widens steadily with the budget: ExpGSI saves 14%, 23%, 31%, and 39% of GSI’s estimated compute at n = 2, 4, 8, and 16, with time per step dropping by 18% at n=16 (Table 1; per-benchmark tables in Appendix 7.8). At n=16 the compounding is strong enough that ExpGSI’s cost falls below even RSD (999 vs. 1164 TFLOPs per problem) and the draft-only S-BoN(πS ) (1182), while scoring 1.2–1.6 points higher than either. ExpGSI has accuracy matched to GSI. The acceleration costs essentially no accuracy. Across the four operating points in Table 1, macro-average accuracy differs from GSI by at most 0.8 points, with no consistent sign: ExpGSI is ahead at Qwen3 n=16 and equal or marginally behind elsewhere, all within seed-level variation. Acceptance rates agree to within 0.3 points throughout, so the early exit leaves the accept/fallback behavior of the underlying sampler essen-
Model family
n
Method
Acc. (%)
4
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
55.9 ± 0.5 0.49 ± 0.01 57.3 ± 1.2 0.58 ± 0.01 62.1 ± 0.4 1.06 ± 0.01 59.9 ± 0.6 0.87 ± 0.01 59.9 ± 0.8 0.84 ± 0.02
– 95.7 ± 0.2 – 82.1 ± 0.2 81.9 ± 0.4
252 ± 6 257 ± 7 297 ± 6 370 ± 5 285 ± 4
S-BoN (πS ) RSD† 16 S-BoN (πB ) GSI ExpGSI (ours)
58.1 ± 0.2 1.05 ± 0.01 58.5 ± 1.0 1.17 ± 0.03 62.5 ± 0.2 1.84 ± 0.05 60.1 ± 0.5 1.71 ± 0.03 59.7 ± 0.8 1.40 ± 0.01
– 97.3 ± 0.2 – 88.8 ± 0.3 88.7 ± 0.4
1182 ± 16 1164 ± 37 1258 ± 13 1627 ± 23 999 ± 24
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
54.5 ± 0.5 0.28 ± 0.00 55.8 ± 0.2 0.31 ± 0.00 66.0 ± 0.5 0.78 ± 0.00 61.2 ± 0.3 0.60 ± 0.00 60.4 ± 0.0 0.55 ± 0.00
– 97.7 ± 0.0 – 89.4 ± 0.1 89.5 ± 0.0
521 ± 1 541 ± 3 642 ± 8 1202 ± 9 891 ± 2
S-BoN (πS ) RSD† 16 S-BoN (πB ) GSI ExpGSI (ours)
54.8 ± 0.1 0.71 ± 0.00 56.9 ± 1.4 0.74 ± 0.00 65.9 ± 0.0 1.34 ± 0.00 61.0 ± 0.1 1.50 ± 0.01 61.8 ± 0.6 1.05 ± 0.00
– 98.5 ± 0.0 – 92.7 ± 0.1 93.0 ± 0.3
2183 ± 4 2203 ± 19 2565 ± 34 5769 ± 40 3169 ± 6
Qwen2.5-Math(1.5b/7b/7b)
4 Qwen3 (1.7b/14b/7b)
Time/step (s) Accept. (%) Est. TFLOPs/prob.
Table 1: Macro-average results over MATH500, MMLU-STEM, and Minerva Math and multiple seeds. ExpGSI maintains accuracy and acceptance comparable to GSI while reducing time and computation. At n = 16 it reduces time and TFLOPs by 18% and 39% for Qwen2.5-Math, and by 30% and 45% for Qwen3. Bold values indicate ExpGSI efficiency improvements over GSI. † RSD follows the GSI implementation and hyperparameter configuration.
tially untouched. Such lossless acceleration is not a given: RSD, the existing reward-gated accelerator, buys its speed with accuracy, scoring 1.2–4.9 macro points below ExpGSI across the four operating points. Among all baselines, only SBoN(πB ) is more accurate than the tilted pair, and it occupies a different design point: every token is generated by the target policy, at the highest step latency of all methods (1.84 s vs. ExpGSI’s 1.40 s at Qwen2.5, n=16). ExpGSI thus retains the design point of GSI–draft-side generation with target-aware selection–while making it strictly cheaper.
Sensitivity to the clipping level. The clipping level C is the only hyperparameter ExpGSI adds, trading fidelity to the GSI selection rule against early-exit efficiency. Sweeping C on MATH500 at n=16 leaves accuracy within seed-level noise for C between 0.5× and 1.5× the calibrated value, with a mild drop only at 2×, while estimated computation increases with C; C=∞ disables early exit and recovers the full-scan cost. Detailed results are in Appendix 7.8.
Generalization to Qwen3. We repeat the comparison with the general-purpose Qwen3 (Yang et al. 2025) pair at n ∈ {4, 16} with two random seeds, reusing the clipping level asis–no additional tuning. As Table 1 shows, the picture carries over: accuracy and acceptance stay at GSI’s level, while the n=16 compute saving grows from 39% (Qwen2.5) to 45%, consistent with the cost structure of early exit–the larger the target, the larger the share of GSI’s cost spent on the avoided evaluations. The result also shows that ExpGSI does not rely on math-specialized policies.
We introduced ExpBoN, an exponential-noise alternative to soft Best-of-n sampling for inference-time alignment. Its exact finite-n tilted decomposition yields geometric convergence to the target distribution and desirable regret guarantees. We further integrated ExpBoN into guided speculative inference, resulting in ExpGSI, which substantially accelerates LLM alignment, as validated by experiments. We discuss several future directions. First, the connection between ExpBoN and Permute-and-Flip (Zhao, Li, and Wang 2025) opens a natural path toward jointly performing alignment and watermarking, whose tradeoff has recently been investigated by Verma, Phan, and Trivedi (2026). Second, under proxy-reward misspecification, faster convergence may approach an overoptimized target more rapidly, and it is therefore useful to combine ExpBoN with reward-hacking mitigation methods (Khalaf et al. 2025). Finally, SBoN has recently been employed in diffusion language models (Bu et al. 2026), and it is of interest to investigate the use of ExpBoN in this setting as well.
5.2
Ablation and Robustness Analysis
Robustness to the reward model. We replace the 7B math-specialized PRM with the smaller, general-purpose Skywork-o1-Open-PRM-Qwen-2.5-1.5B (Team 2024)–the reference PRM of RSD (Liao et al. 2025). The conclusions carry over: accuracy and acceptance stay at GSI’s level, ExpGSI still reduces the estimated computation of GSI, and it remains ahead of RSD in accuracy. Complete results are given in Appendix 7.8.
6
Conclusion and Future Work
References Amini, A.; Vieira, T.; Ash, E.; and Cotterell, R. 2025. Variational best-of-n alignment. In International Conference on Learning Representations (ICLR). Aminian, G.; Shenfeld, I.; Asadi, A. R.; Beirami, A.; and Mroueh, Y. 2026. Best-of-N through the smoothing lens: KL divergence and regret analysis. In International Conference on Learning Representations. Beirami, A.; Agarwal, A.; Berant, J.; D’Amour, A.; Eisenstein, J.; Nagpal, C.; and Suresh, A. T. 2024. Theoretical guarantees on the best-of-n alignment policy. arXiv preprint arXiv:2401.01879. Bender, E. M.; Gebru, T.; McMillan-Major, A.; and Shmitchell, S. 2021. On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, 610–623. Bommasani, R.; Hudson, D. A.; Adeli, E.; Altman, R.; Arora, S.; von Arx, S.; Bernstein, M. S.; Bohg, J.; Bosselut, A.; Brunskill, E.; et al. 2021. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258. Bu, D.; Huang, W.; Han, A.; Nitanda, A.; Xue, B.; Zhang, Q.; Wong, H.-S.; and Suzuki, T. 2025. Consistency Is Not Always Correct: Towards Understanding the Role of Exploration in Post-Training Reasoning. arXiv e-prints, arXiv:2511.07368. Bu, D.; Huang, W.; Han, A.; Wong, H.-S.; Zhang, Q.; Suzuki, T.; and Nitanda, A. 2026. DPRM: A Plug-in Token-Ordering Module for Diffusion Language Models. arXiv preprint arXiv:2604.24357. Christiano, P. F.; Leike, J.; Brown, T.; Martic, M.; Legg, S.; and Amodei, D. 2017. Deep reinforcement learning from human preferences. Advances in Neural Information Processing Systems, 30. Csiszár, I. 1975. I-divergence geometry of probability distributions and minimization problems. The annals of probability, 146–158. Csiszár, I.; and Matus, F. 2003. Information projections revisited. IEEE Transactions on Information Theory, 49(6): 1474–1490. Ding, Z.; Kifer, D.; Steinke, T.; Wang, Y.; Xiao, Y.; and Zhang, D. 2021. The permute-and-flip mechanism is identical to report-noisy-max with exponential noise. arXiv preprint arXiv:2105.07260. Dwork, C.; and Roth, A. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4): 211–407. Flamich, G.; Güner, O. S.; Liu, Y.; and Gündüz, D. 2026. Scalable Differentially Private Data Compression via Diffusion and Stochastic Codes. arXiv preprint arXiv:2607.03392. Gao, L.; Schulman, J.; and Hilton, J. 2023. Scaling Laws for Reward Model Overoptimization. In Proceedings of the 40th International Conference on Machine Learning, 10835– 10866.
Geuter, J.; Mroueh, Y.; and Alvarez-Melis, D. 2025. Guided speculative inference for efficient test-time alignment of llms. arXiv preprint arXiv:2506.04118. Gui, L.; Gârbacea, C.; and Veitch, V. 2024. Bonbon alignment for large language models and the sweetness of bestof-n sampling. Advances in Neural Information Processing Systems, 37: 2851–2885. Gumbel, E. J. 1954. Statistical theory of extreme values and some practical applications: a series of lectures, volume 33. US Government Printing Office. Hendrycks, D.; Burns, C.; Basart, S.; Zou, A.; Mazeika, M.; Song, D.; and Steinhardt, J. 2020. Measuring massive multitask language understanding. arXiv preprint arXiv:2009.03300. Hsu, H.; Lei, E.; and Chen, C.-F. 2026. Best-of-Tails: Bridging Optimism and Pessimism in Inference-Time Alignment. arXiv preprint arXiv:2603.06797. Huang, A.; Block, A.; Liu, Q.; Jiang, N.; Krishnamurthy, A.; and Foster, D. J. 2025. Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment. arXiv preprint arXiv:2503.21878. Huijben, I. A.; Kool, W.; Paulus, M. B.; and Van Sloun, R. J. 2022. A review of the gumbel-max trick and its extensions for discrete stochasticity in machine learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2): 1353–1371. Ichihara, Y.; Jinnai, Y.; Morimura, T.; Abe, K.; Ariu, K.; Sakamoto, M.; and Uchibe, E. 2025. Evaluation of Bestof-N Sampling Strategies for Language Model Alignment. Transactions on Machine Learning Research. Jinnai, Y.; Morimura, T.; Ariu, K.; and Abe, K. 2025. Regularized best-of-n sampling with minimum bayes risk objective for language model alignment. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), 9321–9347. Kalayci, Y.; Raman, V.; and Dughmi, S. 2025. Optimal Stopping vs Best-of-N for Inference Time Optimization. arXiv preprint arXiv:2510.01394. Kang, Z.; Zhao, X.; and Song, D. 2025. Scalable bestof-n selection for large language models via self-certainty. Advances in Neural Information Processing Systems, 38: 19720–19745. Khalaf, H.; Mayrink Verdun, C.; Oesterling, A.; Lakkaraju, H.; and Calmon, F. 2025. Inference-time reward hacking in large language models. Advances in Neural Information Processing Systems, 38: 61720–61760. Kobayashi, T. 2026. Flexible Empowerment at Reasoning with Extended best-of-n Sampling. arXiv preprint arXiv:2604.15614. Kwon, W.; Li, Z.; Zhuang, S.; Sheng, Y.; Zheng, L.; Yu, C. H.; Gonzalez, J.; Zhang, H.; and Stoica, I. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium on operating systems principles, 611–626.
Lewkowycz, A.; Andreassen, A.; Dohan, D.; Dyer, E.; Michalewski, H.; Ramasesh, V.; Slone, A.; Anil, C.; Schlag, I.; Gutman-Solo, T.; et al. 2022. Solving quantitative reasoning problems with language models. Advances in Neural Information Processing Systems, 35: 3843–3857. Li, C. T.; and El Gamal, A. 2018. Strong functional representation lemma and applications to coding theorems. IEEE Transactions on Information Theory, 64(11): 6967–6978. Liao, B.; Xu, Y.; Dong, H.; Li, J.; Monz, C.; Savarese, S.; Sahoo, D.; and Xiong, C. 2025. Reward-guided speculative decoding for efficient llm reasoning. arXiv preprint arXiv:2501.19324. Lightman, H.; Kosaraju, V.; Burda, Y.; Edwards, H.; Baker, B.; Lee, T.; Leike, J.; Schulman, J.; Sutskever, I.; and Cobbe, K. 2024. Let’s verify step by step. In International Conference on Learning Representations, volume 2024, 39578– 39601. Liu, Y.; Advary, S. H.; and Li, C. T. 2026. Nonasymptotic Oblivious Relaying and Variable-Length Noisy Lossy Source Coding. IEEE Transactions on Information Theory, 72(6): 4555–4564. Liu, Y.; Chen, W.-N.; Özgür, A.; and Li, C. T. 2024. Universal Exact Compression of Differentially Private Mechanisms. Advances in Neural Information Processing Systems, 37: 91492–91531. Liu, Y.; and Li, C. T. 2024. One-Shot Information Hiding. In 2024 IEEE Information Theory Workshop (ITW), 169–174. IEEE. Liu, Y.; and Li, C. T. 2025. One-shot coding over general noisy networks. IEEE Transactions on Information Theory, 71(11): 8346–8357. McKenna, R.; and Sheldon, D. R. 2020. Permute-and-flip: A new mechanism for differentially private selection. Advances in Neural Information Processing Systems, 33: 193–203. McSherry, F.; and Talwar, K. 2007. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), 94–103. IEEE. Mroueh, Y.; and Nitsure, A. 2025. Information Theoretic Guarantees For Policy Alignment In Large Language Models. Transactions On Machine Learning Research. Mudgal, S.; Lee, J.; Ganapathy, H.; Li, Y.; Wang, T.; Huang, Y.; Chen, Z.; Cheng, H.-T.; Collins, M.; Strohman, T.; Chen, J.; Beutel, A.; and Beirami, A. 2024. Controlled Decoding from Language Models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, 36486–36503. PMLR. Mukherjee, A.; Bullo, M.; Basu, D.; and Gündüz, D. 2026. Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimality. In International Conference on Learning Representations (ICLR). Ouyang, L.; Wu, J.; Jiang, X.; Almeida, D.; Wainwright, C.; Mishkin, P.; Zhang, C.; Agarwal, S.; Slama, K.; Ray, A.; et al. 2022. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730–27744.
Rafailov, R.; Sharma, A.; Mitchell, E.; Manning, C. D.; Ermon, S.; and Finn, C. 2023. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36: 53728–53741. Raman, V.; Asi, H.; and Kale, S. 2025. AdaBoN: Adaptive best-of-n Alignment. arXiv preprint arXiv:2505.12050. Sriraman, V.; and Block, A. 2026. Revisiting the (Sub) Optimality of best-of-n for Inference-Time Alignment. arXiv preprint arXiv:2603.05739. Stiennon, N.; Ouyang, L.; Wu, J.; Ziegler, D.; Lowe, R.; Voss, C.; Radford, A.; Amodei, D.; and Christiano, P. F. 2020. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33: 3008–3021. Sun, H.; Haider, M.; Zhang, R.; Yang, H.; Qiu, J.; Yin, M.; Wang, M.; Bartlett, P.; and Zanette, A. 2024. Fast best-ofn decoding via speculative rejection. Advances in Neural Information Processing Systems, 37: 32630–32652. Team, S. 2024. Skywork-o1 open series. https://huggingface. co/Skywork. Verdun, C. M.; Oesterling, A.; Lakkaraju, H.; and Calmon, F. P. 2025. Soft Best-of-n Sampling for Model Alignment. In 2025 IEEE International Symposium on Information Theory (ISIT), 1–6. IEEE. Verma, A.; Phan, N.; and Trivedi, S. 2026. Watermarking Degrades Alignment in Language Models: Analysis and Mitigation. Transactions on Machine Learning Research. Yang, A.; Li, A.; Yang, B.; Zhang, B.; Hui, B.; Zheng, B.; Yu, B.; Gao, C.; Huang, C.; Lv, C.; et al. 2025. Qwen3 technical report. arXiv preprint arXiv:2505.09388. Yang, A.; Zhang, B.; Hui, B.; Gao, B.; Yu, B.; Li, C.; Liu, D.; Tu, J.; Zhou, J.; Lin, J.; et al. 2024a. Qwen2. 5-math technical report: Toward mathematical expert model via selfimprovement. arXiv preprint arXiv:2409.12122. Yang, J. Q.; Salamatian, S.; Sun, Z.; Suresh, A. T.; and Beirami, A. 2024b. Asymptotics of language model alignment. In 2024 IEEE International Symposium on Information Theory (ISIT), 2027–2032. IEEE. Zhao, X.; Li, L.; and Wang, Y. 2025. Permute-and-Flip: An optimally stable and watermarkable decoder for LLMs. In International Conference on Learning Representations, (ICLR). Zhao, Y.; Khalman, M.; Joshi, R.; Narayan, S.; Saleh, M.; and Liu, P. J. 2022. Calibrating sequence likelihood improves conditional language generation. arXiv preprint arXiv:2210.00045.
7 7.1
Appendices
We also record the property needed for the lower bounds below. Let
Proofs for Section 3.1
Aλ := {x ∈ XP : r(x) = rmax }.
We define s(x) :=
r(x) , λ
smax :=
If Xi ∈ Aλ , then
rmax , λ
Ti = smax + Ei ≥ smax
and, for t ∈ R, Bt := {x ∈ XP : s(x) ≤ t} . Lemma 7.1. For almost every t with respect to the distribution of Mn , and every x ∈ XP , P (x)es(x) 1{x ∈ Bt } . s(z) 1{z ∈ B } t z∈XP P (z)e
Pr(Y = x | Mn = t) = P
Thus, conditional on Mn = t, the output follows Pλ⋆ restricted to Bt and renormalized. In particular, for almost every t ≥ smax ,
Proof. Let T = s(X) + E and let FT denote its distribution function. Since E ∼ Exp(1), for every x ∈ XP , Pr(X = x, T ∈ dt) = P (x)e
Proof of Theorem 3.2 Proof. Since r is nonconstant on XP , ρλ ∈ (0, 1), while qλ > 0 and pmin,λ > 0. Write a := ρnλ ,
P ⋆ := Pλ⋆ ,
Q := Qn,λ .
Theorem 3.1 gives
Pr(Y = x | Mn = t) = Pλ⋆ (x).
−(t−s(x))
almost surely. Hence, on {Mn < smax }, none of the candidates, and therefore not the selected output, belongs to Aλ . Thus, Qn,λ (Aλ ) = 0.
Pen,λ = (1 − a)P ⋆ + aQ. Therefore, TV P ⋆ , Pen,λ = a TV(P ⋆ , Q) ≤ a.
1{t ≥ s(x)} dt
= e−t P (x)es(x) 1{t ≥ s(x)} dt.
Moreover, since Q(Aλ ) = 0, P ⋆ (Aλ ) − Pen,λ (Aλ ) = qλ − (1 − a)qλ = qλ a.
The noisy scores are independent and continuously distributed, so their maximum is attained at a unique index almost surely. By exchangeability, Pr(Y = x, Mn ∈ dt) = ne−t P (x)es(x) 1{t ≥ s(x)} × FT (t)n−1 dt. For fixed t, all factors except P (x)es(x) 1{s(x) ≤ t} are independent of x. Normalizing over x ∈ XP proves the result. Proof of Theorem 3.1 Proof. For one noisy score,
Taking the event Aλ in the variational definition of total variation yields TV P ⋆ , Pen,λ ≥ qλ a. Pinsker’s inequality in either direction then gives DKL P ⋆ ∥Pen,λ ≥ 2qλ2 a2 , DKL Pen,λ ∥P ⋆ ≥ 2qλ2 a2 . For the first upper bound in the target-to-sampler direction,
h
Pr(T < smax ) = EP 1 − e−(smax −s(X)) h i = 1 − EP es(X)−smax = ρλ . Pr(Mn < smax ) = ρnλ .
If ρλ = 0, then r(X) = rmax P -almost surely, so Pen,λ = Pλ⋆ = P , and the claimed decomposition holds for any distribution Qn,λ on XP . Hence, for the remainder of the proof, suppose that ρλ > 0. By Lemma 7.1, conditional on Mn ≥ smax , the output follows Pλ⋆ . Define A ⊆ XP .
Conditioning on {Mn ≥ smax } and {Mn < smax } gives Pen,λ = (1 − ρnλ ) Pλ⋆ + ρnλ Qn,λ .
and hence DKL P ⋆ ∥Pen,λ ≤ − log(1 − a). For the sharper finite-alphabet bounds, define X (Q1 (x) − Q2 (x))2 χ2 (Q1 ∥Q2 ) := . Q2 (x) x
Since the Ti are independent,
Qn,λ (A) := Pr(Y ∈ A | Mn < smax ),
Pen,λ (x) ≥ (1 − a)P ⋆ (x),
i
Using DKL (Q1 ∥Q2 ) ≤ χ2 (Q1 ∥Q2 ), DKL P ⋆ ∥Pen,λ ≤ χ2 P ⋆ ∥Pen,λ X a2 (P ⋆ (x) − Q(x))2 = (1 − a)P ⋆ (x) + aQ(x) x ≤
a2 2 χ (Q∥P ⋆ ). 1−a
Proof of Corollary 3.5
Furthermore, χ2 (Q∥P ⋆ ) =
X Q(x)2 x
P ⋆ (x)
−1
≤ p−1 min,λ − 1. This proves the second target-to-sampler KL upper bound. Finally, χ2 Pen,λ ∥P ⋆ = a2 χ2 (Q∥P ⋆ ). The inequality DKL (Q1 ∥Q2 ) ≤ log(1 + χ2 (Q1 ∥Q2 )) therefore gives DKL Pen,λ ∥P ⋆ ≤ log 1 + p−1 − 1 a2 . min,λ Substituting a = ρnλ proves all finite-n bounds. Since the constants qλ and pmin,λ are fixed and positive, the stated asymptotic orders follow.
7.2
Proofs for Section 3.2
Proof of Theorem 3.3 Proof. By Lemma 7.1, conditional on Mn = t, the selected output follows Pλ⋆ restricted to {x : s(x) ≤ t}. As t increases, only points with larger reward are added to the conditioning set. Hence the conditional expected reward is nondecreasing in t and is at most EPλ⋆ [r(X)]. Under the natural coupling Mn+1 = max{Mn , Tn+1 } ≥ Mn almost surely. Since the preceding conditional expected reward is a nondecreasing function of t, EPen,λ [r(X)] is nondecreasing in n and is upper bounded by the tilted-target reward. By Theorem 3.1, EPλ⋆ [r(X)] − EPen,λ [r(X)] = ρnλ EPλ⋆ [r(X)] − EQn,λ [r(X)] . The expression in parentheses lies in [0, ∆r ], proving the displayed bound. Since r is not constant, ρλ ∈ (0, 1), and convergence follows. Proof of Corollary 3.4 Proof. XP ,
Since r is nonconstant and Pλ⋆ has full support on EPλ⋆ [r(X)] > 0.
The exact decomposition gives EPλ⋆ [r(X)] − EPen,λ [r(X)] = ρnλ EPλ⋆ [r(X)] − EQn,λ [r(X)] . The left-hand side is nonnegative by Theorem 3.3. Since r ≥ 0, EPλ⋆ [r(X)] − EQn,λ [r(X)] ≤ EPλ⋆ [r(X)]. Dividing by the positive denominator proves the result.
Proof. For every distribution Q on XP , DKL (Q∥P ) − DKL (Pλ⋆ ∥P ) EQ [r(X)] − EPλ⋆ [r(X)] = DKL (Q∥Pλ⋆ ) + . λ Setting Q = Pen,λ , using the nonnegativity of KL and Theorem 3.3, gives DKL Pen,λ ∥P − DKL P ⋆ ∥P λ
∆r n ρ . ≥− λ λ The same reward theorem also gives EPen,λ [r(X)] − EPλ⋆ [r(X)] ≤ 0. Therefore, Theorem 3.2 yields DKL Pen,λ ∥P − DKL Pλ⋆ ∥P ≤ DKL Pen,λ ∥Pλ⋆ 2n , ≤ log 1 + p−1 min,λ − 1 ρλ which proves the localization bound. Proof of the distribution-free reference-KL bound Proof. Let ∆r Pen,λ (x) , Z(x) := . λ P (x) By exchangeability, Z(x) = n Pr s(x) + E1 ≥ max {s(Xj ) + Ej } . aλ :=
j=2,...,n
The winning probability of the fixed candidate is maximized by assigning it reward rmax and assigning every competitor reward rmin . Hence Z ∞ n−1 Z(x) ≤ n e−e 1 − e−aλ −e de 0 n = eaλ 1 − 1 − e−aλ =: un,λ . Similarly, the winning probability is minimized by assigning the fixed candidate reward rmin and every competitor reward rmax , which gives Z ∞ n−1 Z(x) ≥ n e−e 1 − e−(e−aλ ) de aλ
= e−aλ . Moreover, EP [Z(X)] = 1, un,λ ≤ n, and un,λ ≤ eaλ . Therefore, DKL Pen,λ ∥P = EP [Z(X) log Z(X)] ≤ log un,λ ≤ log n. Also, Z(X) ∈ [e−aλ , eaλ ]. Applying the chord bound for the convex function z 7→ z log z under the constraint EP [Z(X)] = 1 gives a a2 λ EP [Z(X) log Z(X)] ≤ aλ tanh ≤ λ. 2 2 Combining the two bounds proves ∆2 DKL Pen,λ ∥P ≤ min log n, r2 . 2λ
7.3
Proof of Theorem 3.6
Proof of Theorem 3.7
Proof. Conditional on X1:n = x1:n , ExpBoN is reportnoisy-max with independent exponential noise and is therefore distributionally equivalent to Permute-and-Flip (Ding et al. 2021). Conditional SBoN is softmax sampling applied to the same candidate reward vector at the same temperature λ. The “never worse” property of Permute-and-Flip (Zhao, Li, and Wang 2025, Theorem 3.1(3)), equivalently McKenna and Sheldon (2020, Theorem 2), therefore gives the conditional inequality. Averaging over X1:n gives the marginal result.
7.4
Proofs for Section 3.4
We first record the mechanism-level stability result used below. Lemma 7.2. For deterministic score vectors u, v ∈ Rn , let qu and qv denote the distributions of arg max {ui + Ei } and arg max {vi + Ei }, i=1,...,n
i=1,...,n
respectively, where the Ei are i.i.d. Exp(1). Define D := max(vi − ui ) − min(vi − ui ). i
i
Then, for every i, e−D qu (i) ≤ qv (i) ≤ eD qu (i). Consequently, in either KL direction, D , DKL (qu ∥qv ) ≤ D tanh 2 and D TV(qu , qv ) ≤ tanh . 2 Proof. Fix i and subtract the common constant vi − ui from all coordinates of v, which does not change qv . The ith score then equals ui , while each competitor score differs from the corresponding score under u by a quantity in [−D, D]. Monotonicity of the winning probability in each competitor score gives qu−Dei (i) ≤ qv (i) ≤ qu+Dei (i), where ei is the ith standard basis vector. Let FE be the distribution function of an Exp(1) variable. Then Z ∞ Y qu+Dei (i) = e−e FE (e + D + ui − uj ) de 0
= eD
j̸=i
Z ∞
e−t
D
Y
FE (t + ui − uj ) dt
j̸=i
≤ eD qu (i). Similarly, −D
Z ∞
qu−Dei (i) = e
−D
e−t
Y
FE (t + ui − uj ) dt
j̸=i
≥ e−D qu (i). This proves the likelihood-ratio bound. The KL and totalvariation bounds follow by applying the chord bounds to a likelihood ratio constrained to [e−D , eD ] and having mean one.
Proof. Condition on the candidate tuple X1 , . . . , Xn and apply Lemma 7.2 to rp (Xi ) rt (Xi ) , vi = . λ λ The conditional score perturbation has oscillation at most ωd /λ, giving the range-based conditional KL and TV bounds. Since the candidate marginal is P n under both mechanisms, the KL chain rule gives DKL (P n qt ∥P n qp ) = EP n DKL qt (· | X1:n )∥qp (· | X1:n ) , ui =
and the analogous total-variation distance is the P n -average of the conditional total-variation distances. The returned response is a deterministic function of this joint object, so data processing gives the range-based output-policy bounds. For the variance-sensitive bound, Lemma 7.2 and tanh(z) ≤ z give the conditional KL bound 2 1 max d(X ) − min d(X ) . i i i i 2λ2 Pn Writing di = d(Xi ) and dn = n−1 i=1 di ,
max di − min di i
i
2
≤2
n X (di − dn )2 . i=1
Taking expectations and using # " n X 2 E (di − dn ) = (n − 1) VarP (d(X)) i=1
proves the variance-sensitive KL bound in both directions. Pinsker’s inequality gives the corresponding TV bound. Proof of Theorem 3.8 Proof. The log-likelihood ratio between the true- and proxytilted targets satisfies log
⋆ Pλ,t (x) d(x) = + constant, ⋆ Pλ,p (x) λ
and therefore has oscillation ωd /λ. For completeness, if a likelihood ratio L = dP/dQ satisfies osc(log L) ≤ w, then the chord bound for L under EQ [L] = 1, optimized over its possible endpoints, gives TV(P, Q) ≤ tanh(w/4). The sharp likelihood-ratio range bound gives ω d ⋆ ⋆ TV Pλ,t , Pλ,p ≤ tanh . 4λ The exact ExpBoN decomposition gives p ⋆ n TV Pλ,p , Pen,λ ≤ ρλ,p . Therefore, ⋆ [rt (X)] − E p [rt (X)] Regn,λ = Bt (λ) + EPλ,t e P n,λ p ⋆ ≤ Bt (λ) + ∆t TV Pλ,t , Pen,λ ,
and the triangle inequality proves the claim.
Proof of Theorem 3.9
Indeed,
Proof. For u ∈ {p, t}, write
⋆ [rt (X)] − EP ⋆ [rt (X)] Regn,λ = Bt (λ) + EPλ,t λ,p ⋆ [rt (X)] − E p [rt (X)] + EPλ,p . e P
⋆ Du := DKL Pλ,u ∥P , and define
n,λ
1 . C∞,u := P (Au )
Au := {x ∈ XP : ru (x) = ru,max } ,
p ⋆ For any c ∈ R, adding c to rp changes neither Pλ,p nor Pen,λ ⋆ and replaces d by d − c. The optimality of Pλ,p for the proxy KL-regularized objective gives ⋆ [rp (X)] − EP ⋆ [rp (X)] ≤ λ(Dt − Dp ). EPλ,t λ,p
Moreover, Cauchy–Schwarz gives ⋆ [d(X) − c] EPλ,u
≤
⋆ X Pλ,u (x)2 x∈XP
7.5
Proofs for Section 4
Fix a reasoning state h. Assume that πB (· | h) ≪ πS (· | h) and that r(h, y) ≤ R for every relevant y. Define i h Zβ,B (h) := EπB (·|h) eβr(h,Y ) , and
!1/2
⋆ πβ,B (y | h) :=
1/2 EP [(d(X) − c)2 ] .
P (x)
πB (y | h)eβr(h,y) . Zβ,B (h)
Recall that
Since ⋆ Pλ,u (x) e(ru (x)−ru,max )/λ 1 ≤ = = C∞,u , P (x) P (Au ) EP e(ru (X)−ru,max )/λ we have
Adding the softening-bias, proxy-mismatch, and finite-n terms cancels Dt . Dropping the nonpositive term −λDp and applying the last bound on ρλ,p proves the result.
⋆ X Pλ,u (x)2 x∈XP
P (x)
≤ C∞,u .
sC (h, y) = βr(h, y)+min{d(h, y), C}, Proof of Theorem 4.1
Proof. Throughout this proof, we suppress the conditioning on the fixed state h when no ambiguity can arise. Define the clipped tilted target
Jensen’s inequality further gives
⋆ πβ,C (y | h) :=
h i 2 EP [(d(X) − c)2 ] ≤ λ log EP e(d(X)−c) /λ . where
For every c ∈ R, ⋆ [rt (X)] − EP ⋆ [rt (X)] EPλ,t λ,p ⋆ [rp (X)] − EP ⋆ [rp (X)] = EPλ,t λ,p ⋆ [d(X) − c] − EP ⋆ [d(X) − c]. + EPλ,t λ,p
Combining this identity with the preceding bounds and the optimality inequality for the proxy objective, optimizing over c yields ⋆ [rt (X)] − EP ⋆ [rt (X)] EPλ,t λ,p p √ p C∞,t + C∞,p . ≤ λ(Dt − Dp ) + ελ
⋆ ⋆ Let P∞,t = P (· | At ). Since EP∞,t [rt (X)] = rt,max and ⋆ ⋆ ⋆ DKL (P∞,t ∥P ) = log C∞,t , comparing Pλ,t with P∞,t in the true KL-regularized objective gives
Bt (λ) ≤ λ (log C∞,t − Dt ) . Finally, the exact ExpBoN decomposition gives n ⋆ [rt (X)] − E p [rt (X)] ≤ Rmax ρ EPλ,p e λ,p , P n,λ
and h i ρλ,p = 1 − EP e(rp (X)−rp,max )/λ ≤ 1 − P (Ap ) = 1 −
1 . C∞,p
UC = βR+C.
πS (y | h)esC (h,y) , Zβ,C (h)
h i Zβ,C (h) := EπS (·|h) esC (h,Y ) .
For one candidate Y ∼ πS (· | h) and E ∼ Exp(1), let H := {sC (h, Y ) + E ≥ UC }. Since sC (h, y) ≤ UC , Pr(Y = y, H | h) = e−UC πS (y | h)esC (h,y) . Consequently, ⋆ Pr(Y = y | H, h) = πβ,C (y | h),
and the per-candidate no-hit probability is ρβ,C (h) = 1 − e−UC Zβ,C (h). Conditional on H, exponential memorylessness gives sC (h, Y ) + E − UC ∼ Exp(1), independently of Y . Hence, conditional on the set of hit ⋆ indices, the hit labels are i.i.d. from πβ,C (· | h) and are independent of their exponential overshoots. Selecting the largest overshoot, as full clipped ExpBoN does, or selecting the first hit in an independent random order, as Algorithm 1 does, therefore yields the same marginal hit-branch law ⋆ πβ,C (· | h). More explicitly, conditional on any nonempty hit set, both rules select an index uniformly from that set,
independently of the i.i.d. hit labels. If no hit occurs, Algorithm 1 evaluates all candidates and returns the exponentialnoise maximizer formed from the same clipped scores and noises. Thus, the index i⋆ selected by Lines 1–14 has exactly the finite-n clipped ExpBoN law; the subsequent GSI acceptance gate and fallback are not part of π en,β,C . Therefore, ⋆ ≤ ρβ,C (h)n . TV π en,β,C , πβ,C Define
and
fG (g) = e−g exp −e−g , respectively. Since the Gumbel distribution is continuous, the maximizer is unique almost surely. Hence, Pr (K = i | X1 , . . . , Xn ) Z ∞ Y fG (t − ai ) FG (t − aj ), dt. = −∞
j̸=i
Using the expressions for fG and FG , the integrand becomes Y fG (t − ai ) FG (t − aj )
o n wC (h, y) := min 1, eC−d(h,y) .
j̸=i
Then πS (y | h)e
sC (h,y)
= πB (y | h)e
βr(h,y)
−(t−ai )
=e
wC (h, y).
Y exp −e−(t−ai ) exp −e−(t−aj ) j̸=i
Writing
⋆ mC (h) := Eπβ,B (·|h) [wC (h, Y )] = 1 − τC (h),
= eai e−t exp −e−t
n X
eaj .
j=1
we obtain ⋆ πβ,C (y | h) =
Let
⋆ πβ,B (y | h)wC (h, y) . mC (h)
S :=
and make the change of variables u := Se−t . Then
Pr (K = i | X1 , . . . , Xn ) Z ∞ = eai e−t exp −Se−t dt −∞ Z eai ∞ −u = e du S 0 eai = Pn . aj j=1 e
y
gives (3).
Report-Noisy-Max with Gumbel Noise
We show that the final selection step of SBoN is equivalent in distribution to report-noisy-max with independent staniid dard Gumbel noises: Fix X1 , . . . , Xn and let G1 , . . . , Gn ∼ Gumbel(0, 1), independently of the candidates. Define r(Xi ) + Gi . K := arg max i=1,...,n λ Then, for every i ∈ {1, . . . , n}, er(Xi )/λ Pr (K = i | X1 , . . . , Xn ) = Pn . r(Xj )/λ j=1 e
(4)
Proof. Condition on X1 , . . . , Xn and write r(Xi ) , i = 1, . . . , n. λ The cumulative distribution function and density of a standard Gumbel random variable are FG (g) = exp −e−g ai :=
du = −Se−t dt,
and therefore
The triangle inequality proves (2). Finally, |EQ [g] − EQ′ [g]| ≤ sup g(y) − inf g(y) TV(Q, Q′ )
7.6
eaj
j=1
Since 0 ≤ wC ≤ 1 and 0 < mC ≤ 1, ⋆ ⋆ TV πβ,C , πβ,B wC ⋆ ,1 = 1 − Eπβ,B min mC ⋆ ≤ 1 − Eπβ,B [wC ] = τC (h).
y
n X
Substituting aj = r(Xj )/λ proves (4).
7.7
More Implementation Details
Models and serving. The Qwen2.5-Math (Yang et al. 2024a) configuration uses Qwen2.5-Math-1.5B-Instruct as the draft policy πS , Qwen2.5-Math-7B-Instruct as the target policy πB , and Qwen2.5-Math-PRM-7B as the reward model; the Qwen3 (Yang et al. 2025) configuration uses Qwen3-1.7B and Qwen3-14B with the same PRM and thinking mode disabled. All models are served as separate vLLM (Kwon et al. 2023) instances with prefix caching enabled. Qwen2.5-Math runs use two NVIDIA A100-40 GPUs per evaluation run (draft and target colocated on one device, PRM on the other); Qwen3 runs host all three models on a single A100-80GB. Step timing excludes one-time engine initialization. Because the two families use different serving layouts, wall-clock numbers should be compared within, not across, model families. Draft- and target-policy logprobabilities are obtained through vLLM’s prompt-logprobs
interface with prefix caching enabled. Since prefix-cached positions return placeholder entries, we apply a thin runtime patch that marks such rows, validate every returned log-probability (rejecting non-finite or positive values), and transparently re-fetch affected candidates with the cache bypassed; the patch does not alter vLLM’s sampling or scheduling behavior and is included in the code release. Benchmarks and evaluation. We evaluate on MATH500 (Lightman et al. 2024), MMLUSTEM (Hendrycks et al. 2020), and Minerva Math (Lewkowycz et al. 2022). For MATH500 and MMLU-STEM we use fixed 400-problem subsets (for MATH500, drawn from the pool that remains after removing the 60-problem calibration block); for Minerva Math we use the full 272-problem set. The same problems and random seeds are shared across all methods and candidate budgets, enabling paired comparisons. Results are reported as means and standard deviations over three random seeds for Qwen2.5-Math and two random seeds for Qwen3. Inference configuration. Following GSI (Geuter, Mroueh, and Alvarez-Melis 2025), all methods use candidate budgets n ∈ {2, 4, 8, 16} (n ∈ {4, 16} for Qwen3), inverse temperature β = 20, acceptance threshold u = 0.5, sampling temperature 0.7, top-p = 1.0, and at most 512 new tokens per reasoning step. RSD (Liao et al. 2025) follows the implementation and hyperparameter configuration adopted by GSI, with acceptance threshold δ = 0.7. The early-exit scan first evaluates a batch of b = max(1, ⌊n/4⌋) candidates (i.e., b = 1, 1, 2, 4 for n = 2, 4, 8, 16); if none passes the exit test, all remaining candidates are evaluated in a single second batch, which for prefix-cache efficiency and reduces scheduling overhead. The batch schedule is a serving-level choice fixed a priori and not tuned on any evaluation set: given the presampled candidate order, the algorithm always selects the first candidate that passes the exit test, so batching changes only the realized computation, never the selected step. Calibration of the clipping level. The only hyperparameter ExpGSI adds over GSI is the clipping level C, which acts as a working upper bound on the per-step log-likelihood ratio d = log πB (y | h) − log πS (y | h): the early-exit ceiling β + C is valid precisely because d rarely exceeds C. We calibrate C as a robust estimate of this upper bound. Rolling out 60 MATH-500 problems held out from all evaluation subsets, with 64 draft candidates per reasoning step, we compute d for every candidate and set C to the empirical 95th percentile, yielding C = 0.45. A percentile is preferred over the sample maximum because d is heavy-tailed: the maximum would inflate the ceiling–and thus suppress early exits–for the sake of rare outliers, whereas the ∼5% of candidates with d > C are simply clipped–a change to the target distribution rather than a sampling error, bounded in Theorem 4.1–and, in practice, the selection rule is left nearly intact. Calibrated once, C is held fixed across all benchmarks, candidate budgets, and both model families without retuning; accuracy is insensitive to this choice over a wide range (Table 7). Computational accounting. Estimated FLOPs follow the convention of RSD (Liao et al. 2025): each token processed
by a model costs 2N FLOPs, where N is the model’s parameter count, and we sum over the forward passes each method actually executes. This comprises (i) generation, charged to the generating policy, including target-policy fallback regeneration; (ii) reward-model scoring, where each call re-reads the full sequence (prompt, accepted prefix, and candidate steps), consistent with the official RSD implementation, since no key–value cache persists across PRM calls; and (iii) the target-policy log-likelihoods used by GSI and ExpGSI, which are served with prefix caching and hence charged only for the candidate suffix, while cache cold starts and refetches are charged at full sequence length. Per-problem totals are averaged over the evaluation set. Computing infrastructure. Qwen2.5-Math experiments (including the reward-model and clipping-level ablations) ran on a server with 8× NVIDIA A100-SXM4-40GB GPUs, AMD EPYC 7542 CPUs (128 hardware threads), 2 TB RAM, and Oracle Linux 9.7, allocating two GPUs per evaluation run as described above. Qwen3 experiments ran on a cloud instance with 6× NVIDIA A100-SXM4-80GB GPUs and 2 TB RAM (Linux), hosting all three models of a run on a single GPU. Both machines used the same software stack: Python 3.12, PyTorch 2.11 (CUDA 13), vLLM 0.24, and Transformers 5.13; a complete dependency freeze is included in the code release.
7.8
Additional experimental results
Results across candidate budgets (Qwen2.5-Math). Tables 2–4 report the complete per-benchmark results. The computational advantage of ExpGSI over GSI increases with the candidate budget on every benchmark, reaching 33–46% of estimated compute at n=16 with latency reductions of 16–23%. Acceptance rates remain close to GSI’s throughout, and accuracy differences show no consistent direction. ExpGSI thus reduces the selection overhead of GSI without systematically changing its solution quality. Per-benchmark results for Qwen3. Table 5 breaks the Qwen3 rows of Table 1 down by benchmark. The picture from the Qwen2.5-Math experiments transfers: accuracy and acceptance remain at GSI’s level on every benchmark (the largest deviation, on Minerva Math, lies within its seed spread), while at n=16 estimated computation drops by 38– 52% and time per step by 23–40%. The larger savings relative to Qwen2.5-Math are consistent with the larger target model: the avoided target-policy evaluations account for a larger share of total cost. Reward-model ablation (Skywork PRM). Table 6 reports the complete results of the reward-model ablation described in Section 5.2: all five methods on MATH500 at n ∈ {4, 16} over three random seeds, with the 7B mathspecialized PRM replaced by Skywork-o1-Open-PRMQwen-2.5-1.5B (Team 2024) and all other settings kept identical to the main experiments. The table follows the same format as the per-benchmark tables above, reporting accuracy, time per step, acceptance rate, and estimated TFLOPs per problem.
n
Method
Acc. (%)
Time/step (s)
Accept. (%)
Est. TFLOPs/prob.
2
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
76.5 ± 0.4 79.3 ± 1.9 83.2 ± 1.1 80.3 ± 1.2 80.2 ± 0.7
0.40 ± 0.00 0.49 ± 0.02 0.91 ± 0.00 0.66 ± 0.02 0.61 ± 0.02
– 96.7 ± 0.3 – 89.6 ± 0.5 89.5 ± 0.8
121 ± 5 118 ± 3 148 ± 1 174 ± 5 147 ± 3
4
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
78.1 ± 0.8 80.0 ± 1.1 83.2 ± 0.8 81.8 ± 1.4 82.3 ± 1.7
0.52 ± 0.03 0.59 ± 0.02 1.11 ± 0.02 0.78 ± 0.02 0.74 ± 0.02
– 97.6 ± 0.1 – 92.4 ± 0.4 92.3 ± 0.7
244 ± 22 247 ± 5 322 ± 6 381 ± 8 288 ± 5
8
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
80.0 ± 0.7 80.6 ± 1.2 84.5 ± 0.5 82.3 ± 1.2 82.1 ± 0.6
0.71 ± 0.03 0.77 ± 0.01 1.44 ± 0.03 1.01 ± 0.01 0.91 ± 0.01
– 98.1 ± 0.6 – 94.1 ± 0.2 94.3 ± 0.1
532 ± 40 511 ± 29 647 ± 30 835 ± 14 524 ± 22
16
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
80.4 ± 0.4 80.2 ± 0.9 84.2 ± 1.4 82.2 ± 1.4 81.8 ± 0.9
1.08 ± 0.02 1.15 ± 0.05 1.96 ± 0.02 1.52 ± 0.06 1.17 ± 0.02
– 98.3 ± 0.4 – 95.4 ± 0.5 95.6 ± 0.3
1130 ± 14 1046 ± 17 1366 ± 16 1679 ± 10 900 ± 24
Table 2: Complete results on MATH500 across candidate budgets. Reported values are means and standard deviations over three random seeds. Bold efficiency values indicate improvements of ExpGSI over GSI. † RSD uses the implementation and hyperparameter configuration adopted by GSI. Sensitivity to the clipping level. We evaluate ExpGSI on MATH500 with n = 16 while varying b ∈ {0.5, 0.75, 1.0, 1.5, 2.0, ∞}, C/C b = 0.45 is used in the main experiments. Each conwhere C figuration is evaluated on the same 400 problems using two random seeds. We report final-answer accuracy, the average number of candidates scored per reasoning step, and estimated computation per problem. When C = ∞, clipping and certificate-based early exit are disabled. The resulting selection rule replaces the Gumbel noise in GSI with exponential noise and scores all n candidates. Accuracy remains broadly stable over the tested clipping levels. Increasing C generally requires scoring more candidates. Removing clipping requires evaluating all 16 candidates and increases TFLOPs per problem. The finite clipping configurations therefore provide substantial computational savings without showing a consistent loss in accuracy. ExpBoN vs. SBoN on real candidate pools. Figure 3 repeats the finite-n comparison of Figure 1 on real candidate pools. Rolling out the calibration problems step by step (Appendix 7.7) yields one pool per reasoning step: the 64 nextstep candidates drawn from πS at that prefix, together with their PRM rewards and log-likelihood ratios. For each pool we take the empirical distribution over its candidates and compute the exact finite-n output laws of ExpBoN and SBoN by one-dimensional numerical integration–no sampling is involved, and the integrator reproduces the exact values of the synthetic example in Figure 1. The two mechanisms are compared on identical scores in four configurations, one per column of Figure 3. The first two
columns use the plain reward score r/λ of Section 2: at the deployed temperature λ = 1/β = 1/20, and at λ = 1/2, the temperature of the synthetic example in Figure 1–so the second column is the direct real-data counterpart of that example. The last two columns use the GSI score of Section 4 without and with clipping (βr + d versus sC = βr + min(d, C); β = 20, C = 0.45), the latter being exactly the quantity on which ExpGSI and GSI select candidates. In all four configurations ExpBoN converges geometrically–within a handful of candidates for the reward scores, and by n ≈ 64 under the GSI scores–whereas SBoN decays polynomially throughout, matching Theorem 3.2 and Corollary 3.4 on real data. Two further observations. First, the likelihood term slows finiten convergence for both mechanisms–d spreads the scores within a pool, leaving less probability mass near the pool maximum–and clipping partially restores the speed by capping the right tail. Second, slower convergence does not conflict with the compute savings of ExpGSI: convergence is governed by the score dispersion within a pool, whereas early exit is triggered by proximity to the fixed ceiling UC , and the exit test is exact at every finite n.
n
Method
Acc. (%)
Time/step (s)
Accept. (%)
Est. TFLOPs/prob.
2
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
59.2 ± 2.1 67.1 ± 0.8 68.8 ± 2.3 68.4 ± 1.5 67.2 ± 1.2
0.35 ± 0.00 0.48 ± 0.01 0.79 ± 0.01 0.81 ± 0.01 0.77 ± 0.01
– 89.4 ± 0.4 – 62.4 ± 1.0 62.6 ± 1.0
107 ± 0 92 ± 2 100 ± 1 133 ± 0 110 ± 3
4
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
64.0 ± 0.7 67.4 ± 2.0 72.0 ± 2.0 69.0 ± 0.4 67.8 ± 1.8
0.44 ± 0.01 0.56 ± 0.01 0.94 ± 0.01 0.94 ± 0.02 0.90 ± 0.02
– 92.9 ± 0.3 – 69.9 ± 0.3 69.6 ± 0.9
212 ± 9 199 ± 7 207 ± 3 283 ± 4 224 ± 5
8
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
63.6 ± 1.7 68.8 ± 2.1 73.1 ± 1.0 68.9 ± 1.3 69.3 ± 3.0
0.61 ± 0.01 0.76 ± 0.01 1.18 ± 0.02 1.23 ± 0.04 1.15 ± 0.00
– 94.6 ± 0.1 – 75.5 ± 0.6 75.1 ± 0.4
517 ± 54 468 ± 21 423 ± 12 581 ± 2 425 ± 5
16
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
67.5 ± 1.7 69.2 ± 1.7 71.6 ± 2.3 69.6 ± 1.9 67.8 ± 0.4
0.94 ± 0.02 1.10 ± 0.03 1.56 ± 0.04 1.81 ± 0.04 1.53 ± 0.04
– 95.7 ± 0.3 – 80.2 ± 0.7 79.9 ± 1.0
1072 ± 54 1020 ± 84 869 ± 8 1224 ± 21 822 ± 20
Table 3: Complete results on MMLU-STEM across candidate budgets. Reported values are means and standard deviations over three random seeds. Bold efficiency values indicate improvements of ExpGSI over GSI. † RSD uses the implementation and hyperparameter configuration adopted by GSI.
n
Method
Acc. (%)
Time/step (s)
Accept. (%)
Est. TFLOPs/prob.
2
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
25.0 ± 1.3 24.9 ± 1.7 31.9 ± 1.5 28.6 ± 1.1 29.7 ± 0.6
0.39 ± 0.01 0.50 ± 0.02 0.90 ± 0.02 0.77 ± 0.01 0.73 ± 0.02
– 94.1 ± 0.2 – 78.1 ± 0.3 78.5 ± 0.8
149 ± 5 150 ± 4 171 ± 5 198 ± 6 175 ± 5
4
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
25.7 ± 0.4 24.4 ± 1.1 31.2 ± 0.6 28.9 ± 0.8 29.4 ± 1.1
0.51 ± 0.01 0.60 ± 0.02 1.13 ± 0.01 0.90 ± 0.01 0.88 ± 0.02
– 96.6 ± 0.5 – 84.1 ± 0.0 83.7 ± 0.5
301 ± 10 325 ± 11 363 ± 10 445 ± 11 342 ± 10
8
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
25.2 ± 0.8 24.9 ± 1.3 32.5 ± 2.1 28.8 ± 1.5 29.0 ± 0.7
0.74 ± 0.00 0.81 ± 0.01 1.44 ± 0.05 1.18 ± 0.02 1.11 ± 0.05
– 97.3 ± 0.2 – 88.2 ± 0.4 87.6 ± 0.9
650 ± 10 654 ± 17 758 ± 11 949 ± 38 693 ± 26
16
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
26.5 ± 1.0 26.2 ± 2.4 31.6 ± 1.0 28.7 ± 0.7 29.4 ± 1.9
1.14 ± 0.02 1.27 ± 0.02 1.99 ± 0.12 1.80 ± 0.02 1.50 ± 0.02
– 98.0 ± 0.4 – 90.6 ± 0.2 90.5 ± 0.4
1343 ± 19 1427 ± 42 1538 ± 21 1977 ± 39 1274 ± 50
Table 4: Complete results on Minerva Math across candidate budgets. Reported values are means and standard deviations over three random seeds. Bold efficiency values indicate improvements of ExpGSI over GSI. † RSD uses the implementation and hyperparameter configuration adopted by GSI.
Benchmark
n
Method
Acc. (%)
Time/step (s)
Accept. (%)
Est. TFLOPs/prob.
4
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
67.6 ± 0.2 67.2 ± 0.0 74.0 ± 0.4 68.2 ± 0.7 67.9 ± 0.2
0.27 ± 0.00 0.28 ± 0.00 0.75 ± 0.00 0.46 ± 0.01 0.40 ± 0.01
– 99.5 ± 0.0 – 98.4 ± 0.2 98.2 ± 0.1
714 ± 13 715 ± 5 802 ± 1 1455 ± 1 1006 ± 7
16
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
68.4 ± 0.5 69.0 ± 1.4 73.9 ± 0.2 68.5 ± 0.4 69.0 ± 1.1
0.70 ± 0.00 0.71 ± 0.00 1.33 ± 0.00 1.34 ± 0.01 0.80 ± 0.01
– 99.7 ± 0.0 – 99.2 ± 0.2 99.3 ± 0.0
2874 ± 14 2884 ± 50 3167 ± 71 6644 ± 37 3181 ± 11
4
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
69.8 ± 0.7 71.5 ± 1.1 86.0 ± 0.4 82.1 ± 1.2 80.9 ± 0.5
0.28 ± 0.01 0.33 ± 0.00 0.80 ± 0.00 0.70 ± 0.02 0.67 ± 0.00
– 96.5 ± 0.0 – 80.5 ± 0.3 80.3 ± 0.4
374 ± 4 395 ± 10 510 ± 7 925 ± 1 736 ± 14
16
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
69.8 ± 0.4 74.2 ± 1.1 86.0 ± 1.8 81.5 ± 0.0 81.2 ± 0.4
0.67 ± 0.00 0.72 ± 0.01 1.30 ± 0.01 1.53 ± 0.00 1.18 ± 0.03
– 97.7 ± 0.1 – 85.9 ± 0.0 86.0 ± 0.4
1616 ± 41 1629 ± 22 2002 ± 12 4558 ± 87 2831 ± 41
4
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
26.1 ± 2.1 28.7 ± 0.5 37.9 ± 1.6 33.3 ± 0.3 32.5 ± 0.8
0.30 ± 0.00 0.34 ± 0.00 0.78 ± 0.01 0.63 ± 0.00 0.57 ± 0.00
– 97.1 ± 0.2 – 89.3 ± 0.2 89.9 ± 0.5
475 ± 6 513 ± 7 613 ± 14 1226 ± 26 932 ± 13
16
S-BoN (πS ) RSD† S-BoN (πB ) GSI ExpGSI (ours)
26.3 ± 1.3 27.4 ± 1.8 37.9 ± 1.6 32.9 ± 0.8 35.3 ± 3.1
0.75 ± 0.00 0.78 ± 0.00 1.39 ± 0.02 1.65 ± 0.00 1.16 ± 0.00
– 98.0 ± 0.0 – 93.0 ± 0.1 93.7 ± 0.4
2058 ± 65 2095 ± 29 2527 ± 18 6106 ± 5 3495 ± 48
MATH500
MMLU-STEM
Minerva Math
Table 5: Complete per-benchmark results for the Qwen3 configuration (Qwen3-1.7B draft, Qwen3-14B target, thinking mode disabled, same PRM and clipping level as the main experiments) at n ∈ {4, 16}. Reported values are means and standard deviations over two random seeds. Bold efficiency values indicate improvements of ExpGSI over GSI. † RSD uses the implementation and hyperparameter configuration adopted by GSI.
Figure 3: Exact finite-n convergence of ExpBoN vs. SBoN on real LLM candidate pools (medians with 10–90% bands). Columns: the reward score r/λ of Section 2 at the deployed temperature λ = 1/20 and at λ = 1/2, the temperature of the synthetic example in Figure 1; the GSI score of Section 4 without clipping (βr + d) and with clipping (sC = βr + min(d, C); β = 20, C = 0.45). Rows: KL divergence to the tilted target and relative centered-reward gap. Output laws are computed exactly by numerical integration; the dotted line marks numerical precision (10−13 ). ExpBoN converges geometrically in every configuration while SBoN decays polynomially; comparing the last two columns, clipping speeds up convergence by capping the right tail of the scores.
n Method
Acc. (%)
Time (s)
Accpt. (%) TFLOPs
S-BoN (πS ) 76.5±0.0 .44±.00 – 41±1 RSD† 79.2±1.4 .93±.02 65.5±.8 43±2 – 76±0 4 S-BoN (πB ) 82.7±0.9 1.09±.02 GSI 83.6±1.0 .98±.01 73.0±1.2 141±3 ExpGSI (ours) 83.8±0.5 1.01±.03 72.2±.7 117±2 S-BoN (πS ) 75.1±1.7 .67±.03 – 148±6 RSD† 80.4±1.0 1.24±.02 72.7±.0 147±4 – 269±4 16 S-BoN (πB ) 84.4±1.3 1.51±.03 GSI 83.2±1.2 1.45±.07 78.9±1.2 540±12 ExpGSI (ours) 83.1±0.9 1.41±.01 79.5±2.3 410±22
Table 6: Results with the Skywork reward model on MATH500. Values are means and standard deviations over three seeds.
b C/C
Acc. (%)
Scored cand./step
Est. TFLOPs/prob.
0.5 0.75 1.0 (default) 1.5 2.0 ∞ (no clipping)
82.4 ± 1.9 83.0 ± 0.4 82.9 ± 0.9 82.3 ± 0.7 80.8 ± 1.4 81.9 ± 0.5
8.9 8.8 9.2 9.6 10.2 16.0
892 892 941 951 993 1592
Table 7: Sensitivity of ExpGSI to the clipping level on MATH500 with n = 16. Accuracy is reported as mean ± standard deviation over two seeds. When C = ∞, clipping and early exit are disabled.