# Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling

arXiv: https://arxiv.org/abs/2510.03199 · HTML: https://mlsanity.com/paper/2510.03199/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 60 of its 73 references that are in the map.
- First posted on arXiv 3 Oct 2025.

## Builds on (most cited first, 30 of 60)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Scalable Diffusion Models with Transformers](https://mlsanity.com/paper/2212.09748/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Scaling Autoregressive Models for Content-Rich Text-to-Image Generation](https://mlsanity.com/paper/2206.10789/) (2022)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [WorldSimBench: Towards Video Generation Models as World Simulators](https://mlsanity.com/paper/2410.18072/) (2024)
- [Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2307.15217/) (2023)
- [Deep Learning Scaling is Predictable, Empirically](https://mlsanity.com/paper/1712.00409/) (2017)
- [Scaling Laws for Autoregressive Generative Modeling](https://mlsanity.com/paper/2010.14701/) (2020)
- [InternLM2 Technical Report](https://mlsanity.com/paper/2403.17297/) (2024)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)

## Built on by (most cited first, 9 of 9)

- [Why Pass@k Optimization Can Degrade Pass@1: Prompt Interference in LLM Post-training](https://mlsanity.com/paper/2602.21189/) (2026)
- [Demystifying LLM-as-a-Judge: Analytically Tractable Model for Inference-Time Scaling](https://mlsanity.com/paper/2512.19905/) (2025)
- [FUSE: Ensembling Verifiers with Zero Labeled Data](https://mlsanity.com/paper/2604.18547/) (2026)
- [Reasoning or Fluency? Dissecting Probabilistic Confidence in Best-of-N Selection](https://mlsanity.com/paper/2601.13735/) (2026)
- [Predicting and improving test-time scaling laws via reward tail-guided search](https://mlsanity.com/paper/2602.01485/) (2026)
- [FluxLite: Inference-Time Proposal Control for Discrete Diffusion Models](https://mlsanity.com/paper/2609.35947/) (2026)
- [The Statistical Benefits of Multiple Responses for Learning from Demonstrations](https://mlsanity.com/paper/2609.33291/) (2026)
- [Provable Test-Time Scaling for Beam Search in LLM Reasoning](https://mlsanity.com/paper/2609.38672/) (2026)
- [Universal Bounds for Self-Normalized Kullback-Leibler Estimation](https://mlsanity.com/paper/2610.12851/) (2026)

## Abstract (arXiv)

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=tildeOmega(C^*), the regret of BoM is O(εopt+√εRM2C^*/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.