Best-of-N Sampling

Follow this topic Ask about this topic

Momentum

2 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 22

Oct 7, 2026cs.LG

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

Best-of-N (BoN) is a common inference-time alignment method that selects the highest-scoring response among N samples from a reference model. Evaluating BoN policies from logged data is challenging under sample-only access because standard off-policy estimators require density ratios that depend on unavailable response likelihoods. In this paper, we propose a sample-only framework for evaluating and selecting BoN policies without access to these likelihoods. We show that the order-statistic structure of BoN allows the required density ratios to be expressed through score-rank probabilities that are estimable from samples alone. We then develop a doubly robust estimator of the BoN policy value (BoN-DR) that efficiently reuses a shared auxiliary sample pool across candidate budgets. We establish valid asymptotic inference even under reward estimator misspecification and prove the efficiency of our BoN-DR estimator. Since larger budgets can amplify errors in the score function and lead to reward overoptimization, we derive two selection rules: (i) maximizing the estimated policy value and (ii) maximizing a lower confidence bound on the improvement over the reference policy, which accounts for estimation uncertainty and provides a no-harm guarantee. Across synthetic experiments and GSM8K with multiple reference and reward models, our framework accurately estimates BoN policy values and selects effective sampling budgets.

Jonas Schweisthal, Yuxin Wang, Athiya Deviyani +2

LMU Munich & MCML · Carnegie Mellon University · Meta (work in personal capacity)

Best-of-N Sampling Off-Policy Evaluation Inference-Time Language Model Alignment Doubly Robust Estimation

Oct 6, 2026cs.CL

Holdout Best-of-N: Unbiased Evaluation and Its Cost

Reusing the scores that select a Best-of-

N

winner can overstate its expected reward. We study evaluation from a fixed matrix of

K

independent scores per candidate for a policy that selects using

J

fresh scores. A single estimator based only on this matrix is exactly unbiased for expected judge reward under every independent, stable collection of candidate-specific score laws if and only if

J<K

, for every pool size

M\ge N\ge2

. At

J=K-1

, the selector deepens as

K

grows. For independent Gaussian scores with common variance and fixed

M\ge N\ge2

, the unbiased minimax risk in this regime is of order

σ^2/\sqrt K

, attained by Holdout; allowing bias improves the rate to

σ^2/K

. For two candidates, we derive the minimum-variance unbiased estimator at known variance and the sharp asymptotic unbiased minimax constant

1/(π\sqrt2)

, which Holdout attains without knowing the variance. The cyclic average over subsets and ties can be computed in

O(MK\log M)

operations. At fixed selector depth, cyclic evaluation of bounded scores has

O(K^{-1})

risk uniformly in pool size. The impossibility result concerns the fixed matrix: one additional fresh winner score permits unbiased evaluation of the all-

K

policy.

Shrey Shah, Yinheng Li

Best-of-N Sampling Policy Evaluation Minimax Estimation Reward Model Evaluation

Sep 28, 2026cs.LG

Audit the Scaffold, Not the Checkpoint: A Stationarity Dichotomy for Recursive Self-Improvement in Agentic Coding

An auditor who checks whether a system's weights are frozen is checking the wrong thing. Our stationarity dichotomy says that iterative self-modification hits strict diminishing returns whenever the agent's reachable set of edits stays fixed, and can escape only if that set expands. Rewriting scaffolding (tools, verifiers, decomposition) expands what an agent reaches without touching a weight, so frozen weights buy an eventual ceiling but no stationarity along the way. The criterion also separates three regimes usually merged: search within a fixed class, test-time training that raises the ceiling itself, and scaffold rewriting between them. Audit the scaffold, not the checkpoint. The same ceiling binds sideways. Best-of-

k

orchestration realizes the best worker's ceiling exactly: width buys rate, not budget. Re-consulting a fixed pool has a horizon computable in advance, decided by the pool alone, and the one arrangement that would beat it, a weighted vote, needs diversity real workers lack: on 30 same-family workers the failure overlap sits at its maximum, and a majority fails 23/55 (42%) of tasks. We obtain the criterion by reading refinement as gradient boosting on the residual error between draft and target, a patch or git diff, and then measuring where that reading breaks: patches compose instead of standing beside each other to be voted on, and failures overlap. What we measure is saturation. Per-round improvement decays toward zero on SWE-bench, and churn decays geometrically across 401 production sessions, a shape shared with a pre-AI human baseline that establishes the regime without identifying its cause. Both breaks are engineering choices rather than laws about code, so together they specify a harness worth building.

Sebastian Bobadilla-Suarez, Bob Suh, Ryan Fortin

OnCorps

Software Engineering Agents AI Agent Auditing Best-of-N Sampling Recursive Self-Improvement

Sep 21, 2026cs.CL

Efficient Reasoning Exploration via State-Conditioned Latent Steering with Progress Guidance

Best-of-

N

is a widely used inference strategy for complex reasoning, whose effectiveness depends on whether sampled candidates can cover diverse and high-quality reasoning paths. However, post-trained reasoning models often suffer from \emph{exploration collapse}, where independent rollouts repeatedly follow similar reasoning paths and limit the gains from increasing the rollout budget. Existing methods alleviate this issue by promoting broader exploration, but do not explicitly guide exploration toward continuations that make meaningful progress, resulting in limited exploration efficiency. To address this, we propose \emph{\underline{S}tate-conditioned \underline{P}rogress-guided \underline{S}teering} (SPS), a training-free latent steering framework. Specifically, SPS constructs a state-conditioned Direction Bank containing multiple progress-guided steering vectors for different prefix-state regions. During online inference, SPS retrieves a suitable steering vector based on the current prefix state and applies it at high-uncertainty transitions to guide the next reasoning step toward meaningful progress. Extensive experiments across multiple model scales and benchmarks demonstrate that SPS consistently outperforms strong baselines. Further analyses validate the effectiveness of its key designs and offer valuable insights for future research. The code is available at https://github.com/rattlesnakey/SPS.

Hengyuan Zhang, Chenming Shang, Zunhai Su +10

The University of Hong Kong · University of California, Los Angeles · Arizona State University +3

Best-of-N Sampling Inference-Time Guidance LLM Reasoning

Aug 8, 2026cs.LG

Evaluator Ensembles Under Reward Hacking: Covariance Geometry and Finite-Search Guarantees

Language-model judges and reward models enable scalable supervision, but finite optimization can exploit evaluator errors rather than improve response quality. We characterize this failure through the covariance geometry of evaluator ensembles. For calibrated judges, the ensemble mean retains common-mode error along the all-ones direction, whereas cross-judge disagreement captures only orthogonal error. Consequently, disagreement can be high despite robust aggregation, or low while shared response-dependent errors persist. We prove that common-mode error is not identifiable from internal judge scores alone. Under a joint sub-Gaussian model, we bound best-of-K selection overstatement and target-quality regret, extending the guarantees to predictably adaptive search under conditional calibration. The resulting search terms scale as the square root of log K and are asymptotically tight for Gaussian projected errors. We further show that noisy quality proxies introduce artificial rank-one covariance without changing disagreement, and propose a bounded two-anchor Bernstein certificate for finite-search error and regret. Fixed-seed Gaussian stress tests over 120 (J, rho, K) configurations and real-model audits validate the theory while revealing the limits of disagreement-based diagnostics under increasing search pressure.

Fariya Afrin, Ibne Farabi Shihab

Department of Computer Science, Kalinga Institute of Industrial Technology · Department of Computer Science, Iowa State University

Reward Hacking LLM Evaluation LLM-as-a-Judge Best-of-N Sampling Reward Model Evaluation

Jul 31, 2026cs.LG

Stabilized Best-of- $K$ Training for Neural Combinatorial Optimization

Leader Reward modifies POMO training to emphasize the best trajectory produced by repeated inference. We test a narrow extension: replace its binary leader/non-leader distinction with a stabilized rank signal indexed by a sampling budget

K

. With the POMO architecture, 3,050-epoch schedule, and TSP-100 test set held fixed, the Leader Reward reimplementation obtains

7.7662

under 100-start, 8-augmentation greedy decoding, matching the reported

7.766

at its displayed precision. Under independent sampling, the stabilized

K=8

recipe lowers realized Best-of-8 cost in all three paired training seeds:

7.7944

versus

7.8136

. This observation is estimation-only and decoder-specific: three seeds are below the six-seed testing floor, Leader Reward is better at sampled

K=1

, and it remains slightly better under its original augmented-greedy protocol. We make no unbiased-estimator, universal superiority, or state-of-the-art claim.

Melveena Jolly, Midhun Xavier

1Independent Researcher

Traveling Salesperson Problem Best-of-N Sampling Combinatorial Optimization RL for Combinatorial Optimization Reward Design for RL Neural Combinatorial Optimization

Jul 23, 2026cs.LG

Best-of-Evidence: Best-of-N Selection under Partial Verification

BoN improves model outputs by sampling several candidates and selecting one with a proxy score, but it assumes that complete candidates can be evaluated reliably. Many vision-language tasks instead provide only partial verification: a finding, span, value, region, or relation may be checkable even when no dependable whole-response verifier exists. Moreover, the same claim may recur across candidates with opposing stances, allowing one observation to support part of the pool and contradict another. We introduce Best-of-Evidence (BoE), an inference-time selection framework that keeps the BoN candidate pool fixed, represents reusable claims with a signed candidate--factor graph, and allocates a limited budget to evidence actions that can change the final choice. BoE formalizes selection under partial verification and provides a practical score-based controller, with the zero-budget case recovering the underlying BoN decision. Theoretically, we show that residual evidence capacity limits any evidence-driven improvement and that shared factor queries can achieve an O(log K) versus Θ(K) query separation in a factor-code model. Common-ledger experiments on four medical VQA settings show that BoE can improve fixed-pool selection and rescue some BoN failures when evidence is reliable, contrastive, and decision-relevant, while also revealing the channel-quality and candidate-generation limits that prevent universal gains.

Cenwei Zhang, Teng Fang, Yuxia Wang +3

IQuest Research · INSAIT · Technical University of Denmark

Model Selection Evidence-Grounded Reasoning Evidence Selection Best-of-N Sampling

Jul 13, 2026cs.LG

Rank-Conditioned Sample Reuse for the Plackett--Luce Best-of- $K$ Objective

We study the coupled objective J_K^WOR = E_{S ~ PL-WOR_K}[max_{i in S} R_i]: the expected maximum reward of a size-K Plackett-Luce draw without replacement, the law of Gumbel-Top-K / Stochastic Beam Search decoding. This estimand differs from the conventional i.i.d. objective J_K^iid = E[max_{i<=K} R_i] targeted by existing sample-reuse Max@K estimators, and reusing their i.i.d. weights under the coupled sampler is provably biased (a closed-form three-item instance gives E[g_iid] = (4/5) grad J_K^WOR exactly; pass@K under the coupled sampler is the binary-reward special case). Generic joint-score REINFORCE is already unbiased for J_K^WOR; what it lacks is sample reuse. Our contribution is to instantiate standard rank-conditioned Horvitz-Thompson estimation for the J_K^WOR subset total: from one Gumbel-Top-n pool (n>K) and its observed priority threshold we build an estimator that reuses all C(n,K) embedded K-subsets, unbiased with an unbiased exact score-function surrogate gradient, plus a reward-sorted Max-specific dynamic program that collapses the C(n,K)-term subset sum (with K!-cost set probabilities) exactly to a one-dimensional integral. A fixed-Q quadrature evaluation costs O(n log n + nKQ) arithmetic and is numerically, not algebraically, exact; no epsilon-approximation rate is certified. Each nonzero degree-K Horvitz-Thompson term has finite second moment exactly when n >= 2K; under the same assumptions the full surrogate gradient has finite second moment whenever n >= 2K (sharpness there is open). At K=1 the construction recovers classical priority sampling. All quantities require only the values and differentiable computation graphs of the n+1 drawn items' probabilities, so finite structured sequence policies sampled by exact SBS are covered. A certified finite-Q quadrature bound and countably infinite support remain open. Validation code is included as ancillary files.

Melveena Jolly, Midhun Xavier

Independent Researcher

Inverse Probability Weighting Best-of-N Sampling

Jul 9, 2026cs.CL

Best-of- $N$ TTS Evaluation is Confounded by ASR Family Alignment

Best-of-

N

(BoN) inference improves content consistency in zero-shot text-to-speech by selecting from

N

candidates with an automatic speech recognition (ASR) verifier. We identify an underexplored evaluation confound: a verifier's apparent quality depends strongly on which ASR family judges it. On LibriSpeech-PC test-clean~\citep{librispeechpc} with F5-TTS~\citep{f5tts}, verifier rankings reverse across Whisper, wav2vec~2.0, and HuBERT evaluators, and same-family verifier-evaluator pairs recover 2-3

\times

more oracle headroom than cross-family pairs despite near-identical representations (linear CKA

0.978

) -- a pattern consistent with identity- or lineage-level coupling rather than representational overlap. We propose two \textbf{cross-family rank ensembles} (rank-averaging and conjunctive max-rank) that attain the lowest mean WER across three independent evaluators --

1.61\%

at

N{=}10

(

-12\%

relative to F5-TTS) -- with no measurable degradation under automatic SIM-o/UTMOS metrics; the best single verifier drives WER from

2.06\%

to

1.72\%

(

-16.5\%

) under the official F5-TTS evaluator. We recommend cross-evaluator triangulation as default reporting practice.

Taehyung Yu, Seongjae Kang

KAIST, Daejeon, South Korea.

Speech Generation Evaluation TTS Evaluation Best-of-N Sampling Zero-Shot TTS Rank Aggregation

Jul 5, 2026cs.CV

Flash-BoN: Instant Drafts for Inference-Time Scaling in Diffusion Models

Inference-time scaling for text-to-image generation has progressed from simple Best-of-

N

(BoN) sampling to guided search methods that verify and steer candidate trajectories at intermediate denoising steps. These approaches focus on when and how often to verify during denoising but largely treat the cost of generation itself as fixed. Moreover, the standard practice of comparing methods by number of function evaluations (NFEs) counts only denoising forward passes and ignores verifier overhead, which can distort efficiency rankings. We show that under wall-clock evaluation, simple BoN already matches or outperforms several guided search techniques, suggesting that compute is better spent on broader exploration than on repeated intermediate verification. This motivates Flash-BoN, which generates a large pool of inexpensive draft candidates by combining three complementary acceleration knobs: timestep truncation, layer skipping, and activation proxies into a single configuration optimized once per model. An efficient multi-stage verification procedure then identifies the most promising draft, which is refined at full quality. Across three benchmarks and three model scales, Flash-BoN consistently outperforms all baselines under fixed wall-clock budgets, with gains that grow at larger model scales (+8% AUC). We further show that our strategy combines well and improves existing orthogonal techniques such as reflection-based prompt optimization (+16% AUC). The gains correlate with increased candidate diversity, which also enables draft-guided selection to accelerate RL post-training convergence.

Ruchit Rawal, Reza Shirkavand, Sayak Paul +5

University of Maryland, College Park, MD, USA · Hugging Face, USA

Inference-Time Scaling Best-of-N Sampling Diffusion Model Inference Acceleration T2I Diffusion Models

Jul 3, 2026cs.LG

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

Inference-time alignment methods, such as Best-of-

N

, offer a flexible alternative to training-based alignment by using reward models to select high-quality responses generated by a reference LLM. However, the efficacy of these methods is inherently limited by the response quality: if the reference LLM assigns negligible probability to high-reward responses, no selection strategy will succeed in finding aligned outputs. In this work, we propose Best-of-Better-

N

(BoBN), an in context learning-based generation framework to address this challenge. Our method utilizes retrieval from high-reward examples relevant to the input query and task. Crucially, we introduce a restyling step where retrieved responses are rewritten by the reference LLM to align with the target task's format and style. These restyled examples are used in-context to shift the sampling distribution toward the high-reward region. We analytically characterize how in-context learning shifts the output distribution of pretrained transformers toward the high-reward region, resulting in provable benefits on the target task. We then evaluate BoBN on safety alignment and mathematical reasoning benchmarks across several reference LLMs. BoBN's higher-quality responses enable better performance to be achieved when the number of responses

N

is fixed, and smaller

N

required to achieve a target performance.

Eric Lei, Hsiang Hsu, Chun-Fu Chen

JPMorganChase Global Technology Applied Research

LLM Alignment Best-of-N Sampling LLM Safety Alignment In-Context Learning Inference-Time Language Model Alignment

Jun 27, 2026cs.LG

When More Sampling Hurts: The Modal Ceiling and Correlation Ceiling of Test-Time Scaling

People overthink; language models over-sample, and the extra effort can talk both into a worse answer. Reasoning systems answer a hard question by sampling it many times (test-time scaling), and the more they draw, the more often a correct answer turns up somewhere, so coverage, the fraction of problems with at least one correct try, climbs and appears to be progress. But a deployed system must return one answer, and choosing it, not knowing which try is right, is selection; selection is capped, and past a point extra samples only make the model surer of a confident mistake, even as every draw adds cost. The gap between climbing coverage and stalled selection, the identifiability gap, is the answer a model can produce but not pick. So the real question is not whether to sample but how far, and the answer is: not far. For picking an answer, the vote has already settled within a few dozen draws, the modal ceiling; for scoring a benchmark, sooner still, the correlation ceiling. Beyond that, extra draws cost compute and add nothing, and can even make the answer worse. This paper turns the cutoff into a single number, the effective number of samples, that any sampling run already reveals. The bottleneck is recognizing a right answer, not generating one.

Yong Yi Bay, Kathleen A. Yearick

University of Illinois at Urbana-Champaign

LLM Evaluation Self-Consistency Decoding Test-Time Scaling Best-of-N Sampling LLM Reliability

Jun 23, 2026cs.CV

Transition-Aware best-of-N sampling for Longitudinal Chest X-ray Reports

In longitudinal clinical practice, every chest X-ray is read in the context of the patients prior exam, and much of what the radiologist communicates is the change from one visit to the next. To the best of our knowledge, we present the first training-free best-of-N sampling scheme for pre-trained chest X-ray report generators that is explicitly aware of this longitudinal prior to current transition. We call it transition-aware best-of-N sampling, each report is split into sentences and embedded into an unordered set in Rd; each (prior, current) pair is reduced to a fixed-dim directional vector via a set-to-set distance designed to encode the change between the two sets; and candidates are scored by cosine distance from their candidate transition vector to a cached bank of ground-truth training transition vectors, aggregated as min or kNN. We instantiate the framework with four directional set distances (mean-shift, novelty residual, directed-Hausdorff anchor, and cost-weighted optimal transport) and evaluate on a multi-visit AP-PA cohort, running inference under three prompts on three vision-language generators. Transition-aware best-of-N outperforms random selection across the board, with the largest relative gains on the Impression section.

Halil Ibrahim Gulluk, Max Van Puyvelde, Wim Van Criekinge +1

Department of Electrical Engineering, Stanford University, Stanford, CA, USA · Department of Biomedical Data Science, Stanford University School of Medicine, Stanford, CA, USA · Department of Mathematical Modelling, Statistics & Bioinformatics, Ghent University, Ghent, Belgium

Radiology Report Generation Radiology VLMs Longitudinal Medical Image Analysis Best-of-N Sampling

Jun 2, 2026cs.CL

Predicting Inference-Time Scaling Gains from Labeled Validation-Set Output Statistics

Best-of-

N

inference scaling (drawing

N

candidate answers from a language model and returning the one a reward model ranks highest) improves accuracy by an amount that varies across models, but predicting that amount in advance currently requires running the procedure end-to-end. Prior work links cheap statistics of a model's sampled outputs and validation-set correctness (how often samples agree, how diverse they are, how confident the model is, and where correct samples appear) to model behavior, but does not isolate which of these form a stable, compact predictor of best-of-

N

gain. We fit ridge predictors on features computed from a single labeled validation-set sampling pass, use bootstrap-Lasso as a stability analysis of the candidate feature set, and give a concentration analysis with an explicit linear-approximation residual. Across three base-model families, six post-training methods, and math and reasoning task domains, the stability analysis identifies a strict three-feature core spanning prompt-level agreement spread, label-assisted first-correct-sample position, and completion-length variance; a compact ridge predictor built from this core plus an entropy add-on reaches Spearman

ρ= 0.90

with actual best-of-

N

gain under a reward-model verifier. The intended use is labeled validation-set screening of candidate configurations before paying the full reward-model scoring cost.

Luyang Zhang, Jingyan Li

Carnegie Mellon University · Johns Hopkins University

LLM Evaluation Inference-Time Scaling Best-of-N Sampling

May 28, 2026stat.ML

Reward Learning from Best-of- $N$ Preference Data: Targets, Tradeoffs, and Design Principles

Best-of-

N

sampling is widely used to construct pairwise preference data:

N

candidates are drawn from a base distribution, and the best is paired with a rejected response. Despite its widespread use, what Bradley--Terry (BT) reward learning extracts from such data, and how to choose

N

and the base distribution, remain unclear. We specialize a recent analysis of preference data via its induced conditional distribution to Best-of-

N

. For independent-reference variants, we derive closed-form reward targets as explicit functions of

N

and the base distribution, and show that they preserve the latent reward ranking. For the practical Best-vs-Random and Best-vs-Worst variants, chosen and rejected responses are coupled through the same candidate set, so exact BT representability generally fails; nevertheless, bounded-class minimizers approach the reference targets as

N

grows. Although margin and connectivity are known to govern sample efficiency in pairwise preference learning, Best-of-

N

couples them through

N

in opposing directions: larger

N

widens pairwise margins but reduces connectivity. This trade-off yields two design principles: use larger

N

when preference labels are the bottleneck, smaller

N

when generation is the bottleneck; and shape the base distribution to place mass between the responses whose comparison matters most at test time. Experiments on synthetic and real preference data support the predicted dependence on sample size and base-distribution shape.

Rattana Pukdee, Maria-Florina Balcan, Pradeep Ravikumar

Machine Learning Department Carnegie Mellon University

Pairwise Preference Learning Reward Modeling Pairwise Comparison Pairwise Preference Evaluation Best-of-N Sampling Pairwise Ranking+2

May 28, 2026cs.CL

CCS: Clinical Consensus Selection for Radiology Report Generation

Radiology report generation (RRG) is commonly formulated as a single-path generation task, where a multimodal large language model (MLLM) produces one decoded report as the final output. While recent progress has largely been driven by scaling training data, model capacity, and retrieval mechanisms, improving report quality at inference time remains underexplored. In this work, we observe that fixed radiology MLLMs often generate clinically stronger reports elsewhere in their candidate pool than the one selected by default decoding, suggesting that inference-time decision making remains an overlooked bottleneck. To address this, we propose Clinical Consensus Selection (CCS), a decoder-agnostic inference-time selection framework that samples multiple candidate reports and selects the one with the highest clinical consensus across the rollout pool. CCS unifies text-based utilities with a radiology-adapted utility computed by an image--report-trained multimodal embedder, which measures candidate agreement beyond surface-level textual similarity. Across three datasets and multiple radiology MLLMs, CCS consistently improves inference-time performance over single-path decoding and generic Best-of-N baselines, with particularly clear gains on clinical metrics. Further analysis shows that image-grounded utility forms a selection axis distinct from textual consensus and that substantial headroom remains for improving RRG at inference time.

Xi Zhang, Yingshu Li, Zaiqiao Meng +2

School of Computing Science, University of Glasgow · School of Electrical and Computer Engineering, University of Sydney · Language Technology Lab, University of Cambridge

Radiology Report Generation Radiology VLMs Healthcare Multimodal Reranking Best-of-N Sampling

May 11, 2026cs.LG

What should post-training optimize? A test-time scaling law perspective

Large language models are increasingly deployed with test-time strategies: sample

N

responses, score them with a reward model or verifier, and return the best. This deployment rule exposes a mismatch in post-training: standard objectives optimize the mean reward of a single response, whereas best-of-

N

performance is governed by the upper tail of the reward distribution. Recent test-time-aware objectives partly address this mismatch, but typically assume that training can use the same per-prompt rollout budget as deployment, which is impractical when post-training must cover many prompts while deployment can allocate much larger per-prompt test-time compute. We study this budget-mismatch regime, where only

m\ll N

per-prompt rollouts are available during training but the target objective is best-of-

N

deployment. Under structural assumptions on the reward tails, we show that the policy gradient of the best-of-

N

objective can be approximated from a much smaller rollout group by extrapolating upper-tail statistics. This yields a family of Tail-Extrapolated estimators for best-of-

N

-oriented post-training: a simple direct estimator, Tail-Extrapolated Advantage (TEA), and a fixed-order debiased Prefix-TEA estimator based on moment cancellation. Experiments on instruction-following tasks show that TEA and Prefix-TEA improve best-of-

N

performance across different language models, reward models and datasets under various training and test-time budget settings.

Muheng Li, Jian Qian, Wenlong Mou

Department of Statistical Sciences, University of Toronto† · Department of AI and Data Science, The University of Hong Kong ⋄

Test-Time Scaling Best-of-N Sampling Policy Gradient Methods RL Post-Training

May 10, 2026cs.CV

On-Policy Distillation with Best-of-N Teacher Rollout Selection

On-policy distillation (OPD), which supervises a student on its own sampled trajectories, has emerged as a data-efficient post-training method for improving reasoning while avoiding the reward dependence of reinforcement learning and the catastrophic forgetting often observed in standard supervised fine-tuning. However, standard OPD typically computes teacher supervision under noisy student-generated contexts and often relies on a single stochastic teacher rollout per prompt. As a result, the supervision signal can be high-variance: the sampled teacher trajectory can be incorrect, uninformative, or poorly matched to the student's current reasoning behavior. To address this limitation, we propose BRTS, a Best-of-N Rollout Teacher Selection framework for on-policy distillation. BRTS augments standard student-context OPD with a teacher-context supervision branch constructed from the curated teacher trajectory. Rather than distilling from the first sampled teacher rollout, BRTS samples a small pool of teacher trajectories and selects the auxiliary trajectory using a simple priority rule: correctness first, student alignment second. When multiple correct teacher trajectories are available, BRTS chooses the one most aligned with the student's current behavior; when unconditioned teacher samples fail on harder prompts, it invokes a ground-truth-conditioned recovery step to elicit a natural derivation. The selected trajectory is then used to provide reliable teacher-context supervision inside the OPD loop, augmented with an auxiliary loss on the teacher trajectory. Experiments on AIME 2024, AIME 2025, and AMC 2023 show that BRTS improves over standard OPD on challenging reasoning benchmarks, with the largest gains on harder datasets. Our code is available at https://github.com/BWGZK-keke/BRTS.

Ke Zhang, Yunjie Tian, Dongdi Zhao +4

Johns Hopkins University · TikTok · University of California, San Diego +1

CoT Distillation Best-of-N Sampling Mathematical Reasoning Language Model Distillation On-Policy Distillation Teacher-Student Learning

Apr 17, 2026cs.LG

Flexible Empowerment at Reasoning with Extended Best-of-N Sampling

This paper proposes a novel method that incorporates empowerment when reasoning actions in reinforcement learning (RL), thereby achieving the flexibility of exploration-exploitation dilemma (EED). In previous methods, empowerment for promoting exploration has been provided as a bonus term to the task-specific reward function as an intrinsically-motivated RL. However, this approach introduces a delay until the policy that accounts for empowerment is learned, making it difficult to adjust the emphasis on exploration as needed. On the other hand, a trick devised for fine-tuning recent foundation models at reasoning, so-called best-of-N (BoN) sampling, allows for the implicit acquisition of modified policies without explicitly learning them. It is expected that applying this trick to exploration-promoting terms, such as empowerment, will enable more flexible adjustment of EED. Therefore, this paper investigates BoN sampling for empowerment. Furthermore, to adjust the degree of policy modification in a generalizable manner while maintaining computational cost, this paper proposes a novel BoN sampling method extended by Tsalis statistics. Through toy problems, the proposed method's cability to balance EED is verified. In addition, it is demonstrated that the proposed method improves RL performance to solve complex locomotion tasks.

Taisuke Kobayashi

National Institute of Informatics and The Graduate University for Advanced Studies, SOKENDAI Japan

Reinforcement Learning Best-of-N Sampling RL Exploration

Apr 16, 2026cs.LG

SCATR: Simple Calibrated Test-Time Ranking

Test-time scaling (TTS) improves large language models (LLMs) by allocating additional compute at inference time. In practice, TTS is often achieved through parallel scaling: generating multiple candidate responses and selecting the best via a Best-of-N (BoN) strategy. Its effectiveness therefore hinges on the scoring function. Learned scorers such as process reward models (PRMs) can be strong, but they are expensive to train and run. Lightweight confidence heuristics based on token log-probabilities are much cheaper, yet we find that they often perform substantially worse. To improve on lightweight confidence heuristics without incurring the full cost of stronger learned scorers, we introduce SCATR, a simple and efficient BoN ranking method that learns a lightweight scorer from a small calibration set using hidden representations from the base model. Across coding and mathematical reasoning benchmarks, SCATR improves over prior confidence-based baselines by up to 9%. Relative to LoRA fine-tuning on the same calibration data, it achieves comparable accuracy with up to 8000x fewer trainable parameters and much lower compute, reducing training and inference latency by up to 150x and 1000x, respectively. SCATR is also competitive with strong PRM baselines, and in several settings improves accuracy by up to 7.8% on math and 4.2% on coding while enabling up to 1000x faster inference. Overall, SCATR offers a strong accuracy-efficiency trade-off for scalable test-time selection.

Divya Shyamal, Marta Knežević, Lan Tran +3

EPFL · MIT

Test-Time Scaling Best-of-N Sampling LLM Reranking Efficient Language Model Inference

Jan 26, 2026cs.CL

Do not be greedy, Think Twice: Sampling and Selection for Document-level Information Extraction

Document-level Information Extraction (DocIE) aims to produce an output template with the entities, relations, and events of interest occurring in the given document. Standard practices include prompting decoder-only LLMs using greedy decoding to avoid output variability. Rather than treating this variability as a limitation, we show that sampling can produce substantially better solutions than greedy decoding, especially when using reasoning models. We thus propose ThinkTwice, a sampling and selection framework in which the LLM generates multiple candidate templates for a given document, and a selection module chooses the most suitable one. We introduce both an unsupervised method that exploits agreement across generated outputs, and a supervised selection method using reward models trained on labeled DocIE data. To address the scarcity of golden reasoning trajectories for DocIE, we propose a rejection-sampling-based method to generate silver training data that pairs output templates with reasoning traces. Our experiments show the validity of unsupervised and supervised ThinkTwice, consistently outperforming greedy baselines and the supervised state-of-the-art.

Mikel Zubillaga, Oscar Sainz, Oier Lopez de Lacalle +1

HiTZ Center - Ixa, University of the Basque Country UPV/EHU

Self-Consistency Decoding Document Information Extraction Best-of-N Sampling LLM Information Extraction

Aug 29, 2025cs.CL

PiCSAR: Probabilistic Confidence Selection And Ranking for Reasoning Chains

Best-of-n sampling improves the accuracy of large language models (LLMs) and large reasoning models (LRMs) by generating multiple candidate solutions and selecting the one with the highest reward. The key challenge for reasoning tasks is designing a scoring function that can identify correct reasoning chains without access to ground-truth answers. We propose Probabilistic Confidence Selection And Ranking (PiCSAR): a simple, training-free method that scores each candidate generation using the joint log-likelihood of the reasoning and final answer. The joint log-likelihood of the reasoning and final answer naturally decomposes into reasoning confidence and answer confidence. PiCSAR achieves substantial gains across diverse benchmarks (+10.18 on MATH500, +9.81 on AIME2025), outperforming baselines with at least 2x fewer samples in 16 out of 20 comparisons. Our analysis reveals that correct reasoning chains exhibit significantly higher reasoning and answer confidence, justifying the effectiveness of PiCSAR.

Joshua Ong Jun Leang, Zheng Zhao, Aryo Pradipta Gema +7

Imperial College London · University of Edinburgh · UCL

Confidence Estimation in Language Models Best-of-N Sampling LLM Reranking LLM Uncertainty Estimation Algorithmic Reasoning LLM Reasoning