Scaling LLM Test-Time Compute Optimally Can be More Effective than Scaling Parameters for Reasoning
Authors: Charlie Victor Snell
Jaehoon Lee
Kelvin Xu
Aviral Kumar
Venue: ICLR 2025 Oral (2025)
Keywords: test-time compute
LLMs
scaling
language models
Primary area: foundation or frontier models, including LLMs
TL;DR: We find that by optimally scaling test-time compute we can outperform much larger models in a FLOPs matched evaluation.

Abstract: Enabling LLMs to improve their outputs by using more test-time compute is a critical step towards building self-improving agents that can operate on open-ended natural language. In this paper, we scale up inference-time computation in LLMs, with a focus on answering: if an LLM is allowed to use a fixed but non-trivial amount of inference-time compute, how much can it improve its performance on a challenging prompt? Answering this question has implications not only on performance, but also on the future of LLM pretraining and how to tradeoff inference-time and pre-training compute. Little research has attempted to understand the scaling behaviors of test-time inference methods, with current work largely providing negative results for a number of these strategies. In this work, we analyze two primary mechanisms to scale test-time computation: (1) searching against dense, process-based verifier reward models (PRMs); and (2) updating the model's distribution over a response adaptively, given the prompt at test time. We find that in both cases, the effectiveness of different approaches to scaling test-time compute critically varies depending on the difficulty of the prompt. This observation motivates applying a "compute-optimal" scaling strategy, which acts to, as effectively as possible, allocate test-time compute per prompt in an adaptive manner. Using this compute-optimal strategy, we can improve the efficiency of test-time compute scaling for math reasoning problems by more than 4x compared to a best-of-N baseline. Additionally, in a FLOPs-matched evaluation, we find that on problems where a smaller base model attains somewhat non-trivial success rates, test-time compute  can be used to outperform a 14x larger model.

Published as a conference paper at ICLR 2025
SCALING LLM TEST-TIME COMPUTE OPTIMALLY CAN BE MORE EFFECTIVE THAN SCALING PARAMETERS FOR REASONING
Charlie Snell", Jachoon Lee Kelvin Xu Aviral Kumar
ABSTRACT
Enabling LLMs to improve their outputs by using more test-time compute is a crit- ical step towards building self-improving agents that can operate on open-ended natural language. In this paper, we scale up inference-time computation in L.M,s, with focus on answering: if an L.M allowed to use a fixed but non-trivial amount of inference-time compute, how much can it improve its performance a challenging prompt? Answering this question has implications not only on perfor- mance, but also the future of LLM pretraining and how tradeoff inference- time and pre- wre-training compute. Little research has attempted to understand the scaling behaviors of test-time inference methods, with current work largely pro- viding negative results for number of these strategies. In this work, we analyze primary mechanisms scale test-time computation: (1) searching against dense, process-basse based verifier reward models (PRMs): and (2) updating the model's 's distribution over response adaptively, given the prompt test time. We find that in both cases, the effectiveness of different approaches to scaling test-time com- pute critically varies depending on the difficulty of the prompt. This observation motivates applying a "ccomuut--optina"" scaling strategy, which acts to, as effec- tively as possible, allocate test-time compute per prompt an adaptive manner. Using this compute-optimal strategy, we can improve the efficiency of test-time compute scaling for math reasoning problems by more than 4x compared to a best-of-N baseline. Additionally, in problems where a smaller base model attains somewhat non-trivia success rates, test-time compute can be used to outperform 14x larger model.
evaluation, find that on
INTRODUCTION
Given a challenging input, can enable LLMs to most effectively make use of additional com- putation at test-time to improve their responses? In theory. additional test-time compute should enable LLM to do better than what it was trained do in zero-shot. Such capability at test- time bears the potential to unlock agentic and reasoning abilities (Shinn et al., 2023; Qu et al., 2024b). Additionally, if pre-trained model size be traded off for additional inference compute, this would enable the deployment of smaller on-device models in place of datacenter scale LLMs.. Automating the inference-time improvement of model outputs also provides path towards general self-improvement algorithm that can function with reduced human supervision.
Prior work studying inference-time computation provides mixed results. On the one hand, some prior work shows that current LLMs can use test-time computation to improve their outputs (Bai al.. 2022; Madaan et al., 2023; Du al., 2023; Saunders et al., 2022; Yao al., 2023), on the other hand, several other works show that the effectiveness of these methods on complex tasks such as math reasoning remains limited (Huang et al., 2023; Stechly et al., 2023; Valmeekam al., 2023; Wang et al., 2024a; Olausson et al., 2024). However, reasoning is domain we should expect to benefit from test-time compute, since reasoning involves drawing inferences from existing knowl- edge as opposed to acquiring new knowledge. Therefore, the disagreement in these prior findings motivates the need for a systematic analysis of different approaches for scaling test-time compute.
In this paper we understand the pros and cons of scaling up test-time compute, and how it compares with scaling up pre-training compute. While the simplest approach for scaling test-time compute is best-of-N sampling sampling N outputs in "parallel" from base I.LM and selecting the that scores the highest per a learned verifier or a reward model (Cobbe et al., 2021; Lightmnnn et al., 2023)
'UC Berkeley (work done during an internship at Google DeepVindy; &Google Deep CMMU; Fiqual advising

---

Published as a conference paper at ICLR 2025
Iteratively Revis ing Answers
Companin
Compure
Computa Optinal Redsiors
In FLOPs Natched Evaustion
Parita
Re Rigatve arprovcrtnn Alpuu
10
From Curpa
30
10
Vaauus Qustira
201
Generation Sudger
Rute ofiifeoroo Tosara la Prezeinig Tokers
Test-time Search Against Verifir
Pretnining
Compute Opiraal Search
a
FLOPs Matthed Evauation
Worth Pilec Our Outivel
Ruatke Liper Erpeovennn ni pr0r
100TH Nocune
20
30
Uniue Suntion
Dudgel
Sato briennce Tokero Protuningg Tokero
Figure 1: Summmary of results. Left: Compute-optimal scaling for revisions and search. We compare the compute-optimal scaling policy with PaLM 2-S* against haselines in the revision (top) and PRM search (bottom) settings. In the revision setting, we find that compute-optimal scaling outperforms best-of-N with 4x less compute. Similarly, with PRM search, compute-optimal scaling shows large early improvements over best- of-N. nearly outperforming best-of-N with 4x less compute points (see Sec. 5 and 6). Right: Comparing test-time compute and parameter scaling, We compare compute-optimal test-time scaling with PaLM 2-5* against 14x larger model without additional test-time compute. We expect X tokens of pretraining for both models and Y tokens inference. larger model, multiplics the FLOPs for both. If we were to apply additional test-time compute to the smaller model, to match this FLOPs multiplier, we see that for the revisions (top) when Y << X, test-time compute is preferable to pretraining. As inference to pretraining ratio increases, test-time compute is preferable easy questions. However, hard questions, pretraining is preferable.
there are many other ways we could conceivably scale up test-time compute. We unify methods into those that modify either the proposal distribution from which responses are sampled (for e.g., by asking the base model to revise its responses (Qu al., 2024b)) or those that alter how the verifier is used for searching directly in the output space (e.g. by training a PRM (Lightman et al., 2023)).
To understand the benefits of scaling up test-time compute, we carry out experiments on MATH (Hendrycks et al., 2021) using PaLM-2 (Anil et al., 2023) models fine-tuned to either revise incorrect answers (Qu et al., 2024b) (e.g. improving the proposal distribution; Section 6) or verify the correctness of individual steps in answer using process-basce reward model (PRM) (Light- man et al., 2023; Wang et al., 2023) (Section 5). We find that the efficacy of different test-time strategies depends both the nature of the specific problem at hand and the base L.M used. For example, on "easier" problems, for which the base LLM can already produce reasonable-looking responses, allowing the model to sequentially revise its initial answer (i.e., modifying the proposal distribution) is a more effective use of compute than reranking N independent answers sampled in parallel. On the other hand, on difficult problems which require searching over many high-level strategies, re-sampling new responses independently in parallel or deploying tree-search against process reward model is more effective. This underscores the need deploy an adaptive "compute- optimal" strategy for scaling test-time compute, wherein the specific approach for utilizing test-time compute selected depending on the prompt, so as to make best use of additional computation. We also show that notion of question difficulty (Section 4) from the perspective of the base LLM can be used to predict the efficacy test-time computation, enabling us to practically instantiate this coompute-pptimal scaling. By appropriately allocating test-time compute in this way, are able to greatly improve test-time compute scaling, surpassing the performance of a best-of-N baseline while only using ~ 4x less computation with both revisions and search (Sections 5 and 6).
Using our scaling strategy, we then study to what extent test-time computation can substitute for additional pretraining. Specifically, conduct FLOPs-matched comparison between smaller
2

---

Published as a conference paper at ICLR 2025
model with test-time compute and pretraining a 14x larger model. We find that easy and interme- diate questions, additional test-time compute is often preferable to scaling pretraining. This finding suggests that rather than focusing purely scaling pretraining, in some settings it is more efficient to pretrain smaller models with less compute, and then apply test-time compute to improve outputs. That said, with the most challenging questions, we observe few benefits from scaling up test-time compute. Instead, on these questions, it is more effective to make progress by applying additional pretraining, demonstrating that current approaches to scaling test-time compute may not be 1-to-1 exchangeable with scaling pretraining. Overall, this suggests that even with fairly na've methodol- ogy, scaling up test-time computation can already be preferable to pretraining in some settings, with only more improvements test-time strategies mature. Longer term, this hints at a future where fewer FLOPPs are spent during pretraining and more FLOPs are spent at inference.
2 UNIFIED PERSPECTIVE ON TEST-TIME COMPUTE: PROPOSER & VERIFIER
We first provide an unified abstraction of test-time compute to situate contemporary approaches. We view the use of test-time compute through the lens of modifying the model's 's distribution on a given prompt, adaptively at test-time. Ideally, test-time compute should allow for the ability to express more complex distributions than naively sampling from the L.M.. In general, there are two knobs to modify an LLM's distribution: (1) at the input level: by augmenting the given prompt with an addi- tional set of tokens that the LLM conditions on to obtain a modified proposal distribution, or (2) at the output level: by sampling multiple candidates from the standard LLM and performing surgery on them, using some post-hoc verifiers or scorers. This process is reminiscent of Markov chain Monte Carlo (MCMC) (Andrieu et al., 2003) sampling from a complex distribution by combining a simple proposal distribution and a score function. Modifying the proposal distribution by altering inputs tokens and using a verifier form the two independent axes of our study.
(1) Modifying the proposal distribution. One way improve the proposal distribution is di- rectly optimize the model for a given reasoning task via RL-inspired finetuning methods such as STaR or ReSTEM (Zelikman et al., 2022; Singh et al., 2024). These techniques specifically finetune the model directly improve the proposal distribution, rather than generating additional tokens at test-time. Instead, techniques such as self-critique (Bai et al., 2022; Madaan et al., 2023; Du et al., 2023: Saunders et al., 2022) enable the model to improve its own proposals test time by instructing it to critique and revise its outputs iteratively. Since prompting off-the-shelf models is not effective at enabling effective revisions at test time, we specifically finetune models to iteratively revise their answers for complex reasoning, using Best-of-N guidance (Qu et al., 2024b; Kumar et al., 2024).
(2) Optimizing the verifier.
The verifier selects the best answer from the proposal distribution. The most canonical way to use such a verifier is by applying best-of-N sampling, wherein we sample solutions and then select the best one with a verifier (Cobbe et al., 2021). This approach can be further improved by training a process-based reward model (PRM) (Lightman et al., 2023), which produces a prediction of the correctness of each intermediate step in a solution. We can then utilize these per-step predictions to perform tree scarch over the solution space, enabling more effective modification of the proposal distribution (Yao et al., 2023; Feng et al., 2024; Chen et al., 2024).
HOW TO SCALE TEST-TIME COMPUTATION OPTIMALLY
Using this unified view of different methods, we would like to understand and characterize how to most effectively use test-time computation to improve performance the question below. When either refining the proposal distribution or searching against a verifier, there are numerous choices on how allocate test-time compute. For example, when using a model finetuned for revisions as the proposal distribution and an ORM verifier, we could either spend the full test-time budget on generating N independent samples in parallel from the model and then apply best-of-N, or we could sample N revisions in sequence using a revision model and then select the best answer in the sequence with an ORM, or strike a balance between these extremes. Intuitively, we might expect that problems where the initial samples are more likely to be on the right track to benefit more from revisions. On the other hand, problems that require exploration over high- level problem solving strategies might benefit from sampling more independent answers in parallel. Finally, in the case of verifiers, we also can choose between different search algorithms (e.g. beam- best-of-N), each of which may exhibit different properties depending on the quality of the verifier and proposal distribution at hand. More sophisticated search procedures might be more useful in harder problems compared to much simpler best-of-N - or majority baseline.
given prompt by answering
search, mookaheadssearch
3

---

Published as a conference paper at ICLR 2025
Problem setup
We are given a prompt and a test-time compute budget within which to solve the problem. Under the abstraction above, there are different knobs we can tune when utilizing test-time computation. How we determine the most effective way utilize test-time compute for given prompt? And how well would this do against simply utilizing much bigger pretrained model?
3.1 COMPUTE-OPTINAL
TEST-TIME SCALING STRATEGY
Per the discussion above, we would like to prescribe the optimal allocation of our test-time compute budget onto a given problem. To this end, for any given approach of utilizing test-time compute (e.g., revisions and search against a verifier in this paper, some combination or other methods in general), define the "lest-time compute-optimal scaling strategy" the strategy that chooses hyperparameters appearing in a given approach for maximal performance benefits on a given prompt at test time. Formally, define Torget(O, NN, q) the distribution over natural language output tokens induced by the model for a given prompt g. using test-time compute hyper-parameters 8, and a compute budget of N. We would like to select the hyper-parametert 0 which maximize the accuracy of the target distribution for given problem. We express this formally as:
Gga (x) (N) = argmaXx (Ey-Tarrgct(,NN.gg (<)=))())))
(1)
where vz) denotes the ground-truth correct response for input query q, and 0" 9.5 (N) repre-
sents the test-time compute-optimal scaling strategy for the problem q with compute budget N. We note that our definition of test-time compute-optimal scaling differs slightly from that of concurrent work (Wu et al., 2024) in that notion of scaling is question dependent.
3.2 QUESTION DIFFICULTY IS A GOOD APPROXIMATION FOR THE OPTIMAL STRATEGY
In order effectively analyze the test-time scaling properties of the different mechanisms discussed in Section 2 (e.g. proposal distribution and verifier), we will prescribe an approximation to this optimal strategy 0i.y ('.y-(g)(A) as a function of a statistic of given prompt. Our approximation estimates a notion of difficulty for a given prompt. The compute-optimal strategy is then defined as a function of the difficulty of prompt. Despite being only an heuristic approach to solve Equation 1, we find that it can still induce substantial improvements in performance over a baseline strategy of allocating this anference-time compute in ad-hoc manner.
Our estimate of question difficulty assigns a given question to one of five discrete difficulty lev- els. We then use these bins to estimate 6* (o) (o) (N) a validation set (given a compute budget), and apply the optimal strategy the test Thus, question difficulty acts as a sufficient statistic for designing the compute-optimal strategy. For example, to optimally allocate test-time compute between parallel best-of-N and sequential sampling, we first pre-compute the accuracy of both tech- niques within each difficulty bin using held-out set. Given a new test question, we then determine the difficulty bin belongs to and select the best performing strategy within that bin.
Defining question difficulty. Following Lightman et al. (2023), we define question difficulty as a function of the given base LLM. Specifically, we bin the model's pass@ rate estimated from 2048 samples- on each test question into five quantiles, each corresponding to increasing difficulty levels. We find this notion of model-specific difficulty bins to be more predictive of the efficacy of using test-time compute compared to the hand-labeled difficulty bins in the MATH dataset.
That said, we note that assessing difficulty as described assumes oracle access to a correctness checker, which is unavailable at deployment. To enable realistic estimate of difficulty, we approx- imate difficulty via a prdeel-reddicedd notion of difficulty, which constructs the bins by averaging the score of learned verifier on the same 2048 samples per problem. We refer to this setting as model-predicted difficulty and the setting which relies on ground-truit correctness as oracle difli- culty. Predicted difficulty removes the reliance on ground truth labels, but still incurs computational cost. Our experiments do not account for this cost largely for simplicity, since our goal is to present some of the first results of what is in fact possible by effectively allocating test-time compute.
4 EXPERIMENTAL SETUP
We first outline our experimental setup for conducting this analysis with multiple verifier design choices and proposal distributions, followed by the analysis results in the subsequent sections.
4

---

Published as a conference paper at ICLR 2025
Best-of-N
Beam Search
Lookahead Search
Durbae
Select beee
Selecttee that rether
Apply Vertier
Solution
Internadiate colution stop
Sedected by veritar
Rejected by vertier
Figure 2:
Comparing different PRM search methods. Left: Best-of-N samples full answers and then
selects the best answer according to the PRM final score. Center: Beam search samples N candidates at each step, and selects the top M according to the PRM to continue the search from. Right: lookahead search extends each step beam-search to utilize k-step lookahead while assessing which steps retain and continue the search from. Thus lookahcad-searde needs more compute.
Datasets. We expect test-time compute to be most helpful when models already have all the basic "knowledge" needed answer query, and instead the primary challenge is about drawing (com- plex) inferences from this knowledge. To this end, we focus on the MATH (Hendrycks et al., 2021) benchmark, which consists of high-school competition level math problems with range of difficulty levels. For all experiments, we use the dataset split consisting of 12k train and 500 test questions.
Models. We use the PaLM 2-S* (Anil et al., 2023) (Codey) model. We chose this model, as it is representative of the capabilities of many contemporary LLMs, and is small enough to efficiently run many experiments on. Most importantly, this model attains non-trivial performance on MATH (but not saturated). For these reasons, we expect this model to provide good test-bed.
5 SCALING TEST-TIME TIME COMPUTE VIA VERIFIERS
In this section, we study how test-time compute can be most effectively scaled by searching against a verifier and keeping the proposal distribution fixed to the base LM. Specifically, we study different search approaches with PRMs and analyze their test-time compute scaling properties, but first provide a brief overview of how a PRM can be trained.
5.1 TRAINING VERIFIERS A AMENABLE TO SEARCH
We follow the approach of Wang et al. (2023), which supervises the PRM using estimates of per-step correctness obtained from running Monte Carlo rollouts from each step the solution. Our PRM's per-step predictions therefore correspond value estimates of reward-to-go for the base model's sampling policy, similar to recent work (Wang et al., 2023; Setlur et al., 2024). We also compared to an ORM baseline (Appendix H) but found that our PRM consistently outperforms the ORM. Hence, all of the search experiments in this section use a PRM model. Additional details are in Appendix F.
Answer aggregation. At test time, PRMs can be used to score each individual step appearing in set of solutions sampled from the base model. To pick out the best answer from N samples with the PRM, we need a function that can aggregate across all the per-step scores for each answer to determine the best candidate for the correct answer. To do this, we take the PRM's prediction at the last step as representative of the full-answer score and then follow et al. (2023) by applying "best- of-N weighted" selection across answers. We include more detail on these decisions in Appendix G.
5.2 SEARCH METHODS AGAINST A PRM
We optimize the PRM at test time via tree search methods. We study three search approaches that sample outputs from few-shot prompted base I.LM (see Appendix J). An illustration is shown in
5

---

Published as a conference paper at ICLR 2025
Comparing PRM Search Methods
Comparing Beamn Search and Blett-d-NN Difficully Level
Bisiut Worghttd
Misritt
MATH Text Actuaney (8)
Tost Teot/GGurT (%)
80
29
40
Seare progth
Seare
Step Lociahest
10
Conerition Budget
Tuxt Quaodions Birned by incressing Dificulll Lanal
Figure 3: Left: Comparing different methods for conducting search against PRM verifiers. We see that low generation budgets, beam search performs best, but as scale the budget further the improvements diminish, falling below the best-of-N baseline. Lookahcad-searre the same generation budget. Right: Comparing beam search and best-of-N binned by difficulty level. The four bars in each difficulty bin correspond to increasing test-time budgets (4, 16, 64, and 256 generations). On the easier problems (bins 1/2), beam search shows signs of over-optimization at higher budgets, whereas best- of-N does not. On the medium difficulty problems (bins 3/4), beam search consistently outperforms best-of-N.
generally underperforms other methods at
Figure 2. We note that for all search algorithms, we use the same PRM verifier, enabling an even comparison. We include additional details about our different search methods in Appendix C.
Best-of-N weighted. We sample N answers independently from the base LLM and then select the best answer according to the PRM's final answer judgment.
Beam search. Beam search optimizes the PRM by searching over its per-step predictions. Our implementation is similar to BFS-V (Yao et al., 2023; Feng et al., 2024). Concretely, we consider a fixed number of beams N and beam width M. At the end of the search we have N final answer candidates, to which we apply best-of-N weighted selection to make our final answer prediction.
Lookahead search. Lookahead search modifies how beam search evaluates each step, At each step in the search, rather than using the PRM score at the current step to select the top options, lookahead search performs a simulation, rolling out steps. We stop early if the end of a solution is reached.
5.3 ANALYSIS RESULTS: TEST-TIME SCALING FOR SEARCH WITH VERIFIERS
We now present our results comparing various search algorithms and identify prompt difficulty dependent compute-optimal scaling strategy for search methods.
Comparing search algorithms. We first conduct sweep over different search settings. In addition to the standard best-of-N approach, we sweep over the two main parameters that distinguish these methods: beam-width M and number of lookahead steps k. While we are not able to exhaustively sweep all configurations, we sweep over the following settings with a maximum budget of 256: 1) Beam search with the beam width set to vN, where N is the generation budget; 2) Beam search with a fixed beam width of 4; 3) Lookahead search with k = 3 applied to both beam-search settings 1) and 2); 4) Lookahead search with k = 1 applied to beam-search setting 1).
To compare search methods as a function of generation budget fairly, we estimate the inference- time cost of each method. For beam search and best-of-N the generation budget corresponds to the number of beams and N respectively. Lookahead search utilizes additional compute: at each step, sample k additional steps ahead. Therefore, the cost of lookahead-search is N x (K- + 1) samples. Querying the verifier also adds a 2x overhead for all methods but we account for this in our analysis.
Results. As shown in Figure 3 (left), with small budgets, beam search outperforms best-of-N. However, at high budgets, these improvements diminish, with beam search underperforming, Ad- ditionally, lookahead-search underperforms other methods, likely due to the additional computation induced by looking ooking-aheaa. It is possible that with further test-time scaling or with an online MCST trained value function, lookahead search may perform better; we leave further exploration of this to future work. The diminishing returns from search are likely due to exploitation of the PRM's predictions. For example, we see instances (such as Figure 32), where search causes the model to generate repetitive low-information steps. In other cases, we find that ovtriopti search can re- sult in overly short solutions, of just 1-2 steps. We include several of these examples in Appendix R.

---

Published as a conference paper at ICLR 2025
Compule Optimal Search
Which problems does search improve? To un- derstand how to scale search adaptively per prob- lem, conduct difficulty bin analysis. Specif- ically, we compare beam-search (M = 4) against best-of-N. In Figure 3 (right), find that, de- spite performing similarly in aggregate, the two
40
-6- FRV Compole Cotima Drude
MATH test Ansummy
-8-
Compulo Phekioed
30
methods exhibit very different behavior across difficulty levels. For example, on easy ques- tions (levels 1/2), the stronger optimizer of the two, beam search, degrades in performance as the budget increases, suggesting possible exploita- tion of the PRM signal. In contrast, on the harder questions (levels 3/4), beam search outperforms best-of-N. Finally, the most difficult questions (level 5), no method makes meaningful progress. These findings match intuition: we might expect that on the easy or medium difficulty questions, the verifier will make mostly correct assessments of correctness. Therefore, by optimizing further, we may be only further amplifying any spurious features learned by the verifier, causing perfor- mance degradation. On more difficult questions, the base model less likely to sample the correct answer, so using search can help steer the model.
16
10
Budget
Figure 4: Comparing compute-optinal test-time scaling against baselines with PRM search. By scaling test-time compute optimally, we nearly out- perform PRM best-of-N using up to 4x less test- time compute (c.g. 32 versus 128 generations). "Compute-optimal oracle" refers to using oracle difficulty bins derived from the groundtruth correct- ness, and "compute-optimal predicted" refers to ing the PRM's predictions to generate difficulty bins.
Compute-optimal search. Given the above, it is clear that question difficulty is a useful statistic for predicting the best search strategy at each budget. Additionally, the selected best search strategy varies as a function of difficulty. We visualize this "compute-optimal" scaling trend, as represented by the best performing search strategy, between best-of-N and beam search (M 4), at each difficulty level in Figure 4. Interestingly. we see that with low budgets, using both the oracle and predicted difficulty. compute-optimal scaling can nearly outperform best-of-N using up to 4x less test- time compute (e.g. 16 versus 64 generations). While at higher budgets, some of these benefits diminish with the use of predicted difficulty, but the oracle bins still see improvements from optimal scaling. This result demonstrates that there are clear performance gains to be obtained by adaptively allocating test-time compute during search using predicted difficulty an input statistic.
Takeaways for compute-optimal scaling of verifiers
We find that the efficacy of any given verifier search method depends critically on both the compute budget and the question hand. Specifically, beam-search more effective on harder questions and at lower compute budgets, whereas best-of-N is more effective on easier questions and at higher budgets. Moreover, by selecting the best search setting for given question difficulty and test-time compute budget, can nearly outperform best-of-N using up to 4x less test-time compute.
REFINING THE PROPOSAL DISTRIBUTION
Now we study how the proposal distribution be used for test-time scaling (Section 2). Con- cretely, we enable to improve its own distribution at test-time, by revising answers iteratively. Simply prompting existing LLMs to correct themselves tends be largely ineffective on reason- ing (Huang et al., 2023). Therefore, we finetune LLMs to iteratively revise their answers.
6.1 TRAINING AND USING REVISION MODELS
Our procedure for finetuning revision models is similar to Qu et al. (2024b), though we introduce some crucial differences. For finetuning, we need trajectories consisting of a sequence of incorrect answers followed by correct answer, that we then run SFT on. To do this, sampled 64 responses in parallel and post-hoc constructed multi-turn rollouts from these independent samples. These rollouts consist of up to four incorrect attempts in context followed by a correct revision. We include more details on our revision model finetuning procedure in Appendix L.
Using revisions at inference-time. Given finetuned model, we then sample a sequence of revisions from the model at test time. While our revision model is only trained with up to four pre- vious answers in-context, we can sample longer chains by truncating the context the most recent
7

---

Published as a conference paper at ICLR 2025
Parallel Sumpling
Using Revision Model Vertferat
Ar So 7M4 yapilne
Parallel Best-ol-
Sequential Revisions
Werler whec
bes
and emp hupar??
LM
A: 4 dep....
suriilyy pendie
Fw
yapsrcop
Combining Sequential Paratiel
Sequential Revisions
cordilien pREvas removes
anovee with each chain
Piat, and orgul A.p hope??
LM
Ve
Figure 5: Parallel sampling (e.g., Bext-of-N) versus sequential revisions. Left: Parallel sampling generates N answers independently, whereas sequential revisions generate each one in sequence conditioned on previous attempts. Right: In both the sequential and parallel cases, we use the verifier determine the best-of-N answers. We can also split our budget hetween parallel and sequential sampling. In this case, first use the verifier to select the best answer within each sequential chain and then select the best answer acmoss chains.
four revisions. In Figure 9left), we see longer chains gradually improve pass @k demonstrating that we are able to effectively teach the model to learn from mistakes in previous answers.
That said, there is distribution shift inference time: the model was trained only sequences with incorrect answers in context, but at test-time the model may sample correct answers. Thus, the model may turn correct answer into an incorrect one. Similar to Qu et al. (2024b), around 38% of correct answers get converted to incorrect with our model. Thus, we employ either sequential majority voting or verifier- verifier-guided selection to select the correct answer from the sequence of revisions (see Figure 5). Querying the verifier adds a 2x compute overhead, and we account for this in our analysis.
Comparisons. To test the efficacy of modifying the proposal distribution via revisions, we up comparison between the performance of sampling N revisions in sequence and sampling N attempts question in parallel. We see in Figure 9 (right), that with both the verifier-based and majority- based selection mechanisms, sequential sampling outperforms parallel sampling.
6.2 ANALYSIS RESULTS: TEST-TIME SCALING WITH REVISIONS
We see that sampling sequentially outperforms in parallel. We might expect however, that these approaches have different properties. Intuitively, sampling in parallel acts as a global search pro- cess that could, in principle, provide coverage over many different approaches for solving a problem. Sequential sampling, on the other hand, may work more as a local refinement process. This motivates striking balance between these two approaches by allocating some of our budget to parallel sampling (e.g. vN) and the rest to se- quential (e.g. VN). We will now show the exis- tence of a compute-optimal ratio between sequen- tial and parallel sampling, and understand their pros and cons based on the difficulty of a prompt.
Compute Optimal Revisione
Hijott
Weigest
Durqu to Optinal Prodetor Pusiie
MATH Feet Accurncy
12- 20
Budget
Figure 6: Compute-optinal scaling with our revi- sion model. By optimally scaling test-time compute, we outperform best-of-N with 4x less compute (i.c., 128 samples versus 512). "Compute Optimal Ora- cle" refers to difficulty derived from ground truth cor- rectness and "Compute Optimal Predicted" refers to using the PRM to estimate difficulty.
Trading off sequential and parallel compute. To understand how to allocate sequential and par- allel compute, we perform a sweep over different configurations. We see, in Figure 7 (left), that in- deed, at given budget, there exists an ideal sequential to parallel ratio. We also see in Figure 7 (right) that this ideal ratio varies depending on question difficulty. Easy questions benefit more from revisions, whereas difficult questions it is optimal to strike balance between sequential and parallel computation. This finding supports the hypothesis that sequential revisions (i.e., varying the proposal distribution) and parallel sampling (i.e., search with verifiers) complementary axes for
8

---

Published as a conference paper at ICLR 2025
Varying Sequentia
Revisionss11 128, Varying the Sequential Ratio
MATH Teal Acsuracy
Numbor Gemeentans
MATH Accuracy
09
20
Suquantia Panallal
Test Questions B Binnod by Increasing Diffouily Level
Figure 7: Left: Varying the ratio of the generation budget allocated sequential revisions to versus parallel samples. Each line represents fixed generation budget the ratio changed. We use the verifier for answer selection. We see that while increased sequential revisions tends to outperform more parallel compute, at higher generation budgets there is an ideal ratio that strikes a balance between the two extremes. Right: Varying the sequential to parallel ratio for a generation budget of 128 across difficulty bins. Using verifier-hased selection, see that the casier questions attain the best performance with full sequential compute. On the harder questions, there ideal ratio of sequential to parallel test-time compute.
scaling test-time compute, which may be more effective of our model's generations in Appendix Q Additional results are in Appendix D.
per-prompt basis. We include examples
Compute-optinal revisions. Given our finding that the efficacy of sequential and parallel sampling depends on difficulty, we can select the ideal ratio of sequential to parallel compute per difficulty bin (we describe the specific ratios in Appendix O). In Figure 6, we plot results using compute- optimal scaling when employing both oracle and predicted difficulty. In both cases, we substantially improve test-time compute scaling by optimally scaling the proposal distribution. In particular, see that at higher generation budgets, parallel sampling plateaus, whereas compute-optimal scaling continues to improve. For both oracle and predicted difficulty, see that compute-optimal scaling can oulperform best-of-N using up to 4x less test-time compute (e.g. 64 samples versus 256). Overall, these results demonstrate the potential for improved test-time compute scaling by adjusting the proposal distribution on per-prompt basis.
Takeaways for compute-optimal scaling by refining the proposal distribution with revisions
We find that there exists tradeoff' between sequential (e.g. revisions) and parallel (e.g. standard best- of-N) test-time computation, and the ideal ratio of sequential parallel test-time compute depends on both the compute budget and the specific question hand. Specifically, easier questions benefit from purely sequential test-time compute, whereas harder questions often perform best with an ideal ratio of sequential to parallel compute. By selecting the best setting for given question difficulty and compute budget, can outperform the parallel hest-of-N baseline using up to 4x less test-time compute.
7 EXCHANGING PRETRAINING AND TEST-TIME COMPUTE
We saw that utilizing additional test-time compute can enable us to represent more complex distri- butions than the one predicted by the base LLM, thereby increasing performance. We now posit that this increased flexibility of representing distributions means that we can expect additional test- time compute to make up for the lack of a gigher-capccity model or training for more FLOPs during pretraining. In this section, we study to what extent this is possible. We pose the following question:
Question: Exchanging pretraining and test-time compute
Suppose model pre-trained with X FL.OPs Assume that plan to run Y FL.PPs of inference with this model. If we want improve performance by increasing the total FLOPSs budget by factor of M (i.e.. (X total FLOPs across both pretraining and inference). should we spend our FLOPs on increased pretraining compute or on additional test-time compute?
Increasing pretraining FLOPS introduces the additional design decision of whether to allocate com- pute to training with more data in which model parameters are scaled up and training data amount is fixed, matching the canonical approach from the LLLMA series of models (Touvron et al., 2023).
parameters (Hoffmann al., 2022). We focus the setting

---

Published as a conference paper at ICLR 2025
Comparing Test-time and Pretraining Compute
Revisions
PRM Search
MATH Difiiuuy Lavel Actunccy (%)
MATH Difficully Level Accurscy (%)
80
Diffica Level
60
40
40
20
20
2'
2
2
2'
2
Proportional tn Inforence FLOPs
Proportional to Inferance FLOPs
Protrshing Compute
Compute
Figure 8: The tradeoff between pretraining and test-time compute in a FLOPs-matched evaluation. Each line represents the performance of scaling test-time tim- compute with our compute optimmll policy in cach oracle difficulty bin for revisions (left) and search (right). The stars represent the greedy pass@ I performance of a base model pretrained with ~ 14 times more parameters. We plot test-time compute budget on the x-axis and stars three different locations along the x-axis, each corresponding to the FLOPs equivalent point of comparison between scaling parameters and scaling test-time compute for three different inference compute loads (e.g. R= Duicens)) ). If star below the line, this implies that it more effective use test-time compute than to Dyaman
scale model parameters,
the star is above line this implies that scaling parameters is more effective. We see that on the easy questions or in settings with a lower inference load (e.g. It << 1), lest-time compute generally outperform scaling model parameters. However, on the harder questions or in settings with higher inference load (e.g. R >> 1). pretraining more effective way improve performance.
Exchanging FLOPs. We use the common formula for pretraining FLOPs X = 6N pretram (Hoff- mann al., 2022), and for inference FLOPs, we use = 4N D inference (Sardana Frankle, 2023), which multiplies the standard 2.N Dinference by two to account for the overhead of calling the verifier. Here N represents model parameters, Dprttmin is the total tokens used for pretraining, and Dinference the total tokens generated at inference. If we multiply N by factor of M, then both the pretraining and inference FLOPs (due to the cost of greedy decoding with the larger model) increase by factor of M, giving total of M + Y) FLOPs.
To match the FLOPs between scaling parameters and scaling test-time compute, we multiply the smaller model's 's inference compute by M (Dree/ Daut) (M 1M1 Notably, this multiplier depends on the ratio D Dree/ Dint- We refer to the inverse of this ratio as R Dint/ Dpre Depending on the specific production setting, we should expect very different values of R. In particular, in large scale production settings, we may expect more inference tokens than pretraining tokens, in which case we have >> On the other hand, in many self- ceffiimprveement setups, we would likely generate fewer inference tokens than pretraining tokens, giving R << 1. Therefore, since the scale of test-time compute depends on this ratio, we expect differing conclusions depending on the specific setting.
In Figure 8, we use this approach to exchanging test-time and pretraining compute to compare our compute-optimal scaling against scaling up model parameters by factor of ~ 14. We conduct comparisons for 3 values of R: 0.08 (R << 1), 0.40 (R ~ 1), and 11 (R >> 1), with each ratio corresponding to an inference budget. Observe that we only expect to see difficult questions (e.g. bins 4/5) or have larger Dinference (i.e., larger R value), then it is often more effective to allocate compute towards pretraining (e.g. the star is above the line). instead, we expect mostly easy or in- termediate difficulty questions (e.g. bins 1-3 and sometimes 4) or have lower inference requirements (as is the case in self-improvemmnt pipelines), then scaling test-time compute preferred.
Takeaways for exchanging pretraining and bist-time compute
Test- tist-time and pretraining compute are not 1-to-1 "exchangeable". settings with a small inference requirement or on questions of moderate difficulty, test-time compute can substitute for pretraining. However, on challenging questions or under higher inference loads, pretraining is likely more effective.
Conclusions. Please see Appendix for a detailed discussion of limitations and future work.
We do not account for finetuning FLOPs, since it is negligible compared to pretraining FLOPs. Even if we accounted for finetuning Fl,OPs, it would not change the overall conclusions of our analysis. We conduct additional analysis in Appendix K to better understand the effect of finetuning on our analysis.
10

---

models in Published as a conference paper at ICLR 2025
8 REPRODUCIBILITY STATEMENT
Our work does not propose any new method and instead conducts analysis using methods proposed in prior works (Wang et al., 2023; Kumar et al., 2024; Welleck et al., 2022; Yao et al., 2023; Qu et al., 2024b) on the popular MATH benchmark (Hendrycks et al., 2021) using the PaLM 2-S* (Anil al., 2023) model. We include extensive details about differences between our work and these prior works that we build on in Sections 5 6 and Appendices C, L, F, G, M, N. J, O including all relevant fine-tuning hyper-paree ppper-parameters used. We also conduct numerous ablations in Sections 5, and Appendix D. E. G, H. N, P. K, and include handful of examples outputs from Appendix R and Q. We believe that all of these details included in the paper contribute to our work's ' reproducibility. The base LLM that we used for our analysis, PaLM 2-S*, can be accessed for both finetuning and inference on the Google Cloud Vertex API (it is referred to as Codey on the API).
Reproductions and subsequent build-ups. Since the paper submission deadline, two subsequent works from Beeching et al. and Liu et al. (2025) have independently reproduced our main findings using open LLMs (e.g. LLaMA and Qwen models) and using other math benchmarks (e.g. AIME- 2024). These results provide additional evidence to support the title and main clam made in this paper that scaling test-time compute can outperform scaling model parameters.
We also remark that more recently, OpenAl ol/o3 models (OpenAI, 2024b) and DeepSeek RI (Aee 2025) models have demonstrated that training models output extended chains of thought (similar in spirit to the iterative revision approach we study), can be highly effective way to enable test time scaling. While we do not analyze this exact approach to test-time scaling in this work, since this approach came out after this paper, these results only further strengthen our main claim about the efficacy of test-time scaling.
ACKNOWLEDGEMENT
We thank Yi Su, Rishabh Agarwal, Yinlam Chow, Aleksandra Faust, Vincent Zhuang, George Tucker, Hao Liu, Jiayi Pan, Ethan Dyer, Behnam Neyshabur, Xavier Garcia, Yamini Bansal, Lam- pros Lamprou, Yuxiao Qu, and Amrith Setlur for their feedback and discussions. We attribute and thank Rishabh Agarwal, Vincent Zhuang, Yi Su, and Avi Singh for ideas and discussions. We thank Slay Petrov for leadership support.
earlier version of the paper
REFERENCES
Christophe Andrieu, Nando De Freitas, Arnaud Doucet, and Michael Jordan. An introduction to meme for machine learning. 2003.
Rohan Anil, Andrew M. Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, Eric Chu, Jonathan H. Clark, Laurent El Shafey, Yanping Huang, Kathy Meier-Hellsterm, Gaurav Mishra, Erica Moreira, Mark Omernick, Kevin Robinson, Sebastian Ruder, Yi Tay, Kefan Xiao, Yuanzhong Xu, Yujing Zhang, Gustavo Hermandez Abrego, Junwhan Ahn, Jacob Austin, Paul Barham, Jan Botha, James Brad- bury, Siddhartha Brahma, Kevin Brooks, Michele Catasta, Yong Cheng, Colin Cherry. Christo- pher A. Choquette-Choo, Aakanksha Chowdhery, Clément Crepy, Shachi Dave, Mostafa De- hghani, Sunipa Dev, Jacob Devlin, Mark Díaz, Nan Du, Ethan Dyer, Vlad Feinberg, Fangxiaoyu Feng, Vlad Fienber, Markus Freitag, Xavier Garcia, Sebastian Gehrmann, Lucas Gonzalez, Guy Gur-Ari, Steven Hand, Hadi Hashemi, Le Hou, Joshua Howland, Andrea Hu, Jeffrey Hui, Jeremy Hurwitz, Michael Isard, Abe Ittycheriah, Matthew Jagielski, Wenhao Jia, Kathleen Kenealy, Maxim Krikun, Sneha Kudugunta, Chang Lan. Katherine Lee, Benjamin Lee, Eric Li, Music Li, Wei Li, YaGuang Li, Jian Li, Hyeontack Lim, Hanzhao Lin, Zhongtao Liu, Frederick Liu, Mar- cello Maggioni, Aroma Mahendru, Joshua Maynez, Vedant Misra, Maysam Moussalem, Zachary Nado, John Nham, Eric Ni, Andrew Nystrom, Alicia Parrish, Marie Pellat, Martin Polacek, Alex Polozov, Reiner Pope. Siyuan Qiao, Emily Reif, Bryan Richter. Parker Riley, Alex Castro Ros, Aurko Roy, Brennan Saeta, Rajkumar Samuel, Renee Shelby, Ambrose Slone, Daniel Smilkov, David R. So, Daniel Sohn, Simon Tokumine, Dasha Valter. Vijay Vasudevan, Kiran Vodrahalli, Xuezhi Wang, Pidong Wang, Zirui Wang. Tao Wang, John Wieting, Yuhuai Wu, Kelvin Xu, Yun- han Xu, Linting Xue, Pengcheng Yin, Jiahui Yu, Qiao Zhang. Steven Zheng, Ce Zheng, Weikang Zhou, Denny Zhou, Slav Petrov, and Yonghui Wu. Palm 2 technical report, 2023.
11

---

Published as a conference paper at ICLR 2025
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Ols- son, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li. Eli Tran- Johnson, Ethan Perez, Jamie Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosuite, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemi Mer- cado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer EI Showk. Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Con- erly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Hatfield- -oddds, Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan. Constitutional ai: Harmlessness from ai feedback, 2022.
Edward Beeching, Lewis Tunstall, and Sasha Rush. open models. URL https: http:s////gggingacceee co/ spaces HugggingFaceeeee /ceH4// -tttsattttttnnnttt---eeee------- timeetttttmem--mmteeeeeee compute.
Scaling test-time compute with
Guoxin Chen, Minpeng Liao, Chengxi Li, and Kai Fan. Alphamath almost zero: process supervision without process. 2024.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Rejichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems, 2021.
DeepSeek-AL. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning, 2025. URL httpttttt/aaateeteeeeeeeeeeeettt //tpxvaaivvv//////////..////aa orgoorgg//s..... 02///.5511...1
Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate, 2023.
Xidong Feng, Ziyu Wan, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training. 2024.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. Pal: Program-aided language models, 2023. URL abs/ 0tts/221..100 10435.
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, 2024. URL https:/ /ttp///axiiv//v
org/ httg//a/////oo 2los/233 2231 02226.
Michael Hassid, Tal Remez, Jonas Gehring, Roy Schwartz, and Yossi Adi. The larger the better? improved Ilm code-generation via budget reallocation, 2024. URL https: /rgg abs /200 00725.
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, 2021.
Jordan Hoffimann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hen- nigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. Training compute-optimal large language models, 2022.
Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song. and Denny Zhou. Large language models cannot self-correct reasoning yet, 2023.
Andy L. Jones. Scaling scaling laws with board games, 2021. URL https: http:///xxxvvv//./// abs/ 22 04.0044..00 03113.
Jikun Kang, Xin Zhe Li, Xi Chen, Amirreza Kazemi, Qianyi Sun, Boxing Chen, Dong Li, Xu He, Quan He, Feng Wen, Jianye Hao, and Jun Yao. Mindstar: Enhancing math reasoning in pre- trained lms at inference time, 2024. URL htw.t:tt//////
/240 6265.
12

---

Published as a conference paper at ICLR 2025
Levente Kocsis and Csaba Szepesv' ari. Bandit based monte-care planning. In European conference on machine learning. pp. 282-28222222 292.299. Springer, 2006.
Aviral Kumar, Vincent Zhuang. Rishabh Agarwal, Yi Su, John D Co-Reyes, Avi Singh, Kate Baumli, Shariq lqbal, Colton Bishop, Rebecca Roelofs, Lei M Zhang, Kay McKinney, Disha Shrivastava, Cosmin Paduraru, George Tucker, Doina Precup, Feryal Behbahani, and Aleksan- dra Faust. Training language models to self-correct via reinforcement learning, 2024. URL
Aitor Lewkowyez, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ra- masesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Soo Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with lan- guage models, 2022.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making large language models better reasoners with step-aware verifier, 2023.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step, 2023.
Runze Liu, Junqi Gao, Jian Zhao, Kaiyan Zhang, Xiu Li, Biqing Qi, Wanli Ouyang, and Bowen Zhou. Can lb Ilm surpass 405b 11m? rethinking compute-optimal test-time scaling, 2025. URL aba/a//s////00 06703.
httpps:/aaee //rxivv
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feed 2023.
Theo X. Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar- Lezama. Is self-repair a silver bullet for code generation?, 2024. URL https://arxt:
org/abs/2306 09896.
OpenAl. Gpt-4 technical report, 2024a.
OpenAI. Openai system card, 2024b. URL
Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, Sihan Zhao, Lauren Hong, Runchu Tian, Ruobing Xie, Jie Zhou, Mark Gerstein, Dahai Li, Zhiyuan Liu, and Maosong Sun. Toolllm: Facilitating large language models to master 16000+ real-world apis, 2023. URL https: aaaxiiiivvv..... org/ abs/ 307 16789.
Changle Qu, Sunhao Dai, Xiaochi Wei, Hengyi Cai, Shuaiqiang Wang. Dawei Yin, Jun Xu, and Ji-Rong Wen. Tool learning with large language models: A survey, 2024a. URL https://
wwx.v.org//aooooa..oo......o..vt abs 2.405.1933
Yuxiao Qu, Tianjun Zhang, Naman Garg, and Aviral Kumar. Recursive introspection: Teaching language model agents how self-improve. arXiv preprint 1rXiv:2407.18211 2024b.
Jon Saad-Falcon, Adrian Gamarra Lafuente, Shlok Natarajan, Nahum Maru, Hristo Todorov, Frash Guha, E. Kelly Buchanan, Mayee Chen, Neel Guha, Christopher Ré, and Azalia Mirhoseini. Archon: An architecture search framework for inference-time techniques, 2024. URL https:
//arxiv. wwweiiiorrgaaae htse//bs/2244 /200 15254.
Nikhil Sardana and Jonathan Frankle. Beyond chinchilla-optimal: Accounting for inference in language model scaling laws, 2023.
William Saunders, Catherine Yeh, Jeff Wu, Steven Bills, Long Ouyang, Jonathan Ward, and Jan Leike. Self-critiquing models for assisting human evaluators, 2022.
Amrith Setlur, Saurabh Garg, Xinyang Geng, Naman Garg, Virginia Smith, and Aviral Kumar. RI on incorrect synthetic data scales the efficiency of Ilm math reasoning by eight-fold. arXiv preprint arXiv:2406. /4532, 2024.
13

---

Published as a conference paper at ICLR 2025
Zhihong Shao, Peiyi Wang, Qihao Zhu, Rumxin Xu, Junxiao Song. Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathe- matical reasoning in open language models, 2024.
Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023.
Avi Singh, John D. Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Xavier Garcia, Pe- ter J. Liu, James Harrison, Jaehoon Lee, Kelvin Xu, Aaron Parisi, Abhishek Kumar, Alex Alemi, Alex Rizkowsky. Azade Nova, Ben Adlam, Bernd Bohnet, Gamaleldin Elsayed, Hanie Sedghi, Igor Mordatch, Isabelle Simpson, Izzeddin Gur, Jasper Snoek, Jeffrey Pennington, Jiri Hron, Kathleen Kenealy, Kevin Swersky, Kshiteej Mahajan, Laura Culp, Lechao Xiao, Maxwell L. Bileschi, Noah Constant, Roman Novak, Rosanne Liu, Tris Warkentin, Yundi Qian, Yamini Bansal, Ethan Dyer, Behnam Neyshabur, Jascha Sohl-Dickstein, and Noah Fiedel. Beyond human data: Scaling self-training for problem-solving with language models, 2024.
Kaya Stechly, Matthew Marquez, and Subbarao Kambhampati. Gpt-4 doesn't 't know it's wrong: An analysis of iterative prompting for reasoning problems, 2023.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. Second edition, 2018.
Gemini Team. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of con- text, 2024.
Ye Tian, Baolin Peng, Linfeng Song, Lifeng Jin, Dian Yu, Haitao Mi, and Dong Yu. Toward self- improvement of lims via imagination, searching. and criticizing, 2024.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajiwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull. David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov. Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Ilama 2: Open foundation and fine-tuned chat models, 2023. URL https:ttp//ooo...... /ar/ivivvvv..////v///aa////aaivv www.iiiorrrr/aee www./orga/.............
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, 2022.
Karthik Valmeekam, Matthew Marquez, and Subbarao Kambhampati. Can large language models really improve by self-critiquing their own plans?, 2023.
Pablo Villalobos and David Atkinson.
Trading off compute in train-
ing and inference, 2023.
URL https:/ https://epochat http://pcccccccccceeeee wwt..orggoooooooo /oggblog///// crading-oof-ccomute Ltwpro---ooottt-------aaannnn-nr waw.iiiig-an--infeeeeeee Accessed: 2024-07-03.
Junlin Wang, Siddhartha Jain, Dejiao Zhang, Baishakhi Ray, Varun Kumar, and Ben Athiwaratkun. Reasoning in token economies: Budget-aware evaluation of Ilm reasoning strategies, 2024a. URL
https:://arxe www./rrgg/so...ooooooo als .0 04461.
Peiyi Wang, Lei Li, Zhihong Shao, R. X. Xu, Damai Dai, Yifei Li, Deli Chen, Y. Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce Iims step-by-step without human annotations, 2023.
Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah D. Goodman. Hypothesis search: Inductive reasoning with language models, 2024b. URL https: //te:///ax...... org//bbs/233 /2309. 05660.
14

---

Published as a conference paper at ICLR 2025
Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct, 2022. URL hattps://axxiv.oxx abs/2211. 00053.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. An empirical analysis of compute-optimal inference for problem-solving with language models, 2024. URL https: //aaxivvorg/abal atapg//abs// /tw.a/////2... 00724.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models, 2023,
Zheng Yuan, Hongyi Yuan, Chengpeng Li, Guanting Dong, Keming Lu, Chuanqi Tan, Chang Zhou, and Jingren Zhou. Scaling relationship on learning mathematical reasoning with large language models, 2023.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning, 2022.
Eric Zelikman, Georges Harik, Yijia Shao, Varuna Jayasiri, Nick Haber, and Noah D. Goodman. Quiet-star: Language models can teach themselves think before speaking, 2024. URL https: //aaaxxi.rggaass///////.oo 09629.
15

---

Published as a conference paper at ICLR 2025
Appendices
A DISCUSSION AND FUTURE WORK
In this work, we conducted a thorough analysis of the efficacy of different techniques that aim to either improve search against a verifier or to refine an LLM's proposal distribution, for scaling test- time compute for math reasoning. In general, we found that the efficacy of a given approach heavily correlates with the difficulty of the problem from the perspective of the base LLM's capabilities. This motivated to introduce the notion of "compute-optima"" scaling of test-time computation, which prescribes an adaptive, prompt-dependent strategy to improve performance under a given test-time compute budget. By applying such a compute-optinal scaling strategy, we find that we can improve the efficiency of test-time compute scaling by factor of 2 - 4x. When comparing benefits obtained from additional test-time compute against benefits from additional pre-training compute in a FLOPs-matched setting, we show for the first time that using test-time computation with seemingly simple methods (i.e., revisions and search) can already scale well on certain types of prompts, providing gains over spending those FLOPs in pretraining.
Limitations. That said, there are also limitations associated with our study that future work can aim to address. Firstly, while we obtained strong results with beam-search, our lookahead search gener- ally underperformed. It is possible that our lookahead search algorithm could further optimized by training PRM verifier with online MCTS training. Future work should explore the degree much PRM search can be improved in this way. Secondly, computing our notion of difficulty requires applying non- non-trivial amount of test-time compute. Future work should consider alternative ways of efficiently estimating prompt difficulty. Finally. it is unclear to what extent our findings gener- alize beyond math and easily verifiable domains more broadly. Furthermore, many limitations of test-time compute are largely unknown; it is possible that in some domains test-time compute may be limited in ways that pretraining is not. While answering this question is out of scope for the present work, we believe it is an important topic for future research.
Future-work. We believe there are many future research directions that can build on our findings. We describe a few of these directions here. While we focused on improving the test-time compute scaling of two primary mechanisms independently (the verifier and the proposal distribution), future work should investigate how test-time compute scaling can be further improved by combining these approaches or via fundamentally different mechanisms than those explored in this paper. Moreover, our work focused purely on test-time compute scaling. In the future, we envision that the outputs of applying additional test-time compute can be distilled back into the base LLM,, enabling an it- erative self-improvement loop that operates on open-ended natural language, which we believe is an exciting direction for future work to explore. Moreover, future work should conduct additional scaling-law analysis with respect test-time compute: 1) how does the scaling of test-time compute improve as pretraining is scaled; and 2) if we were to finetune models on much larger datasets (e.g. of millions of question answer pairs) how would test-time compute scaling improve? In this setting, how would the cost of fine-tuning affect the balance betweeen scaling up model size vs test-time inference? These are questions that future work can study building on framework built in our work.
B RELATED WORK
Language model reasoning. Language model performance on challenging mathematical reasoning tasks has rapidly improved in recent years (Lewkowycz et al., 2022; Team, 2024; OpenAl, 2024a; Shao et al., 2024; Lightman et al., 2023). These improvements can be attributed three primary factors: 1) running continued pretraining on large corpora of math focused data (Lewkowycz et al., 2022: Team, 2024; Shao al., 2024: Lightman al., 2023): 2) improving the LLM proposal dis- tribution by either applying targeted optimization on specific reasoning tasks by finetuning with RL (Singh et al., 2024: Zelikman et al., 2022; Shao et al., 2024; Yuan et al., 2023) enabling models to critique and revise their answers iteratively (Bai et al., 2022; Madaan et al., 2023; Du et al., 2023; Saunders et al., 2022); 3) enabling LLMs to benefit from additional test-time computation by fine- tuning verifiers (Lightman et al., 2023; Cobbe et al., 2021: Uesato et al., 2022; Wang et al., 2023; Yao et al., 2023; Feng et al., 2024; Chen et al., 2024: Tian et al., 2024; Kang et al., 2024). Our work builds these second and third lines of research by analyzing the extent to which test-time compute scaling can be improved by 1) refining an LLM's proposal distribution and 2) conducting search against verifiers.
16

---

Published as a conference paper at ICLR 2025
Analyzing test-time compute scaling. The tradeoff between train-time and test-time compute using Monte-Carlo tree search applied to the board game Hex was previously studied by Jones (2021). We instead focus our analysis full-scale language model math reasoning problems. A survey work by Villalobos & Atkinson (2023) analyzed the tradeoff between training and inference across a number of domains. Similarly, work by Hassid al. (2024) explores the trade-off between scaling test-time compute with smaller models and using larger models without additional test-time compute on code completion tasks. However, in each of these prior works, much of the analysis is focused on test-time scaling in settings where the ground tround-truth answer is known. In contrast, our analysis focuses on the setting when the ground-truth, answer not known. Additionally, a number of works in the RL literature have proposed methods, such as MCTS (Koesis & Szepesv' ari, 2006), which aim to navigate the tradeoff between test-time and training-time compute so as to enable a form of iterative eef-play. The findings in our work can be used to help develop similar algorithms that can operate on open-ended natural language.
Augmenting LLMs with test-time compute. Beyond verifiers and revisions, number of ad- ditional works have proposed alternative methods for enabling LMs to use test-time compute for reasoning. Namely, Wang et al. (2024b) conducts a hierarchical hypothesis search to enable induc- tive reasoning capabilities. A number of related works have proposed augmenting language models with tools at test-time, which can greatly improve their performance downstream tasks (Gao et al., 2023; Qin et al., 2023; Qu et al., 2024a). Several works have proposed methods for learn- ing thought tokens in an unsupervised manner (Zelikman al., 2024; Goyal et al., 2024), enabling models to more effectively utilize the additional test-time compute that comes with sampling longer sequences. Finally, Saad-Falcon et al. (2024) explore applying cerittctturesseacce based techniques to effectively compose several different test-time scaling techniques. While we focus our analysis on two primary mechanisms by which test-time compute can be scaled in this work (e.g. verifiers and revisions), many of the methods by which we conduct our analysis (e.g. compute optimal scaling according to question difficulty) could, in principle, also be applied to any of these other methods of scaling test- ti-t compute, and we believe that this is interesting direction for future research.
C SEARCH ALGORITHM DETAILS
Below we include additional details for each of our search algorithms in Section 5.
Best-of-N weighted. We sample N answers independently from the base LLM and then select the best answer according to the PRM's final answer judgment.
Beam search. Beam search optimizes the PRM by searching over its per-step predictions. Our implementation is similar to BFS-V (Yao et al., 2023; Feng et al., 2024). Concretely, we consider a fixed number of beams N and a beam width M. We then run the following steps:
1. sample N initial predictions for the first step in the solution
2. score the generated steps according to the PRM's predicted step-wise reward-to-ge go estimate (which also corresponds to the total reward from the prefix since the reward is sparse in this setting)
3. filter for only the top N highest scoring steps
4. now from each candidate, sample M proposals from the next step, resulting in total of N/M x M candidate prefixes again. Then repeat steps 2-4 again.
We run this algorithm until the end of solution or the maximum number of rounds of beam expan- sion are attained (40 in our case). We conclude the search with N final answer candidates, to which we apply best-of-N weighted selection described above to make our final answer prediction.
Lookahead search. Lookahead search modifies how beam search evaluates individual steps. It uses lookahead rollouts to improve the accuracy of the PRM's value estimation in each step of the search process. Specifically, at each step in the beam search, rather than using the PRM score at the current step to select the top candidates, lookahead search performs a simulation, rolling out up to k steps further while stopping early if the end of solution is reached. To minimize variance in the simulation rollout, we perform rollouts using temperature O. The PRM's prediction at the end of this view
rollout is then used to score the current step in the beam search. That is, in other words, beam search as a special case of lookahead search with = O. Given an accurate PRM, increasing k should improve the accuracy of the per-step value estimates at the cost of additional compute.
17

---

Published as a conference paper at ICLR 2025
Revision Model Passgg1 Each
Revision Model Paralist Sequential
-9
Seqarttll Pel leuphted
13
Seqaortin Mapnty
Penatet Magelly
35
MATH Teal Apourety
30
21
Number of Generations
Number Generatione
Our revision model's pass@1 @ at each revision step. Pass@1 gradually improves after each revision step, even improving beyond the revision steps that was trained for. We estimate pass@1 at each step by averaging over the performance of 4 revision trajectories of length 64 for each question in the test-set. Right: Sequential vs parallel sampling from the revision model. Comparing performance when generating N initial answers in parallel from revision model, versus generating N revisions sequentially, with the model. To account for the cost of querying the verifier relative majority voting, shift the curves which involve verifier over by one point. When using both the verifier and majority voting to select the answer, we see that generating answers sequentially with the revision model narrowly outperforms generating them in parallel.
Figure 9: Left:
Also note that this version of lookahead search is special case of MCTS (Sutton & Barto, 2018) 2018), wherein the stochastic elements of MCTS, designed to facilitate exploration, are removed since the PRM is already trained and is frozen. These stochastic elements are largely useful for learning the value function (which we' ve already learned with our PRM), but less useful at test-time when we want to exploit rather than explore. Therefore, lookahead search is largely representative of how MCTS-style methods would be applied at test-time.
D ADDITIONAL REVISION RESULTS
In Figure left, we plot the pass@ for our revision model at each revision step. We see that pass@ gradually improves after each step. In Figure right, we compare performance when generating N initial answers in parallel from our revision model, versus generating revisions sequentially, with the model. When using both the verifier and majority voting to select the answer, we see that generating answers sequentially with the revision model narrowly outperforms generating them in parallel.
We plot additional results for majority voting selection using our PaLM 2-S* revision model in Figure 10. With majority selection, we see largely similar trends to those found in Figure for verifier selection.
E DIFFICULTY BINS
Oracle difficulty bins. We compute our oracle difficulty bins by obtaining the ground-truth pass@) correctness rate for each question, and then using this statistic to bin questions into quan- tiles representing 5 distinct difficulty bins. There are in total 500 questions in the test-set. Difficulty levels 1, 2, and 3 all have 100 questions in them. Difficulty levels 4 and 5 have 105 and 95 questions respectively. This imbalance in the last two bins is merely due boundary condition/ties in the quantile computation, causing one bin to inherit slightly more questions than the other.
Predicted difficulty bins. We compute difficulty bins without oracle ground-truth correctness in- formation by averaging the PRM final-answer score over 2048 samples on each question, so as to obtain value estimate corresponding the question. Similar the oracle case, we then bin the value for each question in the test-set into five quintiles (using the same procedure as the oracle difficulty bins). We refer this "predicted difficulty". Each of the bins has 100 questions in this
18

---

Published as a conference paper at ICLR 2025
Varying Sequandal/araalel Majority
Revisiors Majorty@1 18,, Varying Sequential Paraliel Ratio
10"
Numbur of Careratona
MATH Toat Accuraty (ha
eoogeenia Paraa Rabo
MATH Trat Accusayy
Tgx
Test Questions Binned by incmasinn Dificutty Level
Figure 10: Varying the ratio of generation budget allocated to sequential versus parallel samples, using majority voting to select the answer, rather than the verifier. Left: Each line represents fixed generation budget as the ratio is changed. We see that similar to the verifier case, in the majority case, there exists an ideal ratio of sequential to parallel test-time compute at given budget. Right: Analyzing performance across difficulty bins, we see that the easier questions are mostly invariant to the ratio of sequential to parallel, whereas on the harder questions there is an ideal ratio of sequential to parallel test-time compute.
Best-al-108 Sequortial Paralel
14T BEACERS
traqpeniied
Figure 11: Using our PaLM 2 PRM to compute difficulty bins without ground truth correctness information for revisions. On the left we plot verifier selection and on the right we plot majority selection. We see largely similar performance trends with these bins as we do with the ground truth trends in Figures and 10.
case. Technically this procedure is extremely costly because it requires generating many samples. While we do not account for this cost in our analysis, in a practical production setting, this cost would be problematic. A more efficient approach would be to finetune model to predict correct- ness directly, given the question. We do not explore this in our work, but leave such exploration of cheaper methods of estimating difficulty future work.
In Figure 12 we plot PRM-search results using our predicted (non-oracle) difficulty bins, and in Figure 11 we plot the corresponding revision results. We see that in both settings these predicted bins demonstrate similar trends to the oracle bins.
F PRM TRAINING DETAILS
Originally PRM training (Uesato et al., 2022; Lightman et al., 2023) used human crowd-worker labels. While Lightman et al. (2023) released their PRM training data (i.e., the PRMS00K dataset), we found this data to be largely ineffective for us. We found that it was easy exploit PRM trained on this dataset via even naïve strategies such as best-of-N sampling. We hypothesize that this is likely result of the distribution shift between the GPT-4 generated samples in their dataset and our PaLM 2 models. Rather than proceeding with the expensive process of collecting crowd-worker PRM labels for our PaI.M 2 models, we instead apply the approach of Wang al. (2023) to supervise
19

---

Published as a conference paper at ICLR 2025
Compening Beam Swarch and Bext-ofNN with Unsupervsed D fliusyy Bine
MATH Tos (50
Tex: Queed ond Birned with Unsupervsed DiPlorty Bine
Figure 12: Using our PaLM 2-S" PRM compute difficulty bins without ground truth correctness information for PRM search. We see largely similar performance trends with these bins as we do with the ground truth ones in Figure 3.
PRMs without human labels, using estimates of per-step correctness obtained from running Monte Carlo rollouts from each step in the solution. Our PRM's per-step predictions therefore correspond to value estimates of reward-to-go for the base model's sampling policy, similar to recent work (Wang et al., 2023; Setlur et al., 2024). We also compare to an ORM baseline (Appendix H) but found that our PRM consistently outperforms the ORM. Hence, all of the search experiments in this section use a PRM model.
We finetune our PRM binary classifier, where the model predicts value between 0 and I at each step in the solution. We train the model with soft values obtained from the monte-carlo rollouts, using binary cross entropy loss function (e.g. - (ylog(() + y)log(1 9)) where y corresponds to the soft ground-truth value and ý the model's predicted value). We finetune the model base model using the AdamW optimizer, with Ir 3e-5, batch size 128, dropout 0.05, and Adam betas (0.9,0.95). We conduct early stopping, selecting the checkpoint with the lowest validation loss on a random held-out validation set, consisting of 10% of the questions in the original PRM800K training split.
We finetune the PRM on 16 samples per question from the corresponding few-shot prompted base model. At each step, we use 16 monte-carlo rollouts, using the same base model and prompt, to estimate the step-level value. We filter out all samples which fail to output a valid, parsable final answer from the training data, as we found these to hurt PRM performance in initial experiments.
When generating the samples, the base model is prompted to output answers in newline separated step-by-step format, as done Lightman al. (2023). We then separate each of the answers into steps using a simple newline splitting procedure. We include details about our prompt in Appendix J.
G PRM AGGREGATION
At test time, pracess-based verifiers can be used to score each individual step in set of solutions sampled from the base model. In order to select the best-of-N answers with the PRM, we need function that can aggregate across all the per-step scores for each answer to determine the best candidate for the correct answer. To do this, we first aggregate each individual answer's per-step scores obtain final score for the full answer (step-wise aggregation). We then aggregate across answers to determine the best answer (inter-answer aggregation). Concretely, we handle hepe and inter-answer aggregation as follows:
Step-wise aggregation. Rather than aggregating the per-step scores by taking the product or minimum (Wang al., 2023; Lightman et al., 2023), we instead use the PRM's predic- tion at the last step as the full-answer score. We found this to perform the best out of all aggregation methods we studied (see below).
Inter-answer aggregation. We follow Li et al. (2023) and apply "best-of-N weighted" selection rather than standard best-of-N. Best-of-N weighted selection marginalizes the
20

---

Published as a conference paper at ICLR 2025
Best-of-N Verses Best-of-N Weighted
PRM
Majorty
35
of Weighted
MATH Test Ascuracy (%)
30
10
2
2
Generation Budget
Figure 13: We compare best-of-N and best-of-N weighted for ORM and PRM verifiers finetuned from PaLM 2-S*. We use the PaLM 2-S* base LM to sample outputs, using few-shot prompt. To account for the cost of querying the verifier relative majority voting, we shift the curves which involve verifier over by one point. We see that while best-of-N weighted shows superior perfor- mance in both settings, the best-of-N performance with the PRM still very competitive. other hand, in the ORM best-of-N setting, we observe Goodharting at higher budgets.
verifier's correctness scores across all solutions with the same final answer, selecting final answer with the greatest total sum.
G.1 COMPARING STEP-WISE AGGREGATION STRATEGIES
We compare different methods of aggregating per-step PRM scores to produce final score for the full solution. Specifically we compare: 1) taking the minimum score across all steps as done Lightman et al. (2023) (e.g. "min"); 2) taking the product of all step correctness probabilities (e.g. "prod");; and 3) taking just the last step prediction (e.g. "last"). We see in Figure 14 that taking the last step outperforms et al., 2023) found min to be the best aggregator. We believe that the discrepancy is due the fact that our verifier was trained with soft MC return labels, which surface very differently from binary correctness labels, and therefore other aggregation strategies may not have the same effect.
other two approaches. Prior works (Lightman al., 2023; Wang
Interestingly, when using the last step aggregation, we are effectively using the PRM like an ORM. However, see that the PRM outperforms the ORM, suggesting that in training may be largely useful as a form of representation learning, rather than purely as a tool at inference time. Future work should further explore this line of reasoning.
the per-step PRM
G.2 COMPARING INTER-ANSWER AGGREGATION STRATEGIES
In Figure we compare best-of-N against best-of-N weighted for both our ORM and PRM verifiers. We find that while best-of-N weighted shows superior performance in both settings, the best-of-N performance with the PRM is still very competitive. On the other hand, in the ORM best-of-N setting, observe Goodharting at higher budgets.
H COMPARING PRM AND ORM
We trained a PRM and ORM model using the PaLM 2-S* base LM. We see in Figure 15, that the PRM outperforms the ORM, and the gap between the PRM and ORM grows with the number of samples used. We use the last step prediction from the PRM to score the answers as described in Appendix G.
21

---

Published as a conference paper at ICLR 2025
Comparing PRM Aggregation Strategies
40
PRM
PRM prod
PRM leat
Majorit
MATH Tost Accuracy (%)
ORM
20
15
10
2
Generation Budget
We compare different methods of aggregating per-step PRM scores to produce a final score for the full solution: "min" refers to taking the minimum score accross all steps, "prod" takes the product of all step correctness probabilities, and "last" just uses the last step score. To account for the cost of querying the verifier relative to majority voting, we shift the curves which involve verifier over by one point. We see that "PRM last" performs the best across all aggregation strategies.
Figure 14;
ORM Verses PRM
40
PRM best-ot-N weighted
Base LM Majonit
ORM best-of-N weighted
MATH Tost Accuracy (%)
20
15
10
z'
2²
2
Generation Budgel
We compare PRM and ORM models finetuned from PaLM 2-S* in best-of-N evalu- ation. We use the PaLM = base LM sample outputs, using a few-shot prompt. To account for the cost of querying the verifier relative to majority voting, we shift the curves which involve verifier over by one point. We see that the PRM greatly outperforms the ORM large number of samples.
Figure 15:
22

---

Published as a conference paper at ICLR 2025
Compangg
euci of Mejrit
le- o/ Insprtyy
Querttr Cimrdtty nertesiing Difisiyy Level
Teal Questora Direet triitr Dfficdly Lovel
Figure 16: Comparing beam search and best-of-N binned by difficulty level with PaLM (left) and PaLM 2-M (right). The four bars in each difficulty bin correspond to increasing test-time compute budgets (4, 16, 64, and 256 generations). We observe brodly similar trends to those in Figure on PaLM 2-S* demonstrating that our findings likely transfer to other base LLMs.
I SEARCH USING PALM 2-S AND M
In Figure 16, we plot the performance of beam-search and best-of-N binned by difficulty levels using PaLM 2-S and PaLM 2-M as the base models. We observe broadly similar trends to those in Figure on PaLM 2-S*, demonstrating that findings likely transfer to other base LLMs.
J PROMPTING DETAILS
In order to enable the base model output answers in step-by-step format to which PRM can be applicd. we use a 4-shot prompt consisting of randomly selected correct answer examples from the PRM800K data released by Lightman al. (2023). Specifically use answers from the phase training split. These answers correspond to GPT-4 generated correct answer examples, which in- clude the correct step-by-step format. In initial experiments, produces similar results to the prompt used in Lewkowycz et al. (2022). We use this prompt for gen- erating training data for the PRM and the revision model. We also use this prompt when conducting search against the PRM on the test-set. To grade the final answer predicted by this prompt, we use the grading function released by Lightman al. (2023).
found that this prompting procedure
K THE EFFECT OF VERIFIER QUALITY ON OUR CONCLUSIONS
We would like understand whether our conclusions in Section 7, regarding whether scaling test- time compute is favorable to scaling model parameters, are robust to the quality of the specific finetuned PRM verifier that we used our experiments. In particular, we want determine whether we would observe similar trends using less capable verifiers. To do this, we conduct similar analysis to that Section 7, using four different settings that are specifically designed to emulate the effect of having a lower quality verifier:
A) A "uniform random" verifier. Since weighted BoN with a random verifier converges to ma- jority voting, we simulate a random verifier by using majority voting.
B) Our PRM verifier but with 20% i.i.d. label flip noise. In particular, if the verifier predicts correctness probability of p. we flip its prediction to (1 - p) 20% the time.
C) Our standard PRM verifier. This identical to the standard PRM used Section 7.
D) Majority voting using parallel samples from the revisions model with no PRM. This setting is equivalent to using "uniform random" verifier on top of of our finetuned revisions model.
Observe in Figure 17 that while majority voting (A) generally under-performs the larger pretrained model, the noised verifier (B) can outperform pretraining on easy/medium questions in settings with low inference requirements. We also note that majority voting with a revisions model (D) outperform scaling model parameters easy and medium questions, without using verifier
23

---

Published as a conference paper at ICLR 2025
Compaiing and mostaring Cansuda with Lesk Copadbe Warffers Ellbay
Hiprree Viliog
leing
Figure 17: We extend the analysis in Section 7 by comparing the test-time scaling of weaker veri- fiers against the performance of 14x larger pretrained model. We that while majority voting (A) generally under-performs the larger pretrained model, the noised verifier (B) can outperform pertaining on easy/medium questions in settings with low inference requirements. Additionally, majority voting with a revisions model (D) can outperform scaling model parameters on easy and medium questions, without using a verifier.
suggesting that it is still possible to get decent test-time scaling that outperforms pretraining with less capable verifier (or no verifier, if the base model is finetuned in a certain way).
These findings demonstrate that even with somewhat weaker verifier model, the main conclusions from our FLOPs analysis in Section 7 can still hold. Moreover, we see that higher quality veri- fiers tend to show better test-time scaling, suggesting that it may be possible for us to substantially improve the test-time scaling of verifiers by finetuning the verifier on a much larger dataset of math- ematical question answers pairs than the 12k that used in this work. We believe this is an exciting direction for future work to explore.
L REVISION MODEL FINETUNING DETAILS
Our procedure for finetuning revision models is similar (Qu et al., 2024b), though introduce some crucial differences. For finetuning, we need trajectories consisting of a sequence of incorrect answers followed by a correct answer, that answer to be correlated with the incorrect answers provided in context, so as to effectively teach the model to implicitly identify mistakes in examples provided in-context, followed by correcting those mistakes by making edits as opposed to ignoring the in-context examples altogether, and trying again from scratch.
then run SFT on. Ideally,
want the correct
Generating revision data. The on-policy approach of Qu et al. (2024b) for obtaining several multi- turn rollouts was shown to be effective, but it was not entirely feasible our infrastructure due to compute costs associated with running multi-turn rollouts. Therefore, we sampled 64 responses in parallel a higher temperature and post-hoc constructed multi-turn rollouts from these independent samples. Specifically, following the recipe of (Kumar et al., 2024), we pair up each correct answer with a sequence of incorrect answers from this set as context to construct multi-turn finetuning data. We include up four incorrect answers in context, where the specific number of solutions in context is sampled randomly from a uniform distribution over categories to 4. The correct answer used as the last answer in the trajectory (which we train the model to produce) and the incorrect answers are included in context. If the sampled number is greater than O, we then find the closest incorrect character-level edit distance metric include as the last incorrect answer in
answer according the trajectory. The goal here is to select an incorrect answer which is somewhat correlated with the correct answer, improve learning. Note that token edit distance is not a perfect measure of correlation, but we found this heuristic to be sufficient to correlate incorrect in-context answers with correct target answers facilitate training a meaningful revision model, as opposed to randomly pairing incorrect and correct responses with uncorrelated responses. Finally, in the case where there are fewer than 4 incorrect answers sampled, we truncate the uniform distribution's 's max to match the number of incorrect samples. We use this procedure to generate trajectories for all questions in the training data.
We then finetune the base language model on the correct answer solutions in these generated tra- jectories. We use the AdamW optimizer with Ir 1e-5, batch size 128, dropout 0.0, and Adam betas (0.9, 0.95).
24

---

Published as a conference paper at ICLR 2025
We find that generally evaluating loss on evaluation set consisting of trajectories generated as described above, does not provide good signal for early stopping. Rather, we find that checkpoints much after the evaluation loss begins increasing because after finetuning the revision model, the evaluation set represents off-policy data, which will naturally be out-of-distribution compared to the trajectories that the model itself would generate policy. We therefore select our revision model checkpoint slightly after the point where we observe overfitting on the validation set.
much more capable of revisions. This is likely
M REVISION MODEL SELECTION CRITERIA
As described in Section 6.1, in order to effectively use our revision model we need to deploy criteria for selecting the best answer both within a revision trajectory and between multiple parallel trajectories. We use two approaches: 1) ORM verifier; and 2) majority voting.
For the ORM verifier, we train an ORM on the revision model's 's outputs according to the procedure in Appendix N. At inference time then this verifier select the best answer. Since have two axes across which to aggregate (within each revision trajectories and between multiple trajectories), we deploy hierarchical strategy, first selecting the best answer within each revision trajectory and then aggregating these selected answers across trajectories. To select the best answer within each trajectory, we perform best-of-N weighted aggregation and then choose the highest scoring solution with the maximum best-of-N weighted answer. Then, to select the final answer across all revision chains, we perform another round of best-of-N weighted selection using the best answer from each revision chain. The answer after this second round of best-of-N weighted represents our final answer prediction.
For majority voting we found hierarchical aggregation to create problems when the length of the trajectory or the number trajectories was too small. The problem being that without enough samples, majority voting is unable to effectively select the best option. Therefore, for majority voting, we simply take all answers, across all trajectories, at once and take their majority as the final- answer. We found this to produce much smoother scaling behavior than the hierarchical approach.
N REVISION MODEL VERIFIER TRAINING
We found that the PRM we finetuned on the PaLM 2-S* base model outputs was not as effective when applied the P 2-S* revision model's outputs (see Figure 18(a)), likely due to distribution shift with the revision model. We therefore, trained a separate ORM verifier to use with our Pal IM 2-$* revision model. We could have trained a PRM as well, but opted for an ORM due to the high cost of generating per-step PRM labels.
We modified the standard ORM slightly for the revision setting, by finetuning the ORM with previ- ous revision in context, such that the verifier has access to the same context as the revision model, allowing the verifier see the revision model's 's previous answer attempts when scoring the current answer. All other experiment details are identical to those used for training the PRM.
Empirically, we find that including the revision history in context improves performance slightly (see Figure 18(b).. Additionally, even without the revisions in context, still slightly outperforms parallel, demonstrating improvements from sequential sampling are not just due the verifier's context.
that sequential revisions
COMPUTE OPTIMAL. REVISIONS HYPERPARAMETERS
In Table 1 we list the sequential/parallel ratios that we select between at each generation budget when estimating compute optimal scaling in Figure
P RESTEM REVISION MODEL EXPERIMENTS
We experimented with further optimizing our PaLM 2-S* revision model by training the model with simplified RL algorithm: RESTEM (Singh al., 2024). Specifically, we generated 64 revision
25

---

Published as a conference paper at ICLR 2025
Revision Model Verifier Verses Base-LM PRM
Revision Model Verffir With Varse Without History
bar toon UM PMM
Sequrrtia Varter Witbout Peotel
Paadtee
05
MAT Aeturroy
30
30
MATH
25
15
Number of Genorations
Number of Generations
Figure 18: Left: we compare the ORM we trained on the revision model's outputs against the PRM we trained on the PaLM 2-S* base model's s outputs. We see that when applied to outputs from the revision model, the ORM adapted to the revision model outperforms the PRM, likely due to distribution shift with the revision model. Right: we ablate the effect of including previous revisions in the revision model verifier's context. We see that including revisions in-context helps the verifier slightly, but both settings still outperform the parallel baseline.
N
Sequential Aoquential.Paralle Parallel Ratios
1:1
1:2, 2:1
1:4. 1:1, 4:1
1:8, 1:2, 2:1, 8:1
16
1:16, 1:4, 1:1, 4:1, 16:1
32
1:32, 1:8, 1:2, 2:1, 8:1, 32:1
64
1:64, 1:16, 1:4, 1:1, 4:1, 16:1, 64:1
128
1:128, 1:32, 1:8, 1:2, 2:1, 8:1, 32:1, 128:1
256
1:256, 1:16, 1:1, 16:1, 256:1
Table 1: We list the set of sequential to parallel ratios that we consider at each generation budget N. These are the ratios we select between when defining compute optimal scaling Figure 6.
26

---

Published as a conference paper at ICLR 2025
Varying Soquential/Paratel
40
10"
MATH Test Accuraccy (%)
36
Number of Generations
32
-00
10
28
25
10"
Sequentia//aarale Ratio
Figure 19: Performance of our RMST optimized revision model as the sequential to parallel ratio varied. We use majority voting to select the answer. We that this optimized revision model demonstrates substantial performance degradations with additional sequential revisions.
trajectories of maximum length 5 for each question the MATH training set. We stopped the revision model at the first correct answer each trajectory. Using this generated data, we then finetuned the base LM the correct answer data. To help the model learn the task, explicitly balanced the distribution of trajectory lengths.
In Figure 19, plot the performance of this revision model as vary the sequential to parallel ratio. We see that additional sequential revisions substantially hurts performance with this new model. We hypothesize that this degradation is due the fact that the online data obtained from running RM exacerbates spurious correlations in revision data, causing the optimized model to fail to learn the revision task. We believe that using a more offline data collection strategy, as done in Qu al. (2024b), may be more effective, and leave further exploration future work.
REVISION MODEL EXAMPLE OUTPUTS
In Figures 20, 21, 22, 23, 24, 25, and 26, include select examples of revision model's outputs.
R PRM BEAM SEARCH EXAMPLE OUTPUTS
In Figures 27, 28, 29, 30, 31, and 32, include select examples of PRM beam search, We include the PRM score, between and 1, for each step in the examples.
27

---

Published as a conference paper at ICLR 2025
Sfx) (3rac(3-2)(x-2j5,
of Sf(-2) +f[=1){[0]S? Express your answer
common fraction.
Attempt 1:
Let's evaluate $f(-2)8,
We have wtr.://feeeaaa---222222rgrg-0-aa
So (f(-2)=13.
Let's evaluate $F(-1)8.
we have http://1000002000222222200011110 So (T(=3)=Xfrao(55)33
Lat's evaluate $f(8)S.
We have 37005TTheE00--0222277r1122222222
So sf(0)=18.
So want compute
51-xfrac(5) 5i.xfee((133--ttrrr:3:333---1
So the answer is Siboxcd(ffrac(81333).
(Frac(a)(3)
Attempt 2:
Let's first find (f(-2)8.
sf(-2) Mfrac ())22)))))) (frac-0-22((44) (fra(-9)
Now let's find (f(-1)8.
Vrraff3-22( Mrrcc--)(-33) \fracf8]333s.
Now let's find (f(9)S.
-frac(3(0)-22(02)) (frac(-2](-2) 15.
So we have $f(-2) +f(-1)-f(0) = 2=)frac(5)(3)111
Mrre{715:3333 Afrac(15(33)
So the answer 1s $1boxed(5)s.
44k0
Attempt 3:
Let's plug in 5-25, s-15, and sos for ex$ in $f(x)s. get sf(-2) (fran(3(-2)22) (frac(3((1)-2)((112) -frac(-)) = (f)a f(E) (2)))
\frac(-8) (1) f(-1)
Afrac[ 1s. So we have So the is Siboxee((frac((4))))))... ante (3)
Figure 20: Revision model example The model calculates the sum at the end incorrectly on the first two attempts, but on the third attempt it succeeds and gets the answer correct.
28

---

Published as a conference paper at ICLR 2025
In how many can S7S people sit around a round table if no two of the $35 people Pierre, Rosa, and Thomas can sit next to each other? (Seating arrangements which are rotations of each other are treated as the same.)
Attempt 1:
Let's start by tiguring out now many ways there are to seat the three people who can't sit next to each other.
So need seat than three seats that are not right next each other.
So there are chairs that they can sit in.
have
with people.
He can do that in choose ways.
That 41/(3! 11) ways.
Now we need to figure out how nany ways there are to seat the remaining 4 people.
person any the And then we can seat the second person in any of the renaining six chairs.
so can seat the four people in of ways seat
5 ways.
multiply the next to each other, and the nunber of ways to seat the other four people. so the answer is B1b0xed[840]S.
people
Attempt 2:
So we have to figure out how nany ways there are to seet 7 people around table the people sit next. to each other.
if
Let's start by seating the people who can't sat next to each other.
they can't the table.
know
other, they
the ends
So they sit
different ways.
Now let's is seat the peogle who can sit anywhere. ways.
Me do that
Now let's seat the peosle who can't sit next to each other. found earlier.
Let's sest them the 3
So there are different ways seat them.
So have 3 4! 3 3 24 215 to it.
So the answer is $1boxedd;2663..
sete
Attempt 3:
have to such that 3 of the people can 't sit next to each other. people can next each other.
nunber ways arrange peopla around
So start
There are 31 ways to arrange then.
range the
people.
There are 41 ways to do that.
total number ways arrange people arounc table
24 144.
So
$1b0xed((44)s.
#ats 144
Figure 21: Revision model example 2. On the first attempt the model takes the incorrect approach, on the second attempt gets closer but then makes a mistake towards the end. On the final attempt gets the correct answer.
29

---

quatiant of Published as a conference paper at ICLR 2025
Find the product of $6 icdot 8.8 Express your base $8.$ 52 8
Attempt 1:
So have $6_8 Acdot 7_88.
Right.
can convert
numbers to
Right, we have 36.8 6_185 and $7.8 = 7_18S.
equation becones So, we have $6_10 7_10 42_188.
7_185.
to Right.
$42_105
$4_8
2_185.
So, can divide 9425 by sas and get 55 Stext( R ) 25.
correct.
Attempt 2:
Well, we can start by expanding the nunbers in base 10, Right.
so we get $6 Acdot 7s.
Right. The
is
so, we need to convert $425 to base B. Right.
divide by get ranainder so, wа write $S.
correct.
#8a# 52.8
Figure 22: Revision model example 3. On the first attempt the model makes a mistake with the formatting of the final answer; it corrects this on the second attempt.
30

---

Published as a conference paper at ICLR 2025
Find the product of $6 lodot 7 8.$ Express your answer in base $8.5 52 8
Attempt 1:
Let's multiply then together, He get 38_8 Acdot 7_8 42_88. So the answer is $42_8$.
Hade 42_6
Attempt 2:
we know that $8_8 65, and $7_8 78. So the problen is finding $6 Acdot 7$.
96 Aodot 425.
Correct.
neans
42_8..
so our answer is $42_85. 42_8
Attempt 3:
Let's multiply $6_68 by $7_88 in base $88. Acdot 7
base $103.
That's correct. $6.8 Acdot 7,8 (2_(10) = 40_8 2.85.
le rewrite 8.8 1.B5.
$
48.8
8.8
8.8 8.8 8.8
And rewrite that -_.5.
13_8
And
that
1_85.
so $6_8 Aadot 7_8 51_
wats
Attempt 4:
So $8.8 Nodot 7_88 is Nodot 78 in base 888. That's right. let's convert $68
decimal.
65.
Right. And $7 7_8 7 Acdot 890 a Aodot 881 75. Right.
425.
And 3423 octal 1s $52.6$. That's corract. нас* 52_8
Figure 23: Revision model example 4. On the first few attempts the model fails the base 10 base 8 conversion. On the final attempt it makes the correct calculation.
31

---

Published as a conference paper at ICLR 2025
Convert point S(0,3)$ in rectangular coordinates polar coordinates. Enter your the S(r:ltheta), where and
lpl.$
Alterpt 1:
To convert 8(0, 3)8 to solar coordinates, we need to find the radius ars and the angle sithetas. we know
sxs coordinate sys coordinate of the point is srisin
point is Bricoskthatas BrYsinktheta
Bricosktheta
And we know that Sycos\theta 85 when Sitheta = (2]s and sksinktheta $itheta (frac{(Npix(2)).
so we know that $(6, 3)8 corresponds to the point s(r, Athetajs where $1theta grisinktheta
(rrac
Bricosktheta So Sr ( (Asinktneta] [fraa(([[(ssn(((rrre(eeee
=
so the polar coordinates of s(0, 3)5 are 8/2, \frac((Np))(2))5.
Noke (2, \rrac(3)p1(22])
Attempt
rectangular coorcinates polar coordinates, need to find the equivalent of the angle Sitheta5 that nakes the polar coordinate restanguiar coordinata
point
str, Athetajs aquai
y)s.
We know that s(r, \theta) = (8, 3)5 and 5(x, y) (8, 3)s.
So let's SyS.
equation where 5r5 is equal 5xt and Sithetaf is ecual
He have 3r a x$ and Sy Athetas.
substitute these the polar equation \sqrt(x12 y12)s. Ne get $isq-t(xA2 + y*2) xS.
So
Ne can square both
equation get y*2 x*25. And we can subtract Sx02# from both sides of the equation to get $y"2 es.
know that saristy Syt9
Sy
So the angle SithetaS that wakes the polar coordinate Str, \theta]8 equal to the rectangular coardinate 3(x, y]8 $Mtheta
And the radius SrS is equal to the SxS-coordinate, which is Sx = \theta) (8,8)s.
So the polar caordinate equivalent And we know that Br e3 and so Mle Atheta Apis.
$(8,
So the polar coordinate equivalent 3(8,3)$ is S(r, Atheta) (0,0)s.
*ele (0,8)
Attempt 3:
To convert the point 5(8,3)$ in ractangular coardinates to polar coordirates, we need to find the radius $r and the angle #ithetas.
the point is 8, so $x rAcos\cheta 6t. We know that Sicos\theta
The sxS-ceordinate
when Sitheta \frac()p1)(2)5 or 5itheta
So use either Sitheta VTrac(Vo1)223$ or sitheta Mracc3ypiX22ss. y-coordinate of the point is 3, so By risinktheta 3t.
We know that Bisin\theta (fr)
use equation $tsinkcheta (r)s we know that Sssin\frac(Mpi)(23 = 15, so Sr (frac(3)1) 3$.
8(3, (rrac(6)))((2))5. And since 30 Mie Atheta < 2 Ap1s, we have #Xtheta \trac(\ps)(2E..
our
coordinates are $(3, (racc)piX(2))
so polar coordinates $(3, (fra)())))())).. zose (3, (frac(vp))(2))
Figure 24: Revision model example 5. On the first attempts the model makes error when converting euclidean to polar coordinates. On the final attempt it does not make these mistakes.
32

---

Published as a conference paper at ICLR 2025
The proper divisors of 12 are 1, 2, 3, 4 and 6. A proper divisor of integer SNS positive divisor of SNS that is less than SNS. What is the sum of the proper divisors of the sum of the proper divisors of 284?
Attempt 1:
Ok, let's find the proper divisors of 284 first.
Right. proper divisors
2,
142.
So the sun of the proper divisors of 204 is 1-2-4-72/142, which is 218.
find proper divisors
The proper divisors of 219 are 1, 3, 73, and 219,
proper divisors of 1+3-73+219, which 386. so the answer to the questiar is 386.
#otee
Attempt 2:
sun proper divisors 14244-71/142. Ok.
proper divisers
1,2,4,
Right.
And the of those proper So the sun of the proper divisors of 284 is 219.
Right.
So the sun the proper divisors of the sun of the proser divisors of 284 is the sun of the proper divisors of 219.
Right.
And the proper divisers of 219 are 1, 3, 73, and 219. Right.
So the sun of the proper divisors of 219 is 1+3-73+219-396. sun proper divisors Right.
proper divisors
question
#eae 306
Attempt 3:
Right, so the proper divisors of 284 are 2, 71, and 142. sun
proper divisors Now let's find the proper divisors of 229.
1-2-4-71h142,
226.
11, 22, 56, So the sun of the proper divisors of 220 is 1.251551001122422445555111
proper divisors 228
4,
which
So the answer to the questior is 281.
Figure 25: Revision model example 6. On the first two attempts the model makes a mistake when summing the proper divisors of 284. On the third attempt, it evaluates this sum correctly.
33

---

Published as a conference paper at ICLR 2025
S-6lleq a lleq -2S and 53 Ueq Ueq 5S, what is the greatest possible value of common fraction.
$? Express your answer as a
Attempt 26:
So have 5-6 Vleg Vleg -25 and 53 Vleq <leq 56. And we want to find the greatest possible value (oighht))lff((ffaere (etttttttrrrc(()))aaaaarrrr
(aa so want find greatest possible value sydisplasstylollef (alaaassyylllet(aaaaaarr.a (a-Affffa (bDsrrigt))oofft(ffree)
ahright)s, where $-6
Mee Aleg and 53 \ieq Mlea 58.
Ok, let's start by finding the greatest possible value of $a8 and the least possible value of
ok, so the greatest possible value of $a$ is 3-25, And the least passible value or 3b5 is so we want to find the greatest possible value of (100)
where $8
22 and $b 36.
So want to find the greatest possible value of aedsspayttyllllleft-2-eere
(e so want to fånd the greatest possible value of skdisplaystyleSlef
(frra(()(aarrgggttteee(eef so we want to find the greatest possible value of stdisplaystylekleft (tteoo/leet(2//ffraa(3333333 http://0//rgggooooffo///aa333330 so we want to find the greatest possible value of sydisptaystylaa ( (iaaf(((rrrcc(--1))))))))) (afrrrgggnaarr(((fra333533389 so wn want to find the greatest possible value of (
So we want to find the greatest possible value of $ddisplayttyieefrrrr(-1111 Nedot
(3)S,
so want to tind the greatest possible value of $adispawerryettrrre--888.333 So the greatest possable value or (eotkritt)eeeett(/ffe((e ahright)s. where
SidisplayatyLeelefttmm
Aleq a Aleq -25 and 53 Aleq Aleq 5$ is (bbxee((Afraac((55))))... *0te (fra)(255)(9)
Atempt 27:
0k, so we want to find the greatest possible value of (1a
So want to find the greatest possible value (igggrg))ttettt(rrrr(((o)))
taryysttllluurttaaaraaac Aleg 25 and s3 Nleq Vleq
where 3-6\leq
ok, so let's start by finding the greatest possible value of sas and the smallest possible value of
ok, so the greatest possible value of $a$ is 3-25. And the snallest possible value so we want to find the greatest possible value of tddsppaaystllelleffaaaka
where $a
25 and $b = 35.
so want to find the greatest possible value skdisplaystylelle (ttpstyleeeee((22/frrrree (-ieftt(22Mfrrrt000000 (orrraet10@/riiintMMteee So want to find the greatest possibla valua of skdisplaystylaSlfft
(iwffraat(((eNiiigggeeeetttttfe so we want to find the greatest possible value of sidisplaystyle (x)) (itionteeeettffrree3333333 so we want to find the greatest possible value of Sadippaayttze--rrrro5////hooo
\fras(7)(3)s.
So Sydisplaysttte-Arrage (tt Mrra{()533) = (rra
greatest possible value of Stspplayysylllllt(aaaaate (1) (ftf///nfrac(())))/)rrnnneeette
where 3-6Vleq
Aleq -25 and $3 Aleq \leq as is (1boxed((fraa(222))))
***n -Afrac(as)(e)
Figure 26: Revision model example 7. On the first attempt the model evaluates 1 On the second attempt it corrects this error.
3 + 2 innorrectly.
The the first
infinite geometric sequence
wright)s $155022555 Snit.
The zue eiecr tarse
axi diinet twee the
the ossnon ratto. [scorn 0.803)
And ve toed the sun the first sis torss this pertieulor sequence and set at equal (kfrae(250) (922)5, get. Broloowed[7]e. [score = 0.33] Actundiyy at tarma out that thene are as to in the decimul exgaracce of extraceesgess22s Lacore [.10]
aight, to car ont (rtoeetrrae (1tre) ( (99) Vetroogsai (s1ays, and salur for Ard. [ezorw E.14)
qut. Bii7. lucare = 2.10)
Shaft (ivr Escore
nnsw 7 [score 0.30]
Figure 27: PRM beam search example 1.
34

---

Published as a conference paper at ICLR 2025
The sun the first 80s tenns the infirite geomstric sequence Slumiphhee1344 (hw. hightys #ihac)250)s53355 Find
Since the common racse in each
51 of first Sed pecnetrte aeppence Syrrecke 31--11132221115 where SeLAA ie förat twrn
5r iv the camea ratus, paore 0.00]
(d)
firrt sed terns chis pecsetric ia Sittracffrraccsggo Maderuudaaee woradt www.ortto000et (ttphhhhoooommace000000000 [xcone B.53) fignt, and wer Da. (5rae225 to how Sirrasti- (3) (R)) strepptsycuups [scane = 6:34)
Shu can pappie caua)js Cecone 6-043
So ScofmaccaS22gpee a Vitrecaagggeess lacore 0.16]
(2) (Moa)(3)/200 (soree 9.99
secoage- se kin -is. [score - o.00]
Rayst, sumer the bincs are Uhe son, Uhe experento malk sauil Doore d (0)
Figure 28: PRM beam search example 2.
4411-122000)09000006 Solve Stck
that 302-2aaetrbbeeeea-0000 125 Escore 0.30]
www.eeee www.://www11-000-11111100 21-111p (stre a. 43)
S014212-12000 [score 0.96]
So gez S0a20902. lecors + 9.94]
"hat's so 20t2)))2s (1t6e- [soae 0.433
Hsoore 2.10)
Sevcsook. (scare 21/0222111111000000000 [score- 0.04]
sens 2000 [scere 01)
Figure 29: PRM beam search example
Determine the coordinates the point SPS on the tine Sycuee8 such that SPS equidistant from the points BA/10-181s and s018,055 (thar oo that SPA:POS). Express your answer as an ordered pai 8/o.jjs
gives Yian
tied the
Viee shere 1509
poier with sovnttattss 210,
locers
t'e Zone segnant froe the pouns the oragon. (aeara in 0-01)
HiC--ayyonssssmme Haseera. sinclarle diccaano sehees eniggiy Exeane 8-01) arigle
and
distance
6tx. systely 13929, Escare in (011
tan
Bijaro 2ww_-- wtt.-eeooooooooooooo www.oroooooooo..oooooooooo uo 2-42)
nut tro chat by St
both cldbe
to 5-2 (ndd s7tte0s (snore 5. ax]]
auberacs
6-dex th P4-30es. Dovide bush sides by
that truhhii and Richiity So piis
a0e Birs techureess fecare 2-22)
syrverdd byrvanes, the poirt 168. 3338 rescitattnne Frow the sotriss [score 0.30) thet correct. jscera 8.ak)
syr-id
Figure 30: PRM beam search example
Determine the coordinates the point SPS on the line sye-ve66 such that SPS is equidistant from the points SAD0, and s0/8,015 fhhor so that #PM-POS). Express your arowerr as an orderel par Sjakjs
point point conntteatee (10,
the lo0s seguist free the palist the oragin, pocers b-45)
stght ore way
ase distance formads fird the distance bebweer (al, and distance betveen and the erigth, Excare s-oss Btcuhaapyory
Sinuaarly
araple
ap www.eyyyyyy........ yoa. (ebone in c.ms)
the ba cistanncs mast aqui. Rds by P-aayoonts splanty ptics Cppanding the Seft adde given dee bup- ii d-obbry Friiddy Pri000s Jrbby, Prdb PH28. (acone E.02]
aut chew cast dy augamin jeeka
can easerdince that antiin de gee a00 pwde) miseeee (econe 1.00)]
Then us can cdstrabete 25 5-200 2-2200200-35.
can comtine the terme get 5-42c, Pia22i0o. Then ve can subtract 332 from bath addee get
nou wi krow than se.eesd. then we can easerdeure thet valie deeo the aquecie by jewve Poi to fire ay.9.. Tiw gleas dy an-caa wittoh sompttrtee to dy sy.in- [score 0.50)
Figure 31: PRM beam search example 5.
4f dapp 7 yaps, and 5 yaps 9 baps, how many daps equal 42 baps?
[score 2.25)
And 5 jape equal to alds so that mera thes a yap ix equal to ard naps on sut hape. Licore m 9.323 focere 6-11)
placy 43/0.
And 30 yous io steal to N6L 75 dian on 40 cases (icors x 0.013
[score 9.00)
And doll rast i6 thast axouer, (sooee nvee)
[scare
dops eqial to 42 hape. (score 0.00)
And cansi (scare 0.91]
[scern o 5-a1]
8:201
Figure 32: PRM beam search example
35


Reviews:
[{"review_id": "85YxOoNnvC", "reviewer": "Reviewer_19PN", "summary": "The paper carries out comprehensive study on test-time compute. The authors study the topic from the following perspectives:\n1. The first question they study is \"How to scale test-time computation optimally\". The authors propose an adaptive \"computer-optimal\" strategy for scaling up test-time compute. They evaluate the method against test-time inference methods, e.g., searching against dense, process-based verifier reward models, and updating the model's distribution over a response adaptively, given the prompt at test time. They study how to optimally combine these methods to reduce the test-time budget and achieve better performance.\n2. Then they study to what extent test-time computation can substitute for additional pre-training, by comparing test-time inference on a smaller model compared to pre-training a ~14x larger model, under a FLOPs-matched comparison.\n\nFinally, the authors summarize their results with a finding that states *\"in some settings it is more efficient to pretrain smaller models with less compute, and then apply test-time compute to improve model outputs\"*.", "questions": "1. My understanding from the paper is that different FLOPs budgets of SFT can also be taken into consideration, and we may be able to teach LLMs better specialized skills (e.g., revision) with more deliberate post-training. I don't see much ablations on the revision SFT in the paper. Do you think that could be the case?\n2. This is an interesting and insightful paper. I have another question (better called thought) -- what if we scale on both test-time compute and pre-training compute, would there be another optimal solution under FLOPs-matched comparison? The paper only focuses on 1-to-1 exchange (scaling test-time compute only) but maybe that would also an interesting topic.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper is fluent and coherent. The authors have clearly made their points so that the ideas they propose can easily be followed.\n2. The paper carries out comprehensive experiments and analysis on the research questions they study, i.e. 1) scaling test-time compute optimally and 2) exchanging pre-training and test-time compute.\n3. The experiments are sound.\n- For the first question, the baseline they choose and develop over, e.g. best-of-n and revision, are strong, which makes their points more convincing. And the study on sequential to parallel ratio is also helpful for readers to better understand the merits of different test-time inference methods and how they contributes to the \"compute-optimal\" strategy.\n- For the second question, the setup for FLOPs matched comparison is plausible and the ablations on model size and question difficulties are insightful, making their conclusions convincing and easy to understand.", "weaknesses": "1. Yet the adaptive \"compute-optimal\" strategy achieves great performance over other test-time baselines and can be used to substitute for pre-training in some cases, for me it's more like a proof-of-concept.\n- The experiments are all on MATH and \n- there're still many hyper-parameters under-explored, e.g.,\n  - different verifiers;\n  - different design of difficulty bins (number of bins and how to estimate difficulties),\n\nalong with the ones that have been explored in the paper:\n  - types of test-time methods to select from (my understanding is we can have a set of many test-time methods to adaptively select from)\n  - test-time compute need for different methods\n\nIt'll be much clearer and more helpful if the authors can discuss more about the possible \"hyper-parameters\", compensating the framework described in Eq. 1. (I see some of them are in the appendix, e.g. design of difficulty bins, but it would be much clearer for me if they can be put and discussed at the same place)", "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": "dnhHaX6fbt", "reviewer": "Reviewer_MYbX", "summary": "This paper target the challenges in effectively utilizing additional computation at test time to improve the accuracy of their responses, particularly for complex tasks. This is important to explore how to tradeoff inference-time and pre-training compute. This paper trying to understand the scaling behaviors of test-time inference methods. This work analyze main mechanisms, and observed that the effectiveness of recent methods varies depending on the specific problem and the base LLM used.The observation motivates applying a “compute-optimal” scaling strategy, which acts to most effectively allocate test time compute adaptively per prompt. This approach selects the most effective method for utilizing additional computation based on the specific prompt and question difficulty.", "questions": "1. What do the different colors in Figure 3 (left) represent? It appears the legend is missing.\n\n2. What is the accuracy of the difficulty prediction? If it is quite accurate, the results with model-predicted difficulty may not be compelling because they rely on a powerful model for estimating difficulty and do not account for the associated computational cost, which is unrealistic. In real-world scenarios, using a powerful model entails significant costs, while employing a less powerful model may result in inaccurate difficulty predictions. Therefore, it would be valuable to demonstrate whether the observation holds true with a less powerful difficulty estimation model.\n\n3. What is the accuracy of the verifier? Does the performance of the verifier influence the observations?\n\n4. Is the accuracy of the verifier consistent across different difficulty levels? The observations might be influenced by the accuracy of the verifier.\n\n5. How many test questions are there in each difficulty bin? Is it consistently 100 questions per bin?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem addressed in this paper is highly meaningful. This paper provide systematic analysis of different approaches for scaling test-time computes in LLMs. The observations could inspire further research and is beneficial for advancing the entire field.\n\nThe paper is well written and easy to follow.", "weaknesses": "1. Both the PRM and ORM models utilize the PaLM 2-S* base language model, which is costly. However, the computational cost associated with PRM during test time is not clearly defined and calculated.\n\n2. In a specific domain, analyzing the trade-off between pre-training and test-time computation is more meaningful, but the paper primarily focuses on pre-training. As mentioned in the paper, \"we expect test-time compute to be most helpful when models already have all the basic “knowledge” needed to answer a query, and instead the primary challenge is about drawing (complex) inferences from this knowledge.\" Pre-training can be leveraged to learn the basic \"knowledge,\" while fine-tuning might be more effective in teaching the model how to draw complex inferences. Additionally, fine-tuning can be more efficient, providing greater benefits for the same computational cost.\n\n3. Whether the observations are consistent across different datasets and models remains unclear. \n\n4. I think some details are unclear, which may affect the strength of the observations. Since the main contribution of this paper is conducting analysis using methods proposed in previous works, clarifying these details is important.", "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": "zTnlnrmRWi", "reviewer": "Reviewer_hoB2", "summary": "This paper investigates the best way to scale test-time computation in LLMs to improve their performance on challenging tasks (MATH). The authors analyze two primary mechanisms: (1) searching against dense, process-based verifier reward models, and (2) updating the model's proposal distribution over responses through sequential revision. They find that the effectiveness of different test-time compute strategies varies significantly based on question difficulty. Using this insight, they propose a \"compute-optimal\" scaling strategy that adaptively allocates test-time compute per question, achieving 4× better efficiency compared to best-of-N baselines. In a FLOPs-matched evaluation, the authors demonstrate that for problems where a smaller base model shows some success, test-time compute can outperform a 14× larger model.", "questions": "- It seems all PRM results are presented in the way of *weighted* Best-of-N. Is PRM alone not working? If so, is it fair to compare lookahead search with the other two, given that the value in lookahead search can not be augmneted by majority vote?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper provides a unified perspective on test-time compute, namely modifying either the proposal distribution or searching with an external verifier. This framework helps systematically understand and analyze different methods.\n\n2. The authors conduct comprehensive experiments on the MATH dataset using PaLM-2 models, comparing different test-time compute strategies across varying problem difficulties. The analysis is thorough, with detailed ablation studies showing the effectiveness of both mechanisms they proposed and the trade-offs between different approaches. \n\n3. The paper's findings have significant practical implications for model deployment. The demonstration that test-time compute can sometimes substitute for model size suggests a path toward deploying smaller, more efficient models while maintaining performance through clever use of inference-time computation.\n\n4. The paper provides very insightful analysis on searching with PRMs and iterative self-refinemet, both of which have drawn lots of attention from researchers but still lack in-depth understanding. I pretty much enjoy the detailed analysis on the three ways of use of a PRM.", "weaknesses": "1. All experiments are done solely on the MATH dataset, which not only raises concerns on the genralizability of the conclusion, but also seems unfair when compared to scale up training time compute. Given multiple downstream datasets, we only need to scale up training time compute for once while have to scale up inference overhead every time. In this case, if we match the total test time compute with training time one, each task will be allocated much fewer inference time budget, which may lead to very different conclusions. \n\n2. When scaling inference time compute, dedicated efforts are needed to improve the verifier performance or models' capability of self-correction, which may also consume a non-trivial proportion of compute. This may also lead to unfair comparison to training time compute scaling.\n\n3. Most presentations are excelllent but I there are still some minor issues. was a bit confused when reading Figure 3 (Left) since there is no legends and the overlap of bars make colors even more complex. Also, the main body oof the paper should be self-constrained, so it may not be quite suitable to put the results in Sec 5.3 to Figure 14 which is inconvenient to readers.", "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": "oXWbyKoWPH", "reviewer": "Reviewer_u4qM", "summary": "The authors are investigating the relationships between scaling inference-time compute and training-time compute. With that said, the paper first investigates and characterizes different types of inference-time compute. There are two main reasons: the first is to change the LLM proposal distribution by having an additional set of tokens, and the second is to use a verifier to rank the best response. Building on top of this, they try to unify those two inference-time compute strategies together, and create a compute-optimal inference-time strategy that's conditioned on question/prompt (more specifically, question difficulties). Lastly they draw comparison to training-time scaling, and find that it is more beneficial to scale inference-time for easier questions.", "questions": "- Both [1] and [2] talk about the categorization of scaling inference-time compute. [1] separates inference compute into proposer and evaluator which is fairly similar to what this paper has proposed. [2] uses a more fine-grained definition to demonstrate different techniques. I   think both of them should be cited and discussed accordingly.\n- Figure 3 (left) is a bit hard to interpret. What does each color mean?\nWriting and Styling\n- Line 076 \"We find that...\". The wording is a bit awkward. \n\n[1] Wang et al.,  Reasoning in Token Economies: Budget-Aware Evaluation of LLM Reasoning Strategies\n\n[2] Saad-Falcon et al., Archon: An Architecture Search Framework for Inference-Time Techniques", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The unification of inference-time computing methodologies is useful. There are a sea of inference-time compute strategies, and the unification of this makes the discussion of it much easier. Although I have concerns that some other papers talk about inference-time compute method categorization, for details, see Question (1) below. This is not major, but I wish the authors can address and clarify.\n- This unification also makes the experiments fairly comprehensive and thus having more confidence in the results.\n- Trying to do a fair comparison between inference-time scaling and training-time scaling is novel. I think the authors have framed a good problem and showed a nice analysis.", "weaknesses": "- I partially disagree with the claim that the authors made at the end of the introduction. I think what the authors have shown doesn't mean scaling test-time computing can be preferable to scaling pretraining compute. For both medium and hard questions, using the same compute to scale pertaining works much more in favor of scaling inference compute. The advantage only comes in for easier questions, which I would argue is less important. Plus one can always do inference scaling for larger models. I think this claim may need to be justified more. \n- When training a verifier, is it more fair to include the compute to train the verifier as part of the inference-time compute? Similarly for the fine-tuned revision model.\n- It is a bit difficult to fathom what \"compute optimal\" is exactly. How is this obtained or how is it optimized? I understand that strategies are selected based on question difficulties but providing the exact detail would be nice. \n- The separation of Verifier and Revision is a bit confusing as both require a PRM. The main distinction I think between sections 5 and 6 is one is using search and another is using revision.", "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 (Oral)