Best-of-Majority: Minimax-Optimal Strategy for Pass@ k Inference Scaling
cs.LG, stat.ML
Submitted: 2025-10-03
Updated: 2026-10-28
Comments: 26 pages, 4 figures, 4 tables, ICLR2026
License: http://creativecommons.org/licenses/by/4.0/
The gist: LLM inference often generates a batch of candidates for a prompt and selects one via strategies like majority voting or Best-of- N (BoN).
Terminology
Abstract
LLM inference often generates a batch of candidates for a prompt and selects one via strategies like majority voting or Best-of- N (BoN). For difficult tasks, this single-shot selection often underperforms. Consequently, evaluations commonly report Pass@ k: the agent may submit up to k responses, and only the best of them is used when computing regret. Motivated by this, we study inference scaling in the more general Pass@ k inference setting, and prove that neither majority voting nor BoN exhibits the desirable scaling with k and the sampling budget N. Combining the advantages of majority voting and BoN, we propose a new inference strategy called Best-of-Majority (BoM), with a pivotal step that restricts the candidates to the responses with high frequency in the N samples before selecting the top- k rewards. We prove that when the sampling budget is N= Ω(C*), the regret of BoM is O(ε opt+ sqrt ε RM 2C*/k), where C* is the coverage coefficient, ε RM is the estimation error of the reward model, and ε opt is the estimation error of reward at the optimal response. We further establish a matching lower bound, certifying that our algorithm is minimax optimal. Beyond optimality, BoM has a key advantage: unlike majority voting and BoN, its performance does not degrade when increasing N. Experimental results of inference on math problems show BoM outperforming both majority voting and BoN.
Sources
- GPT-4 Technical Report
- Best-of-N through the Smoothing Lens: KL Divergence and Regret Analysis
- Theoretical guarantees on the best-of-n alignment policy
- Large Language Monkeys: Scaling Inference Compute with Repeated Sampling
- The Importance of Pessimism in Fixed-Dataset Policy Optimization
- Pass@k Training for Adaptively Balancing Exploration and Exploitation of Large Reasoning Models
- Training Verifiers to Solve Math Word Problems
- Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training
- Interpretable Contrastive Monte Carlo Tree Search Reasoning
- DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- Measuring Mathematical Problem Solving With the MATH Dataset
- Scaling Laws for Autoregressive Generative Modeling
- Deep Learning Scaling is Predictable, Empirically
- Training Compute-Optimal Large Language Models
- Self-Improvement in Language Models: The Sharpening Mechanism
- Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment
- Scaling Scaling Laws with Board Games
- Scaling Laws for Neural Language Models
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
- Beyond Pass@1: Self-Play with Variational Problem Synthesis Sustains RLVR
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis