Thank you for your thoughtful and constructive review! We address your questions and concerns in the following.

---

Questions about Assumption 3.1

Thank you for raising the questions about Assumption 3.1, which indicates room for improvement in the clarity of our writing. Let us try to explain this assumption better.

Definitions of "correct-and-strong" and "correct-but-weak" solutions.

In 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. On 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}$.

Is Assumption 3.1 sufficient for success guarantees of the league-style algorithm?

The answer is yes. The 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), but rather about ensuring that any incorrect solution will not be selected. And 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; with sufficiently many samples, this is also true for the empirical estimates of average win rates.

Remark 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.

Remark 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. This 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.

Why do we need a separate correct-but-weak set?

This is mostly because we want to relax as much as possible the technical assumptions required by provable success of the league algorithm. Instead of assuming "any correct solution has a higher average win rate (against $M_{gen}$) than any incorrect solution does", our 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.

Natural examples for correct-and-strong vs correct-but-weak solutions?

Consider a reasoning-focused (e.g., math or physics) multiple-choice question. A correct-and-strong solution contains not only a correct final answer (option A/B/C/D) but also a strong reasoning process. In contrast, a correct-but-weak solution might contain a flawed reasoning process, but happens to arrive at the correct final answer by luck. It 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". We 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.

---

Thank you again for raising the questions. We hope that the above clarifications, which will be incorporated into the revised manuscript, have resolved your concerns regarding Assumption 3.1.

---

Other questions and comments

Question about the title, and connection with "scaling laws".

In this work, we adopt the general concept of "inference scaling law", that is, "the performance of an LLM or LLM-based system keeps improving with more test-time compute". Different metrics of "performance" have been adopted in the literature, such as accuracy on a dataset, or success rate on a specific problem; the former is indeed equivalent to taking the average of success rates over the problems within a dataset. We hope that this can explain why the current work is closely in line with the topic of "inference scaling laws".

Suggestion: "An algorithm environment describing the algorithm in Section 3 would be helpful."

Thank you for the suggestion. We will add one in our revision.

Question: "Can experiments be provided for larger values of N, e.g. for Figure 3?"

In the manuscript, we have chosen the maximum values of N based on the computational resources available to us. Following your suggestion, we have extended the results in Figure 3 up to N=256 during the rebuttal period. Before 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.

The updated results on GPQA-subset for the "Mixed" option are shown in the following table. Recall 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, and then plot the accuracy curve for a new, independent trial of the algorithm on this subset. The 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. This 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. This motivates us to further tighten the filtering condition, such as $\hat{p}\_{comp} > 0.6$ or $0.7$. The results in this table confirm that the accuracy ceiling indeed gets higher on a problem subset that meets a stricter condition.

---

Thank you again for your review, which helps us a lot in improving the current work! We hope that our responses have provided satisfactory answers to your questions, but do let us know if you have any further concern that we can address.

Thank you for your thoughtful and constructive review! We address your questions and concerns in the following.

---

Question 1: The citation at line 30 appears abrupt and lacks sufficient explanation or context.

Thank you for pointing this out. We will divide the cited papers into smaller sub-categories and provide more context about this line of literature in our revision.

---

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?

In terms of experiments: Detailed explanations for the choices of N and K in our experiments can be found in Lines 223 - 226, which we reiterate in the following. For the knockout algorithm, we fix K at a small value (2 or 4), and scale up N alone; the total number of LLM calls thus grows linearly with N. For 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; nonetheless, 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.

In terms of methodology and theory: For 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. For 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. In 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).

It 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.

---

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?

Given the vast literature on test-time scaling techniques, we have chosen to focus our attention on methods that are (1) within the category of "repeated sampling and then aggregation" (as explained in Lines 28 - 31), and (2) foundational and broadly applicable to generic tasks, rather than task-specific. To 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. Furthermore, 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. This leaves us with majority voting as the only suitable baseline for our empirical study.

---

Question 4: The datasets used in the experiments are mostly multiple-choice question types. Are there evaluations on other types of tasks?

We choose to stick with multiple-choice or math questions in the current work, for the purpose of (1) unambiguous and objective evaluation, and (2) controllable computational costs of experiments. We 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.

---

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?

Indeed, 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. This includes Lines 251 - 308 for the knockout algorithm, Lines 316 - 328 for the league algorithm, and the corresponding figures of experiment results. For 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. In such cases, it is no surprise that the knockout algorithm (or other test-time scaling methods) fails to solve this problem.

---

Question 6: What is the difference between the proposed knockout-style algorithm and the BoN sampling method?

Both methods initially generate multiple candidate solutions. The difference lies in the aggregation stage that returns a final output. BoN uses an external verifier or reward model to score each candidate independently, and then pick the one with the highest score. In 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.

---

Thank you again for your review, which helps us a lot in improving the current work! We hope that our responses have provided satisfactory answers to your questions, but do let us know if you have any further concern that we can address.

Thank you for your thoughtful and constructive review! We address your questions and concerns in the following.

---

Suggestion: "The paper would be significantly improved if the authors made the limitations of these assumptions much clearer earlier on in the paper."

Thank you for pointing out some limitations of the proposed assumptions, which helps enhance our understanding of them. We 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. It 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.

Following your suggestion, we plan to make these revisions to the current work:

• In Line 58, we will replace "two natural (and arguably minimal) assumptions" with simply "two assumptions".

• 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".

• 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."

• 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.

• 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.

We hope that these will make the strengths and limitations of Assumptions 2.1 and 3.1 clearer to the readers, and we'd love to hear your feedback on whether any further improvement can be made.

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?"

Yes, we have seen such candidates in our experiments. Recall 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. The scatter plot in Figure 5, as well as those in Appendix D.3, indicates the existence of problems with $\hat{\Delta} < 0$; in 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.

We 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.

Question: error bars for each datapoint in the scaling plots?

Due to the high computational or monetary costs of the experiments, we have run the knockout or league algorithm only once for each (model, dataset) combination, which prevents us from plotting error bars in the scaling plots. Nonetheless, we have made our best efforts to enhance the stability and reliability of the plots in the manuscript:

• For the knockout algorithm, we take advantage of its binary tree structure (shown in Figure 1). For 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. 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.

• This is also true for the league algorithm. For 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), 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.

Question: how robust is the result for MMLU-Pro-S Philosophy shown in Figure 4?

Figure 4 indeed suggests that increasing N can be harmful for Qwen2.5 on a 100-question subset (cf. Line 207) of MMLU-Pro-Philosophy. To see whether this is a robust and reproducible result, we conduct an experiment on the full MMLU-Pro-Philosophy set, which contains 499 questions, during the rebuttal period. The result demonstrates a similar trend, as shown in the following table:

As 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. The 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.

---

Thank you again for your review, which helps us a lot in improving the current work! We hope that our responses have provided satisfactory answers to your questions, but do let us know if you have any further concern that we can address.

Thank you for your thoughtful and constructive review! We address your questions and concerns in the following.

---

Concerns about Assumptions 2.1 and 3.1

Thank you for pointing out some limitations of the proposed assumptions, which helps enhance our understanding of them. One 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. This work presents our best progress so far, and with some theoretical insights, we have developed algorithms that indeed perform well empirically. Nonetheless, 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.

Justification: why the proposed assumptions improve upon what is required by BoN

The reviewer points out that Assumptions 2.1 and 3.1 can be fragile and broken by a single adversarial candidate solution, akin to the case of BoN. We 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.

Meanwhile, 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. The key lies in the difference between pointwise verification/scoring and pairwise comparison. It is widely believed that the latter is typically much easier and more accurate than the former, supported by common practice and extensive empirical evidence.

We claim that this should be true in theory as well; in particular, "no adversarial candidate exists for BoN" implies "no adversarial candidate exists for the knockout algorithm", but the reverse is not necessarily true. To 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. In this case, it is easy to check that if BoN enjoys success guarantees, then so does the knockout algorithm. As 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).

Another benefit of our proposed assumptions is their probabilistic nature. This 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.

Given 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.

Tentative revisions

Motivated 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:

• In Line 58, we will replace "two natural (and arguably minimal) assumptions" with simply "two assumptions".

• 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".

• 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."

• 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.

• 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.

We'd love to hear your feedback on whether any further improvement can be made.

---

Other concerns

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.

We believe that this is reasonable and well expected, since there are always counterexamples to an assumption. This is also true for other methods like majority voting or Best-of-N, whose provable inference scaling laws rely on assumptions that fail on certain problems and datasets in reality (cf. Lines 42 - 52, Lines 338 - 349, and the references therein).

Indeed, 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. This includes Lines 251 - 308 for the knockout algorithm, Lines 316 - 328 for the league algorithm, and the corresponding figures of experiment results. For 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. In such cases, it is no surprise that the knockout algorithm (or other test-time scaling methods) fails to solve this problem.

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.

To the best of our understanding, involving the data (i.e., input problem) in the formal definition of "provable inference scaling law" is reasonable and perhaps inevitable. After 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. In 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. We are uncertain about what a definition that doesn't involve the data should look like, and would appreciate further hints on this aspect.

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".

We 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. In 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; to improve the clarity of our presentation, we plan to add this message to the caption of Figure 2 in our revision. Even when using the total number of LLM calls (rather than $N$) as the cost metric, the knockout algorithm still demonstrates advantages over majority voting in terms of convergence speed and ceiling of the accuracy curves, as explained in Lines 246 - 250.

---

Thank you again for your review, which helps us a lot in improving the current work! We hope that our responses have provided satisfactory answers to your questions, but do let us know if you have any further concern that we can address.