Study Pass@$k$ inference, where the model may submit $k$ answers.
Prove that majority voting and best-of-$N$ do not scale correctly in both $k$ and the sampling budget $N$.
Best-of-Majority keeps high-frequency answers among $N$ samples, then selects the top-$k$ by reward.
When $N=\tilde{\Omega}(C^*)$, the regret is $O\bigl(\epsilon_{\mathrm{opt}}+\sqrt{\epsilon_{\mathrm{RM}}^2 C^*/k}\bigr)$, matching a lower bound for any Pass@$k$ rule.
Unlike majority voting and best-of-$N$, the bound does not degrade as $N$ grows. BoM also outperforms both on math reasoning tasks.