Research map / Large language models / Reasoning and chain of thought
Majority of the Bests: Improving Best-of-N via Bootstrapping
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.
Proposes Majority-of-the-Bests (MoB), which bootstraps the output distribution of Best-of-N with reward models and returns its mode, improving over BoN and self-consistency in most of 30 setups.
Problem
Best-of-N with imperfect reward models is stochastic and often fails to reliably pick the correct answer, even when the correct answer is the most likely BoN outcome.
Approach
Estimate the output distribution of Best-of-m over resampled (bootstrap, m-out-of-N) subsets of sampled outputs and select its mode instead of sampling from it, with m chosen adaptively via a ratio-based criterion and a closed-form O(N log N) computation.
Key results
- MoB-Adaptive improves over BoN by 6.00 points on MATH500 with Qwen2.5-3B and GRM at N=128 (69.95 vs 63.95).
- MoB outperforms BoN in 25 of 30 base-model, reward-model, and benchmark setups.
- MoB-Adaptive improves MATH500 with Llama3.1-8B and ArmoRM by 11.35 points over BoN at N=128.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MoB-Adaptive instead of BoN | Qwen2.5-3B + GRM · MATH500 | accuracy: 6.00{ $\pm$0.78} | Helped |
| use MoB-Adaptive instead of BoN | Qwen2.5-3B + GRM · MMLU-Pro-Math | accuracy: 3.20{ $\pm$0.79} | Helped |
| use MoB-Adaptive instead of BoN | Qwen2.5-3B + GRM · MMLU-Pro-Chem | accuracy: 7.45{ $\pm$0.94} | Helped |
| use MoB-Adaptive instead of BoN | Qwen2.5-3B + GRM · GSM8K | accuracy: 1.90{ $\pm$0.51} | Helped |
| use MoB-Adaptive instead of BoN | Qwen2.5-3B + GRM · CSQA | accuracy: -0.30{ $\pm$0.52} | Hurt |
| use bootstrapped subsets rather than independent BoN runs followed by voting | MoB vs. BoN+SC · MMLU-Pro-Math | accuracy | Helped |
| choose adaptive m or m=√N rather than the optimal m variant | MoB · MATH500 and other evaluated benchmarks | accuracy | No clear effect |
| vary adaptive m parameter q (ablation) | MoB with adaptive m · MATH500 | accuracy: 61.85\% to 63.15\% | Mixed |
Surprising findings
- Under imperfect rewards, BoN's own success probability can stay well below 1 even with large N, while the mode of its output distribution is often correct.
- On CommonsenseQA with Qwen2.5-3B, MoB-Adaptive is slightly below BoN (-0.30 points, not significant), and WBoN collapses to 54.90.
Limitations
- Limited to tasks with discrete final answers that can be extracted and compared.
- Like other sampling methods, incurs higher inference cost than zero-shot decoding.
- Theoretical consistency result relies on finite answer sets and mild tail assumptions on reward distributions.
Experimental setup
Datasets: MATH500 GSM8K MMLU-Pro-Math MMLU-Pro-Chem CommonsenseQA
Benchmarks: MATH500 GSM8K MMLU-Pro-Math MMLU-Pro-Chem CommonsenseQA
Metrics: accuracy standard error l1 distance between selection distributions
Baselines: Best-of-N self-consistency Weighted Best-of-N BoN+SC
Builds on: Best-of-N self-consistency Weighted Best-of-N bagging subagging
Closest papers by meaning
- Scalable Best-of-N Selection for Large Language Models via Self-Certainty (NeurIPS 2025 · similarity 0.89)
- Variational Best-of-N Alignment (ICLR 2025 · similarity 0.89)
- BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling (NeurIPS 2024 · similarity 0.89)
- Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment (ICML 2025 · similarity 0.89)
- Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems (NeurIPS 2026 · similarity 0.88)
- On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference (ICML 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.