Provable Scaling Laws for the Test-Time Compute of Large Language Models
Authors: Yanxi Chen
Xuchen Pan
Yaliang Li
Bolin Ding
Jingren Zhou
Venue: NeurIPS 2025 poster ()
Keywords: test-time compute
inference scaling law
large language model
Primary area: general_machine_learning

Abstract: We propose two simple, principled and practical algorithms that enjoy provable scaling laws for the test-time compute of large language models (LLMs). The first one is a two-stage knockout-style algorithm: given an input problem, it first generates multiple candidate solutions, and then aggregate them via a knockout tournament for the final output. Assuming that the LLM can generate a correct solution with non-zero probability and do better than a random guess in comparing a pair of correct and incorrect solutions, we prove theoretically that the failure probability of this algorithm decays to zero exponentially or by a power law (depending on the specific way of scaling) as its test-time compute grows. The second one is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents, rather than eliminated upon loss to a single opponent. Under analogous but more robust assumptions, we prove that its failure probability also decays to zero exponentially with more test-time compute. Both algorithms require a black-box LLM and nothing else (e.g., no verifier or reward model) for a minimalistic implementation, which makes them appealing for practical applications and easy to adapt for different tasks. Through extensive experiments with diverse models and datasets, we validate the proposed theories and demonstrate the outstanding scaling properties of both algorithms.

Provable Scaling Laws for the Test-Time Compute of Large Language Models
Yanxi Chen'
Xuchen Pan" Alibaba Group
Alibaba Group
chenyanxi cyxealibaba-aa inc..ii...c.c com
panxuchen. prrnucchen.xxcellbbbbee aaaabaallbbbaaae. inceaa--nnccoom com
Yaliang Li Alibaba Group
Bolin Ding
Alibaba Group
yaliang. wwllllillaabainnnnn inabba-inc.oomm com
bolin deiinndig@allibe wawpggglllbbbaaaae inca com
Jingren Zhou
Alibaba Group
j jingren zhou@al www.bbbbbabbc.. com
Abstract
We propose two simple, principled and practical algorithms that enjoy provable scaling laws for the test-time compute of large language models (LLMs). The first one a two-stage knockout-style algorithm: given an input problem. it first generates multiple candidate solutions, and then aggregate them via knockout tournament for the final output. Assuming that the LLM can generate a correct solution with non-zero probability and do better than random guess in comparing a pair of correct and incorrect solutions, we prove theoretically that the failure probability of this algorithm decays to zero exponentially or by a power law (depending on the specific way of scaling) as its test-time compute grows. The second one is two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents, rather than eliminated upon loss to single opponent. Under analogous but more robust assumptions, we prove that its failure probability also decays to zero exponentially with more test-time compute. Both algorithms require a black-box LIM and nothing else (e.g., no verifier or reward model) for minimalistic implementation, which makes them appealing for practical applications and easy to adapt for different tasks. Through extensive experiments with diverse models and datasets, validate the proposed theories and demonstrate the outstanding scaling properties both algorithms.
Introduction
Despite the astonishing advancements of large language models (LL.Ms) in the past few years, they still face challenges with reliability and stability. This hinders their applications in high-stakes scenarios where a problem need to be solved with success probability 99.9% rather than 90%. Similarly, an LLM-based agentic workflow that involves solving many sub-problems, each of them need to be solved with near near-perfect success rate, since a single error in the process can lead to an incorrect final output. In these and many other similar scenarios, one is willing to boost the success probability by spending more test-time compute on LLM inference. One category of methods for this purpose include iterative approaches like generating sequential chain of thoughts
"qqual contributions.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

37 or self-refinement [6, 8 50, 51]. Another category, which is the focus of this work, about repeatedly sampling multiple solutions and then aggregating them for the final output; examples include best-of-N sampling S 2 36 55 K
43 18 29 53
7
majority voting [4] 3 21, among 54 These two categories are complementary and often used together for the
others [3 15 22
best performance 35
12 28)
Goal of this work. We aim to augment the toolkit of LLM inference scaling with practical algo- rithms and foundational insights. Throughout this work, we consider a generic problem formulation where an conceptual simplicity, we evaluate any solution with a binary metric indicating whether it correct or incorrect. We desire algorithms that enjoy provable inference scaling laws in the following sense:
algorithm is given an input problem and asked to output solution. For
Definition 1.1. We say that an LLMM-asee algorithm enjoys a provable inference scaling law for a specific input problem, if its success probability (with respect to the inherent randomness of the algorithm) in returning correct solution to the problem can be boosted arbitrarily close to 100% as its test-time compute grows, provided that certain clearly identified assumptions about the problem and the LLM(S) being used are satisfied.
Limitations of existing methods. Strong baseline methods widely adopted in practice may fail (in theory and practice) to achieve this goal, even if a single LLM call already solves the input problem correctly with high or moderate success probability. For example, best-of-N (BoN) sampling with an imperfect verifier might suffer from performance decay as the number of sampled solutions grows because, as explained in Section 5.1 of [5), "the benefits of search are eventually outweighed by the risk of finding adversarial solutions that fool the verifier", Indeed, prior works highlighted that developing test-time scaling methods that do not rely on perfect verifiers remains an important direction for further research 2 (36. Majority voting, another strong baseline, might fail for different reasons: even the LLM has moderate probability, say 45%, of generating a correct final answer, the success probability of majority voting will actually converge zero as the number of samples grow there exists an incorrect final answer that single I.LM call generates with probability 46% 3
Main contributions. In pursuit of provable inference scaling laws, we propose a two-stage knockout- style algorithm that first generates multiple candidate solutions, and then select one via a knockout tournament where pairwise comparisons among the candidates are conducted. We prove theoretically that its failure probability decays zero exponentially (Theorem 2.33) or by a power law (Theorem 2.44 with respect to the total number of LLM calls, depending on the specific way of scaling. These guarantees rely two assumptions:
(1) the LLM can generate correct solution with non-zero probability, and (2) the L.M can do better than a random guess in choosing the right winner between any pair of correct and incorrect solutions.
We further propose a two-stage league-style algorithm that also enjoys a provable scaling law. Unlike the knockout-style algorithm that eliminates a candidate upon loss to a single opponent, the league- style algorithm evaluates each candidate by its average win rate against multiple opponents. We prove that its failure probability also decays zero exponentially (Theorem 3.3 as its test-time compute scales up. under the technical assumption that there exist correct solutions whose average win rates against a distribution of opponents are higher than that of any incorrect solution.
Both proposed algorithms require black-box I.LM and nothing else (e-g., no external verifier or reward model) for minimalistic implementation, which makes them appealing for practical applications and easy to adapt for different scenarios. Our practical implementations are efficient and scalable, with support for parallel and distributed computation. While the technical assumptions in our theories might seem strong from a practical perspective, our empirical results confirm that the proposed algorithms - developed based on the theoretical insights indeed perform well and demonstrate outstanding scaling properties across diverse LLMs (Llama3. 1, Qwen2. 5, GPT-4o, QwQ-32B and datasets (GPQA. MMLU-Pro MATH-500).
A two-stage knockout-style algorithm
This section studies the following two-stage knockout-style algorithm for solving input problem:

---

1. Generation. We first generate N candidate solutions, which can run in parallel. In situations where the final answer contains only a few tokens (e.g., for multiple-choice problems or math calculation), we require that each solution contains a thinking process, which can be elicited by chain-of-thought (CoT) prompting 4 18 for example; such information can be useful for enhancing pairwise comparisons in the next stage.
2. Aggregation. We aggregate the candidate solutions via a knockout tournament. At each round, the candidates are grouped into pairs randomly, and each pair of candidates are compared for K times. The winner of each pair is the one that is favored for more than K/ / times; ties are broken randomly. Only the winners will move on to the next round. The final-round winner at the end of this tournament will be the final output of the algorithm.
Figure visualzess this process, For a mini- malistic implementation, both stages can be executed with a single black-box LLM (or an ensemble of multiple LLMs). We next introduce some formal notations, followed by our analysis for both success probabil- ity and computational efficiency [16] 4 of the proposed algorithm, to be presented in Sections 2.1 and 2.2 respectively.
Winner
Candicate 2
Winner
Gandicite
Winner
Candicato
Pairers comparioon for Krmees
Winner output)
Imput problem
Candicate 5
Winter
Winner
Candicate 7
Formal notations. Let MMga and Mcomp denote the probability distribution of the out- put of one LLM call for generating solu- tion and for comparing a pair of solutions respectively. Given an input problem x, the proposed algorithm first samples N inde- pendent candidate solutions y1..... M/N ~ (z)n(zr) during the generation stage. Then, for each pair of candidates (y.3') encountered in the knockout stage, the algorithm samples K independent comparison results Ti,.... TK ~ Moomp (1.)) y. y'), and identifies the candidate that is favored by the majority of beekk as the win- ner. Sampling from Maen and Mcomp throughout the algorithm is the sole source of randomness in the following amalysis of success probability. The randomness within Mgen and Mcomp can originate from LLM decoding with non-zero temperature, the randomized choice prompting method or LLM backend for each LLM call, among others.
Candicate 8
candidate solutions
Stage apgragate knodiout
Figure I: A visualization of the proposed two-stage knockout-style algorithm, with N = 8 in this example.
2.1 Analysis of success probability
Our theoretical guarantees for the propesed algorithm rely on the following assumption about the input problem under consideration and the LLM(s) being used.
Assumption 2.1. For the input problem J, there exists Pgen > 0 such that
P Py~Myr(*) (y is a correct solution) 2 Pgen > 0.
In addition, there exists Peomp > 0.5 such that, for arbitrary pair of candidate solutions (y. v²) where one of them is correct and the other is incorrect, it holds that
IP ProcMomp(...s9)) (r identifies the right winner) 2 Peomp > 0.5.
In other words, we assume that the LLM generate correct solution with non-zero probability, and do better than a random guess in comparing a pair of correct and incorrect solutions. Here, Pgen and Peomp are defined for specific input problem, not for distribution of problems Remark 2.2. While this assumption seems minimal and natural at first glance, its requirement that Peomp 0.5 holds for any pair of correct and incorrect solutions renders it somewhat restricted and non-robust. This will motivate our development for an alternative algorithm and its provable scaling law under different technical assumptions, to be elaborated in Section
benchmark.
Scaling up both and K. As N (the number of initial candidate solutions) and (the number of times that each pair of solutions involved in the knockout stage are compared) grow, it becomes
3

---

more likely that (1) there exist initial candidate solutions that are correct ones, and (2) they tend to be selected as the winners in pairwise comparisons against incorrect solutions, which together lead to the correctness of the final output of the algorithm. This is formalized in the following theorem.
Theorem 2.3. If Assumption 2.7 holds for the input problem, then the probability that the proposed knockout-style algorithm returns an incorrect final output decays zero exponentially with respect to the hyperparameters N and K:
P(faiture) - S (1 [Pen)) NN + [log, Ne
2K (Powa 0.5)²
proof can be found in Appendix B.1
Another way interpret this theorem is follows: for
targeted success probability 1 - 8 (which can be arbitrarily close to as the failure probability d > 0 approaches zero), it suffices have
2 2 N1
N
log
8 and
K
Peoom 0.5)² log
(I)
Pgen
In other words, N and K have logarithmic dependence on 1/6, and linear dependence on 1/Ppen and 1/ (Peamp 0.5)² respectively.
Scaling up N while K is fixed. Although Theorem 2.3 guarantees an arbitrarily small failure probability, requires to be sufficiently large, depending on the value Peomp that might be unknown priori in practice. To resolve this, we provide alternative theorem suggesting that scaling up alone sufficient, even when is a fixed constant and thus there is still a good chance that the wrong winner is identified when comparing specific pair of candidates.
To streamline the statement of our theorem, we introduce the notations Meomp, and Peump. which generalize Meump and Peomp that appear in Assumption 2.1 Let Muump, K denote the probability distribution the comparison result obtained with K independent LLMM calls followed by majority voting (with ties broken randomly). Then we have
P ProMounp (1.N))) identifies the right winner) 2 Peomp, K >> 0.5,
(K) ΣE [P=(K/2] (e) )CCompp Ek 2t=K/2+1 (2)mmmp Poomp) K-E + 2 Pcompp)
where Poomp.K K K
Poomp) K-E P if K is odd, and Poomp, K K K/2 Poomp) K222 if K is even.
Theorem 2.4. Suppose that Assumption 12. holds and N is power of 2. Let ps be the prob- ability that a candidate solution the i-th level of the knockout lournament is correct, where N.Then
i i= 1.1.1..... 1=0.1....,log log, NP
Then Pgen and
Pi+1 2 Pi (2pommp, K
1)(p: pt) for
log2 N 1
Consequently, the success probability of the overall algorithm, namely Plog, N. converges I as N grows; for any 0 < 8 < 0.5, one has Plog, N 2 11-6 5 as long as
log maxx 2pan 1})
log 25
log2 N log (1 + (Peomp. - 0.5)) + log (Poomp, K 0.5))
proof can be found Appendix B.2 The linear relationship between log, N and 10g(1/8) reveals power-law relationship between the failure probability ö and the number of candidates N.
2.2 Analysis of computational efficiency
The minimalistic implementation of the proposed knockout-style algorithm starts by generating N candidate solutions with N LLM calls that can in parallel. Since the number of candidates is reduced by half at each round of the knockout tournament, there is at most [log, N rounds total. For notational convenience, let assume that N is power of 2 for the rest of this analysis. At the
In our notations, the zeroth level of the tournament contains initial candidates, the first level contains N/2 winners after the first round of pairwise comparisons, and so on. All candidates within the same level of the knockout tournament have the same probability of being correct one, due to their symmetric roles.

---

i-th round, there are N/2' pairs of candidates, and each pair need K comparisons; thus a total of K N/22 LLM calls are needed, which again can be parallelized.
In sum, the total number of L.MM calls required by the two-stage algorithm N + K x Σ, N/2 < (K + 1) x N, whereas the end-to-end latency, if sufficiently many machines are available, is merely Teen + +ogg(NN x T comp, where T and Tomp represent the latency of one LLM call for generating candidate solution and for comparing pair of solutions, respectively.
3 A two-stage league-style algorithm
In this section, we propose a two-stage league-style algorithm that also enjoys provable inference scaling law, under technical assumptions that are analogous to but more robust than those required by the knockout-style algorithm.
Algorithm 1 The proposed league-style algorithm
Input:
the problem σ.
Generate N candidates 3/....., MN MMen (r).
2. Compare each candidate ys against K random oppo- nents and estimate its average win rate μú, by Eq. 2
Output: the candidate with index ī arg max; jus.
The proposed algorithm. To begin with, we generate N candidate solu- tions ,...... UN (z) as before. Then, for each candidate with index [N], we randomly sample K opponents with indices o.. ((() E [N]} uniformly and with replacement, conduct one independent pairwise comparison against each opponent, and obtain the responses ri( ~ Meamppas yis No.(1)) for [K].
The average win rate of each candidate y; is then estimated by
1 K
Σ JE(K
where ((r(()) Vo- Mo,())) denotes the score assigned, based on rj()), to the candidate y, in its comparison against (o.( c.g., I for a win, for loss, and 0.5 for a tic. Finally, the candidate with the highest average win rate ñi; is chosen (with ties broken randomly) as the output of the algorithm. See Algorithm for a summary of this method.
Regarding computational efficiency, the proposed algorithm requires N fully parallelizable LLM calls for the generation stage, and N K fully parallelizable LLM calls for the aggregation stage.
Analysis of success probability. For a solution y, we denote its average win rate against MMen by
My == Ey
Monn p(r, (r. y. v/).
Our key assumption is presented below.
Assumption 3.1. For the input problem æ. there exist Pes > 0, A > O, and a way of dividing the set )' of all possible solutions into three disjoint subsets y V2 U Umme (where "cs". "ew" and "inc" stand for sourect-and-srropg
"correct-but but-weak""""" and "incorrect", respectively), such that
P PymMMa(ss) E Va) 2 Pes 0 and
min My VEV.
max My A A>0 0. DENi
In other words, we assume that the LLM can generate, with non probability, correct solution whose average win rate against Mgen is higher than that of any incorrect solution; such a solution is called correct-and-stront by our definition. We also allow the existence of correct-but- weak solutions, imposing no assumption on their average win rates. Note that Assumption 3.1 can be tolerant of systematic errors by L.MSs in comparing certain pairs of candidates, i.e., may still hold true when there exist correct solution y and incorrect solution y/ such that Eew (2. (r. y.y") < 0.5, whereas Assumption 2.1 fails in such cases.
Remark 3.2. One limitation of Assumption 3.1 is that it can be broken by an adversarial incorrect solution whose average win rate is unusually high, similar to the failure mode of best-of-N sampling discussed in Section I Nonetheless, on the presumption (backed by common practice and extensive empirical evidence) that pairwise comparison is more accurate and reliable than individual point-wise verification, we might safely say that Assumption 3. conceptually weaker and more robust than the condition required by BoN (c.g.. perfect point-wise verifier) for provable inference scaling laws.
5

---

Intuitively, if Assumption 3.1 holds true and the hyperparameters N and K are sufficiently large, then with high probability, (I) there exist initial candidates that are correct-and- and-strong solutions, and (2) The is an accurate estimate of My, for each i E [N]. These conditions together lead to correct final output of the algorithm. We formalize this intuition in the following theorem.
Theorem 3.3. If Asssumpttin 3. holds for the input problem, then the probability that the league-style algorithm (with hyperparameters N and K) returns an incorrect final output is bounded by
P(failure) S (1 - Pa)) + 2NN - 2N
This theorem, whose proof can be found in Appendix B.3, ensures that the failure probability of the lcague-style algorithm decays zero exponentially with respect N and K. Another way to interpret this theorem is as follows: to guarantee success probability 1 - 6, it suffices to have
N Z max
log
8
log
6NN (GN) 8
+1
and K Z
8
log
6N
Pos
8
A
A
8
That is, N and K have logarithmic dependence on 1/6, and linear dependence on m/x(s/Pes. 1/A²} and I/ (up logarithmic factors) respectively.
Remark 3.4. The provable success of the knockout-style algorithm relies on Assumption 2.T while that of the league-style algorithm relies Assumption 3.1 Although the latter is conceptually more robust than the former, we note that neither assumption is strictly weaker than the other (and thus both algorithms have their unique values). In other words, there exist scenarios where Assumption 2. holds true while Assumption 3.1 does not, and also scenarios where the reverse true. Interested readers may refer to Appendix for some minimal examples.
Experiments
We conduct empirical studies to validate the efficacy and scaling properties of the proposed algorithms, while bridging their practical performance with the theories developed in previous sections.
and MATH- 500 (26). GPQA consists of over 1000 graduate-level multiple-choice questions splitted into three categories ("main". "diamond" and "extended"), all of which are used in our experiments. MMLU- Pro contains 14 categories of multiple-choice questions, some of which require advanced reasoning while others are more knowledge-focusee
Datasets. We use three datasets for our experiments: GPQA 33 MMLU-Pro 22
Due to limited computational resources, we use a randomly sampled subset of 100 questions for each category of MML U-r in our experiments, which leads to a total of 1400 questions; we refer to this subset as MMLU-Pro-S throughout this work. MATH-500 a subset of 500 problems from the MATH dataset introduced in [22]. Due to space limitations, we focus mainly on GPQA in this section, deferring empirical results for MMLU-Pro-S and MATH-500 (as well as supplementary results for GPQA) to Appendix D
Implementations. We use Llama3. 1.taa.....70BB. Instruutt (Llama3. 1 for short) 24 and Qwen2.5-72BB
Instruct (Qwen2.5 5 for short) 49 in our experiments, as well as a Mixed option that uses a mixture during the generation stage, half of the initial candidates are sampled by Llama3. 1 and the other half by Qwen2. 5; similarly, when pair of candidates are compared for multiple times during the aggregation stage, half of them are done by Llama3. 1 and the other half by Qwen2.5 5. The rationale is that the capabilities of different LLMS can be complementary to some extent, and thus using a mixture of them can make it more likely that Assumptions 2.1 and [3. hold truef) Other models considered in our experiments include QwQ-32B [31]. long-CoT reasoning LLM, and G4T-4o [0), a proprictary API-based LLM; due to high computational or monetary costs, they are tested only on
of both LLMs 39 54 13:
for smaller range of N.
TTo formalize this intuition, consider minimal scenario with two LLMs denoted by Mj and M2. and two problems denoted by æ and z2. Suppose that M, effective for the first problem æ1 (with Pgn 0.2 and Peomp 0.7) but ineffective for Ia (with Psen
and Poomp 0.5), while the reverse holds true for M2. When either LLM is used alone, only one problem satisfies Assumption 2.1 However, when a mixture of two LLMs is used, both problems now satisfy Assumption 2. with Paen
(0 + 0.2)/2 = 0.1 > 0 and
Peomp (0.5 + 0.7)/2 0.6 0.5, and thus can be solved by algorithm.

---

GPQA
GPQA: diamond
LLaama33 (KO)
UJmm331 (MV)
OwO (KO) - QwO (MV)
Figure 2: Accuracy ver- sus the number of ini- tial candidates N for the knockout-style algorithm (KO), as well as for ma- jority voting (MV), strong baseline widely adopted in practice.
OwenZ,5 5 (KD)
Qwenn2.5 (MV)
0.75
GPT-4o (KO) GPT-4o (MV)
0.575
Nixed (KD)
Mixed (MV)
0.70
0.550
0.65
0.500
0.60
0.475
0.55
0.50
0.425
16
N
We leverage zero-shot chain-of-thought prompting [8] for both generation and aggregation stages of the proposed algorithms. Unless specified otherwise, for the knockout-style algorithm, we fix K for Llama3. 1/ Qwen2. 5/ Mixed, and K 2 for GPT-4o/ QwQ-32B; for the league-style algorithm, we consider a round-robin [46] version it, with K = 4 comparisons conducted between each of (2) pairs of initial candidates. To make the proposed algorithms efficient and scalable practice, we implement them based on AgentScope [9]. multi-agent framework that supports parallel and distributed computatior Further implementation details can be found in Appendix D.1
In our experiments, we consider a solution as correct one if its final answer matches the ground -trut answer, and use accuracy (i.e., the proportion of correctly solved problems) as the performance metric for running (deterministic or randomized) algorithm once on dataset. This metric is, in expectation, equivalent to the mean success probability of the algorithm on the dataset.
4.1 Results for the knockout-style algorithm
Efficacy and scaling properties. Figure 2 confirms that the accuracy of the knockout-style algo- rithm improves with N for all LLMs on GPQA or GPQA-diamond. For example, the accuracy of Mixed improves by 10 points (from 45% to 55%) as N scales to 64, and the accuracy of QwQ-32B improves by 12 points (from 60% to 72%) N scales to 16. We also observe that Mixed consistently outperforms Llama3. 1 and Qwen2.5 5 as N gets larger, which confirms the previously explained rationales for using a mixture of different LLMs.
Comparison with majority voting. Figure includes results for majority voting, a strong baseline widely adopted in practice. It is observed that, for all L.M. backends (except for Llama3. 1), the knockout-styl algorithm consistently achieves higher accuracy when given the same number of initial candidates. Caution should be taken here: recall from Section [2.2
that the knockout-style algorithm takes (K + 1) x N LLM calls for solving one problem, i.c., x N for Llama3, 1/ Qwen2.5 5/ Mixed and 3 x N for GPT-4o/ QwQ-32B, whereas majority voting only requires N LLM calls. Nonetheless, the knockout-style algorithm still has advantage when this taken into account, e.g., its accuracy at N 8 (resp. 4) is higher than that of majority voting N 64 (resp. 16) for Mixed (resp. Q=Q-32B). Moreover, based on the trends shown in Figure 2] it is most likely that for majority voting, further increasing N will bring limited performance gains [3] and result in converged accuracy lower than what can be achieved by the knockout-style algorithm.
But the theorems promise 100 % accuracy, don't they? The results in Figure arre indeed consis- tent with the theorems developed in Section 2.1] which guarantee that the knockout-style algorithm can achieve an arbitrarily high success probability for any input problem satisfying Assumption 2.7 namely Paen > 0 and Peomp > 0.5. For a problem that does not, is still possible that the algorithm has chance of solving it correctly (since Assumption 2.1 is a sufficient condition for its success and might not be necessary), but there is no formal guarantee. Consequently, for benchmark or a distribution of input problems, denoted by DD our algorithm is guaranteed to achieve accuracy at least Pa-D(( (x satisfies the assumption) as its test-time compute grows. Indeed, a benchmark contains an extremely difficult problem, e.g., "solve the P versus NP problem", then any test-time scaling method will fail achieve 100% accuracy on such a benchmark.
'Our implementations can be found at https http://ttwaaaaoooceeccc////////a http:///wwaa.xpppe//oo//oeeeebba wwwpppppproaaeeeeeeeeeeppep
pxc/paper_provatee hatpee/eeaaapplepppeeeeeeeeeeeee

---

To further bridge the empirical results with theories, let us start by estimating the param- eters Pgen and Promp in Assumption 2. For each problem, we define Pgen as the propor- tion of the N = 64 initial candidate solutions with a correct final answer, which serves as a good proxy for Pgen. To find proxy for Poomp. we define Poomp by picking all LLM calls for comparing a pair of correct and incorrect so- lutions throughout the knockout tournament, putting higher weights sults from later rounds of the tournament, and taking the sum of the weights of comparisons that identify the right winners
GPQA
GPQA: subset
1.0
Klgorp 2 0.5] 620
0.9
Poma
Accuracy
0.5
0.7
KO 10.5)
MV (0.5
KO 10.8]
(06)
N0 51
405
KO (0.7)
(0.7)
0.0
0.5
1.0
0.5
2
4
0 16 32 64 120256
418 p0
Pree
a1 -1]
N
the comparison re-
Figure 3: Left: the distribution of GPQA problems, characterized by Pgen and Peomp that are estimated with the knockout-style algorithm (Mixed). Each problem is represented by a circle if it is solved correctly at N = 64, and by cross otherwise. Right: accuracy versus N for the knockout-style algorithm and ma- jority voting (both with Mixed), on filtered subset of problems satisfying 0 < Pgen < and Promp > where E {0.55 0.6, 0.7). The values of accuracy are calculated with new trials of the algorithm, thus statistically independent of Pgen and Peomp.
Figure in Appendix D.2 characterizes the distribution of GPQA and MMLU-Pro-S problems in terms of Pgen (the X-axis) and Peomp (the Y-axis); one such plot can also be found in Figure [3 (left). On the top half of each scatter plot are problems with Poomp > 0.5, most of which are solved cor- rectly by the kttyk algorithm and represented as circles. These include some problems with small Pgen- for which the knockout stage successfully identifies a correct candidate even though the initial candidates are mostly incorrect. We further observe from Figure 7 that,
compared to L1 ama.3.3. 1 and Qwen2.5, the Mixed option achieves pgen > 0 and Poomp > 0.5 for a
larger proportion of problems, which explains its superior accuracy shown in Figure 2
To further
consolidate this analysis, we pay special attention to the subset of problems satisfying 0
< <Pgen < 1
and Peomp >> 0.5. These are approximations for the conditions stated in Assumption 2.1 except that
those easy problems with Pgen = 1 are excluded. We run new. independent trials of the knockout-style algorithm (Mixed) on this subset. Figure (right) confirms that significant improvements in accuracy (from 55% to 80%) can be achieved by scaling up N, which matches what our theories predict. Unsurprisingly, the scaling curve still plateaus eventually (since Peomp > 0.5 is merely a proxy for Poomp 0.5), and tightening the filtering condition (e.g., Poomp > 0.6 or 0.7) will bring it closer to 100% accuracy.
Intuitions: when does Assumption 2.1 hold?
MMLU-Pro-S: engineering
MMLU-Pro-S phil asophy
Interestingly, we observe that the scaling prop- erties of the algorithm vary across different cat- egories of MMLU-Pro-S, and also across LLM backends. For instance, Figure performance scales well for all of Llama3. 1/ Qwen2. 5/ Mixed in the "engincering" category, while the scaling of amaa.3... 1 outperforms the other two options in "philosophy". An intuitive explanation is that, for a reasoning-foctte focused task like "engineering". LLMs can compare the rea- soning processes of two candidate solutions side by side, which provides additional infor- mation compared to generating or verifying an individual solution, and thus leads to large value of Peomp and accurate comparison results. In contrast, for a knowledge-heavy task like "philosophy",
0.70
0.70
.8 Lilamaaaa 3.1
--weed
ACcUrTOr
0.66
that the
0.50
Ulmm33
0.64
0.55
Owenn23
Figure 4: Accuracy versus N for the knockout-style
algorithm on two categories of MMLU-Pro-S.
'The rationale for weighting the comparison results is explained as follows. In the early rounds of the knockout tournament, the comparison result between correct-but-weal candidate and an incorrect candidate cause negative bias in estimating Peomp: similarly, correct candidate might have a very high win rate against an opponent that not only incorrect but also very weak, which can cause a positive bias estimating Peomp- In contrast, the correct or incorrect candidates that survive the early rounds of the knockout tournament tend to be stronger ones, which make the comparison results among them (in later rounds of the tournament) more reliable and meaningful for the purpose of estimating Peump.
8

---

GPO4
GPCA: subset
GPGA
10
M66-30)
0.00
0.52
0.50
3.
0.79
0.50
-a-0mmm -en-Winn
Lamax 180)
3.5
0.40
40- Piecd 2.00
-Pecd 2001
-10
blaad
0.0
Liaroo 1 18- Qpeer Viece
101112251445155
3.0
19.112:304.5
(8)
(b)
(c)
(d)
Figure 5: Empirical results for the ltague-style algorithm. (a) Accuracy versus the number of initial candidates N for the league-style (L.G, solid lines) and knockout-style (KO, dotted lines) algorithms, given the same initial candidates. (b) The distribution of GPQA problems, characterized by Pex and that are estimated with the Mixed option. Each problem is represented by circle if it is solved correctly at N 16, and by cross otherwise.
(c) Accuracy versus N on the subset of problems satisfying 0 < Pcs < and Â 0. The values of accuracy are calculated with new trials of the algorithm, thus statistically independent of Po. and Â. (d) Accuracy versus M, the number of subsampled opponents for each candidate, for the league-style algorithm with N 16.
one would not expect significant gains from pairwise comparison if the LLM simply does not have the right knowledge embedded within its model weights, in which case Peomp might be close (or even below) 0.5.
4.2 Results for the league-style algorithm
Efficacy and scaling properties. Figure 5 shows that the accuracy the league-style algorithm grows with N for all of Llama3. 1, Qwen2.5 5 and Mixed options on GPQA, e.g., accuracy of Mixed improves by points (from 45% to 53%) as N grows 16. The Mixed option consistently outperforms Llama3. 1 and Qwen2. 5, similar to the case for the knockout-styy algorithm. Given the same initial candidates, the league-style algorithm achieves higher accuracy than the knockout-stye algorithm does in some cases and lower in other cases, although the differences are minor in general.
Bridging with the theories. Let start by finding proxies for the Pes and A parameters in Assumption 3.1 For the former, we define Pes as the fraction of initial candidate solutions with the correct final answer. For the latter, we define Á ūü, Mig. where i == arg max;e[N]: is correct ii; and i2 == arg [aX is incorrett 72 are the indices for the strongest correct candidate and for the strongest incorrect candidate, respectively. Note that by definition, for any problem with Pes & (0, 1}. the league-style algorithm returns a correct solution to the problem and only if Â 0.
Figure 15 in Appendix D.3 characterizes the distribution of GPQA and MMLU-Pro-S problems in terms of Pas (X-axis and Â (Y-axis); the plot corresponding GPQA and Mixed can also be found in Figure (b). is noteworthy that there exists a non-trivial proportion of problems for which Pos is fairly small (i.c.. most of the initial candidates style aggregation stage still manages attain a positive Â and thus identify a correct candidate for the final output. On the other hand, for problems with A < 0 (which indicates violations of Assumption 3.I.. there is success guarantee for the algorithm. Figure 5 significant improvements in accuracy, e.g., 25% increase for Mixed, can be achieved on the subset of problems that approximately satisfy Assumption 3.1
incorrect), yet the proposed Icague-
(c) further confirms that
Efficacy of subsampling opponents. While all previous experiments consider the round-robin version of the league-style algorithm, we also wonder if it is feasible to improve its computational
efficiency by estimating the average win rate of each candidate with M < N subsampled opponents, while maintaining its accuracy. The empirical results in Figure 5 (d) provide positive answer and match what our theories in Section J predict: (1) accuracy initially increases with M, which confirms the benefits of comparing each candidate with multiple opponents; (2) once M exceeds a threshold (around or 5) that is much smaller than = 16, accuracy saturates around the level achieved by the round-robin version, but lower computational cost.

---

5
Related works
There exist other test-time strategies that enjoy provable inference scaling laws in the sense of Definition 1.1. One example is majority voting, whose provable success requires two assumptions
4.47: : (1) it is feasible to divide the candidate solutions into several groups and have a meaningful
count for each group (which is not the case in tasks like open-ended writing, where all candidate solutions are distinct), and (2) the probability that one LLM call generates a solution belonging to the correct group is higher than that for any other group. In comparison, our proposed algorithms free from the first restriction, and only require Pgen > O while making additional assumptions about LLMs' capabilities in pairwise comparisons. Another example is best-of-N (BoN) sampling, for which deriving a provable scaling law is straightforward provided that a perfect verifier is available: if one LLM call generates a correct solution with probability Pgen -0, then the failure probability of
BoN is (1 Pgen) One obvious limitation is that verifiers are unavailable or imperfect in many practical scenarios. which can hinder the performance of BoN 5 36 2 We refrain from comparing our methods with BoN in our experiments, since introducing an external verifier or reward model will bring extra variability that makes it difficult to conduct a fair and meaningful empirical comparison.
Our algorithm design has drawn inspiration from various areas. For example, the essential idea of pairwise comparison has been prominent in LLM alignment [ 30 32 and the LLM-as-a- juddee paradigm [57 20). Although it is possible to verify, score refine solution by itself [14] 23 6 [1], it is often much easier (for LLMs or human) to detect the errors or hallucinations in an incorrect solution when it is placed right next a correct one, evaluate the quality of solution by comparing it to another one. The knockout and league tournaments have also been investigated in
prior LLM research [17 23 56 19 [. albeit with purposes or implementations that are different from ours. Given this context, we remark that the main novelty and contributions in this work are perhaps less about the proposed two-stage algorithms themselves, but rather more about developing rigorous and theoretical understanding of their underlying assumptions and efficacy (via clearly identifying sufficient conditions for boosting their success probability up to 100% and formally deriving quantitative bounds for their computational and sample complexities), and demonstrating their promising empirical performance through extensive experiments.
6 Limitations and future work
One limitation of this work is that, like any other test-time scaling method, the proposed algorithms trade computation for higher success rate. Future work may try find practical ways determine the smallest values of hyperparameters N and K necessary for a targeted success probability. We also note that the provable success of the proposed algorithms relies on technical assumptions that might not always hold true (as is the case for many other thcories), although we anticipate optimistically that with the ongoing developments of LLMs, the assumptions made in this work (and thus our algorithms) will automatically become feasible for more and more challenging tasks.
Future work may also try extend the methodologies and theories broader scenarios, including (I) evaluating the proposed algorithms in more diverse tasks; (2) combining the proposed algorithms with other test-time scaling strategies for the best performance 355; : (3) efficiently amplifying the success probability of an agentic workflow by applying the proposed algorithms to each sub-task; (4) converting the proposed methods anytime algorithms 455 in online scenarios where the amount of available test-time compute is adaptive and unknown a priori. We defer detailed discussions to Appendix A due space limitations.
Acknowledgments
The authors would like to thank the anonymous reviewers and Area Chairs for their constructive feedback that has helped improve this work.
References
[1] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39:324, 1952.
10

---

[2] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv, 2024.
[3] Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei Zaharia, and James Zou, Are more Ilm calls all you need? towards the scaling properties of compound ai systems. In The Tiihth- Annual Conference on Neural Information Processing Systems, 2024.
[4] Yanxi Chen, Yaliang Li. Bolin Ding, and Jingren Zhou. Designing algorithms empowered by language models: An analytical framework, case studies, and insights. Transactions on Machine Learning Research, 2025.
[5] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv, 2021.
[6] Jared Quiney Davis, Boris Hanin, Lingjiao Chen, Peter Bailis, Ion Stoica, and Matei Zaharia. Networks of networks: Complexity class principles applied to compound ai systems design. arXiv, 2024.
[7] DeepSeek-AI. Deepseek-rl: Incentivizing reasoning capability in ilms via reinforcement
learning. arXiv, 2025.
[8] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. Improv- ing factuality and reasoning in language models through multiagent debate. In Forty-first International Conference on Machine Learning, 2024.
[9] Dawei Gao, Zitao Li, Xuchen Pan, Weirui Kuang, Zhijian Ma, Bingchen Qian, Fei Wei, Wenhao Zhang, Yuexiang Xie, Daoyuan Chen, Liuyi Yao, Hongyi Peng, Zeyu Zhang, Lin Zhu, Chen Cheng, Hongzhu Shi, Yaliang Li, Bolin Ding, and Jingren Zhou. Agentscope: A flexible yet robust multi-agent platform. Xrviv, 2024.
[10] Hello got-4o. httpp:///openaa..cmm//neeaee hww.:///oooneneedeeeeeeeeoooooee
2024.
[11] Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. Large language models cannot self-correct reasoning yet. In The Twelfth International Conference on Learning Representations, 2024.
[12] Yixin Ji, Juntao Li, Hai Ye, Kaixin Wu, Jia Xu, Linjian Mo, and Min Zhang. Test-time computing: from system-l thinking to system-2 2 thinking. arXiv, 2025.
[13] Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. Lim-blender: Ensembling large language models with pairwise ranking and generative fusion. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14165-14178, 2023.
[14] Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfell-Doddss, Nova DasSarma, Eli Tran-Johnson, Scott Johnston, Sheer El-Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hernandez, Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom Brown, Jack Clark, Nicholas Joseph, Ben Mann. Sam McCandlish, Chris Olah, and Jared Kaplan. Language models (mostly) know what they know. arXiv, 2022.
[15] Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B Murthy. Position: Lims can't plan, but can help planning in Ilm-modulo frameworks. In Forty-first International Conference on Machine Learning, 2024.
[16) Sayash Kapoor, Benedikt Stroebl, Zachary S. Siegel, Nitya Nadgir, and Arvind Narayanan. Ai agents that matter. arXiv, 2024.

---

[17] Akira Kawabata and Saku Sugawara. Rationale-awar answer verification by pairwise self- evaluation. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, 2024.
[18] Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems, volume 35, pages 22199-22213, 2022.
[19] Sangkyu Lee, Sungdong Kim, Ashkan Yousefpour, Minjoon Seo, Kang Min Yoo, and Youngjae Yu. Aligning large language models by on-policy self-judgment. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 11442-11 1459, 2024.
[20] Dawei Li, Bohan Jiang, Liangjie Huang, Alimohammad Beigi, Chengshuai Zhao, Zhen Tan, Amrita Bhattacharjee, Yuxuan Jiang, Canyu Chen, Tianhao Wu, Kai Shu, Lu Cheng, and Huan Liu. From generation to judgment: Opportunities and challenges of Ilm-as-a-judge. arXiv, 2024.
[21] Junyou Li, Qin Zhang, Yangbin Yu, Qiang Fu, and Deheng Ye. More agents is all you need. Transactions on Machine Learning Research, 2024.
[22] Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, llya Sutskever, and Karl Cobbe. Let's verify step by step. In The Tweifth International Conference on Learning Representations, 2024.
[23] Tianqi Liu, Yao Zhao, Rishabh Joshi, Misha Khalman, Mohammad Saleh, Peter J Liu, and Jialu Liu. Statistical rejection sampling improves preference optimization. In The Twelfth International Conference Learning Representations, 2024.
[24] Llama Team, Al @ Meta. The Ilama 3 herd of models. arXiv, 2024.
[25] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with felfbeeee In Thirty-seventh Conference Neural Information Processing Systems, 2023.
[26] Math-500.
2024.
[27] Soheil Mohajer, Changho Suh, and Adel Elmahdy. Active learning for top-k rank aggregation from noisy comparisons. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2488 2498-2297.22 PMLR, 2017.
[28] Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannanch Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling, arXiv, 2025.
[29] OpenAI.
Openai o1 system card. openal-o1-system-coome card/ 2024.
https:://opeaai.com/nnee
[30] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke F. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, 2022.
[31] Qwq-32b: Embracing the power of reinforcement learning. https::/qvenll... wha.llm..gttuu..... io/ Blog/quq-32h) 2025.
[32] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. In Advances in Neural Information Processing Systems, 2023.
12

---

[33] David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R. Bowman. GPQA: graduate-level google-prodd q&a benchmark, In First Conference on Language Modeling, 2024.
[34] Rylan Schaeffer, Joshua Kazdan, John Hughes, Jordan Juravsky, Sara Price, Aengus Lynch, Erik Jones, Robert Kirk, Azalia Mirhoseini, and Sanmi Koyejo. How do large language monkeys get their power (laws)? arXiv, 2025.
[35] Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv, 2024.
[36] Benedikt Stroebl, Sayash Kapoor, and Arvind Narayanan. Inference scaling flaws: The limits of Ilm resampling with imperfect verifiers. arXiv, 2024.
[37] Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, Chuning Tang, Congcong Wang. Dehao Zhang, Enming Yuan, Enzhe Lu, Fengxiang Tang. Flood Sung, Guangda Wei, Guokun Lai, Haiqing Guo, Han Zhu, Hao Ding, Hao Hu, Hao Yang, Hao Zhang, Haotian Yao, Haotian Zhao, Haoyu Lu, Haoze Li, Haozhen Yu, Hongcheng Gao, Huabin Zheng, Huan Yuan, Jia Chen, Jianhang Guo, Jianlin Su, Jianzhou Wang. Jie Zhao, Jin Zhang, Jingyuan Liu, Junjie Yan, Junyan Wu, Lidong Shi, Ling Ye, Longhui Yu, Mengnan Dong, Neo Zhang, Ningchen Ma, Qiwei Pan, Qucheng Gong, Shaowei Liu, Shengling Ma, Shupeng Wei, Sihan Cao, Siying Huang, Tao Jiang, Weihao Gao, Weimin Xiong, Weiran He, Weixiao Huang, Wenhao Wu, Wenyang He, Xianghui Wei, Xianqing Jia, Xingzhe Wu, Xinran Xu, Xinxing Zu, Xinyu Zhou, Xuehai Pan, Y. Charles, Yang Li, Yangyang Hu, Yangyang Liu, Yanru Chen, Yejie Wang, Yibo Liu, Yidao Qin, Yifeng Liu, Ying Yang. Yiping Bao, Yulun Du, Yuxin Wu, Yuzhi Wang, Zaida Zhou, Zhaoji Wang, Zhaowei Li, Zhen Zhu, Zheng Zhang, Zhexu Wang, Zhilin Yang, Zhiqi Huang, Zihao Huang, Ziyao Xu, and Zonghan Yang. Kimi k1.5: Scaling reinforcement learning with llms. arXiv, 2025.
[38] Roman Vershynin. High- lige-Dimesiooal Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018
[39] Junlin Wang, Jue Wang, Ben Athiwaratkun, Ce Zhang, and James Zou. ofxture-of-agents enhances large language model capabilities. arXiv, 2024.
[40] Peiyi Wang. Lei Li, Liang Chen, Zefan Cai, Dawei Zhu, Binghuai Lin, Yunbo Cao, Lingpeng Kong, Qi Liu, Tianyu Liu, and Zhifang Sui. Large language models are not fair evaluators. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pages 9440-9450, 2024.
[41] Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023.
[42] Yubo Wang, Xueguang Ma. Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj. Xuan He, Ziyan Jiang, et al. Mmlu-pro: more robust and challenging multi-task language understanding benchmark. In Advances in Neural Information Processing Systems, 2024.
[43] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Huai hsin Chi, F. Xia, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, 2022.
[44] Sean Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf. Alex Xie, Graham Neubig, Ili Kulikov, and Zaid Harchaoui. From decoding meta- meta-generatton. Inference-time algorithms for large language models. Transactions on Machine Learning Research, 2024.
[45] Wikipedia, Anytime algorithm. 2024.
aalgorllggiaaaeo thm
13

---

[46] Wikipedia. Round-robin tournament.
tournament 2024.
[47] Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. An empirical analysis of compute-optimal inference for problem-solving with language models. arXiv, 2024.
[48] Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, Rui Zheng, Xiaoran Fan, Xiao Wang. Limao Xiong, Yuhao Zhou, Weiran Wang, Changhao Jiang, Yicheng Zou, Xiangyang Liu, Zhangyue Yin, Shihan Dou, Rongxiang Weng, Wensen Cheng, Qi Zhang, Wenjuan Qin, Yongyan Zheng, Xipeng Qiu, Xuanjing Huang, and Tao Gui. The rise and potential of large language model based agents: A survey. arXiv, 2023.
[49]
An Yang, Baosong Yang. Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang. Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report. arXiv, 2024.
[50] Zhangyue Yin, Qiushi Sun, Cheng Chang, Qipeng Guo, Junqi Dai, Xuanjing Huang, and Xipeng Qiu. orehange-of-thoughe Enhancing large language model capabilities through cross- cross-model communication. In Proceedings of the 2023 Conference on Empirical Methods in Natural 2023.
Language Processing, pages
[51] Zhangyue Yin, Qiushi Sun, Qipeng Guo, Zhiyuan Zeng, Xiaonan Li, Tianxiang Sun, Cheng Chang, Qinyuan Cheng, Ding Wang, Xiaofeng Mou, Xipeng Qiu, and Xuanjing Huang. Ag- gregation of reasoning: A hierarchical framework for enhancing answer selection in large language models. In Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024), pages 609-625, 2024.
[52] Matei Zaharia, Omar Khattab, Lingjiao Chen, Jared Quincy Davis, Heather Miller, Chris Potts, James Zou, Michael Carbin, Jonathan Frankle, Naveen Rao, and Ali Ghodsi. The shift from models to compound systems. https:://bairbberkeeeey 2024.
berkeley eddbbllog//222////////
[53] Zhiyuan Zeng, Qinyuan Cheng, Zhangyue Yin, Bo Wang, Shimin Li, Yunhua Zhou, Qipeng Guo, Xuanjing Huang, and Xipeng Qiu. Scaling of search and learning: A roadmap to reproduce ol from reinforcement learning perspective. arXiv, 2024.
[54] Kexun Zhang, Shang Zhou, Danqing Wang, William Yang Wang, and Lei Li. Scaling I1m inference with optimized sample compute allocation. arXiv, 2024.
[55] Lunjun Zhang, Arian Hosseini, Hritik Bansal, Mehran Kazemi, Aviral Kumar, and Rishabh Agarwal. Generative verifiers: Reward modeling as next-token prediction. The 4th Workshop on Mathematical Reasoning and Al at NeurlPS 244, 2024.
[56] Yao Zhao, Rishabh Joshi, Tianqi Liu, Misha Khalman, Mohammad Salch, and Peter J. Liu. Slic-hf: Sequence likelihood calibration with human feedback. arXiv, 2023.
[57] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging LLM--a--a-udde with MT-bench and chatbot arena. In Thirty-seerrth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023.
14

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We have provided the GitHub link codebase, as well sufficient instructions to reproduce the main experimental results, in Section and Appendix D.1
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc
aublic//uidde//Coeettuiiiss cesssiinnooyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wwtps/cccppplgguuuiieeeeee
www.sssoiccgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details necessary to understand the experimental results can be found in Section and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Error bars are not reported because it would be too computationally expensive to run the necessary experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: This work involves large number of experiments that were executed on different days and possibly on different machines, which makes it difficult to track the computer resources for each of them. We have provided detailed information about the datasets, LLMS and hyperparameters (e.g., and K) for our experiments, which can be useful for estimating the amount of computer resources needed to reproduce the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttps:/nnerript
Answer: [Yes]
Justification: The research conducted in the paper conforms, every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
18

---

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

---

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

---

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

---

Structure of the appendix
This appendix is organized follows. AppendixAA|suppleent
the discussions in Section 6 about potential extensions of the current work to broader scenarios. Appendix [ includes the proof's for main theorems, and Appendix presents some minimal examples that assist understanding about how Assumptions [2.1] and 1 compare with each other. Appendix [D] includes additional implementation details and the prompt templates used throughout our experiments, as well as supplementary empirical results.
A Discussions: extensions to broader scenarios
Combination with other test-time strategies. The proposed two-stage methods are orthogonal and complementary many other test-time scaling strategies. For example, our experiment with QwQ-32B shows that the performance of a long-Con -oo reasoning LLM can be further boosted with the knockout-style algorithm. Future work may investigate systematic approaches of combining different inference scaling strategies for achieving the best performance [35
Application to agentic workflows. In complex real-world scenarios, common practice is to adopt an agentic workflow that decomposes the original task into manageable sub-problems and involves multiple L.M calls to solve all of them [52 48 4. Applying the knockout//eague-stylle algorithm proposed in this work to each sub- sub-problem can efficiently amplify the success probability of the overall workflow. To
how this works, consider scenario where solving the original problem requires solving all S 2 1 sub-problems correctly, and each sub-problem satisfies Assumption 2.1 with parameters Pgen
and Promp 0.5. Directly solving all S sub-problems has a exponentially small success probability Pren- and thus generating correct solution alone already requires (2((1/ggmm) attempts, not to mention identifying which attempt is successful. In contrast, by applying the knockout-style algorithm (with hyperparameters N and K) each sub- sub-problem, an overall success probability 1 for solving the original problem can be guaranteed as long as the failure probability for each sub-problem bounded by 8/S, thanks to the union bound. According to Eq. (I). this is guaranteed with
28 log Pgen both with logarithmic dependence on S. The total number of LLM calls with this approach is (K' + 1) x N x S (ef. Section 2.2 which grows with S linearly, up to logarithmie factors.
2 2 NIS
N
and K
2(Pomp 0.5)² log
Anytime algorithms for online settings. In many real-world scenarios, the available amount of test-time compute is adaptive and unknown a priori. To address such cases, we can easily convert the knockout-style algorithm to an "anytime" variant (45) that does not require pre-specifying N. For example, the algorithm might start with 4 candidate solutions and choose the winner via knockout tournament. If more test-time compute allowed (c.g., the user is not cagerly requesting the solution, more computational resources become available), then the algorithm can launch another tournament with 4 freshly sampled candidates, the winner of which will compete with the winner of the previous tournament. This complete process is indeed equivalent with N = + 4 = 8. Such a process can continue until the user finally requests the solution; the eventual value of N is determined online and automatically achieves the maximum value allowed by the available test- time compute. Similarly, the league-style algorithm can be converted to an anytime variant, where the total number of candidates and/or the number of comparisons for each candidate increase gradually as more test-time compute becomes available. It would be interesting future work to investigate such anytime algorithms from theoretical or practical perspective.
single tournament
B Proofs of main theorems
B.1 Proof of Theorem 2.3
To begin with, we have a straightforward analysis for the failure probability of the generation stage of the algorithm, where N candidate solutions are sampled independently:
P(no candidate solution is correct) S (1 Peen)
22

---

As for the knockout stage, let us first consider a single pair of correct and incorrect candidate solutions. Recall that they are compared for K times with K LLM calls (followed by majority voting). and each LLM call identifies the correct candidate solution the winner with probability μ 2 Peomp > 0.5 by assumption. Therefore, the failure probability of comparing this pair of candidates can be bounded as follows, where X, denotes an independent Bernoulli random variable with mean ja:
K
(failure of comparison) s P
X
S
= PP K
Σ KE[K]
X S 0.5)
2
KE|K]
P
Σ kE[K]
Xi 1 S -(u -mu-000) -0.5)
-2K(4 - -0.5)) S exp (-2K (22(Peom (Promp -.5)²).
S exp
Here use Hoeffding's inequality 38 in the last line.
Now we are ready to control the failure probability of the complete knockout stage. Let us condition on the event that the generation stage succeeds, i.e., there is at least one initial candidate solution that is correct. We arbitrarily pick a correct candidate, and focus on its path to the final output of the algorithm in the binary tree visualized in Figure | We claim that, with high probability, the comparison (with K LLM calls) for each pair along this path yields the correct outcome. This can be proved by induction: for each pair along this path, if one of the input candidates (which is the output of the previous pairwise comparison on this same path) is correct, then the output of comparing this pair will also be correct with failure probability no greater than exp( 2K (Promp 0.5)²), ). regardless of whether the other input candidate is correct or not. By taking a union bound over the failure events along this path with [log2 N pairs to be compared, this path yields the correct outcome (which immediately implies that the final output of the algorithm correct), with failure probability greater than [log2 N1 exp(- 2mpp-KK(( (Pcoup 0.
claim that the comparison for each pair along
Finally, taking a union bound over the failure events of both stages of the algorithm completes our proof of Theorem 2.3
Remark B.1. There exists analysis in the literature of top-k ranking (e.g.. Section 4. of [2 that are similar to our analysis for the knockout stage. We choose to present our own version here to make our work more self-contained and complete.
B.2 Proof of Theorem 2.4
For the first part of the theorem, can derive p++1 from p; follows. Notice that a candidate the (i 1)-th level of the knockout tournament is the winner of pairwise comparison between a pair of statistically independent candidates at the i-th level. Thus, the winner is a correct solution if both candidates of the pair are correct, or only one of them is correct and happens (with probability at least Poomp.K K by assumption) to be chosen as the winner. Therefore.
Ps+1 2 2 + 21 Pi)peomp.K = p? + 2Peomp,K K (p= p.) = P: - p; + ps + PPcomp, K (p: - p?)
P; + (2Dcomp. K () -
This implies Pi+1 > Pt. as long as Peomp. > 0.5 and ps < 1.
For the second part of the theorem, consider the convergence of {p:} in two cases: when it is still below 0.5, and when it has exceeded 0.5.
If p; < 0.5, then 1 pt 0.5, and
Pi+1 2 Ps + (2Pcomp.k K 1)(1 pt)Ps
> p: + (Peomp, K 0.5)p;
= + (Promp. - 0.5) pi-
In other words, the sequence {p:) grows exponentially when it is below 0.5, and
log (max 2paes 1))
ps 2 Pgen [ (Pcomp, K - 0.5)) 2 0.5 as long as
log (1 + (Pcomp.K - 0.5)
23

---

For any i > J and hence p; 2 0.5, we have
1 - Pi+1 S 1 Pt- (2Pcomp, 1)p,(1 P:)
Σ Pt (Poomp, K 0.5)(1 pi)
(Promp, - 0.5) (1 - pp)).
In other words, the sequence {1 - p2} converges to O, and
1 1- s1 p.) (1 [Poomp,K K - 0.5) -
(Pcomp. -0.5)
i-j
log
as long as i log (1 (Poomp.X - 0.5))
(4)
Putting Eq. 3 and Eq. 4 together concludes our proof of the theorem.
B.3 Proof of Theorem 3.3
To begin with, we have a straightforward analysis for the generation stage:
P yi Nes, Vi INT) < (1 P(x)
For the aggregation stage, we aim to show that for each i E [N]. the estimated average win rate 76: calculated within the algorithm is close to its average win rate against Mgen- denoted by μt == My. To see this, let us recall the definitions of μ4 and pss as well as introduce new notation f4;
μ1 = By'rMM (x) Bro M. ((, 3')
e4 = 1 N JE(N)M(
Momo 0r, Vi, Uj)
U of JE B.m ) Mi, "',
i. Σ ((:(U), Us: Vor()))
JE(K]
Note that in the last line, yo,()) ~ J E [iT]) and rz()) ~ Mcomp (z, yis Bor())) By Hoeffding's 's inequality, we have the following for each i [N]:
A
< 2 exp (- KA2
P [44 Tual
2 P
Σ
Thi 2
K
4
8
SEIK]
A
TTu - M4l PP
2
N-1
Bmn. UJ) - M4
2
4
JE
(N
1)A2
2xp
8
These, together with the fact that lp:
Hil
17,
T4al
7i4 pil. implies that
A
A 1) (N 1)
P p
2
P
lite
Tuel
+ IP
|i
141
K
A
2xxp
exp
8
8
Finally, taking a union bound over i E [N] and over both stages of the league-style algorithm, we have the following: with probability at least
KA²
(N 1)A2
- (1- - Pes) 2N exp
2N exp
8
8
there exists some E [N] such that yı E Ve. and [ī Mzl < A/2 for all E [N]. These conditions,
together with the assumption that minyexi, By max,e My 2 A, guarantee that the final output of the algorithm is correct solution.
24

---

C Examples for understanding and comparing the assumptions
This section presents some minimal examples for assisting our understanding of Assumptions 2.1 a.1 and in particular, for comparing the condition Promp > 0.5 stated in the former and A > 0 stated in the latter. For simplicity, we assume that the set of all possible candidate solutions returned by the generation stage, denoted by y, has a small number of unique elements, e.g., y {A, B, C). We use the notation PA IP Mys))) (x) (y = A), and let P(A > B) denote the probability that one comparison between A and B identifies the former as the winner. When two identical candidates are compared, we assume that tie broken randomly and thus either candidate wins with probability 0.5. All average win rates involved in these examples are calculated with respect to the distribution Mgen-
Example C.1. We demonstrate a scenario where both Assumptions 2.1 and 3.1 hold, and there is correspondence between the parameter Peomp in the former and A in the latter. Suppose that y = {A. BJ, where A is correct and B is incorrect. In addition, PA 0,PB = 1 a, and P(A > B) Peomp > 0.5. Then we can calculate the average win rate of each candidate as follows:
a. = PA x 0.5 + PB X Peump = 0.5 x a Pecemp x (1 aa)) a)
(0.5 Peomp) X a + Poomp:
μB = Pn x 0.5 + PA X (1 Peomp) = 0.5 x (1 - a) + (1 Pcomp) X a
(0.5- Poomp) x + 0.5,
which implies that
A MA μB Poomp 0.5 > 0
is independent of the value of a.
Example C.2. We demonstrate scenario where both Assumptions 2.1 and hold, but the parameter A in the latter can be much smaller than Poomp 0.5 in the former. Suppose that y = {A, B, C}, where only A is correct. In addition, PA = pg a. PC P(A > C) = IPB > о) 0.9. Then we can calculate the average win rate of each candidate as
2a, P(A > B) Poomp 0.5, and
follows:
PA PA X 0.5 + PB X Poomp + PC x 0.9
= a x (0.5 + Poomp) + (1 - 2ax) x 0.9,
μB PA (1 Poomp) + PB 0.5 - pC 0.9 a X (1.5 Poomp) + (1 2a)) x 0.9,
PC = PA X 0.1 + PB x 0.1 + pC x 0.5
a x 0.2 + (1 2a) x 0.5,
which implies
A = μA - uB = 2ox x (Dcomp 0.5).
As result, A 0 can be much smaller than Promp 0.5 if a is small.
Example C.3. We demonstrate a scenario where Assumption holds true but Assumption 3.1 does
not. Suppose that y {A, B, C}. where only correct. In addition, PA = 0.2, 0.2, PC
0.6, IPA > B) = P(A > C*) = 0.6, and P(B > C* = 0.9, which satisfies Assumption 2.1 Then
we have
AA PA X 0.5 + PB x 0.6 + PC x 0.6 = 0.58,
#B PA X 0.4 + PB x 0.5 0.5 PC x 0.9 0.72,
Ac PA X 0.4 + Pg x 0.1 + Pc x 0.5 = 0.40.
In other words. the average win rate of the only correct solution is lower than that of an incorrect solution B, which violates Assumption 3.1
Example C.4. We demonstrate a scenario where Assumption
3.1 holds true but Assumption 2. does
not. Suppose that y [A, B, C}. where only A is correct. In addition, PA 0.2, Pg 0.2, PC 0.6, P(A > B)= = 0.4, P(A > C) = 0.9, and P(B > C') = 0.5, which violates Assumption 2.1 However, we have
μ^ = PA X 0.5 + PB X 0.4 + PC x 0.9 = 0.72,
μB PA X 0.6 + PB x 0.5 + Po x 0.5 0.52,
PC = PA x 0.1 + PB x 0.5 + Pc x 0.5 = 0.42,
which satisfies Assumption 3. since the only correct solution A has the highest average win rate.
25

---

MMLU-Pro-S
MATH-500
Accursty
0..80
0.75
0.70
0.55
-Uamma3
Owen2.5 Mixed
32
0.50
N
Figure 6: Accuracy versus the number of initial candidates for the knockout-styy style algorithm on MMLU-Pro-S (left) and MATH-500 (right).
D Supplementary materials for experiments
D.1 Additional implementation details
Throughout our experiments, the temperature for LLM decoding is set to 0.5 for the generation stage, and 0.1 for pairwise comparisons during the aggregation stage. Our early exploration suggests that these choices strike a good balance between diversity and preciseness in LLM decoding.
During the generation stage, we ask the LLM (via zero-shot CoT prompting [8] to generate reasoning process first and then its final answer. For each pairwise comparison during the aggregation stage, we also leverage zero-shot CoT prompting and ask the LLM to think step by step before deciding which solution the pair is more plausible, unless specified otherwise. Tables and 2 at the end of this section include the prompt templates used in our experiments for GPQA and MMLU-Pro-S, both of which are multiple-choice datasets. The prompt templates for MATH-500 are largely the same, only slightly adjusted to account for the desired output formats. Some parts of our prompts, as well as code for parsing LLMs' responses and extracting the answers for evaluation, are modified from those in the official GitHub repository of MMLU-PrC
To account for the positional bias of LLMs [57
we ensure that when pair of candidates are compared for multiple times, they are placed in one order within the prompt for half of the comparisons, and in the opposite order for the other half.
40
Due to the high computational or monetary costs of the experiments, we have run the knockout/league- style algorithm only once for each <model, dataset> combination. To enhance the stability and reliability of the plots in this paper, we take the following approaches:
For the knockout-style algorithm, we take advantage its binary tree structure (shown in Figure Dp. After rumning the algorithm once with N 64, automatically get the results 64 independent trials for N 1, 32 trials for N = 2. 16 trials for N = 4, and so on. We have thus taken the average of accuracy values from multiple independent trials for each datapoint (except for the rightmost one) in each scaling curve.
For the league-styy stylu algorithm, after running it once with N = 16. we are able to obtain the results of multiple trials for 8 (or any value smaller than 16), each corresponding to 8 randomly sampled candidate solutions and the comparison results among them. Each datapoint (except for the rightmost one) in each scaling curve has been calculated by an average of multiple results obtained this way.
D.2 Additional results for the knockout-style algorithm
Experiments with more datasets. on MMLLU-ProSS and MATH-500.
Figure 6 validates the efficacy of the knockout-style algorithm
Distribution of problems. Figure 7 illustrates the distribution of GPQA and MMLU-Pro-S prob- lems, characterized by Pgen and Peomp that are estimated with the empirical results for the knockout-
26

---

GPQA
GPQA
GPQA
1.00
0.55
1.00
2aw (055 500
1.00
0.50
0.50
0.50
0.00
Poapp 5]
456
0.00
0.00
405
0.00
2.00
0.00
0.25
0.50
0.25
0.50
0.75
1.00
0]
Pans
WI 11
164
Pams
<16
78
Pac
11
MMLU-Pro-S
MMLU-Pro-5
MMLU-Pro-S
1.00
1.00
1.00
0.75
0.50
0.50
0.50
0.25
0.25
0.00
0.00
0.00
0.00
0.25
0.50
1.00
0.00
0.25
0.50
0.75
0.25
0.50
0.75
1.00
0)
Pans
522
41
327
71
Pam
#0 1]
Figure 7: The distribution of GPQA (top) and MMLU-Pro-S (bottom) problems, characterized by Pren and Peomp that are estimated with the empirical results for the knockout-style algorithm using the Ll amlama3.1 1 (left), Qwen2.5 5 (middle) Mixed (right) option. Each plot is annotated with the number of problems satisfying the condition Poomp > 0.5, Peomp I 0.5, Pgan = 0 or Pgan = To the right of each plot is a histogram for Promp- Each problem is represented by circle if it is solved correctly by the knockout-style algorithm with Pgen 0 or 1, i..., problems for which the initial candidate solutions are all incorrect or all correct, since there is no way of obtaining meaningful estimate of Peomp for such problems.
64, and by a cross otherwise. We neglect problems with
GPQA; diamand
GPQA; diamond
1.00
P D5)
1.00
All
0.75
0.75
0.50
0.50
0.00
0.00
0.75
1.00
3.00
412
33 25
Age
016
03 25
Aas
P 11-14
Figure 8: The distribution of GPQA-diamond problems, characterized by Pgen and Peomp that estimated with the empirical results for the knockout-style algorithm using the QwQ-32B (left) or GPT-4o (right) option. Other settings are the same those in Figure 7
style algorithm using the Llama3.1 1 (left), Qwen2.5 5 (middle) or Mixed (right) option. Similarly, Figure & illustrates the results for QwQ-32B and CPT-4o.
the impact of K. The results in Figure P suggest that the performance of the knockout- style algorithm is insensitive K (the number of times that each pair of candidates are compared) in the setting of our experiments, as long as K > 2 for Llama3. 1 and Qwen2.5, 5, or K > 4 for Mixed. This is mainly due to our choice of a small temperature (0.1) for LLM calls that conduct pairwise comparisons. For Llama3. 1 and Qwen2.5 5, K 2 suffices to cover all prompting options, i.e., the order in which two candidate solutions are placed within the prompt. Similarly, for Mixed, K suffices to cover both prompting options and both LLM backends.
Ablation:
the impact of CoT prompting for pairwise comparison. Figure 10 confirms the benefits using zero-shot chain-of -f-thugh prompting for the aggregation stage of the knockout-style algorithm (versus prompting the LLM to answer directly which solution is preferred), especially as the test-time compute scales up. This matches the intuition that CoT prompting improves L.LMs' performance in conducting pairwise comparisons.
Ablation:
27

---

GPQA
0.50
Accurso)
0.45
.Jamm IK- 2)
Owen (1-21
L-Lamm (Km4) - Owen (X+4)
Liama (K=B) B) Owen (K=B)
(X+4)
(K+8)
30
Figure 9: The impact of K for the knockout-style algorithm.
GPQA
MMLU Pro
0.54
0.75
0.52
0.74
0.50
0.73
0.48
0.44
LiLamaaa.... 1OT
Owen2 OCT
--Lammaa...ccmm 2.COT
Liama3 OT
Owen2 5 OCT
0.70
10
20
30
50
60
10
20
30
40
50
60
Figure 10: The advantages of zero-shot chain tf-thhughtt prompting for pairwise comparisons, versus prompting the LLM to answer directly which solution is preferred (dashed lines), during the aggregation stage of the knockout-style algorithm.
Results for each category of GPQA and MMLU-Pro-S. Figure 11 includes empirical results of the knockout-style algorithm for each category of GPQA, while Figures 12 and include those for MMLU-Pro-S.
GPOA: diamand T0
CPOA: diamond
CPOA: diamond
0.75
0.75
0.75
0.53
0.53
0.52
0.51
6:51
GPGA: extended
GPQA: extended
GPOA: extended
retented
0000
0.55
0.55
0.53
EATS
0.82
0.57
6:5
main
1.00
1.00
1.02 alfeessdd
3.54
0.57
035
035
0.25
0.2
028
0.15
3.50
0.35
3.50
350
0.3 1.50
+2
Figure 11: Empirical results of the knockout-style algorithm for each category of GPQA.
28

---

NMLL--Fre bibboy
SNLU bi
KNLU bwagg
KYLU- barogy
0.75
0.75
0.75
0.52
0.53
6:53
MMLi--Pa-d: bunimas
HNLi-Po-: bairmas
HNLU-Prodi bosiraas
1.00
1.00
1.02 Alf
0.53
0.50
0.50
0.82
0.82
-1
-1---11130
MVLL Chemiory
1.00
1.00
1.33
0.50
0.00
0.25
0.25
0.25
265
16
008
0.25
3.50
0.15
2f 22
3.30
002
6.25
1.50
0.55
=f
3.50
002
1.2
3.50
0.35
2.50
20
NYLU-PO- compuier Sdanno
MML Piu--PrrS
MMLU-Pro
MMLL
0.75
0.75
0.25
0.25
0.25
002
6.25
330
3.50
002
6.5
350
3.30
002
633
3.50
HMLLSPOO ecoromics
K9L1- econamics
KoL aconomis
MNLi-P economes
0.75
0.75
0.75
2.2
Ower22 Plass
0.55
0.51
0:53
002
007
onpinouting
HMLL1-Pr-G: engineeding
HVLl--Po-G engineeding
HVLli-P--6 engineeding
0.72
0.72
6.7-
0.5
0.5
035
335
0.57
0.57
0.5
12
66
-11-11
1.0
ois
Po
-B-uaed Ower23 Poad
1.00
1:01
1:01
0.25
0.25
26
22
0.35
410
6.25
3.50
0.35
350
035
Figure 12: Empirical results of the knockout-style algorithm for each category of MMLU-Pro-S (Part 1).
29

---

HILLIPP-S: 1atory
HMLL--rr Natory
HILLL- Natory
WiLL Natory
0.75
0.75
0.75
0.2
07L
0.52
0.53
6:30
MVLL-Prod:
1.00
1.00
1.03
3.55
0.53
0.50
0.50
0.82
0.82
<0
-1 10
H84L Pro. math
1.00
1.00
1.00
0.0
3.03
0.25
0.25
-0-L Owarr Mac
54
0.2
-1
0.25
3.50
0.55
3.30
000
6.25
1.5
0.55
2.50
002
1.2
3.50
0.35
-1
2.50
MEALL frc other
MM
MMLU-Pr-
NMLU-Pm--
0.33
1.02
1:03
0.75
0.75
0.75
0.25
0.25
0.25
002
6.25
330
3.30
002
3.30
002
639
3.50
10p--l-- fum
VNLUPPOO 5 phaesophy
KHU--Poo ph philosohh
KHLi--ho-2 philosohhy
KMLL--ho-2 pritsophyy
0.75
0.75
0.75
0.55
0.51
0:53
0.2
002
002
MMLL-2mo-S phydes
MMiL--2ro- physee
MMiLA2ro-S phystes
0.21
3375-
0.72
0.72
0.5
0.50
0.5
0.57
0.57
0.57
64
-21--
poyche ogy
poycto ogy
poychology
1.00
1:01
1:01
0.25
0.25
236
23
0.35
410
6.25
0.35
-1-
002
6.25
350
035
Figure 13: Empirical results of the knockout-style algorithm for each category of MMLU-Pro-S (Part 2).
30

---

MM-L--Pr-S
MMLU--Pr--5
0.705
0.75
0.755
0.74
0.750
0.73
0.745
Ulama3 L [LG]
4lama3,1 1 (K0)
0.71
0.wu225
(LG)
Owen2.5
(KD)
0.735
Llama3.
Mixud
0.0
14111531
121312131415
Figure 14: Empirical results for the league-styl style algorithm MMLU-Pro- S. Left: accuracy the number of initial candidates N for the league-style (LG, solid lines) and knockout-style (KO, dotted lines) algorithms, given the same initial candidates. Right: accuracy versus M, the number of subsampled opponents for each candidate, for the league-style algorithm with N = 16.
GPOA
GPOA
GPQA
(0000.0) - 411
[600.0 3/2
16 00.0 408
44
0.0
0.0
0.0
-1.0
H M.0mb. 45-
-1.0
(l0 341
-1.0
(16.0.0 - 428
0.00
1.00
0.00
0.25
0.50
0.75
0.00
0.25
0.50
0.75
+/ 00 0) 185
* 1P 145
*/---
0) 247
Pam
PP - 1] 251
- 0)
156
Pam
o 1) 142
MMLU-Pro-S
MMLU-Pro-S
MMLU-Pro-S
1.0
M.-00.0) - 401
(6000.) - 2m
16-00.0 453
0.5
0.5
0.5
-0.5
-0.5
-0.5
-1.0
0.00
2.00
0.00
0.25
0.50
0.75
0.25
0.50
0.75
1.00
#i 139
Pans
#1 11
Pam
=1 773
Figure 15: The distribution of GPQA (top) and MMLU-Pro-S (bottom) problems, characterized by Pes and A that are estimated with the empirical results for the league-style algorithm using the Llama3.1 1 (left), Quen2.5 5 (middle) or Mixed (right) option. Each plot is annotated with the number of problems satisfying the condition > 0, Â < 0, Pes = 0 or Pes = 1. To the right of each plot is histogram for A. Each problem is represented by circle if it is solved correctly by the league-style algorithm with 16, and by a cross otherwise. We neglect problems with Pos = 0 or 1, i.c., problems for which the initial candidate solutions are all incorrect or all correct, since there is no way of obtaining meaningful estimate of Ä for such problems.
D.3 Additional results for the league-style algorithm
Results for MMLU-Pro-S. Figure 14 includes empirical results for the league-style algorithm on MMLU-Pro-S.
Distribution of problems. Figure 15 illustrates the distribution of GPQA and MMLU-Pro-S
problems, characterized by Pes and A that are estimated with the empirical results for the league-style algorithm using the Llama3. 1 (left), Qwen2.5 (middle) or Mixed (right) option.
closer look at both algorithms and their differences. Figure 16 detailed comparison between the empirical performance of both algorithms. It characterizes the distribution of GPQA and MMLUUPro-S problems in terms of Peomp from the knockout-style algorithm and A from the league-style algorithm, and provides the concrete number of problems that one algorithm solves correctly/ineorrectyy and the other algorithm solves correctly/inoorrectyy
31

---

(0wen2.5)
3.00
1.05
3.00
6.75
K5-U7 1f 001
0.75
Kl.ah
6.75
0R-M 10 921
0.50
42 JN 2601
0.52
KN
1
2021
0.50
021 UN
2401
6.25
0.22
0.25
6.00
0.02
0.00
0:25
0.25
4,50
0.52-
6,50
0.75
3.0
0.2
0.6
0.8
0.2
6.7
0.5
0.5
6.8
1.0
3.0
0.2
3.6
1.
616
415
MMLU (MExd))
1.60
1.02
3.00
0.75
1317712 10 - 431
0.75
6.75-
00 up
RN-W
197)
1611
8.50
0.52
6.50
6.25
0:25
0.25
0.00
0.01
0.00
-6.25
-0.25
-0.50
-0.50
0:75
0.75
-3.00
2.0
0.2
2.4
0.6
0.5
1.5
0.5
0.4
0.5
0.5
5-5
1.0
2.5
0.2
1.4
0.6
0.8
1.5
418
11
41
Parp
41
41
Fure
40% 21
Figure 16: The distribution of GPQA (top) and MMLU-Pro-S (bottom) problems, characterized by
Poomp from the knockout-style algorithm and A from the league-style algorithm (both with N = 16) using the Llama3. (left), Qwen2. 5 (middle) or Mixed (right) option. The following abbreviations used for the legend: K knockout, L league, R right, W wrong. For example, "KW-LR
(# = 66)" means that there are 66 problems for which the knockout-style algorithm did wrong while
the league-style style algorithm did right.
GPOA: damond
GPOA: dimmnnd
GPOA: dimmnnd
GPOA: damend
0.5
0,5
5.5
0.00
-0.
-03
-05
-0-48743 - Coer22 -e-tai
123 21
0.00
0.55
6.50
1.00
0.00
025
Fan
6.90
3.75
1000
11
0:00
625
Fam
3.75
11
1.60
GPOA: exlanded
CPON: extended
CPON: extended
CPON: extended
0.32
1.
1.0
1.0
0.45
#44bm33
0.42
255
15.0 1255 ihe
GPCA:
GPOK main
GPOK main
0.54
0.32
0.50
1.25
025
0.00
025
1.00
Mfp-
-1
Figure 17: Empirical results of the league-style algorithm for each category of GPQA.
Results for each category of GPQA and MMLU-Pro-S. Figure 17 includes empirical results of the stague-style algorithm for each category of GPQA, while Figures 18 and 19 include those for MMLU-Pro-S.
32

---

14 Pro-S:
Nelogy
HN-L-PO-S Melogy
MHLU-PO-S Melogy
0..4
0.37
0.35
0.38
100
2.73
100
100
hr
WMLU-Poo: Business
WMLL-too: Dusiness
HMLL-Ph--: Dusiness
0.30
05-
05-
0..5
0.50
0.32
-65-
-65
0.20
28 LUrI5 -..ra.1 Road
255
53
33.0 32.5 150
-0-4
0.00 0.5
6.5
An
-1-4--46
110
-(-3
0.00
025
6.9
-1-
160
-f1--112
0:50
625
1:00 fim
6:
M9B1:Pro-S cheristry
NNLURRO chemisty
NMLURPO chembsty
HNLL-Pro chemisty
10 32
10- 435x001111
0.50
0.
00
00
0.20
0.50
1a. lit
Aor
NMLL--P computer science
HMU computer science
HMU computer science
0.70
0.28
0.72
35.0 12.5
0.00
022
0.30
Anr
275
100
0.00
025
0.00
275
100
0.00
025
0.30
100 frm
375
WNLLI-Prro eccnomis
MHU: esonomics
NHU Pro economics
NHW Pro coonomics
0.411
0.75
-03
0.203
50
15, 180
125
150
Fur
HPIutPrre:: engineerin
PNU-Pro engineering
MMU- engineerin
engineering
P10031-
0.6
0.55
-10
-10
-10
325
2.7
100
0.00
372
100
0.0
150
S:
MULUP health
MPLUPo- healt
MALLL-o- heaks
05
0.5
0.20
-05
-05
-03
10 LirrnC3 O.te2.5 Maod
Mia lie
0.00
0.55
6.50
1.00
11
56
#f---1112
0.00
0.25
Fam
6.50
2.7%
-
1.00
11-5
#fy--1-11
0.00
625
Fmr
3.7
1.00
21
Figure 18: Empirical results of the league- algorithm for each category of MMLU-Pro-S (Part 1).
33

---

Pro Mitory
KiMattry
0.28
0..0
0.70
100
2.73
100
100
Pre
MMLU-me- kW
MOLU law
MOLUP law
0.50
0.-
05-
05-
0.54
-65
0.52
Omar2.1 Hoad
2.5
53
13.0 32.5
150
0.00 0.5
6.50
-1--1112 11-13
1.0
0.00 625
6.90
1:0
0:50 825
-1--1
1:00
WHW Pro math
WHW Pro math
MMW Pro math
10
10
10
03
00
00
0.50
0.15
2.5
75
360
125
150
WMLL-Pro-S: other
PML--- other
MM---- other
P10031-1
0.00
Lltnn333 O.0r2.1 Mool
0.59
125
0.00
022
0.30
275
100
0.00
022
0.00
275
100
-11-5
0.00
025
0:30
2.7
150
VNILL-PRo- philoupphy
HML Pro Milosophy
MMLU Pro S: Milosophy
MALU Pro S: Milessphy
0.50
0.95
-03
0:47
Lameh1 Ower2
220 Ra Lie
#fa Anr -1
Fam
NNLU Pro chyses
shysics
physice
physice
PAb03
0.20
0.24
0.20
-10
-10
-10
325 158
100
0:50
3.75
100
0.0
110
saycho agy
Pross paychology
KMLL paychology
PMLL-Pro: poychology
0..54
0.
0.5
05-
0.77
0.78
-05
-05
-03
0.25
12.1
0.00
1.00
11
C
#f--11-12
0.00
0.25
Fam
2.70
- 11-17
1.00
#fy--117
0.00
625
3.75
110--1--00
1.00
Figure 19: Empirical results of the league- algorithm for each category of MMLU-Pro-S (Part 2).
34

---

Table 1: The adopted prompt template for generating candidate solution.
% System prompt Please read the following multiple-chin questions provide the most likely answer based on the options given.
correct
% User prompt Question
[qestiio]] ]
Output Format
<reason>your step-by-step reasoning, process </reaso>>
<answer>"the tthe answer is (X)" where X is the correct letter choice</answer>>
Table 2: The adopted prompt template for pairwise comparison.
% System prompt
You are an impartial Judge. Given a question and two candidate solutions your task to choose which solution answer the question better Your judgment should be unbiased, without favoring either Solution I or 2.
User prompt QUESTION
qquestion] }
Solution
(candidate_a]
Solution 2
ccandidate b)
OUTPUT FORMAT
ccompare>compare both candidate solutions -tep-by-step thoroughly, and double check if there mistakes in either solution </compare> <winner-Solution or Solution or Tiez/winner>
35


Reviews:
[{"review_id": "GWP5aNahfM", "reviewer": "Reviewer_PgPW", "summary": "The paper proposes and studies two algorithms for provable scaling laws for the test-time compute. The first algorithm, the two-stage knockout-style algorithm, first generates multiple candidate solutions and then aggregate them via knockout tournament. The second algorithm, the two-stage league-style algorithm, first generate multiple candidates and then each candidate is evaluated by its average win rate against multiple opponents. The authors prove scaling laws with respect to test-time compute and run empirical experiments to validate the proposed theories.", "questions": "I am mainly concerned about the assumptions. I will raise my score if the authors can well-justify the assumptions. Specifically, the authors claim the drawback of BoN is requirement of a perfect verifier while the assumption the authors require for their proposed algorithms also implies a perfect verifier. Although the “perfectness” assumption can be relaxed for two-stage  league-style algorithm, this still is a strong assumption. It just changes what we mean by “perfectness”. Although two-stage league-style algorithm is more robust, adversarial candidate should still be able to break the assumption.\n\nAlso, regarding definition 1.1, the authors define the concept of provable inference scaling law to a specific input problem. So, this property of provable inference scaling law is not only a property of the algorithm but also a property of a specific input data. I feel this definition that includes the data is less useful than a definition that does not involve the data.", "limitations": "The authors have included a limitation section.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Overall, the idea of provable scaling laws for test-time compute is interesting. The experiments result also demonstrate that the proposed algorithms outperform baseline methods such as majority voting. However, I am concerned about the assumptions. Assumption 2.1 and assumption 3.1 are quite strong. \n\nFor example, I see assumption 2.1 technically the same as having a perfect reward model. The reason is that it requires that the large language model can distinguish the right solution to ALL the incorrect solutions. However, as one scales up more candidates, it is likely that there might be an adversarial solution that can fool the LLM (the same failure mode of BoN) which results in $p_{comp}$ smaller than 0.5. \n\nIndeed, the authors find in experiments that there are quite some inputs that do not satisfy this assumption (Fig 3 and Fig 5) and as a result, there is no provable scaling law for those problems. Additionally, for MATH-500 results in Fig. 6, the results suggest that the know-out algorithm does not have a provable inference scaling law for this dataset.\n\n\nAdditionally, I am concerned about the comparison between the proposed algorithms and the baseline of majority voting. Specifically, the authors only count the compute to generate the candidates but neglect the compute for aggregation. This is an unfair comparison as the authors use CoT for aggregation and as a result the compute for aggregation is non-trivial and should be accounted for.", "was_revised": true, "final_justification": "My primary concern remains with the assumptions presented. While I agree with the authors that these assumptions are weaker compared to those required by BoN, they are still quite strong, and the improvement over BoN is relatively minor. Nonetheless, the authors have effectively clarified my other concern regarding the fairness of their comparison. Additionally, their proposed revisions to the wording surrounding the assumptions have improved the paper's clarity and rigor. Consequently, I have raised my score accordingly.", "rebuttal": "Thank you for your thoughtful and constructive review! \nWe address your questions and concerns in the following.\n\n\n---\n\n\n# Concerns about Assumptions 2.1 and 3.1\n\n\nThank you for pointing out some limitations of the proposed assumptions, which helps enhance our understanding of them.\nOne of our objectives in this work is to push forward the boundary of our knowledge about what sufficient and/or necessary conditions make provable inference scaling laws possible.\nThis work presents our best progress so far, and with some theoretical insights, we have developed algorithms that indeed perform well empirically.\nNonetheless, we do acknowledge that the proposed assumptions (as sufficient conditions for theoretical guarantees) can still look strong from a more practical perspective, and it would be intriguing future work to further relax the assumptions for provable inference scaling laws.\n\n\n## Justification: why the proposed assumptions improve upon what is required by BoN\nThe reviewer points out that Assumptions 2.1 and 3.1 can be fragile and broken by a single adversarial candidate solution, \nakin to the case of BoN.\nWe agree that this is indeed a limitation of the proposed assumptions, and plan to revise the manuscript (which will soon be elaborated) to better reflect this.\n\nMeanwhile, we also believe that Assumptions 2.1 and 3.1, as sufficient conditions for the provable success of our proposed algorithms, are strictly weaker than what is required by BoN.\nThe key lies in the difference between *pointwise verification/scoring* and *pairwise comparison*.\nIt is widely believed that the latter is typically much easier and more accurate than the former,\nsupported by common practice and extensive empirical evidence.\n\nWe claim that this should be true in theory as well;\nin particular, \"no adversarial candidate exists for BoN\" implies \"no adversarial candidate exists for the knockout algorithm\", but the reverse is not necessarily true.\nTo see this, note that a naive bottomline for pairwise comparison would be simply to verify/score each candidate within the pair separately (in a pointwise manner), and then compare the results to select the winner.\nIn this case, it is easy to check that if BoN enjoys success guarantees, then so does the knockout algorithm.\nAs for the reverse direction of the above claim, note that pairwise comparison allows putting two candidate solutions side by side within the prompt, which is *strictly more informative* than looking at either candidate alone (as done in pointwise verification for BoN).\n\nAnother benefit of our proposed assumptions is their probabilistic nature.\nThis allows the proposed algorithms to amplify the success probability up to 1, while tolerating (a possibly massive number of) errors in comparing pairs of candidate solutions, as can be seen from the proofs of Theorems 2.3 and 3.2.\n\n\nGiven the above, we believe that the proposed Assumptions 2.1 and 3.1, despite their limitations, contribute to enriching our knowledge about what conditions make provable inference scaling laws possible.\n\n\n\n## Tentative revisions\n\nMotivated by your feedback, we plan to make the following revisions to make the strengths and limitations of Assumptions 2.1 and 3.1 clearer to the readers:\n\n- In Line 58, we will replace \"two natural (and arguably minimal) assumptions\" with simply \"two assumptions\".\n\n- In Lines 64 - 65 (the second paragraph of \"main contributions\" in introduction), we will add one sentence to state our assumption for the league algorithm more explicitly: \"there exist correct solutions whose average win rates against a distribution of opponents are higher than that of any incorrect solution\".\n\n- In Line 71, we will slightly rephrase the last sentence of introduction, to faithfully acknowledge the gap between theory and practice. A tentative version is as follows: \"Although the technical assumptions in our theories can seem strong from a more practical perspective, our empirical results confirm that the proposed algorithms, developed based on the theoretical insights, indeed perform well and demonstrate outstanding scaling properties across diverse LLMs and datasets.\"\n\n- In Lines 112 - 114 (following the statement of Assumption 2.1), we will remark that $p_{comp} > 0.5$ is assumed for any pair of solutions, which is a strong assumption and thus will motivate our development of the league algorithm (and its theory) in the next section. Such a remark indeed resembles the beginning of Section 3 in the current manuscript.\n\n- In Lines 177 - 181 (following the statement of Assumption 3.1), we will remark that Assumption 3.1 precludes the existence of an adversarial, incorrect candidate that achieves a higher average win rate than any correct solution does.\n\nWe'd love to hear your feedback on whether any further improvement can be made.\n\n---\n\n\n# Other concerns\n\n\n**In experiments, there are problems that do not satisfy the assumptions, and the algorithms do not achieve provable inference scaling laws on such problems or datasets.**\n\nWe believe that this is reasonable and well expected, since there are always *counterexamples* to an *assumption*.\nThis is also true for other methods like majority voting or Best-of-N, \nwhose provable inference scaling laws rely on assumptions that fail on certain problems and datasets in reality\n(cf. Lines 42 - 52, Lines 338 - 349, and the references therein).\n\nIndeed, a large part of our empirical study has been dedicated to understanding the empirical success and failure of the proposed algorithms, and in particular, to what extent the proposed technical assumptions hold true in reality.\nThis includes Lines 251 - 308 for the knockout algorithm, Lines 316 - 328 for the league algorithm, and the corresponding figures of experiment results.\nFor example, if a problem (e.g., \"solve the P versus NP problem\") is simply beyond the LLM's capabilities, then the LLM will effectively have $p_{gen} = 0$ or $p_{comp} \\le 0.5$ on this problem, which violates Assumption 2.1 required by Theorems 2.2 and 2.3.\nIn such cases, it is no surprise that the knockout algorithm (or other test-time scaling methods) fails to solve this problem.\n\n\n\n**The concept of \"provable inference scaling law\" in Definition 1.1 is not only a property of the algorithm but also of the input problem, which feels less useful than a definition that does not involve the data.**\n\nTo the best of our understanding, \ninvolving the data (i.e., input problem) in the formal definition of \"provable inference scaling law\" is reasonable and perhaps inevitable.\nAfter all, given the capabilities and limitations of today's LLMs, we do not expect that there exists an LLM-based algorithm that can solve *any* possible input problem by scaling up its test-time compute.\nIn other words, the feasibility of a provable inference scaling law must rely on certain assumptions not just about the LLM and algorithm, but also about the input problem.\nWe are uncertain about what a definition that doesn't involve the data should look like,\nand would appreciate further hints on this aspect.\n\n\n\n**Comparison between the proposed algorithms and the baseline of majority voting, \"the authors only count the compute to generate the candidates but neglect the compute for aggregation\".**\n\nWe would like to clarify that **the costs of both generation and aggregation stages have been taken into account in our comparison** between the knockout algorithm and majority voting, although we choose to use $N$ as the X-axis in Figure 2 for clean visualization.\nIn particular, we highlight in **Line 244** that the knockout algorithm requires a total of $5 \\times N$ or $3 \\times N$ (depending on the experiment settings) LLM calls for solving a problem, while majority voting requires only $N$ LLM calls;\nto improve the clarity of our presentation, we plan to add this message to the caption of Figure 2 in our revision.\nEven when using the total number of LLM calls (rather than $N$) as the cost metric,\nthe knockout algorithm still demonstrates advantages over majority voting in terms of convergence speed and ceiling of the accuracy curves,\nas explained in **Lines 246 - 250**.\n\n\n\n\n\n---\n\nThank you again for your review, which helps us a lot in improving the current work!\nWe hope that our responses have provided satisfactory answers to your questions,\nbut do let us know if you have any further concern that we can address."}, {"review_id": "G2IWaiSVux", "reviewer": "Reviewer_fB8B", "summary": "The authors propose two knockout style algorithms to improve the likelihood of generating a correct answer from a large language model. \nIn the first algorithm they generate N possible answers and then select the winner through a bracket tournament system where a judge model picks a winner by performing repeated pairwise comparison.\nIn the second algorithm, each generated answer gets compared against K other randomly selected answers and the answer with the highest average winrate gets picked.\nThe authors then prove probabilistic success guarantees for both algorithms as N & K are scaled under simple theoretical assumptions.\nFinally, they show that their algorithm improves the success rate of LLMs across three multiple choice datasets.", "questions": "- As noted in the weaknesses above I would have liked to have seen a further acknowledgement that the assumptions are quite strong in practice earlier in the paper. I think this would take the paper from a weak accept to an accept for me.\n- Did you investigate the possiblity of the existance of \"strong-and-incorrect\" candidates in your empirical evaluation? If so could you add some discussion about this in the paper?\n- I'm quite interested in the results of MMLU-Pro-S philosophy shown in figure 4, where it seems that increasing N can be actively harmful to accuracy for certain models, how robust is this result? Is this simply because the dataset is quite small and thus quite noisy or is this a reliably reproducible result?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n - The proposed algorithms are very simple/elegant and thus easy to implement\n - The paper clearly outlines a compelling reason for why this method would work\n - The authors provide formal guarantees which aren't often available for LLMs\n - The empirical evaluation section is thorough and left me convinced that this method significantly improves the performance of models on multiple choice tasks.\nWeaknesses:\n - The assumptions the authors make for both of their algorithms are much stronger than they might initially appear.\n    1. For the bracket algorithm the assumption of p_comp > 0.5 is key to the exponentially decaying rate as we scale N & K, but this assumption is implausible unless the success probabilities from the judge model are independent of each other as the candidate solutions are varied.\n    2. For the two-stage league-style algorithm the authors assume the existence of \"correct-and-strong\" answers whose expected winrate score when compared to the expected winrate of incorrect algorithms is greater than 0. But if a single \"incorrect-and-strong\" answer exists in the candidate generation set then the proof no longer works.\nThe paper would be significantly improved if the authors made the limitations of these assumptions much clearer earlier on in the paper.\n- I would have liked to have seen error bars for each of the datapoints in the scaling plots to get a better idea of the variance of these results, especially for figures that represent smaller datasets.", "was_revised": true, "final_justification": "Authors successfully addressed all my questions and concerns so raising score to accept.", "rebuttal": "Thank you for your thoughtful and constructive review! \nWe address your questions and concerns in the following.\n\n\n---\n\n\n**Suggestion: \"The paper would be significantly improved if the authors made the limitations of these assumptions much clearer earlier on in the paper.\"**\n\n\nThank you for pointing out some limitations of the proposed assumptions, which helps enhance our understanding of them.\nWe acknowledge that these assumptions, as sufficient conditions for provable success of the proposed algorithms in theory, can still look strong from a more practical perspective.\nIt would be intriguing future work to push forward the boundary of our knowledge about what sufficient and/or necessary conditions make provable inference scaling laws possible.\n\n\nFollowing your suggestion, we plan to make these revisions to the current work:\n\n- In Line 58, we will replace \"two natural (and arguably minimal) assumptions\" with simply \"two assumptions\".\n\n- In Lines 64 - 65 (the second paragraph of \"main contributions\" in introduction), we will add one sentence to state our assumption for the league algorithm more explicitly: \"there exist correct solutions whose average win rates against a distribution of opponents are higher than that of any incorrect solution\".\n\n- In Line 71, we will slightly rephrase the last sentence of introduction, to faithfully acknowledge the gap between theory and practice. A tentative version is as follows: \"Although the technical assumptions in our theories can seem strong from a more practical perspective, our empirical results confirm that the proposed algorithms, developed based on the theoretical insights, indeed perform well and demonstrate outstanding scaling properties across diverse LLMs and datasets.\"\n\n- In Lines 112 - 114 (following the statement of Assumption 2.1), we will remark that $p_{comp} > 0.5$ is assumed for any pair of solutions, which is a strong assumption and thus will motivate our development of the league algorithm (and its theory) in the next section. Such a remark indeed resembles the beginning of Section 3 in the current manuscript.\n\n- In Lines 177 - 181 (following the statement of Assumption 3.1), we will remark that Assumption 3.1 precludes the existence of an adversarial \"incorrect-but-strong\" candidate that achieves a higher average win rate than any correct solution does.\n\nWe hope that these will make the strengths and limitations of Assumptions 2.1 and 3.1 clearer to the readers,\nand we'd love to hear your feedback on whether any further improvement can be made.\n\n\n**Question: \"Did you investigate the possibility of the existence of \"incorrect-and-strong\" candidates in your empirical evaluation? If so could you add some discussion about this in the paper?\"**\n\nYes, we have seen such candidates in our experiments.\nRecall that in Lines 318 - 320, we define $\\hat{\\Delta}$ as the difference between the empirical average win rate of the strongest correct candidate, and that of the strongest incorrect candidate.\nThe scatter plot in Figure 5, as well as those in Appendix D.3, indicates the existence of problems with $\\hat{\\Delta} < 0$;\nin other words, for each of these problems, there exists an incorrect-but-strong candidate that achieves a higher average win rate than any correct candidate does.\n\nWe will add a discussion in the paragraph of Lines 322 - 328 about this, to explain that the existence of incorrect-but-strong candidates (which violates Assumption 3.1) prevents the league algorithm from boosting the accuracy up to 100% on a dataset, similar to the case of the knockout algorithm that has been discussed in Lines 251 - 291.\n\n\n**Question: error bars for each datapoint in the scaling plots?**\n\n\nDue to the high computational or monetary costs of the experiments,\nwe have run the knockout or league algorithm only once for each (model, dataset) combination,\nwhich prevents us from plotting error bars in the scaling plots.\nNonetheless, we have made our best efforts to enhance the stability and reliability of the plots in the manuscript:\n\n- For the knockout algorithm, we take advantage of its binary tree structure (shown in Figure 1).\nFor example, after running the algorithm once with N=64, we automatically get the results of 64 independent trials for N=1, 32 trails for N=2, 16 trials for N=4, and so on.\nWe have thus taken the average of accuracy values from multiple independent trials for each datapoint (except for the rightmost one) in each scaling curve.\n\n- This is also true for the league algorithm.\nFor example, after running the algorithm once with N=16, we are able to obtain the results of multiple trials for N=8 (or any value smaller than 16), \neach corresponding to 8 randomly sampled candidate solutions and the comparison results among them.\nEach datapoint (except for the rightmost one) in each scaling curve has been calculated by an average of multiple results obtained this way.\n\n\n**Question: how robust is the result for MMLU-Pro-S Philosophy shown in Figure 4?**\n\n\nFigure 4 indeed suggests that increasing N can be harmful for Qwen2.5 on a 100-question subset (cf. Line 207) of MMLU-Pro-Philosophy.\nTo see whether this is a robust and reproducible result,\nwe conduct an experiment on the full MMLU-Pro-Philosophy set, which contains 499 questions, during the rebuttal period.\nThe result demonstrates a similar trend, as shown in the following table:\n\n| N                                 | 1 | 2 | 4 | 8 | 16 | 32 | 64 |\n| --- | --- | --- | --- | --- | --- | --- | --- | \n| Accuracy by knockout             | 0.630 | 0.630 | 0.632 | 0.630 | 0.627 | 0.621 | 0.615 |\n| Accuracy by majority      | 0.630 | 0.629 | 0.633 | 0.635 | 0.632 | 0.632 | 0.627 |\n\nAs discussed in Lines 306 - 308, our intuition for this phenomenon is that pairwise comparisons among candidate solutions might bring limited benefits for knowledge-heavy questions that mostly require correct memorization of relevant knowledge.\nThe corresponding scatter plot in Figure 13 (5th row, 3rd column) indeed shows that there are slightly more problems with $\\hat{p}_{comp} < 0.5$ than with $\\\\hat{p}_{comp} > 0.5$ for Qwen2.5 on the MMLU-Pro-Philosophy subset.\n\n    \n\n\n\n---\n\nThank you again for your review, which helps us a lot in improving the current work!\nWe hope that our responses have provided satisfactory answers to your questions,\nbut do let us know if you have any further concern that we can address."}, {"review_id": "jEVcEq6t5A", "reviewer": "Reviewer_SKdM", "summary": "The authors propose two theoretically grounded test-time inference scaling algorithms: knockout-style and league-style, which are designed to improve the reasoning accuracy of LLMs under increased computational budgets. Theoretical analyses demonstrate that, under the assumptions that the LLM has a non-zero probability of generating a correct solution and can make pairwise comparisons better than random guessing, the failure probability of both algorithms decreases exponentially or polynomially as test-time compute increases.", "questions": "Please see weakness.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n\n1. The paper presents two inference scaling algorithms with rigorous theoretical guarantees, demonstrating solid theoretical foundations.\n2. The proposed methods rely solely on a black-box LLM, requiring no external verifier or reward model, which simplifies implementation.\n3. The paper is clearly written and well-structured.\n\nWeaknesses\n\n1. The citation at line 30 appears abrupt and lacks sufficient explanation or context.\n2. It is unclear how the authors determine the values of N and K. What are the implications for time efficiency in real-world applications?\n3. The paper does not seem to compare against strong baseline methods. Are there no suitable test-time inference scaling approaches available for comparison?\n4. The datasets used in the experiments are mostly multiple-choice question types. Are there evaluations on other types of tasks?\n5. The paper lacks an in-depth failure case analysis. For example, why do some problems remain unsolved even when more candidates are generated?\n6. What is the difference between the proposed knockout-style algorithm and the BoN sampling method?", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and constructive review! \nWe address your questions and concerns in the following.\n\n\n---\n\n\n\n**Question 1: The citation at line 30 appears abrupt and lacks sufficient explanation or context.**\n\nThank you for pointing this out.\nWe will divide the cited papers into smaller sub-categories and provide more context about this line of literature in our revision.\n\n---\n\n**Question 2: It is unclear how the authors determine the values of N and K. What are the implications for time efficiency in real-world applications?**\n\n\n**In terms of experiments:**\nDetailed explanations for the choices of N and K in our experiments can be found in Lines 223 - 226,\nwhich we reiterate in the following.\nFor the knockout algorithm, we fix K at a small value (2 or 4), and scale up N alone;\nthe total number of LLM calls thus grows linearly with N.\nFor the league algorithm, we scale up N and mostly adopt a round-robin setting where each candidate is compared against all other candidates, leading to a total of $O(N^2)$ LLM calls;\nnonetheless, our experiment results in Lines 329 - 336 (as well as Theorem 3.2) also confirm that it is feasible to use a significantly smaller number of opponents (thus fewer LLM calls) while maintaining accuracy.\n\n\n**In terms of methodology and theory:**\nFor the knockout algorithm, our general recommendation is scaling up N alone while fixing K at a small value (mainly to account for the positional bias of LLMs and to cover multiple LLMs if a mixture of them is used in the algorithm), which is backed by Theorem 2.3.\nFor the league algorithm, our general recommendation is scaling up N alone and adopting the round-robin setting for simplicity, although it is certainly feasible to tune down the number of opponents for better efficiency.\nIn practice, one may scale up N until a given budget is met, or use the \"anytime\" variants of the proposed algorithms that can automatically adapt to the compute budget unknown a priori (cf. Lines 627 - 640).\n\nIt is also worth noting that the LLM calls in either algorithm are highly parallelizable (as explained in Lines 147 - 156 for knockout, and Lines 170 - 171 for league), hence the wall-clock latency can substantially benefit from parallel computation.\n\n---\n\n**Question 3: The paper does not seem to compare against strong baseline methods. Are there no suitable test-time inference scaling approaches available for comparison?**\n\nGiven the vast literature on test-time scaling techniques, \nwe have chosen to focus our attention on methods that are\n(1) within the category of \"repeated sampling and then aggregation\" (as explained in Lines 28 - 31), and\n(2) foundational and broadly applicable to generic tasks, rather than task-specific.\nTo the best of our knowledge, majority voting (or \"self-consistency\") and Best-of-N are the most prominent approaches satisfying these conditions, and they are most widely adopted in benchmarking LLMs.\nFurthermore, as discussed in Lines 349 - 351, we refrain from comparing our methods with BoN in our experiments, since introducing an external verifier or reward model will bring extra variability that makes it difficult to conduct a fair and meaningful empirical comparison.\nThis leaves us with majority voting as the only suitable baseline for our empirical study.\n\n---\n\n\n**Question 4: The datasets used in the experiments are mostly multiple-choice question types. Are there evaluations on other types of tasks?**\n\nWe choose to stick with multiple-choice or math questions in the current work, for the purpose of \n(1) unambiguous and objective evaluation, and (2) controllable computational costs of experiments.\nWe hope that our work will inspire the community to try out the proposed algorithms in more diverse tasks, although this is beyond the scope of our current focus in this work.\n\n\n---\n\n**Question 5: The paper lacks an in-depth failure case analysis. For example, why do some problems remain unsolved even when more candidates are generated?**\n\nIndeed, a large part of our empirical study has been dedicated to understanding the empirical success and failure of the proposed algorithms, and in particular, to what extent the proposed technical assumptions hold true in reality.\nThis includes Lines 251 - 308 for the knockout algorithm, Lines 316 - 328 for the league algorithm, and the corresponding figures of experiment results.\nFor example, if a problem (e.g., \"solve the P versus NP problem\") is simply beyond the LLM's capabilities, then the LLM will effectively have $p_{gen} = 0$ or $p_{comp} \\le 0.5$ on this problem, which violates Assumption 2.1 required by Theorems 2.2 and 2.3.\nIn such cases, it is no surprise that the knockout algorithm (or other test-time scaling methods) fails to solve this problem.\n\n\n---\n\n\n**Question 6: What is the difference between the proposed knockout-style algorithm and the BoN sampling method?**\n\nBoth methods initially generate multiple candidate solutions.\nThe difference lies in the aggregation stage that returns a final output.\nBoN uses an external verifier or reward model to score each candidate independently, and then pick the one with the highest score.\nIn contrast, the knockout-style algorithm conducts a series of pairwise comparisons among the candidates; this is largely motivated by the common belief (which is backed by extensive empirical evidence) that it is typically much easier to compare a pair of solutions than to assign an accurate absolute score for each individual solution.\n\n\n\n\n---\n\nThank you again for your review, which helps us a lot in improving the current work!\nWe hope that our responses have provided satisfactory answers to your questions,\nbut do let us know if you have any further concern that we can address."}, {"review_id": "eZgXo9uvGN", "reviewer": "Reviewer_NB6t", "summary": "This paper considers scaling laws for test-time compute. In particular, the paper proposes two algorithms to bound the probability that LLMs generate a wrong answer to problems under certain assumptions. The authors provide experiments on multiple choice and math questions to test their algorithms.", "questions": "- A algorithm environment describing the algorithm in Section 3 would be helpful.\n- What would be some more natural examples when Assumption 3.1 hold, beyond what is discussed in Appendix C? In particular, correct and strong vs correct and weak.\n- What's the intuition that we need a separate correct-but-weak set? It's not used in the proof of the Theorem 3.2 in the appendix.\n- Assumption 3.1 by itself does not seem to be sufficient to guarantee that the algorithm will fail to choose a correct answer with (exponentially small) vanishing probability. Inherently, there should be an assumption quantifying the win rate between a correct and strong vs a correct and weak answer. It seems be possible such that with constant probability, a correct but weak answer is chosen. Consider the following realistic analogy where the goal is to consider the correctness of proofs (answers) to theorems (questions). Letting an undergrad student be the \"aggregator\" (who can identify incorrectness, but cannot identify a weak vs a strong answer and thus gives ties to these matches) will yield constant probability of weak answers. The scenario considered in the paper seems to implicitly assume a stronger aggregator who can identify between the three sets (and thus is not black-box).\n- Can experiments be provided for larger values of N, e.g. for Figure 3? The current results don't indicate the exponential decay of failure as backed by the experiments.\n\nThe fourth point is my major concern in the paper and I may be wrong, but clarifying it will raise my score in the positive light.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The results are backed by complete proofs and experiments.\n- The paper is well-written and discussion is well-motivated.\n\nWeaknesses:\n- I think the title is a little misleading because the connection with \"scaling laws\" is rather loose. In particular, the main contribution is introducing algorithms to boost the success rates of LLMs.\n- The algorithms and their corresponding theoretical results aren't surprising. For instance, ideas in Section 2 are reminiscient of boosting the success rate of BPP algorithms. Nonetheless, the originality is imposing seemingly reasonable assumptions that apply to LLMs.\n- Assumption 3.1 is not motivated very well. Also see the questions below.", "was_revised": true, "final_justification": "The authors provided a thorough response and addressed all of my concerns on Assumption 3.1, so I increased my score. I recommend acceptance, and hope the authors will add this additional clarification on the assumptions to the paper.", "rebuttal": "Thank you for your thoughtful and constructive review! \nWe address your questions and concerns in the following.\n\n\n---\n\n\n# Questions about Assumption 3.1\n\nThank you for raising the questions about Assumption 3.1, which indicates room for improvement in the clarity of our writing.\nLet us try to explain this assumption better.\n\n**Definitions of \"correct-and-strong\" and \"correct-but-weak\" solutions.**\n\nIn Assumption 3.1, a \"correct-and-strong solution\" $y$ is *defined as* a solution that not only contains a correct final answer, but also has a higher average win rate $\\mu_{y}$ against a distribution ($M_{gen}$) of solutions than any incorrect solution does.\nOn the other hand, a correct-but-weak solution contains a correct final answer, but we make no assumption about its average win rate against $M_{gen}$.\n\n**Is Assumption 3.1 sufficient for success guarantees of the league-style algorithm?**\n\nThe answer is yes.\nThe main intuition behind the proof of Theorem 3.2 is not about ensuring that the league algorithm will select a correct-and-strong solution as the final output (and this is indeed not guaranteed),\nbut rather about ensuring that any incorrect solution will not be selected.\nAnd this is true because, by definition, the average win rate (against $M_{gen}$) of any incorrect solution is lower than that of a correct-and-strong solution; \nwith sufficiently many samples, this is also true for the empirical estimates of average win rates.\n\nRemark 1: We can't say for sure whether the final output of the league algorithm is a correct-and-strong or correct-but-weak solution, since we make no assumption about the average win rate of the latter.\n\nRemark 2: In your review, you mention a potential failure case when a correct-but-weak solution wins with constant probability when competing against a correct-but-strong solution.\nThis is not necessarily an issue, since the league algorithm evaluates each candidate solution based on its overall comparison results against multiple opponents, rather than any single one.\n\n\n**Why do we need a separate correct-but-weak set?**\n\nThis is mostly because we want to relax as much as possible the technical assumptions required by provable success of the league algorithm.\nInstead of assuming \"any correct solution has a higher average win rate (against $M_{gen}$) than any incorrect solution does\", \nour final version of Assumption 3.1 says \"there exist correct solutions that have higher average win rates than any incorrect solution does\", while no assumption is imposed on other correct solutions.\n\n**Natural examples for correct-and-strong vs correct-but-weak solutions?**\n\nConsider a reasoning-focused (e.g., math or physics) multiple-choice question.\nA correct-and-strong solution contains not only a correct final answer (option A/B/C/D) but also a strong reasoning process.\nIn contrast, a correct-but-weak solution might contain a flawed reasoning process, but happens to arrive at the correct final answer by luck.\nIt is indeed funny that sometimes the LLM could conclude a flawed reasoning process with something like \"the result of my calculation is -5, and the options are (A) 100, (B) 200, (C) 300, (D) 400, so I would choose (A) because it is the closest to my calculation\".\nWe shouldn't expect such a correct-but-weak solution to have a high win rate against another (correct or incorrect) opponent, since the reasoning process in each candidate is taken into account when pairwise comparisons are conducted.\n\n---\n\nThank you again for raising the questions.\nWe hope that the above clarifications, which will be incorporated into the revised manuscript, have resolved your concerns regarding Assumption 3.1.\n\n---\n\n# Other questions and comments\n\n**Question about the title, and connection with \"scaling laws\".**\n\n\nIn this work, we adopt the general concept of \"inference scaling law\", that is,\n\"the performance of an LLM or LLM-based system keeps improving with more test-time compute\".\nDifferent metrics of \"performance\" have been adopted in the literature,\nsuch as accuracy on a dataset, or success rate on a specific problem; \nthe former is indeed equivalent to taking the average of success rates over the problems within a dataset.\nWe hope that this can explain why the current work is closely in line with the topic of \"inference scaling laws\".\n\n\n**Suggestion: \"An algorithm environment describing the algorithm in Section 3 would be helpful.\"**\n\nThank you for the suggestion. We will add one in our revision.\n\n\n\n**Question: \"Can experiments be provided for larger values of N, e.g. for Figure 3?\"**\n\n\nIn the manuscript, we have chosen the maximum values of N based on the computational resources available to us.\nFollowing your suggestion, we have extended the results in Figure 3 up to N=256 during the rebuttal period.\nBefore we present the updated results, we have to first admit that we mistakenly used the wrong plot for Figure 3 in the manuscript, and we promise to correct it in the revision.\n\nThe updated results on GPQA-subset for the \"Mixed\" option are shown in the following table.\nRecall that in the experiment for Figure 3, we first identify a subset of GPQA problems that the knockout algorithm achieves an estimated $\\\\hat{p}\\_{comp} > 0.5$ on,\nand then plot the accuracy curve for a new, independent trial of the algorithm on this subset.\nThe updated results in the first row of the table below show that accuracy of the knockout (KO) algorithm keeps improving with $N$ up to 256, although the trend eventually slows down.\nThis is not surprising, because $\\hat{p}\\_{comp} > 0.5$ is just a proxy for the condition $p\\_{comp} > 0.5$, and thus there still remain problems in GPQA-subset that violate Assumption 2.1.\nThis motivates us to further tighten the filtering condition, such as $\\hat{p}\\_{comp} > 0.6$ or $0.7$.\nThe results in this table confirm that the accuracy ceiling indeed gets higher on a problem subset that meets a stricter condition. \n\n\n| N | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | \n| $\\hat{p}_{comp} > 0.5$ subset, knockout | 0.556 | 0.657 | 0.700 | 0.728 | 0.752 | 0.766 | 0.782 | 0.786 | 0.797 |\n| $\\hat{p}_{comp} > 0.5$ subset, majority | 0.556 | 0.625 | 0.647 | 0.666 | 0.678 | 0.685 | 0.685 | 0.685 | 0.695 |\n| $\\hat{p}_{comp} > 0.6$ subset, knockout | 0.609 | 0.728 | 0.775 | 0.807 | 0.834 | 0.849 | 0.863 | 0.865 | 0.881 |\n| $\\hat{p}_{comp} > 0.6$ subset, majority | 0.609 | 0.698 | 0.718 | 0.735 | 0.745 | 0.752 | 0.749 | 0.747 | 0.755 |\n| $\\hat{p}_{comp} > 0.7$ subset, knockout | 0.657 | 0.788 | 0.837 | 0.871 | 0.893 | 0.907 | 0.917 | 0.926 | 0.931 |\n| $\\hat{p}_{comp} > 0.7$ subset, majority | 0.657 | 0.753 | 0.774 | 0.788 | 0.798 | 0.803 | 0.804 | 0.803 | 0.809 |\n| $\\hat{p}_{comp} > 0.8$ subset, knockout | 0.730 | 0.869 | 0.909 | 0.932 | 0.945 | 0.960 | 0.964 | 0.970 | 0.976 |\n| $\\hat{p}_{comp} > 0.8$ subset, majority | 0.730 | 0.841 | 0.862 | 0.877 | 0.894 | 0.900 | 0.905 | 0.899 | 0.899 |\n\n\n\n\n\n---\n\nThank you again for your review, which helps us a lot in improving the current work!\nWe hope that our responses have provided satisfactory answers to your questions,\nbut do let us know if you have any further concern that we can address."}]

Author rebuttal:

Meta-review: Test time compute is increasingly being used to improve the accuracy of LLMs. For example, a very simple method is to over-sample several possible answers, and then output the majority vote. This paper proposes two cleverer methods inspired by tournament scoring. Both methods involve having different answers "compete" with each other, with the winning answer moving onto the next round. In addition to providing experimental results, the paper analyzes the success probability of each method as the number of answers considered is increased.

Reviewers liked that the paper provides formal guarantees of the method's success rate, though they do note that the assumptions needed for these guarantees to be true are quite strong, and this limitation is not sufficiently addresses in the paper. The reviewers note that the empirical results are convincing, although there is some concern that the authors didn't choose enough baselines to compare against.

Overall, I think the proposed methods are interesting and the paper is enjoyable to read. I recommend its acceptance.

However, in their camera ready version, the authors should make sure to add a longer discussion of Assumptions 2.1 and 3.1 and their limitations.
Decision: Accept (poster)