Research map / Large language models / Reasoning and chain of thought

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

NeurIPS 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Frames Best-of-N sampling for verifiable problems as a competition between the upper reward tails of correct and incorrect responses, derives extreme-value phase classification and finite-n scaling laws, and proposes a label-free tail-tension early-stopping rule.

Problem

Best-of-N sampling with incomplete reward models can show non-monotonic behavior and reward hacking, and its scaling rate under imperfect selectors is poorly understood.

Approach

Treat BoN success as a competition between the maxima of correct and incorrect reward distributions; use extreme value theory to classify regimes (correct-tail-dominant, incorrect-tail-dominant, critical) and show that with an incomplete selector convergence can be polynomial rather than exponential. A two-component Gaussian mixture fitted unsupervised to reward scores gives an early-stopping poin

Key results

• Under Gaussian rewards, incorrect responses with larger variance dominate selection for large n, producing reward hacking when mu_c > mu_w and sigma_c < sigma_w.
• On RAMO-Llama3.1-8B, tail-tension early stopping mitigates degradation on reward-hacking problems while reducing sample cost (e.g., 27.6% cost saved for Skywork-Qwen3-1.7B at n=2^13 on hacking cases, with higher accuracy than no-stop).
• Empirically, incorrect responses have larger reward variance than correct ones in most real reward-model settings, and real reward distributions are reasonably fit by max-stable families per the AD test.

Surprising findings

• Incorrect responses often have larger reward variance than correct responses, so high-reward tails are dominated by incorrect answers in real reward-model settings.
• With an incomplete selector, BoN convergence to accuracy one can be polynomial in n rather than exponential.

Limitations

• Focuses on verifiable problems; open-ended tasks not covered.
• Early stopping assumes bimodal, roughly Gaussian reward distributions separating correct from incorrect answers; misassignment of mixture components can hurt.
• Analysis is asymptotic in n; identifying regimes at finite n from real data remains open.

Experimental setup

Datasets: Monkey Business dataset (10,000 responses per problem, Brown et al. 2024) MATH MiniF2F GSM8K CodeContests

Benchmarks: MATH MiniF2F GSM8K CodeContests

Metrics: best-of-n accuracy number of generated samples (cost) Anderson-Darling goodness of fit AIC BIC

Baselines: No-stop Best-of-N ucb_t090 ucb_t095 ucb_t099 ucb_c1e-3 ucb_c2e-4

Builds on: Best-of-N sampling Fisher-Tippett-Gnedenko theorem Brown et al. 2024 large language monkeys scaling Kalayci et al. 2025 early stopping for BoN

Closest papers by meaning

• Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment (ICML 2025 · similarity 0.90)
• On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference (ICML 2026 · similarity 0.90)
• Inference-Time Reward Hacking in Large Language Models (NeurIPS 2025 · similarity 0.89)
• Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck (NeurIPS 2026 · similarity 0.88)
• Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification (ICML 2025 · similarity 0.88)
• Majority of the Bests: Improving Best-of-N via Bootstrapping (NeurIPS 2025 · similarity 0.88)