ExpBoN: Exponential-Noise Best-of-$n$ for Efficient Test-Time LLM Alignment

Yanxiao Liu; Sicheng Wan; Deniz Gündüz

cs.LGSep 18, 2026

ExpBoN: Exponential-Noise Best-of- $n$ for Efficient Test-Time LLM Alignment

Authors: Yanxiao Liu, Sicheng Wan, Deniz Gündüz

Organizations: Imperial College London · University of Washington

Abstract

Best-of- $n$ (BoN) sampling is a simple yet effective inference-time 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.

Figures & tables

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

\lambda=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

\rho_{\lambda}^{n}

from Corollary 3.4 and the corresponding

O(1/n)

SBoN bound. Panel (c) uses

r

as the true reward and

r_{p}=r+0.1(1,0,-1)

as the proxy reward at

\lambda=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.

Figure 2: Compute–accuracy planes at each candidate budget $n$ (Qwen2.5-Math; macro average over MATH500, MMLU-STEM, and Minerva Math; $3$ -seed means). Arrows mark the GSI $\,\to\,$ 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 .

r_{i}\leftarrow r(h,y_{i}),\qquad\ell_{B,i}\leftarrow\log\pi_{B}(y_{i}\mid h)

Algorithm 1 ExpBoN-based GSI

Model family	$n$	Method	Acc. (%)	Time/step (s)	Accept. (%)	Est. TFLOPs/prob.
Qwen2.5-Math(1.5b/7b/7b)	4	S-BoN ( $\pi_{S}$ )	$55.9\pm 0.5$	$0.49\pm 0.01$	–	$252\pm 6$
		RSD †	$57.3\pm 1.2$	$0.58\pm 0.01$	$95.7\pm 0.2$	$257\pm 7$
		S-BoN ( $\pi_{B}$ )	$62.1\pm 0.4$	$1.06\pm 0.01$	–	$297\pm 6$
		GSI	$59.9\pm 0.6$	$0.87\pm 0.01$	$82.1\pm 0.2$	$370\pm 5$
		ExpGSI (ours)	$59.9\pm 0.8$	$\mathbf{0.84\pm 0.02}$	$81.9\pm 0.4$	$\mathbf{285\pm 4}$
	16	S-BoN ( $\pi_{S}$ )	$58.1\pm 0.2$	$1.05\pm 0.01$	–	$1182\pm 16$

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.

$n$	Method	Acc. (%)	Time/step (s)	Accept. (%)	Est. TFLOPs/prob.
2	S-BoN ( $\pi_{S}$ )	$76.5\pm 0.4$	$0.40\pm 0.00$	–	$121\pm 5$
	RSD †	$79.3\pm 1.9$	$0.49\pm 0.02$	$96.7\pm 0.3$	$118\pm 3$
	S-BoN ( $\pi_{B}$ )	$83.2\pm 1.1$	$0.91\pm 0.00$	–	$148\pm 1$
	GSI	$80.3\pm 1.2$	$0.66\pm 0.02$	$89.6\pm 0.5$	$174\pm 5$
	ExpGSI (ours)	$80.2\pm 0.7$	$0.61\pm 0.02$	$89.5\pm 0.8$	$\mathbf{147\pm 3}$
4	S-BoN ( $\pi_{S}$ )	$78.1\pm 0.8$	$0.52\pm 0.03$	–	$244\pm 22$

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.

$n$	Method	Acc. (%)	Time/step (s)	Accept. (%)	Est. TFLOPs/prob.
2	S-BoN ( $\pi_{S}$ )	$59.2\pm 2.1$	$0.35\pm 0.00$	–	$107\pm 0$
	RSD †	$67.1\pm 0.8$	$0.48\pm 0.01$	$89.4\pm 0.4$	$92\pm 2$
	S-BoN ( $\pi_{B}$ )	$68.8\pm 2.3$	$0.79\pm 0.01$	–	$100\pm 1$
	GSI	$68.4\pm 1.5$	$0.81\pm 0.01$	$62.4\pm 1.0$	$133\pm 0$
	ExpGSI (ours)	$67.2\pm 1.2$	$\mathbf{0.77\pm 0.01}$	$62.6\pm 1.0$	$\mathbf{110\pm 3}$
4	S-BoN ( $\pi_{S}$ )	$64.0\pm 0.7$	$0.44\pm 0.01$	–	$212\pm 9$

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 ( $\pi_{S}$ )	$25.0\pm 1.3$	$0.39\pm 0.01$	–	$149\pm 5$
	RSD †	$24.9\pm 1.7$	$0.50\pm 0.02$	$94.1\pm 0.2$	$150\pm 4$
	S-BoN ( $\pi_{B}$ )	$31.9\pm 1.5$	$0.90\pm 0.02$	–	$171\pm 5$
	GSI	$28.6\pm 1.1$	$0.77\pm 0.01$	$78.1\pm 0.3$	$198\pm 6$
	ExpGSI (ours)	$29.7\pm 0.6$	$\mathbf{0.73\pm 0.02}$	$78.5\pm 0.8$	$\mathbf{175\pm 5}$
4	S-BoN ( $\pi_{S}$ )	$25.7\pm 0.4$	$0.51\pm 0.01$	–	$301\pm 10$

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.
MATH500	4	S-BoN ( $\pi_{S}$ )	$67.6\pm 0.2$	$0.27\pm 0.00$	–	$714\pm 13$
		RSD †	$67.2\pm 0.0$	$0.28\pm 0.00$	$99.5\pm 0.0$	$715\pm 5$
		S-BoN ( $\pi_{B}$ )	$74.0\pm 0.4$	$0.75\pm 0.00$	–	$802\pm 1$
		GSI	$68.2\pm 0.7$	$0.46\pm 0.01$	$98.4\pm 0.2$	$1455\pm 1$
		ExpGSI (ours)	$67.9\pm 0.2$	$\mathbf{0.40\pm 0.01}$	$98.2\pm 0.1$	$\mathbf{1006\pm 7}$
	16	S-BoN ( $\pi_{S}$ )	$68.4\pm 0.5$	$0.70\pm 0.00$	–	$2874\pm 14$

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\in\{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.

$n$	Method	Acc. (%)	Time (s)	Accpt. (%)	TFLOPs
4	S-BoN ( $\pi_{S}$ )	$76.5{\pm}0.0$	$.44{\pm}.00$	–	$41{\pm}1$
	RSD †	$79.2{\pm}1.4$	$.93{\pm}.02$	$65.5{\pm}.8$	$43{\pm}2$
	S-BoN ( $\pi_{B}$ )	$82.7{\pm}0.9$	$1.09{\pm}.02$	–	$76{\pm}0$
	GSI	$83.6{\pm}1.0$	$.98{\pm}.01$	$73.0{\pm}1.2$	$141{\pm}3$
	ExpGSI (ours)	$83.8{\pm}0.5$	$1.01{\pm}.03$	$72.2{\pm}.7$	$117{\pm}2$
16	S-BoN ( $\pi_{S}$ )	$75.1{\pm}1.7$	$.67{\pm}.03$	–	$148{\pm}6$

Table 6: Results with the Skywork reward model on MATH500. Values are means and standard deviations over three seeds.

$C/\widehat{C}$	Acc. (%)	Scored cand./step	Est. TFLOPs/prob.
0.5	$82.4\pm 1.9$	8.9	892
0.75	$83.0\pm 0.4$	8.8	892
1.0 (default)	$82.9\pm 0.9$	9.2	941
1.5	$82.3\pm 0.7$	9.6	951
2.0	$80.8\pm 1.4$	10.2	993
$\infty$ (no clipping)	$81.9\pm 0.5$	16.0	1592

Table 7: Sensitivity of ExpGSI to the clipping level on MATH500 with

n=16

. Accuracy is reported as mean

\pm

standard deviation over two seeds. When

C=\infty

, clipping and early exit are disabled.

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/\lambda$ of Section 2 at the deployed temperature $\lambda=1/20$ and at $\lambda=1/2$ , the temperature of the synthetic example in Figure 1; the GSI score of Section 4 without clipping ( $\beta r+d$ ) and with clipping ( $s_{C}=\beta r+\min(d,C)$ ; $\beta=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.

Best-of-N Sampling

Best-of-N sampling generates multiple candidate outputs and selects one using reward, confidence, agreement, or task-specific evidence.

See all 32 papers

Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment
Mar 5, 2026Ved Sriraman, Adam BlockBest-of-N Sampling Inference-Time Language Model Alignment
Department of Computer Science, Columbia University · Department of Electrical Engineering, Columbia University
Best-of-Better- $N$ : Generating Pre-Aligned Responses with In-Context Learning
Jul 3, 2026Eric Lei, Hsiang Hsu, Chun-Fu ChenLLM Alignment Best-of-N Sampling
JPMorganChase Global Technology Applied Research
Privacy Without Regret: Differentially Private Inference-Time Alignment
Aug 26, 2026Ishi Jain, Nandini Bhattad, Sayak Ray ChowdhuryInference-Time Language Model Alignment Best-of-N Sampling
Indian Institute of Technology Kanpur

Mar 5, 2026J/K move · Enter open · S save

Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment

Ved Sriraman, Adam Block

Department of Computer Science, Columbia University · Department of Electrical Engineering, Columbia University

Best-of-N Sampling Inference-Time Language Model Alignment Reward Hacking

Open paper AskPDF arXiv

Best-of-N (BoN) sampling is a widely used inference-time alignment method for language models, whereby N candidate responses are sampled from a reference model and the one with the highest predicted reward according to a learned reward model is selected. Despite its widespread practical use, recent theoretical work has suggested that it is statistically suboptimal and vulnerable to reward hacking, the process by which models exploit weaknesses in the learned reward model to achieve high estimated reward without genuinely improving performance. We revisit this question under assumptions that more closely reflect practice than that of prior work. In particular, in contradistinction to earlier analyses that focused on expected true reward, which may not be meaningful in many practical settings, we investigate how inference-time alignment affects the win-rate, a pairwise comparison-based metric more closely aligned with how reward models are trained and evaluated in practice. We demonstrate that, under minimal conditions on the quality of the reference model and learned reward model, properly tuned BoN is both computationally and statistically optimal in achieving high win-rate, partially explaining its widespread practical success. Because BoN remains susceptible to reward-hacking in this setting, we propose a simple and practical variant that provably eliminates reward-hacking while maintaining optimal statistical performance. Finally, we show that prior approaches are provably suboptimal when considering win-rate, highlighting the importance of choosing appropriate objectives when analyzing inference-time alignment methods.

Abstract

Best-of-N Sampling

Explore similar work

Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment

Best-of-Better-NNN: Generating Pre-Aligned Responses with In-Context Learning

Privacy Without Regret: Differentially Private Inference-Time Alignment

Best-of-Better- $N$ : Generating Pre-Aligned Responses with In-Context Learning