Majority of the Bests: Improving Best-of-N via Bootstrapping
Amin Rakhsha, Kanika Madan, Tianyu Zhang, Amir-massoud Farahmand, Amir Khasahmadi
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 noisy rewards, even with a large number of sampled solutions for a given question, the probability of selecting its 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.