Majority of the Bests: Improving Best-of-N via Bootstrapping

Inference-time computational methods significantly enhance the reasoning abilities of Large Language Models (LLMs). Among these, Best-of-N has gained attention for its simplicity and scalability. It generates $N$ solutions from the LLM and selects the best one based on the reward model's evaluation. Due to imperfect rewards, even with a large $N$, the probability of selecting the correct answer does not necessarily converge to one. To mitigate this limitation, we propose Majority-of-the-Bests (MoB), a novel and hyperparameter-free selection mechanism that estimates the output distribution of Best-of-N via bootstrapping and selects its mode.Experimental results across five benchmarks, three different base LLMs, and two reward models demonstrate consistent improvements over Best-of-N in 25 out of 30 setups. We further provide theoretical results for the consistency of the bootstrapping.