Majority of the Bests: Improving Best-of-N via Bootstrapping
This addresses a reliability issue in LLM output selection for tasks with discrete answers, offering a simple alternative that could benefit AI practitioners, though it is incremental as it builds on existing BoN and self-consistency methods.
The paper tackles the problem of Best-of-N (BoN) selection failing with imperfect reward models in LLMs, proposing Majority-of-the-Bests (MoB) which uses bootstrapping to estimate the output distribution and select the mode, achieving improvements in 25 out of 30 experimental setups.
Sampling multiple outputs from a Large Language Model (LLM) and selecting the most frequent (Self-consistency) or highest-scoring (Best-of-N) candidate is a popular approach to achieve higher accuracy in tasks with discrete final answers. Best-of-N (BoN) selects the output with the highest reward, and with perfect rewards, it often achieves near-perfect accuracy. With imperfect rewards from reward models, however, BoN fails to reliably find the correct answer and its performance degrades drastically. We consider the distribution of BoN's outputs and highlight that, although the correct answer does not usually have a probability close to one under imperfect rewards, it is often the most likely outcome. This suggests that the mode of this distribution can be more reliably correct than a sample from it. Based on this idea, we propose Majority-of-the-Bests (MoB), a novel selection mechanism that estimates the output distribution of BoN via bootstrapping and selects its mode. Experimental results across five benchmarks, three different base LLMs, and two reward models demonstrate consistent improvements over BoN in 25 out of 30 setups. We also provide theoretical results for the consistency of the bootstrapping. MoB serves as a simple, yet strong alternative to BoN and self-consistency, and more broadly, motivates further research in more nuanced selection mechanisms.