We thank the reviewer for their thorough review with close attention to details of our work. We would like to present further analysis on when MoB work and clarify some of the concerns.

When does MoB succeed/fail?

The change from BoN to MoB can be split into two steps:

1. Change from Best-of-$N$ to Best-of-$m$: To be able to approximate the distribution, MoB is forced to work with the output distribution of Best-of-$m$ ($\pi_m$) for some $m < N$. This is usually inferior to $\pi_N$ used by BoN, which means this step is a downgrade in accuracy.

2. Change from Best-of-$m$ to MoB: MoB estimate and picks the mode of $\pi_m$, but Best-of-$m$ samples from it. If the mode is correct, MoB will be correct with high probability and improve the success probability over Best-of-$m$. On the other hand if the mode is not correct, the small probability to solve the problem by chance is eliminated and MoB will be worse.

Together, the impacts of these two steps on the performance govern whether MoB will outperform BoN or not. The impact of each of these steps varies for each question and depends on the base model's generation and reward model's reward distributions in that question. These two distributions, especially the reward, can be complex. We suggest the following two scalar metrics to allow further intuitive analysis.

• BaseSProb = Chance of a generation being correct.
• RewardAcc = Fraction of correct-incorrect output pairs correctly judged by the reward model.

These two metrics can be estimated for each question and evaluate how good the base and reward models are for that question. We now study how these metrics can predict the impact of the modification steps from BoN to MoB discussed above. Then, we study when MoB can improve over BoN.

Impact of the change from Best-of-$N$ to Best-of-$m$ (Step 1)

Consider the setup with MMLU-Pro-Math, gemma2-9b-it, and ArmoRM. To match our experiments section, we set $N = 128$. The following table shows the accuracy of Best-of-$N$ minus the accuracy of Best-of-$m$ for subsets of the benchmark with different reward and base model accuracies. Note that the value of $m$ varies among questions.

The smaller the advantage of Best-of-$N$ over Best-of-$m$ shown in the table is, the less MoB suffers from its use of $\pi_m$ instead of $\pi_N$. The results of the table match the intuition, increase in budge from $m$ to $N$ is more beneficial in questions with good rewards (top row). Especially when the chance of generating the correct answer is small, we benefit a lot by having a larger number of generations $N$ compared to $m$ (top-left cell). MoB is negatively affected if the BoN performance is not saturated for a question and more budget significantly improves BoN performance.

Impact of the change from Best-of-$m$ to MoB (Step 2)

We can categorize questions into three categories:

• Type A: Questions where mode of $\pi_m$ is correct, and $0.1 \le \pi_m(Z^*) \le 0.9$. Picking the mode is better than sampling.
• Type B: Questions where mode of $\pi_m$ is incorrect, and $0.1 \le \pi_m(Z^*) \le 0.9$. Sampling is better than picking the mode.
• Type C: Questions where $\pi_m(Z^*) > 0.9$ or $\pi_m(Z^*) < 0.1$ . Sampling and picking the mode are similar.

The impact of this step can roughly be measured by the number of questions of type A and B. Higher number of type A questions have a positive effect on the performance of MoB. Table 2 shows the frequency of these types in each combination of generation and reward accuracy.

In questions with poor generation or rewards, the mode is incorrect more often. In comparison to BoN, MoB has a smaller probability to solve these questions by chance.

Comparing MoB and BoN under various generation and reward accuracies

The relative performance of MoB to BoN depends on the combination of the impacts of the two steps. The following table gives the final accuracies.

In questions where the base model's success probability is at least 0.25, MoB performs better. This can be explained by the fact that number of type A questions are larger than type B questions. The positive effect of step 2, is over dominating the the negative impact of step 1 in high-accuracy reward questions as well. In contrast, in question with very small base model success probability, BoN's performance is not saturated with our current choice of $N$ (large negative impact in step 1), and also there are more type B questions than type A. This leads to BoN outperforming MoB.

Comparison of 30 setups

Now we can explain why in some setups MoB introduces more improvement than other setups. In the accuracy plots (Fig 13-17) we observe that the performance of BoN plateaus quite early in almost all benchmarks. This means the impact of step 1 should be minimal, and most of the variation among setups should come from the impact of step 2. To test this, we calculate the difference between the number of type A questions and the number of type B questions for all 30 setups. Our analysis is verified by the fact that this metric has a spearman correlation of $0.89$ with the difference between MoB accuracy and BoN accuracy.

Clarifications

(W1 and W2) Demonstrating the capabilities of a general-purpose test-time scaling method is inherently challenging, as it involves choices across numerous dimensions—generative models, reward models, and benchmarks. We aimed for as comprehensive an evaluation as feasible by selecting generative models from diverse families and benchmarks spanning multiple subjects. From the RewardBench leaderboard, we intentionally selected strong, uncontaminated reward models, particularly those performing well on reasoning tasks. This combination of models and benchmarks resulted in 30 distinct experimental settings, which, in our view and compared to prior work, represents a broad and meaningful coverage of the space—though we acknowledge that alternative selections could certainly be made.

Our choice of benchmarks was guided by two considerations: (1) a focus on tasks with discrete final answers, enabling the majority voting mechanism integral to MoB, and (2) coverage of domains where reasoning is critical. We also note that RewardBench2 was released after our submission deadline. However, above, we have reported math500 results for the strongest model on their leaderboard—Skywork- Reward-V2-Llama-3.1-8B—and these results are consistent with the overall findings we present. We plan to expand these updates in the paper by including results for the rest of the benchmarks and generative models using this reward model.

(W3) Regarding the use of few-shot prompting versus CoT, we aimed to follow the common practice for each baseline setting. Our primary focus was to keep variation factors consistent when comparing MoB with other baselines, ensuring that differences in results reflect the methods themselves rather than inconsistencies in setup. The use of few-shot prompts for GSM8K was, in fact, unintentional—we relied on the default configurations in LM Evaluation Harness for that experiment. We will clarify this in the paper and ensure alignment with the implementations and intentions described in the original works. Lastly, we studied the general problem of selecting among a given set of outputs using scalar rewards. Li 2022 originally introduced WBoN in a more special case that we have control over the generation and more informative rewards, but our implementation of the algorithm is widely used by the community in our general problem setting as well.

(W4) We have tried our best to provide a fair comparison of our method with the baselines. In our tables, intervals that contain the highest average accuracy are bolded. This is perhaps not a common strategy, and we will change it. However, it is not always in favor of MoB and is applied consistently. Lastly, the 25 out of 30 claims is based on averages.

We thank the reviewer for their review with multiple insightful points. Here are some thoughts and clarifications.

(W1) This is indeed an interesting question. The uncertainty of reward and BoN output is perhaps an informative signal that can be used to modify our agent sampling budget or sampling temperature. If we are restricted to the outputs and rewards given to us, the mode might be useful. If it is correct, the agent will be correct deterministically instead of having a probability much lower. This approach has been proven widely usefully by self-consistency too. More often than not, the mode is correct and picking it almost deterministically is a better approach than sampling. Our observations confirm this for BoN output distribution.

(W2) It is true that extreme statistics are more tricky to bootstrap. This is exactly the reason we have the more complicated approach of choosing the subsample size $m$ smaller than $N$ and carefully pick it. However, as we provide the literature, it has been studied thoroughly and has both empirical and theoretical support. The small sample size can also make the estimate difficult. The main point that makes our algorithm viable is that the accuracy of distribution estimation is not critical to the algorithm. We are only concerned with picking the mode, which can be done with rough estimations as well. Even if an error happens, we still pick a descent output as BoN already is a strong algorithm that samples from the distribution.

(W3) The goal of that figure was to show there are significant number of question in our dataset that picking the mode is significantly different from sampling, hence motivating MoB. If the probability of the correct answer is close to 0 it will not be picked by neither of sampling or mode selection. On the other hand, if its probability is close to 1, it will be picked almost certainly by both methods. It is only in the intermediate probabilities that mode selection deterministically succeeds/fails, but sampling remains stochastic.

(W4) The latency of all these algorithms is with orders of magnitude dominantly governed by the latency of output generation. LLM inference is far slower than the selection phase. Roughly speaking, the outputs are generated in 10s or at most 100s tokens per second and generating a typical 1000-token output will take a few seconds. For comparison, the CPU compute of MoB in our experiments was $2.6$ milliseconds, which is practically negligible. It is true that BoN has a faster selection but it is irrelevant for the whole algorithm latency.

(Q1) In the experiments we estimate it by generating far more than $N$ outputs. The naive approach is to run Best-of-$N$ many independent times and use the empirical distribution. We use bootstrapping here to reduce this cost and use $\hat \pi_{N, 1400}$. Nonetheless, it is a very computationally heavy task and we have only done in one of the settings to provide intuitions of the algorithm. More details is provided in Appendix D.2.

We thank the reviewer for their feedback and positive review. We would like to present some clarifications and additional experimental results to address the reviewers concern.

(W1 and Q2) Our choice of models was limited by our resources and desire to test our algorithm on many environments with reasonable confidence intervals. Nonetheless, as the reviewer suggests, some experiments on larger models will also be insightful. To address this, we here provide the results for GPT-4o-mini on MATH500 and ArmoRM reward model.

This is aligned with our observations with smaller models and show MoB outperforming the baselines. We will try to provide further results with larger models at the time of publication of the paper.

(W1) Regarding ablations on $B$, we want to further clarify that the approximate distribution $\hat \pi_{m,N}$ can be calculated in close-form, and sampling from it to find its mode unnecessary. We introduced $B$ for the sake of simplicity of the main text and intuitive understanding of the algorithm. In line 181 we referred to Appendix B where the close-form is presented. Though admittedly, we have not been clear enough and other reviewers also missed this. The close-form calculation of the approximate distribution allows us to achieve the same distribution as achieved with $B = \infty$. Our implementation of the algorithm does not have a parameter $B$ at all.

(W2 and Q1) We thank the reviewer for the suggestion to expand our anlysis of MoB failure modes and the conditions of its improvement, We also believe it will strengthen the paper. Towards this, we present an extensive new set of analysis that we have provided in our response to reviewer DAFe. We refer the reviewer to that response for complete details. As a summary, we further confirm our insights from Appendix C in one of realistic experiments. There are two factors that can negatively affect MoB:

1. MoB works with Best-of-$m$ instead of Best-of-$N$ for some $m < N$. This negatively affects MoB If BoN's performance is still not saturated, and we significantly benefit from a larger number of outputs ($N$ compared to $m$).

2. MoB picks the mode of output distribution of Best-of-$m$. While it is immensely helpful and is the main reason for the better overall performance of MoB compared to BoN in our benchmarks, it might be downgrade the performance if the mode is not correct. If the correct answer is not the mode, it might get a chance to be chosen when sampling, but MoB's mode selection significantly reduces this chance.

In our complete discussion in our response to reviewer DAFe, we report the impact of each of these two factors for questions with various base model success probability and reward accuracy. We confirm the insight from Appendix C in the synthetic example. The first failure mode is question with very low base success probability, which the reviewer mentions here. We observe that amon these questions, either questions where the mode is incorrect are more common, or BoN can still benefit from more generations to have more correct ones. Second failure case is questions with low quality rewards. This is explained by the higher number of questions where the mode is incorrect. Overall performance of the algorithms is governed by how many questions fall into these failure modes.

(W3 and Q3) It is true that MoB can only improve BoN when discrete output space and repetition in final answers allow majority voting. However, unlike SC which turns into random selection in absence of final answer repetition, MoB just matches BoN. We can still run MoB by setting $Z_i = f(Y_i) = Y_i$. If all $Z_i$ s are distinct, MoB's choice will be the same as Best-of-$N$, as long as $m > 1$. To see this, we can use the close-form description of $\hat\pi_{m,N}$ in line 470. Lastly, we have already included SC in all our experiments. Perhaps the reviewer could further clarify what result they believe can benefit the paper.

We appreciate the reviewer's close attention to our work and thank them for their time and thorough review. We present some clarifications and additional experimental results to hopefully address the reviewers concerns.

(W1) We appreciate the reviewer's suggestion. Here are the results on MATH500 benchmark using Skywork-Reward-V2-Llama-3.1-8B reward model. This model is currently ranked first on RewardBench overal ranking and second in the math ranking.

We see that MoB's again provides the best or the second best performance. It is important to note that the dependence on reward imperfection is not a sign that MoB will become obsolete with better reward models, or it lacks any merit. First, as models progress, we will aim to solve more and more difficult tasks that will keep challenging the models. The newer and stronger reward models will again prvide imperfect models in the newer more difficult tasks. Second, there is a significant cost in using larger models. MoB provides an unarguable benefit by allowing the use of cheaper models that provide lower quality rewards to save costs. The chosen reward models were the SOTA in reasoning performance on RewardBench among their size classes at the time of submission.

(W2) We understand the reviewer's point of view and perhaps the paper needs some clarification. The reason we compare MoB to BoN is because of its algorithmic similarity to it. We view MoB as an algorithm that picks the mode of BoN output distribution instead of sampling from it. Also it is important to note that if the output space is not discrete (all $Z_i$ s are distinct), BoN, WBoN, and MoB all become equivalent (See equation at line 470 in appendix for justification for MoB-BoN equivalence). It is true that MoB's improvement is only in the cases of discrete outputs. and they are equivalent otherwise. As a brief comparison with WBoN, MoB has a higher accuracy in 27 out of 30 setups (ignoring confidence intervals).

(W3) Indeed, we agree that a breakdown of for questions the MoB is the most helpful is a valuable insight. In our respponse to DAFe, we have included an extensive study of this subject. We categorize questions based on the quality of output generation and rewards and describe the behavior of two factors that together determine how MoB performs compared to BoN. Lastly, the results for all 30 setups are already included in our supplementary material due to the space constraints of the main text.

(W4) We still want to emphasize that neither of $q$ and $B$ need to be tuned. Regarding $B$, in fact there is no choice of $B$ in our implementation! As we briefly mention in line 180 (which perhaps needs to be more clear) and explain in detail in Appendix B, $\hat \pi_{m,N}$ has a close-form solution and there is no need to estimate it through $B$ samples. Using this close form, we operate equivalent to $B = \infty$ as also mentioned in implementation details in line 522 of supplementary material. Even if $B$ is used for Monte Carlo estimation, it is rarely discussed in any bootstrap papers as it just needs to be sufficiently large. Also for $q$, there is literature on the insignificance of its choice (c.f. line 283). To further test this in the following table, we provide the ablation results on the value of $q$ on Llama3.1-8b-instruct and ArmoRM across benchmarks, which confirms the negligible importance of the choice of $q$.

(W5) We agree with the reviewer that further studies on generative reward models will be insightful. We hope the results with Skywork reward model addresses the reviewers concern.

(W6) We again refer the reviewer to Appendix B where we introduce a close-form calculation of $\hat \pi_{m,N}$ that allows us to operate equivalent to $B=\infty$ in $O(N\log N)$ compute complexity. Our implementation of MoB took an average of 2.6 milliseconds on a laptop CPU. This is irrelevant compared the latency in generating the outputs.

(Q1) This is the result of one of the weaknesses of WBoN that limits its applicability to positive rewards. It seems like GRM reward model is outputing negative rewards in the CSQA benchmarks. We are not aware of a standard way to fix this. For example naively adding a constant to the rewards, turns WBoN to SC.

(Q2) Absolutely. The plots for all setups are provided in the supplementary material (Figures 13-17).