Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling
Authors: Qiwei Di
Kaixuan Ji
Xuheng Li
Heyang Zhao
Quanquan Gu
Venue: ICLR 2026 Poster (2026)
Keywords: Inference-time scaling
Pass@k
Primary area: learning theory

Abstract: LLM inference often generates a batch of candidates for a prompt and selects one via strategies like majority voting or Best-of-
N (BoN). For difficult tasks, this single-shot selection often underperforms. Consequently, evaluations commonly report Pass@$k$: the agent may submit up to $k$ responses, and only the best of them is used when computing regret. Motivated by this, we study inference scaling in the more general Pass@$k$ inference setting, and prove that neither majority voting nor BoN exhibits the desirable scaling with $k$ and the sampling budget $N$. Combining the advantages of majority voting and BoN, we propose a new inference strategy called Best-of-Majority (BoM), with a pivotal step that restricts the candidates to the responses with high frequency in the $N$ samples before selecting the top-$k$ rewards. We prove that when the sampling budget is $N=\tilde\Omega(C^\*)$, the regret of BoM is $O(\epsilon_{\mathrm{opt}}+\sqrt{\epsilon_{\mathrm{RM}}^2C^\*/k})$, where $C^*$ is the coverage coefficient, $\epsilon_{\mathrm{RM}}$ is the estimation error of the reward model, and $\epsilon_{\mathrm{opt}}$ is the estimation error of reward at the optimal response. We further establish a matching lower bound, certifying that our algorithm is minimax optimal. Beyond optimality, BoM has a key advantage: unlike majority voting and BoN, its performance does not degrade when increasing $N$. Experimental results of inference on math problems show BoM outperforming both majority voting and BoN.

Published as a conference paper at ICLR 2026
BEST-OF-MAJORITY: HINIMAX-OPTIMI STRATEGY FOR PASS @k INFERENCE SCALING
Qiwei Di', Kaixuan Ji", Xuheng Li", Heyang Zhao, Quanquan Gu
Department of Computer Science
University of California, Los Angeles
CA 90095, USA {giwei2000, kaixuanji, xuheng, 1i, hyzhao, qgu) ucla edu
ABSTRACT
LLM inference often generates batch of candidates for a prompt and selects one via strategies like majority voting Best-of-N (BoN). For difficult tasks, this single-shot selection often underperforms. Consequently, evaluations commonly report Pass k: the agent may submit up to k responses, and only the best of them is used when computing regret. Motivated by this, we study inference scaling in the more general Pass@ k inference setting, and prove that neither majority voting nor BoN exhibits the desirable scaling with & and the sampling budget N. Com- bining the advantages of majority voting and BoN, we propose new inference strategy called Best-of- Best-of-Maoority (BoM), with a pivotal step that restricts the can- didates the responses with high frequency in the N samples before selecting the top-k rewards. We prove that when the sampling budget N = I(C*), the regret of BoM is O(Eopt + VettMtC/k)) where C* is the coverage coefficient, ERM is the estimation error of the reward model, and capt. is the estimation error of reward at the optimal response. We further establish matching lower bound, certifying that our algorithm is minimax optimal. Beyond optimality, BoM has a key ad advantage: unlike majority voting and BoN, its performance does not degrade when increasing N. Experimental results of inference on math problems show BoM outperforming both majority voting and BoN.
INTRODUCTION
Scaling law serves powerful tool for guiding the training of large language models (LLMs), providing insight into how increased training compute, data, and model size contribute to perfor- mance improvements. Originating in the early days of deep neural networks (Hestness al. 2017
Rosenfeld et al.. 2019), the concept has since demonstrated remarkable predictive power across variety of domains, including strategic board games (Jones) 2021). image generation (Henighan
ctt al. 2020 Yu et al. [022 Peebles & Xie 2023). video modeling (Brooks et al., 2024). language al. 2022 Achiam
generation Kaplan et al. a 2220) et al. 2024 Cai et al.) (025), and reward modeling (Gao et al. 2023 Rafailov et al., 2024). While training- ttmee scaling has proven effective, it also highly resource- resource-intnnsvve. As result, increas- ing attention has been directed toward complementary paradigm: inference, which examines how model performance can be improved after training. This relationship between additional compute at inference time and performance improvement is known as the inference scaling law (Brown et al. 2024| (nell et al.) 2024: Wu et al. [024b] Guo et al.) (2025).
2023), retrieal systems (Fagg
Compared to training-time scaling, inference scaling allows for increasing computational cost in several distinct ways, including expanding the generation input via chain-of of-innof-thouuht prompting (Wei
et al., 2222 Li et al. (2024), incorporating iterative self aal--improveeett, (Zheng et al. 2023 Wu et al.
2024a), and applying search-based algorithms (Yao al. 2023 Feng et al. 2023 Gao al.) 2024 Zhang et al. 2024). It can also be realized through repeated sampling, using strategies such as majority voting (Wang et al. 2022] Lewkowyez al.) 2022 Li et al., (023) or Best-of-N (BoN) (Lightman et al. 2023). In parallel, growing line of works has sought to establish theoretical guarantees for inference strategies. WWu et al. (2024b) provided convergence bounds and rates for the scaling of majority voting algorithms. |Huang et al. (2024) showed that BoN can achieve self- improvement via a special mechanism called sharpening.
Huang et al. (2025a) analyzed the sample
"qqual contribution

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of @ass@k inference strategies. Our algorithm BoM is the first minimax- optimal @ass@k k inference strategy. Compared with majority voting and BoN, BoM is scaling- monotonic, indicating that the optimal performance can be achieved with large sampling budget N, making it preferable when scaling up N to achieve better performance. Additionally, the term ( RR /*/k) in the regret of BoM scales optimally with k. while majority voting suffers from constant regret. BoN lacks the regret upper bound in the Pass @ k inference problem. Optimal k-scaling
Algorithm
Worst-case regret
Scaling-monotoe
12(1)
Majority voting
No
No
(Theorem
(minn V R v/K})
Best-of-N
No
Unknown
(Theorem 4.2
(Kopp + VC
R. C* /k)
Best-of-Maoority (Ours)
Yes
Yes
(Theorem 5.1)
(e + V CTaCC* /k:
Lower Bound
(Theorem 6.1
complexity of BoN and proposed a pessimistic inference algorithm with provable benefits. Chen
al.] (2025a) bridged test-time computation with theoretical analysis of transformers in the setting of in-context learning of linear regression.
While most existing analyses focus on inference algorithms that output a single response, there are tasks that allow for multiple candidate outputs, where it is considered solved if any one of them is correct. This setting is captured by the Pass@k metric (Li et al., 2022). Building on this metric, we propose a novel Pass @ k inference framework, in which the inference algorithm is allowed to generate N responses and return up to l of them. Since N k. the performance depends not only on generating a diverse set of candidates but also on the algorithm's 's ability to effectively select the k outputs that are most likely to be correct. [Brwnn al. (2024) conducted empirical studies on this inference framework and observed the relationship between the coverage and the performance of the algorithm. However, this work is restricted to the majority voting and BoN inference strategies, and failed to theoretically justify the inference scaling law.
As there have been few works understanding the scaling of the Pass@ k inference problem, are motivated to investigate the following fundamental question:
Q1: What is the optimal scaling of the Pass k inference problem?
To answer this question, we derive minimax lower bound as function of i that characterizes the fundamental limits of any @ inference strategy, establishing the theoretical scaling behavior for Pass inference problems.
Going one step further, also aim to evaluate existing inference strategies for the Pass k in- ference problem and find a strategy that achieves the optimal scaling. Beyond standard metrics like regret and sample complexity, we further introduce formal definition of scaling- cadding-moottoiicity (Huang et al. 2025a), which captures whether an inference algorithm maintains (or improves) its performance as the number of samples N increases. This leads our second question:
Q2: What inference strategies are scaling-monotoen Unfortunately, our analysis reveals that majority voting and BoN are not scaling- scaling-monotonic, Fur- thermore, these methods face fundamental limitations that make it difficult, if not impossible, to attain the optimal regret scaling with respect to k. To address this issue, we propose new infer- ence strategy, -fst-of-Majority (BoM), which integrates the core ideas of both majority voting and BoN. We establish regret upper bound for BoM that matches the minimax lower bound, thereby demonstrating that our algorithm is minimax optimal. Please refer to Table for detailed results. We summarize our main contributions as follows:
and optimal in the Pass@ inference setting?
Inference scaling laws for @ass@k. We show that the minimax lower bound of the regret is N(Copt + Viten C* /*/k) for any Pass k inference strategy, where copt is the error of the reward model at the optimal response, <RM is the expected error of the reward model, and C is the coverage of the reference LLM.
Optimal algorithm for Pass kt We propose a new Pass & inference strategy called Best-of- Majority (BoM). At the core of BoM is a step similar to majority voting that restricts the candidates
2

---

Published as a conference paper at ICLR 2026
to the responses with high frequencies in the generated samples, before selecting responses with top-k rewards. We prove that the regret of BoM is OEEogt C /k) with sample complexity N = @(C*), thus matching the minimax lower bound without increasing the computation over- head. With a formal definition of scaling monotonicity, show that BoM is scaling monotonic, while majority voting and BoN are not.
Experiments. We compare our algorithm BoM against majority voting and BoN. Our results empirically demonstrate the superiority of BoM against majority voting and BoN and verify the scaling monotonic properties of three algorithms, which corroborates our theoretical results.
Notations. We use [M] to denote the set of integers 21. M). We use [[:] to denote the indicator function. We use 8.j to denote the Kronecker delta, i.e., d.y = 1 if j. and 8,3 = 0 otherwise. We use y. Yi to denote the elements in the set of response D. V. Ys to denote the generated responses, and V. V/ to denote the final outputs. We use standard asymptotic notations O(-), s(()) and (()), and use O(+), ((.) and (-)) further hide the logarithmic factors.
2 RELATED WORK
Inference-time scaling. Compared to training- time scaling laws, the study of inference- scaling laws has emerged much more recently. [Sardana et al. (2024) extended the Chinchilla scaling law (Hoffmann et al. 2022) to incorporate inference costs. Wu al. (2024b) conducted a systematic study of inference scaling laws, analyzing a range of inference strategies including greedy search, majority voting, best-of-N. weighted voting, and two variants of tree-based search algorithms. Con- currently, [Snell et al. (2024) analyzed the inference scaling problem by searching against process- based verifier reward models. In contrast, [roon et al. (2024) explored repeated sampling as a sim- ple scaling method to improve performance. [hen et al. (2024) studied the performance of majority voting and a variant that incorporates a filtering mechanism. They observed that as the number of generated samples N increases, performance initially improves but eventually declines. They also proposed a predictive scaling model to characterize the performance trend. Muennighoff et al.) (2025) developed simple methods to construct a samplc-efficient test-time scaling dataset. More- over, Huang et al. (2025b) studied the sample complexity and representation ability of test-time scaling with transformers.
Inference strategies. One of the most straightforward inference strategies is best-of-N, NN, which has been widely adopted in the inference of language models (Stiennon et al.) 22020) Nakano al. [221] Touvron et al., [2023] Gao et al. 2023). For its theoretical guarantees, Yang et al. (2024a) established connection between the asymptotic behavior of BoN and KL-constrained reinforcement learning quantities. Beirami et al. (2024) provided a tighter upper bound for the KL divergence between the BoN policy and the ref- erence policy. [Mrouhh (2024) proved guarantees for BoN algorithm from a information theoretic view. HHang et al. (2025a) further provided guarantees on performance when the estimated reward model and true reward are mismatched. |Aminian et al. (2025) extended the analysis to smoothed variant of BoN called SBoN. They proved that BoN can suffer from reward overoptimization, and SBoN can serve as mitigation. Another common inference strategy is majority voting (Lekkowyc7) cct al. 2022] Wang et al., 2022 Li et al. 2023). Wu et al.] (2024b) established convergence bounds and rates characterizing how the performance of majority voting algorithms scales with the number of samples. Other inference strategies include variants of BoN (Jinnai et al. 2024 Qiu et al.)
methods, characterizing this relationship through information-thhorrel
2024)
rejection sampling (Liu et al.
2023 Xu et al.] 2024), and search-based algorithms (Yao et al.
2023
Feng et al. [023]] Gao et al.]
2024 Zhang et al. (204)..
Pass @ k alignment. To the best of our knowledge, the theoretical Pass inference framework is
novel and remains unexplored in the existing literature. Moreover, aligning the training process with different inference algorithms has also emerged as promising direction (Balashankar et al. (024). In this direction, Pass & has also been proved useful the training of large language models. TTng et al. (2025) demonstrated that training language models using Pass @ k-based objective can lead to improved overall model performance. More recently, Chen et al. (205b used Pass @ le as the reward to train the language model and observe improvements on its exploration ability. Liang et al. (2025) proposed training methods to mitigate entropy collapse, which in turn lead to improved performance on the Pass @ k metric.
Chhent
3

---

Published as a conference paper at ICLR 2026
3 PASS @ INFERENCE SCALING PROBLEM
Let A' be the set of prompts and y the set of responses. We represent an LLM as a conditional policy
T- z)) that maps each prompt 2 E X' to a distribution over V We have access to reference policy Tet which, for instance, can be trained using the supervised finetuning (SFT) method. For each pair (I,y) E X' V, we assume the existence of ground-truth reward model r" X x y [0. 1}, which evaluates the quality of response y given prompt xr
During inference time, we can use the reference policy Tef to generate multiple responses. To evaluate the quality of these responses, we utilize imperfect reward model F X' x y [0. 1]. which provides approximate assessments of response quality. For a given prompt v, we make the following assumptions regarding the accuracy of the reward model.
Assumption 3.1 (Reward Estimation Error). The expected squared error between r" and f is upper bounded by 2 (M)))), i.e,
By (a) (1, (2, F(x, (F)z)))( (M))).
This assumption is the standard squared loss of the reward model, with respect to the reference policy Tet. The same assumption has been made in prior work like (uuag et al. (2025a). We further assume that the optimal answer is unique, which is natural condition in many domains where the correctness of the final solution is verifiable, such as in mathematical problems.
Assumption 3.2. There exists a unique y" = argmaxyey r" (z, y), with r" (e)y") = 1. Moreover, the estimated reward at y" is close to optimal, satisfying
| (2. v²) F(x, v²)) = (a)(
Combining Assumption 3.1 with Assumption 3.2 we directly know Feeryy < (2p((x S cixa(()
In practice, an accurate reward model is crucial for the post-training and inference of large language models. A common approach is to align the model with human preference data through supervised
learning or reinforcement learning from human feedback (RLHF) (Ouyang et al., 2022, Casper al., 2023 Zhu al. 2024] Yang et al., (002bb. Since the training of the reward model extensively studied and is not the focus of this work, we directly assume access to a pre-training reward model that satisfies Assumptions and a 3.2
In this work, we study a novel setting called the @ inference scaling problem. Different from the settings where the model is allowed generate and submit & candidate responses, goal is to maximize the highest ground-truth reward of the k samples. Specifically, for a given prompt x, the model is allowed generate up N candidate responses and select subset yı, 3/,...;> : y/ for submission. Increasing N improves the likelihood of obtaining high-quality outputs, but also incurs greater computational cost, a trade-off between accuracy and efficiency. We consider the following regret metric:
Regret(z) (z) = B,, [r (xx,)) Ey .Va.....
max fr (x)(), ISisk
(3.1)
where π¹ = == is the maximizer r".
In tasks with a unique correct answer, such as mathematical problem solving, the ground-truth re- ward model y* functions as a binary verifier, returning values in 1). In this case, the regret (3.1) naturally aligns with the Pass @ & metric (Li et al. 2022), since minimizing (3.1] is equivalent to maximizing the probability that at least one the selected responses correct.
Remark 3.3. Compared with the sample-and-evaluat framework (Huang et al. 2025a), our frame- work goes one step further by explicitly characterizing the dependence on k. This dependence con- stitutes a novel focus of our analysis, as it has not been examined in prior works on inference-time algorithms (Huang et al. 2024 2025a Verdun et al. 2025).
In the setting of test-time (inference) scaling, responses are generated by Tee-- Sampling from a good reference model can lead to performance improvement. Motivated by this, we need metric to evaluate the performance of the reference model. Following Huang et al. (2025a), we introduce the reference policy's -cooeerae coefficient follows:
C (x) == Ey-r (-lx) (2/z)) m(rl)/)))
(3.2)
4

---

Published as a conference paper at ICLR 2026
Moreover, the uniform coverage coefficient is defined
C (z) == sup a ((lm)//maa((l))
(3.3)
Since Assumption 3.2 ensures that the optimal policy क² is deterministic and uniquely defined as x (1(yxx) = 1 y. the L1 and uniform coverage coefficients coincide. Consequently, we have (²(z)= (z) 1/mrr/yy
Besides the regret, we are also concerned with the following important property of the algorithm, named as caaling-monotonicct (Huang et al. 2025a). We provide the formal definition follows:
Definition 3.4. Assume that k. prompt æ and the coverage coefficient C' (*)) are fixed. An algorithm is scaling-monotone if for any 8 > O, there exists eD > 0 and No E N+ such that for any N 2 No and any instance that satisfies Assumption 3.1 with CRM (x) S co. the regret satisfies
Regret(a:) S 8.
Intuitively, sealing-monoteen algorithm should achieve arbitrarily small regret if the reward model F is accurate and sufficiently many samples of responses from Tel are observed. Furthermore, scaling monotonicity also guarantees that the performance of the algorithm does degrade when increasing N. Therefore, it is crucial property in practice because the sampling budget N can be easily scaled up in hard instances instead of requiring accurate tuning. While this concept is not completely new, as far as we know, we are the first to formally define this property.
SUBOPTIMALITY OF EXISTING INFERENCE STRATEGIES
In this section, we first introduce two commonly used strategies for LLM inference, namely (weighted) majority voting (Section 4.1) and Best-of-V (BoN, Section 4.2). We will show that neither strategy is scaling-monotonte by constructing hard instances where the inference strategies suffer from constant regret even when + oc. Additionally, the Pass@ & inference problem is less stringent than Pass 1, since it only requires success in any of the k sampled attempts rather than a single one. Consequently, the regret is expected to decrease as increases, suggesting a negative association between regret and the sampling budget kt
4.1 (WEIGHTED) MAJORITY VOTING
Majority voting is simple semble method for LLM inference: Multiple responses to the same prompt are sampled using the ref- erence policy ( to make the responses diverse enough, and the answer occurring most often is se- lected as the final output.
Algorithm 1 (Weighted) Majority Voting
Require: Reference policy Tiefs sampling budget N, number of candidates k. (estimated reward model f, weight func- tion w(-)).
1: Observe context
2: Independently generate N responses
D
=
(ūr 72. ... DN from (e)((-1)))
3: 1 S then
Specifically, let ÚI..... UN denote the generated responses for a given query. After calculating the frequency of each response R(y)= = N + ( = y). the final pre- diction is then chosen as the answer that appears most frequently among these samples, i.e..
4: return D.
5: else
6: Calculate frequency of each response E D: f(y)
1 =y.
7:
if weighted then
8:
Query reward labels (F(z. Tn Dt)...,, F(.. TN))
9: Select "I....,
. = Top-k (y E u(((l)) a(1)).
10:
else
V1. Tx Top-k 5 #.)))
11: Select Vi..... Tt = Top-k
12: end if
Majority voting has demonstrated strong empirical
13: return ( 7.
performance Lewkowyez
14: end if
Wang et 2022
et al. 2022 Li et al. 2023). With reliable reward model F, it can be further enhanced by
weighting candidate frequencies with reward scores. Using an increasing weighting function w(.).
the selection rule becomes:
V1 ....... Dh Top-kfy E 5 w (f(v)) #(0)).
5

---

Published as a conference paper at ICLR 2026
While the reward weighting introduces extra computation for reward evaluation, weighted majority voting has been shown to achieve better performance than the unweighted version (Wu et al. 2024b).
Despite its empirical success, we show that (weighted) majority voting is suboptimal in the worst case, even when the exact reward function is available, i.e., Tex (x) = 0.
Theorem 4.1. For the (weighted) majority voting Algorithm [ with weight function w(-), assume
that C (x) 2 1 + 2kzr(1) / (/(l/w((12))))) Then, there exists an instance I = (X, V, "r";,,, r² Tref,
such that the coverage coefficient is (xx), and F = r* satisfies Assumptions 3.1 and 3.2 with
<RM (x) = Capt (x)) = 0. N 2 9C*(x) log(2k + 2), the algorithm suffers from a constant regret:
Regret(x) = 211)
Majority voting relies on exploiting the reference model's distribution. Consequently, the hard case can be constructed by designing multiple distinct "bad" answers, each receiving higher probabil- ity under Ree than the probability of the optimal answer (e Theorem 4.1 demonstrates that increasing the sampling budget N or the number of submitted responses & does not guarantee con- sistent improvement for (weighted) majority voting. In fact, when N is sufficiently large, (weighted) majority voting incurs constant regret even if the reward model is accurate.
4.2 BEST-OF-N
Algorithm Best-of-NV (BoN)
Best-of-N is another effective I.LM in- ference strategy. Instead of aggregating answers by frequency, the model gener- ates multiple candidate responses for the same query and then selects the single best response according to reward model f. Formally, given N sampled responses LN. the Best-of-N strategy selects the outputs that maximize the reward signal i.e.
Require: Estimated reward model f, reference pol- icy Tref sampling budget N, number of candi- dates k.
Observe context rr
2: Independently generate N responses 5 =
(ūn, v2......................... UN } from (er(-|r))
3: Query reward labels (f(z, v.)........ F(x,, ,,,)..,,,,,,,,,, UN).
4: if 5 < k then
5: return D.
6: else
91 y1...., U2 Top- Topp- 5: :(()).
7: Select VT..... th
For the BoN algorithm, we have the follow-
8: return (
ing theorem on the lower bound of the regret.
9:
end if
Theorem 4.2. For BoN (Algorithm D. assume that (x) > 2k. Then, there exists instance (X v, n r", Tee, ?) such that the coverage coefficient is (*(x), and (F, satisfies Assump- tions 3.1 and 3.2 with (2) and Cope If S C* Cxxx), Algorithm 2 suffer from constant regret,
i.e.
Regret(r) = -(1)
Otherwise, the regret satisfies
Regret(x)) = 22 min {I, V ((R
BoN leverages the reward model's signal, but this makes it vulnerable reward overoptimization (ao et al. 2023; Stroebl et al., (024) when the reward model is inaccurate. Thus, we construct the hard case by introducing multiple distinct "bad" answers that are assigned higher estimated rewards.
With a carefully chosen, problem-dependent sampling budget N Ô (z)). the lower bound will become δ / ( which aligns with the general lower bound for inference algorithms (as will be discussed in Section o. However, this lower bound implies that BoN is not scaling- monotonic, as for fixed i and <RM (æ), the regret converges to a non-zero constant when N becomes sufficiently large. Thus, increasing N for BoN not only causes higher computational overhead, but can also degrade performance when the reward model is inaccurate.
Remark 4.3. For the case where which recovers Theorem 3.2 in Huang et al. (2025a). Notably, |Huang et al. (2025a) also provided matching upper bound when = 1. However, for A > 1, our analysis reveals an additional factor of 1/V/ in the lower bound, which has not been considered in prior works. direct application of the upper bound analysis from (Hann et al. (205aa) fails to capture this dependence on k, leaving theoretical gap of 1/Vk. It remains unclear whether this suboptimality is due to limitations in the analysis or is an inherent weakness of BoN. We conjecture that obtaining a regret upper bound for BoN with the optimal 1/vk scaling under the Pass@ setting may be fundamentally infeasible. We leave this future work.
1, we establish lower bound of M(min (1, / Ne (z)))

---

Published as a conference paper at ICLR 2026
5 OPTIMAL ALGORITHM FOR PASS @K INFERENCE
In Section 4 we have proved that neither (weighted) majority voting nor BoN is scaling monotonic, and neither demonstrates the desirable scaling with k for the @ k inference scaling problem. We also explicitly describe how the corresponding hard instance is constructed. By contrast, instances that do not satisfy the properties of these hard cases are precisely those on which the algorithms perform well. Thus, our earlier analysis also reveals complementary strengths of these methods: majority voting performs well when the reference policy assigns higher probability to the ground- truth answer than to incorrect ones, while Best-of-N can be highly effective when the reward model f is accurate. However, each method also exhibits weaknesses, they fail to fully exploit the avail- able information from either the policy or the reward model. To address these limitations, we intro- duce new algorithm, Best-of-Majority (BoM), which integrates the advantages of both approaches. Our algorithm is built upon the principles of pessimism commonly used in reinforce-
Algorithm 3 Best-of-Majority (BoM)
ment learning (Buckman et al. 2020; Jin al., 202T). When the reference policy Tet assigns low probability to a response, that response is rarely observed in the training data. Consequently, the reward model receives limited supervision in this region, leading to higher uncertainty and likelihood of error. The pessimism princi- ple advocates making conservative predic- tions under such uncertainty, which mo- tivates our design choice: rely the reward model only when Tref assigns suf- ficiently high probability the candidate. Since net cannot be directly observed, we approximate it using empirical frequen-
Require: Estimated reward model f. reference policy Tiefs frequency threshold a, sampling budget N, number of candidates k.
1: Observe context.2 .r
2: Independently generate N responses 5
{Ūr, V2..... yN from Tee(--|z).
3: Calculate frequency of each response y Y:
7(y) = Σ 1():=1 gy)
4: Eliminate responses with frequency less than as
5e. ty E 5: f(v) 2 a).
5: Query reward labels ( ((a,,))...,,,,. ŪN)).
6: if 15aa S k then
7: return Da.
8: else
9: Select Vi..... Th = Top--yyy D. :(v)). .......... ..))
cies of generated responses. Specifically,
10: return ("1....,
let ..,..., UN denote the N generated re- sponses for a given query. We first calcu-
11: end
late the empirical frequency of each emerging response:
N f
1 N
Σ 10 :)
Guided by the pessimism principle, we discard responses whose frequency falls below a threshold a, retaining only the subset
(v E 7(v) 2 a). =
Then we query the reward model on the surviving candidates and select the top h responses ac- cording to their predicted rewards, V1..... Th = Top-k/y E Da f(y)). The following theorem demonstrates the upper bound of BoM.
Theorem 5.1. Assume that the isreshold a= 3/(44((( Then the regret BoM (Algorithm 3 satisfies
(e) S (ogu(z) + C +0 (x) (00p)///))))_(((000a0000///1"/00
we have Moreover, when the sampling budget satisfies N 2 (x) log (AC (x)/
Ræ) & (xp((x) 5 (V (c))))
Here, we let N > 16(' log (x))/(()())()) with a term dependent on <RM(x) simplify the results. In general, we can replace the (x) with any accuracy that we wish achieve. Thus, Our selection of N do not require the knowledge of CRM(2), and our results will continue to work when (2) = O. When Cope (z) < (z) (z), the second term dominates, and con- sequently the overall regret scales 1/V consistent with the intuition that increasing & enlarges the candidate set and thereby makes the problem easier. Moreover, for fixed x, k, and C*)),, the regret bound converges 0 as N - co and (x) 0. This yields the following corollary.

---

Published as a conference paper at ICLR 2026
Corollary 5.2. BoM (AlgorithmB) is scaling- monotonic..
Computational Complexity. According to Theorem 5.1] the BoM algorithm requires approxi- mately (x(**))) (x)) samples to achieve low regret. comparison, Theorem 3.4 in Huang et al. (2025) shows that when = 1, the Best-of-N (BoN) algorithm also requires ((C* samples. This means for Pass @+ k inference, BoM achieves a better regret bound with a 1/vV improvement with- incurring additional generation cost. Moreover, BoM only queries the reward model for a filtered subset of candidates (see Algorithm
3 Line 5). which can reduce the number of reward evaluations.
Proof Sketch of Theorem 5.7 The crucial step BoM involves the construction of Va to approxi- mate the set of all responses with [z)(() a, denoted by Va. The following two properties of Ya makes preferable as the set of candidates: Firstly, if y/s E (x) for all i E [kt. we have an upper bound of the minimum estimation error min 4;, where A [F V r (z. 0:)1:
Σ
A?/k E Tea (+) ((ak) v (=)()))(ak),,
min A [E
(5.1)
where we used the property [x) 2 a in the second incquality. Secondly, since (e<(y"(>) 2
1/C*(x) we have y² E (1//C=(=). Therefore, (x) = (x)) the algorithm either outputs y² among the k submitted responses, incurring zero regret, or outputs & responses with f(x,, 7i) 2 F(x,y"), where the regret can be decomposed
r" (2, r" (" U1) I |r" (e, f(x, y
F(z, v²) - f(z, T.)] + [Zz, V. r" rx, v.)
(a)
<0
A
We take the minimum, plug in (5.1 and obtain
(x,,9)) - max r (2r, De S (x) + min Ag. S fop((a)) + v 1C (M) .E(k]
(E[k]
However, without direct access to Trals we use the empirical frequency म instead of गee in the con- struction of V., making 5% approximation of V'.. To extend the two properties of Va to Pa. we require the following event that sandwiches (a)())-()))x)) with (1))) and (a))
& (1) C (a)(ac)(o))))) (()(())()))()))
Under event &, can be set as 1/(4C*(x)) (z)) in 5.1.. The complete expectation formula gives
Regret(x) = E 1" (x, v2' - max (z, 71 8
P(E)+ + E (x,)") - max r (", (z, 76) E PP(-))
[E(A]
(E[s]
<x) + (
so it remains to characterize the prohability E. The probability of (1)c=(a)()) & (()())))))(()) can be characterized by first bounding Ply (((())(a))(t)) for any y (i/c-(a)(x)) using the Chernoff bound, and then apply- ing the union bound with the crucial observation of [1)c)(()(x)) < (z)).. When char- acterizing P(()((c-(e((x)) & (is(oc(tn)())),, we can similarly use the Chernoff bound in Ply D))(4c-(a))))) (z)) for any y E because the cardinality of the set ((x)))a///cc (I) is unknown. To resolve this issue, we assign elements of (Gr(() < (x)))(x)). The smallest number of bins is no more than 4C* because any two bins with Tee S 1x)44((x)) can be merged. With this assignment, we can bound P(G, n Dayaic (a)) (x) * Ø) with the Chernoff bound, and then use the union bound with the bins, which resolves the problem because the number of bins is bounded.
but the union bound does not hold
into "bins" {G,]. each with capacity 1/(2C* i.e.,
6 GENERAL LOWER BOUNDS
In this section, we establish a lower bound that highlights the fundamental factors influencing the Pass l inference problem. Specifically, the bound depends the coverage coefficient C* (x), the reward model estimation error & (æ) and cape (x), and the number of candidates k. It matches the upper bound in Theorem 5.1 which indicates that the algorithm BoM is minimax optimal.
8

---

Published as a conference paper at ICLR 2026
Theorem 6.1. For given prompt x, assume that (z)x) 2 2k. Then for any algorithm A for
the Pass k inference problem, there exists an instance 7 (X.3, T², rr, Tet. F) such that the
coverage coefficient is C* (x)), and .F) satisfies Assumptions 3.1 and 3.2 Moreover, and regret can be lower bounded by
(egret(x) = 52 (Cop(()) + (C
Theorem 6.1 shows that the term (ap unavoidable in the @ass@k inference problem and does not diminish as the number of candidates k increases. In contrast, the component associated with the expected squared loss, (RM(2), decreases at rate of 1/vk. This bound matches the upper bound for BoM (Theorem (.T.)rem5.T................... demonstrating that BoM is minimax optimal.
7
EXPERIMENTS
In this section, we empirically verify the effectiveness of our proposed BoM algorithm on mathe- matical reasoning tasks.
7.1 EXPERIMENT SETUP
Models and Datasets. We use Beennn-----nsstutt---- (Team 2025
(Qwen3-4B) as the reference
policy The We adopt AceMath-7B-- (Liu et al. 2024) as the reward model 7, mathematical reward model trained on large corpus generated by different language models which is selected due to its strong performance and moderate size. We adopt the widely used GSM8K (Cobbe et al., 2021). MATH-50K (Hendrycks et al. 2021), , and AIME242 data2eddataset dataset as testing corpus. We first
sample N trajectories and call the reward model to evaluate each trajectory. The answers are then extracted from the trajectories and clustered by mathematical equivalencd_ For each answer group, we use the average of the rewards of all the corresponding trajectories as the reward of this group. We also calculate the frequency of each answer group as estimation of (Te(-)).
Method and Baselines. Given specifie k, we consider our method BoM, and two baselines, majority voting and BoN. In BoM, we set threshold and select the lc answers (up to mathematical equivalence) with highest reward score and frequency greater than a. In BoN, we directly select the l answers (up to mathematical equivalence) with highest rewards. As for majority voting, we directly select I answers (up to mathematical equivalence) with highest frequency. Additionally, consider the SBoN algorithm studied in Aminian al. (2025); Verdun et al. (2025). Given N generated answers { we select & answers in a sequence, without replacement according to a softmax distribution p(y: (r) exp(33(2r, y:)), where is tunable parameter. We examine two variants: with and without reward calibration, where the calibration is implemented in the same way as in (Balashankar al. 2024). In the calibrated case, rewards are normalized using the win rate over the reference policy Tel.. We denote these versions SBoN(C) and SBoN, respectively.
7.2 RESULTS
Results with varying k. We first plot the results for h E (1,2,3,5 10) in Figure ((a) for GSM8K, Figure ( for MATH-500, and Figure [[C] for AIME24. We sample N = 2000 for GSM8k, and N 500 for MATH-500 and AIME24. On MATH-500, the performance of BoM consistently outperforms the baselines. On GSK8K and AIME24, BoM also shows large improvement over majority voting and outperforms BoN for small k. These results empirically verify the effectiveness of the BoM algorithm.
Results with varying N. We also study the performance of the three methods under different sample sizes. We conduct the experiments
the AIME24 dataset and vary N between 100 and 2000, with = 1,3.5. 5. Except for the case of N = 100 where the threshold of BoM is set to a = 0.015, we 0.005 in all other settings. We compile the results in Figure 2 the performance of majority voting remains consistently low, which aligns with Theorem 4.1, demonstrating that majority voting incurs constant regret and does not benefit from increased sample size. The performance of BoN tends to degrade as N increases. In contrast, when N 2 200, BoM consistently outperforms both
Please see Appendix results on additional models. https::// http::s:///gggngggggc.
co/datasets. /dii zhang fdu/AIME 1983 2024
TThe equivalence is determined through the standard implementation in Qwen2.5-Mar Math repository and refers the readers to their public implementation for more details. hattps://gitau com /wmm/wweLLM/////
Qwen2. wwt.saaaahbbbb//aaaaaaaa
6f Tec06f 03006f433442260 1220074773445, /vva i
grader py

---

Published as a conference paper at ICLR 2026
Malerty
SBoWiC:
SB:N
Numberat dk
Candiatee
Numberet Candcieecis)
(a) GSM8K
(b) MATH-500
(c) AIME24
Figure 1: The results with different BoM consistently outperforms the baselines on MATH-500 for all k and on AIME24, GSM8K when & is small, and matches the performance of baselines in other settings.
70
Arrowwwyy AR122
The Neturacy 190 en AMM22
55-
Mojarity Sirting
Mejority Verting BoN
The Menurecy 180
Majority Voiing
Buh
Bolt
BcM
DoN
SoMt
-0
500
1009
1500
2000
510
10.00
1500
2000
500
10000
1500
2000
Samples
Samples
Samples
(a) k
(b) A = 3
(c) k 5
Figure 2: The results with fixed and different N. When N increases, the performance of BoN is likely decrease over all the k. The performance of Majority voting remains low level. Among them, BoM has more consistent performance and outperforms baselines with larger N.
baselines and does not decrease significantly with the increase of N. This observation is consistent with our theoretical results, as BoM scaling-monotonie
7.3 ABLATION STUDY a
In this section, we present ablation study of the hyperparameter our BoM algorithm. When = 0, BoM will degrade to BoN, meaning that as a approaches 0, BoM behaves similarly to BoN. We further observe that selecting larger a can potentially improve the performance when k is small, although this comes at the cost of deteriorated performance for larger k. More experimental results are included Appendix [
Table 2: Ablation study of a of BoM MATH500, Qwen3-4B
@ass@k k
2
5
10
a (BoN)
83.6
87.2
88.8
89.2
0.003
86
88.8
89
89.2
90
α 0.005
86.8
89.2
89.6
89.8
90.2
& = 0.007
86.6
89
89.6
89.8
90.2
0.011
86.6
88.8
89.4
89.4
89.6
& 0.015
87.4
88.8
89.4
89.4
89,8
Majority voting
86.4
88
88.4
88.8
90
CONCLUSION
In this work, we demonstrate the scaling laws of the Pass@k inference problem by displaying the minimax lower bound of the regret and proposing the algorithm BoM with regret matching the lower bound. We also show that BoM has the advantage of scaling monotonicity compared with majority voting and BoN, which makes BoM preferable when scaling up the generation budget. For future work, it would be interesting to explore instance-dependent lower bounds, instead of the minimax lower bound as Theorems 4.1 4.2 and 6.1 addition, our current analysis assumes the uniqueness of the optimal response, such that the coverage coefficient will not depend the choice of optimal policy T" How to define generalized coverage coefficients under the multiple optimum setting remains be explored.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
We thank the anonymous reviewers and area chair for their helpful comments. QD, KJ. XL, HZ and QG are supported in part by the National Science Foundation DMS-2323113, CPS-2312094, IIS-2403400 and the Sloan Research Fellowship. QD is also supported in part by Amazon PhD Fellowship. The views and conclusions contained in this paper are those of the authors and should be interpreted as representing any funding agencies.
ETHICS STATEMENT
Our work investigates a novel @ass@k inference problem, focusing on the theoretical analysis of different inference strategies. In addition, propose new algorithm, Best-of-Majoric (BoM), which achieves optimal theoretical guarantees, and we further provide empirical validation to sup- port its effectiveness. Importantly, our experiments focus on solving mathematical problems with LLMs, and the language models do not generate or promote harmful content, nor does it raise issues related discrimination, bias, fairness.
REPRODUCIBILITY STATEMENT
In this paper, we conduct experiments with open-source LLMs on widely used mathematical datasets. A detailed description of the models and datasets is provided in Section while the key experimental parameters are discussed in Section 7.2 On the theoretical side, we present a proof sketch of the upper bound of the BoM algorithm in Section [] with the complete proof deferred to contains several lower-bound results, corresponding to the theorems in
Appendix B Appendix C
Sections
4.2 and
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.088 088777444 2023.
Gholamali Aminian, Idan Shenfeld, Amir R Asadi, Ahmad Beirami, and Youssef Mroueh. Best-of-n through the smoothing lens: KI divergence and regret analysis. arXiv preprint arXiv:2507.05913, 2025.
Ananth Balashankar, Ziteng Sun, Jonathan Berant, Jacob Eisenstein, Michael Collins, Adrian Hut- ter, Jong Lee, Chirag Nagpal, Flavien Prost, Aradhana Sinha, al. Infalign: Inference-aware language model alignment. arXiv preprint arXiv:2412. 2024.
Ahmad Beirami, Alekh Agarwal, Jonathan Berant, Alexander D' Amour, Jacob Eisenstein, Chirag Nagpal, and Ananda Theertha Suresh. Theoretical guarantees on the best-of-n alignment policy. arXiv preprint arXiv:2401.01877 2024.
Tim Brooks, Bill Peebles, Connor Holmes, Will DePue, Yufei Guo, Li Jing, David Schnurr, Joe Taylor, Troy Luhman, Eric Luhman, al. Video generation models world simulators. OpenAl Blog, 1(8):1, 2024.
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 arXiv:2407.21787, 2024.
Jacob Buckman, Carles Gelada, and Mare Bellemare. The importance of pessimism fixed- dataset policy optimization. arXiv preprint arXi::2009.06799 2020.
Hongru Cai, Yongqi Li, Ruifeng Yuan, Wenjie Wang, Zhen Zhang, Wenjie Li, and Tat-Seng Chua. Exploring training and inference scaling laws in generative retrieval. In Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1349, 2025.
Zheng Cai, Maosong Cao, Haojiong Chen, Kai Chen, Keyu Chen, Xin Chen, Xun Chen, Zehui Chen, Zhi Chen, Pei Chu, et al. Internlm2 technical report. arXiv preprint arXiv:2403.17297 2024.
11

---

Published as a conference paper at ICLR 2026
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomek Korbak, David Lindner, Pedro Freire, et Open problems and fundamental limitations of reinforcement learning from human feedback. Transactions Machine Learning Research, 2023.
Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei A Zaharia, and James Y Zou. Are more Ilm calls all you need? towards the scaling properties of compound ai systems. Advances in Neural Information Processing Systems, 37:45767- 2024.
Xingwu Chen, Miao Lu, Beining Wu, and Difan Zou. Towards theoretical understanding of transformer test-time computing: Investigation on in-context linear regression. arXiv preprint arXiv:2508.0757,, 2025a.
Zhipeng Chen, Xiaobo Qin, Youbin Wu, Yue Ling, Qinghao Ye, Wayne Xin Zhao, and Guang Shi. @ass@ k training for adaptively balancing exploration and exploitation of large reasoning models. arXiv preprint arXiv:2508. 107.225508..77,,, 2025b.
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. arXiv preprint arXiv:21 10. 14168, 2021.
Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomised algorithms. Draft Manuscript, http://www. brics. dk/ale/papers. html, 1998.
Devdatt Dubhashi and Desh Ranjan. Balls and bins: A study negative dependence. BRICS Report Series, 3(25), 1996.
Yan Fang, Jingtao Zhan, Qingyao Ai, Jiaxin Mao, Weihang Su, Jia Chen, and Yiqun Liu. Scaling laws for dense retrieval. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1339-1349, 2024.
Xidong Feng, Ziyu Wan, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309. 17179, 2023.
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pp. 10835-10866. PMLR, 2023.
Zitian Gao, Boye Niu, Xuzheng He, Haotian Xu, Hongzhang Liu, Aiwei Liu, Xuming Hu, and Lijie Wen. Interpretable contrastive monte carlo tree search reasoning. arXiv preprint 200.v22410.01707, 2024.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12945 2025.
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. arXiv preprint ar 103. 033774844 2021.
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, et Scaling laws for autoregressive generative modeling, arXiv preprint arXiv:2010.1477 2020.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically, arXiv preprint arXiv:
2017.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Train- ing compute-optimal large language models. arXiv preprint arXiv:2203. 15556, 2022.
12

---

Published as a conference paper at ICLR 2026
Audrey Huang, Adam Block, Dylan J Foster, Dhruv Rohatgi. Cyril Zhang, Max Simchowitz, Jor- dan T Ash, and Akshay Krishnamurthy. Self-improvement in language models: The sharpening mechanism. arXiv preprint arXivv:412.01199 2024.
Audrey Huang. Adam Block, Qinghua Liu, Nan Jiang, Akshay Krishnamurthy, and Dylan J Foster. Is best-of-n the best of them? coverage, scaling, and optimality inference-time alignment. arXiv preprint arXiv:2503..2188 200.00...88..... 2025a.
Baihe Huang, Shanda Li, Tianhao Wu, Yiming Yang, Ameet Talwalkar, Kannan Ramchandran, Michael I Jordan, and Jiantao Jiao. Sample complexity and representation ability of test-time scaling paradigms. arXiv preprint arXiv:2506.0052) 2025b.
Ying Jin, Zhuoran Yang. and Zhaoran Wang. Is pessimism provably efficient for offline rI? In International conference on machine learning, pp. 5084-5096. PMI., 2021.
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 Alignment, 2024.
Andy Jones. Scaling scaling laws with board games. arXiv preprint arXiv:2104.03113 2021.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski. Vinay Ra- masesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Soke et al. Solving quantitative reasoning problems with language models. Advances in neural information processing systems, 35:3843-3857, 2022.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5315- 5333, 2023.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling. Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, 378(6624)
2022.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402.12871 1, 2024.
Xiao Liang, Zhongzhi Li, Yeyun Gong, Yelong Shen, Ying Nian Wu, Zhijiang Guo, and Weizhu Chen. Beyond pass @ 1: Self-play with variational problem synthesis sustains rlvr. arXiv preprint arXiv:2508. 14029, 2025.
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 on Learning Representations, 2023.
Tianqi Liu, Yao Zhao, Rishabh Joshi, Misha Khalman, Mohammad Saleh, Peter Liu, and Jialu Liu. Statistical rejection sampling improves preference optimization. arXiv preprint 2.Xi:23309006577 2023.
Zihan Liu, Yang Chen, Mohammad Shoeybi, Bryan Catanzaro, and Wei Ping. Acemath: Advancing frontier math reasoning with post-training and reward modeling. arXiv preprint, 2024.
Youssef Mroueh. Information theoretic guarantees for policy alignment in large language models. arXiv preprint arXiv:2406.0588 055883 2024.
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 arXiv:2501. 2025.
13

---

Published as a conference paper at ICLR 2026
Reiichiro Nakano, Jacob Hilton, Suchir Balaji. Jeff Wu, Long Ouyang, Christina Kim, Christo- pher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al. Webgpt: Browser-assisted question-answer with human feedback. arXiv preprint 21XIv:2112.093322222 2021.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to fol- low instructions with human feedback. Advances in neural information processing systems, 35: 27730-27744, 2022.
William Peebles and Saining Xie. Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 4195-4205, 2023.
Jiahao Qiu, Yifu Lu, Yifan Zeng. Jiacheng Guo, Jiayi Geng, Huazheng Wang, Kaixuan Huang, Yue Wu, and Mengdi Wang. Treebon: Enhancing inference- time alignment with speculative tree- search and best-of-n sampling. arXiv preprint 0rXiv:2410.1603: 2024.
Rafael Rafailov, Yaswanth Chittepu, Ryan Park, Harshit Sushil Sikchi, Joey Hejna, Brad Knox, Chelsea Finn, and Scott Niekum. Scaling laws for reward model overoptimization in direct align- ment algorithms. Advances in Neural Information Processing Systems, 37:126207-126222, 2024.
Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. arXiv preprint arXiv: 1ttp:/999./..3.3 2019.
Nikhil Sardana, Jacob Portes, Sasha Doubov, and Jonathan Frankle. Beyond chinchilla-optimal: Ac- counting for inference in language model scaling laws. In International Conference Machine Learning. pp. 43440. PMLR, 2024.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in neural information processing systems, 33:3008-385 -0008830011200000 2020.
Benedikt Stroebl, Sayash Kapoor, and Arvind Narayanan. Inference scaling flaws: The limits of I1m resampling with imperfect verifiers. arXiv preprint arXiv:2411. 2024.
Yunhao Tang, Kunhao Zheng, Gabriel Synnaeve, and Rémi Munos. Optimizing language models for inference time objectives using reinforcement learning. arXiv preprint arXiv:2503. 19595, 2025.
Qwen Team. Qwen3 technical report, 2025. URL
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Niko- lay Bashlykov. Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307.002288 2023.
Claudio Mayrink Verdun, Alex Oesterling, Himabindu Lakkaraju, and Flavio P Calmon. Soft best- of-n sampling for model alignment. arXiv preprint arXiv:2505.03/56 2025.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arxiv:2003. 11171, 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans. Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, al. Chain-of-thoughh prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Tianhao Wa, Weizhe Yuan, Olga Golovneva, Jing Xu, Yuandong Tian, Jiantao Jiao, Jason Weston, and Sainbayar Sukhbaatar. Meta-rewarding language models: Self-improving alignment with arXiv preprint arXiv:2407.1953 2024a.
Yangzhen Wu, Zhiqing Sun, Shanda Li. Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solvin with language models. arXiv preprint a 240i 2000044444 2024b.
14

---

Published as a conference paper at ICLR 2026
Yuancheng Xu, Udari Madhushani Sehwag, Alec Koppel, Sicheng Zhu, Bang An, Furong Huang, and Sumitra Ganesh. Genarm: Reward guided generation with autoregressive reward model for test-time alignment. arXiv preprint arXiv:2410.08119, 2024.
Joy Qiping Yang, Salman Salamatian, Ziteng Sun, Ananda Theertha Suresh, and Ahmad Beirami. Asymptotics of language model alignment. In 2024 IEEE International Symposium on Informa- tion Theory (ISIT), pp. 2027-2032. IEEE, 2024a.
Rui Yang, Ruomeng Ding, Yong Lin, Huan Zhang, and Tong Zhang. Regularizing hidden states enables learning generalizable reward model for Ilms. Advances in Neural Information Processing Systems, 37:62279-62309, 2024b.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in neural information processing systems, 36: 1809-11822) 2023.
Jiahui Yu, Yuanzhong Xu, Jing Yu Koh, Thang Luong, Gunjan Baid, Zirui Wang, Vijay Vasudevan, Alexander Ku, Yinfei Yang, Burcu Karagol Ayan, al. Scaling autoregressive models for content- rich text-to-image generation. arXiv preprint arXiv:2206. 10789, 2(3):5, 2022.
Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. Rest-mets*; Llm self-training via process reward guided tree search. Advances in Neural Information Processing Systems, 37:64735 64772, 2024.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging llm-as-a-judge with mt- mt-bench and chatbot arena. Advances in neural information processing systems, 36:46595-46623, 2023.
Banghua Zhu, Evan Frick, Tianhao Wu, Hanlin Zhu, Karthik Ganesan, Wei-Lin Chiang, Jian Zhang, and Jiantao Jiao. Starling-7b: Improving helpfulness and harmlessness with rlaif. In First Con- ference on Language Modeling, 2024.
A COMPARISON WITH AMINIAN ET AL. (025
In Aminian et al. (2025), the theoretical guarantees of BoN are studied under different setting, and a variant called SBoN (Soft BoN) also analyzed. this section, we provide a comprehensive comparison of the assumptions and theoretical regimes considered in both works, Aminian et al. 2023) made three main assumptions.
The reward function is bounded, i.c., 0 S. r+(()) Rmax. 0 S f(.) S Rmax.
The reward estimation error (x) := Y/2 lo (exp(
(3(r" ( (1t, 1/ f(xx ))))
Maximal reward can be achieved for the estimated reward f.
In comparison, the first assumption aligns with our setting with R = 1. The second assumption aligns with Assumption 3.1 only when 0. For the third assumption, assume the maximal
value can be achieved only for the true reward model r", with a unique optimizer. And the error at the optimal point is specially considered.
Results of BoN: Aminian et al. (2025) proved regret of
+ (aoo))//Coooo (coo))) + ev log (1+ Coe.Fier(x)) 11)
Regret(z) x) = V (z) V
( Coo,Fier(x))
N
for some constant e > O. In this result, it considers two coverage definitions dependent on f and r", Moreover, the reward estimation error is 5 oo, which corresponds to the case of supreme norm, instead of the squared norm. When N + co, the convergence rate /1/N. Comparison with our results: One central distinction lies in our different focuses. Our work focuses on analyzing algorithmic performance within the Pass framework, and therefore our theoreti- cal results explicitly account for the ability to submit & different answers, which is not studied in Aminian et al. (2025). In particular, for the theory of BoN, Thcorem 4.2 establishes a lower bound that depends explicitly on k, which serves As for upper bound of BoM, we prove that it has an exponential decay dependence of N, together with a term of O / /ee /k), which directly has dependence. Although the definition reward emror differs, thus the results not be directly compared, we have shown faster convergence rate
parallel result to Aminian et al. (2025).
15

---

Published as a conference paper at ICLR 2026
of N than Aminian et al. (2025)
Results of SBoN: For SBoN. Aminian et al. (2025) proved a regret of
(eg V (e3.(x)) (v Coo + /Coo.r ver(x))
+ + log (1+ (oo,Free(())- 1 log(Coc,r)) (x (x))/))
N
Note that + O, as the last term will explode. Thus, the setting of of|Aminan et al. (2025) is never same as ours. Again, when N - co, the convergence rate of SBoN is vI/N, compared with our exponential decay. Finally, our focus is on the Pass@A k setting, which has never been analyzed in Amiinian et al. (2025).
B THEORETICAL GUARANTEE OF BoM (ALGORITHM) 3)
In this section, we will prove Theorem 5.1 which provides the theoretical upper bound of Algorithm To start with, for any 0, we denote
(x) = ty E A(r): Ter()) 2 a},
indicating the set of responses with relatively high probability for Tee- Using the definition of the coverage coefficient (3.2), we have y" (1) as long 2 1xC*(z). Next, we will build the relationship between the empirical set (x)) and (x).) Denote & as the event such that
(1)c-(()(()) c P2/(1C-()) ())
Our proof consists of two parts:
Step 1: We first show that & holds with high probability.
Step 2: Provided that & holds, since y² E (1)c)=()(xx), we have Y² E D furthermore,
since yi E (a)(( we have Ti E (1)(4"= (x). so )ne((ūi)z)) 2 1/(4C"(1)) (x)) for every sub-
mitted response 1/5. We can then characterize A, = Ir (ar, Di) Alx, 76)1 using the definition of the estimation error fiM- If y {UI..... ............. }k then the regret is zero; if y o 121..... yk then using Assumption 3.2] we have
r" (xx,y") r (x, T.) (x, F(x,
[(x, v) F(x, Wi)
[rx V.) r (x)
(x)
$0
Combining these parts together, we complete the proof of Theorem 5.1
We now get into the details of the proof. The following lemma states that the event of will occur with high probability:
Lemma B.1. E holds with probability at least - (z)e
N/(32C" (x))
Proof. The proof consists of two parts that characterize the probabilities of P1yc(s(2)) &
(a)( and Vay(4C=<=)) of Ar respectively:
Part I: Probability of (1))-())()) of Da)(4c-(2))- We first fix any e )))c-(o)(()) By Chernoff bound, we have
((f(v) < <3/(4C(())) S exp (-NToc(ula) (1 (x) )) S NN/(3200
(B.1)
where the first inequality holds due to the Chernoff bound, and the second inequality holds because Trer(y|>)) 2 1/C" (x). Applying the union bound to all E (1)00(()(()) we have
(()))) & )al(c)())) = =
V
1 < 33(C4 (x)))
(
Σ
P(R(y) < 3/(4C'(x))
1 - (x)) . NN/33CC
16

---

Published as a conference paper at ICLR 2026
(B.2)
where the first incquality holds due to the union bound, the second inequality holds due to BB. and the last inequality holds because (e)) (x)).
Part II: Probability of (3/(AC^(w)) E (1)( (2). We cannot use the same union bound as
B.2)) because the cardinality of the set to take union bound (()1/(cc=<<)) (2) is unknown. To (2) into groups, then apply Chernoff bound to each group, and finally apply the union bound to the groups. This technique resolves the problem because the number of groups is in the order of ((C*()) and the union bound goes through
resolve this issue, we first partition ((C)
without incurring the cardinality of J (1/((aa<==))((
In detail, suppose that y J/ (==))(( Ya to of the groups sequentially. For each response yi E (e)))) if there exists group Gj such that
(9r We start with a single group G1 = Ø, and add
Σ Terllyla) S 20*(x)'
(B.3)
VEG,
then we update G3 with Gj U {a;} where j is the smallest index that satisfies (B.3). Otherwise, we create new group {a:}. From the construction of the groups, we can easily see that the probability of any group Gj under the reference model satisfies
1 Tyet (G.lz) = Σ Tnr(aax)) S 2C'(x))
(B.4)
aEC,
Furthermore, the total number of groups M should be no larger than 40" because otherwise, suppose that (B.3) does not holds for y and any existing group Gý(i E [M]) where > (x)(x)) 1, i.e.,
Σ (y)() > (x)(z) (ur((() (C'(x)) D
(B.5)
where the last inequality holds because (a) < (x)4 We then have
Σ
(
VEy
M
[vo(() + Σ mer(ullz)
+ Σ
Σ yEG
T
j=2
1
+M 11) 40)((z)
(0*
(x) + (40 (1) 11) (x) =1 1,
where the first inequality holds because the union of a; and all existing groups is a subset of A(x).. the second inequality holds due to (B.5). and the last inequality holds due to the assumption of M > 40* 1. We have thus arrived at a contradiction, and we conclude that M < 40" 4C"(z). For each group, we apply the Chernoff bound:
V 1(((y) 2 3/(40*(z))) VEG;
<((A(G,) 2 (x))
s exp - (3/(40((z) - Teet Teer (G, (G,lz))² 3/(40((x)) + Tea G,[[z)
< <e- 2/2000))))0)),
(B.6)
where the first inequality holds because if the frequency of one response in G, is larger than (/AA"(x)). then the total frequency of group Gj should be larger than 3/(4C*(1)) the second
17

---

Published as a conference paper at ICLR 2026
inequality holds due the Chernoff bound; the last inequality holds due B.. union bound to all groups.
Applying the
P(Ds/(aC)()) & (L((o=(())()) = IP
17(x) 2 3/(4C
P
( 2 3/(AC
MEG,
$ Me N/(200"(x))
< 40 (z)e ( NN((220(x)),
(B.7)
where the first inequality holds due to the union bound, the second inequality holds due to (B.6). and
the last inequality holds because M < (x) and e N/20C" (u)) S e e-N/(32C" (x)), Combining
B.2 and (B.7), using the union bound, we have
P(E) 2 5Ce 5Ce-N/(32C"()),
Thus, we have completed the proof of Lemma B.1
Using this lemma, we then proceed with the proof of Theorem 5.1
Proof of Theorem 5.7 Suppose that & holds. If y" is included in the submitted responses, then the regret is O. We now consider the case where y" submitted. According to the definition of the coverage coefficient, we have
< x (v"lx)/)* (x)"
80 1² (o))) Furthermore, since Vi (x) C Sas(ic-()) when & holds, we have y" E )3((4C-(=)) Since y" is not selected as the output, we know that (i) at least & responses are submitted because otherwise all responses in P3/(40-(e)) would be submitted, and (ii) F(x, x)+) s F(x, D1) for any i [k.. We thus have
f(z.ū)) 2 F(z, v²) r" (I,z") Copi (x)
(B.8)
where the second inequality holds due to Assumption 3.2 Therefore, the regret conditioned on event is
min (r" "² r" (xx (()) S Cape + min (f(rr, Mi) r. (2. iE(k]
(E(A]
cope <opp(1)
[ Ti) r. 02)
Te
4C (x)
I Cope (x)
T (Te(( (x, 12)
k
(C*())
(x)
[(r()))))F(..v) - (xx,
h:
NEV
4C* (x)
= (x)
(B.9)
k
where the first inequality holds due to (B.8) the second inequality holds because the minimum is no larger than the average, the third inequality holds because = 2 1/(4C*(x)) for any y E
(ls((ac=(=)) when Pay(ac (x)) C D1/ccc--en (2)), the fourth inequality holds because {ūr,... 7k is subset of y, and the last equality holds due to the definition of the estimation error f
Combining (B.9) with the case where y" ....... ] and the regret condition E,
conclude that under
140 (x0*()) (x)
1" (x,8") max maxr (xx Th. S (x) + kE(k]
(B.
k
18

---

Published as a conference paper at ICLR 2026
Finally, we take the complete expectation of the regret:
Regret(x) B
rr y²)
maxx
r" (z, Ti)
P(E) + (r max
(" (x, 01))
-cj PP(-E)
iE(A)
aE(A]
4C (2 (M)
Eopr(z)
+P(E)+1-P(-)
40 ((M + (z)e N/
Cape +
k
where the first inequality holds due BB10 and (ægret(2) 1, and the second inequality holds because P(E) S 1 and due to Lemma B.1 Finally, when N 16C* (x) log (=)/RR(( have
Regret(2) S (xp + (o))
We complete the proof of Theorem 5.1
C PROOF LOWER BOUNDS
In this section, we will prove the lower bounds used in the main text of this paper. Specifically, we establish the results for majority voting (Theorem 4.1 Best-of-N (Theorem (42 and the general case of Pass @ k inference algorithms (Theorem 66. Before proceeding, we first establish an inde- pendent lower bound regarding Copt (z). This result is general and can applied any subsequent lower bound, introducing an additional (x) term.
C.I LOWER BOUND REGARDING copr(2)
We first study the following hard case where any algorithm for the Pass Tass@k inference problem suffers from the regret of 22 (x))p(())) Combining this lower bound with any algorithn-dependent lower bound b (obtained from the analysis of a hard instance), we can show that the lower bound of the algorithm is
A(max (oop b}) (2) + 6).
Lemma C.1. Assume that (ope(z) < (c) (r) and (*(x) 2 2k. Then there exists an instance I (X, y, r", Tref: f) such that the coverage coefficient (*)),, and (r*,F) satisfy Assumptions 3.1 and 3.2 Furthermore, for any prompt x E X, the regret of any algorithm for the Pass@ le inference problem satisfies
Regret(x) = (x(Copr(:))
Proof. For simplicity, we omit the prompt in our proof. We apply the idea of the averaging hammer, which considers total of M hard instances such that no algorithm can perform well on all instances. It is technique commonly used in the proof of lower bounds (see e.g., Theorem 24.1 in Lattimore & Szepesvári (2020)). The responses set is {Vo, VI:-.., MMM for all M hard instances. The reference policy and the approximate reward model are also shared by all instances:
(yo) F(go) = O, F(y1) = ... = f(yM) = Copt- The hard instances are different only the ground -ound-truth reward model and n* For instance I, (X,Y, m3, r3, ree) where j [M] set
M/C", (eee
(Tr( = 1/C";
0
i 0;
():) 8ej, (y))
i j:
E
otherwise.
For all hard cases, the total estimation error is 2 CC* < < Among these M hard instances, any algorithm that outputs up responses will fail to output optimal response at least M instances, inducing the regret of cope. Therefore, the average regret of these M instances is at least
M - k M Copt.
Regret
Setting M 2k, we have Regret- R((app))
19

---

Published as a conference paper at ICLR 2026
C.2 LOWER BOUND OF MAJORITY VOTING (THEOREM 4.1
Proof of Theorem 4.7
For simplicity, we omit the prompt x in our proof. Consider the following
hard instance. The size of the response set is 2 k, with y {yo, y M1, 1/, 12,........................ ,................. ,.. The ground truth reward satisfies:
r' ('0) = 0;
(v") = 1;
A1 siss. r"((:) = 1/2,
Therefore, the optimal policy " satisfies:
n (y0) = O;
("²) =; (vi) = 0,
In this instance, we assume that the estimated reward function iis accurate. Let = 2w(1)/ We further define the reference policy as:
(uo) 1 (1 nk)/C*;
TTe(y²) = 1/C" TTp((:)) - =n/0", L1 u k.
The reference polity is well defined as long as C 2 1 2k) (1)2 Now we consider the sampled responses V1, Ø2,. .........e.............. ..., ÖN. Define
N Σ 1( y"); j=1
N Σ
1 = v1), We [
j=1
Then the expectations of N and N; are
N
n C
E[N"]
B[N
Aisisk.
C
Using the Chernoff bounds, we have
N
3
N
N
3n
-N1
N
2C
exp
90
P
N
<
40
<xxp
10
(C.I)
Denote E as the event such that
N
3
N
3n
Vi e [k].
20
N
40
Taking the union bound with C..1
have
(-N
Nn
N
P(E) 2
k exp
2 1 (k: + 1) exp
9C*
40
90'
where the last inequality holds because > 1. Under event E, we have
w(1/2)N, w: (1)N*
N//N
w(1/2)
3n/(4C")) (1) 3/(2C*) 1,
N*/N
where the inequality holds due to the definition of the event & and the definition of n. Therefore, conditioned on event E, the (weighted) majority voting (Algorithm [ suffer from 1/2 regret. To summarize, the regret satisfies
will output (3h..... M& and
( 2
1- (k: + 1) exp (,m1)
Regret 2 P(8)- E [[Regret >
When 2 (x" log + 2),
N
(k: 1) exp
2 1/2.
9
C.3 LOWER BOUND OF BON (THEOREM 4.2
To prove Theorem is small, then it is very likely that y" does not appear in {Ū1.... .... ØN ); (ii) When N is large, then it is very likely that number of responses that are suboptimal in r* but better than y in f are sampled. The two hard instances share the same structure but are different in parameters.
we construct two hard instances to accommodate two cases: (i) When N
20

---

Published as a conference paper at ICLR 2026
For simplicity, we omit the prompt x. We consider two hard instances, one for I C* and the other for 2 C
Proof of Theorem 4.2
Case 1: N < C*. We consider a hard instance with y = {yo, 8" J. and
π (yo) = O, Teer = 1/C", Terrly)) = 1/C"; F(yo) O, f(v") =
" (v")=; r" (yo) = 0,
r" (1")) =
For this instance, the estimation errors are Copt ERM the regret 1. The probability that y & ......., NN } (1 1/C*) Therefore, we have
no sample yi..... ON is y², then
Regret 2 (1 - 1/C"M 2 (1-1/C") 22122111 1/4,
where the second inequality holds because N I C*, and the second inequality holds because C* 2 Therefore, the BoN algorithm incurs constant regret in this hard instance when Σ C",
Case 2: 2 C We consider the following hard instance: The response set is y {v" Yo: M1. M1..... yM J- Let p > 0 be parameter be determined. The reward models are
r r0")) 1, (wo) 0, (1()) CRM 2/F
-1-")=1-6 F(yo)= 0, f(y.)
where 8 Copt is sufficiently small positive number ensure that the reward of y1,-.. y is slightly better than y" in f, but y" is still the optimal response in r", In this way, x (g") = 1 and x Ty() 0 for 0, ,,, M. The reference model satisfies
ne 1/C", (yo)
1/C* p.
Tee(()) p/M.
For this instance, the coverage is C*, and the estimation error is less than CR when is sufficiently small.
Simple analysis. We first consider a simple setting where M k. When "I....,ūy UN covers ev- ery response in (yi,..., }. then VJ.....,14. will be the output of BoN, causing the regret of ERM/2.p. The probability any yi not being covered
(1 p/k)
Using the union bound, the probability that there exists y, not being coverer is upper bounded by
P yi & (
. ON }1 S k(1 - p/k)
Thus, the regret of making the wrong decisions in 1/1 3h lower bounded by
- k(1 pp/k)
Then the regret satisfies
Regret 2 (1 k(1 - -p/k)²) ERM 2/p
(C.2)
In this instance, when / Ne RM/ k log [2 < 1, we select p (k/N) log(2k). Then, RRM/(2 <RM/(2/P) /Nehus/ log [ < 1. Thus, the constructed y* satisfies 0 r(()) 5 1. Then we have
1 1 k(1 - p/k)) = k log(2k)
N
2 1 k. exp (- log(2k)
)
N
1 k exp 1lg((k))
1/2.
where the first inequality holds due to the basic inequality 1- < exp(-x), Vr E R. Substituting this into C.2 we have proved that the regret be lower bounded by Zi R(/Neffaa/ (klog k)).
21

---

Published as a conference paper at ICLR 2026
Otherwise, when / RM log (loo((2))//))) 22) 2 1, let rR//4. Then, the regret in lower bounded by
C.2 can be
Regret
1- k
RM
4k
RM
1k (2g((k))// /
4k
2
4k (2k)
RR
2 A exp
4k:
1 k exp
- log(2k)
1/2,
where the third inequality holds due to the basic inequality 1 exp(-x), Vx E R. Therefore, we have
Regret 2 O min {I, / (klg
This analysis will lead to additional logarithmic term on k which is unnecessary. To avoid this term, we consider the following improved analysis.
Improved analysis. We consider the instance where M = 2k. Consider the event where at least responses among .1..... VM are covered by D1.....
... Nv. Since f(y,) f(y") for 1, 1...., M, the optimal responses y" is not included in V1. Vi.....: Vks which also incurs the regret of (2v//2v/)) We
now consider the probability of this event. Define the following random variables:
Define S as the number of samples within y1,..., WAr, i.c.,
M Σ
S
T
=
1=1
Define O, as the occupancy of yj. i.e.,
N 0 = V
1o = ツs4
1=1
Define D the total occupancy of (.I..... yM J. i...
M
D = Σ Oz.
Our goal is to lower bound IPD 2 kt). Fix $o > Using the total expectation formula, we have
P(D 2 k)) = Σ
P(D KIS = P)P =)
22
Σ
P(D K$s s)P(S
#2
2 P(D 2 h== = P(S so).
(C.3)
where the first inequality holds because 2 k. and the second inequality holds because P(D > k|S = s) > PDD 2 A|S = so) when s 2 so. We then calculate the two probabilities separately. We first use the Chernoff bound to characterize P(S sa). The expectation of S is
N E|S = P(O P(O E (Vi,... ..rr) = Np.
Then by the Chernoff bound, we have
(Np so)?
P(S 2 so) 2 exp
(C.4)
2Np
22

---

Published as a conference paper at ICLR 2026
We then calculate the conditional probability P(D > k|S su), and assume without loss of generality that .i.....80 Noo fall within {311 Yor). Conditioned on this event &, we have P(β: = the vanilla Chernoff bound
yy) = 1/M for 1 < i 5o and 1 S j S M. Although we cannot to bound (P 2 k S = s). we can use the Chernoff bound for negatively-correlate variables (Dubhashi & Ranjan 1996) (or See Theorem 4.3 in Dubhashi & Panconesi (1998) to bound the probability. We first calculate the expectation of D, which is
random
E[DIS = sul [E M(1 P(u + Uj. Vi E [soll) M (1 */.
We then verify that OI...., OM are negatively correlated, which is to show that for any subset
J C [M], we have | O₁] I A [. i.e., P(O; = 1, E J) S I P(O; 1). We prove by induction with respect to the cardinality of J. The inequality is trivial When | = 1. Suppose that the inequality holds for all J such that [J] I n. It then suffices to show the inequality
holds for J = [n + 1]. Note that
P(O L, ..... On+1 = =)
= -P(O; = 1, ,,..,,,, O0, =1)-P(O, = I,..., O2 = 00h=1[0m+ = =) =)) P(On+1 = 0)
=P(O) 1,..., O2 1.)==1PPP(On. = 1)
+ [P(OO, L.... On =) - PPO1 1, 0,. = 110x+1 0)] PP(On+1 = 0),
Using the induction hypothesis, we have
P(O I,....
=
II 5=1
P(O, = 1).
It then suffices to show that
P(O,, = 1, 1,, (.,,,,,,=))PP(()111..... On
11
which is trivial because the event Øi = yı [n]) becomes more likely conditioned of the event that Tr * Vn+1- Therefore, the inequality holds for [J] = =n + 1, and we complete the verification of Oj being negatively correlated. Therefore, using the Chernoff bound for negatively-correle random variables, we have
exp (M[ (1- -})2
P(D 2 K|S = so) 2 1
(C.5)
2M - (1 1/M]00]
Substituting C.4
and
C.5
into
C.3
we have
CRM
Regret 2 P 2 k)
2/P
[M[] (1- 1/ (1 k32
] [[- [ exp (- [NNp (NNp=50)² s0)2
ERM 2/p
1 - exp
(C.6)
2M - - 1/M)a00
2NP
Let M = 2k, Su = 3k. /N4 S 1, we set = 4k/N. Then, (HM/(2vp)) =
N /k/4 < 1. Thus, the constructed r" satisfies 0 S (+) - 1. In this case, we have
- 11-11 = 1 (1- 2k
3k
2 1 - 1.5
3
4'
We thus have
{M[ - (1 - 1/ kj2
1 1 exexp
2M - (1 10
(2k 3/4 114-kk -k²²
2 1 exp
2. 2k 3/4
1 k/12
> 1 1/12
where the second inequality holds because k: 2 1. We also have Np = 4k, so
(-
(Np - ss)² = 1 - 1eexp
(4k 3k)
1 1-exp
= 1 e k/8 2 =
2Np
2. 4k
23

---

Published as a conference paper at ICLR 2026
where the last inequality holds because & 1. Combining all the above, we have
NERM
Regret 2
ERM
(1- (1--))_11--- - 2 0.004\
VAk/N
Otherwise, if (/ee/////// 2 let / Then, with the same argument as that in the Simple analysis part, the regret is lower bounded by (1()). Therefore, have
Regret 2 2 min { v Nay.ee NcRM/k))
C.4 GENERAL LOWER BOUND (THEOREM 6.1
We first provide
general version of Theorem 6.1
Theorem C.2. Assume that (x) 2 max 2}. Then for any positive integer M E [k; (*))
and any algorithm A that outputs k responses, there exists hard instance I = (X V n², r", Tiet 7) such that the coverage is C, the estimation error is ERM and the regret of algorithm A satisfies
M - k
(*)))
(x)
M
M M-1
When C 2 2k, we can set M = 2k and obtain the regret lower bound of ON RM/ /k) in Theorem
6.1
We now present the proof of Theorem C.2
Proof of Theorem C.2
We consider the case of = {x], and omit the prompt x A(x), mer(-|ar).
F(x,-), etc.
To prove Theorem 6.1
again apply the idea of the averaging hammer, and consider total of M hard instances such that no algorithm can perform well on all instances. All of these hard instances have a total of M + possible responses (Mo..... yos and we aim make /1,,.. Mas hard to distinguish from each other. In detail, all hard instances also share the same reference model and the same f:
(yor =1 - M/C, Tee((y)) = ... = - F(yo) = 0, f(y1) = =.u.:.(fM))--
For hard instance (j E [M]). we make Yj the optimal response with ground truth reward be- ing 1 and It (Vr) = 1, and make all other responses suboptimal with gap of 5, i.e., I, = (R, 23, ( r.. Teet, F), where
T] (w1) = 652,
(m)
= j;
1 8 otherwise.
In this hard instance, the coverage C, and in order to make the estimation error equal to e we require
(M 1) 8 1/C= C
which indicates that 5 CCRM (M - 1). Since any algorithm can only output a maximum of different responses, cannot output the optimal response in at least M k out of the M hard instances, suffering from the regret of least ö. Therefore, the averaged regret of the M instances is at least
M
Ce
B B (13(.))))(((()) max (1i(0)), .T (Ta))) 2 M (M k) 8
M
M
M
Therefore, there exists an instance Iy- within the M hard instances such that
M
CefM M -1
Egt..... ii ~ -a (13- (2)r)) max fr²- (M),, ... (mx)
M
24

---

Published as a conference paper at ICLR 2026
D FURTHER ABLATION STUDIES
In this section, we present additional ablation studies on the choice of a, using the AIME24 and GSM8K datasets.
Table 3: Ablation study of of BoM in AIME24, Qwen3-4B
Pass @ k
2
5
10
0 (BoN)
53.3
60
63.3
70
73.3
& = 0.003
56.7
66.7
70
73.3
73.3
0.005
53.3
66.7
70
70
70
& 0.007
56.7
70
70
0.011
50
63.3
63.3
63.3
63.3
a 0.015
60
60
Majority voting
36.7
43.3
46.7
46.7
60
Table Ablation study of a BoM in GSM8K, Qwen3-4B
Pass@
0 (BoN)
83.58
88.56
91.50
92.38
93.26
Q
0.003
85.34
90.32
92.38
92.67
92.67
0.005
85.34
90.03
92.08
92.38
92.38
0.007
85.92
90.62
92.08
92.08
92.08
0.011
86.22
90.32
91.50
91.50
91.50
0.015
86.22
90.32
91.20
91.20
91.20
Majority voting
90.03
92.96
92.96
E ABLATION STUDY OF REWARD MODEL
To further demonstrate that our findings are not tied to any particular reward model, we addition- ally evaluate using InternL.M-rrwwrrd (Cai et al., 2024). This model is not specifically trained for mathematical reasoning and shows weaker performance the evaluation of Liu et al. (022).. Even under this weaker reward model, algorithm behaves consistently and leads to the same overall conclusion.
Test Accuracy (%) on AIME24
70
60
50
Majority Voting
BoN
BoM
40
SBoN
SBoN (C)
2
6
10
Number of Candidates (k)
(a) AIME24
Figure 3: The results of different & with N = 500 using InternL.2-rrewrrd, Qwen3-4B-Instrue
25

---

Published as a conference paper at ICLR 2026
$7.5
pee Accumtr CD on MMEE
15.0
SBoWIC
SBSNIC)
Numberat dk
Cardestte
Number Candcneecis)
(a) GSM8K
(b) MATH-500
(c) AIME24
Figure 4: The results of different & with 500 Qwen2.5-1.5B.
F ADDITIONAL EXPERIMENTS
In this section, conduct experiments additional model, Qwen2.5-Math 1ituth-115.. 1.5B- 1B-Instruct (Qwen2.5-1.57) for more results. The other experiment setups follows the experiments on Qwen3 unless specified. The results Qwen2.5-1.58 compiled in Figure|4 In particular, BoM matches the performance of BoN on GSM8k and outperforms BoN on MATH-500 and AIME24. The per- formance of BoM also surpasses majority voting on GSM8K and MATH-500 with < 5. These results shows that BoM demonstrates a better overall performance over baselines when k is small.
THE USE OF LARGE LANGUAGE MODELS (LLMs)
We use I LLMs as tool to refine our writing and correct grammatical errors.
26


Reviews:
[{"review_id": "C4tMDI6bbg", "reviewer": "Reviewer_h4Se", "summary": "The paper considers the problem of how to use a given LLM, a proxy (potentially inaccurate) reward model, and $N$ responses to a prompt (sampled iid from the LLM), to select $k$ out of the $N$ responses. The performance metric for any selection scheme is the regret between the expected reward of the best response and the expected best reward of the $k$ selected items, according to a (unknown) ground-truth reward model, also termed the pass@k regret. Within this setting, the paper argues that existing inference strategies such as Best-of-$N$ and weighted majority vote do not perform satisfactorily in that they do not give $o(1)$ regret with $N \\to \\infty$ and the are not monotone, i.e., their performance can degrade with more samples $N$ and an accurate proxy reward model. The paper goes on to design a new algorithm (Best of Majority) that, in spirit, is a 'best of both worlds' solution, blending the strengths of both these strategies using an additional probability threshold hyperparameter $\\alpha$. This algorithm is shown to achieve monotone scaling and $o(1)$ regret as $1/N$ and the proxy reward model error tend to $0$. The paper also exhibits a fundamental lower bound (in a worst-case sense with a hard instance) on the regret scaling as a function of the reward model approximation errors, the base policy coverage distribution and $k$.", "questions": "- Please see the 'Weaknesses' section for questions that are posed inline. \n\n- (minor) Why bother defining two coverage coefficients $C^*(x)$ and $C^*_\\infty(x)$ when you finally argue that they coincide?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The problem formulated and studied in the paper is very timely and relevant. Inference efficiency and quality optimization at scale carries a high potential to make real-world impact in LLM pipelines. \n\n- The paper's mathematical model of the inference problem is thorough, and captures several practical aspects, including the fact that reward model oracles used for cheaply judging quality of responses must be only approximately accurate, and that upto $k \\geq 1$ responses could be proposed for a prompt in the pass@k performance metric.\n\n- I appreciated the clear and precise technical analysis of the regret performance metric, using appropriate tools from probability and concentration methods. The results are presented with clearly stated hypotheses/assumptions and expose the underlying problem-dependent quantities clearly, e.g., $\\epsilon_{RM}$, $C^*(x)$, etc.\n\n- The paper's analysis is comprehensive, showing both algorithm-dependent and fundamental performance limits for the pass@k regret. \n\n- The paper designs a new inference algorithm (best of majority aka BoM) to circumvent the weaknesses raised about the existing inference algorithms.", "weaknesses": "- While the negative results for existing inference algorithms such as BoN and weighted majority vote are illuminating, they are essentially of a worst-case flavor in the sense that a 'bad' instance is constructed in each case to render high $\\Omega(1)$ regret. A concern is that this is too 'pathological'; instead, bringing out the dependence of an arbitrary problem instance and its parameters in the regret lower bound per algorithm could be more insightful and, of course, a stronger result that would imply, as special cases, the worst-case instances above. \n\n- Perhaps the most significant weakness is that, while the new algorithm BoM ensures controlled regret, it also puts the burden on the deployment engineer of tuning the additional crucial hyperparameter $\\alpha \\in [0,1]$. The performance guarantee of BoM in the paper is only valid when $\\alpha$ is set proportional to the probability of the base policy on an optimal answer, $\\pi_{ref}(y^*|x)$, in addition to ensuring that $N$, the total number of generations, is above a threshold determined by the reward error $\\epsilon_{RM}(x)$ **per prompt**. I wonder what practical modalities exist to be able to set these hyperparameters in this way. There is no adequate discussion of whether these hyperparameters can be estimated or learnt from data or trials. \n\n- In a similar vein, the paper's experiments shed no additional light on how to set $\\alpha$ and $N$ 'well' depending on the problem instance and reward model error. There is no discussion on what considerations went into the choice of $\\alpha$ used in the experiments, as well as an ablation on how different values of $\\alpha$ influence overall performance. These would be essential in judging the quality and robustness of the new algorithm. \n\n- The dependence on $N$ (the total number of generations) is missing in Theorems 5.1 and 6.1. This is in contrast to the referenced work of Huang et al (2025) that clearly outlines how $N$ influences regret performance. Could the author(s) please discuss this explicitly?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iKWJsDvBHX", "reviewer": "Reviewer_ckrW", "summary": "The paper studies Pass@k inference and proves that majority voting and Best-of-N are not scaling-monotonic, then introduces Best-of-Majority (BoM).", "questions": "please see weaknesses", "limitations": "", "rating": 2, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "An optimal algorithm for inference-time algorithm", "weaknesses": "**Weaknesses**\n\n1. **Relation to [1].** Aminian et al. [1] also derive an **upper bound** on BoN regret. Please state their result precisely, compare assumptions and regimes (dependence on (N), and reward-model error), and explain how your bounds differ or complement theirs.\n\n2. **Comparison to InfAlign [2].** Please include an empirical and conceptual comparison to **InfAlign** [2], clearly outlining the methodological differences and where each approach is expected to excel or fail.\n\n3. **Soft-BoN vs. BoN vs. yours.** As noted in [1], BoN can over-optimize; **Soft-BoN** is proposed as a mitigation. How does **Soft-BoN** perform relative to your method—both theoretically (regret guarantees, assumptions) and empirically?\n\n4. **Asymptotics in Theorem 4.2.** Using Theorem 4.2, in the limit $(N\\\\to\\\\infty)$ the regret for a non-zero error appears to approach a **constant independent of (N)**. Please elaborate on the mechanism, the constant’s dependence on problem/reward parameters, and its practical implications.\n\n5. **Reward calibration.** Is the **reward function calibrated**—either in the formulation (assumptions/guarantees) or in experiments (procedure, metrics)? \n\n6. **“Mathematical equivalence.”** When you write “select (k) answers (up to **mathematical equivalence**) with highest frequency,” what exactly constitutes equivalence (e.g., algebraic identity, numerical equality within tolerance, format-invariant parsing)? Please define the criterion and how it’s implemented in experiments.\n\n**References**\n\n[1] Gholamali Aminian, Idan Shenfeld, Amir R. Asadi, Ahmad Beirami, Youssef Mroueh. *Best-of-n through the smoothing lens: KL divergence and regret analysis.* arXiv:2507.05913, 2025.\n\n[2] Ananth Balashankar et al. *InfAlign: Inference-aware language model alignment.* ICML, 2025.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tAesXLoaB9", "reviewer": "Reviewer_JFFa", "summary": "This paper studies inference-time scaling under the Pass@k framework, where the algorithm may generate up to $N$ responses but submit at most $k \\leq N$ of them. In this paper, the evaluation of algorithms focus on (1) the scaling of regret in $k$ and (ii) a notion called \"scaling-monotonic\", i.e. whether the algorithm degrades as $N$ grows (when the reward model is accurate.) \n\nThe authors show the limitations of two common baselines: (Weighted) majority voting suffers a constant regret lower bound even when the reward model is perfect; also, Best-of-N (BoN) admits a lower bound violating scaling-monotonicity. As a fix, they propose an algorithm called *Best-of-Majority (BoM)*, which can be viewed as a \"combination\" of both: BoM (1) first filters to responses whose empirical frequencies are high (a majority-style step), and then (2) selects the top-$k$ by reward (a BoN-style step). Then they show that BoM achieves an upper bound matching the minimax lower bound they show for the setting. Crucially, BoM scales with $k$ (in addition to an optimal estimation error of the reward) and satisfies the scaling-monotonicity.\n\nEmpirically, they compare BoM against majority voting and BoN. The experimental results show that BoM generally outperforms or matches the baselines -- the plots versus $k$ show BoM consistently better on MATH-500 and competitive on GSM8K/AIME24, especially for small $k$.", "questions": "Could you respond to the points listed in the Weakness section? (e.g. discuss how sensitive the guarantees are when there are several maximizers or when rewards are flat within a small margin, etc.)", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper is well-written, with a clear structure and flow of logic. It isolates the scaling-monotonicity (which is defined formally) as a target property and then set it as an explicitly goal of algorithms. By showing how baseline approaches fail this goal, and the present a lower bound and a simple algorithm that matches it, the line of work feels convincing and clean. \n\n- I think the story that motivates the construction of the BoM makes good sense: Indeed, an ideal algorithm should balance the considerations on both uncertainty and the reward. For the former, BoM uses the empirical frequencies of generated responses to approximate the probability, and for the later, BoM then query the reward model on the surviving candidates.", "weaknesses": "(I should probably stress that the topic of this paper is not my area. Thus I may not have the expertise to fully assess e.g. the novelty and relevance of this work.)\n\n- The uniqueness-of-optimum assumption feels restrictive. One can easily think of many tasks that admit multiple equally good answers (or near-ties). It seems that several bounds and the neat identification of $\\mathcal{C}^*$ relies on the uniqueness assumption.\n\n- It seems that BoM needs a coverage threshold that depends on $\\mathcal{C}^*$, which can be unknown and may be badly misestimate. This paper does not offer, e.g. a data-driven estimator or a quantification of how misspecification affects regret or monotonicity.\n\n- The empirical scope feels a bit narrow: all datasets are math/verifier-style. Given this, I'm not sure whether the empirical results are representative on a broader set of tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kMgNRIK12W", "reviewer": "Reviewer_kb59", "summary": "This paper studies the Pass@k inference scaling problem for large language models (LLMs), where a model can generate $N$ candidate responses and select up to $k$ outputs, and only the best of them is used to compute the regret. The authors observe that widely used inference strategies for Pass@1 inference, such as majority voting and Best-of-$N$ (BoN), fail to exhibit desirable scaling behavior as $k$ and $N$ increase. \n\nTo address this, they propose a new inference strategy, Best-of-Majority (BoM), which ensures a $O(\\epsilon_{\\text{opt}} + \\sqrt{C^{*}\\epsilon_{\\text{RM}}^2/k})$ regret bound. Here, $C^\\star$ is the coverage constant, $\\epsilon_{\\text{RM}}$ is the estimation error of the reward model, and $\\epsilon_{\\text{opt}}$ is the estimation error of reward at the optimal response. They also provide a matching minimax lower bound for any Pass@k inference strategy. Importantly, BoM is shown to be scaling-monotonic, meaning its performance does not degrade with larger sampling budgets $N$, which separates the.\n\nEmpirically, the method is validated on GSM8K, MATH-500, and AIME24, where BoM consistently outperforms or matches the baselines.", "questions": "Please refer to the 'Weaknesses' section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Strong theoretical foundation: The authors show strong lower bounds on the regret of previous methods of majority vote and BoN, providing insightful explanations on why they do not benefit from the scaling law. \nThe construction of the BoM method, which combines the advantages of the two previous methods, is simple and intuitive. They also show matching lower and upper bounds to demonstrate the minimax optimality for BoM.\nThe theoretical model and analysis are novel.\n\n2. Good empirical validation: Experiments on various datasets align well with theory and convincingly support the claims.", "weaknesses": "Practical relevance: \n\ni. It is slightly unclear from the text the broader impact of the Pass@k inference problem. The authors do mention the usage of Pass@k alignment in training LLMs in Section 2, but it could be beneficial to discuss its application in LLM inference or generation.\n\nii. In the paper, the BoM method is proved to be scaling monotonic, which is emphasized as a major separation from previous methods. From my understanding, this property guarantees that the error should converge to zero eventually as $N$ increases. However, in the experiments, the BoM method doesn't seem to benefit from this property, e.g., in Figure 2(a), the accuracy decreases at first, and in Figures 2(b) and 2(c), the accuracy is always $0.7$. This seems to suggest that we shouldn't use large $N$ in practice anyway. Is it because of the inherent error from the chosen reward model, i.e., $\\epsilon_{\\text{RM}}$, or is $N$ not large enough?\n\nClarity:\n\ni. The authors could provide more explanation of the intuition of the technical terms, e.g., the coverage constant, the definitions in Assumption 3.1 and Assumption 3.2, especially for audiences with diverse backgrounds.\n\nii. In Theorem 5.1, the parameter $\\alpha$ of the BoM algorithm is chosen to be $\\Omega(1/C^*)$. In the experiment, the authors set $\\alpha = 0.015$ for $N = 100$ and $\\alpha = 0.005$ for other choices of $N$. I would assume the coverage constant is hard to compute in practice, but the authors do not explain the reasons for their choices of $\\alpha$. Why are different parameters needed for different $N$? Also, I'm curious about how the accuracy varies with different $\\alpha$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iX424VHhcn", "reviewer": "Reviewer_Df6F", "summary": "The paper considers scaling laws for inference: A model is required to output $k$ responses $y$ to a given prompt $x$, and the regret, compared to the optimal response, is measured according to the best one in this set of $k$ responses. In this paper the model is allowed to output a total of $N$ responses, and pass chosen $k$ ones to evaluation, based on a given estimated reward model. Thus, $N$ represents the computational cost of inference. A minimax lower bound on the regret as a function of $k$ (as well as the reward model estimation error) is stated, and the regret of two previously proposed algorithms (used in practice) Majority voting and Best-of-$N$) is analyzed. Both these algorithms are shown to be non-minimax. An algorithm (Best-of-Majority, BoM) is proposed which is shown to be minimax optimal with respect to $k$. The main idea of the algorithm is that even if a large number of responses $N$ are generated, they should be filtered to the most frequent ones, which are also assumed to be the ones in which the reward model is most reliable.", "questions": "1) Line 82 - We further “introduce a formal definition of scaling-monotonicity”: What is exactly the contribution of this paper to this definition, beyond Huang et al. 2025). Line 188 - “we introduce the reference policy..”: The same question. 2) Could you explain the dependence on $C^{\\star}$  and why it is essential? Under Assumption 3.2, $C^{\\star}$ is the inverse of the probability of the reference policy at the optimal response. Isn't it possible to slightly mix $\\pi_{ref}$ with a uniform distribution over the response alphabet, to make $C^{\\star}$ effectively a constant? \n\n3) Line 204 – “sufficiently many samples are observed” is unclear: Samples for reward estimation or responses?\n\n4) Line 252- “each receiving higher probability under $\\pi_{ref}$”: Higher than what?\n\n5) “Moreover, our earlier analysis reveals complementary strengths of these methods...” - this is unclear since the analysis thus (Theorems 4.1 and 4.2) only focused on impossibility bounds. \n\n6) In (B.4), I would propose to add a citation for the Chernoff bound for negatively correlated random variables. \n\n7) In the proof of Theorem B.2, what is meant by “the idea of averaging hammer”", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper derive theoretical bounds for a timely problem of inference scaling laws. \n\n2) Two practical algorithms are analyzed, which are shown to be sub-optimal, and a new one is proposed, which is established to be minimax optimal.", "weaknesses": "1) The main goal of the paper is to study the trade-off between the computational cost of inference, as expressed by $N$ and the regret. From this aspect, it is unreasonable that both the upper for BoM and the minimax lower bound do not depend on $N$, and thus do not capture this trade-off. \n\n2) Theorem 5.1: The result does not cover the regime $k\\lesssim N\\lesssim C^{*}(x)$. \n\n3) The algorithms and analysis are based on empirical counts over the response alphabet $\\mathcal{Y}$. It is not obvious how the performance scales with this alphabet size. \n\n4) The proposed algorithm requires the knowledge of $C^*(x)$ in order to make sure that $N$ is large enough. Similarly, the algorithm requires knowledge of a lower bound on $\\epsilon_{RM}$ which is somewhat cumbersome since the reward model is designed to have a small error.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)