Whether or Where? Tail Calibration Signals Finite-Budget Reward Hacking in Best-of-N Selection

Cheng Gui; Yihua Shao; Lei Li; Jingcai Guo; Maolin Wang

cs.LGOct 25, 2026

Whether or Where? Tail Calibration Signals Finite-Budget Reward Hacking in Best-of-N Selection

Authors: Cheng Gui, Yihua Shao, Lei Li, Jingcai Guo, Maolin Wang

Organizations: City University of Hong Kong · University of Science and Technology Beijing · University of Washington · Hong Kong Polytechnic University

Abstract

Best-of-N (BoN) inference returns the candidate with the highest proxy reward, so a larger $N$ tests the proxy's extreme tail more than its average ranking quality. We show that the exact BoN value is a Beta-weighted integral of conditional true reward over within-prompt score quantiles. It follows that BoN depends on scores only through their ranks. It also follows that BoN can decline only if the calibration curve in the tail turns downward, and the budget where the decline appears depends on where that turn lies. Under a bounded additive model, the error tail sets the limit: Gaussian errors keep improving, Laplace errors reach a plateau, and heavy-tailed errors return to the prior mean. When error variance is largest at low true reward, even Gaussian noise can push BoN below random selection. Synthetic phase maps agree with this taxonomy. On real candidate pools spanning several verifiable domains, base policies, and learned reward models, tail failures are rare and all occur in code generation. A held-out tail calibration statistic reliably predicts where a cross-fitted budget cap helps. It does about as well as rank accuracy, and the cap is competitive with a Soft-BoN baseline. Tail calibration therefore does not replace ranking metrics. It is an audit that is unchanged by any monotone rescaling of the reward scores and shows which budgets are at risk.

Figures & tables

Error model	$\lambda_{\star}$	Limiting utility	Budget behavior
Gaussian	$\infty$	$r_{\max}$	Nondecreasing
Laplace (scale $b$ )	$1/b$	$m(1/b)$	Nondecreasing; plateau
Student- $t_{\nu}$	$0$	$\mu$	Returns to prior
Heteroskedastic Gaussian	—	$r_{\sigma}$	Can end below $\mu$

Table 1: Tail regimes for bounded rewards. The first three rows assume independent additive error (Theorem 3.3 ); Gaussian and Laplace monotonicity follows from Proposition A.5 . The last row assumes a unique scale maximizer (Proposition 3.4 ). Rates and further families are given in Appendix A.7 .

Figure 1: Synthetic phase maps. D denotes an interior peak whose peak-to- $N=512$ simultaneous max- $t$ interval is above zero; P denotes an inconclusive interior or saturated boundary; M denotes a maximum at 512. The bounded Uniform map is primary. Prior shape changes finite-window boundaries but preserves the broad separation between light and heavy additive tails.

Figure 2: MATH-500 input-format controls on a fixed candidate pool. Each panel holds the reward model and all 500

\times

256 answers fixed while varying only the score input: QA (blue circles), answer-only (orange-red triangles), masked question (teal squares), or deterministically shuffled question (magenta diamonds). The thin horizontal dotted line is base correctness.

RM	Input	Rank acc.	$E_{1}$	Peak $N$	Drop [95% CI]
Tulu-3 8B	QA	.741	+.054	64	.0051 [-.0118,.0220]
	answer-only	.581	-.031	4	.0597 [ .0316,.0878]
	masked question	.698	+.049	96	.0082 [-.0069,.0232]
	shuffled question	.613	+.023	16	.0098 [-.0143,.0339]
Skywork Qwen3-4B	QA	.812	+.084	256	—
	answer-only	.799	+.101	256	—

Table 2: MATH-500 input-format controls on the same 500

\times

256 candidate pool.

E_{1}

is top-1% tail excess; drop intervals are simultaneous within each condition. — indicates that the empirical maximum is at

N=256

, so there is no selected interior peak contrast or corresponding interval.

Figure 3: External PPE validation. (a) Top-12.5% tail excess for 13 learned reward models across five tasks. Negative cells concentrate on MBPP+. (b) Calibration-fold tail risk versus held-out gain from the calibration-selected cap, with two folds per learned cell. Cell-clustered bootstrap intervals are reported in Table 3 .

Predictor	ROC AUC [95% CI]	AP [95% CI]	$\rho_{s}$ [95% CI]
$-E_{\mathrm{tail}}$	.983 [.954,.998]	.825 [.449,.973]	.254 [.020,.459]
Low rank accuracy	.972 [.927,.995]	.747 [.337,.953]	.258 [.023,.453]
Score-tail spread	.355 [.133,.589]	.057 [.026,.117]	-.107 [-.292,.074]
Tail $-$ rank	.012 [-.003,.042]	.079 [-.015,.215]	-.004 [-.043,.039]
Tail $-$ spread	.628 [.384,.858]	.769 [.382,.915]	.361 [.060,.656]

Table 3: Diagnostic validation on 65 learned PPE cells. Intervals resample task–RM cells and keep both cross-fit folds together. Differences are tail risk minus the comparator.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Task	Input	RM	Rank acc.	Peak $N$	Drop [95% CI]
MATH-500	QA	Skywork 1B	.746	24	.0049 [-.0180,.0278]
	QA	Skywork 3B	.772	160	.0014 [-.0087,.0115]
	QA	Skywork Qwen3-4B	.812	256	—
	QA	Tulu-3 8B	.741	64	.0051 [-.0118,.0220]
	answer-only	Skywork 1B	.712	24	.0109 [-.0141,.0360]
	answer-only	Skywork 3B	.735	256	—

Appendix

Table 4: All original controlled conditions. Drop is the selected interior peak minus

N=256

with a within-condition simultaneous max-

t

interval. — denotes a boundary maximum at

N=256

, with no interior peak contrast.

MBPP+ RM	Rank acc.	$E_{\rm tail}$	Peak	Drop	Cap gain [95% CI]	$q$
Eurus-7B	.537	-.014	2	.059 D	.059 [.024,.093]	.0047
Skywork-Llama-8B	.514	-.028	2	.043	.039 [.001,.078]	.192
Starling-7B	.387	-.157	1	.165	.165 [.128,.202]	$<10^{-4}$
InternLM2-1.8B	.464	-.039	1	.045	.045 [.002,.088]	.161
InternLM2-7B	.452	-.114	1	.171	.171 [.132,.213]	$<10^{-4}$
Nemotron-340B	.477	-.068	1	.076	.076 [.030,.119]	.0027

Appendix

Table 5: Learned PPE cells with negative primary tail excess. “D” marks the strict interior-downturn definition;

q

is for the cross-fitted cap policy over all 70 cells.

Population	Cells	Tail cap $\Delta$	Rank-Soft-BoN $\Delta$	Cap $-$ soft
All learned	65	.0085 [.0019,.0168]	.0068 [-.0003,.0156]	.0017 [-.0003,.0036]
Negative tail	6	.0924 [.0519,.1383]	.0916 [.0511,.1339]	.0009 [.0000,.0020]

Appendix

Table 6: Held-out mitigation comparison against hard BoN-32. Intervals resample learned task–RM cells and keep both folds together.

Input	$\rho_{L}$	$\Delta_{L}$ [95% CI]	$\Delta_{B}$ [95% CI]	$E_{1}$ [95% CI]
QA	-.106	-.020 [-.031,-.009]	+.084 [.069,.100]	+.053 [.034,.073]
Answer-only	-.144	-.029 [-.040,-.018]	-.026 [-.041,-.011]	-.031 [-.048,-.013]
Masked	-.042	+.006 [-.005,.018]	+.067 [.052,.082]	+.048 [.029,.066]
Shuffled	+.050	+.027 [.016,.038]	+.024 [.011,.037]	+.023 [.006,.038]

Appendix

Table 7: Descriptive Tulu MATH top-1% features.

\rho_{L}

is mean within-prompt Spearman correlation between score and log character count;

\Delta_{L}

and

\Delta_{B}

compare top-tail versus remaining log length and boxed-marker frequency;

E_{1}

is correctness excess.

Feature	Median contrast	RM-cell range
Log character count	+.121	[.025,.150]
Line count	+2.986	[.424,3.850]
Syntax valid	+.018	[.007,.022]
Defines target function	+.021	[.000,.036]
Target-function docstring	+.029	[.007,.037]
Examples or assertions	-.133	[-.217,-.112]

Appendix

Table 8: MBPP+ incorrect top-tail minus other incorrect response features over the six negative-RM cells. Binary-feature contrasts are proportions.

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 33 papers

Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems
Oct 14, 2026Taro Yano, Yoichi Ishibashi, Masafumi OyamadaBest-of-N Sampling Inference-Time Scaling
NEC Corporation
Efficient Best-of-N policy evaluation for inference-time alignment
Oct 7, 2026Jonas Schweisthal, Yuxin Wang, Athiya Deviyani +2Best-of-N Sampling Off-Policy Evaluation
LMU Munich & MCML · Carnegie Mellon University · Meta (work in personal capacity)
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

Oct 14, 2026J/K move · Enter open · S save

Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems

Taro Yano, Yoichi Ishibashi, Masafumi Oyamada

NEC Corporation

Best-of-N Sampling Inference-Time Scaling

Open paper AskPDF arXiv

Best-of-N sampling is a simple inference-time scaling strategy for large language models, yet its behavior under incomplete reward models remains poorly understood. We study Best-of-N as a competition between the extreme reward tails of correct and incorrect responses. This view shows that success depends not only on the probability of sampling a correct response, but also on whether correct responses dominate incorrect ones in the upper tail. Using extreme value theory, we characterize three asymptotic regimes: correct-tail-dominant, incorrect-tail-dominant, and critical explaining both monotonic gains and reward-hacking-induced degradation. We further derive finite-sample scaling laws for representative reward distributions, showing that, under Gaussian rewards, incorrect responses with sufficiently large variance can dominate selection even when their mean reward is lower. Unlike oracle selection, convergence with an incomplete selector can be polynomial rather than exponential. Finally, we propose a lightweight tail-tension criterion to estimate when additional sampling may become harmful. Experiments on synthetic data and real reward model scores are consistent with the theoretically predicted regimes, scaling laws, and diagnostic behavior, suggesting that tail competition provides a unified lens on Best-of-N sampling for verifiable problems.

Abstract

Best-of-N Sampling

Explore similar work

Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems

Efficient Best-of-N policy evaluation for inference-time alignment

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