Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for LLM Problem-Solving
Authors: Yangzhen Wu
Zhiqing Sun
Shanda Li
Sean Welleck
Yiming Yang
Venue: ICLR 2025 Poster (2025)
Keywords: Inference Scaling Law
Test-time Scaling
Compute-optimal Inference
LLM reasoning
Primary area: foundation or frontier models, including LLMs
TL;DR: We study inference scaling laws and compute-optimal inference of LLMs on mathematical problem solving.

Abstract: While the scaling laws of large language models (LLMs) training have been extensively studied, optimal inference configurations of LLMs remain underexplored. 
We study inference scaling laws (aka test-time scaling laws) and compute-optimal inference, focusing on the trade-offs between model sizes and generating additional tokens with different inference strategies. As a first step towards understanding and designing compute-optimal inference methods, we studied cost-performance trade-offs for inference strategies such as greedy search, majority voting, best-of-$n$, weighted voting, and two different tree search algorithms, using different model sizes and compute budgets. Our findings suggest that scaling inference compute with inference strategies can be more computationally efficient than scaling model parameters. Additionally, smaller models combined with advanced inference algorithms offer Pareto-optimal trade-offs in cost and performance. For example, the Llemma-7B model, when paired with our novel tree search algorithm, consistently outperforms the Llemma-34B model across all tested inference strategies on the MATH benchmark. We hope these insights contribute to a deeper understanding of inference scaling laws (test-time scaling laws) for LLMs.

Published as a conference paper at ICLR 2025
INFERENCE SCALING LAWS:
AN EMPIRICAL ANALYSIS OF COMPUTE-OPTIMAL INFERENCE FOR LLM PROBLEM-SOLVING
Yangzhen Wu'; Zhiqing Sun", Shanda Li,, Sean Welleck2, Yiming Yang² Institute for Interdisciplinary Information Sciences, Tsinghua University School of Computer Science, Carnegie Mellon University wuyangch21 erraangch2@@milss @emammmlll... weeiiisssssnnniiii teiinnuunu...... weigghaa.du..c.mm edu.cn en
{zhiqings, shandal, swelleck, yiming)0cs. cmu.cmt.... https://thhi tettthuuu.......... mrz.ggithub io/ inference scaling/
ABSTRACT
While the scaling laws of large language models (LLMs) training have been exten- sively studied, optimal inference configurations of LLMs remain underexplored. We study inference scaling laws (aka test-time scaling laws) and compute-optinal inference, focusing on the trade-offs between model sizes and generating ad- ditional tokens with different inference strategies. As first step towards un- derstanding and designing compute-optimal inference methods, we studied cost- performance trade-offs for inference strategies such as greedy search, majority voting, best-of-n, weighted voting, and two different tree search algorithms,, us- ing different model sizes and compute budgets. Our findings suggest that scal- ing inference compute with inference strategies can be more computationally ef- ficient than scaling model parameters. Additionally, smaller models combined with advanced inference algorithms offer Pareto-optimal trade-off's in cost and performance. For example, the Llemma-7B model, when paired with our novel tree search algorithm, consistently outperforms the Llemma-344 -3B model across all tested inference strategies on the MATH benchmark. We hope these insights con- tribute deeper understanding of inference scaling laws (test-time scaling laws) for LLMs.
Inference scaling (Weighted Majority)
Inference scaling (Weighted Majority)
410M
70
Test error GSMBK
1.48
Test Test error on GSMBK
60
2.88
60
14.0
50
6.98
50
13.5
128
13.0
40
40
12.5
169
30
12.0
11.5
2
8
32
128
512
2048
0.5
2
16
Inference FLOPs per question (x1011)
Model size (B)
Figure 1: Inference scaling laws exhibited for Pythia (Biderman et al., 2023) models and GSM8K test error. We evaluate the error rate (lower is better) of models using various sizes and numbers of sampled solutions for weighted majority voting. Left: the error rate for each model size decreases steadily as inference-compute increases, and converges at the end. Right: the optimal model size (shown stars for 241, 2 and 247 FLOPs) varies based the inference-time compute budget. For instance, smaller models are compute-optimal at 241 and 24 FLOPs, Both axes are log scale.
WWrk done during the visit Carnegie Mellon University

---

Published as a conference paper at ICLR 2025
INTRODUCTION
Scaling laws of neural networks (Hestness et al., 2017; Rosenfeld et al., 2020) have been established across a range of domains, including language modeling (Kaplan et al., 2020; Hoffmann et al., 2022; OpenAI, 2023), image modeling (Henighan et al., 2020; Yu et al., 2022; Peebles & Xie, 2023), video modeling (Brooks et al., 2024), reward modeling (Gao et al., 2023), and board games (Jones, 2021). These studies have demonstrated how model performance is influenced by both the size of the model and the amount of training compute. However, there is limited knowledge on how varying the compute during inference affects model performance after the model has been trained.
To improve the task performance of large language models (LLMss), inference techniques typically involve additional compute as performance maximization step at inference time (Nye et al., 2021; Wei al., 2022; Wang et al., 2023b; Yao et al., 2023; Chen et al., 2024b). The computational cost of these techniques must be taken into account for compute-optimal inference. For example, Monte Carlo Tree Search (MCTS) may improve task performance, but it potentially requires much more compute than simply sampling solutions multiple times (Jones, 2021). Generally speaking, we need a comprehensive understanding of how various inference-time methods (e.g., best-of-n, majority voting (Wang et al., 2023a; Li et al., 2023)) trade off between performance and cost. To improve our understanding, this paper presents a thorough empirical evaluation with careful analysis over various configurations of representative LLMs and inference algorithms.
Specifically, we explore how to select an optimal size for the language model and an effective in- ference strategy (e.g., greedy search, majority voting, best-of-n, weighted voting, and their tree- search variants) to maximize performance (i.e., accuracy) with given compute budget. We control the inference compute (FLOPs) of a fixed model by generating more tokens through the language model', sampling further candidate solutions, and ranking them with a reward model. We analyze the performance of fine-tuned models of various sizes given different inference FLOPs on mathe- matical reasoning benchmarks (e.g., GSM8K test set (Cobbe et al., 2021) and MATH500 test set (Hendrycks al., 2021b; Lightman al., 2024)). Our experiments cover several model families, including general-purpone LLMs (e.g., Pythia (Biderman et al., 2023) & Mistral (Jiang et al., 2023)) as well as math-specialized ones (e.g., Llemma (Azerbayev et al., 2024)).
Our results on Pythia (Fig. 1) illustrate how performance scales with increased inference compute across various model sizes. Typically, increasing the compute budget leads to higher accuracy until the accuracy reaches saturation. As the compute budget increases, smaller models initially perform better than larger ones, but once the accuracy of the smaller models saturates, the larger models have favorable performance. The right panel of Figure demonstrates that the optimal model size for inference varies with different levels of computational budgets. However, in real-world deployment, the available compute is typically much lower than the point where the accuracy of relatively small models saturates and larger models begin to show their advantage (as shown in Fig. 4, where the 7B model outperforms the 34B model until 128 Llemma 7B solutions are sampled). This indicates that relatively smaller models could be more compute-optimal for inference.
We analyze the asymptotic behavior of sampling and voting- voting-based inference strategies. showing their convergence upper bound and rate of convergence. Given a dataset, the accuracy of the lan- guage model will ultimately saturate to a fixed limit which determined by the output probabilities assigned by the model, exhibiting exponential convergence speed through sampling and voting. This implies that, without an oracle verifier, simple strategies like sampling cannot achieve perfect ac- curacy even with an infinite number of samples, leading to diminishing returns. Therefore, this highlights the necessity for more sophisticated inference algorithms.
We have also found that the commonly-used MCTS method does not perform well with weighted voting, as it often yields many unfinished solutions, hence having less effective votes. To address this issue, propose a novel tree search algorithm, REward BAlanced SEarch (REBASE), which pairs well with weighted voting and achieves a Pareto-optimal trade-off between accuracy and inference compute. The key idea of REBASE is to node-quality reward to control node expansion, which eliminates the need for explicit rollouts while ensuring enough candidate solutions for voting.
Following Uesato et al. (2022), we refer to the main language model generating outputs as the policy model. It can be paired with reward model, which scores outputs from the policy model to facilitate inference.
2

---

Published as a conference paper at ICLR 2025
In our experiments, REBASE consistently outperforms sampling and MCTS methods across all set- tings, models, and tasks. Importantly, we find that REBASE with a smaller language model typi- cally achieves Pareto-optimal trade-off. For instance, show that the Llemma-7B model can achieve competitive accuracy to a Llemma-34B model while using 2x less FLOPPs when evaluat- ing on MATH500 (Fig. 4) GSM8K (Fig. 5). Moreover, Llemma-7B with REBASE outperforms Llemma-34B with standard majority voting across all compute budgets. Our results show the value of using smaller models with advanced inference-time algorithms, and the benefits of new algo- rithms for achieving better returns on inference- time compute.
Our contributions are summarized follows:
We explore new inference scaling laws and compute-optimal inference by evaluating the performance of various model sizes under fixed inference strategy. We show that smaller models can outperform larger ones under the same compute budget by increasing the num- ber of samples.
We provide new theoretical analysis of the scaling behavior of voting methods, presenting convergence bounds and rates. Our analysis shows performance limits and diminishing returns from sampling, pointing to the need for more sophisticated inference algorithms.
We formulate a new compute-optimal inference problem and propose a novel tree search algorithm, REBASE, which is compute-optimal compared to widely-used sampling and MCTS methods, Our results show benefits of using smaller models with advanced infer- ence algorithms, and new algorithms for achieving better cost-performance tradeoffs.
RELATED WORKS
Scaling laws. Recent research on scaling laws has established that model performance follows predictable power-law relationships with respect to the number of parameters, the size of the train- ing dataset, and the available compute (Hestness et al., 2017; Rosenfeld et al., 2020). The seminal function
work by Kaplan et al. (2020) demonstrates that the test loss of language models decays of model size and data in a highly regular manner. Subsequent studies refine these initial observa- tions and extend them into more diverse settings (Hoffmann al., 2022; Alabdulmohsin al., 2022; Muennighoff et al., 2023; Lin et al., 2024; Goyal et al., 2024b). However, most of these existing works are primarily focused on the training regime. Sardana al. (2024) study scaling laws taking both training and inference into account, but only a fixed inference algorithm is considered. In com- parison, our work systematically demonstrate inference scaling laws, i.e., LLM problem-solving performance improves with increased inference-tine time compute budget, and we propose and study compute-optimal inference.
Inference strategies and inference-time compute utilization in LLM problem-solving. A vari- ety of inference strategies have been developed to generate sequences with a trained model (Welleck al, 2024). Deterministic methods such as greedy decoding and beam search (Teller, 2000; Graves, 2012) find highly probable sequences which typically have decent quality but lacks diversity. Sam- pling algorithms (e.g.. temperature sampling (Ackley et al., 1985)) can produce diverse set of results which are then aggregated to achieve higher accuracy (c.g., via the self-consistency ap- proach (Wang et al., 2023a)). Recent methods combine search algorithms with LLMSs, including breadth-first or depth-fire first search (Yao et al., 2023), Monte-Carlo Tree Search (MCTS) (Zhang et al., 2023; Zhou et al., 2024; Liu et al., 2024; Choi et al., 2023), and guided beam search (Xie et al., 2023). Several prior studies also find that LLM problem-solving performance can be im- proved by outputting "dummy" tokens at inference time (Goyal et al., 2024a; Přau et al., 2024). All of these methods show that using search at inference time can lead performance gains the cost of increased inference-tima time compute, but they do not characterize the cost-performance trade-off systematically. We are the first to formulate and study compute-optimal inference, analyzing the trade-off between compute budget and problem-solving performance and proposing the REBASE method that is empirically Pareto-optimal. Concurrently, Snell et al. (2025) also study how to scale inference-compute optimally and provide complementary insights, since we consider more model families and sizes while they study several different inference strategies.
Mathematical Reasoning with LLMs. Large language models have made significant progress in recent years, and have exhibited strong reasoning abilities (Brown et al., 2020; Hoffmann et al., 2022; Lewkowyez et al., 2022; Chowdhery al., 2023). Mathematical problem solving is a key
3

---

Published as a conference paper at ICLR 2025
Computee-ptinnll Training
Compute-Optimal Inference
Training Tokens
Model Size
Inference Strategies
Greedy / Best-of-N /
iT 2T /
FB /3BB /
Tree-Search /
I1 Chinchilla Scaling Law
Ours
Figure 2: Illustration of compute-optimal scaling laws in training and inference. The Chinchilla scaling law (Hoffmann et al., 2022) shows how to choose model size and number of training tokens under training-compute budget, while our work shows how choose model size and an inference strategy under an inference-compute budget.
task for measuring LLM reasoning abilities (Cobbe et al., 2021; Hendrycks et al., 2021b). Ling al. (2017) first developed the method of producing step by step solutions that lead to the final answer. Later, Cobbe al. (2021) extended the work by training verifier for evaluating and ranking solutions. Subsequent research has shown the performance benefits of inference-time techniques such majority voting and weighted majority voting (Lewkowycz et al., 2022; Li et al., 2023). We choose problem solving in mathematics as the task to study compute-optimal strategies since allows us accurately evaluate problem solving ability.
3 COMPUTE- OPPIIMAL INFERENCE FOR PROBLEM-SOLVIE
We explore the following question: Given fixed FLOPs budget, how should one select optimal model size for the policy model, and an effective inference strategy to maximize performance (i.e., accuracy)? We are the first to formulate this problem and study the associated inference-time scaling laws, setting our work apart from previous scaling law studies (Fig. 2).
To address this, we represent the problem-solving error rate E(N, (:: as a function of the number of model parameters N, the number of generated tokens T and the inference strategy S. The com- putational budget C' is a deterministic function FLOPs N. S), based on N and T. Our goal is to minimize E under the test-time compute constraint FLOPs (N, S) C:
(Nope (C), Topt (C); =
arg min (N,T,S) s.L. (LOPs(N.T.S)
E(N,T:8)
where (C) and Topt denote the optimal allocation of a computational budget C.
Here, the inference compute (FLOPs) for fixed model can be modulated by generating more tokens with the policy model and inference strategy, e.g., sampling additional candidate solutions and subsequently ranking them using a reward model. As the inference strategies, we primarily consider sampling and tree-search approaches paired with re-ranking majority voting. This includes greedy search, majority voting, best-of-n,, weighted voting, and their tree-search variants.
3.1 INFERENCE STRATEGIES
We consider the following inference strategies which popularly used in practice:
Greedy search. This strategy generates tokens token at each step. It is computationally efficient but often suboptimal in terms of diversity.
time by selecting the highest probability
best-of-n. This strategy, also known as rejection sampling, generates a set of candidates and chooses the one with the highest score given by the reward model.
4

---

Published as a conference paper at ICLR 2025
Majority voting. In this strategy, set of candidates generated, and the final answer to the problem is determined by the most frequently occurring answer in all the outputs.
Weighted majority voting. This strategy is a variant of majority voting in which the candidates are weighted based on the scores given by the reward model.
We say strategy is sampling- temperature sampling) to generate the candidate set (greedy search is separate, in that it only has a single deterministic candidate). A tree-search variant uses tree search to generate the candidate set. Before discussing tree-search methods, we analyze sampling-base -based voting below.
if it uses standard autoregressive sampling algorithm (e.g.,
Theoretical analysis of sampling-bai behavior of voting-based strategies given infinite compute in Theorems & 2. Informally, we show that the accuracy of standard/weighted majority voting converges with infinite samples, and the limit only depends on the distribution modeled by the language model (and the reward model). This theoretical finding is also aligned with our empirical findings shown in Sec. 4.2, which show saturation at high sampling budgets. The proofs are presented in Appendix A.
voting. We present thcoretical results on the asymptotic
Notations and assumptions. Let V be a finite vocabulary and V its Kleene closure, i.c., the set of all strings. Given a problem I, we say language model answers y to this problem if the model outputs rey where r E V can be any "reasoning path" and e E V denotes a special token that marks the end of reasoning. We further assume that the answer string is always shorter than L tokens, i.e., lvl S L for some fixed L E N" where [y] denotes the length of For a language model т,, denote by (vlw) the probability of generating v given input (prompt) w. For reward model p. denote by p(v) the score it assigns to the string v. We use to denote the indicator function.
Theorem 1. Consider dataset 'D {( [ where 3yg and ys denotes input and true answer, respectively. For language model æ, denote by acc (D; R) the accuracy on 'D using majority voting with n samples. Following the notations and assumptions defined above, we have:
lim n +-+
acen
MV (D;
I
yb
arg max Σ ((reyla;) JUL
(almost surely);
m
1=1
reV.
1
and
E acc
MV (D; r]]
T
y: arg max
Σ Treey(a;)
O(c
DISL rEv.
for some constant e 1.
Theorem 2. Consider dataset D = {x1, Bi) For a language model π and a reward model p. denote by acc WV (D; p) the accuracy on 'D using weighted majority voting with n samples. Following the notations and assumptions defined above, we have:
lim acc, (D; p) +-0+00
V1 arg max Σ
((rey)z:)p(arre))
(almost surely);
M
rEV"
m
and [aco WV WV (D;
y/ arg max
Σ -EV-
オ ((roy)
Occ
m
W
for some constant e > 1.
Remarks. Theorems & 2 state the convergence of the accuracy with increasing number of sam- ples, indicating that the performance gains of using more samples will saturate for any fixed models. The limit is determined by the likelihood of generating the correct answers through all possible rea- soning paths (and the likelihood should be viewed as weighted sum for weighted majority voting). This motivates us to consider inference algorithms that search for "good" reasoning paths, such as the ricesseach-bbaee variants detailed in Sec. 3.1.1 & 3.1.2.
Theorem 1 & 2 also present insights to compare standard majority voting with weighted majority voting. Informally, as long as the reward model is "better than random", i.e., assigning higher rewards to correct solutions on average, the accuracy limit of weighted majority voting is higher than that of majority voting. In our experiments, dominates majority voting. Thus, we focus on best-of-n and weighted majority voting in the main paper and defer majority voting results to Appendix D.
consistently find that weighted majority voting
5

---

Published as a conference paper at ICLR 2025
Observe that 2+ =
0.1
Explore more
We'll solve this as follows..
0.4
Explore less
Explore based on reward model scores
Process reward model
Step 1:
Step 2:...
Step 3:2 2
[0.1]
Solution-so-far
Figure Illustration of one iteration REward BAlanced SEarch (REBASE).
3.1.1 MONTE CARLO TREE SEARCH (MCTS)
Monte Carlo Tree Search (MCTS) has proven effective in domains such as board games where strategic decision-making is required (Silver et al., 2016; 2017; Jones, 2021). Recent work has shown that adapting MCTS to the context of LLMs can enhance the text generation process (Zhang et al., 2023; Zhou et al., 2024; Liu et al., 2024; Choi et al., 2023; Chen et al., 2024a; Tian et al., 2024; Chen et al., 2024a). this context, MCTS paired with a value model to score and guide the exploration steps. For additional background, we provide review of MCTS in Appendix B.
Recent work in MCTS or its variants mainly focus on improving the performance (e.g., accuracy) on the studied tasks. However, generic comparisons MCTS with conventional methods like best-of-n and majority voting in terms of computational budget, measured in generated tokens or processing time are scarce or indicate potentially unfavorable cost-performance tradeoffs. For example, MCTS consumes substantially more resources, often requiring dozens of times more generated tokens than simpler methods. Specifically, significant portion of the paths the search tree are used to estimate and select nodes, and these paths do not necessarily become a part of the final candidate solution, although MCTS ensures that the sampled solutions comprise high-quality intermediate steps. In contrast, sampling methods generate multiple solutions in parallel and independently, and all the generated sequences are included in the candidate solutions. However, the intermediate steps in guaranteed be of high quality, there is mechanism for pruning poor steps or exploiting promising ones.
these sequences
This highlights the need for new tree search method that can achieve a comparable (or better) per- formance as MCTS, and that is computationally less costly, with cost similar to weighted majority voting and best-of-n. This motivates our new method, Reward Balanced SEarch (REBASE).
3.1.2 REWARD BALANCED SEARCH (REBASE)
The REBASE tree search method, illustrated Fig. 3, inherits exploitation and pruning proper- ties of tree search, while using a reward model alone to estimate quality of intermediate nodes. This saves inference compute compared to methods such as MCTS, since it does not involve estimate node quality with explicit rollouts. In short, the underlying idea is determine how much each node should be expanded at each depth. Namely, REBASE expands nodes reward scores, subject to a total expansion
process reward model to
given depth according to their budget. We describe this procedure in more detail below.
Notations. We view the fine-tuned LLM as a policy нe which generates the solution step by step. Given question and the first & steps of solution 71 ..... the (k + 1)-th step is sampled from To(-|27 rk). REBASE generates a solution tree during inference, in which the root node the question æ, and other nodes corresponds to solution steps. When generating solution trees, generate children of тı by sampling from To(+[2r, -.. rt). We use the corresponding solution step to denote node. The reward of node rx generated by the PRM: R(rx): R(#r r....).

---

Published as a conference paper at ICLR 2025
Inference scaling (Weighted Majority)
Inference scaling (Best-of-N)
75
Sampling (78)
Sampling (7B)
Test error on MATH
Sampling (34B)
Test error on MATH
Sampling (348)
70
MCTS (78)
70
MCTS (78)
MCTS (34B)
MCTS (348)
65
REBASE (7B)
(7B)
65
REBASE (3-48)
REBASE (348)
60
55
55
50
4
16 64
256
1024
16
64
256
1024
Inference FLOPs per question (x1012)
Inference FLOPs per question (x10²²)
Figure 4: MATH inference scaling across inference strategies and model sizes (lower is better). Detailed MCTS configurations can be found in Appendix B. The left/right panel shows the error rate on MATH based on weighted majority/best-of REBASE is the compute-optimal strategy at all budgets, with 7B typically the optimal model size.
Initialization. Given the question I, a balance temperature To >> O, and target number of generated solutions N, sample N instances of the first step for the question, yielding all the nodes of depth I in the search tree. We let the sampling budget of depth O, Bo. to N at initialization.
Reward assignment and update. In the i-th iteration, the PRM assigns the rewards all the nodes at depth i. After that, the algorithm examines whether the solutions up to depth i are complete. Supposing there are C; completed solutions, we update the sampling budget using B, Bi-1-B1 C.- If B; O, the process ends, and we obtain N solutions.
Exploration balancing and expansion. For all of the nodes ny with reward R(n,) in the depth of the tree, we calculate the expansion width of the ny as:
exp (R(n,)/TH
W Round
B,
E exp (R (mx))/TT)
Then we sample W, children for ny for all the nodes in depth and start the next iteration.
EXPERIMENTS
Our experiments are centered around two main questions:
Compute-optimal model size: How does performance scale as inference-time compute is increased with a fixed inference strategy, but with varying model size?
Compute-optimal inference strategy: How does performance scale as inference-time compute is increased with various inference strategies (and various model sizes)?
We detail experimental setup below.
4.1 SETUP
Datasets. We conduct experiments on two mathematical problem-solving datasets to investigate the effects of scaling inference compute for both challenging and simpler problems. Specifically, MATH (Hendrycks et al., 2021a) and GSM8K (Cobbe et al., 2021) datasets containing high school mathematics competition-level problems and grade-school level mathematical reasoning problems, respectively. Following Lightman al. (2024); Wang al. (2024); Sun al. (2024), we use the MATH500 subset as our test set.
Policy model (solution generator). To study the how performance scales as inference compute is increased using fixed strategy, the primary axis of variation is model size. Therefore, choose Pythia (Biderman et al., 2023) as our base models, since various model sizes are available in the Pythia family. To study inference scaling under different inference strategies (e.g., tree search, weighted majority voting), we use math-specialized Llemma models (Azerbayev et al., 2024). We finetune these models the MetaMath dataset (Yu et al., 2024) using full parameter supervised
7

---

Published as a conference paper at ICLR 2025
Inference scaling (Weighted Majority)
Inference scaling (Best-of-N)
Test erro on GSMBK
28
32
Sampling (34B)
Sampling (7B)
Test Test error on GSM8K
28
32
Sampling (34B)
Sampling (7B)
REBASE (7B)
REBASE (7B)
24
REBASE (348)
24
REBASE (34B)
20
20
16
16
12
12
16
64 128
256
2
16 32
128 256
Inference FLOPs per question (x10
Inference FLOPs per question (x10²2)
Figure 5: GSM8k inference scaling across inference strategies and model sizes (lower is bet- ter). The left/right panel shows the problem-solving eπror rate on GSM8K based on weighted majority/best-of-n MCTS is not included in the comparison because of its poor compute-accurag trade-off. REBASE is the compute-optimal inference strategy, and the optimal model size varies.
fine-tuning (Full-SFT), The finetuning configuration is given in the Appendix. Additionally, we test the Mistral-7B (Jiang et al., 2023) to expand our findings across different models and architectures.
Reward model. All of the experiments the same Llemma-34B reward model, which we fine- tuned on the synthetic process reward modeling dataset, Shepherd (Wang et al., 2024). We added reward head to the model, enabling it to output a scalar reward the end of each step.
Inference configuration. We sampling and tree search methods to generate multiple candi- dates, and select the answer through best-of-n, majority voting, or weighted voting. Each con- figuration is multiple times to calculate the mean and variance, which mitigates effects from randomness and thereby improves the reliability of our conclusions. Unless explicitly stated other- wise, each point in the figures in this section corresponds to 2 samples, where an integer starting from O.
4.2 COMPUTE-OPTIMAL MODEL SIZE
To compare the inference compute budgets of different models, we plot the figures with the num- ber of FLOPs used per question during inference. We compute the inference FLOPs based on the commonly-used formula proposed by Kaplan et al. (2020).
Scaling law of compute-optimal inference for model size. Fig. 1 shows the relationship between inference compute and error rate for different model sizes. The error rate first decreases steadily and then starts to saturate. Initially, sampling many times from smaller models is compute-optimal. At larger compute budgets the larger models are preferable, since the performance of small models has saturated. As highlighted in the right panel of Fig. 1, the optimal model size varies based on the inference budget. We performed a regression analysis on inference FLOPs C and model sizes N to establish a relationship between given computational budget and its optimal model size. The resulting equation, logı0 (C) = 1.19 log (N) + 2.03, lets us estimate the optimal inference model size for specific compute budget.
Llemma-7B achieves competitive accuracy to Llemma-34B with less compute. Fig. 4 and Fig. 5 shows the relationship between error rate and inference FLOPs for Llemma 7B and Llemma 34B using different inference strategies. Llemma-7B requires around 2x less total FLOPs than Llemma-34B to achieve comparable accuracy. This held across inference strategies (sampling strate- gies, MCTS, REBASE) and tasks (MATH, GSM8K). This result suggests that, with the same training dataset and model family, generating more tokens with a suitable inference strategy using a smaller model can have more favorable perfformaee tradeoffs than using a larger model.
4.3 COMPUTE-OPTIMAL INFERENCE STRATEGY
REBASE is Pareto-optimal. REBASE consistently achieves the best cost tess-performance tradeoffs, outperforming the sampling- based methods in all settings when fixing the model and the evaluation task (Fig. 4, 5, 6, and 7). For example, in Fig. 4, REBASE is the compute-optimal strategy at all
8

---

Published as a conference paper at ICLR 2025
Llemma-78
Llemma-348
Mistral-7B
80
75
80
Test error on MATH
75
Sampling BoN
Sampling W.M.
Test error on MATH
70
Sampling BoN
Sampling W.M.
Test exteron on MATH
75
Sampling BoN
Sampling W.M.
70
REBASE W.M.
65
REBASE W.M.
REBASE W.M.
65
REBASE BoN
REBASE BoN
REBASE BcN
60
65
60
55
60
50
50
55
45
45
50
16
256
1024
16
32
64
128 256 5121024
16 32 64 128256512
Infer. FLOPs per question (x10
Infer. FLOPs per question (x10
Infer. FLOPs per question (x10
Figure 6: MATH inference scaling across inference strategies and models (lower is better). The tested models are Llemma-7B (left), Llemma-34B (middle), & Mistral-7B (right). In the legend, W.M. and BoN refer to weighted majority and best-of-n, respectively.
Liermma78
Llemma-34B
Mistral-7B
40
26
26
Test error on GSM8K
35
Sampling BoN
Sampling W.M.
Test error on GSMBC
24
22
Sampling BoN
Sampling W.M.
[5MBK
24
Sampling BoN
Sampling W.M.
20
REBASE W.M.
20
REBASE W.M.
18
REBASE W.M.
REBASE BoN
18
REBASE BoN
Test o
16
REBASE BoN
16
14
14
12
15
12
10
2
16 32
64
16
32
64
128 256
2
4
8
16
32 64
Infer. FLOPs per question (x10
Infer. FLOPs per question (x10'2)
Infer. FLOPs per question (x1012)
Figure 7: GSM8K inference scaling across inference strategies and models (lower is better). The tested models are Llemma-7B (left), Llemma-34B (middle), & Mistral-7B (right). In the legend, W.M. and BoN refer to weighted majority and best-of-n1, respectively.
Llemma-78 MATH-easy
Llemma-78 on MATH-hard
Llemma-348 MATH-easy
Llemma-34B on MATH-hard
42
Sampling
Sampling
39
Sampling
72
Sampling
Frror 198
REBASE
REBASE
REBASE
REBASE
72
69
36
69
33
66
33
66
63
30
30
63
27
60
27
57
2
16 32
4
32
64
2
16
2 4
32 64
Number of Samples
Number of Samples
Number of Samples
Number of Samples
Figure 8: Comparisons of sampling and REBASE using weighted majority voting on MATH-easy problems (levels 1-2) and MATH-hard problems (levels 3-5). The tested models are Llemma-7B and Llemma-34B.
inference compute budgets, with 7B typically the optimal model size. On the other hand, MCTS underperforms the sampling-based methods at each compute budget, likely due to its costly rollouts (Fig. 4) compared to the efficient use of the reward model in REBASE.
Tab. 1 shows that REBASE achieves better accuracy with a lower compute budget compared to sampling-basee weighted voting. With the 7B model, REBASE achieves higher accuracy with times less compute. This finding is novel, and differs from previous tree search methods that typi- cally improve the performance at the cost of higher computational expense compared to sampling- based voting (Chen et al., 2024a; Xie et al., 2023).
REBASE yields greater gains on hard problems. ficulty level from to 5. This enables finer-grained analysis of the relationship between problem
The MATH dataset assigns each problem a dif-

---

Published as a conference paper at ICLR 2025
Table 1: REBASE with a lower compute budget achieves better accuracy compared sampling with a higher compute budget. We use weighted voting to aggregate candidates for both sampling and REBASE.
# Samples
FLOPs
MATH500 Accuracy (%)
Mistral-7B
Sampling REBASE
256
8.70 x 1024
42.8
32
1.36 x 10
45.0
Llemma- 7B
Sampling REBASE
256
10.0 x 10
45.5
32
1.48 x 10
46.8
Llemma-344
Sampling REBASE
64
12.1 x 10
46.7
32
7.08 x 10
49.2
difficulty and inference strategy. We divide the MATH test set into MATH-easy (levels 1-2) and MATH-hard (levels 3-5) and compare REBASE to sampling on these two subsets. The results are shown in Fig. 8. The performance of sampling and REBASE on easy problems (levels 1-2) is com- parable. However, REBASE demonstrates a significant advantage on harder problems (levels 3-5). This suggests that advanced inference strategies like tree search especially effective for solving difficult problems.
REBASE saturates later than sampling with higher accuracy. From Fig. and Fig. 7, we ob- serve that both sampling and REBASE saturate early in GSM8K and relatively late in MATH. We attribute this to the difference of in difficulty levels between GSM8K and MATH. Specifically, the LLM may assign high probability only correct solutions in easy problems, but spread probability mass across solutions harder problems. Thus, harder problems may require aggregating over more solution paths to converge to the distribution over answers shown in Theorems 1 & 2. On MATH (Fig. 6), we see that REBASE finally saturates with higher accuracy than sampling. We hypoth- esize the reason is that drawing samples from REBASE corresponds sampling from policy that assigns high probability to true answers compared to sampling from the underlying language model. If this was indeed the case, Theorems 1 & indicate that the upper bound would become higher. We leave formally analyzing the behavior of tree search algorithms as interesting future work.
5 CONCLUSIONS
We study the relationship between task performance and the amount of compute expended during inference for various model sizes, model families, and inference strategies, to form empirical in- ference scaling laws. These relationships let us reason about compute-optinet inference: inference configurations that give the best performance at a given compute budget.
Our results lead to three main takeaways. First, find that using smaller model and generat- ing more tokens in an inference strategy often outperforms using a larger model at fixed compute budget. This has implications for models deployed in the real world, where inference compute is constrained in various ways. Specifically, it is potentially beneficial to deploy smaller models with more sophisticated inference strategies for better cost cost-performe perforrmacce trade-off. Second, we show that in the limit of infinite compute (allocated by drawing more samples), sampling-base majority voting strategies inevitably saturate to a distribution that depends on the underlying generation pol- icy. Hence, it is of interest to alter the sampling distribution by designing alternative inference strategy. Third, we design such an inference strategy-the novel REBASE tree search-and find is Pareto optimal, in that it achieves the best performance across all tested compute budgets. Notably, outperforms commonly used weighted majority voting and MCTS methods that have attracted much interest and widespread use. This finding not only shows the strength of REBASE, but also indicates that there is large headroom to improve language model performances via inference-tine time algorithms.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
Zhiqing Sun acknowledges the support of the Google Fellowship. Sean Welleck thanks NSF SCALE (NSF DMS 2134012) and Convergent Research.
REFERENCES
David H Ackley, Geoffrey E Hinton, and Terrence J Sejnowski. A learning algorithm for boltzmann machines. Cognitive science, 91)::147-169, 1985.
Ibrahim M Alabdulmobsin, Behnam Neyshabur, and Xiaohua Zhai. Revisiting neural scaling laws in language and vision. Advances in Neural Information Processing Systems, 35:22300-22312, 2022.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. Program synthesis with large 2108 077 07732.
language models, 2021. URL https: /arxivvvvv. www.eiiww....e......eeeeeeoeeeee
Zhangir Azerbayev, Hailey Schoelkopf, Keiran Paster, Marco Dos Santos, Stephen Marcus McAleer, Albert Q. Jiang, Jia Deng, Stella Biderman, and Sean Welleck. Ilemma: An open language model for mathematics. In The Twelfth International Conference on Learning Representations, 2024.
URL http::///ppereeieew net
Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O' O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning, pp. 2397-2430. PMLR, 2023.
Tim Brooks, Bill Peebles, Connor Holmes, Will DePue, Yufei Guo, Li Jing, David Schnurr, Joe Taylor, Troy Luhman, Eric Luhman, Clarence Ng. Ricky Wang, and Aditya Ramesh. Video generation models as world simulators, 2024. URL
rideo-generate mereatiiooommmlsssseeeeee was-world-- simulators.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot leamners Advances in Neural Information Processing Systems, 33:1877-1901. 2020.
Guoxin Chen, Minpeng Liao, Chengxi Li, and Kai Fan. Alphamath almost zero: Process supervision without process. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a. URL https: opwprevieneeeeeeeeeeeeeeee net /tt////ouumn//aaa/33333
Ziru Chen, Michael White, Ray Mooney, Ali Payani, Yu Su, and Huan Sun. When is tree search useful for I1m planning? depends on the discriminator. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1; Long Papers), pp. 13659- 13678, 2024b.
Schyun Choi, Tianqing Fang, Zhaowei Wang, and Yangqiu Song. KCTS: Knowledge-constriin tree search decoding with token-level hallucination detection. In The 2023 Conference Em- pirical Methods in Natural Language Processing, 2023. URL ht http:///ppeeeeee...e.. net./
Forum?1d=7H45:FF
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240): 1-113, 2023.
Karl Cobbe, Vincet 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 preprint arXiv:2 10, 14168, 2021.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Leuman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprint 407. 2024.
11

---

Published as a conference paper at ICLR 2025
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pp. 10835-10866. PMLR, 2023.
Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan. Think before you speak: Training language models with pause tokens. In The Twelfth International Conference on Learning Representations, 2024a. URL httpst/////ee /ttp:::///ppeevvee.. net htte//orummicc - w.w.hpphh0ppPPPC 4CRKPdC.
Sachin Goyal, Pratyush Maini, Zachary Lipton, Aditi Raghunathan, and Zico Kolter. Scaling laws for data filtering- data curation cannot be compute agnostic. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 22702-22711, 2024b.
Alex Graves. Sequence transduction with recurrent neural networks. arXiv:1211.3711 2012.
arXiv preprint
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He. Dawn Song, and Jacob Steinhardt. Measuring coding chal- lenge competence with APPS. In Thirty-fifth Conference on Neural Information Processing Sys- tems Datasets and Benchmarks Track (Round 2), 2021a. URL httpt:::ppppeeeeeeeeette .eteeieewwweweeeeeeeeem...... Forum?id=sD93G0nia
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Thirty-fifth Conference Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021b. URL https: / http//ppeeeeeieeeeeeeeeeeeeeeeee net
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B. Brown, Prafulla Dhariwal, Scott Gray, et al. Scaling laws for autoregressive genera- tive modeling. arXiv preprint (xXv:2000014701,, 2020.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically, arXiv preprint arXiv:1712.00040 2017.
Jordan Hoffmaann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, al. Train- ing compute- optiiall large language models. arXiv preprint arXiv:2203.15552 2022.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023.
Andy L Jones. Scaling scaling laws with board games. arXiv preprint arXiv:2104.03113, 2021.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Aitor Lewkowyez, Anders Johan Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Venkatesh Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative rea- soning problems with language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: wpwpreveeeeeeeeeeeeeeeeeeee net forum? 1==IFXZERXXNTT.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Mak- ing language models better reasoners with step-aware verifier. In Anna Rogers, Jordan Boyd- Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5315-5333, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 18.18663/v aal.o...llloog2291. URL https: / //cl//aclaaaaa anthol 2tgg2023.ao acl acl-long long.. 291.
12

---

Published as a conference paper at ICLR 2025
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 Twelfth International Conference Learning Representations, 2024. URL https: oppnreviee... met//foure ? (d=v1100p66G0
Haowei Lin, Baizhou Huang, Haotian Ye, Qinyu Chen, Zihao Wang, Sujian Li, Jianzhu Ma, Xiaojun Wan, James Zou, and Yitao Liang. Selecting large language model to fine-tune via rectified scaling law. In International Conference Machine Learning, pp. 30080-30107. PMLR, 2024.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale gener- ation: Learning to solve and explain algebraic word problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 158-167, 2017.
Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannanch Hajishirzi, and Asli Celikyilmaz. Don't throw away your value model! generating more preferable text with value- guided monte-carlo tree search decoding. In First Conference on Language Modeling, 2024. URL https:://penre:
net Dorummdd=xh92ttt 2Ldmn.
Niklas Muennighoff, Alexander Rush, Boaz Barak, Teven Le Scao, Nouamane Tazi, Alcksandra Piktus, Sampo Pyysalo, Thomas Wolf, and Colin A Raffel. Scaling data-constrained language models. Advances in Neural Information Processing Systems, 36:50358-50376, 2023.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:21 2021.
OpenAl. Gpt-4 technical report, 2023.
William Peebles and Saining Xie. Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4195-4205, 2023.
Jacob Pfau, William Merrill, and Samuel Bowman. Let's think dot by dot: Hidden computation in transformer language models. In First Conference on Language Modeling, 2024. URL https: //openreview. net wwt.orommmdddddddeeeooo
Jonathan S. Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. In International Conference on Learning Representa- tions, 2020. URL https: http::://///eeeeeeee/ee nnt forum/ormmmmmmmm htt////ooummrim//ooeee id=ryenvpEKDr.
Nikhil Sardana, Jacob Portes, Sasha Doubov, and Jonathan Frankle. Beyond chinchilla-optimall Ac- counting for inference in language model scaling laws. In International Conference on Machine Learming, pp. 43445-43460. PMLR, 2024.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittieseer, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(75877:4844489, 2016.
David Silver, Julian Schritwieserr, Karen Simonyan, Ioannis Antonoglou, Aja Huang. Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354359,, 2017.
Charlie Victor Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling test-time compute opti- mally can be more effective than scaling LLM parameters. In The Thirteenth International Con- ference on Learning Representations, 2025. URL https: openreview net forum? id=44WWwZtd22m.
Zhiqing Sun, Longhui Yu, Yikang Shen, Weiyang Liu, Yiming Yang, Sean Welleck, and Chuang Gan. Easy-to-hard generalization: Scalable alignment beyond human supervision. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:// openreview.co n www.:/eee//oooiiooem f
13

---

Published as a conference paper at ICLR 2025
Virginia Teller. Speech and language processing: introduction to natural language processing, computational linguistics, and speech recognition, 2000.
Ye Tian, Baolin Peng, Linfeng Song, Lifeng Jin, Dian Yu, Lei Han, Haitao Mi, and Dong Yu. Toward self-improvement of LLMs via imagination, searching, and criticizing. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:// openreview net/ forum? 1d=tPdJ2qHKOE
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process- and outcome-based feedback. arXiv preprint arXiv:2211 1..::225111475.. 2022.
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhi- fang Sui. Math-shepherd: Verify and reinforce LLMs step- step-by-step without human annotations. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.). Proceedings of the 62nd Annual Meer- ing of the Association for Computational Linguistics (Volume I: Long Pupers), pp. 9426-9439, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 18653v1ll 2024.acl-long.51 URL https: http::///aaaaaahaooaecooo
org/ 2024 1ee44.ac--oonn 510/.
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoc 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 2023a. URL net/
https:// fttps::/cpperevele wttp:/eeee//oummeeeeeeeeeee forummidd1PPLNNEE
Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A Smith, Daniel Khashabi, and Hannaneh Hajishirzi. Self-instruct: Aligning language models with self senf-geeerated instructions. In Proceedings of the st Annual Meeting of the Association for Computational Linguistics (Volume
1: Long Papers), pp. 11484-13508 2023b.
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le. and Denny Zhou. Chain of thought prompting clicits reasoning in large language models. In Alice Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Ad- vances in Neural Information Processing Systems, 2022. URLhttps: peettp:://ppeet hwwp//eeeee.eeeee//e/e/ee wwerreeeeeeeee/e/eeeeeee Berum?id=_VjooMees
Sean Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf. Alex Xie, Graham Neubig, Ilia Kulikov, and Zaid Harchaoui. From decoding to meta-generation: Inference-time algorithms for large language models. Transactions Machine Learning Research, 2024. ISSN 2835-8856. URL https: / /ppppreeeevieeeeeeeeeeeeeeeeeeee net /forrmrrt d IbMS. Survey Certification.
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min- Yen Kan, Junxian He, and Qizhe Xie. Self- evaluation guided beam search for reasoning, In Thirly-seventh Conference on Neural Information Processing Systems, 2023. URL https: http:///ppeerreeeeeee net. Forum? i d= 2arr882wwg55 hww55Q3.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: / //openreview.o sepperrevee.nee//oooooe.e. wttpi/wwwwe//ooommm/..m httet//ooommmiixxleeeeeeeee 5xc1eexx1....
Jiahui Yu, Yuanzhong Xu, Jing Yu Koh, Thang Luong, Gunjan Baid, Zirui Wang. Vijay Vasudevan, Alexander Ku, Yinfei Yang. Burcu Karagol Ayan, Ben Hutchinson, Wei Han, Zarana Parekh, Xin Li, Han Zhang, Jason Baldridge, and Yonghui Wu. Scaling autoregressive models for content-rich text-to-image generation. Transactions Machine Learning Research, 2022. ISSN 2835-8856.
URL https: http://pppeeeeeeeeeeeeee net forum/ormmm/// "wooummii=ADDDe... id==FDcYJKH.N Featured Certification.
Longhui Yu, Weisen Jiang, Han Shi, Jincheng YU, Zhengying Liu, Yu Zhang, James Kwok, Zhen- guo Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap your own mathematical questions for large language models. In The Twelfth International Conference on Learning Representations, 2024. URL https::///............tt opwnreview. net. / forum d=N@NOggNDRt.
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B. Tenenbaum, and Chuang Gan. Planning with large language models for code generation. In The Eleventh International Confer- ence on Learning Representations, 2023. URL https: wpwppeveeee..eeeeoo//e/e net forum?id I. c00t
14

---

Published as a conference paper at ICLR 2025
Andy Zhou, Kai Yan, Michal Shlapentokh Shlapentokh-Rothman, Haohan Wang, and Yu- Xiong Wang. Language agent tree search unifies reasoning. acting, and planning in language models. In Proceedings of the 41st International Conference Machine Learning, pp. 28138-62160, 2024.
15

---

Published as a conference paper at ICLR 2025
A OMITTED PROOFS
A.1 PROOF OF THEOREM 1
Proof. Recall that we assume the answer must be shorter than tokens. Let A {or |u| < L} be the set of all possible answers. Let #(y æ) be the probability of the language model outputting the answer y to the question æ after marginalizing over the "reasoning paths", i.e.
7 x) = Σ (reylzz)
rEV.
Given an imput x, Assume that y* arg max हे (y)22), 1/.22.... 3/ arg max #(ylz), and denote
yEA
yEAMUu
8 #yy (z) 1)'1z))
For any y, denote by (1) the number of times that the model answers y in the first n samples. Let En be the event that majority voting with samples does not output y". We note that E,, happens only if there exists y" such that fn (v") 2 fn (v²). Therefore, by union bound,
P(F))) of E AV 2 fn(v))
E P(f((V) 2 fa(()))
""EA(O") < <(AIP((a())) 2 (n))")
Note that fx(y") - fn(y)) can be viewed as a sum of i.dd random variables, which take value 1 with probability xz) -1 with probability #(y/ (r), and 0 otherwise. Thus, their expectations are all 5 = #ty" [x) (1/(x)). By Hoeffding's 's inequality, we have
no²
P(f((1) 2 fa((')) & exp
2
Thus,
no82
to
P(E.) < |A| exp
+
Σ P(En) < +00.
2
n=1
By Borel-Cantelli lemma, we have
P limsup Fm
=0 0,
n-4400
which implics the following is true almost surely:
3 E N", such that for any n 2 N, 8" = arg max fn())
DEA
Hence
lim acc +00
MV (((x, [yy y²] (almost surely).
Recall the definition of y", the above shows the theorem is true for dataset with single example {(x,))). For general datasets with m examples, one can apply the above argument to each examples and combine the results to conclude the proof of the almost-sure convergence.
plicity as follows: We let y (z;) = arg max के ( r.), y ([D): We slightly abuse notation for sim- BEA
Next, we prove the asymptotic result on E [aco.M MV
arg max #y)(2;), and let vEA)(o)(a;))
8min min # (mt))ar)) (x))))))) (Z.D))D
16

---

Published as a conference paper at ICLR 2025
We denote by (x,) the event that majority voting with samples does not output y" (ax) given input 24. Then it's easy to see that
no
((E,();)) & exp
min
P(En(2:)) = (ce
2
where e is a constant (which does not depend on i).
Note that if acc,, ((2;, M/ Tr = 1, we have y; y" (2:) unless E, (I:) happens. In other words,
acc
MV (f Vi ) - [v: (x;)) + F[
E
acc MV (fz,, ::: ly, = y" (4:)) S (x;n( O(e
Taking summation over the entire dataset D yields
1
1 Σ
acc, (D;
MV
IT
Lys (x:))
=(En(z:))=O(C) Occ
771
which concludes the proof.
A.2 PROOF OF THEOREM 2
Proof. The proof is similar to the proof of Theorem 1. We only need to set
x)
Σ
Treyy ((rey)a:))(zz,ree)
rEv"
Then the technique in the proof of Theorem immediately applies.
17

---

Published as a conference paper at ICLR 2025
B MCTS DETAILS
In this section, we present additional background on the Monte Carlo Tree Search (MCTS) algo- rithm. The MCTS process can be formulated the following steps:
Selection. The process begins at the root node. Here, the algorithm recursively selects the child node that offers the highest Upper Confidence Bound applied to Trees (UCT) value, continuing until node is reached that has not been expanded. The UCT is calculated using the formula
In (N(Parent(s)) (())
UCT(s)= - + +C
where Q(s) denotes the quality of node N(s) is the number of visits node s, Parent(s) denotes the parent node of s, and C' is a constant determining the level of exploration.
Expansion and evaluation. Upon reaching a non-terminal node s, the node expanded by gen- erating multiple child nodes. Each child node e is then evaluated using a value function Vcc), which predicts the potential quality continuing the sequence from node
Backpropagation. After evaluation, the algorithm updates the UCT values and the visit counts for all nodes along the path from the selected node back to the root. For any node n in this path, the updates are made as follows:
N(n) N(n) +
Q(n) (N(n) - 1))mm)))m)m + (s)) N(n)
18

---

Published as a conference paper at ICLR 2025
C HYPER-PARAMETERY
Finetuning. All the hyperparameters for model fine-tuning can be found in Tab. 2. We preprocess the MetaMath Dataset to make the solutions in a stepwise format.
Table 2: tuninn Hyper- parem--arametes: LR refers to the learning rate, BS refers the batch size. Pythia, Llemma-7B and LLemma-344 are the generators we use in our experiments, RM is short for Reward Model. We only use problems from GSM8K to train the Pythia models.
Model
# Epoch
Dataset
BS
LR
Max Seq Length
Dtype
Pythia-410M
MetaMath (GSM8K)
128
8E-5
768
FP32
Pythia-1.4D
MetaMath (GSM8K)
128
4E-5
768
FP32
Pythia-2.8B
MetaMath (GSM8K)
128
3E-5
768
FP32
Pythia-6.9B
MetaMath (GSM8K)
128
2E-5
768
FP32
Pythia-128 12B
MetaMath (GSM8K)
128
1E-5
768
FP32
Llemma-7B
MetaMath
128
8E-6
1024
FP32
Llemma-344
MetaMath
128
8E-6
768
FP32
Llemma-344 RM
Math-Shepherd
128
1E-5
768
BF16
Inference. For all the inference strategies, the temperature for LLM token generation is set 1.0. Max tokens for the output is 1024 and max tokens for one step 256. For REBASE, we set the balance temperature (i.e., the parameter T3 in Eq. (1)) to 0.1. For MCTS, set C in the UCT value to and we expand 4, 8, 16 children for the root, 2 children for other selected nodes with total 32, 64, 128 expansions respectively. New expanded nodes will be assigned values by the PRM, and then backpropagate the Q values through the process described in the last section.
19

---

Published as a conference paper at ICLR 2025
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 MAJORITY VOTING EXPERIMENT RESULTS
In this section, we additionally include experimental results on the majority voting method, along with its comparison with weighted majority voting (Fig. 9, 10 ,1, 12). The experiments show that although the gap between majority voting and weighted majority voting on sampling is huge. This gap becomes much smaller if we apply REBASE. This phenomenon can be caused by the selection ability of tree search like REBASE. Once REBASE already samples solutions with high rewards, conducing weighted majority voting gains less since the sampled solutions may all have relatively high and stable rewards compared with those of sampling.
D.2 ADDITIONAL EXPERIMENTS ON LLAMA3 MODELS
We conduct additional experiments with Llama3-8B-Ing I-sstrucctt (Dubey et al., 2024) model on MATH and GSM8K datasets, as shown in Fig. 13. Results for code generation task MBPP are presented (Austin et al., 2021) in Tab. 3. These experiments demonstrate that our conclusions generalize to the Llama3 architecture and coding tasks, confirming that increased computational effort improves performance until saturation is reached, and REBASE reaches the optimal performance-compun trade-off.
In mathematical reasoning tasks, REBASE consistently outperforms the sampling approach across different answer selection strategies, including best-of-n, majority voting, and weighted voting. The highest performance on each dataset is achieved using REBASE. Specifically, on GSM8K, REBASE combined with weighted majority voting using 128 samples achieves an accuracy of 90.2%, sur- passing the best accuracy of 89.7% obtained by the sampling method with 256 samples using the best-of-n strategy. Similarly, on MATH, REBASE with weighted majority voting using 128 samples
Llemma-7B
Llemma-34B
Mistral-7B
80
75
80
Sampling M.V.
Sampling M.V.
Sampling M.V. REBASE M.V.
Test error on MATH
REBASE
Test error on MATH
70
REBASE M.V.
Test error on MATH
75
70
65
70
65
60
60
55
55
60
50
50
55
45
4
16
64
256
1024
16
32
64
128 256 5121024
4
8
16
32 64 128256512
Infer. FLOPs per question (x1012)
Infer. FLOPs per question (x1012) Infer. FLOPs per question (x1012)
Figure 9: The inference scaling laws of different models for the problem-solving error rate on MATH test set. The tested models are Llemma-7B (left), Llemma-34B (middle), & Mistrall7B (right). In the legend. M. V. refer to majority voting.
Llemma-7B 7B
Liemma-34B
Mistral-7B
26
Test erro on GSM8K
30
Sampling M.V.
REBASE M.V.
Test error on GSMBK
22
24
Sampling M.V.
REBASE M.V.
Test on GSMBK
22
24
Sampling M.V. REBASE M.V.
20
20
25
18
18
20
16
16
14
14
15
12
12
10
10
10
16 32
64
64 128 256
2
4
Infer. FLOPS per question (x1012)
Infer. FLOPs per question (x1012)
Infer. FLOPs per question (x1012)
Figure 10: The inference scaling laws of different models for the problem-solving error rate on GSM8K test set. The tested models are Llemma-7B (left), Llemma-34B (middle), & Mistral-7B (right). In the legend, M.V. refer to majority voting.
20

---

Published as a conference paper at ICLR 2025
Llemma-78
Llemma-348
Mistral-7B
80
75
80
Test error on MATH
75
Sampling W.M.
Sampling M.
Test error on MATH
70
Sampling W.M.
Sampling M.V.
Test exeeron on MATH
75
Sampling M.V.
Sampling W.M.
70
REBASE M.V.
65
REBASE M.V.
REBASE M.V.
65
REBASE W.M.
REBASE W.M.
REBASE W.M.
60
65
60
55
60
50
50
55
45
45
50
16
256 1024
16
32 64
128 256 5121024
16 32 64 128256512
Infer. FLOPs per question (x10
Infer. FLOPs per question (x10 Infer. FLOPs per question (x10
Figure 11: The inference scaling laws of different models for the problem-solving emror rate on MATH test set. The tested models are Llemma-7B (left). Llemma-34B (middle), & Mistral-7B (right). In the legend, M. V. and W.M. refer majority voting and weighted majority, respectively.
Liermaa77
Llemma-34B
Mistral-7B
40
26
26
Test error on GSM8K
35
Sampling M.V.
Test error on GSMBK
24
Sampling M.V.
24
Sampling M.V.
Sampling W.M.
22
Sampling W.M.
20
Sampling W.M.
REBASE M.V.
20
REBASE M.V.
8
18
REBASE
REBASE W.M.
18
REBASE
16
REBASE W.M.
20
16
14
14
12
15
Test
12
10
10
2
16 32
64
16
32
64
128 256
2
4
8
16
32
64
Infer. FLOPs per question (x10
Infer. FLOPs per question (x10²2)
Infer. FLOPs per question (x10
Figure 12:
The inference scaling laws of different models for the problem-solving error rate on GSM8K test set. The tested models Llemma-7B (left), Llemma-34B (middle), & Mistral-7B (right). In the legend, M.V. and W.M. refer to majority voting and weighted majority, respectively.
Table 3: Zero shot pass rates of Sampling and REBASE MBPP code generation task.
# Samples
Sampling FLOPS
Sampling Pass Rate
REBASE FLOPs
REBASE Pass Rate
8
8 x 10
63
8.3 x 10
69.6
16
16 x 10
69.4
17.5 x 10
72.4
32
32 10
72.4
34.9 x 10
75.8
64
64 12
79
69.2 x 10
81.4
achieves an accuracy of 47.4%, significantly outperforming the sampling method's best accuracy of 41.9% with 256 samples using best-of-n.
For the code generation task MBPP, we analyze scaling behavior and compute-optine inference through pass rate evaluation. The results confirm that REBASE is more compute-efficiers than sam- pling- This advantage can be attributed to the use of a reward model that evaluates partial code solutions. By conducting one iteration of REBASE, our method prunes suboptimal partial solutions while encouraging exploration of promising ones, thereby enhancing computational efficiency and solution quality.
D.3 COMPARISON OF DIFFERENT STRATEGIES ACROSS DIFFERENT MODELS
We show the accuracy of different strategies under a specific compute budget in Tab,
21

---

Published as conference paper at ICLR 2025
Slama--instruct-n
Llarma-instruct-BB
30
Sampling M.V.
Sampling M.V.
error on GSMBK
22
Sampling BoN
Sampling
Test error on MATH
75
Sampling BoN
Sampling
70
REBASE W.M.
65
REBASE WIM.
15
REBASE BoN
REBASE BoN
12
60
10
55
32
128
512
16
64
256
1024
Infer. FLOPs per question (x1012)
Infer. FLOPs per question (x10'2)
Figure 13: GSM8K (left) and MATH (right) inference scaling across inference strategies and models (lower is better). The tested model is Llama3-instruct In the legend, M.V., W.M., and BoN refer to majority voting, weighted majority, and best-of-n, respectively.
Table 4:
Accuracy of different inference configurations under specific compute budget. MV, BoN and WV denote Majority Voting, best-of-n and Weighted Voting, respectively.
# SAMPLES
MATH FLOPS
GSM8K FLOPS
MATH500
GSM8K
MISTRAL-7B
GREEDY
3.4 x 10a2
2.3 x 1012
28.6
77.9
SAMPLING MV
32
109.2 10
72.6 x 10
36.1
85.7
SAMPLING + BON
32
109.2 10
72.6 x 10
40.3
89.4
SAMPLING WV
32
109.2 10
72.6 1012
39.7
89.1
REBASE + MV
32
136.2 X 10
78.9 x 10
44.1
88.8
REBASE + BON
136.2 10
78.9 X 10
45.4
89.4
REBASE + WV
32
136.2 10
78.9 X 10
45.0
89.8
LLEMMA-7B
GREEDY SAMPLING + MV
3.92 10
2.3 10
30.0
68.5
32
125.4 X 12
73.9 x 10
41.0
80.0
SAMPLING BON
125.4 10
73.9 X 1012
41.7
85.6
SAMPLING WV
32
125.4 X 10
73.9 X 10
43.5
85.4
REBASE +
32
148.0 X 10
82.6 x 1012
46.1
86.1
REBASE BON
32
148.0 10
82.6 10
44.1
86.9
REBASE + WV
32
148.0 X 10
82.6 x 10
46.8
87.3
8B
GREEDY SAMPLING + MV
3.84 x 10
2.28 10
29.6
79.0
32
122.9 x 10
73.2 x 10
35.4
84.6
SAMPLING BON
32
122.9 10
73.2 1012
39.7
88.5
SAMPLING WV
32
122.9 X 12
73.2 x 10
39.5
88.6
REBASE + MV
172.8 10
79.3 x 1012
45.2
88.3
REBASE + BON
32
172.8 10
79.3 x 10
45.5
88.7
REBASE + WVV
32
172.8 x 10
79.3 x 10
43.7
89.1
LLEMMA-344
GREEDY SAMPLING MV
19.0 x 10
11.2 x 10a2
33.0
78.4
152.3 10
89.7 x 10
39.9
84.3
SAMPLING BON
8
152.3 10
89.7 x 10
40.4
86.7
SAMPLING WV
152.3 x 10
89.7 x 10
41.0
86.0
REBASE + MV
176.8 10
98.7 1012
43.9
86.1
REBASE + BON
176.8 X 10
98.7 X 10
43.6
86.9
REBASE + WV
176.8 10
98.7 X 10
42.9
86.9
22


Reviews:
[{"review_id": "FkzYXrjKYd", "reviewer": "Reviewer_8MgV", "summary": "This paper focuses on the intriguing topic inference scaling laws. The authors conducted a detailed analysis using language models of various sizes on math-related datasets, GSM8K and MATH. They discovered that, under the same computation cost, smaller models might outperform larger ones. However, once the performance of smaller models saturates, larger models may achieve better results. These phenomenon is quite significant. Subsequently, the authors carried out theoretical analyses and developed a novel tree search algorithm called REBASE, aiming to achieve a Pareto-optimal trade-off between performance and computational efficiency, following by experiments to demonstrate the effectiveness of the REBASE method.", "questions": "- The authors analyzed inference scaling laws using Pythia and Llemma but did not include REBASE experiments for Pythia, opting instead for Llemma and Mistral-7B. Including REBASE experiments on Pythia could strengthen the findings.\n- The paper focuses on mathematical datasets, yet the title \"LLM Problem-Solving\" suggests a broader scope beyond math. The methods and analysis in Section 3 do not specifically mention \"Math\", indicating potential applicability to other areas. Exploring additional problem-solving domains, like coding or logical reasoning, could enhance the study's relevance and impact.\n- While the models Pythia, Mistral-7B, and Llemma have been around for some time, recent advancements with models like Llama3 show significant progress. Analyzing these newer models could provide valuable insights and keep the research up-to-date.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- This paper conducted experimental analysis using language models of varying parameter sizes on math-related datasets GSM8K and MATH. It was observed that smaller models can sometimes outperform larger models in terms of performance, given the same inference computational cost. Furthermore, the authors noted that once the performance of smaller models reaches saturation, their performance tends to be inferior to that of larger models. These observations are significant.\n- The author conducted a theoretical analysis, demonstrating that the performance of both standard and weighted majority voting inference strategies will converge when there is an infinite number of samples and the performance after convergence depends solely on the distributions modeled by the language model and the reward model. These theoretical analysis aligns with the experimental results.\n- The author proposes a new inference strategy that can achieve comparable or even better performance with less computational overhead than MCTS.\n- The organization of the article is clear, and the writing is excellent. It's easy to understand when reading.", "weaknesses": "- The authors conducted an analysis of inference scaling laws on Pythia and Llemma. However, they did not perform REBASE experiments on Pythia. Instead, they used Llemma and Mistral-7B for these experiments. It would be more convincing if the author could also conduct REBASE experiments on Pythia.\n- This paper only conducts experiments on mathematical datasets. Although the authors acknowledge this limitation, their title is \"LLM Problem-Solving\" rather than \"LLM Math Problem-Solving\". In fact, the analysis and method proposed by the authors are not confined to math-related problem-solving. A clear indication of this is that in Section 3 (theoretical analysis and the introduction of the REBASE method), the term \"Math\" is not mentioned. This suggests that similar phenomena may occur in other problem-solving scenarios. Conducting experiments in a broader range of problem-solving areas, such as coding and logical reasoning or others, would enhance the generalizability of the authors' findings and contribute more significantly to the community.\n- The models Pythia, Mistral 7b, and Llemma were introduced quite some time ago. In the past year, more powerful open-source LLMs like Llama3 have been proposed, achieving remarkable advancements across various metrics. It would be beneficial if the author could continue to analyze these newly introduced and widely used models, such as Llama3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k5qP4pZzYr", "reviewer": "Reviewer_EzJx", "summary": "The study investigates the inference scaling laws for large language models (LLMs), focusing on finding compute-optimal inference configurations. The authors examine the trade-offs between different model sizes and inference strategies, analyzing how these factors impact computing costs and model performance. Through empirical analysis, the study finds that smaller LLMs can outperform larger models given the same computational resources by employing advanced inference strategies. The paper also introduces a compute-optimal inference algorithm which can help small LLMs achieving better cost-performance tradeoffs.", "questions": "Please answer the questions in the weakness section.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The study’s motivation of studying the selection of model size and inference strategy under limited computation budgets is meaningful and justified.\n2. The formal definitions and proofs presented in the paper are clear and maintain good readability.\n3. The integration of a reward model to guide LLMs' inference process is reasonable.\n4. The experimental results are clearly presented and easy to read.", "weaknesses": "1. The paper lacks technical contribution. The proposed REBASE framework merely integrates process reward models (PRM) into the existing Monte Carlo Tree Search (MCTS) framework. Considering these components are well-established and the simplicity of the REBASE framework, there are concerns regarding the novelty of the work.\n2. While the paper employs a PRM as the reward model within REBASE, it fails to detail the training and inference processes of the reward model. Moreover, it does not address how to ensure the reliability of the rewards generated by this model. An unstable or suboptimal reward model could significantly impact the overall framework, and the authors should consider this aspect.\n3. The paper provides theoretical analyses for four inference strategies: greedy search, majority voting, best-of-n, and weighted voting, but does not offer comparative experimental results. A detailed experimental comparison involving different model sizes and inference strategies should be included.\n4. Similar to traditional MCTS methods, REBASE necessitates extensive intermediate interactions with LLMs before obtaining the final generated results. Additionally, it introduces the extra PRM component. This could lead to significant resource consumption. The authors should provide data analysis on resource usage and runtime to demonstrate whether REBASE is more efficient than conventional MCTS methods.\n5. According to the experiments in Section 4.2, both small and large LLMs show high error rates under limited computation scenarios, suggesting that both models are not good enough in these situations. Claiming that smaller models perform better in such conditions is not sufficiently convincing.\n6. The experiments in Section 4.3 show inconsistent performance trends of REBASE compared with sampling methods on the MATH and GSM8K datasets. The authors attribute this inconsistency to differences in dataset difficulty, which seems unconvincing. The authors should provide more credible explanations.\n7. In the scenarios where REBASE is purportedly advantageous (i.e., less compute-intensive situations), the performance on the MATH dataset with Llemma-34B and Mistral-7B models is either weaker than or merely comparable to the Sampling method. This indicates that REBASE does not consistently achieve improvements. An explanation for this should be provided.\n8. The paper only uses two baselines: sampling and MCTS, without elaborating on their implementation details. It would be beneficial to include the latest baselines and provide detailed introductions and comparisons of the baselines and the proposed REBASE method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mtoTUihkDs", "reviewer": "Reviewer_2jwG", "summary": "In this work, the authors study how varying the amount of compute utilized during inference (i.e., varying the number of samples collected during decoding) affects model accuracy on a task. In particular, they explore how to maximize accuracy given a specific compute budget (measured in FLOPs). They experiment with Pythia, Mistral and Llemma models on 2 mathematical reasoning tasks. In experiments, they vary the inference strategy among sampling and tree search methods, coupled with best-of-n selection or weighted majority voting among the generated candidate sets.  Their results show that in many cases, under small compute budgets, smaller models with more compute-intensive inference yields the best results; under large compute budgets, larger models perform better. The results also suggest that their proposed tree-search method–ReBASE–tends to yield the optimal compute-accuracy tradeoff across compute budgets and models. The paper also includes an asymptotic analysis of voting methods as the number of samples goes to infinity. Based on these results, the authors defend a need for more sophisticated inference algorithms.", "questions": "- What is the difference between ReBASE and beam search with sampling turned on? They appear to be quite similar.\n- Not a question, but I think that you may want to discuss the “Dot-by-dot” paper (https://arxiv.org/abs/2404.15758) since it also concludes that generating more tokens can be helpful; albeit their setup is much different from yours.\n- In the expression denoting the reward of a node r_k (last line of page 6), what was q?\n- In Figure 5, what happens if you continue sampling from the 7B model with ReBASE until the maximum number of FLOPs considered (i.e., if we extend the orange line all the way to the right, what does it look like)?\n- Why is test error reported instead of task accuracy? Please report the test accuracy for the sake of comparison to other work.\n- Can you report the number of samples you were able to draw from each model / inference method corresponding to the number of FLOPs used?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "**Topic and Formalization.** I think the question being explored in this paper is interesting and timely–especially considering recent papers, such as those discussed in the concurrent work section. I also find the formalization–maximizing performance under a compute budget–attractive and satisfying. As such, the work is well-motivated, easy to follow and likely to be relevant to many.  Practitioners would be well-suited to consider this type of analysis when deciding what models to deploy.\n\n**Well-designed experiments & complete analysis.** For the experiments that were run, the authors did a good job designing the experiments, and analyzing and visualizing results. The methods selected for comparison are good. I believe that the compute budgets selected are _likely_ good however it would be helpful to report the number of samples drawn for each model/method under each compute budget to make sure they cover a sufficiently large, yet realistic, number of samples.  Generally, it is easy to use the visualizations to see which methods and models are best under various compute budgets. In addition to the discussion of the main results, the discussion of the affect of tree search on weaker models as well as performance saturation adds to the paper. The results make sense and are likely useful. I appreciate the inclusion of error bars.\n\n**Well-written.** The writing is clear and the paper is easy to follow. \n\nOverall, the paper exhibits a number of good characteristics. It’s well written, the topic is interesting, it provides some theoretical analysis, the experiments are solid and the results are relevant.", "weaknesses": "**Mathematics Tasks Only.**  The experiments only study two datasets, both of which are related to mathematical reasoning. As such, I’m concerned about the generalizability to new domains and new tasks. I think this paper could be strengthened with experiments on additional tasks like question answering and/or its variants.\n\n**Limited models tested.**  The set of models tested leaves something to be desired. In my understanding and experience, Pythia models tend to be weak in comparison to newer open-source models, such as the Llama3.1 family of models. Lemma is a special purpose model for the mathematical domain; Mistral-7B is generally understood to be a strong model.  As such, I’m a bit worried that the conclusions would not extend to better models. As is reported, the proposed method, ReBASE, tends to help the weakest models and might not provide the same advantages for a model like Llama3.1-7b-instruct. \n\n**Some results seem insignificant.** Figure 7 shows a lot of overlap amongst the methods tested. This is especially the case for Mistral-7B (which is perhaps the strongest model tested).  This overlap exists in Figure 6 as well; albeit, less so. Again, this makes me concerned about how much the results extend to better models. And, in Figures 4 and 5, ReBASE with the larger models doesn’t seem to be significantly better than sampling.\n\nOverall, I’m concerned about the generalizability of the results to new tasks, and the extent to which the results would hold for the most performant models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZItlP84Iic", "reviewer": "Reviewer_oZkX", "summary": "This paper presents an empirical analysis of inference scaling laws for large language models, focusing on the trade-offs between model sizes and generating additional tokens with different inference strategies. The authors explore how varying the compute during inference affects model performance after the model has been trained. They compare various inference techniques, such as greedy search, majority voting, best-of-n, weighted voting, and two tree search algorithms, using different model sizes and compute budgets.", "questions": "Q1: How well do the findings generalize to non-mathematical reasoning tasks, such as natural language inference or summarization?\n\nQ2: How sensitive are the results to the specific model architectures used in the study? Would different architectures yield similar findings?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "S1. The standpoint of this paper is interesting and can provide some insights into the LLM community.\n\nS2. The paper provides an extensive empirical study on the relationship between model size, inference computation, and performance, which is valuable for both research and practical deployment of LLMs.\n\nS3. The paper analyzes not only the performance of different inference strategies but also provides a theoretical analysis of voting methods, offering insights into their convergence behavior.\n\nS4. The experimental results are clearly presented, making it easy to understand the performance trade-offs between different models and inference strategies.", "weaknesses": "However, there remain some concerns for me:\n\nW1. The analysis is focused on mathematical reasoning tasks, which may limit the generalizability of the findings to other types of problems. In detail, the paper does not provide extensive discussion on how these findings might generalize to other domains beyond mathematical reasoning.\n\nW2. The study is based on specific two LLMs, and it's unclear how the results would extend to other model architectures.\n\nW3. Some of the figures are a bit unclear. For example, in Figures 2 and 3, although the description is vivid, the set font is a bit hard to read.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)