Majority of the Bests: Improving Best-of-N via Bootstrapping
Authors: Amin Rakhsha
Kanika Madan
Tianyu Zhang
Amir-massoud Farahmand
Amir Khasahmadi
Venue: NeurIPS 2025 poster ()
Keywords: llms
test-time compute
best-of-n
bootstrap
inference-time computation
Primary area: deep_learning
TL;DR: We improve best-of-n leveraging bootstrapping without computational overhead.

Abstract: 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.

Majority of the Bests: Improving Best-of-N via Bootstrapping
Amin Rakhshal.24 1,2,3*
Kanika Madan 3
Tianyu Zhang
Amir-massoud Farahmand 4,3,1
Amir Khasahmadi
University of Toronto
2 Vector Institute
Autodesk
Polytechnique Montréal
Mila Quebec Al Institute
Abstract
Sampling multiple outputs from Large Language Model (LLM) and selecting the most frequent (Sosf-consistency) or highest-scoring (Best-of-N) candidate 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 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 sample from it. Based on this idea, we propose Majority-of-the ---tt-eettts 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 30 setups. We also provide theoretical results for the consistency of the bootstrapping. MoB serves as simple, yet strong alternative to BoN and seff-consistency, and more broadly, motivates further research in more nuanced selection mechanisms.?
Introduction
Scaling the inference-time computation of language models has led to a significant improvement of their performance on variety of tasks (Brown et al., 2024; Snell et al.. 2025; Wu et al., 2024; OpenAI, 2024; DeepSeck-AL, 2025). A growing number of methods have been introduced this paradigm, such generating long chains-of-thound asking the model to evaluate and improve its own outputs (Madaan et al., 2023), and tree search (Yao al., 2023; Hao et al., 2023; Zhang al., 2024). Another family of such algorithms, termed sumple-and-margindde
(Wei et al., 2022; Muennighoff al., 2025),
by Wang et al. (2022), generate multiple outputs from the model and then aggregate them into final answer. Examples include Self-consistency (Wang al., 2022), Best-of-N (Lightman et al., 2023), and Weighted Best-of-N (Li et al., 2022). These methods have gained popularity due to their simplicity and scalability.
"Work done during internship Autodesk. Correspondence aminrêcs. tdronto.edu. Code and data available at
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

y1
y55
y1
y1
Answer
Sumpling AM
y2
y3
y4
y3
Mojerty siding
Question
:
B
final answve
12
2.5
F22
y5
y6
y2
y6
fina answer
25
y1 3/
final amnserr
y5
y4
y4
Majority-of-the oofe------tthhetttee first, N outputs are generated for the given question. Then, we create a large number of subsets of size m N by sampling with replacement from the generated outputs. From each subset, we choose the output with the highest reward. The most frequent answer among these chosen outputs reported as the final answer.
Figure 1:
Self-consistency (SC) (Wang et al., 2022), also referred to as "majority voting", is widely used algorithm in this paradigm. It samples multiple outputs from the model and selects the final answer that appears most frequently among them. SC improves the performance by leveraging key property of the model's output distribution: on difficult problems, the probability of generating the correct answer often far from 1, making single-sample predictions unreliable. SC capitalizes on the fact that, even if the model's output distribution is imperfect, it may still favor the correct answer and generate it more frequently than incorrect ones.
Best-of-N (BoN) (Lightman et al., 2023) uses a reward model to evaluate the generated outputs and chooses the final answer in the highest-scoring output. With an ideal reward model, BoN succeeds as long as one of the generated outputs is correct. In this paper, we highlight that in the realistic setting of an imperfect reward model, the success of BoN is no longer (nearly) guaranteed. In such cases, BoN exhibits stochastic behavior akin to the underlying generative model. While the reward model improves the likelihood of selecting the correct answer, it often falls short of ensuring certainty. This is the same property that underlies the effectiveness of SC. Motivated by this observation, we show that applying similar principle-aggregattnn multiple samples identify the most probable answer-leads to a better performance over BoN.
We introduce Majority-of-ther th-ts--eessss (MoB). method that leverages bootstrapping improve upon BoN by approximating the most probable output of BoN. As illustrated in Figure 1, after obtaining multiple (parallel) solution samples for given question and computing their rewards, we apply bootstrapping: we create subsets of size m by sampling with replacement from the generated outputs. For each subset, select the sample with the highest reward. This results in new set of high-reward samples, over which we perform majority voting to determine the final answer. Just like BoN and SC, MoB can be applied independent of the output generation procedure. It only modifies the selection of the final answer with marginally extra computation on the CPU. We provide procedure to adaptively select m, eliminating any critical hyperparameters from the algorithm. We show the consistency of the algorithm theoretically. and empirically show significant improvements over BoN on 25 out of 30 tested setups.
2 Background
In this section, we formulate BoN and bootstrapping and provide some background for the algorithm and its theoretical grounds. Given a prompt I, in the standard procedure with LLMs, we sample an output Y ~ Piet from base model Pief. This output yields corresponding final answer Z = f(Y) after applying post-processing or evaluation function f. For example, for a multiple choice problem, Z is the chosen option and Y is the whole output containing both Z and its justification. We denote the distribution of the final answer in this procedure as Teel that is, Z Tee- The goal is find the correct final answer
z". We define the success probability for this given problem as the probability of selecting the correct final answer. If the algorithm's final answer is Z. the success probability is defined as PZZ- = =²) =²). Given dataset of questions, the average of the success probabilities over all questions referred to as the accuracy. For the standard procedure, the success probability equal to [x)(("") and the corresponding accuracy is called the pass @1 accuracy. We assume access to

---

Correct
Probability
Incorrect Output
0.8
25
Density
Frequency
15
0.4
0.2
5
0.05
0.15
0.1
0.1
N
Reward Value
Success Probability
Figure 2: (Left) BoN's success probability as a function of N for question 647 from MMLU-Pro-M The success probability remains below 80%. (Middle) Distribution of the reward for correct and incorrect outputs for the same question. A separation between the two distributions is ideal. (Right) Histogram of Best-of-64 success probabilities over 500 questions.
reward model r that assigns a reward = r(Y) to the output Y, reflecting its accuracy, coherence, or alignment with human preferences (Uesato et al., 2022; Lightman et al., 2023). For given budget N, sample-and-mare margdnalizze algorithms generate N independent outputs Yı,-.. YN Pref and select the final answer reached by one these outputs, BoN selects the final answer from the output with the highest reward, that is,
Z Best
= =f( argmax r(y)).
N
WE (V1.....N))))
Regularized versions of BoN have also been introduced to address its reward hacking issues in the presence inaccurate rewards (Jinnai al., 2024; Ichihara et al., 2025). Alternatively, self- consistency or majority voting selects the final answer that occurs most frequently among Z ZN. is large enough, this most frequent answer
where Z, = f(Y,) is the final answer for output Y, will be the mode of the final answer distribution ree Li et al. (2022) suggested the Weighted Best-of- (WBoN) selection method. For each final answer, WBoN sums the rewards of all outputs that lead to it. Then, it selects the final answer with the highest total reward.
Bootstrapping. Bootstrapping a powerful and widely used non-parametric resampling technique for estimating the distribution of statistic repeatedly drawing samples with replacement from the original dataset (Efron, 1992; Efron and Tibshirani, 1994). The core idea is to generate multiple "bootstrap samples", by sampling observations uniformly and with replacement. For each bootstrap sample, the statistic of interest is computed. The collection of these computed statistics from the many bootstrap samples forms empirical approximation of the statistic's true distribution. We use this technique to approximate the distribution of BoN's output.
Motivation: Output Distribution of Best-of-N
To motivate algorithm, highlight the behavior of BoN's final answer distribution. We denote this distribution by n. means,
Best NN-
Assume among the N sampled outputs, N. outputs (Yf,.... ...., Y } S (Y,) yield the correct final answer: f(Y9) z Conversely, N₁,
N₂ outputs [YT".... Y S (V:).1 lead to an incorrect solution. Then, BoN's output is correct if the highest reward among the correct outputs is larger than the highest reward among the incorrect ones. Formally, we can express this condition as:
(Y)
mex(((X"""......((
((Y
(1)
There are two factors that influence the probability this event. First, note that each side of (1) maximum of some random variables. As the number of random variables increases, the probability distribution of their maximum shifts towards higher values. Therefore, larger values of N. and smaller values of N... make condition (1) more likely. The values of N. and N depend mer(2") )

---

the probability of the correct answer 2" in the base model's final answer distribution Tel For large enough n, we will have
N₂ Rd N. Ter((z)) No R N (1 <<r(("))
It means that if the base model has a higher chance of solving the problem, BoN is also more likely to select the correct answer.
The second factor is the distribution of r(Y;9) and r(y,") on each side of (I). The reward a correct output follows the conditional distribution P. - P()()))(()) = =*) while the reward of
an incorrect output follows the conditional distribution Pe & P(r(Y))(())) & =*). We hope that the reward model assigns higher rewards to correct outputs, and r(y,)) Pe on the left side of (1) generally be larger than r(Y;")) ~ Pw on the right side.
Therefore, the success probability of BoN heavily depends on the separation between Pa and P.- A perfect reward model would always assign a higher value to a correct output than to an incorrect one. In that case, long at least one correct output is generated (which is highly likely for large enough N). condition (1) is satisfied. The resulting success probability is close to I, indicating a nearly deterministic final answer. On the other hand, consider the case where P. and Pw are identical. In this case, the reward of an output becomes independent of its correctness, and choosing according to the reward model will be no better than random choice. Consequently, the success probability of BoN will be the same as the base model, i.e. N (2") = T=)((=). In practice, our reward models exhibit a middle ground between these two extremes. They might not be perfect for BoN to succeed with single correct output, but they can still be somewhat informative to increase the success probability of BoN compared the base model.
In Figure 2, we show an example of these dynamics for Question 647 of the MMLU-Pro-Mo Pro-Matth benchmark (Wang et al., 2024b) with base model Qwen2.5-3B (Qwen Team, 2024) and reward model ArmoRM ( (Wang et al., 2024a). We approximate the output distribution Pref with large pool of 1400 samples. In Question 647 (Figure 2), the two distributions Pa and P.. overlapping, and even with large values of N, the success probability remains below 80%. Nonetheless, BoN still outperforms the base model, which is equivalent to Best-of-1 1 and has success probability of 30% in this case.
We expect the stochasticity of BoN's output to depend on the difficulty of the question relative to the base and reward models' capabilities. For more difficult questions, the base model generates fewer correct outputs, and the reward model is less likely to distinguish the correct outputs from the incorrect ones. Through the two factors discussed above, BoN is not able pick the correct answer with high certainty. The right plot in Figure 2 shows the histogram of the success probability of Best-of-64 among 500 randomly selected MMLU-Pro-Me 175 problems, BoN has a success probability between 0.1 and 0.9. That means, BoN has a significant chance of returning the correct answer but fails to do reliably. The idea behind our introduced method, MoB, is that if we can find the most probable output of the BoN distribution, we may reliably pick the correct answer even if its probability is well below 1.
problems. We see that for approximately
4 Majority-of-the-Berr
In Section 3, we showed that BoN's final answer is stochastic, and this stochasticity might remain true even with a very large budget N. In this section, we introduce MoB can select the correct answer with high probability as long as the correct answer is the most probable output of BoN, even if its probability is well below 1. We first showcase this idea in the hypothetical case where BoN's output distribution n is given by an oracle. Later, we show how to estimate this distribution using bootstrapping.
offority-of-the-Besss (MoB).
4.1 MoB with Oracle Access BoN's Output Distribution
Suppose the distribution of BoN's final answer n is known through an oracle. Instead of sampling from this distribution, which is equivalent to BoN and is a noisy decision, we propose selecting the mode of this distribution. That is
2
OracleMoB argmax NN (z).
(1)

---

70.0
65.0
62.5
Accuracy (96)
63.0
Accuracy
60.0
57.5
57.5
55.0
BoN
MoB
MoB
52.5
50.0
MoB
10
20
30
40
50
60
10
30
50
60
Number Generations (n)
Number of Generations (n)
Figure 3: Final answer accuracy comparison of BoN, MoB, and Oracle MoB MMLU-Pro-Math using Qwen2.5-3B (Left) and Llama3. 1-BB (Right) as the base model, and ArmoRM as the reward model. Results are averaged across all problems and multiple runs. Shaded area indicates the standard error.
We refer to this algorithm as Oracle MoB as it relies on an oracle. By selecting the mode, the correct answer has higher probability than any of the other answers, it will be selected without any randomness that would reduce the success probability. Since Tref = TI, we can say SC for a large N equivalent Oracle MoB with N 1. It has been extensively shown that SC improves the LLM's original accuracy. As we will also empirically show, MoB similarly increases the accuracy of BoN by selecting the mode of its output distribution.
In Figure 3, we compare the accuracy of Oracle MoB with BoN on MATH500 (Lightman et al., 2023; Hendrycks al., 2021) and math problems of MMLU-Pro (Wang al., 2024b). We use the same output pool, base model, and reward model as Figure 2. We can see that depending on the value of N, Oracle MoB provides 5 to 10 percentage points improvement accuracy. Oracle MoB unrealistically requires an oracle access to n.. Next, we will show how nN can be estimated via bootstrapping and remove the oracle dependence.
MoB with Estimated BoN's Output Distribution
We discuss how, without the oracle access to the BoN's output distribution TN, approximately find its most probable output. The most obvious approach is to follow the same procedure SC. For some k 2 1, we rum l independent BoN procedures, each with outputs. Then, out of the resulting answers, we select the final answer that appears the most number of times. The answer of the BoN procedures let approximate mm. and selecting the most frequent answer among them will approximate Oracle MoB (1) with budget m. We refer to this algorithm as "BoN+SC" due to its simple combination of BoN and SC. To keep the generation budget fixed at N, we are forced to use smaller budget m for each of the BoN runs. For now, we treat the choice of m hyperparameter, but will return this choice later. Assume m N and [N/m]. Formally,
Z Best, m
=
argmax
r(v)
(i = 1,...... 1,....)),
(2)
WE (Vins (1+1)m-1)
BBNN + SC mn
argmax
Beat = =2]_
The main problem with BoN+SC is that it is too expensive. We would like to have a large value for m to get the benefits offered by BoN. To have a fairly accurate estimation of Ti, we need reasonably large value for kt Together, this requires a large budget z mk.
The deficiency of BoN+SC comes from the fact that each sample Y, only contributes to generating one BoN output. To address this deficiency, we propose estimating m. not by generating independent samples from it, but by bootstrapping. To do that, we first note that the distribution n.m of 2Best is a function of the unknown distribution Pres- Bootstrapping suggests to estimate 7m with the BoN's output distribution under known approximation Piet s Pref- The typical non non-parametric approach is
5

---

0.50
BoN
BoN
Approximated Distributon Eiror
MeB
MoB
0.45
0.40
0.35
Accuracy
0.30
0.20
0.10
60
100
Number Generations (n)
Generations
Figure 4: Comparison of MoB and BoN+SC using Qwen2.5-3B as the reference model and ArmoRM as the reward model. (Left) 7m approximation error in é -n-orrm for m = 8. (Right) Average accuracy on MMLu-Pro-Math dataset. Shaded area indicates the standard error.
to set Pref to be the empirical distribution of the generated samples (Y,,... J. Since Pret is known, cheaply sample from it. For any arbitrarily large value B, we generate B approximately sampled BoN outputs. We first create B datasets of size m from Pret That is
Dj = (Yr,, Y,. ~ Pret:
(i= (I=1...,,B) B).
This is equivalent to sampling m outputs from the original pool (Yí... Yn with replacement.
Then, similar to BoN+SC, we can run BoN on each dataset, and then pick the most common outcome. Formally,
Best, mm
aargmax r(y)
(i 1,..... B),
(4)
vED.
B
2 MaB M.N
argmaa
Σ
2
Best.())
m
=
(5)
This procedure our MoB algorithm for a given m. We define w, be the (random) distribution of (1), given {Yi} at hand. With sufficiently large B (usually B 10, 000 is sufficient), the empirical distribution of (Bsst.()) will accurately estimate um,N. With this approximation, we can write
MoR so arginax क (z)
(6)
Note that this is a light computation that can carried out on the CPU. Therefore, we can freely choose large B. In the supplementary material, provide an even more efficient way of estimating fm,N with O(N log N) complexity that finds 2 directly and without creating B datasets. It worth mentioning that our use of bootstrap samples resembles bagging (Breiman, 1996) and subagging (Scornet et al., 2015), where a family of models is trained on the subsampled datasets and then aggregated.
In Figure 4, we compare MoB with BoN+SC in the same setup as Figure 3. In the left plot, we fix m and compare the algorithms' error on estimating Tm for range of values for N. We measure the distance between the two distributions according to the fn-nomm As can see, bootstrapping is consistently the superior approach for this approximation task and offers a more accurate estimation of mm the right plot, we set m LvN N and compare the final accuracy of the algorithms. The choice of m = [/N] ensures that ze VN and will also increase as N increases. We observe that the superior accuracy of bootstrapping in the estimation of Tm translates to better final accuracy of the algorithm, especially when the budget is more limited.
One might wonder if it is possible to choose to be much larger than what was possible in BoN+SC, potentially even m N. There no obvious limitation on the size of resampled datasets Dü, and nonetheless, most commonly in bootstrapping, the size of resampled datasets is equal to the original

---

0.650
0.673
Accuracy (S)
0.575
Accuracy (%6
0.550
0.625
0.525
0.000
0.500
Mell (0ptimal ml
0.575
Moll (Oiptimal
McB (Adaptive)
McB (Adaptive)
McB (N)
0.550
McB (m (N)
Number of generations (n)
Number generations (n)
Figure 5: Comparing selection methods using ArmoRM reward model with MMLU-Pro C---U--PPMatt and Qwen2.5-3B (Left) and MATH500 and Llama3. 1-8B (Right). Shaded area indicates the standard error.
dataset. However, estimating the distribution of values related the cxtremes random samples is a classic example of failure for the conventional bootstrapping, see for example Athreya and Fukuchi (1994) and Efron and Tibshirani (1994, Section 7.4). Since BoN selects the output with the highest reward, it is affected by the same failure. To this, note that the output with the highest reward appears in each dataset with the probability of (N-1) ym, and it will be chosen any dataset in which it appears. Therefore, if m N.
N N
IP [BBsst.0)
Best 2 21-
1 - -- 0.632.
This means that NN.N will always incorrectly assign probability of at least 0.632 to the conventional BoN's 's answer.
Fortunately, using smaller resampled datasets, failures of bootstrapping and is well-studied in the literature Athreya and Fukuchi, 1994; Bickel al., 2011 I). This approach is referred to m-out-of-n bootstrapping. We show that under the usual conditions of m--ut-of-n bootstrapping and mild assumptions on the tail of reward distributions, our of bootstrapping estimate Tm valid one. Similar the typical guarantees for bootstrap estimations, we show that our bootstrap estimation is indeed consistent.
do in MoB, is of the remedies for such
Theorem Under mild assumptions on the distribution of rewards, if there are finite possible values for Z and N + oo, we have m - oc and m/N - O, then the estimated im.N will converge to the true distribution wi- That is, for any e 0,
Jim P[ - Tmll 2 =0 40000
We defer the exact technical statement and proof to the supplementary material. Theorem shows that the estimated distribution #,. will match the true BoN output distribution Tn, means that MoB with bootstrapped distribution in (6) will reach the same accuracy as its oracle version in (1), but with a larger required budget due to m N. To achieve this, it suffices to pick m such that the condition of Theorem holds, which is possible by simply using fixed schedule of the form m(n) = n for some a < 1. the next section, we will discuss the choice of m in more detail and provide procedure to choose automatically.
4.3 Adaptive Subsample Size
The choice of m imposes trade-off. A larger value of m means that we are running BoN with larger number of samples. Since we expect the success probability of BoN to increase with more samples, this means that the mode of T. will be more likely to be correct. On the other hand, as m becomes larger and closer n, our estimate a,,N nm becomes more inaccurate. As we saw in Section 4.2, bootstrapping might fail to provide a consistent estimate if m N.
Ideally, would like to find such that our final answer MMoB based the estimated distribution in (6) becomes closest the Oracle MoB (1) of Section 4.1. The natural approach for this goal is

---

to find the value of m that minimizes the distance between N, and TN. that is
MN argmin Am.N Tv
(7)
This minimization problem automatically captures both aspects of the trade-off. Large values of m make Ty, which is approximated by am..N closer to wN, but at the same time if m is too large, the error of this approximation becomes too large and increases the objectíve || mx
Unfortunately, the distribution Ny in the objective of (7) unknown, and therefore cannot be used in practice. The theoretical results by Götze and Račkauskas (2001) show that if Z only takes two possible values and under some other technical conditions, the distance | - fm/2.N is proportional to the one in (7)*: || - #m/22. x ||ām,N - -xylli
Inspired by this result, Bickel and Sakov (2008) provides some optimality results for choosing m by minimizing the more general loss || m - &mm.N |l for some < q < instead of just = 0.5
considered by Götze and Račkauskas (2001).
Based on the findings of Bickel and Sakov (2008), we propose using the following approach to pick m. We first consider the candidates of the form [g' NJ and pick the value among them that minimizes
| Agm,N l|
m, = | N]
( = 0,,,,,
Mr argmin Ayy Amy-1.Nvl1- m=m;
Note that this involves calculating mn.N for all values of my. These will be just Ollog N) distributions and computationally cheap. Finally, output selected by MoB with adaptive is ZMoB
Z MoB 'N..."
The choice of q has been observed not be critical in most applications. Bickel and Sakov (2008) observes no significant difference among = 0.75, 0.65, 0.6, 0.5. In our experiments, we fix q 0.75. In Figure 5, we evaluate the efficiency of this procedure select m. For each N, measure the highest accuracy achieved by MoB when choosing m from (Nº) for a E [0.1, 0.9). We plot the accuracy of our adaptive m as well as m = vN approach against this optimal performance for two different settings. These figures show both that adaptive m and the simple m = VN achieve performance close to the optimal m variant. This indicates MoB's performance is not sensitive the choice of m and both the adaptive and simple square root choices achieve a near-optimal performance without hy hyperparameter tuning. We repeat this comparison in more settings Appendix E.
Intuitions and Conditions for Improvement
We now investigate why and when MoB outperforms BoN. To this end, we decompose the algorithmic changes from BoN to MoB into two steps, allowing us to study their individual impact more easily. MoB is the result of applying these two changes BoN:
1. Change from Best-of-N to Best-of-m. To be able to approximate BoN's output distribution, MoB forced to work with T., the output distribution of Best-of-m, for some m N.
2. Change from Best-of-m to MoB. The output of Best-of-m is sample from its output distribution Tym On the other hand, MoB estimates Tm and selects its mode.
Together, the effects of these two steps determine whether MoB outperforms BoN. The impact of each step varies by question and depends on the base model's generation distribution and the reward model's reward distribution for that question. These distribution-cca can be complex. To enable an intuitive analysis, we measure two metrics for each question: the base model's 's success probability and the reward model's accuracy, defined as the fraction of incorrect-corees output pairs in which the correct output receives a higher reward. We
esspeccall the reward
'This is a rough interpretation of the results by Götze and Rackauskas (2001), where the ratio of the two losses is studied. We refer the reader to the original paper for more details.
8

---

the highest improvement by MoB over BoNN (Accuracy
(Accuracy
(Accuracy %%
1.00
32
Bom:25
Bom:71
Bom:87
Bom:99
MoB.38
MoB:100
McB:38
McB:97
MoB:99
MoB:100
Bolc45
Bol:83
BoN:95
BoN:
Bom 25
Bom:71
Bom:87
Bom:99
BoN:45
BoN:83
BoN:95
BoN:100
Reward Accuracy
200
261
0231
18G2
120
143
012
192)
134)
050
0323
Dom:13
Bom:48
Bom:73
Bom:92
MoB:8
MoB:60
McB:34
McB:90
MoB:8
McB:68
M4B:94
MoB.90
DoN:18
DoNk:3
DoN:72
BoN:92
0om:13
Dom:48
Bom:73
Bom:92
BoA:10
BoN:53
BoN:72
0oN:92
0.50
Bom:za
Bom:47
MoB:0
MoB.50
Mo8:33
BoN.6
BoNi33
B5
Bom:28
Bom:47
Bom:57
BoN.0
BoNu6
BoN:33
BoN:25
0.25
1.00
Base Success Probability
Base Success Probability
Base Success Probability
Figure 6: Comparison of Best-of-m (m chosen adaptively) Best-of-NN (Left), MoB Best-of-m (Middle), and MoB vs. BoN (Right). Numbers in parentheses are the size of each group.
84
Accuracy (96)
Accuracy (16)
80
DoN SeltCoriistenyy WeightedWestOON
SelfConsistency
Weighted
74
80
Number of Generations (n)
Number of Generations (n)
Figure Accuracy comparison on different datasets using base model Qwen2.5-3B and GRM reward model. Standard deviation is shown as the shaded area. (Left): MMLU-Pro-Chen (Right); GSM8k
then categorize questions into 12 groups according to the value of these two metrics and analyze the effects of our changes each group.
In Figure 6, we compare the accuracy of Best-of-N, Best-of-m, and MoB across the groups for MMLU-Pro-Matt benchmark with Gemma2-9B base model, ArmoRM reward model, and 128. The left plot compares Best-of-N with Best-of-m to show the impact of the first step. In questions with accurate rewards but weak base model performance, BoN benefits the most with more outputs. Therefore, we observe that using m outputs instead of N has the most negative effect on the performance. The performance of Best-of-m compared to MoB in the middle plot of Figure to measure the impact of the second step. In questions where the mode is correct, MoB will outperform Best-of-m by picking
correct answer with high probability, even if its chance selection by Best- of-m is low. On the other hand, if the mode is incorrect, MoB will be wrong with high probability. but Best-of-m can still solve the problem by chance. The effect of choosing the mode instead of sampling on the performance depends on the relative number of these two kinds of questions. We expect the mode to be correct more often in groups with accurate enough rewards and base model generations. This is verified by our observation where Best-of-m for these questions.
Lastly, the right plot in Figure 6 shows the combined effect of the two changes and compares MoB with BoN in each group. MoB improves upon BoN the most questions where the reward and base models are good enough to make the mode correct, but are not good enough to achieve near perfect accuracy. Appendix C, we study the success probability MoB and BoN in a synthetic setup with N and make similar observations.

---

Experiments
We conducted series of experiments compare the performance of our proposed method against other well-known and reward models. The datasets include MATH500 (Lightman et al.. 2023), GSM8K (Cobbe et al., 2021b), MMLU-Pro (Wang et al., 2024b) questions in math (MMLU-Pro-Math) and chemistry (MMLU-Pro-Cheed and CA (Talmor et al., 2018). We have experimented with three different generative models from different families and different sizes: Swven..5-3B-Insee
approaches across a range of datasets, generative models,
(Qwen Team, 2024), Llama-3.1 1.1ma-3.1-8B-.. 15.1-8B-Instrus (Grattafiori et al., 2024), and 1emmma-2-9B-. (Team al., 2024). For reward models, we used two widely adopted ORMs: ArmoRM (Wang et al., 2024a) and GRM (Yang et al., 2024), with 8B and 3B parameters, respectively. These choices result in thirty diverse experimental setups that rigorously evaluate our method's ' performance.
Figure 7 presents the accuracy of different methods GSM8K and MMLU-Pro-Chem across varying values of N. Our method consistently outperforms the baselines, showing clear improvements even smaller N values. Table presents the accuracy and its standard error for MoB with adaptive m and m vN alongside SC, BoN, and WBoN for N 128 across all benchmarks, using Qwen and GRM models. Algorithms with statistically insignificant difference to the best algorithm according to a paired one-sided t-test (p-value 0.05) are also shown in bold. In Table we report the accuracy on MATH500 for all base and reward model combinations. This table also includes a row showing the performance improvement outperforms BoN in every setting. These results show the potential of MoB as strong replacement of BoN in tasks with discrete final answers. Complete results for all thirty experiment configurations are provided in Appendix E.2.
our method over BoN. As shown in both tables, MoB consistently
Table 1: Results for Qwen2.5-3B and GRM as base and reward models (N = 128).
MATH500 MMLU-Pro-Math
MMLU-Pro-Chen
GSM8K
CSQA
BoN
63.95+1.07
1.06
19.00=#112
80.95+0.88
77.70++0.3
SC
66.40+
1..60+1106
52.50+1.12
80.40++0.89
76.20+0..5
WBoN
67. 1.04
64.35.11.07
53.1011.12
81.25100.7
54.90.11.11
MoB-Ade MoB-Adaptive (Ours)
69.95.11.03
6..30.11.03
56.4511.111
82.85.10.84
77.4011..4
MoB-Poly (Ours)
69.45:11.03
70.15:11.02
56.30.1..11
83.10.10.84
77.45:10.93
Moo over BoN
6.00
3.20:10.9
7.45
1.9010.51
-0.3010.52
Table 2: Results on MATH500 across all base and reward models (N = 128).
ArmoRM
GRM
L1ama3.1-8B
Gemma2-9B
Qwen2,5-3B
Llama3.1-8B
Gemma2-9B
Qwen2.5-3B
BoN
51.55++1.12
52.20+1112
60.60+11009
56.65+1.11
54.95+11111
63.95++1.07
SC
60.65
52.90=11112
6..60=1.06
60.65=1.09
52.90=1.12
66.40+11.0
WBoN
62.90:::108
53.85=+1.11
67. 1.005
63.55=1.08
16.15=1.11
6..45++1.05
MoB-Adaptive (Ours)
62.90::1.08
56.15=:1.11
68.50=1.04
64.30=1.07
57.45=1.11
69.95+1.03
MoB-Poly (Ours)
62.40::1.08
57.05=:1.11
6..85=+1004
64.00=1.07
58.10=1.10
69.45:1003
MMoB over BoN
11.35-00.86
3.95+:068
7.90+00.78
7.65-+0.80
2.50+0.64
6.00=0.78
7 Conclusion and Future Work
In this paper we highlighted that with imperfect rewards, BoN's chosen answer can be highly stochastic and fail to pick the correct answer reliably. To address this, we introduced Majority-of- the-Bests (MoB), which estimates BoN's output distribution via bootstrapping and chooses the most probable outcome. MoB achieves superior performance compared to other selection algorithms such as, BoN, Self-consistency. and Weighted BoN outperforming them in most of our 30 experimental setups. Our method is scalable, requires no hyperparameter tuning, and adds only negligible CPU computational overhead. MoB can serve as strong alternative to BoN and SC in problems with discrete final answers. Looking forward, we believe MoB's selection signal could enable early stopping in parallel LLM generation, or be applied more broadly in any framework that relies on sampling from an LLM. However, MoB is limited to settings where the task requires producing a final answer, and like sampling-basee methods, incurs higher inference costs compared to zero-shot approaches.
10

---

Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers who provided valuable feedback that led to significant im- provements to the paper. AMF acknowledges the funding from the Natural Sciences and En- gineering Research Council of Canada (NSERC) through the Discovery Grant program (2021- 03701).
References
K. B. Athreya and J. Fukuchi. Bootstrapping extremes of LLD.. random variables. In Proceedings of the Conference Extreme Value Theory and Applications, Volume 3. pages 23-30. National Institute of Standards and Technology (NIST), 1994.
Peter Bickel and Anat Sakov. On the choice of in the m out of bootstrap and confidence bounds for extrema. Statistica Sinica, pages 967-985, 2008. 8
Peter J. Bickel, Friedrich Götze, and Willem R. van Zwet. Resampling fewer than n observations: gains, losses, and remedies for losses. In Selected works of Willem van Zwet, pages 267-297. Springer, 2011. 7, 16
Leo Breiman.
Bagging predictors. Machine Learning, 24:123-140, 1996.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv2407.21777, 2024.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchir Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. 2021a. 18
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems, 2021. URL hmts::/arxxv. org/abs/21 htt//b//21101441110 14168, 9, 2021b. 10
DeepSeek-AL Deepseek-Ri R1: Incentivizing reasoning capability in LLMs via reinforcement learning, 2025.
Bradley Efron. Bootstrap methods: another look at the jackknife. In Breakthroughs in statistic:: Methodology and distribution, pages 569-593. Springer, 1992. 3
Bradley Efron and Robert J. Tibshirani. An introduction to the bootstrup. Chapman and Hall/CRC, 1994. 7,7
Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Alain Le Noac h. Haonan Li, Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika. Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. The language model evaluation harness, 07 2024. 19
Friedrich Götze and Alfredas Račkauskas. Adaptive choice of bootstrap sample sizes. Lecture Motoo-hoo Series, pages 286-309 2001.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinay Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, er al. The Ilama 3 herd of models. arXiv preprini arXiv:2407.21788. 2024. 10, 19
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305. 14992, 2023. 1

---

Dan Hendrycks. Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song. and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. 5, 18, 19
Yuki Ichihara, Yuu Jinnai, Tetsuro Morimura, Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Eiji Uchibe. Evaluation of best-of-n sampling strategies for language model alignment. Transactions on Machine Learning Research, 2025. 3
Yuu Jinnai, Tetsuro Morimura, Kaito Ariu, and Kenshi Abe. Regularized best-of-n sampling to mitigate reward hacking for language model alignment. In ICML. 2024 Workshop on Models of Human Feedback for Al Aligument, 2024. 3
Nathan Lambert, Valentina Pyatkin, Jacob Morrison, LJ Miranda, Bill Yuchen Lin, Khyathi Chandu, Nouha Dziri, Sachin Kumar, Tom Zick, Yejin Choi, Noah A. Smith, and Hannaneh Hajishirzi. Rewardbench: Evaluating reward models for language modeling, 2024. 18
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Vian-Guang Lou, and Weizhu Chen. Making large language models better reasoners with step-aware verifier. arXiv preprint arXiv:2206.02336, 2022. 1,3 3
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards. Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference Learning Representations, 2023, 1, 2, 3, 5, 10, 18
Chris Yuhao Liu, Liang Zeng, Yuzhen Xiao, Jujie He, Jiacai Liu, Chaojie Wang, Rui Yan, Wei Shen, Fuxiang Zhang, Jiacheng Xu, Yang Liu, and Yahui Zhou. Skywork-reward-v2. Scaling preference data curation via human-ai synergy. arXiv preprint arXiv:2507.01352 2025. 21
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36:46534-46599 2023. I
Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang. Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. arXiv preprint Xiiv:2501.11399 2025.
OpenAl. Introducing openai ol. https: h htwp/////////aa//////e//ee com/oo/. OpenAl Blog.
Qwen Team. Qwen2.5: party of foundation models, September 2024. URL https::////:
github.io/blog//eee qwwng//wweee....mmmm 5/. 4, 10
Erwan Scornet, Gérard Biau, and Jean- Sann-Phllippe Vert. Consistency of random forests. The Annals of Statistics, 13(4):1716-174) 2015. 6
Charlie Vietor Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time com- pute optimally can be more effective than scaling parameters for reasoning. In The Thirteenth International Conference on Learning Representations, 2025. 1
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsensega: A question answering challenge targeting commonsense knowledge. arXiv preprint arXiv:1811.009977, 2018. 10
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQA:: question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pages 4149-4158, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. 18
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based gemini research and technology. arXiv preprint arXiv:2403.08229 2024. 10
12

---

Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-an outcome-based feedback. arXiv preprint arXiv:2211. 142275, 2022. 3
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-22 272, 2020. 19
Haoxiang Wang, Wei Xiong, Tengyang Xie, Han Zhao, and Tong Zhang. Interpretable preferences via multi-objective reward modeling and mixture-of-experts In Conference on Empirical Methods in Natural Language Processing, 2024a. 4, 10
Xuezhi Wang, Jason Wei, Dale Schaurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. 22t.222033..1777 2022. 1,2
arXiv preprint
Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, et al. Mmlu-pro: A more robust and challenging multi- task language understanding benchmark. In The Thirty-eight Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2024b. 4, 5, 10, 18
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. of-thnoh- prompting elicits reasoning in large language models. Advances in Neural information processing systems, 35:24824-24873 2022. 1
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Scaling inference computa- tion: Compute-optimal inference for problem-solving with language models. The 4th Workshop on Mathematical Reasoning and Al at NeurlPS'24, 24, 2024.
Rui Yang, Ruomeng Ding, Yong Lin, Huan Zhang. and Tong Zhang. Regularizing hidden states enables learning generalizable reward model for llms. arXiv preprint arXiv:2406.102/6 2024. 10
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong. and Jie Tang. ReST-MCTS*:
LLM self-training via process reward guided tree search. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
13

---

List of Appendices
We provide brief description of the material in the appendix of the paper.
Appendix A provides theoretical results on the asymptotic behavior of BoN's output distri- bution and the proof for Theorem
Appendix provides a closed-form calculation of bootstrapped BoN's output distribution for more efficient calculations.
Appendix investigates the effect reward noise and base model on different algorithms in a synthetic setup.
Appendix D provides extra details for the experiments and implementations.
Appendix E provides additional experimental results.
A Theoretical Results
In this section, we provide the formal theoretical results and the proof of Theorem 1. To do so, we first need show the convergence of BoN's output distribution, which is done in Section A.1 and Theorem 2. We prove Theorem in Section A.2.
A.1 Asymptotic Behavior of BoN's Output Distribution
Theorem 2. For final answer such that (2) (0, 1). let Fo and F1 represent cumulative distri- bution functions (CDFs) of the conditional distributions P(r(Y))f(Y)) = 2) and P(r(()))()) # 2). respectively. Define Tn and iı be their right endpoints,
To - supfr R Fo(x) 13. x1 sup e R: Fz)) 13.
As N 20,
(i) if < x1, we have NN (2) + 0.
(ii) xo > xn, we have NN (z) - 1.
(iii) x = 21 x², Fu and Fi are continuous and strictly increasing, and for some c E [0, oo].
lim Fo(x) = #t2² - Fz
then we have
Trr((2)
(2
1 (c- 1) (2)
Proof. We first define random variables to better express (2). Assume use Fo and F1 to iid. Fi. For n 2 1, let 5 and S% be the generate i.i.d. samples Rº. RQ.... ~ Fo and R] R2.... maximum of the first n samples from Fo and F1, that is,
SO A max R. E
S) max R
i=
Also, for outputs Y,.... Yv. let 2, = S(Y), No be the number of outputs that reach the final
answer z, and N N No be the number outputs that do reach the final answer
We can express N (2) as
TN. (x) Σ
P
Best Best 2 z|Z1:N 21:N) P(Z = 21:N)
21:M
Σ FiNN
maxr(Y)) > maxr(Yi) ZI.N = 21:N) P(ZI.N = =2IN).
(2)
2==2
14

---

Now, note that due Yi..... YN being i..d., we have
P(r(Y))....., ZI.N 21:N) 11 P(r(Y)) 2:).
By definition of R.. and R,, we can therefore write (2) as
TN (2) CP(S S 1NNN =1.N) PP 21.N) = PSS S2r1).
For simplicity, we define S - Nu and 5 - No Now, we can express (T) as
nN(2) = P(5 > S*).
Note that S 4 Tn and S 4 21, which leads to the statement for cases (i) and (ii). We focus on case (iii). Let (a( - Fo(x)) and Pi (x) a Fi (ar) be the complementary CDFs of Fo and Fi, respectively. To quantify P(50) 8²), we note that Fi strictly decreasing in neighborhood of S" Thus,
lim TN(=)= = lim P(S > 8*) N
lim P(NR((5) < (S)))))). N-+00
N-x
Therefore, turn study the joint distribution of (NF (S as oc. This will be achieved by quantifying the distribution of (no to the distribution of (N (S"), (S")).
(15%) (5 ni Fi (S as no. + co and relating it
Since Fj continuous, Fi (IR)) U(0, 1] is uniformly distributed for any i. Define U, F1 (12))
U|0, 1]. It is well known that
71
min
U S Exp(1)
(n1 - x0),
which due to min, Fi = (S ) translates to
n1 (s,,) $ Exp(1)
(ni + 00).
Similarly, we can show that no Fo(S 4 Exp(1) as no + cc. However, our goal is to analyze
the distribution of no Fi (5 (p))) ). To do so, we use the tail-equivalence condition (1). We note that
s 4 xx, therefore, (o )/ Fi (S)))) 4 no
Together, we get
no Fo
4 Exp(11
no Fi = (S F
(no + 00).
(5)
c
Due to the independence of St and 5 we can combine (4) and (5) to get
(noPi (is)) FE
(no, n4 - 00),
where F, F lid Exp(1). As N xX, we have No, NI 2, co, therefore,
(N NO FI 4 (E/c,F)
(N + oo).
Finally, we the fact that No 4 (Te((z) and N $ 1 Tre((z) to get
(NFF(S"), NF No Fi N (S))))
$
E C (2))(2)) Tee((2)
F
(6)
No/N N//N
Combined with (3), we conclude that
lim (2) = -P( N
E (T)(T)
< 1 - Tee((2)
1 [T)(2) + CTT (2)
15

---

A.2 Proof of Theorem
We restate Theorem with the assumptions not included in the main text.
Theorem 3. Assume that there are finite possible values for Z and for every possible final answer 2, the conditions of Theorem 2 for one the cases hold. If as N oo, have m - de and m/N + then for any > O, the estimated Rm,N will converge to the true distribution Tm- That is,
lim [I =m 2 e) 0.
Proof. Since there are finite possible values for Z, it suffices to show the convergence in estimated probability of each possible final answer We show that for any 2, and >> O, we have
lim P((mm,N(=) Tm (=))) 2 N
0.
We use the result by Bickel et al. (2011, Equation 3.14) to show this claim. To do so, first frame our problem in their notation. For S i S N, let Z _ -(Y)) be (the one-hot encoding of) the final answer reached by Y, and R. _ rYy) be the numerical reward of Y,. We define
X; _ (Zz R₂).
We define the bootstrap statistic of X1, x1..... X
D 4
Tn [2 Best =2
Lms
where [[-] is the indicator function, D ~ Bernoulli(O.5) is independent Bernoulli random variable, and I'm defined to the distribution of Ti. Basically, Tm the indicator of being selected by BoN, plus small random noise to ensure the non-degeneracy condition as - co. We define the function (t) = l[[t > 0.5]. so that the parameter of interest 6m. becomes
On A (T((m) (2),,,
as intended. Lastly, one can verify that since Tm is invariant of repetitions and permutations of its inputs XI...., Xm in our case, have for any 0 < < 1,
6m(x)
T ||me (z) Tm (z)
We now show the conditions of Bickel et al. (2011, Theorem 2). First, we need to show that Lms the distribution of Tm, convergent. According to Theorem
have
lim (z) A (z) m=+00
for some Toa (2) E [0, 1). Therefore, as m + 0o, we have
Bernoull((055)
Lm $ (ernoulli(T=<s))) + 4
For condition Bickel et (2011, Equation 3.11) we need show that for any M oc, we have 6m xm -1/2) + 0
uniformly for all M. By definition, suffices to show that for any 0 < x < M, we have
TTT m--/// (2) Tm (2) + O.
This follows from the fact that nm convergent oo (z). For any > O, pick My such that for any mo 2 Mo, we have
Tmg (z) - Too (=)l < E
2"
and M, such that for any M, M MyM 2 Mo. Then for any 2 M1, we have
b Im mmm-amml (z) - (z) < e/2 and (m) - x (2) < e/2.
Together, we have
t [m-zym mm (2) T. (z) <E
and achieve the uniform convergence condition. Finally, note that our statistic Tn, is not dependent on the sampling distribution Peer and Bickel et al. (2011, Equation 3.13) is satisfied.
D
16

---

B Closed-Form Calculation of Bootstrapped BoN's Output Distribution
In Section 4.2, we proposed approximating x by running BoN on large number of subsets of size m sampled with replacement from the N generated outputs, In practice, / = 10, 000 is commonly considered sufficient. This calculation is negligible compared to the generation of outputs from the LLM and can be carried out on CPU. Nonetheless, we here show that it can also be done in (N log N).
Define R2 r(Y;) for sis N, and let i1, ,2,...,,y be such that
Ri, < Ri, .... Rix-
For simplicity, we assume no ties occur among the rewards. The key insight is that for any 1 1 & S N, the probability of Y, being selected randomly sampled subset of m outputs can be calculated in closed-form. We note that Yi, is selected if the subset only includes outputs among ......, Yie. but (and therefore contains Yi,). We get
not limited ...,..., Vi,
P(Y, is the output of BoN on a resampled subset) =
N
N
Thus, for any final answer 2, the probability of it being selected in a subset
k
m
k
m
n (2)
Σ
k:
This procedure only requires sorting the outputs according to their rewards and therefore has com- plexity O(N log N).
C Effect of Reward Noise and Base Model's Success Probability
SC
BoN
MoB
Roward (8)
2²-
Success Probabillty lit
0.8
21.
2
2-
0.2
0.4
0.6
0,8
1.0
0.2 0.4
0.6
0.8 1.0
0.2
0.4
0.6
0.8
1.0
Base Success Probability
Base Success Probability
Base Success Probability
Figure 8: Success probability of SC, BoN, and MoB with infinite budget (N = oo) for different values of the base model's success probability and reward noise.
In this section, we investigate the effect of the base model and reward noise on the success probability of SC, BoN, and MoB. We consider synthetic setup for TRUE/FALSE question, where the correct answer is TRUE, Let be the success probability of the base model, which is the probability that the base model generates solution reaching the correct final answer.
Assume pracle is an oracle reward model that always assigns the reward of to solutions that reach the correct answer, and 0 otherwise:
pracle (Y) = {1. if f(Y) = TRUE,
Lo. if f(Y) FALSE
To investigate the effect of an imperfect reward model, we consider noisy reward model noisy that is equal to the oracle reward plus an exponentially distributed noise:
moisy (Y)
uracle (Y) + Exp(1/9)
17

---

The parameter 3 controls the noise level, where larger 3 indicates noisier reward model. To see this, note that the expected value and the standard deviation of the noise are equal to If [ is large. the noise will dominate the signal from the oracle reward, and the noisy reward model will be less informative.
We visualize the success probability of SC, BoN, and MoB with infinite budget N = oc in Figure 8. SC's success probability, shown in the left plot of Figure 8. is independent of the reward noise. It is either equal to when p > 0.5 (the correct answer is the most probable answer), or equal to 0 otherwise. For BoN, consider two extreme cases for the reward noise. When the reward model is perfect (3 small), BoN's success probability is 1 regardless of the base model's 's success probability. This is shown in the bottom edge of the middle plot Figure 8. this case, BoN is preferable over SC. On the other hand, when the reward model is completely uninformative (3 large), BoN's 's success probability is equal to the base model's success probability. This shown in the top edge of the middle plot in Figure 8. MoB's success probability is equal to if BoN's success probability is at least 0.5, as shown in the right plot of Figure We see that MoB shows a similar behavior to SC when the reward model is uninformative, and when the reward model is perfect, MoB behaves like BoN.
In this setup, we can study the success probability of BoN and MoB with an infinite budget N = oo theoretically. BoN's success probability depends on the reward's ' noise level. It can be calculated from Theorem 2 as
e//pp
BoN success probability with infinite budget 1 1-p+eld ee1pp
Note that if the reward model is perfect (3 0), both the numerator and denominator go infinity, and we reach the success probability of 1. With 3 = oc, the noise becomes dominant, and BoN's success probability remains equal to the base model p even with infinite budget. Due to Theorem MoB solves the problem if the correct answer is BoN's most probable outcome. Therefore,
1, if 1-p+el/np > 0.5,
MoB success probability with infinite budget
0, otherwise.
This is favorable over BoN in scenarios where BoN still prefers the correct answer, as it can find the correct answer reliably without randomness.
D Implementation and Experiment Details
In this section, we provide more details on how the experiments in the paper are conducted.
D.I Evaluation Experiments
Benchmarks. We run our experiments five popular benchmarks. MATH500, first introduced by Lightman et al. (2023), is a randomly sampled subset of 500 math questions with short final answers from the MATH dataset (Hendrycks al., 2021). We the math and chemistry questions from the MMLU-Pro benchmark (Wang et al., 2024b), which includes multiplc-choice questions on a variety of topics. We also run our experiments on GSM8K (Cobbe al., 202 that contains grade school math questions in short final answer format. Lastly, we use the CommonsenseQA benchmark (Talmor al., 2019) that tests the model's commonsense reasoning through multiple-choice questions. For all benchmarks, we randomly select 500 questions for our experiments.
Base and Reward Models. We have used the models Qwen/Qwen2 5- Instruct. google/gemma- (eremm---9b--ae 2- and meta- Pasta-llama/LLaaa-33 1-8B-Instruc. from Huggingface as base generative models. Our reward models are RLHFlow/ MitmoooM-Lama3-813 according to Rewardbench (Lambert al., 2024) in reasoning tasks.
2-------raaat rewB-rrawdddddeee-ee and 1, which are the best performing 3B and 8B reward models
Implementation Details.
In the implementation of MoB, we always use the closed-fome calculation of #,,N discussed in Appendix B to efficiently perform the bootstrap estimate. Therefore, in the actual implementation, there is parameter B and we effectively operate as if B oo was chosen.
18

---

We use Huggingface's Python library for all the output generations. The generation was carried on H100 GPUs. The compute cost was not tracked, but we estimate thousand GPU-hours. We always use temperature for inference and no extra modification of the next-token sampling procedure. The final answer extraction and evaluation are calculated using the Language Model Evaluation Harness (Gao et al., 2024). For each question, we generate 512 outputs and for each budget size N,, we run each algorithm [512/N] times. Reported standard errors for the accuracies are calculated with the assumption of normal errors and from the standard deviation of 500 x [ independent runs of the algorithm (500 is the dataset size across all benchmarks). The numbers reported the improvement of MoB over BoN are based on the adaptive MoB, and its standard error calculated from the standard deviation of paired differences of the algorithms score in 500 X 512/N] runs. We use the Scipy library (Virtanen et al., 2020) in python conduct one-sided paired t-test to decide statistical significance of the difference between the best performing algorithm with another algorithm in tables. Algorithms with insignificant (p-value 0.05) difference also shown in bold.
on the order of a few
For GSM8K, use 5-shot prompt. For MATH and MMLU-Pro questions, of-touhh prompting used the official Llama3. models evaluation (Grattafiori al., 2024) on MATH (Hendrycks et al., 2021). This prompt and the prompt used for CommonsenseQA are given the following.
the zero-shot
Prompt for MATH and MMLU-Pro
Solve the following <topic> problem efficiently and clearly:
For simple problems (2 steps or fewer) Provide a concise solution with minimal explanation.
For complex problems (3 steps or more): Use this step-by-step format: ## Step 1: [Concise description] [Brief explanation and calculations] ## Step 2: [Concise description] [Brief explanation and calculations]
Regardless of the approach, always conclude with: Therefore, the final answer is: \boxed(answerrj. hope it is correct.
Where [answer] is just the final number or expression that solves the problem.
Problem: <problem from dataset>
Prompt for CommonsenseeA
Use commonsense to solve the following multiple choice question. First explain your solution and then give the final answer. Always finish your answer with "the answer is (X)" where X is the correct letter choice. Question:: <problem from dataset>
D.2 Details of Other Experiments
In Figure 2, we discussed the success probability of BoN, which requires an estimate of BoN's output distribution. We use the same technique in MoB estimate this output distribution. To minimize the error of this approximation, we specifically generate 1,400 outputs for the math problems in MMLU-Pro with Qwen2.5-3B Then, we use N1,000 as defined in Section 4.2 as estimate for nN. Same technique is used in Figure where the mode of N is chosen as the output of oracle where the distribution estimation error is calculated with respect to fm.1400
MoB, and Figure instead of the true T...
In Figure 5, consider seven fixed schedules for m, specifically 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8. At any budget N, we compared the accuracy of MoB with adap- tive against the highest accuracy among the seven instantiations of fixed schedule MoB.
No for
In Figure 6, for each question, we measure base model's success probability and reward model's accuracy using 512 outputs. We ignore questions with all-correct or all-incorrect outputs, since the
19

---

reward accuracy is not defined for them, as well as questions with reward accuracy bellow 0.25 due all algorithms having zero success probability on them. Also, m is calculated adaptively for each question.
Additional Experimental Results
In this section, we provide additional experimental results for all 30 setups.
E.1 Adaptive Subset Size Selection
In Section 4, we compared MoB with adaptive choice of m and m VN with the optimal choice of m. We provide this comparison in MATH500 (Figure 9). MMLU-Pro-We Chem (Figure I 1), GSM8K (Figure 12). and CommonsenseQA (Figure 13). In Table 3, we compare the performance of MoB with adaptive q for various values of q on all benchmarks Llama3.1 1-BB base model and ArmoRM reward model. As also observed in the literature, we observe that the choice of q is not sensitive one.
(Figure 10), MMLU-Pro
Table 3: Performance of MoB with adaptive across different choices of q for Llama3. 1-BB base model and ArmoRM reward model.
q
0.40
0.50
0.60
0.70
0.80
0.90
MATH500
61.85%
63.00%
63.15%
62.20%
62.45%
60.70%
MMLU-PP MMMLU-Pro-Mail Pro-Math
66.60%
66.85%
66.75%
66.60%
67.10%
66.35%
MMLUU-ProChie
56.75%
57.40%
57.85%
57.15%
56.95%
56.35%
GSM8k
91.60%
91.55%
91.55%
91.85%
91.80%
91.85%
CSQA
77.45%
77.40%
77.30%
77.25%
77.35%
77.30%
Qwen2.5-38
Liama3.1-88
Gemma2-98
0.700
0.650
0.58
0.825
0.56
0.600
Accursyy (h))
ArmoRt
0.625
0.22
0.600
0.50
0.575
0.500
MDB Ooparal ml
Net 10pommal mi
Ned Optmmal
0.475
0.46
Mell jn- -7i
(R)
Maal (n- -R)
0,500
0.450
0.48
100
129
0.70
0.56
Accuracy 1%6)
0.65
0.60
0.50
0.55
Holl Oppamaal
Nol rOppimal
Mall Opptinal
Mob (Adago
Nod rAdaptine
0.46
Ned (daapov
MoB (mm S51
Hed (R)
Med Inw (8)
Doh
0.46
2oh
20
40
60
80
100
120
20 40
60
80
100
120
20
40
60
80
100
120
Number of Generations (N)
Number of Generations (N)
Number of Generations (N)
Figure 9: Comparison MoB with adaptive m and m = v v against MoB with optimal m on MATH500 dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-3B (Left), Llama3. 1-8B (Middle), and Gemma2-9B (Right) base models. Shaded areas show standard error.
E.2 Evaluation Experiments
We compare MoB with adaptive and m VN with baselines in MATH500 (Figure 14, Table 4), MMI.U-Po-Maad (Figure 15, Table 5), MMI.U-Pro-Chem (Figure 16, Table 6), GSM8K (Figure 17, Table 7), and CommonsenseQA (Figure 18, Table 8).
20

---

Qwen2.5-2
Liama3.1-80
Gerna22 9B
0.700
0.625
0.852
ArmoRM
Accuracy (8)
0.650
0.575
0.925
0.500
0.550
0.600
0.575
0.775
0.590
0.500
0:525
Moll ridiptho)
0.475
0.925
0.700
0.70
0.675
Accurscy (N)
0.65
0.050
0.925
0.60
0.525
0.600
0.500
2.55
Mes ingrival ni
0.475
0.500
Holl Jn -7
Med (R)
(n
0.50
40
129
Number Generations (N)
Number Generations (M)
Number Generations (N)
Figure 10: Comparison of MoB with adaptive and VN against MoB with optimal on the MMLU-Pro- Pro-Math dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-33 (Left), Llama3.1 1-8B (Middle), and Gemma2-9B (Right) base models. Shaded areas show standard emro.
Qwen2.5 5-3B
Llama3. 3-880
Gemma2
0.60
0.60
0.55
0.55
Accursiy (8)
0.50
ArmoRM
0.50
0.65
0.45
0.60
ridaptive)
0.60
Mall (Adaprive)
0.35
Sch
80
0.55
Accursol (16
0.55
0.500
GRM
0.50
0.475
0.45
0.45
rostina
0.40
0.000
0.375
20
40
40
60
Number Generations (N)
Number Generations (M)
Number Generations (N)
Figure 11: Comparison of MoB with adaptive and VN against MoB with optimal on the MMLU-Pro-Chee dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-33 (Left), Llama3.1 1-8B (Middle), and Gemma2-99 (Right) base models. Shaded areas show standard error.
E.3 Results on Skywork-v2 Reward Model
Additionally, we report the results for wwtwworr//kkwokk--ao -aaaadd-----a------- 3-1-8B (Liu et al., 2025), more recent reward model in Tables 9-13.
21

---

Qwen2.5-38
Liamn3.11
Germa22 9B
0.92
0.93
Accuraiy (N)
0.52
0.8
ArmORM
3.06
0.1
0.78
0.82
Holl vidiptio))
0.79
0.78
BoV
0.70
0.54
0.52
Acurssy (N6
HoB Copamal
Hed rOpsimal mi
0.79
Red Copaimal (Alarron
jateprest
Hedeptinn
HoB Jmm S7
Red (W)
Mad Oni (R)
0.28
20
40
20
80
100
120
60 80
100
129
60
100 120
Number Generations (N)
Number Generations (M)
Number Generations (N)
Figure 12: Comparison of MoB with adaptive and V against MoB with optimal the GSM8K dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-3B (Left), Llama3.1 (Middle), and Gemma2-9B (Right) base models. Shaded areas show standard error.
Qwen2.5-3B
Jlama3.1-8B
Gemma2-93
0.79
0.78
0.61
ArmoRM
Accurser (%)
0.78
0.77
0.60
0.76
0.79
0.75
0.78
10ctira
rostimal
(Optiraln
Midiptivel
0.77
0.72
0.73
0.76
0.82
0.79
0.63
Acarasy (5)
0.78
GRM
0.76
(Dolima res snclptive
Med rOstimaln mn Nod (Adagtive)
Med :0ptemalnn Red Dadlprives
0.74
0.77
Nes ies +B)
Mat (mi +R)
0.73
0.76
20
120 Number of Generations (N)
40
50
120
0
20
40 60
B0
100
120
0
20
40
60
BD
100
120
Number of Generations (N)
Number of Generations (N)
Figure 13: Comparison MoB with adaptive m and m VN against MoB with optimal m on the Commonsense(A dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-3B (Middle), and Gemma2-9H (Right) base models. Shaded areas show standard error.
Table 4: Results on MATH500 across all base and reward models (N 128).
ArmoRM
GRM
Llama3.1
Gemma2-9B
Qwen2.5-3B
Llama3.1-8P
Gemma2-9B
Qwen2.5-3B
BoN
51.55-1.12
52.20
60.60=1.0
56.65
54.95a1.1
63.95=1m7
SC
60.65-1.w
52.90+1.2
66.40+108
60.65
52.90
66.40=10s
WBoN
62.90-14R
53.85
67.10=105
63.55
56.15st.1
67.45=1.8
MoB-Adaptive (Ours)
62.90-148
56.15
68.50 :1.04
:0.m
57.45
69.95-1mt
MoB-Poly (Ours)
62.40
57.05
67.85
64.00 1.7
58.10-1.0
69.45
MoB over BoN
11.35-0.5
3.95
7.90+
7.65-n8n
2.50Ho..4
6.00-m7k
22

---

Table 5: Results MMLU-Pro-Marn across all base and reward models (N 128).
ArmoRM
GRM
Llama3.1-88
Gemma2-9B
Qwen2.5-3B
Llama3.1 1-8B
Gemma2-9B
Qwen2.5-3B
BoN
-1
60.45a11.
65.95
64. 10
16.11
66, 60.10
SC
62.95 08
19.95
65.60
62.95
49.95s1.12
65.60:10s
WBoN
66,45
52.25
66.70 2100
60.05
56.45
64.35
MoB-Adaptive (Ours)
66.70
61.55:1..9
69.80 :1.03
69.05
59.35
69.30
MoB-Poly (Ours)
67.20
62.05:1.09
70.05
69.30
59.45
70.15
MooB over BoN
5.30
1.10aa7
3.85
4.95=0a:
3,20
3.20
Table 6: Results MMLU-Pro-Chem across all base and reward models (N 128).
ArmoRM
GRM
Llama3.
Gemma2-9B
Qwen2.5-3B
Llama3.1-88
Gemma2-9B
Qwen2.5-3B
BoN
49.70-1.x
56.60s1.1
48.05
53.05
49.25
49.00=112
SC
50,25-1112
43.40
52,50at12
50.25
43.40
52.50
WBoN
57.65-1.10
45.45
53.30e112
49.75
57.25
53. 10
MoB-Adap MoB-Adaptive (Ours)
57.40
58.00 38.05
54.75
60.75
54.60
56,45-111
MoB-Poly (Ours)
57.80-1.0
58.80
54.90
60.00
55.00
56.30
MoB over BoN
7.70.092
1.45
6.70ao92
7.70
5.35
7.45-094
Table 7: Results on GSM8K across all base and reward models (N = 128).
ArmoRM
GRM
Llama3.1-B8 1-BB
Gemma2-9B
Qwen2.5-3B
1.lama311- 1-8B
Gemma2-9B
Qwen2.5-3B
BoN
89.00-a70
84.20
83.85
87.15sar
81.20 :087
80.95
SC
88. 1.:2
80.55
80.40:0.9
88. 1.5
80.55
80.40:a.9
WBoN
888.7
80.75
81,10 :0:10.
77.75
a0:45
81.25
MoB-Adaptive (Ours)
91.75-naz
83.30+aaa
83.85 -n.82
90.50-auss
81.15:057
82,85-0x4
MoB-Poly (Ours)
91.80=0a1
83.15aam
83.80 .0.2
90.05
80.85 i0.8
83.10
MooB over BoN
2.75
-0.90
a.00
3.35
-0.05
1.90
Table 8: Results CSQA across all base and reward models (N 128).
ArmoRM
GRM
Llama3.
Gemma2-9B
Qwen2.5-3B
JJama3.1--82
Gemma2-9B
Qwen2.5-3B
BoN
77.80=a33
81.20
80.15
78005
80.55
77.70=
SC
75.75
79.25+091
76.20+aa5
75.75
79.25
76.20
WBoN
76.75=094
80.05
76. 26.60=aa5
36.
49.80st11
54.90=1.1
MoB-Adaptive (Ours)
77.40-n94
81.20 euxn
79.40 ...0
78.45
81.45 in87
77.40
MoB-Poly (Ours)
77.30-n94
81.45
19.15
78.65
81.15 =087
77.45
MoB over BoN
-0.40-047
0.00+n4r
-0.75
0.40-n.44
0.90+e.s
-0.30
23

---

Qwen2.5.33
Liama3.1.44
Gemma2
0.790
0.675
0.625
0.50
0.650
0.603
0.54
ArrORR
Accurszy (6)
0.575
0.600
0.300
0.575
0.525
0.50
2.48
0.30
R3
0.525
100
120
100
100
Accurscy 195)
0.54
0.50
0.50
0.55
0.99
0.48
0.50
Wieo
MAdestinx
0.45
Wioe
Medapline
0.44
(Ataptied
100
120
120
120
Number of Generations (N)
Number Generations (N)
Number Generations (N)
Figure 14: Comparison of MoB with the baselines on the MATH500 dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-3B (Left), Llama3.1-8B (Middle), and Gemma2-9B (Right) base models. Shaded areas show standard error.
Qwen2.5-38
Llama3.1-80
Gemma2 98
0.700
0.675
0.625
0.050
ArmoRM
Accurssy (8)
0.650
0.523
0.575
0.625
0.500
0.600
0.575
0.575
Ban
0.525
B3R
0.475
Ecl
0.52
HEB
H&ll
Vell (Adapthr))
100
120
100
100
0.70
0.675
0.65
0.550
Acairacy
0,625
2.60
0.525
0.600
0.500
2.55
0.475
0.50
3.50
60
100
120
Number Generations (N)
Number Generations (N)
Number Generations (N)
Figure 15: Comparison of MoB with the baselines on the MMLU-Pro-Math dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-3B (Left). Llama3.1 1-8B (Middle), and Gemma2- 9B (Right) base models. Shaded areas show standard error.
24

---

Qwen2.5-38
Llama3.1.4
Gomma2 98
0.60
0.55
Accuracy (%)
0.50
ArTOORM
0.59
0.50
0.45
0.45
0.60
Fell
0.40
0.35
80
100
0.55
0.80
0.55
Accurscy (36)
0.55
GRM
0.50
0.50
0.45
0.45
0.45
0.40
Woun
22
Induptiol
(Adustiri
(Ataptiee
20
40
20
40
60
100
120
Number of Generations (N)
Number Generations (N)
Number Generations (N)
Figure 16: Comparison of MoB with the baselines on the MMLU-Pro-Chen dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-3B (Left), Llama3, (Middle), and Gemma2- 9B (Right) base models. Shaded areas show standard error.
Qwen2.5-31
Llama3.1
Gemma2
0.85
0.90
Accurasy (%)
0.52
0.83
ArMoRM
0.88
0.81
0.78
B2N
0.82
BCM
0.80
Ecl
0.79
0.78
(Adapttae)
0.78
Vell (Adaztiv))
60
100
0.84
0.52
Acarrscy (96)
0.95
Haus
0.89
Mrill (Adaptiv))
0.79
0.80
0.78
0.76
detantind
20
40
40
BD
Number of Generations (N)
Number Generations (N)
Number Generations (N)
Figure 17: Comparison of MoB with the baselines on the GSMSK dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-3B (Left), Llama3.1-88 (Middle), and Gemma2-9B (Right) base models. Shaded areas show standard error.
25

---

Qwen2.5-3B
Jlama31--8B
Gemma2-88
0.79
0.82
0.81
ArmoRM
Rocuracy (56)
0.78
0.77
0.80
0.76
0.79
0.75
0.75
0.74
0.77
0.75
0.8
0.80
0.7
0.73
Accuracy (8)
0.70
GRM
Bo4
Ze1
EoN
0.65
0.65
iiduption
(Adaptiri
Ved (Adaptind
0.60
0.00
0.50
0.55
0.4
1000
120
20
40
50
60
100
120
20
40
60
80
100
120
Number of Generations (N4
Number of Generations (N)
Number of Ganerations (N)
Figure 18: Comparison of MoB with the baselines on the Commonsense(QA dataset with ArmoRM (Up) and GRM (Down) reward models, and Qwen2.5-3B (Left), Llama3. 1--BB (Middle), and Gemma2- 9B (Right) base models. Shaded areas show standard error.
Table 9; Results MATH500 with Skywork reward model across all base models (N 128).
Skywork
Llama3.1-8)
Gemma2-9B
Qwen2.5-3B
BoN
54.50=
55.85++0.79
63.35
SC
60.65=1.09
52.90:11.12
66.40:1.006
WBoN
6..05
57.95.11.10
68.8011.04
MoB-Adaptive (Ours)
63.95-11077
19.45
69.70++1.03
MoB-Poly (Ours)
63.65=1.08
19.15
70.35:+102
MoBB over BoN
9.45++0.1
3.60++0.2
6.35++0.78
Table 10: Results MMLu-Pro-Math with Skywork reward model across all base models (.V 128).
Skywork
Llama3.1-8P
Gemma2-9B
Qwen2.5-3B
BoN
60. 10.077
54.20=10.79
67.80-10.74
SC
62.95
49.95.11.12
6..60.1.06
WBoN
69.45
60.00
69.80
MoB-Adaptive (Ours)
1..00=1.06
19.10
72.55+1100
MoB-Poly (Ours)
6.070=1105
59.10=11.10
72.85
MoB BoN
5.90+10.75
4.90+0.88
4.75++0.75
26

---

Table 11: Results on MMLU-Pro-CHIE with Skywork reward model across all base models (NV 128).
Skywork
Llama3. 1-8B
Gemma2-9B
Qwen2.5-3B
BoN
5..2
53.20
57.70
SC
10.60=
13.10
52.50+1.12
WBoN
1.18
58.60
58.65
MoB-Adaptive (Ours)
60.87
17.75
61.50-11.09
MoB-Poly (Ours)
60.92=1.14
57.40=1.111
61.55++1.09
MoB over BoN
3.64:10.79
4.55++0.98
3.80++0.82
Table 12: Results on GSM8K with Skywork reward model across all base models (N 128).
Skywork
Llama3. 1-BB
Gemma2-9B
Qwen2.5-3B
BoN
85.15
80.98:1062
82.37=1.05
SC
18.0020.7
80.53++089
1.58
WBoN
88.25=0.72
10.1090..89
82.07=1.50
MoB-Adaptive (Ours)
89.55=0.68
81.23:10.87
84.04
MoB-Poly (Ours)
89.85-0068
81.23
83.89++1443
MoB over BoN
4.40.10.1
0.25.
1,67-10.82
Table 13: Results on CSQA with Skywork reward model across all base models (N = 128).
Skywork
Llama3.1-8B
Gemma2-9B
Qwen2.5-3B
BoN
77.00
80.15
78.85.10.65
SC
75.95
79.25
76.20-10.95
WBoN
76.45-t0.95
80.20+10.89
76.15+00.95
MoB-Adaptive (Ours)
77.90
81.00
77.0011.94
MoB-Poly (Ours)
78.00 0.93
81.00
77.25
MoB over BoN
0.80+10.3
0.85+10.41
-1.85-10.49
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The results supporting the claims are reported in the Method and Experiments
section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Mentioned the limitations in the Conclusions and Future Work section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
To the best of our knowledge, all theorems are correct, and every mathematical citation properly used.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All the implementation details and the choice of model//dataasetbennhhmakk provided in the main text and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
29

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: All of the data that have used is already public. We will publish the code upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm Phbllc//guieesCodeeeeee
wwwssssssslllll.oo onPolicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /ttppp.ccpppiiiiiememt wwtppccpppc///cccc.ccccccccccclt htalli///uideess http//uide/e//eee https//oooSSSumissiseeee wwaibbmmsssioPPP ssionPoiccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our model has only one hyperparameter which is automatically tuned by our method. The generative models and datasets are all well-known and widely used in the community.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provided confidence intervals in our tables and figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
30

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, we will provide as many quantifiable and trackable information as possible to address these questions.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https:/
Answer: [Yes]
Justification: Yes we have followed the guidelines mentioned on the website during the course of the project.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our method general technique for improving inference generative models. The societal impacts depend heavily on the specific use cases and deployment contexts of these models. Therefore, a detailed discussion of societal impacts falls outside the scope of this work.
31

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymemt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [Yes]
Justification: We are not releasing any new dataset or scraped datasets. Every model and dataset used in this paper is already open-souree sonreouure and public.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [No]
Justification: We have provided proper citation for every model/dataset that we have used. The reader find the licensing of those assets in those references, but have not mentioned those licenses in our manuscript.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
32

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcodeccooee.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
The code of our method will be public. We are not releasing any new asset (e.g. model/dataset) except our method's code.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
33

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in our research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy (https: : Ccmps//ccooeeeeeeee/222222 /LLM) for what should or should not be described.
34


Reviews:
[{"review_id": "vPndOtzA2g", "reviewer": "Reviewer_ufGg", "summary": "The paper proposes \"Majority of the Bests (MoB)\" a simple method to improve best-of-n sampling with LLMs using  bootstrapping. The proposed method works by sampling multiple times from generated LLM outputs, selecting the highest rewarded output, followed by selecting the majority answer from the filtered outputs. The paper provides both theoretical and experimental support for superiority of their method. When evaluated on multiple datasets, 3 generator models and 2 different reward models, the method outperforms both BoN and weighted BoN.", "questions": "Please See the Weaknesses Above.\n\nAdditionally:\n1. The results in Table 1, Row: WBoN and Column: CSQA are abnormally low. Is there a typo?\n2. I particularly like the Figure 6 showcasing how Accuracy varies with number of generations. Form graph it seems, the performance difference is particularly higher for smaller N. Could authors provide results for other setups, and plot performance difference as a function of N? The analysis might further strengthen the paper.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths:\n1. The paper proposes a simple method to improve the performance of LLMs, while showcasing strong results across a broad range of datasets and models.\n2. The method can act as a replacement for the widely used Weighted Best-of-N method across the domains tested.\n3. The paper is well-presented and easy to follow.\n\n---\n\n## Weaknesses\n1. The MoB method works based on the assumption that reward model outputs are noisy. While generally true, the paper does not compare against the latest strong reward models. If the authors could show results with them (e.g., by choosing the strongest reward model from RewardBench on respective domains), the effectiveness of MoB could be further strengthened.\n2. In the text and tables, the authors continuously emphasize comparison with BoN instead of WBoN (e.g., the improvement row in Table 2). Further, the authors claim \"MoB is a drop-in replacement for BoN\". However, this framing is arguably unfair, since evaluations are a.) only done on tasks with a discrete output space and b.) majority is calculated over final answers and not full outputs.\n3.  There is limited analysis in the paper. For instance, the authors could add what are some failure modes of the method, on which questions the methods fail, how scaling RM size changes the performance, or the effects of hyperparameters. The complete results for the stated \"30 setups\" are also not presented.\n4. The paper claims the method requires no hyperparameter tuning; however, both variables q and B have to be chosen, and an analysis studying their effects is missing.\n5. Scaling the number of model outputs is one dimension, while scaling the number of outputs from generative reward models (which are often used) is another. Comparing the effect, and how MoB can be used with generative reward models, would be an interesting study. \n6. The paper claims the method is computationally efficient. However, it may still require significant CPU resources because of the large value of B (10,000), which might increase latency and cost in real-world usage. Results showing actual wall time and CPU usage are missing.\n7.  The paper lacks a dedicated Related Work section. While a minor issue, omitting one makes it harder to understand the work's novelty.\n---\n\nOverall, the proposed method is promising with some exciting results. However, a more thorough analysis is needed to further validate the claims.", "was_revised": true, "final_justification": "The authors have addressed my concerns thoroughly, and overall, the contribution of the paper is valuable. However, at the same time, the results are not consistently better than WoB (eg, with SkyWork RM), highlighting that the proposed method may not be a universal replacement.", "rebuttal": "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.\n\n**(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.\n\n|      |  Llama3.1-8b-instruct  |  Gemma2-9b-it  |  Qwen2.5-3b-instruct  |\n|:----:|:----------------------:|:--------------:|:---------------------:|\n| BoN  |         54.50%         |     55.85%     |        63.35%         |\n|  SC  |         60.65%         |     52.90%     |        66.40%         |\n| WBoN |         65.05%         |     57.95%     |        68.80%         |\n| MoB  |         63.95%         |     59.45%     |        69.70%         |\n\nWe 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. \n\n**(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. \nAs a brief comparison with WBoN, MoB has a higher accuracy in 27 out of 30 setups (ignoring confidence intervals). \n\n**(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.\n\n**(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$.\n\n\n|      $q$      |  $0.40$  |  $0.50$  |  $0.60$  |  $0.70$  |  $0.80$  |  $0.90$  |\n|:-------------:|:--------:|:--------:|:--------:|:--------:|:--------:|:--------:|\n|    MATH500    |  61.85%  |  63.00%  |  63.15%  |  62.20%  |  62.45%  |  60.70%  |\n| MMLU-Pro-Math |  66.60%  |  66.85%  |  66.75%  |  66.60%  |  67.10%  |  66.35%  |\n| MMLU-Pro-Chem |  56.75%  |  57.40%  |  57.85%  |  57.15%  |  56.95%  |  56.35%  |\n|     GSM8k     |  91.60%  |  91.55%  |  91.55%  |  91.85%  |  91.80%  |  91.85%  |\n|     CSQA      |  77.45%  |  77.40%  |  77.30%  |  77.25%  |  77.35%  |  77.30%  |\n\n\n**(W5)**\n 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.\n\n**(W6)**\nWe 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. \n\n**(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.\n\n**(Q2)** Absolutely. The plots for all setups are provided in the supplementary material (Figures 13-17)."}, {"review_id": "41sMcHIZ7O", "reviewer": "Reviewer_kwjQ", "summary": "The paper proposes **Majority-of-the-Bests (MoB)**, a hyper-parameter-free alternative to Best-of-N (BoN) sampling for inference-time reasoning with LLMs.\n\n- **Motivation.** BoN’s success probability can saturate well below 1 with imperfect rewards. If the correct answer is the most probable output of BoN, we are likely to fix the errors of BoN by doing majority voting over BoN results.\n\n- **Key idea.** After sampling *N* candidate traces and scoring them with a reward model, MoB repeatedly bootstraps *m*-sized subsets (with replacement), keeps only the best-of-m trace in each subset, and select the mode of these “best” traces.\n\n- **Theory.**  The authors proves that:\n  - An *m-out-of-N* bootstrap consistently estimates BoN’s output distribution. That is, MoB converges to its oracle version on large N.\n  - Their algorithm of adaptively select nearly optimal m with theoretical gaurantee under certain situation. Empirical results also show that adaptive m performance closely follows the optimal m variant.\n- **Experiments.**  On five benchmarks, three open-weight LLMs and two reward models, MoB outperforms BoN, Self-Consistency and Weighted BoN in **25 / 30** settings; at $N = 128$ it raises accuracy by largely over BoN.\n- **Practicality.**  The method adds only marginal CPU overhead; the computational-heavy sampling part remains unchanged.", "questions": "1. **When does MoB underperform BoN?** The appendix hints that very hard questions (base success rate <1%) may favor larger m or even plain BoN since the correct answer may no longer be the most probable one for BoN under small m. Could you add a difficulty-conditioned analysis and a practical decision rule?\n2. **Larger / proprietary models.** Can you report at least a subset of results on proprietary LLMs and larger open-weight LLMs like GPT-4o, Gemini 2.5, and Qwen3-30B-A3B, perhaps on fewer datasets, to further demonstrate scalability and generalizability?\n3. **Comparing with SC.** Given that MoB shares the same limitation of not supporting open-ended generation with SC, could you also add SC as an additional baseline and report MoB improvements over SC?\n\n**Rating swing.** Demonstrating (1) a principled failure-mode analysis and (2) results on at least one >10B or proprietary model with consistent results would increase my overall score by 1 point (to 5: Accept).", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- Solid theoretical analysis and a proof of bootstrap consistency; extensive evaluation across 30 settings; results reported with confidence intervals.\n- Motivation is intuitive; algorithm and adaptive-*m* procedure are clearly described with helpful figures.\n- MoB can serve as a drop-in replacement of BoN with marginal overhead, offering systematic gains without tuning.\n\n**Weaknesses**\n\n- Models stop at 9B parameters and open-weight models; no ablation on bootstrap budget *B*.\n- A few typos remain; discussion of failure cases is brief and buried in the appendix.\n- Share the same limited use cases as SC. Open-ended generation (summaries, codegen) is not supported, unlike BoN.\n- Relies on combining previous methods (bootstrap, majority voting, BoN); originality is limited.", "was_revised": true, "final_justification": "The authors addressed my primary concern about failure modes and provided additional experimental results on proprietary models. As such, I revised my score upward.", "rebuttal": "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. \n\n**(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. \n\n|      |      Accuracy         |\n|:----:|:----------------------:|\n| BoN  |         69.4%         |\n|  SC  |         72.0%         |\n| WBoN |         72.2%         |\n| MoB  |         74.0%         |\n\nThis 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.\n\n\n**(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.\n\n**(W2 and Q1)** \nWe 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:\n\n1. 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$). \n\n2. 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.\n\nIn 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.\n\n**(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."}, {"review_id": "dfxTTMTNRZ", "reviewer": "Reviewer_ZoLM", "summary": "This paper proposes Majority-of-the-Bests, a method to improve Best-of-N decoding for LLMs by using bootstrapping to estimate the distribution of BoN outputs and selecting the most frequent outcome. By aggregating rewards over resampled subsets, MoB aims to mitigate errors from noisy reward models and shows consistent empirical gains across multiple benchmarks.", "questions": "- How do you define the Oracle final answer distribution? I am not sure how one can access the true pi_N.", "limitations": "There does not seem to be a separate limitations section or a societal impact section. Please add them.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- Conceptually simple methodology\n- Consistent experimental results on a wide range of settings\n\n# Weaknesses\n- The paper frames BoN’s randomness as a problem to be mitigated. But if reward scores are noisy and correctness is inherently uncertain, is forcing the \"mode\" always desirable? Sometimes randomness can reflect epistemic uncertainty, not just noise.\n- Bootstrapping is a statistical resampling technique that works well when the sample size is large and the statistic of interest is smooth and not too sensitive to outliers. However, this work applies bootstrapping to a relatively small sample set and attempts to approximate the extreme statistic: the maximum reward. So I am a bit suspicious about the validity and soundness of applying the bootstrapping technique.\n- In Figure 2, I am curious why the authors assigned differently-sized bins for the histogram. To claim that \"BoN has a significant chance of returning the correct answer but fails to do so reliably\", a more fine-grained histogram is needed to demonstrate the skewness of the success probability distribution.\n- The BoN itself is a computationally heavy algorithm that is not often used in practice. Although authors disclose that the CPU computation overhead is marginal, I suspect MoB will take longer to compute overall. It would be helpful to have a full comparison of computation time (latency) among methods: Best-of-1, BoN, MoB, and BoN+SC.", "was_revised": true, "final_justification": "I went through the other reviewers' questions and responses, and most of my concerns have been resolved and had a chance to have better understanding of the approach.\nI now think the paper holds promise, and will adjust my scores accordingly.", "rebuttal": "We thank the reviewer for their review with multiple insightful points. Here are some thoughts and clarifications.\n\n**(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.\n\n**(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.\n\n**(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.\n\n**(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.\n\n**(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."}, {"review_id": "TwwREIM2IK", "reviewer": "Reviewer_DAFe", "summary": "A popular trend in inference-time scaling of LLMs involves sampling many responses, and using some strategy to aggregate their answers to produce a single final answer.  This work is motivated by the shortcomings of common approaches like Best-of-N (BoN) and self-consistency (SC), proposing to improve on BoN by applying a bootstrap approach to debiasing the choice of the noisy reward model.  Theoretical and empirical evidence is provided to support the approach, with experiments showcasing applications in Math, Chemistry and QA.", "questions": "Please see weaknesses section.", "limitations": "The authors address limitations in one sentence in the conclusion.  More discussion (and demonstration) of the algorithm’s limitations would be welcomed.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\nThis paper offers a solution to a high-priority problem for the LLM community: broadly, what is the best way to scale inference-time compute, and in particular, how should we combine solutions from many samples.  As opposed to the many heuristic approaches that have been taken to this problem, the bootstrapping method proposed here is underpinned by rigorous theory. Also, the compute cost compares favorably with other methods.\n\nIn terms of the paper presentation, the method description (and accompanying empirical demonstrations) offer solid support for the proposed algorithm.\n\n## Weaknesses\n\nWhile I appreciate the simplicity and motivation of the MoB algorithm, I find the experimental evaluation to have significant weaknesses that prevent the reader from gaining a thorough impression of when and why this algorithm might be helpful.\n\nFirst, it is not clear why certain experiment details are chosen.  For example, why is evaluation done on this selection of 3 math, 1 chemistry, and 1 QA tasks?  Are these domains where you expect the method to be particularly useful, or that are helpful to reveal the strengths and weaknesses of the algorithm?  Also, does it make sense to use these two reward models for all of these tasks?  One could imagine that different reward models might be chosen for different tasks, e.g., math or QA.  Also, these do not seem to be the strongest available reward models of their size (according to rewardbench).  Finally, why do some experiments use few-shot prompting, and some use zero-shot CoT?  \n\nNext, related to the last question, it seems that baseline implementations may not match the approach suggested in the original work.  For Wang 2022, I believe that SC is always meant to be combined with chain of thought (as opposed to few-shot prompting).  Similarly, for WBoN with Li 2022 as a reference, I believe the original method involves some diverse prompting and (crucially) step-level labeling, which do not seem to be applied here.\n\nFinally, and potentially my biggest concern with the experiments, is that the presentation of results seems aimed at boosting the perceived performance of MoB.  For example, I am quite confused by how items are bolded or not in tables.  Across the 5 tables, I found 9 examples of unbolded results that have overlapping CIs with the best result.  Accordingly, I am further confused by the claim in the conclusion that MoB outperforms all baselines in 25 of 30 settings.  This does not reflect the results in the tables.\n\nOverall, I feel that the experiment section can benefit from more focus on “when” and “why?” questions about the algorithm’s performance, as opposed to focusing purely on outperforming baselines.  Given that the algorithm is not technically deep, the weaknesses of the experimental results outweigh the strengths of the paper in my opinion.\n\nAlso, ideally code would be included.", "was_revised": true, "final_justification": "The authors did a great job in their rebuttal of addressing the various \"why\" questions that I had about the experiments.  As such, I revised my score upward to a weak accept.", "rebuttal": "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.\n\n# When does MoB succeed/fail?\nThe change from BoN to MoB can be split into two **steps**:\n\n1. **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.\n\n2. **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.\n\nTogether, 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.\n\n* BaseSProb = Chance of a generation being correct.\n* RewardAcc = Fraction of correct-incorrect output pairs correctly judged by the reward model. \n\nThese 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.\n\n## Impact of the change from Best-of-$N$ to Best-of-$m$ (Step 1)\nConsider 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.\n\n|**Reward Acc \\ Base S Prob**|$0.00-0.25$|$0.25-0.50$|$0.50-0.75$|$0.75-1.00$|\n|:-:|-:|-:|-:|-:|\n|  $0.75-1.00$ |  20 |  13 | 8 | 0 |\n|  $0.50-0.75$ | 5 | 5 |  -0 | 0 |\n|  $0.25-0.50$ |  -2 | -22 | -14 | -32 |\n\nThe 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.**\n\n## Impact of the change from Best-of-$m$ to MoB (Step 2)\nWe can categorize questions into three categories:\n\n* 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.\n* 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.\n* Type C: Questions where $ \\pi_m(Z^*) > 0.9 $ or $ \\pi_m(Z^*) < 0.1$ . Sampling and picking the mode are similar.\n\nThe 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.\n\n|  **Reward Acc \\ BaseSProb**  |  $0.00-0.25$  |  $0.25-0.50$  | $0.50-0.75$  | $0.75-1.00$  |\n|:-:|:-:|:-:|:-:|:-:|\n| $0.75-1.00$  | $ \\textcolor{blue}{A: 33}, \\textcolor{red}{B: 33} $ | $ \\textcolor{blue}{\\textbf{A: 13}}, \\textcolor{red}{B: 0} $ | $ \\textcolor{blue}{\\textbf{A: 5}}, \\textcolor{red}{B: 2} $ | $ \\textcolor{blue}{\\textbf{A: 1}}, \\textcolor{red}{B: 0} $ |\n| $0.50-0.75$  | $ \\textcolor{blue}{A: 4}, \\textcolor{red}{\\textbf{B: 13}} $ | $ \\textcolor{blue}{\\textbf{A: 14}}, \\textcolor{red}{B: 7} $ | $ \\textcolor{blue}{\\textbf{A: 8}}, \\textcolor{red}{B: 0} $ | $ \\textcolor{blue}{\\textbf{A: 4}}, \\textcolor{red}{B: 0} $ |\n| $0.25-0.50$  | - | $ \\textcolor{blue}{A: 1}, \\textcolor{red}{\\textbf{B: 2}} $  | $ \\textcolor{blue}{A: 1}, \\textcolor{red}{B: 1} $  | $ \\textcolor{blue}{A: 0}, \\textcolor{red}{\\textbf{B: 1}} $ |\n\n**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.**\n\n## Comparing MoB and BoN under various generation and reward accuracies\nThe relative performance of MoB to BoN depends on the combination of the impacts of the two steps. The following table gives the final accuracies.\n\n|  **Reward Acc \\ Base S Prob** |$0.00-0.25$|$0.25-0.50$ |  $0.50-0.75$ |  $0.75-1.00$ |\n|:-:|:-:|:-:|:-:|:-:|\n|  $0.75-1.00$ | $ \\textcolor{blue}{MoB: 38}, \\textcolor{red}{\\textbf{BoN: 45}} $ | $ \\textcolor{blue}{\\textbf{MoB: 97}}, \\textcolor{red}{BoN: 83} $ | $ \\textcolor{blue}{\\textbf{MoB: 99}}, \\textcolor{red}{BoN: 95} $ |  $ \\textcolor{blue}{MoB: 100}, \\textcolor{red}{BoN: 100} $ |\n|  $0.50-0.75$ | $ \\textcolor{blue}{MoB: 8}, \\textcolor{red}{\\textbf{BoN: 18}} $  | $ \\textcolor{blue}{\\textbf{MoB: 68}}, \\textcolor{red}{BoN: 53} $ | $ \\textcolor{blue}{\\textbf{MoB: 94}}, \\textcolor{red}{BoN: 72} $ | $ \\textcolor{blue}{\\textbf{MoB: 98}}, \\textcolor{red}{BoN: 92} $ |\n|  $0.25-0.50$ | -  |  $ \\textcolor{blue}{MoB: 6}, \\textcolor{red}{BoN: 6} $ | $ \\textcolor{blue}{MoB: 33}, \\textcolor{red}{BoN: 33} $  | $ \\textcolor{blue}{\\textbf{MoB: 50}}, \\textcolor{red}{BoN: 25} $ |\n\nIn 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.\n\n## Comparison of 30 setups\n\nNow 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. \n\n# Clarifications\n\n**(W1 and W2)** Demonstrating the capabilities of a general-purpose test-time scaling method is inherently challenging, as it involves\nchoices across numerous dimensions—generative models, reward models, and benchmarks. We aimed\nfor as comprehensive an evaluation as feasible by selecting generative models from diverse families and\nbenchmarks spanning multiple subjects. From the RewardBench leaderboard, we intentionally selected\nstrong, uncontaminated reward models, particularly those performing well on reasoning tasks. This\ncombination of models and benchmarks resulted in 30 distinct experimental settings, which, in our\nview and compared to prior work, represents a broad and meaningful coverage of the space—though\nwe acknowledge that alternative selections could certainly be made.\n\nOur choice of benchmarks was guided by two considerations: (1) a focus on tasks with discrete final\nanswers, enabling the majority voting mechanism integral to MoB, and (2) coverage of domains where\nreasoning 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-\nReward-V2-Llama-3.1-8B—and these results are consistent with the overall findings we present. We\nplan to expand these updates in the paper by including results for the rest of the benchmarks and\ngenerative models using this reward model. \n\n**(W3)** Regarding the use of few-shot prompting versus CoT, we aimed to\nfollow the common practice for each baseline setting. Our primary focus was to keep variation factors\nconsistent when comparing MoB with other baselines, ensuring that differences in results reflect the\nmethods themselves rather than inconsistencies in setup. The use of few-shot prompts for GSM8K\nwas, in fact, unintentional—we relied on the default configurations in LM Evaluation Harness for that\nexperiment. We will clarify this in the paper and ensure alignment with the implementations and\nintentions 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. \n\n**(W4)**\nWe 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."}]

Author rebuttal:

Meta-review: This paper introduces a simple method to improve the Best-of-N (BoN) inference strategy by leveraging bootstrapping to find the most frequent answer. The approach is well-motivated by the problem of noisy reward models and is supported by both theoretical consistency guarantees and experiments across numerous benchmarks and models, where it consistently outperforms established baselines. The reviewers engaged in a thorough discussion, and the authors provided a detailed rebuttal, including an analysis of the method's performance under different conditions and additional experiments with stronger reward models and proprietary LLMs. The consensus is that the paper presents a valuable and well-validated contribution to improving inference-time computation for LLMs.
Decision: Accept (poster)