Scaling Test-Time Compute Without Verification or RL is Suboptimal
Authors: Amrith Setlur
Nived Rajaraman
Sergey Levine
Aviral Kumar
Venue: ICML 2025 spotlightposter (2025)
Keywords: LLMs
test-time compute
verification
RL
finetuning
reasoning
RL theory
Primary area: deep_learning->large_language_models
TL;DR: We show that using verification signal scales test-time compute better than verification free methods, asymptotically.

Abstract: Despite substantial advances in scaling test-time compute, an ongoing debate in the community is how it should be scaled up to enable continued and efficient improvements with scaling. There are largely two approaches: (i) distilling successful search or thinking traces; and (ii), using verification (e.g., 0/1 outcome rewards, or verifiers) to guide reinforcement learning (RL) and search algorithms. In this paper, we prove that finetuning LLMs with verifier-based (VB) methods based on RL or search is far superior to verifier-free (VF) approaches based on distilling or cloning search traces, given a fixed amount of compute/data budget. Further, we show that as we scale test-time compute (measured as the output token length) and training data, suboptimality of VF methods scales poorly compared to VB when the base pre-trained LLM presents a heterogeneous distribution over correct solution traces (e.g., different lengths, styles, etc.) and admits a non-sharp distribution over rewards on traces sampled from it. We formalize this condition using anti-concentration [Erdős 1945], implying a stronger result that VB methods scale better asymptotically, with the performance gap between VB and VF widening as test-time budget grows.
We corroborate our theory empirically on didactic and math reasoning problems with 3/8/32B-sized pre-trained LLMs, where we find verification is crucial for scaling test-time compute.

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Amrith Setlur' Nived Rajaraman
Sergey Levine
Aviral Kumar'
Abstract
Verifar-Frae: E.g. SFT search traces
Despite substantial advances in scaling test-time compute, an ongoing debate in the community is how should be scaled up to enable continued and efficient improvements with scaling. There are largely two approaches: (i) distilling success- ful search or thinking traces; and (ii), using ver- ification (e.g., 0/1 outcome rewards, or verifiers) to guide reinforcement learning (RL) and search algorithms. In this paper, we prove that finetuning LLMs with verifier-based (VB) methods based on RL or search is far superior to verifier-fre free (VF) approaches based on distilling or cloning search traces, given a fixed amount of compute/- data budget. Further, we show that as we scale test-time compute (measured as the output token length) and training data, suboptimality of VF methods scales poorly compared to VB when the base pre-trained LLM presents a heterogeneous distribution over correct solution traces (e.g., dif- ferent lengths, styles, etc.) and admits a non- sharp distribution over rewards traces sampled from it. We formalize this condition using anti- concentration (Erdös, 1945), implying a stronger result that VB methods scale better asymptoti- cally, with the performance gap between VB and VF widening as test-time budget grows. We cor- roborate our theory empirically on didactic and math reasoning problems with 3/8/32B-size pre- trained L.MSs, where we find verification is cru- cial for scaling test-time compute.
Prompts (problams
Expert 7y
P em Expert trace
Verifer Based
Gap grows as v/#
nemwerd
Prob Base riloot Reward rfc.
Annotator
Free
Base its
Verifar-Basedh E. RL with ground truth
scaling tast time compute R. draining cata (LF)
rewards, lest-lime search
Figure 1: Scaling test-time compute: Given of problems, verifier-free (VF) methods query expert traces, whereas verifier- based (VB) methods collect reward annotations for rollouts from the base LLM. Crucially, one aims to mimic "good" traces and the other seeks improve access to verification. We prove a /H gap between a simple VB method and any VF method as we scale data n and compute H, and verify this in practice.
result, scaling test- cest-time compute is emerging as an alternate paradigm for improving reasoning performance, where an LLM is made capable of executing search or refinement procedures, either implicitly by training for it, or by explic- itly executing the search top of the LLM outputs. The goal here is to search over responses for test query, which naturally leads to traces much longer than a direct answer. Broadly, we can classify the set of prevalant approaches for scaling test compute into two categories (see Figure 1).
The first class uses some form of verification, e.g., 0/1 outcome reward verifier, for test-time search (Cobbe et al., 2021 or reinforcement learning (RL), e.g., Deepseek R1 (DeepSeek-A) AI et al., 2025) uses outcome reward. The second class of approaches circumvents verification alto- gether and runs supervised fine-tuning on "expert" traces, obtained either by piecing together tree search (Gandhi et al., 2024; Moon al., 2024), or by querying bigger models trained generate longer traces, i.e., distillation approaches (e.g., S1 (Muennighoffi et al., 2025), OpenThinker (Team, 2025), etc.). We refer to these as "verifier-free", as these methods do not query any verification signal for guiding learning. Despite the prevalence of both classes, Lee. verifier- based (VB) and verifier-free (VF), it is not clear which class results in better test-time scaling, especially when the amount of test-time compute increases. We theoretically and empirically show that when fine-tuning pre-trained L.M,, VB methods are expected to perform better.
1. Introduction
Pre-training and post-training of LLMs rely heavily on ac- cess to high-quality "expert" data, but it is projected that by 2028, the availability of such data on the Internet will dimin- ish (Villalobos et al., 2022; Liu et al., 2024), and improving model performance on several domains (e.g., reasoning, safety, etc.) often requires more data (Li al., 2024). As
'Carnegic Mellon University PUC Berkeley. Correspondence to: Amrith Setlur <asetlur@ es.cmu..cuu.
Theoretically, we show in this paper that VB methods out- perform VF methods as we scale data and compute, To do so, we operate in a setting where we are given a base
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
LLM Ty and dataset of problems. We represent the total available test-time compute in terms of the total number of tokens H/ that can be used to produce solution. Our goal is to finetune TT to make efficient use of test-time compute, Le., attain best performance within a given compute budget. For learning, VF methods are allowed to obtain at most n correct solution traces for these problems by querying an expert (e.g., humans, linearized search (Gandhi et al., 2024), etc.). On the other hand, VB methods are allowed to query reward annotator that measures correctness of given re- sponse on n samples generated from T6 but never observes expert traces. When operating in this setup (which reflects practical scenarios), we prove that as we scale training data n and test-time compute budget H, the separation between simple verifier-based approach based on RL, and any verifier-free method grows. Since both class of approaches involve finetuming T&, the properties of the pre- trained Ti plays key role in our separation result, as we discuss below.
timality gap of Q(H/v ( in the worst case. For this we build on second-order suboptimality bounds in Foster et al. (2024a). That said, we then show that the suboptimality for simple VB method that runs RL with a trained verifier or actual 0/1 outcome rewards scales as O(H/n). In fact, we show that the heterogeneity of the base policy is often helpful for VB approaches, as long as the heterogeneity also implies anti-concentration, i.e., there is a reasonable chance to sample traces with rewards slightly better than the mean reward attained under the base policy. Consequently, the performance difference between VB and VF methods scales with the horizon or test compute H. This implies the need for training verifiers, running RL, or at the very least, using rewards when finetuning LLMs for test-time scaling.
Empirical results corroborating theory. We corroborate our theoretical results math reasoning with 3B/8B Llama models, and the S1 (Muennighoff et al., 2025) model. For the S1 model that is trained in a verifier-free manner, we show that a simple verifier-based approach performs better than S1 across a set of test-time compute budgets (Figure 6). For the LL models, we explicitly control the heterogene- ity of the base LLM and show that VF methods perform poorly with more heterogeneous base LLMs, and that the gap between VB and VF performance scales with more test- time compute (Figure 5 in Section 7). Our investigation also reveals that common pre-trained LLMs are indeed heteroge- ncous and satisfy anti-concentration, which are abstractions we introduce to prove our theoretical results (Figure 7, 8). To the best our knowledge, this is the first theoretical result and systematic study showing separation between VF and VB methods, under realistic assumptions on the base model.
What properties of the pre-trained LLM enable VB meth- ods to scale better than VF methods? To evaluate the per- formance of different approaches across varying test-time compute budgets, we define rewards that are high when the LLM arrives at the correct solution, and does so with- out completely exhausting the provided token budget. We show that when the base LLM admits sufficiently hetero- geneous distribution over rewards (i.e., it admits coverage over multiple correct sequences of varying lengths for a given problem), then scaling test-time compute by running any VF approach is suboptimal. In contrast, under spe- cific form of heterogeneity (which is also generally satis- fied in practice), the performance of the policy obtained by running RL with verifiers (either implicit 0/1 "regex" matching rewards or explicitly trained numerical, generative verifiers) is better at any given test-time compute budget, and, moreover, also scales better as we further increase test- time compute. We term this specific form of heterogeneity as antii-concentration: for given problem, a base LLM is said to be antiiconcentrated if it admits non-trivial probabil- ity mass over solution traces that achieve rewards slightly better than the mean reward for that problem under the base policy. In Figure 3 we illustrate these two properties: het- erogeneity and amti-concentratioo. Given a problem. if the base L.M samples correct responses of varying response length (heterogeneity), but also samples solution traces that rewarded higher than the mean reward on that problem (anti-concentration)) we prove that VB methods asymptot- ically dominate VF methods as we proportionately scale both training data n and the test-time compute H.
Implications and takeaways. Our work presents several im- plications for practitioners. As long as the pre-trained LLM is sufficiently hetergeneous and anti-concentrated, which we verify are both satsified in practice for models we evaluate, our analysis implies: (i) While recent results imply that both verifier-free and verifier-based methods
work well at large compute budget, we show that VB methods scale better as the test-time budget increases; (ii) This gap can be amplified further when the number of prompts for VB fine- tuning also scales linearly with the allowed test-time token budget. Another implication of our results that since VF methods work well when heterogeneity is small, this means that in order for them to scale well, pre-trained LLMs must also exhibit low heterogeneity, but we believe that this is rarely the case with modern L.MSs in practice.
2. Related Work
Overview of how we show the separation between VB and VF. For our main result, we first prove an information- theoretic lower bound showing that the suboptimality of any VF algorithm scales as the heterogeneity diversity of the base policy being finetuned, which implies subop-
Scaling test-time compute. Recent works (Sardana et al., 2023; Snell et al., 2024) show that scaling test-time compute can improve performance at rates faster than sealing data (Li et al., 2024) or model size (Hoffmann et al., 2022), either by (i) training an LLM to implement search (Yao et al., 2023;
2

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Gandhi et al.. 2024) or refinement (Kumar et al., 2024; Qu al., 2024) procedure in its long thain-of-thought; or (ii)
token dn the environment deterministically transitions to state St+1 (sn, (4) obtained by concatenation and col- lects reward Th =: r(s,, a,)). A policy E I1 is a function Th S (AA) which produces distribution over tokens at each state. We use dz to denote the distribution over S₁ in- duced by オ. A solution trace is a rollout T = (x, 01..........................00 an)) in the MDP, and r(T) = En r(s,, as). We use the notation Ep.. [ to denote the expectation Exxo [->-
wrapping LLMs with search procedures (Wu et al., 2024;
Beeching et al., 2024) that use trained verifiers (Cobbe et al.,
2021a; Setlur et al., 2024b) as cost functions for search. We do not study this distinction in this paper, but rather focus on an orthogonal axis that can be used to separate test- time methods: whether or not there access a reward or verification signal during training and/or inference.
4. Effectively Scaling Test-Time Compute
Verifier-based (VB) algorithms. Several works use 0/1 "outcome" reward annotations (Uesato et al., 2022; Bi et al., 2024) for training LLM reasoners. Some also use trained verifiers (Hosseini et al., 2024) or run search test-time search (Welleck et al., 2024; Chen et al., 2024b). More recently, using 0/1 verification signals for RL (Kimi-Team, 2025; DeepSeek-AI et al., 2025) has shown impressive re- sults. Other algorithms use verification by converting 0/1 rewards into a value function (Rafailov et al., 2023; Zelik- man et al., 2022; Singh et al., 2023; Setlur et al., 2024a). Verification can be done generatively (Zhang et al., 2024) and implicitly (Yuan et al., 2024), all within one single LLM alternating between generation and verification. We bucket all of these VB methods and show that querying verifiers or rewards is critical for scaling test-time compute.
Our goal is to compare methods that finetune LLMs to most efficiently scale test-time compute. We say that an algorithm is effective at making consistent use of test compute if it attains the best performance possible within a fixed compute budget. In practice, this means that an approach must strike a balance between directly "guessing" an answer, which uses the least number of tokens but is unlikely succeed, and re- attempting sequentially (i.e., run linearized search), which is less token efficient and wastes compute, but is more likely to succeed at least once. This entails procedure where models are deployed with an ever-growing upper bound on test-time token budgets in hopes to find more successes for a given prompt, underscoring the necessity of efficient asymptotic scaling as we formalize in this section.
ferifier-free (VF) algorithms. With the goal of distilling search procedures multiple works (Yang et al., 2022; Xie et al., 2024; Lehnert et al., 2024; Gandhi et al., 2024). SFT pre- LLMs on search traces (Gandhi et al., 2024; Nie et al., 2024) that all succeed eventually. This is done so that the LLM learns to search for solutions on test problems (Sel et al., 2023). These methods are reward-free and are thus forced to mimic heterogeneous search traces with varying token counts. This makes generalization difficult for any SET method, leading to poor test-time scaling, aligning with prior findings (Kumar et al., 2024; Xiang et al., 2025).
Denoting a base LLM as an autoregressive policy To (als) and given budget on test-time compute represented in terms of a maximum H output token length, we evaluate a finetuning algorithm by measuring the performance of the policy produced by finetuning Ty under a specific reward function r(s, a). This reward function should capture both the accuracy and the efficiency of attaining the solution. One such family of reward functions is bi-level reward.
Bi-level reward. As discussed in Property 4.1, we say that a reward function is a bi-level reward when on any given trajectory, the reward remains 0 until it reaches a state corre- sponding to the correct solution, at which point receives a reward of (for the first time), and then continues to collect 1s in the future no matter what it samples (Figure 2). That is, once the LLM generates correct solution, it continues to attain high rewards. For solution trace T = (x, 01,... an)) we define the reward r(T) =: formance (expected reward) of is JT( =: Ep, [r(r)). A correct trace T is one that gets the answer correct at some point within the budget of H tokens, i.e., r(r) > 0. To maxi- mize efficiency, we want r(T) to be as high as possible in the distribution of the test problem, denoted p. i.e., max, Jr J,( where (T( =: Ep. Σ r(si, az). The Q-value is de- fined as : Q* an) =; Ep. E/ r(s,,()) Sh, an
3. Notation and Preliminaries
Notation. We use the usual 0/52 notation, where (b)) when O(b max(1, polylog(b))), and S b for (b)) The set of integers {1, .1. n) is denoted as [ni]. For a set S. the set of all measures over S is given by ASS).
HH Σh= r(s,, and the per-
Preliminaries. Following prior work (Kazemnejad et al., 2024; Setlur et al., 2024a) we model language genera- tion as a token-level Markov decision process (MDP): M(S, A. r, H), with state space S. token space A, binary reward S x A + {0, 1} in class R, and horizon (to- ken budget) H. Let Sn denote the set of states at time h (so, S = , The set of initial states S₁ is the set of input problems X' e x, sampled from a distribution p. At time h, state 8, is given exactly by the concatenation of the problem x and the sequence of tokens sampled till
Property 4.1 (Bi-level rewards). For any trajectory T, rewards are binary and non-decreasing, i.c. Vh E [M]. rh+1 (S a1+1) (5/++1)0441)) 2 r (sh, an). (example in Figure 2).
step h- 1, iee, Sh, = (x, a),-.., ah-1):: 1); upon producing
3

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Reword
1.0
issues such memorization and optimization pathologies from finetuning (Kang et al., 2024; Tajwar et al., 2024). For e.g., one predominant way of constructing expert data is to first sample multiple traces from Tr and then retain all correct traces (Zelikman et al., 2022; Gulcehre et al., 2023). While existing theoretical abstractions do not prescribe an ideal condition to quantify (b), we formalize this practical constraint by constraining the expert to be the highest reward policy in IT. the set of all policies with x² divergence w.r.t. the base Th. We choose x² over other f-divergences like KI. for simplicity (Huang et al., 2024b).
0.0
5
Time step
Figure 2: Example of bi-level rewards: After the first step where reward is 1, irrespecctvve of future actions reward remains 1.
Asymptotic test-time compute efficiency. Having defined how we can measure the efficacy of a finetuning algorithm in scaling test-time compute within a budget of H tokens, we now turn to providing a formal definition that allows us compare different fine-tuning algorithms. Concretely, Definition 4.2 defines what it means for an algorithm to "asymptotically" scale test-time compute by Ha, compared to another algorithm. Under our bi-level reward formulation, a higher value of a implies that algorithm A is able to arrive at the correct answers spending = H less compute on average compared to A2, as we scale H. In the next section, we show that verifier-based algorithms scales test compute by (2(H) compared to veriifer-fre free algorithms.
Tee (T x)
(T( x -
1) 27
xxa (Tell =: Ep.r.
S n. (I)
We refer to the x-X² ball of expert policies as II,, and the optimal expert, i.e., arg max (T), as Tx.
A verifter-based (VB) algorithm is one that finetunes the base policy without an expert, but instead queries an annota- tor to provide rewards to solution traces sampled from my. E.g. RL with outcome rewards (DeepSeek-Al al., 2025) or using generative verifiers (Zhang et al., 2024) count as VB methods. Note that this definition does not necessarily require a learned verifier. In all, these classes of methods differ in the learning signal being ued: access to an expert policy vs. access toa a bi-level reward annotator.
Definition 4.2 (Scaling test-time compute by I1 Fix any bi-level reward r, base policy Th. horizon H and data budget n = (.H). we say that algorithm A₁ producing policy (H),, asymptotically scales test-time compute by Ha compared to As producing (2(H) if:
(.(A(HH) - (A222 (H)) = (HH)).
We compare VF and VB methods, given n rollouts sam- pled from expert policy for VF methods and n base policy rollouts with reward annotations for VB. We are interested in evaluting whether VB methods scale test-time compute better than VF as per Definition 4.2. Our main theoreti- cal result, Theorem 5.1, states that for any bi-level reward function, there exist base policies Te. representative of pre- trained LLMs, where a simple VB method scales test-time compute better than all VF methods by at least D( ((VH) H.)
5. Theory: When Does Verification Enable Asymptotic Scaling of Test Compute?
In this section, we theoretically compare verifier-free and verifier-based algorithms when scaling test-time compute. We show that for any bi-level reward, there are base policies (pre-trained LLMs) that enable verification based algorithms to asympptotcally scale test-time compute H, by factor of 9( ((VH) H)) relative to any verifier-free approach, and quantify these properties of the pre-trained base LLM.
Theorem 5.1 (Main result; informal). For any bi-level re- ward and sufficiently large data budget n, there exists a base policy Th. perifier-based algorithm A, such that fine- tuning Ty with A scales test-time compute (Definition 4.2) by Ω H)VH) relative to any verifier-free algorithm.
A verifier-free (VF) algorithm finetunes the base LLM Tb to mimic data from an expert policy xe without using any re- wards or verification. The expert n. can produce a solution trace that directly results in the final correct answer (Ze- likman al., 2022) or perform number of search and/or backtracking operations eventually end in the final correct answer (Gandhi et al., 2024). The expert policy samples correct traces T, i.e. r(T)= > 0, however these traces are not guaranteed to be the most compute-efficient
Key insight. To prove the above, we establish an instance- dependent information-theoreii lower bound on the sub- optimality gap of any VF method, which is H/vū when m, is sufficiently heterogeneous, i.e., solution traces for a given prompt vary a lot in token efficiency. Then, we show that simple verifier-based method attains a suboptimality gap upper bound of only H /nn, even when no is heteroge- neous. For this, т. should cover some high-reward traces with a sufficient probability. Formally, when the distribution over rewards attained by traces sampled from NT is hetero- geneous and not too "sharply" " concentrated around its mean and n = ((H) (typically the case for best performance).
efficient (i.e., r(T) * H) as each one may get to the answer spending varying number of tokens for search, backtracking, and COT.
The performance of any verifier-free algorithm is dependent on the choice of the expert. So, how do we choose "good" experts for learning? Such experts must satisfy two condi- tions: (a) they should attain high rewards (end in correct final answer), and (b) the expert's 's distribution should be at least somewhat "close" to the base policy ne to prevent
4

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Likelioood
VB methods scale test-time efficiency by VH over VF meth- ods. A pictorial illustration of these conditions is shown in Figure 3, which we also show holds empirically (Section 7). Then, we use techniques from second-order adaptive bounds to develop an analysis for proving the separation result.
Rewards
Heterogeneity
Property 52
Anti-concentration
Property 5.8
5.1. Lower Bounds for Verifier-Free Expert Cloning
Figure 3: Illustration of properties of the base model me that enable VB methods to outperform VF methods: heterogeneity (Property 5.2) and anti-concentration (Property 5.6).
We first derive an information-tin thhorretcc lower bound for VF methods comparing them to the expert policy Te. To under- stand the implications of our theoretical result, we state our lower bound using a notion of "base policy heterogeneity", which measures the variability in the token sequences that all attain the same final answer under Tb- We define this notion of policy heterogeneity as follows:
Theorem 5.4 Informattion-theoreti lower bound verifier-free free algorithms). Given any p. T, To, expert pol- icy Te and ls S |x4/4, there exists a family of alternate expert policies II' of size 2 and reward class R' C R. s.t. for any #yf returned by any verifier-free algorithm:
Property 5.2 (Policy heterogeneity). Given problem x, the heterogeneity of E x is given by:
log II'
max max Jx(T') (
E'El' MERR'
TE
H
Σ
E Ea [Vara=>(1<a)) (Sh: an)l x]]
Va' E IT' 0z. = =o(2)) under any alternate reward function r' E R', and 11' C [Ieaee Finally, when the total hetetogeneity o² S (6/5)0², then the median hetero- geneity across problems ã. scales Ma.,), i.e, we can replace öe in the bound above with Te.
h=1
Total heterogeneity across problems is o = =Pxmp Exmp [0
the median is ã= == Median : x E )),, and the mean across problems is or = Ex-p [0
For the expert policy, heterogeneity is non-zero when dif- ferent solution traces spend different tokens and token bud- gets to attain the final answer from any state-action tuple attained in trajectory. We expect most practical LLM finetuning datasets obtained by rejection sampling, concate- nating search traces, collecting human thinking trace data, or distilling from larger models to induce quite hetero- geneous expert, since a high diversity of solution traces is often a desideratum employed by practitioners when gen- erating training data in supervised finetuning (Chen et al., 2024a). In order to obtain heterogeneous expert traces, we would also need the base policy To to be heterogeneous. In fact, we show useful result relating heterogeneity of me to that of Th, which allows us to present our lower bound directly in terms of a, of the base policy (instead of oz). Lemma 5.3 (Lower bound on expert heterogeneity). Let the heterogeneity of base policy To be oß. For any expert me E
To prove this result, we extend the lower bound result from Foster et al. (2024a), which applies to only one prompt, to an instance-dependent lower bound that applies to set- ting with more than one prompt and bi-level rewards. See Appendix C.3 for formal statement and proof. This result implies that it is challenging to clone highly heteroge- neous experts: when ã scales as Q(H). ), the bound grows as Q H Vn). A linear dependence on horizon is unavoidable, even though the transition dynamics in this problem are triv- ial (i.e., just concatenation) and the transitions are known. The one scenario where this bound can be reasonable is when ōb is small, but this is rarely the case in practice be- cause pre-trained LLMs tend to be quite heterogeneous. Due to pathologies from training on narrow data, users prefer using more heterogeneous base models and experts.
5.2. A Simple Verifier-Basse Algorithm
T1, its heterogeneity o satisfies la? - of S Hop/k/2.
So far, we saw that heterogeneity can hurt the performance of any VF algorithm that uses expert data without reward annotations. Next, we show that this limitation does not ex- ist for VB methods, by constructing a simple algorithm that trains a verifier using n reward annotations on data sampled from the base policy T. (which need not be an expert). Con- cretely, our algorithm first trains a verifier to predict sparse 0/1 1 correctness of a given solution trace using the provided data, to the best possible accuracy. Then, it finetunes the LLM to maximize the verifier scores on the distribution of problems Note, that at test-time we sample problems i. d. from p. Crucially, the algorithm does not assume access to ground-truie truth rewards over the entire distribution p. but only a small training dataset Dr,- We present this approach for-
Reading Theorem 5.4. This bound means that a dataset of n datapoints from fixed expert Te is fundamentally insufficient to resolve uncertainty as to which of the experts E II' was the one generating the data. Using a verifier-free algorithm here incurs a suboptimality that depends on 8./vm for the worst choice of this expert in I1', meaning that for any given reward function, base policy and expert, there is a problem instance II' and an alternate reward r' where this guarantee is tight. Further, when the total heterogeneity of x o², then we can replace the median with the expert's heterogeneity de, which is in turn close to the base LLM's heterogeneity db as stated by our Lemma 5.3.
5

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
mally in Algorithm 1. In particular, Step 2 produces class of verifiers R. that are 7-optimal as measured by squared loss. Step 3 produces policy that performs optimally the worst reward in R.,. This technique of optimizing a pessimistic reward is common in both theory and practice of offline RL (Wang et al., 2024), and has also been useful for preventing reward overoptimization (Coste et al., 2024).
traces from To on a given prompt. We call this the anti- concentation condition. As long as the reward distribution puts a constant probability mass reward values that are R Øxvi higher than the mean reward To gets on prompt x, we say that the policy is anti-concentrated (Property 5.6; an illustration of this condition is shown in Figure 3).
Property 5.6 (Antticoncentraate Tb). For problem x, horizon H. and base policy Ty. let cx(E) be the prob- ability mass that reward r(r) is larger than the mean ETwTa(11x) [r(r]] by a margin of Tb.EV..
In practice, algorithms that use some sort of verification, either train a policy on ground-truth 0/1 rewards on a fixed set of training problems, e.g., in RI (DeepSeek-Al et al., 2025), DeepScaleR (Luo et al., 2025); or train outcome/pro- cess verifiers to predict ground-trutt rewards on the same training problems, and use the verifiers at test time to run search over responses sampled from the hase policy given test problems, e.g., best-of-N (Cobbe et al., 2021a), beam search (Beeching et al., 2024; Snell et al., 2024; Setlur et al., 2024b). The former trains policy that generalizes onto test problems, and the latter trains a verifier with the expecta- tion that the verifier's predictions are accurate on the test problems. Algorithm below falls in the latter category of verification- approaches. Next, we show that this VB
(x(E) =: :PPrwaa((1x)) [(T) - x) [r(r))+ +
The base LLM To is said to be c-anticoncentrated if miny (x(Nxx 2 e, where fix =: Dx= (i (=))(xx]l= xx) and 7x denotes the best policy in II, (highest perfor- mance). The value of Ky depends on how much an expert is allowed to deviate from To on problem x.
Even under high heterogeneity (Property 5.2), an anti- concentrated Ta covers-with a constant mass-a policy that improves over its own mean. This means that an algorithm using the reward signal to fine-tune T& should be able to discover this "better" policy. VF algorithms that do not uti- lize to the reward signal fail at finding this high-rewardigg policy. While non-heterogeneous base policy (for e.g., one that always samples a single trace for given x) will not satisfy Property 5.6, hetergeneous distributions can easily be anti-concentrated since heterogeneity is a property of a moment (i.e., variance) of the reward distribution whereas Property 5.6 fundamentally relates to the shape or the CDF of the reward distribution. We demonstrate in our experi- ments that pre-trained LLMs often satisfy this property.
Algorithm 1 Simple Verifier-Based Algorithm
Require: Base policy Te, dataset Dir =: {(x;, R)) of problems x, ~ p and traces Ti <> Tb(- |x).
1: For every Tı annotate (x,, T,) with bi-level reward yi-
2: Learn set of classifiers R. C. R that are y-optimal, i.e.,
Ry =: = [VER E - E "
3: Return any optimal pessimistic verifier-based policy, avb E arg max min (f).. REll rER,
How can VB algorithms b from anti-concentration of n As discussed above, Property 5.6 ensures the existence of a good policy that is covered by the base policy, with high probability. Intuitively, running RL should be able to then sample traces that attain high rewards and learn to pick up on this reward with more training. From theo- retical perspective, note that the suboptimality gap of any VB method depends on the distribution shift between the data data-generating policy (TA. in our case) and the compara- tor policy that we wish to provide the guarantee against (7x), since this shift dictates how generalization error dur- ing training gets amplified when the model is deployed. This notion of distribution shift is typically formalized as bounded coverage coefficient (Rashidinejad et al., 2021) of an unknown comparator policy, which is restrictive. We strengthen the notion of coverage coefficient by leveraging anti-concentration, which allows us to optimally construct a high-reward comparator policy covered by the base policy.
algorithm attains a lower suboptimality gap. To do so, we first prove an intermediate Lemma 5.5, which upper bounds the accuracy of the verifier trained on Drr in Algorithm 1.
Proposition 5.5 (Verifier accuracy). For any bi-level reward base policy Th, and learned reward function function i E R, from Algoritium 1, with probability 1 - 8, the following error bound is true: Ep.ry [I((T) - -(()]] < HH (H-los( (B 1/m)
Equipped with this result, we can now bound the suboptimal- ity of the learned policy ayb in Algorithm 1. We show that when used with a specific subset of heterogeneous Ty Ty-which are empirically show are representative of real pre-trained LLMs- VB algorithm attains a stronger suboptimality guarantee of H/ H/n, when compared to the best policy म. belonging to the ball, 1l,, around the base policy. In- tuitively, this subset of heterogeneous policies are charac- terized by a condition pertaining to how concentrated or "sharp" is the distribution of rewards induced by sampling
Note that our simple VB method admits no direct depen- dency in ob (base policy's 's heterogeneity), which scales as
6

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
0.90
Teat-tim etfelency
0.75
Tex-sime alficiency
0.90
0.75
Ret-time elficiency
0.80
0.60
42%
0.60
0.65
37%
0.45
0.30
0.30
0.50
233
0.15
Tu(aa)))
(Espart
52 (RL)
4f (SFT)
0.15
T, (Expert)
72 (HL)
of (SFT)
(SFT)
0.00
0.00
0.35
2-
24
2
2
2
2
2
2
21
24
28
21
2F
Horizon H [compute at test-time)
Data budget
Horizon [test compute). data
(a)
(b)
(c)
Figure 4: Contextualized planted subsequence: We setup heterogeneous base policy Th. and induce an expert by rejection sampling correct traces from no. (a) Fixing data size at 2 we scale test compute, training separate SFT. RL policies for each compute budget. (b) For a fixed compute budget of 2 we scale data, and train set of SFT and RL policies for each n. In (a), (b) we find RL scales both data and test-time compute efficiency over SFT. In (c) we scale both test compute and training data and note that the gap between the performance of RL and SFT grows super lincarly, as predicted by our result in Theorem 5.8.
((H) in the worst case. This implies that as long as m. satis- fies Property 5.6 for some hg < H, VB methods only incur suboptimality that scales as (1) when n = S2H)) whereas for any VF method this is 2!( (V)). Mathematically, this is because once Property 5.6 is satisfied for some co at given horizon ho, then it continues to hold for co and A H >> hg- This is consequence of the structure of the bi-level reward as we show in Lemma C.22 in Appendix C.4.
problems). We first note that the performance of the best expert policy मh which belongs the the K x² x2-ball around my will only continue to improve a function of H by solving more questions (i.e., by finding new x where r flips from O to 1). To see why, note that Dx= grows in H meaning that at large H, the expert Rx cannot be simultaneously close to the base policy and maximize reward unless it solves new questions too. Now note that if n = ((H)) samples are used for training, then the VB algorithm attains a suboptimality of ((1) compared this best expert, but the VF algorithm still suffers from a horizon is heterogeneous). This means that if the suboptimality gap with respect to the best expert continues to be (1) as we increase the token budget, then we are solving harder problems, not just being more efficient on easier problems.
Theorem 5.7 (Suboptimality upper bound for VB against any expert). Consider a bi-level reward r, base policy Th that is co co-anticoncentrated at some horizon ho S H. Then, w.p. 1-6, for the policy wyb returned by Algo- rithm 1, the suboptimality gap w.r.l the best expert: axi
suboptimality (if mb
1 H (og((R
J²( - J (+ 27
CO
6. Illustrating Theory in Practice
Overall, Theorem 5.7 implies that if TT covers some correct solution traces for a given prompt, then VB methods can find these traces and minimize suboptimality, whereas VF methods may not be able to discover them and will try to mimic multiple traces, which also naturally increases the chances of failing at the problem. Combining the upper and lower bounds (Theorem 5.7 and 5.4) allows us bound the efficacy of test-time scaling with VB and VF methods.
Our theoretical results in Section 5 show that when the base policy is heterogeneous, VF approaches perform poorly, However, this can still be favorable for VB Algorithm 1, as long the anti-comcentration condition (Property 5.6) holds. We now use didactic setting representative of typical LLM reasoning problems to validate our theoretical results, and study real math reasoning problems in the next section.
Didactic setup. We extend the planted subsequence prob- lem from Sethur et al. (2024b) to a contextual version. Con- cretely, for an input problem response y with Hf tokens is a correct trace if there exists gold contiguous subsequence (g(=1)....g(())))) (xs)) planted in y. Here, the underlying mapping g [10] [30) is fixed but unknown. For a state s =: (x, 41,.., a,), the bi-level reward r(s) = if and only if there exists some //' < h such that the last 5 tokens before ht' match the gold subsequence. To use the same scale compare methods trained for different horizon H values (test-time budget), we JT(TT) and divide it by the maximum reward of H 4. Details in Appendix D.
Theorem 5.8 (Separation between test-time scaling of VB and VF methods). For any heterogeneous Th with ōb
(x1,.., as)), we say that
D H),, and is cu-anticoncentraaee for horizon ho & H. the policy ayb returned by the simple verifier-based Algorithm and #xf returned by any verifier-free method satisfy:
J,(#yb) Jr ( = 52 (4/vm),
which implies our test-fime scaling result in Theorem 5.1.
Takeaways: Verification enables test-time scaling VF suffer when the base policy is heterogeneous. VB outperform any VF algorithm given that the base policy is heterogeneous and the induced reward distribution is anti-concentrated.
Base policy. We wish to construct base policies na that: (i) differ in heterogeneity, and (ii) satisfy the anti-concentration condition. To do so, we finetune GPT2-xl (Radford et al.,
Remark 5.9 (VB methods improve over VF by solving more
7

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Scaling compute
Scaling data
Scaling compute and data (3B)
0.54
0.52
0.40
Venifen-baeed (Bol)
Varifer-feus (SFT)
0.50
8B
0.48
88
Aguuncy
0.
Vorthor free (SF T]
0.44
Verifor free (SFT)
0.37
17%
20%
0.42
Varifio bused (BoN)
0.40
Verifor based [BcN]
0.34
0.38
0.36
3B
6x
3B
8x
0.31
0:34
0.32
Super linear increase in gap
0:30
0.28
0.28
2
2
2
2
2
2
2
2
2
2 2
2 2
test compute (tokknss)
data budggtt (n)
test compute (tokens). n H
(a)
(b)
(C)
Figure 5: Scaling test compute H. and training data n on MATH: We compare two common algorithms for spending test compute: (i) ferifier-free SFT on manually stitched sequential revisions (Qu et al., 2024; Muennighoff ct al., 2025) from an expert, and (ii) BoN (Cobbe al., 2021a) search using verifier trained on base LLM. In (a), scale H, with data size n=2 and find BoN scales test-compute by 8x over SFT. (b), we fix H=2 scale n. and note the 6x gain in sample efficiency for BoN. In (c), we compare RL and SFT following Definition 4.2 where we scale both n and H, and corroborating Theorem 5.8 the gap between RL. and SFT grows super linearly.
2019) on samples obtained from mixture of hand designed "procedural" policies. Inspired from Setlur et al. (2024b), procedural policy (y |s)( 7 when the last k tokens in the state s, match the first & tokens in the gold subsequence y". Thus, the normalized return for ( -1, as 70000. We vary the heterogeneity of my by finetuning GPT2-xI on data from a mixture of procedural policies with 7 E [1000].
edly, we see the performance of both SFT and RL improve, but the slope for the RL curve is much higher than that of SFT, which agrees with our theoretical result on VB being more sample efficient (1/x) than VF 1//o in Theorem 5.4).
Effect of policy heterogeneity. In Figure 4(c), we compare the performance of SFT and RL policies as we reduce the heterogeneity of the base policy. Consistent with our discus- sion in Section 5. the suboptimality gap for SFT reduces with the base policy's 's heterogeneity. In this regime we also find that VF methods outperform VB, primarily because of the decline in verifier accuracy (Appendix D), and perhaps the anti-concentration property is also not satisfied.
Verifier-free SFT & verifier-based RL. Given n prompts, we collect trajectories from expert by running rejection sampling over T.. i.., for each prompt, we sample responses from Ty until a correct trace is sampled. Next, we run SFT on this dataset in a verifier-free manner to obtain nx. similar to Zelikman et al. (2022). For RL, we implement a practical version of Algorithm 1. We train reward model (GPT2-xI) as a multiclass classifier that predicts the bi-level reward over 1 values: O to H. To collect training data, we draw response ~ Tb(- x) for each of the prompts and annotate it tround-truth r(r). Using this, we train a reward model f, and learn policy #yb by running REINFORCE (with a KL constraint) against f (Ahmadian et al., 2024).
7. Results: Large-Scale Math Reasoning
Next, we extend our empirical results to math reasoning problems where we compare VF supervised finetuning on manually stitched search traces, and VB best-of-N search (BoN) (Cobbe et al., 2021b). In BoN, we sample multiple responses from the base LLM, and choose the best one with an outcome verifier trained to predict 0/1 correctness labels. Here, the verifier is trained on n samples generated from the base LLM for questions in the training data. Thus, BoN mimics the first few iterations of VB online RL algorithm, initialized with the base LLM,, and that maximizes rewards from trained verifier. We mainly evaluate performance on the MATH (Hendrycks et al., 2021) reasoning benchmark, and use LLama-3.1133 8B/3B instruct models (Dubey et al., 2024) supervised finetuned on MATH as the base LLMs. We vary the test-time compute budget from 29 to 21 tokens, and also vary the training data budget n from 2 to 26
Results: scaling test-time compute. In Figure 4(a), we compare the test-time efficiency (normalized J,) of SFT and RL as we scale test-time token budget H, fixing 2=210 The performance of any procedural policy (ey improves with H, since there is a greater chance of sampling the gold sub- sequence. A similar argument applies to base and expert policies that are mixtures over (by. But perhaps counterintu- itively, the gap between SFT and expert policy worsens as H increases, matching our result in Theorem 5.4 where the gap grows with H. This is because the heterogeneity of each procedural policy (and hence o7)) scales with H. On the filp side, RL nearly matches the expert (Theorem 5.7 shows suboptimality gap that is independent of ow), until a much higher H, after which it deviates slightly, likely because of decline in verifier accuracy at higher H (Appendix D), resulting in reward hacking (Gao et al., 2023) during RL.
Verifier-free approach: SFT on stitched search traces. Motivated by the approach of scaling test-time compute via iterative revisions (Qu et al., 2024), in this setting, we SFT total test-time budget H on running as many rounds of revision as possible within the budget. To construct SFT data, we follow Snell et al. (2024) and construct an expert policy that is "close" to no by first sampling a bunch of conrect/incorrect solution traces from Tb. and then manually
Scaling data budget. In Figure 4(b), fix the test-time compute to 26 tokens, and scale the data budget n. Expect-
8

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
stitching a uniformly random number of incorrect solutions
Vidie fro
followed by the correct into one search trace.
Wartenbaod
1200
+2.6
berifier-based approach: Best-of-N sampling against a verifier. For each training problem, we collect a given number of traces ~v Tb, and label them with a 0/1 correctness score based on final answer match. We then train a verifier with binary cross-enties cross-entropy loss. On test problem, we use the verifier to rank N solutions from (-]x), at temperature 1.0 and choose the best one (N scales linearly in budget H). While we run online RL in Section 6, due to computational constraints at higher H. we only compare with BoN here, which runs 1-step of policy improvement.
800
Mod High
Avg. hettenggeestyy.c it,
lstelograsity
Figure 7: Heterogeneity hurts SFT, but SFT outperforms BoN on homogeneous problems: Across problems, we plot the distri- bution of 6x (Definition 5.2), bucket problems by heterogeneity, and run SFT, BoN on each bucket. We find that verifier-free SFT can outperform BoN when the heterogeneity measured by dx low, but the opposite true when ox is high.
VB BoN scales compute by 8x, data by 6x of VF SFT. At a fixed data budget of 214 samples, BoN scales test-time compute by 8x over SFT, and a fixed test compute of 2 tokens, VB scales data efficiency by 6x (Figure 5(a) Revisiting Definition 4.2, we scale n with H and analyze the gap between BoN and SFT. We find that the accuracy gap grows super linearly in log H, i.e., the reward gap grows as ((V () (Figure 5(c)), matching Theorem 5.1.
VB BoN, which can suffer from lack of coverage or inaccu- racy of verifier (Appendix E). In contrast, when dx is larger, VB BoN dominates since VF SFT fails to generalize under heterogeneity and mainly memorizes responses. The distri- bution of xx also skewed towards higher values, resulting in VB methods performing better on average (Figure 5).
Hard 0.27-anticoneentrate
Easy (0.26 anticoncenttaae)d]
40
Frequecy
1.00
MATH 590
0.64
20
95
20
0.44
0
300
Reward
Reward
Varte-taa
0.24
Figure 8: Anti-concentration coefficient in practice: For casy and hard problem sets in MATH, we compute the distribution of bi-level rewards on the correct traces sampled from base LLM. We find that for x = 0.5 (controls the x² ball of the expert policy), there is a non-trivial (+s 1/4) probability of observing rewards better than the mean reward by atleast a a/ / (ar computed by aver- aging over prompts in the easy/hard bucket). implying that base policy is roughly 0.25-anti-come concennrnett (Property 5.6).
Dicilitio
0.00
0.14
1054
4006
4235
(slone)
Figure 6: Results with sl: Fixing training data, and scaling test- time compute budget, we compare the performance sl (Muen- nighoff et al., 2025) trained with verifier-free approach: super- vised distillation, and our simple VB method: best-of-N search. In compute matched evaluation, sampling N short responses and selecting the best one with the trained verifier outperforms the budget forcing approach used in Muennighoff' et al. (2025).
Base LLM is anti-concentrated in practice. In Figure 8, we plot the distribution over bi- rewards (Property 4. that measure test-compute scaling, conditioned on correct answers. With k = 0.5, we mark in red the performance needed for trained LLM to improve over any expert in x-x² ball around Ty. On both easy (acc.>0.3) and hard prob- lems
s1 trained with verifier-free distillation performs worse than BoN. In Figure 6, across different test compute bud- gets, we plot the performance of budget forcing in Muen- nighoff et al. (2025), that scales test compute over the s1 model. sl itself was trained by running supervised distilla- tion over traces from the Gemini Thinking (Google, 2024) model in a verifier-free manner. We compare this with BoN, where we sample N responses of length 29 (MATH500) or 210 (AIME) and choose the best one with a trained outcome verifier. In a compute matched evaluation, we find that even when we fix the training data n. the verification based BoN approach improves over budget-constrained sl.
the region beyond the red mark is = 1/4, implying that T. has anti-concentration coefficient of x acc. x 0.25 (Property 5.6). Thus, the VB BoN is able to cover correct answers, which only improves with more test compute. Theorem 5.7 suggests that with H/n samples BoN can outperform a policy that is 17 close to the red mark.
Takeaways: Trends on MATH match our theory,
VF generalizes less heterogeneous problems, but mem- orizes heterogeneous ones. We analyze the performance of running SFT/BoN on different problem buckets, where each bucket consists of problems of low, medium or high value of heterogeneity, at token budget 210 (Figure 7). When ox is small, VF SFT clones the trace well and improves over
Base LLMs (e.g., Llama-3. 3.1--B..B))) 1-8) exhibit hetero- geneous and anticoncentrated reward distributions. VB methods outperform VF for a fixed test com- pute budget and the gap only grows as we increase training data and test budget. Although, when het- erogeneity is indeed low, VF can outperform VB.

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Acknowledgements
that much for 2+ 3=? the overthinking of ol-like Ilms. arXiv preprint arXiv:2412.21187, 2024c.
All experiments in this work were run at Carnegie Mellon University. We thank Max Simchowitz, Andrea Zanette, Yuxiao Qu, Max Sobol Mark, Kwanyoung Park, Matthew Yang. Bhavya Agrawalla, Christina Baek, Charlie Snell, Yifei Zhou, Yi Su, Paria Rashidinejad, Ahmad Beirami and members of the CMU AIRe lab for feedback on an ear- lier version of this paper and informative discussions. AK is thankful for the support from Office of Naval Research under NO0014-244 1-2014-24-22 AS is thankful for the generous support of JP Morgan AI PhD Fellowship. NR is thank- ful for support from NSF Grants IIS-1901252 and CCF- 221 1209. The authors thank the TRC program at Google Cloud and Lambda labs for providing compute resources that supported this work.
Chow, Y., Tennenholtz, G., Gur, I., Zhuang, V., Dai, B., Thiagarajan, S., Boutilier, C.,, Agarwal, R., Kumar, A., and Faust, A. Inference-aware fine-tuning for best-of- n sampling in large language models. arXiv preprint arXiv:2412.15285 2024.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C.,, and Schulman, J. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14166, 2021a.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L.,, Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21
Impact Statement
2021b.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Coste, T., Anwar, U., Kirk, R., and Krueger, D. Reward model ensembles help mitigate overoptimization. In The Twelfth International Conference on Learning Represen- tations, 2024. URL https: openrevieweeeeeeeeeeeeeeee nnt//
References
Daniely, A., Sabato, S., Ben-David, S., and Shalev-Shwartz, S. Multiclass learnability and the erm principle. In Pro- ceedings of the 24th Annual Conference Learning Theory, pp. 207-232. JMLR Workshop and Conference Proceedings, 2011.
Ahmadian, A., Cremer, C., Gallé, M., Fadaee, M., Kreutzer, J. Pietquin, O., Üstün, A., and Hooker, S. Back Revisiting reinforce style optimization for learning from human feedback in llms. arXiv preprint arXiv:2402. 14740, 2024.
to basics:
DeepSeck-AL, Guo, D., Yang, D., Zhang, H., Song. J., Zhang, R., Xu, R., Zhu, Q., Ma, s., Wang, P., Bi, X., Zhang, X., Yu, X., Wu, Y., Wu, Z. F., Gou, Z., Shao, Z., Li, 7.,, Gao, Z., Liu, A., Xue, B., Wang, B., Wu, B., Feng, B.. Lu, C., Zhao, C., Deng, C., Zhang, C.,, Ruan, C., Dai, D., Chen, D., Ji, D., Li, E., Lin, F., Dai, F., Luo, F., Hao, G., Chen, G., Li, G., Zhang, H., Bao, H., Xu, H., Wang, H., Ding, H., Xin, H., Gao. H., Qu, H., Li, H., Guo, J., Li, J., Wang, J., Chen, J., Yuan, J., Qiu, J., Li, J., Cai, L.,, Ni, J.. Liang, J., Chen, J., Dong, K., Hu, K., Gao, K., Guan, K., Huang, K., Yu, K., Wang. L.. Zhang, L., Zhao, L., Wang, L., Zhang, L., Xu, L., Xia, L., Zhang, M., Zhang, M., Tang, M., Li, M., Wang, M., Li, M., Tian, N., Huang, P., Zhang, P., Wang, Q.. Chen, Q., Du, Q. Ge, R., Zhang, R., Pan, R., Wang, R., Chen, R. J., Jin, R. L., Chen, R., Lu, S., Zhou, S., Chen, S., Ye, S. Wang, S., Yu. S., Zhou, S., Pan. S., Li, S. S., Zhou, S. Wu, S., Ye, S., Yun, T., Pei, T., Sun, T., Wang, T., Zeng, W., Zhao, W., Liu, W., Liang, W., Gao, W., Yu, W., Zhang, W., Xiao, W. L., An, W., Liu, X., Wang, X., Chen, X., Nic, X., Cheng, X., Liu, X., Xie, X., Liu, X., Yang, X., Li, X., Su, X., Lin, X., Li, X. Q., Jin, X., Shen, X., Chen, X., Sun, X., Wang, X., Song, X., Zhou, X., Wang, X., Shan, X., Li, Y. K., Wang, Y. Q. Wei, Y. X., Zhang,
Beeching, E., Tunstall, L., and Rush, S. Scaling test- time compute with open models, 2024. URL ht https: //huggingface. wtwsppace////////eeoooooccc...ea Huugg//ggggagggiiiiiaeeee
Bi, X., Chen, D., Chen, G., Chen, S., Dai, D., Deng, C., Ding, H., Dong, K., Du, Q., Fu, Z., et al. Deepseek Ilm: Scaling open-source language models with longtermism. arXiv preprini arXiv:2401.022 002954, 2024.
Chen, H., Waheed, A., Li, X., Wang, Y., Wang, J., Raj, B., and Abdin, M. I. On the diversity of synthetic data and its impact on training large language models. arXiv preprint arXiv:2410. 15226, 2024a.
Chen, L., Davis, J. Q., Hanin, B., Bailis, P., Stoica, I., Za- haria, M., and Zou, J. Are more Ilm calls all you need? towards scaling laws of compound inference systems. 2024b.
arXiv preprint arXiv:2403.0244
Chen, X., Zhang, Y., et al. On bayes risk lower bounds. Journal of Machine Learning Research, 17(218):1-58, 2016.
Chen, X., Xu, J., Liang. T., He, Z., Pang, J., Yu, D., Song,
L., Liu, Q. Zhou, M., Zhang, Z.,, et al. Do not think
10

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Y. Xu, Y., Li, Y., Zhao, Y., Sun, Y., Wang, Y., Yu, Y., Zhang, Y., Shi, Y., Xiong, Y., He, Y., Piao, Y., Wang. Y, Tan, Y., Ma, Y., Liu, Y., Guo, Y., Ou, Y., Wang, Y., Gong,
Hosseini, A., Yuan, X., Malkin, N., Courville, A., Sordoni, A., and Agarwal, R. V-star: Training verifiers for self- taught reasoners, arXiv preprint Se0iv::20020044557 2024.
Y., Zou, Y., He, Y., Xiong, Y., Luo, Y., You. Y., Liu, Y., Zhou, Y., Zhu, Y. X. Xu, Y., Huang, Y., Li, Y., Zheng,
Huang, A., Block, A., Foster, D. J., Rohatgi, D., Zhang, C., Simchowitz, M., Ash, J. T., and Krishnamurthy, A. Self-improvement in language models: The sharpening mechanism. arXiv preprint arXiv:2412.0199.
Y. Zhu, Y., Ma, Y., Tang. Y., Zha, Y., Yan, Y., Ren, Z. Z.,
Ren, Z., Sha, Z., Fu, Z., Xu, Z., Xie, Z., Zhang, Z., Hao,
2024a.
Z. Ma, Z.. Yan, Z., Wu, Z., Gu, Z., Zhu, Z., Liu, Z., Li,
Z., Xie, Z., Song, Z., Pan, Z.., Huang, Z., Xu, Z.,, Zhang, Z. and Zhang, Z. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning, 2025. URL https: / //axivivvv...//// www.iv.ogg/aai.. wwt. awt.aa////00 12948.
Huang, A., Zhan, W., Xie, T., Lee, J. D., Sun, W., Krish- namurthy, A., and Foster, D. J. Correcting the mythos of kl-regularization Direct alignment without overopti- mization via chi- chi-squared preference optimization. arXiv preprint arXiv:2407.13333 2024b.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama herd of models. arXiv preprint Mxxiv:2407.2178. 2024.
Jones, A. L. Scaling scaling laws with board games. arXiv preprint arXiv:2104.0311 2021.
Kang, K., Wallace, E., Tomlin, C., Kumar, A.. and Levine, S. Unfamiliar finetuning examples control how language models hallucinate, 2024.
Erdös, P. On lemma of littlewood and offord. American Mathematical Sociery, 1945.
Kazemnejad, A., Aghajohari, M., Portelance, E., Sordoni, Foster, D. J., Block, A., and Misra, D. Is behavior cloning all you need? understanding horizon in imitation learning. arXiv preprint ar 2rXiv:2407.15007 2024a.
A., Reddy, S., Courville, A., and Roux, N. L. Vineppo: Unlocking potential for IIm reasoning through refined credit assignment. arXiv preprint 1rXiv:2410.01669, 2024.
Foster, J., Han, Y., Qian, J., and Rakhlin, A. Online esti- mation via offline estimation: An information-thhoreet framework, arXiv preprint arXiv:2404. 10122, 2024b.
Kimi-Team. Kimi k1.5: Scaling reinforcement learning with llms, 2025.
Gandhi, K., Lee, D., Grand, G., Liu, M., Cheng, W., Sharma, A., and Goodman, N. D. Stream of search (sos): Learning to search in language. arXiv preprint arXiv:2404.03663, 2024.
Kumar, A., Zhuang, V., Agarwal, R., Su, Y., Co-Reyes, J. D., Singh, A., Baumli, K., Iqbal, S., Bishop, C., Roelofs, R., et al. Training language models to self-correct via reinforcement learning. arXiv preprint arX1v:2409.12917, 2024.
Gao, L., Schulman, J.. and Hilton, J. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pp. 10835- 10866. PMLR, 2023.
Langley, Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference Machine Learning (ICML 2000). pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Google. Gemini 2.0 flash thinking mode. generative- (gemini-2.0-flash-
http:://cloud.goglle wow.gol.o..o/eeeeeeeellllt com/vertex-ai/
ai/docs/thinking--ood 2024.
thinking-exp-1219)..
Lehnert, L., Sukhbaatar, S., Su, D., Zheng, Q., Mcvay, P., Rabbat, M., and Tian, Y. Beyond a Better planning with transformers via search dynamics bootstrapping. arXiv preprint 24Xi 14083, 2024.
Gulcehre, C., Paine, T. L., Srinivasan, S., Konyushkova, K.,
Weerts, I., Sharma, A., Siddhant, A., Ahemn A., Wang, M., Gu, C., Macherey, W., Doucet, A., Firat, O., and de Freitas, N. Reinforced self-training (rest) for language modeling, 2023.
Li, C., Wang, W., Hu, J., Wei, Y., Zheng, N., Hu, H., Zhang, Z., and Peng, H. Common 7b language models already possess strong math capabilities. arXiv preprint arXiv:2403.0447 2024.
Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Measuring math- ematical problem solving with the math dataset. NewrIPS, 2021.
Ling, S. and Xing, C. Coding Theory: A First Course. Cambridge University Press, 2004.
Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D. d. L., Hendricks, L. A., Welbl, J., Clark, A., et al. Training compute-optimal large language models. arXiv preprint arXi: 2022.
Liu, R., Wei, J., Liu, F,, Si, C., Zhang, Y., Rao, J., Zheng, S., Peng, D., Yang, D., Zhou, D., and Dai, A. M. Best prac- tices and lessons learned on synthetic data for language models, 2024.

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Luo, M., Tan, S., Wong, J., Shi, X., Tang, W., Roongta, M., Cai, C., Luo, J., Zhang, T., Li, E., Popa, R. A., and Stoica, I. Deepscaler: Surpassing ol ol-preview with a 1.5b model by scaling rl, 2025. Notion Blog.
Setlur, A., Nagpal, C., Fisch, A., Geng, X., Eisenstein, J., Agarwal, R., Agarwal, A., Berant, J., and Kumar, A. Re- warding progress: Scaling automated process verifiers for Ilm reasoning, arXiv preprint arXiv:2410.081 2024b.
Moon, S., Park, B., and Song, H. O. Guided stream of search: Learning to better search with language models via optimal path guidance. arXiv preprint arXiv:2410.02999, 2024.
Setlur, A., Qu, Y., Yang. M., Zhang, L., Smith, V., and Kumar, A. Optimizing Ilm test-time compute involves solving a meta-rl problem. https: / mm1 cmu. edu, 2025. CMU MLD Blog.
Muennighoff, N., Yang, Z., Shi, W., Li, X. L., Fei-Fei, L.. Hajishirzi, H., Zetrlemoyer, I., Liang, P., Candès, E., and Hashimoto, Т. sl: Simple test-time scaling. arXiv preprint arXiv:2501. 19393, 2025.
Singh, A., Co-Reyes, J. D., Agarwal, R., Anand, A., Patil, P., Garcia, X., Liu, P. J., Harrison, J., Lee, J., Xu, K., et al. Beyond human data: Scaling self-training for problem-solving with language models. arXiv preprint arXiv:2312.0658. 2023.
Nie, A., Su, Y., Chang, B., Lee, J. N., E., Le, Q. and Chen, M. Evolve: Evaluating and optimizing llms for exploration. arXiv preprint arXiv:241000623: 2024.
Snell, C., Lee, J., Xu, K., and Kumar, A. Scaling Ilm test- time compute optimally can be more effective than seal- ing model parameters. arXiv preprint 241::22008003314, 2024.
Polyanskiy, Y. and Wu, Y. Lecture notes on information theory. Lecture Notes for ECE563 (UIUC) and, 6(2012- 2016):7, 2014.
Song, Y., Zhang, H., Eisenach, C.,, Kakade, S., Foster, D., and Ghai, U. Mind the gap: Examining the self- improvement capabilities of large language models. arXiv preprint arXiv:2412.02674 2024.
Qu Y., Zhang, T., Garg, N., and Kumar, A. Recursive introspection: Teaching language model agents how to self-improve. arXiv preprint arXiv:2407.1821 2024.
Radford, A.,
Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Tajwar, F., Singh, A., Sharma, A., Rafailov, R., Schneider, J., Xie, T., Ermon, S.,, Finn, C., and Kumar, A. Preference Fine- Tine-Tuning of LLMss Should Leverage Suboptimal, On- Policy Data, 2024.
Rafailov, R., Sharma, A., Mitchell, E., Ermon, s., Manning, C. D., and Finn, C. Direct preference optimization: Your language model is secretly reward model. arXiv preprint arXiv:2305. 18290, 2023.
Team, O. Open Thoughts. https://ppem-thought.aau Febru- ary 2025.
Tsybakov, A. B. Nonparametric estimators. Introduction Nonparametrie Estimation, pp. 1-76, 2009.
Rajaraman, N., Han, Y., Jiao, J., and Ramchandran, K. Sta- tistical complexity and optimal algorithms for nonlinear ridge bandits. The Annals of Statistics, 226522555-2 2024.
Uesato, J., Kushman, N., Kumar, R., Song, F., Siegel, N., Wang. L., Creswell, A., Irving, G., and Higgins, I. Solv- ing math word problems with process-and outeome-based feedback. arXiv preprint arXiv:2211.14275. 2022.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. Bridging offline reinforcement learning and imi- tation learning: A tale of pessimism. arXiv preprint arXiv:2103.12021, 2021.
Villalobos, P. and Atkinson, D. Trading off pute in training and inference, 2023. URL https://epochai.
Sardana, N., Portes, J., Doubov, S., and Frankle, J. Beyond chinchilla-optimal: Accounting for inference in language model scaling laws. arXiv preprint vrXiv:2401.00445 2023.
and-inference. Accessed, pp. 9-26, 2023.
Villalobos, P., Sevilla, J., Heim, L., Besiroglu, T., Hobbhahn, M., and Ho, A. Will we run out of data? an analysis of the limits scaling datasets in machine learning. arXiv preprint S.Xi:2211.0032.. 2022.
Sel, B., Al-Tawaha, A., Khattar, V., Jia, R.. and Jin, M. Algorithm of thoughts: Enhancing exploration of ideas in large language models. arXiv preprint arXiv:2308. 10379, 2023.
Wainwright, M. J. High-dimensional statistics: A non- asymptotic viewpoint, volume 48, Cambridge University Press, 2019.
Setlur, A., Garg, S., Geng, X., Garg. N., Smith, V., and Kumar, A. RI on incorrect synthetic data scales the effi- ciency of llm math reasoning by eight-fold. arXiv preprint arXiv:2406. /4532, 2024a.
Wang, Z., Zhou, D., Lui, J., and Sun, W. Model-based rl as a minimalist approach to horizon-free and second-order bounds. arXiv preprint arXiv:2408 089944 2024.
12

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Welleck, S., Bertsch, A., Fin M., Schoelkopf, H., Xie, A., Neubig, G., Kulikov, I,, and Harchaoui, Z.. From de- coding meta-generation: Inference-time algorithms for large language models. arXiv preprint arXiv:2406. 2688,8, 2024.
Wu, Y., Sun, Z., Li, S., Welleck, S., and Yang. Y. Infer- ence scaling laws: An empirical analysis of compute- optimal inference for problem-solving with language models. arXiv preprint trXiv:2408.00772 2024.
Xiang, V., Snell, C., Gandhi, K., Albalak, A., Singh, A., Blagden, C., Phung, D., Rafailov, R., Lile, N., Mahan, D., et al. Towards system 2 reasoning in llms: Learning how to think with meta chain-of-though. arXiv preprint arXiv:2501 0066222422...... 2025.
Xie, Y., Goyal, A., Zheng, W., Kan, M.-Y., Lillicrap, T. P., Kawaguchi, K., and Shieh, M. Monte carlo tree search boosts reasoning via iterative preference learning. arXiv preprint ar arXiv:2405.00433 2024.
Yang, A., Yang, B., Hui, B., Zheng, B., Yu, B., Zhou, C., Li, C., Li, C., Liu, D., Huang, F., Dong, G., Wei, H., Lin, H., Tang, J., Wang, J. Yang, J., Tu, J., Zhang. J.. Ma, J., Xu, J., Zhou, J., Bai, J., He, J., Lin, J., Dang, K., Lu, K., Chen, K., Yang, K., Li, M., Xue, M., Ni, N., Zhang, P., Wang, P., Peng, R., Men, R., Gao, R., Lin, R., Wang, S.,
Bai, S. Tan, S., Zhu, T., Li, T., Liu, T., Ge, W., Deng, X., Zhou, X., Ren, X., Zhang, X., Wei, X., Ren, X., Fan, Y., Yao, Y., Zhang, Y., Wan, Y., Chu, Y., Liu, Y., Cui, Z Zhang, Z., and Fan, Z. Qwen2 technical report. arXiv preprint (CIi:2407.1067777 2024.
Yang, M. S., Schuurmans, D., Abbeel, P., and Nachum, O. Chain of thought imitation with procedure cloning. Advances in Neural Information Processing Systems, 35: 36366-36381, 2022.
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, L., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate prob- lem solving with large language models. arXiv preprint 0rXiv:2305.10600 2023.
Yuan, I., Li, W. Chen, H., Cui, G., Ding, N., Zhang, K., Zhou, B., Liu, Z. and Peng, H. Free process rewards without process labels. arXiv preprini arXiv:241.001911, 2024.
Zelikman, E., Wu, Y., Mu, J., and Goodman, N. Star: Boot- strapping reasoning with reasoning, Advances in Neural Information Processing Systems, 15:15476-15488 2022.
Zhang, L., Hosseini, A., Bansal, H., Kazemi, M., Ku- mar, A., and Agarwal, R. Generative verifiers: Re- ward modeling next-token prediction. arXiv preprint 2504500408., 2024.
13

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Appendices
A. Discussion, Conclusion and Limitations.
B. Additional Related Work.
C. Proofs from Section 5.
D. Additional Experiments in the Didactic Setup.
E. Additional Experiments on MATH.
A. Discussion, Limitations, and Future Work
Recent results show that capabilities of foundation models improve as we sample more tokens from them test time. But, this paradigm of scaling test-time compute is only sustainable if there exist learning algorithms that can learn policies, which make efficient use of test-time compute and keep improving we scale test-time budgets. To study this, we first formalize the problem of optimizing sst-time compute efficiency under our bi-level rewards (Property 4.1.. Then, we define what it means to scale test-time compute efficiency asymptotically, mainly when comparing a pair of algorithms (Definition 4.2).
Based on these definitions, we present a novel theoretical study that analyzes two classes of popular algorithms. These algorithms train LLMs to use higher compute budgets test-time, much higher than the length of correct answers for typical problems. Crucially,
separate these classes along the axis of access to reward or verification signals, and find that without access to verification (which can be in the form of 0/1 rewards during training, trained verifiers test-time), the performance of learning algorithms may not scale efficiently to large budgets compares to simple verification- approach. We prove this separation under two conditions on the base pre-trained LLM we start with. In particular, we show that when the base policy is heterogeneous (i.e., conditioned on a problem, the distribution of bi-level rewards has a high variance), no verifier-free learning algorithm can accurately learn any expert in a x² ball around the base policy. While every verifier-free algorithm suffers from a heterogeneous base policy, we show that when the base policy satisfies weak anti-concentration condition: for all problems, the pretrained LLM puts a constant mass on region of rewards, slightly higher than mean performance the problem, then simple verifier-bseed algorithm closely approximate the expert policy, which is supposed to scale well as we scale test-time compute further. We verify that the above conditions of base policy heterogeneity and anti-concentration are satisfied in practice, which neatly ties our theoretical abstractions and results to practical settings and empirical observations. We also compare our theoretical predictions on the gap between VF and VB methods on the MATH and AIME benchmarks (with the si model (Muennighoff et al., 2025) and sequential self-correction model (Snell et al., 2024)), and a didactic setting which allows us to control the heterogeneity explicitly.
analyze is already good enough to
Limitations and future work. In this work, we mainly group algorithms based on whether or not they utilize access to verification signals for learning. Future work should consider building on our analysis to compare verifier-base algorithms that query sparse vs. dense forms of verification, e.g., process- process-based rewards. Theoretically. it would also be interesting to extend our analysis of verifier-based algorithms with bi-level rewards to other classes of reward functions, including generative rewards (Zhang et al., 2024). Finally, since it is very expensive to train LLMs to use long contexts at test-time (> 32k) an analysis of scaling behaviors for RL with outcome, or dense rewards, and other verifier- based approaches would be crucial for making progress in this area. We believe that our analysis could provide certain "intuitions" about how to set up the right problems for such scaling study.
B. Additional Related Work
Scaling test-time compute. Recent works (Sardana et al., 2023; Snell et al., 2024) have shown that scaling test-time compute can improve performance at rate faster than that afforded by traditional approaches of scaling data (Li et al., 2024) or model parameters (Hoffmann et al., 2022), implying that training compute can often be traded off optimally for test-compute (Villalobos & Atkinson, 2023; Jones, 2021). There are two popular ways of spending test compute. First, is to autoregressively sample from the LLM long chainss-ff-thouge Gandhi et al., 2024) or an iterative refinement of answers (Qu et al., 2024; Kumar et al., 2024). Second, is to explicitly implement search procedures (Wu et al., 2024; Beeching et al., 2024) with trained verifiers (Cobbe et al., 202 la; Setlur et al., 2024b). In our work, we empirically show that either of these approaches can scale well, and both theoretically and
that resemble linearized search traces (Yao al., 2023;
14

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
empirically examine a different and critical axis of separating these approaches: access verification during training or inference. Additionally, recent works (Chen et al., 2024e; Setlur al., 2025) raise concerns about the unncessary wastage of test-time compute by sampling overly long responses for even simple questions (Yang al., 2024). In our work, we use "bi-level" reward formulation to capture what it means to efficiently use test-compute, and how to compare the asymptotic compute efficiency of verifier-free and verfier-based algorithms.
Access to verification. We say that a finetuning algorithm has access to verification it directly uses ground truth rewards, e.g., the 0/1 correctness labels on math solutions (Uesato et al., 2022; Bi et al., 2024); if it queries trained verifiers for collecting training data (Hosseini et al., 2024) and running search procedures at test-time (Welleck al., 2024; Chen et al., 2024b; Chow et al., 2024). The former approach of training LLMs to generate long "chains of thought" with final reward on-policy RL (Kimi-Team, 2025; DeepSeek-A Al et al., 2025) has shown impressive gains on reasoning benchmarks. For off-policy RL algorithms (Rafailov et al., 2023; Zelikman et al., 2022; Singh et al.. 2023) that utilize verification, converting the same 0/1 rewards into value function based process verification has been shown to be critical (Setlur et al., 2024a). Apart from these verification can also be generative (Zhang et al., 2024) and implicit (Yuan et al., 2024) where the same LLM is trained to generate and self-verify responses iteratively. In this work, we bucket all the above as verifier-based algorithms, and formally show that the asymptotic performance of this class scales test-compute more efficiently than approaches that do not query any sort of rewards, highlighting the critical role played by access to verification.
Verifier-free algorithms. Multiple works have proposed to scale test-time compute by finetuning pre-trained LLMs on manually stitched search traces (Gandhi et al., 2024; Nie et al., 2024) that all lead to the correct solution. The goal here is to force the LLM to mimic known search procedures like Monte-Carlo tree search (Yang et al., 2022; Xie et al., 2024) or A (Lehnert et al., 2024) on training questions, with the hope that the LLM learns to search for solutions on test problems too (Sel et al., 2023). Crucially these algorithms do not annotate search trajectories in the training data with any reward, and the LLM is forced mimic multipe search traces that are "heterogeneous" in nature, i.e., different traces spending varying number of tokens (for search) to arrive the same final solution. In our work, we analyze how this heterogeneous nature makes it hard for any supervised finetuning algorithm to generalize, resulting in poor test-time scaling law for these, matching observations in practice (Kumar et al., 2024; Xiang et al., 2025).
Formalizing self-improvement in LLMs. Some recent works analyze self-improvement in LLMs under the assumption of a verification verification-geneaation gap (Song et al., 2024), or frame sharpening model confidence (Huang et al., 2024a) as a form of inffompproeeett, where the most likely solution assumed be correct. In contrast, we do not assume that learning to verify is easier than learning to generate the correct trace, but instead show much weaker yet realistic conditions on the pre-trained LLM, where such a gap exists.
C. Proofs from Section 5
C.1. Useful Lemmas
For a pair of probability measures P and Q, we define the total variation distance as Drv = = dQ), and define the >d-vivereence by 2x² (PI(Q) = (dQ-dQ)² P < Q and x2 (PI[Q) = too otherwise. We define the KL divergence by DKL (PI f log (dP)
dQ
if Q and DKL (PIIQ) = too otherwise.
dQ)
Lemma C.1 ((Polyankkiy & Wu, 2014)). The following inequalities hold:
DIv < Dn (P,Q) < 2Dr (P,Q). (m.(P.Q < 2 [ (P+Q))) Q)) s Dna (P,Q).
(P. S V DKL (PIIQ)
Lemma C.2 (Change of measure (Polyanskiy& & Wu, 2014; Foster et al., 2024a)). Let P and Q be probability distributions over a measurable space (), ().). Then for all functions h: y + R,
[E](((Y)] EelA(Y)]] S v Varq [b(Y)] Dx= (PIIQ)
(2-CoM
2 (Ep [12(Y)] + Eg }((()))) (P.(
(HI-CoM)
15

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Lemma C.3 (Total expert heterogeneity). For any policy n, recall the definition of heterogeneity in Definition 5.2. For this definition of heterogeneity the following equivalance to the expected conditional variance of rewards is true:
o Exxx (axxxx()))) [r(r)]-
Proof. Let begin by recalling the definition of o²
2
Bsardt (Var=((sa)) 1Q (Sp, an)l]
Now let us expand ((ew) 1Q (Sh, an)) in the following way.
H r(sh: and)
Var
Sh
k/=h
Vara
r(sh: an) +
r(s aw) Sh.
W/ #=
E
r(sh, an) - (8(8 +
Σ
r(sw,aw) aw)
rssu,
8h
W==h+1
H
Ex
rshh + (=($h+1) - (r() +
Σ Wmm++
r(sn axe) - Vx (sh-1)
H Σ k'
2
En
Q ah) -V +
r(sw, an) - V Vz(Sn+1)
8h
Breaking the above expectation into three terms by expanding the square, note that the third term is zero because, E, (Qr(sn, (S++1) sn] 0, for any state Sn, and in autoregressive MDP with deterministic dynamics,
(sh, an) r(sn, (n) V, (Sx+1);
also for every state Sh. Recall that, here the state S (sn, an). Additionally, we also take the expecation over the state distribution of Sn d... and since the equality is true individually for each value of sh. it also holds under the expectation over Sh. This gives us the following.
H
2
Esg wdk
Ex
r(sh, and + (1h+ (sh)
Σ W M=
r(sw, and - Va (a(+t))
Sh
H Σ
2
EEa vdg
Ex (r(ss, an) + (SN++)1) V (=x)))
+ E,
r(sw, aw) - Vg (sn+1)
5/h
W=h-1
H r(sw, - V (s
+ 2. Es, vdj
Ex [r(sh, an) + (Sh+1)) (s((s))sA] Ex
W=++1
As we noted above, the third term in the summation above is zero. Thus,
H Var Σ W=++1
Bgg -d
Var
r(sk: aw)
Sh
E -d
rssw, and)
8h
Exnndy
[Var [Q+ an ]s|
16

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
H both left and right The above induction is true for all values of h. Now, taking the over h, from sides of the equation and using the definition of o get:
H as)
2 = Rx wdy
Var
Σ A==1
r(sh
81
Recall from Section that the first state 81 is simply the input prompt x. Thus df is indpendent of a and simply the distribution over the input prompts x, which is defined as p. Plugging this into the above equation we get:
0²
Excup
Varx
Σ J=11
r(sh ah) x
Exxx (Var>=z(1x)) [r(r)]]
Lemma C.4. Consider a random variable which is almost surely non-negative and has mean and variance o². For any
0 2 0,
0(u A)
E
$ 202
(2)
o 0A
Proof. Let f()) E
((w-A) 040A
Observe that,
A
0(p - A)A
(((0) E
E
0A
(a + 0A)2
(μ A)A
T0( A)
(0) 2E
2E
(a + 0A)2
(o 0A)3
10 A)A?
(μ A)A(o 0A)
2F
(a + 0A)
(A A)A
2
(a + 0A)$
u(A u)
(A 112
2
+ 2
(c 0A)3
(a + 0A)3
4(A 4)
(A 2
< 20E
+ O0
(a + 0A)3
4(A 4))
26E
+
(a 0A)3
Note that ((AA - 14) and (a + 0A)3 are both increasing functions in A, and therefore,
p(A- -4) 14)
1
E
I 2o [0 40] E
0.
+ 0A)3
(o 0A)S
This results in the upper bound
|| 2. Since f(0) and f'(0) = 0, we have that,
((0) f ("( < 20?
C.2. Lower bound on de: Proof of Lemma 5.3
In this section, we show that for any base policy ma and any expert policy na such that DKL. (TT)( S n.
0² oh - -ov x/2.
17

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Since DKL (-1-)) x-Il-) pointwise, this implies the lower bound on de within the x² ball.
By definition, observe that,
t Ex-pl Var x)) [r(r]]]
Exup [Br, (x) (x) ((((T) [(((() -
Note that the squared Hellinger divergence D satisfies ( S DKL(..) pointwise (cf. Lemma 2.4 in Tsybakov (2009)). With the choice Y = (T, r') in the change-of-measune argument in Equation (H-CoM) of Lemma C.2, h(Y) =
(r(T) - r(r'))² and P denote the distribution over trajectories mp( x) and Q denote the distribution over trajectories induced by Te(- x).
1
(xx0/((T]]] - Var (a (1)I((T)]
S
2 2
(Ep [Y) + Eg [+²(Y)) DEL ((Te: Tell T())
$ 2 V (Er [b)( + BQq [M²(Y)) DEL (TellT))
(3)
where in the last inequality, we use the fact that T. and r' are i.i.d. ~ Te(- x). and likewise To and og are i..dd ~ ms(- x), and the chain rule of KL divergence. What remains is to bound E (x) ((((T) - -(7')) for т Te and π mb. Since (r(r) - r(r)) < almost surely,
(x) - -(())) = 2H (ar
Let's denote A V (1)))(()) and B Va [T()) Combining with Equation (3) and squaring, and denoting DKL (FellT,)- Kx.
(A B)² 2 H
(A B). Kix
2B + Kx H
H²
A
A
B²
B SO
(4)
4
This is quadratic equation in A. Solving, get,
Nx 2
Kx H2 2
Kx Hx H2
>
B +
B+
B2
B
8
8
4
B Kx H2
Fix H2
1-111
H1
8
2
64
2 B H Kxx B/2
where the last inequality uses the subadditivity of the v function. This implies that,
(+x) Var x) [r())) H (kx\2) 2arr/2)aaraaa (xr
Taking an expectation over x ~ p on both sides, and using Jensen's inequality,
o² 2 oh HEXxp [v (arr
> of HV Ex (1i// 2 Rxpp [Var==
oh HHOHK// x/2
Noting that [xxxl[ix] K. Solving for the larger root of the quadratic in Equation (4), we also arrive the upper bound,
H2
A B+ Ky B/2
xH²
o: SoS of + Hob / k/2 +
(5)
4
which follows by taking an expectation over x ~ p.
18

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
The above result tight up to constants. Consider an autoregressive MDP with a single prompt, where picking action ag at time results in hitting bi-level (so, regardless of future actions, reward of is collected at each step) and picking action ai results in reward of 0 forever. picks the first branch with probability p and the second with probability 1 p at t = 1. Then, of = p(1 p) and by scaling p from 0 to 1/2, any 0 S of & H² /4 can be achieved. On the other hand, consider the policy ne which plays dn with probability 0 at 1. Suppose is a constant. Then,
Optimality of Lemma 5.3.
(p- (p-0)²
1 1 2(p - 0) + (p 0)2
(xel(TT))
p
1 1-p
p²
2p8 + 8
(1 - p)² + 20 - p) + 8²
+
1 p
8
8
P
0²
p(1 1 p)
Therefore, choosing 0 = min v kpp(1 p)}. J. we get,
x (Te To) S K
And furthermore that, of = (p- (1 (p H2 and therefore,
o² - of = (p 0)(1 (p - 0)) p(1 - H??
(0 + 6² - H?
when 0 P, we get of 00. 0. When 0 /kp(1 p). this assumed be in the regime 0 > p and so,
0² o s (0 + p0 22²)
5 2 112
where in the last equation we recall the assumption that < 1/2. Plugging in 0 and observing that H HOLVE completes the proof.
C.3. Proof of Theorem 5.4
We will state a slightly more formal version of Theorem 5.4 below in Appendix C.3.3. Prior to this, we introduce some relevant notation necessary to state the main result.
C. MEASURE COMPLEXITY: Li
Consider an arbitrary partitioning of the prompt space X' into is disjoint parts, denoted (X)) Let (x² Ji=1 denote the partitioning of the prompt space which maximizes,
(((&)))) =: min (Ex~ploe.xI(s Xi) K S [A]] and [ 2 k/4}.
(6)
And let L = -((x;)))) Our construction, and lower bounds derived therafter are stated in terms of (XT) and Li We devote the first part of this section toward interpretations of L
Recall that T. = Median((ar.x : x E x)),, T. = Ex=plong.x] and o² = Exxppo2 xd always. Later, we will show that if o² & o for a sufficiently small constant c <> 1, Ti 2 de-
x. We will first show that Li 2 ōe
C.3.2. INTERPRETATIONS OF, AND BOUNDS ON L
Lemma C.5. Consider any 8 < k < / Then, L 2 32 Ce.
Proof. We will prove this statement in two assertions,
19

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
1. When k is power of two, 1///2 2 Li--
2. When k is any power of two, and any k/2 S k S K. Li 2 L4
For subset X S X, define its score s(X) = 1 E X]] Assuming these two assertions, we will prove the main lemma first, and then come back proving them.
Proof of the main lemma. Consider i as the largest power between | and |x|/2. For this choice, consider the partition of X into & sets by choosing the first & parts as singleton sets, consisting of the top k prompts x E X with the highest values of Texx the remaining prompts are distributed among sets in the partition arbitrarily. Notably, the score of each part Xr in this partition satisfies s(t)) 2 Median(fs(fx)) x E H); by implication, for any such value of k.
|
1 2 (Mdiia((ss())) x E x))
Median((=((x))) x E x 16
Median((oex E x
(7)
16
where the last equation uses the fact that p is the uniform distribution over X. Therefore, for any k S we have that L 2 2 1 = 1 Median(foe.a
X)).
32
(x;) Proof of the first assertion. Consider the optimal partition which induces Li. {x] Ji=I, arranged in increasing order of scores. Note then, that L = = s(2)) Consider the partition of X' into k/2 parts, as
k/4
XJUX, ........ K
Since scores are additive, the k/8 parts with the lowest scores must be {xp U 1441) This implies the first assertion.
Proof of the second assertion. Consider the optimal partition which induces Lλ, { By dissolving the bottom k- - k' parts (in terms of score) of (2 ) and merging them with other parts, this results in a partitioning of X such that the sum of W// /4 worst scores of the parts must be at least (k' ///h 2 22/2.
1 Lemma C.6. Suppose of S 20 then o. 2 Jo 2 Te.
Proof. By the Palcy-Zyen Bagmu-Z inequality,
4 5
a²
Pr x~p
dex 2
x
(8)
10
When o² < f0 the LHS is at least 3/5. This means that least 3/22/5 of the prompts satisfy dex 2 Te and so
Median ( x x)) 2 1 -e.
As corollary of this lemma, we have that, Corollary C.7. Under the condition of S (4/3)0?, for every k S |X1/4, we have that L3 2 co for some absolute constant e > 0.
Having introduced these interpretations of Lie. we prove the following instance-dependent lower bound on the suboptimality of any verifier-free algorithm.
C.3.3. LOWER BOUNDS ON VERIFIER-FREI APPROACHES
Below we introduce the class of rewards for which we prove the instance-dependent lower bound Theorem 5.4. Definition C.8 (Half-bi-level rewards). Define the class of half-bi-level rewards, R1/2, as those reward functions such that every trajectory contains a bi-level at or before time t = [H/2]. Namely, for any trajectory (81, a1, ... 8H, aH). r(st. a)) for every 2 [H/2] for any reward r R1/2-
Remark C.9. Although half-bi-level rewards are constrained to have all their bi-levels before time H/2, this does not preclude there from existing policies having high variance under rewards from this class. In particular, there exists a policy and reward r E R1/2 such that x² = H²2 H²/116
20

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Theorem C.10. Suppose [X] 2 16 and choose any 4 S k /2//4. Consider any autoregressive MDP and assume that p= Unif( For any choice of reward r E RR1/2 base policy my and expert policy Te E TT, there exists alternate family of expert policies II' of size [2k/1] and reward class R' C R. (also of the same size), such that,
1. E II' and R',
2. II' " llg. corresponds to a family of feasible expert policies with e' = 3(1 +s) max
Hymmm
H H
min
Here, miin milxxx Tex-
3. For every r' R' and policy o' 11', (1') S of Ho. Essat 2122
4. For any realizable verifter-based based learning algorithm, satisfying 2n II',
max max Pr (J,.(T)) J. (+x)) 2 I (esu))))) 2 1/8 Ell' r'ER
(9)
lT') and assume that is sufficiently large that Esta minxEx / (Te
Here, we define Estat
Proof structure. We define the alternate policy class I1' across Lemma C.14 and Lemma C.15, culminating in Ap- pendix C.3.4. Property 2 (i.e,, II' S ITge) and Property 3 (i.e., the bound on the variance of policies in II' on rewards in R') are established in Lemma C.14.
Remark C.II. The results of (Foster et al., 2024a) establish a similar lower bound for autoregressive MDPs. However their construction specifically assumes, either (i) there is a single prompt, or (ti) the adversary constructing an alternate hard instance can change the initial state distribution p. This follows from the fact that their alternate policy is constructed in a way which does not preserve the initial state distribution of the MDP (cf. Lemma G.1 their paper).
Our lower bound scales with Lī Z Je where ग. Median for. 2024a) hints in the case a single prompt. In general, it turns out that it is not possible to have an instance-dependen lower bound that scales as 22
X)), rather than de, as previous work (Foster et al.,
()))n. There exist a class of MDPs where verifier free approaches achieve an error of O (lo.Vlog([IT]] (T) //n). even under the worst case choice of policy class, and improve over the suggested O(a. (ooo(llo()))))))) instance-dependent error.
Theorem C.12. Consider autoregressive MDP with [A] 2 and H 1. 1. There exists expert policy Te, such that for any policy class II 3 of size [II] 2 20(2)), there exists verifier-free learner such that with probubility at least - 8,
log((UI)
log((II))
(T(T J+(#%) < ① 21..6
Je
rER
n
log(IIT)
log( log((1]) [T])
a x
+
Vixi
n
n
as long as 5 2 |x0 exp( /2///x)
Proof: WLOG, assume A = {0, 1}. Consider the following expert: for the tth prompt, arranged in arbitrary order, let Te(1 (1()),,) 2. Observe that,
8. 0 (
(log( [og((x)))
0. Eploaxxl S <E.Iv Tz (1|x)
1
0. / Eplo2xx 2 V
B
2 2
21

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
For each action, construct the empirical distribution estimator,, and return this policy (0/x). Then, with probability least 1 5, conditioning the number of samples fx observed with prompt
(0/x) (0/x) S min { 1,
{
Te To x) (2g()/6)
1og(2/5)
1x
Y1x
Therefore, with probability at least 1 - 5,
max (TT) - - ) rER
B, [rTv
Tee Te(0
1og(2)X1/0)
log(2/0)
S Ep
1.
(10)
nx
Rx
With probability - 6, we have that nxx by union bounding. we have that with probability at least 6, for x E X, nix 2 with probability at least 26,
2
[
10
[
a
log(1/6) for every x E X. Assuming 2 expe V//
a
Combining with Equation (10),
2|²7
(0(x)) log( 12g(2/0)
max Jr(TT) (r 2
rER
n n
xE
log( (og((>11/8)
| log(2/6)
< 2 10x(1211))
+ 2
n||x1|
log( log( (TI log(1X(/0)
2 log (2/()
27.
n
where the last inequality uses the fact that [II| > 20((2()) and by construction, the value of ōe.
Lemma C.13. For any reward r E R1,2, there exists another reward 7 E R such that, for any policy Il and input distribution p.
[r,)]((T]] = H ((T) = Var [((T]
Proof. Consider the bi-level reward and consider the set of minimal states: UrE.4 fsg- where t* min(1 S H ((8-1100)) > r8))-2,4,11). These are the states where a bi-level may be first visited. For each such minimal state, the bi-level property implies that any trajectory which visits this state collects a reward of at every point in time regardless of the sequence of actions played. Based on this construction, we define the reward 7 as follows: for every minimal state which appears at time t, consider the subtree rooted at this node (i.c., the set of trajectories which visit this state). Delete this minimal state, and replace by the set of all H new minimal states corresponding to the set of all states the subtree at depth H t. Let 7 be induced by this new of minimal states; moreover, is feasible to construct this set because of the assumption that E R1/2: every minimal state appears some value of t H/2.
Consider any trajectory Suppose this trajectory visits bi-level at time t < H/2. Now the same trajectory is guaranteed to visit a bi-level at time H - - 2 H/2. Thus, F(r) = H r(T), and the assertions about Ep.-(((T) and Var [(T)] follow suit.
Lemma C.14. For any policy n and reward r, and S { S minxex [[..(.. there exists class 2f 2 policies, IT {Tx : {0, 13ab indexed by binary vectors, and class 2 rewards indexed similarly R2 frz z {0,
such that,
1. For any z, E (0,, 13 D&a (T=]( S 8E. Furthermore, Dya (Tz]| S 8E.
22

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
2. Jr2 (TTz) Jr. (Tz) V T(2 + z((x)) ExxpleexI(xx EX))
3. For every reward r' E R2 and every n' E l oe ('x('', r²) S dxx + Ho,.VE H2
4. Recall that Te E L1g, the e-radius KL ball around Tb. Then, every T' E 11g belongs in the ball 1lgs where,
VEH min
= 3(1 max
max
(11)
o min
and where min mitlxex de
Proof. The policy Tx is defined as follows. For each E [Rt] and x E X,
(T(x)) & (Dex + (xr(())= [e(T(x),
if otherwise.
(12)
where 8x 2 0 is parameter to be determined later. Likewise, the reward is defined as follows. For each x E X,
r(r), i =1 f(F[x), otherwise.
r= (r(x)) x
(13)
where F is the reward defined in Lemma C.13. Since we only care about values and variances, for all intents and purposes, F the same as (which itself may not be a bi-level reward).
Assertion 1: Bounding the x divvergen between тæ and Tzr. Consider any pair of binary vectors 2, x' e 10, z; z,. then Dy² (Tz (T=(-1x)) (+ (-1x)) for any x E X. Otherwise, if z; = and z/ O, for any x E X.
2 (T= (-xx)]| (1xx) D,² (Tz (-(xx)]]
E3 [6 x + 0x (xr(T))2(x)
E., [Te,x + fx |x|²
dex - 20x0 (Tclx) + (T.(()(T)))))) + +x2x) -1
(oe + (x)
o202
(oex + (Te
(14)
where the last equation follows by choosing 6x such that 0x VE(gex (TT There will always exist feasible choice of 0x > 0 satisifying this equation as long as the condition VE S Jx xx) is satisfied, and under the
stronger restriction V S xexx (exx//J/(TTTxx we will have that 0x s 2VE. On the other hand, if 2xx) = 0 and z'(x) 1, for any x E X,
xxo (T= (T=(-1x)) ((xx)|==>(((11)))) Dxa (Ne
1
E 1oe.x - 0xr (x)(TT)(]] [x] EE,r
Tex + (xT(T)
x
Oex - Jx (Te (x)
En
x
Tex + 0x (T)
(x((((Te())) [x) - r(7))
Ez
x
Tex + 0x)(T)
(8)
< 20
< 88
(15)
where (1) follows from Lemma C.4 and the last inequality relies on the choice of 0g < 2VE. Combining Equations (14) and (15) with an expectation over ~ results proof of the first assertion.
23

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Assertion 2: Bounding the value gap. Observe that [ - (TTz xx for any x E if 2/.. In 2; 1
and z = 0 and any Nr r=(r)= r(r) for any which visits and,
By Bx(oer(T) (x(r(T)) Jrz (Te|x)
Jr. (Tx Jrz (xxx
Be( (xr(T)|x
(Te xx) + 0x ( + (
(Te
Jex + 0
0xo2 CX
Te + (
= E
(16)
where the last equation follows by choice 8x. When 2; and z 1, the same analysis results the same bound [x(x=[x) (T x) V for any E Nr and taking an expectation over p proves the second assertion.
Assertion 3: Bound on variance of -.. This follows from Equation (5), which bounds the variance of policy which lies within a radius k x² ball of another: in particular, T= (-Ix) lies in a {-sized KL ball around me(-)x), which has variance o x and taking an expectation over x Note also that the reward r= preserves variances across policies compared to r (cf. Lemma C.13 3 and the fact that Tz uses either or 7), so suffices to carry out the variance computation under r.
Assertion 4: Bound on Dx² (T||<T) for æ E TT. For any z E {0, 1} note that Tz and ne have density ratio upper bounded by,
(T x) Tee (T(x)
Oex + 0x
Tex + 8x (Te (x)
S + 2 2VHH
miin
This upper bound on the density ratio implies that,
Dx2 (T (b))
Ex~o
[Dx² (TT (+xx) (+xx)][[T[[[[]
S 2VEH
2
(1 + Dx² (Te
Omin
VEH EH?
S 3(1 + B) max
Omin
o
Lemma C.15. There exists subset Z C 10 with |Z| [2 and such that every pair z, z, Z satisfies,
Ilz, x1) > k/4
Proof. This statement essentially follows from the Gilbert- Sireert-varsamov bound (cf. Theorem 5.2.6 in (Ling & Xing, 2004)).
C.3.4. CONSTRUCTION OF POLICY CLASS II' AND REWARD CLASS R'
Consider the set of policies IT' = { z E 2} C 1T and R' = frx 2 E 2} (see the proof of Lemma C.14 for a definition of n2, IIg and R2). By Lemma C.15, [IT' x 2k/4 and furthermore, for any z, E Z,
J, (Tz) (TT) LAVE
(17)
z' where LŽ is defined in Equation (6). This bound follows from the first assertion in Lemma C.14 and the fact that x and differ at least k/4 coordinates; Lg. by definition, captures the deviation for the worst-case choice k/4 coordinates.
24

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Definition C.16 (CChen et al., 2016; Rajaraman al., 2024)). The -iinforrmttivt defined as,
xxa (x; - inf x² (Pxy Px x Qy)
Qy
Theorem C.17. Consider the family of policies II' defined above. Let piv denote the uniform prior over them (alternately, the distribution Tz for Unift 2)). Let the policy ît be constructed via dataset D and assume that the verifier-free learner is realizable, satisfying nn E I.. Then,
Pr(Jr. (T²) (+ L1 12VE)2 21 IT'] ( +1
Proof. Let P be the joint distribution of & and D. Let Q be the distribution Unif(Z) x Qdata for a generic (arbitrary) data distribution Qdaa- Let T (z, D) + [[Jr, (m²) - Jr. ( 2 LEVE) be a generic map, and P o T and Q o T be the pushforward measures of P and Q by T. Letting {z, D) [Jr, (TI² Jr, (# 2 LEVE)), the data-processing inequality gives,
De (PIl)) 2 Dx² (P 1
Q(E(2, D)))
(18)
Q(E(Z, D))(1 Q(E(2, D)))
Let us assume that the learner's policy Ā is realizable, and satisfies स E 11'. By the product structure of Q, we have that,
1
((E < sup Pr (Tx) Jr. (T) La LEVE)
II'
where the last inequality uses the fact that for any x' # 2, Jr. (Tx) Jrs (Tx) ) 2 LA V (ef. Equation (17)). Combining with Equation (18), rearranging, simplifying and taking the infimum over Quau completes the proof.
Lemma C.18. Consider any realizable verifier-free learner, satisfying A% E IT'. Then,
log((1r) 16n
1
Pr Jr. (T²) Jr. (+7) 2 1x
2
4
Proof. Observe that,
/ (pn(TT))) (IITED T (T)
(); +1 inf Qum
dDdr
PTI( ) (D)
Prr (TT2) (IITED TT(T))
dDdm
1IrE (T)
/ (T((TT) (IIreD Tx (IIFEDT=(TT))
dDdd
ITED (T(
Erapp [[1 Dx² (T (T=)(
(1) 1 8E)
where in (1) we choose Qdata as the data distribution realized by me and in (ii), we use the first assertion of Lemma C. 14.
IT'
Choose Estat
we get,
16n
log (T'(
Pr
Jr. JTz(Tz) ( < L
2 4
n
25

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
C.4. Bounding the performance of Algorithm 1
C.4.1. UNDERSTANDING THE ANTI-CONCENTRATION ASSUMPTION
Recall that the anticoncentration assumption controls the probability the reward r(r) for no(-(x) of exceeding its mean by margin of Ve times its standard deviation. Namely,
(x(E) =: ( (r(T) 2 En, [r(r)] ObxVE).
The interpretation of (e) is natural, as prompt-conditional measure of anticoncentration of the rewards r(r) collected by the base policy. However, as we discuss in the next lemma, the deviation term Ex,(-Ix [r(r]] + ob. serves a dual purpose: precisely captures the maximum value achievable in a x² ball around T. of radius E.
Lemma C.19 (Characterizing the optimal value within the x² ball). For single prompt E X, consider the set of policies (x(x))) S {.). Then,
Tx = { xx (M(+|s) (((-)ss((((((
sup E bx 2 Bes((bol((T] ob.VE. T
(19)
2 Furthermore, as long as E S x)) this inequality an equality.
Proof. Consider the candidate policy T(Flx) x (ob,x + (r(T)) for @ be chosen later. Mirroring the calculation in Equation (14) (with ne replaced by ma), see that,
02o
xxo (x(()x)]lmo(xxxx) = (ob, + OJ, (T)
of
The maximum achievable value of the x² divergence by this policy is (J,(+)))))= Equation (16),
Likewise, mirroring the calculation in
O07
[x(T/x) - (x( Ox + (J,(TT obx Dx² (T(1 = ob.VE
Therefore, with the appropriate choice of 0, this policy a feasible policy achieving the supremum the statement, What remains show that the supremum can larger. By Lemma C.2, with the choice of Y r((), as the distribution over induced by (-(xx (x) and Q the distribution over trajectories induced by To(-(x). Then,
E (x0 - EE x) [r(())] s / (arr D2a (1(-1)) = .b.VV
This shows that the supremizing value is exactly Vb.
Property C.20 (Regularity). Assume that for each x E X that Jr (TT xx)] > and,
oi (J, (J+
Ex =: Dya (7x((xx]lmm((xxx)
where 7e is any policy which collects the maximum value, while remaining within IIg-
Lemma C.21. Suppose my is cy ag-anticomcentrated for some problem horizon hg and assume that Property C.20 holds tue for the base policy at this value of ho, Define collection of parameters, {>x X3 where R. 3 xx (0, σb 2/) Then, there exists policy he such that,
1. Almost surely, r(r) > for 7 ~ Tel. x) and any x E X.
2. Ne is no worse than we. Namely, Jr(me) 2 sup JA(T) 2 (T()).
(r(x) S c -1
3. For every x E X, sup,, (7|x)> [T(x(
26

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Proof. Fix a prompt x X. We will construct Fe separately for each prompt and later argue about each of these three assertions. Since тe is eg-anticoncentrated for some problem horizon ha, long 6x =: Dx2 (7x (-1x)) s di
(I.())))) by Lemma C.19, defining T as the set of trajectories (r(r) 2 suPreTlex. (xxx))))((7]] Then,
Pr (T T) 2 co (-
(20)
Consider the policy T-(xx) which is the mixture over the trajectories T = :T:T) 2 (1)]((())[((T]) + b. Pbxx/xx with mixture weights Wr x PT..(-Ix) (7). Since the MDP is autoregressive (i.e., tree-like), ==(-(x) corresponds to a simple policy (as opposed to a mixture over policies), since two trajectories in T can not visit the same state again after different action played between them, i.e., breakpoint. This implies that the mixture these two trajectories the same as the policies which agrees with them until the breakpoint and picks one of the trajectories follow the breakpoint, proportional its weight. The same argument applies when considering mixture more than two trajectories. Next, prove the three assertions of this lemma.
(-(+(x) is only supported trajectories which collect rewards which exceed suprell.u.x E--r(-)>)) [r()] 2 (E (r])) By Property C.20, we have that (E)-)o()))) [r(r]] > 0; this implies that the reward collected by every such trajectory is not only strictly positive, but must at least (by the bi-level property of the rewards).
Assertion 1: Rewards are strietly positive.
Assertion 2: Value bound.
Te(-Ix) supported on trajectories which collect reward at least:
sup =ellxxi
Thus, with probability 1, for any trajectory t sampled from Te(+ r(T) 2 supxell. Ex-x(1xx [r(r)] Taking an expectation over 7 ~ Te(-Ix), we get, E8 (1x) 2 sup (r Further, taking an expectation over x P.
Ep. [r(T)] 2 Exup
sup Ex-A)))(((] rElla
2
sup
[p,(((r)]
x fxx xxxx
sup [r((r(r]] sell.
where the last equation follows by definition of ex (cf. Property C.20).
Assertion 3: Bounds on coverage. support of (-(x).
Note that Te(+(x) the policy Erer wr In particular, for any trajectory in the
Proc (T|x)
Wr
(21)
Pro, (7|x)
P-
ETEr (raa(1xs)T))
where the last equation follows by definition of w., By Equation (20), Erer PI co. This completes the proof of the last assertion.
Lemma C.22. Suppose my is Co ca-antcomnenttatee for some problem horizon bo and assume that Property C.20 holds true for the base policy To this value of he- Consider the policy ne introduced in Lemma C.21 this value be For any horizon H >> ha, there exists policy H. which satisfies essentially the same conditions,
1. Almost surely, r(7) 0 for xc(. for any x E X,
2. Re is no worse than ne when deployed on horizon H. Namely, J (Fo) 2 supnemg J (T) 2 J (Te).
3. supr:Prr, (r|x)0 (rn,((
(Txx x) < co
27

---

Below, we provide implementation details of Algorithm 1 and slightly more formal version of Theorem 5.7. We will define the confidence set ft below, and choose appropriately as any upper bound to Est," (5) (see Equation (22)). One such upper bound is provided in Lemma C.25. For the purpose of this section, we will assume that Algorithm 1 carries Scaling Test-Time Compute Without Verification or RL is Suboptimal
Here, we point out that the in the third assertion (coverage), (a) Irajectories are of length H. and (b) the variance term (b(ho) that appears is that of the base policy evaluated on the horizon ha- Everywhere, we take care superscript J, and 11g to indicate the horizon over which the policies are considered.
Proof. Consider the "extension" of Te, defined till time ho. by mi (which we assume is defined for every t E N). Namely, consider the policy ne which follows He till time hg and plays actions according to TT thereon.
The first three assertions follow from the fact that ne is only supported on trajectories with strictly positive reward. By the bi-level property, each of these trajectories collect unit of reward at every > hg- Thus, J," (fe) J (#c) + (H ho), while ееР J.H (T)) S = J (T) + (H - ho). This follows from the fact that the supremizing policy for the H horizon problem can be truncated to the first hg steps to result in a candidate policy in o in the process the value of the policy decreases by most he. The last assertion follows from the fact that 7, and Ty agree after time hg. so the worst-case density ratio cannot increase as increases beyond hy-
C.4.2. ANALYSIS OF ALGORITHM 1: PROOF OF THEOREM 5.7
out least square estimation with respect to some reward class R.b such that r belongs to this class, and may be a subset or superset of the set of all bi-level rewards, R.
Theorem C.23 (Formal version of Theorem 5.7). Consider a bi-level reward base policy Th that is ca-anticonnenttrated at some horizon ho S. H and assume that Property C.20 is satisfied at ho. Suppose the verifier is used to label the cunulative reward of every trajectory and results in a dataset of noisy reward annotations, {(x,, Ts. )=) assume that the reward annotations are of the form Yj- = r(T:)) ) + Zz where the 7 's are independent and standard normal with trajectory level variance Var[Z,] S o mose Then, the policy ayb returned by Algorithum 1, the suboptimality gap w.t.. the best expert
Th E II satisfies: with probability 1- 8,
(H + +o log( (Ralf8)
(ma)) - (t x
TCO
With independent O(1)-variance noise at steps of a trajectory, note that o2 noise S O(H).
Below we instantiate the confidence set Ry Algorithm 1. Recall that we assume that Algorithm carries out least square estimation with respect some reward class Rab: with As the least squares estimator,
1 (1)(())) - vi)²
fss x inf
E' n i=1
R, r' E Rub
(r( -
n i=1
R, (round((r())) :T E R
Where rr())(r(-)) is the "rounding" of the reward r, for every т, r(T) is rounded to the nearest integer, breaking ties arbitrarily. We define the offline estimation error of the least-squares estimator below. Define &g as the event,
((a(T))-(TT)) < Est Off (8)
(22)
And suppose Pr(Es) 2 1 1-6 where the probability computed over the randomness of the training dataset [(x; 7:) The analysis of the verifier-based learner in Algorithm follows the standard analysis of pessimism- based algorithms. For
28

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
arbitrary comparator policy Ne.
Jx(Te)- J, Jr(eT))
min Jr J+(An)) FER,
min Jr Ji( FEll S sup Bp... [|((T) - f(T) fell,
$ Jr(TT)
(23)
With the choice of the comparator policy me c., defined in Lemma C.22,
sup (x) - J. ( S sup co B,,,, (I(()) - -(())) rell.
FER,
where note that the base policy is assumed to be eo-anticoncentrated for the horizon fg. The performance of the algorithm thus relies on establishing a generalization bound for the reward estimation problem, which proved below in Theorem C.24. In conjunction, this results the upper bound: with probability
(H + mise) log RRl/6)
sup J, SO
xell.
Cy
Theorem C.24. Recall that the reward annotations are of the form y = r(T)) Ze where the noise Zς is assumed be independent and standard normal with trajectory level variance onoise Consider any 5 E (0, 1). Then, with probability 1 8, simultaneously for all r' Ray
E (p. ( @noise) (Roo(()))/))
n
Note that with independent noise at each step, noise S O(H.
Proof. This result is a direct combination of Lemmas C.25 and C.27.
Lemma C.25 (Lemma C.I in (Foster al., 2024b)). It suffices to choose,
8 noise log [R /8)
Est (8)
(24)
n
to guarantee that Pr(Es) 2 2 - 5.
Lemma C.26. With the choice 7 = Est (6)), under the event Es, r E R.. Under the same event, for every reward e Ro,
(((T)) ( S 16 00
Proof. The first assertion follows by definition of R, and Equation (22), and the fact that is bi-level reward, so is unperturbed by the round(-) operation. For the second assertion: under Eg, for any reward E Ry.
1 (r((T)) r(7))
2 (r())) - 2 + (r(r.) (T((T)))) < ot n
(25)
Consider the n = round(r")) E Ry, for this choice of reward, observe that >"(r) - r(r) E Z, since both rewards only take integer values. Furthermore, (a) if (T()) r(7) < 1/2, then we know that ((()) r(7) = surely, and (b)
29

---

Scaling Test- Time Compute Without Verification or RL is Suboptimal
(r(T)) r(r) 2 1/2, then (r) - r(r)) This implies,
-(+))
- r(t)) ((0()))))-000() 1/22)
1 Σ
(r((7) - -(()) -(())))) (r))) > 1/2)
1(1(((7) -(r) > 1/2)
$ 16 Est (8)
where the last inequality follows from Equation (25).
C.4.3. PROOF OF PROPOSITION 5.5
Lemma C.27 (Generalization bound for learning in Li-eroor). With probability 1 - 28, simultaneously for all r' e Ryy
E (rm) - r(())]] < so log /b) + Es (6)
Proof. For any fixed reward r' E Ryh. by Bernstein concentration, with probability 2 - 6,
- -
Varp [|(()) - (T](T] log(1/8 1/8)
Ep. (p.m
B Bpmr((((T)) (T)) log(1/5)
H Bp [|((T] (r)) log(4/)
Union bounding over rewards in Ryb, and choosing an arbitrary
E Ry by Lemma C.26, with probability 2 1 26,
E P. (r(()) s 16 (5) H E p. [r(T] ( r'()]] logg RRul/5)
7
Solving the quadratic equation results in the upper bound: with probability 2 - -22
Hllog( (..((1.o1/5))) + Est Off (8)
Wr' E Ryy Ep.mo1r(6 (()]) 5o
7
72
C.5. Weakening the notion of anti-concentration
The notion of anti-concentration consider can be weakened to accommodate "average-case" notions of anti-concentration at the cost of a slightly weaker dependency of the reward gap, as function of n. In particular, using Hölder's 's inequality we may show that,
sup J,(m) J. < [2(1/2]1/
p 2 2.
(26)
1-1p/2
rEll.
This change is purely analytical, and does not require any modification to the algorithm. In comparison, our current result shows the bound:
H n
sup J,(T) - ), < ||1/cxl|o
(27)
30

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
which corresponds letting p - oo in Equation (26). The result in Equation (26) has an improved dependency on the individual unti-concentration parameters, Cx, and longer depends the smallest value, but this comes the cost of worse dependency In particular, with p 3. get bound of the form:
H
sup (x - < Ex 1/c tENT,
1/22/
1/3
(28)
n2/3"
For any constant p strictly greater than 2, say 2 + the verifier based bound decays H/n which is strictly faster than the H/ /n rate exhibited by SFT. In particular, this results in the same conclusion as Theorem 5.8 in the current paper: the advantage now, is that the bound depends on a weaker notion of anti-concentration than the worst case bound considered in the paper.
C.6. Proof of Theorem 5.8
The proof of this result follows directly from the instance lower bound in Theorem 5,4 and suboptimality upper bound result in Theorem 5.7. When, 0B = S2(H), the lower bound on the suboptimality gap of any VF method scales as log()))/,, with respect to any expert in ((1-xx² ball around the base policy To. where as my is co anti-concentrated, then there exists an algorithm that yields an upper bound on the suboptimality gap of H log RRI/n, with constant probability. Thus, in compliance with the definition of scaling test-time compute in Definition 4.2, as we scale SHH), get the result in Theorem 5.1.
As example of such To. consider single prompt, and a base policy that gets reward of 1 with probability > &h on any trajectory rolled out till horizon H = Ho, and that this mass remains constant as we scale H - oc, i.e., the fraction of in correct trajectories (in the set SH,) remain incorrect no matter how much we rollout Tg. For this distribution, it is easy to see that d6 = 2 H), but is 0.5-anti-concentrated.
C.7. Analyzing Verifier Accuracy Under 0/1 Loss
Consider the following modified version of Algorithm 1.
Algorithm 2 Simple Verifier-Based Algorithm with fo/1 loss
Require: Base policy Tp, dataset {(x;, T=) of prompts x, ~ P and traces T; ~ Tb(. x). For every 7; annotate (x,, 75) with bi-level reward r(Ti).
2: Learn set of classifiers Ry C R that are 7-optimal, i.e,,
R R.= fr' r' E R n E" (o)((r())) s7 $n)
3: Return any optimal pessimistic verifier- verifier-based policy,
vb arg max min J+ sEll ref,
Proposition C.28 (Verifier accuracy). For any bi-level reward r, base policy Th, there exists an algorithm querying the at most reward annotator times to learn è R, w.p. 1-8. 8. Ö, loog( RR)6)) log H Yaar-
E (o/l(
In Algorithm 1, setting 7 Yinas E R. w.p. 2 1 5.
Definition C.29 (Graph dimension). Let H be a hypothesis class on an input space X' and label space V. Let S C X. The class H. is said to G-shatter S if there exists an f S + y such that for every T C S, there is a g E H. such that Vr E T, (x)) = f(x), and Ya E S \ T, g(x) + f(x). The graph dimension of H. denoted do(H), is the maximal cardinality of a set that is G-shattered by H.
Theorem C.30 (Sample complexity of multiclass classification (Daniely al., 2011)), There exists an absolute constant
31

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
O such that for every hypothesis class H. given a H-realizable i..dd dataset D of size nle), where,
n(e) c (do(H) log(1 1/6) 1og(1/0))
(29)
empirical risk minimization on D with the hypothesis class H. incurs 0-1 loss of at most E with probability at least 8. Lemma C.31 (Upper bound on the graph dimension), For any hypothesis class H. dG(H) & log2((?()..
Proof. For set S S X' to be G-shattered by H. if there exists a function f such that for any subset T S S there exists an discriminator 9T E H that agrees with f on T and disagrees with it on S \ T. Across different choices of the subset T - S, the discriminating gr cannot be the same: indeed for Ti # T2 S S, 9T, and 97, must disagree on points in (Ti \ T2) U (I2) Ti), the symmetric difference of the two subsets. This is simply because on points in Tj \ Tz. 9r, agrees with f and 9Ts disagrees with f, while on points T2 T1 9T, agrees with f and 9r, disagrees with f. Since the map T 9r is injective, and there are 2| choices of T, this means that S can only be G-shattered if [H] 2 2
Theorem C.32. Given dataset of n(e) trajectories from To, there exists algorithm which calls the verifier (cc) [)] times and learns a reward model such that,
E p.m. [T((T)) f(T)) Se.
(30)
Proof. Recall that R is assumed to be a bi-level reward class. For each r R, consider the multiclass classifier f. (8 A) + I + 1] which maps a trajectory T {(5), (1s1,a))..... a1). (sH, ax)} the value of h E [H] such that the first point in the trajectory where r(sh, 0n.) 1, i.e., the location of the bi-level in the trajectory. If the reward stays 0 entirely through the trajectory, then [r(r) H + 1. First, we relate the 0-1 error of a reward estimator ř to the multiclass classification error of fr, assuming the labels come from fr. Observe that,
Ep [U(((T) # f(T)) S Ep.,, [U(((T)) + fr(T))]
(31)
This follows from the fact that, if r() A f(T), then the li-le in this trajectory is identified incorrectly, implying that fT(T) # f+()). Recall that the expert dataset is composed of n ne()) trajectorics D = {(x, rT)) for some >> 0 (see Equation (29) for the definition of n())). Using the verifier to annotate rewards, by binary searching, the location of the bi-level in any of these n trajectories may be located: thus with n [log2(H) calls to the verifier, a dataset of n examples may be constructed of the form {(T;, f- (T))) ! for the ground truth reward r. By carrying out empirical risk minimization over the hypothesis class F = (s+ r R} to learn a hypothesis f. and invoking Theorem C.30, with probability 2 1 6,
E E [(F((T) f(7)) se.
(32)
C.8. Proof of Theorem 5.4 for the single problem instance
This result follows using a similar approach as the instance-dependent lower bound against behavior cloning proved in (Foster al., 2024a). For the case, where have single prompt x, the following lemma to argue that given an expert policy Ne, we can always construct another policy म.. and a pair of rewards {r, f} that satisfy certain properties, while ensuring that each policy observes a variance of o² in the range (0, H²/4] /4] for either of the rewards.
Next, we consider the following incquality, which holds for any > 0:
min max max (J. 2 A 2 min max (1())))))(()) 2 A]. Aig #E (E()))
Alg =E(
Here, (T) denotes the expected reward under the reward function r, and for convenience, we abbreviate J(TT) = J, going forward. Let Pa represent the probability distribution of the offline imitation learning dataset when the data is collected under policy π. By choosing [J(xe)-J(ãe) and applying the standard Le Cam two-point argument, we can conclude that:
2
32

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
max {Pä J(E)) AP
A]}
bounded below by:
(1 P [[((e) - J(#) < P [J( J( 2 Al)
This, in turn, is further bounded below by:
(1 Ph- (J
2 A F [ ((+) 2 A])
and by standard application of the data processing inequality for the total variation distance, have:
(1 - DTv PT ):
2
Utilizing the tensorization property of the Hellinger distance (Wainwright, 2019), we further lower bound this by:
1 (1 1 Du (Pro, P&.)
Next, we proceed to show the following key inequality:
War (e) sup ([](m)-J(( [ Dr (P"r PT)) {²) 2(1 V oo E2,
for any e >> 0 sufficiently small. The final result follows by setting g² +T and defining:
म. arg max {1](m) [[Te]] Du (P*,, s =²}
To prove this, we invoke the following technical lemma:
Lemma C.33 (Lemma G.1 in Foster al. (2024a)). For any distribution Q and any function h satisfying [h] R almost surely, holds that for all < E² <
[Mr there exists a distribution IP such that:
412
1. EM[M] 2 /Vrrehl...
2 2-3
2. (QIIP) S..
In the case of stochastic policies π in the autoregressive Markov Decision Process M these policies are equivalent to defining arbitrary joint distributions over the sequence (aI...., aH) using Bayes' rule. Consequently, since (
Σ H S== The Lemma C.33 ensures that for any e² Va E rh there exists policy मe such that:
ET
1R
DH < DRL. (1TT .pf) S Ee
and:
J(me) -((e)) > 2-
Var
Σ rh
E2.
33

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
This establishes the desired inequality. Setting 8² & for some constant c 0, we achieve n
Vn Dn (PTe, Fro) S 2
which is valid provided that n 2 c'. c.. _ta
D. Additional Experiments in the Didactic Setup
Details on the setup. We generalize the planted subsequence problem from (Setlur et al., 2024b). The input prompt is We fix the unknown function to
a sequence of length? with the tokens chosen randomly from the set {1, 21,,,3.... ....... 103. be g(x) = 2x + 5. We fix the vocabulary for the policy we are training to be the set V =: (O.......) Here 0 is treated as the padding token. Concretely, for input problem x (x1,-.,55)) we say that response y with H tokens from the vocabulary V is correct trace if there exists a gold contiguous subsequence (g(z1) (z5)) planted in y. Here, the underlying mapping g :[10]=> [30] is fixed but unknown. For a state s =: (x, (I.....,,,),, an), the bi-level reward r(s) = 1 if and only if there exists some h' < h such that the last 5 tokens before h' i.e., (ak' match the gold subsequence. In order to use the same performance scale to compare methods trained for different horizon H values (test-time compute budget), we J, (T) and divide it by the maximum reward of H - 4.
We wish to construct base policies Ty that: (i) differ in heterogeneity, and (ii) satisfy the anti-coneentration condition. To do so, we finetune GPT22-x (Radford et al., 2019) on samples obtained from mixture of hand-designed "procedural" policies. Inspired from Setlur et al. (2024b), a procedural policy (1 (8) (s)x y when the last k tokens in the state match the first k tokens in the gold subsequence y*. Thus, the normalized return for pay -,,, as 70000 We vary the heterogeneity of Te by finetuning GPT2-xl on data from a mixture of procedural policies with E (5, 10, 20, 50, 100, 5003. Once the last 5 tokens match the gold sequence, the procedural policy puts mass x on the padding token O. See Figure 9 for an illustration of data sampled from different procedural policies.
For any compute budget Hl (token length), we train separate SFT and RL policies, where SFT is run on traces that are H tokens long. We also run RL on the same token budget, against trained verifier. The verifier is trained samples from the base policy. For this, we train a GPT2-xl transformer as a multiclass classifier, that takes in an H length sequence and outputs single value in 0 to H (i.e., it is an H + 1-way classifier).
Experiment details. For the RL runs, we use REINFORCE (Ahmadian et al., 2024) train for 20k iterations in both with a batch size of 64, and a constant learning rate of 1e - 4, with the Adam optimizer. The RL runs are initialized with the base policy, and to prevent reward hacking we also use a KL penalty (with weight 0.2), in addition to the REINFORCE training objective. For every trace in a batch, we query the trained verifier, which outputs value between 0 and H. which directly tells us where the "staircase" appears in the bi-level reward. For example, value of 2 implies that the staircase appears on the second last token. We convert this outcome supervision into token-level 0/1 rewards and update the policy with the computed policy gradient. For SFT, we also use the Adam optimizer with a learning rate of 2e - 4, and a batch size of 64. Similar to RI., we apply a KL regularization term in addition to the next token prediction loss (ignoring the padding token 0), where the strength of the KL term is the same as RL. SFT runs are also initialized with the base policy, Using the same hyperparameters, we obtain the base policy by running SFT on 200k data points sampled i.i.d. from the uniform mixture over procedural policies outlined above. To collect training data for the verifier, we draw random sample of n/log if prompts in Dur, and then make log calls each of them to binary search for the token where the correct answer first appeared. This way, we only query reward annotator times. Finally, for our experiments, where we vary base and expert policy heterogeneity, we simply change (reducing variance over it), in a way that the average performance of the base/expert policy remains roughtly the same.
Accuracy of trained verifier. In Figure 10(left), we plot the accuracy of the verifier (black line), as we scale the horizon. We fix the data budget to 2n 4 here. Since, here budget implies a multi-class classification over more classes, the problem hardness increases for the verifier, which explains the performance drop. Initially, we do see an improvement with H. since the coverage over high reward trajectories improves with H, as we sample the base policy for longer. We also plot the upper bound on RL performance, where we train the RL policy with ground-truth staircase rewards. Looking at its performance, it is clear that across all horizons, RL with trained verifier mainly suffers from the inaccuracy of the trained verifier (i.c., reward hacking issues). In Figure 10(right), we plot the accuracy of the learned verifier on two distributions (base policy), and the policy learned by RL. As we reduce base policy heterogeneity, it is easier to generalize on the base policy, but the verifier inaccurate outside the narrow distribution of the base policy, making it more susceptible to reward hacking. As a
34

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Input (Conlext)
Procedural policy y = 10
Procedural policy 1000
1, 3,
9. 7, 25, 9. 15,14, 14, 20 Reward: O, Normalized: 0
7.9. 15, 11, 21 0. 0,0
Reward: Normalized:
3, 1, 7, 6,
11. 7, 71 2, Reward: 3, Normalized: 0.5
11.7 19,9, 17 0.
Reward: 6, Normalized;
Unknown mapping: g(x) 2
Gold subsequence
Figure 9: Procedural policies for the generalized planted subsequence problem: For two values of 7: 10, and 1000, we show examples of two draws, over H = 10 tokens from each. Here, the unknown mapping is g(z) = 2x + 5. When is 1000, the policy (over the first 5 tokens) is almost like a dirac delta distribution on the gold subsequence, followed by which it samples the padding tokens. On the other hand, when 7 = 10, it makes multiple attempts and completing the sequence. Once it fails, makes a new attempt. the second sample, we see that after a few tokens it gets the correct sequence. achieving total bi-level reward of 3, and normalizing it with H 4, we get normalized reward of 0.5.
0.90
0.95
0.95
Test-time efficiency
0.85
0.85
Accuracy
Accuracy
0.80
0.75
0.75
0.65
0.65
0.70
0.55
0.55
Accuracy policy #t
(RL)
2 (RL w/ GT)
Accuracy policy as
0.45
0.45
0.60
2
2
2
2
10a
10 Base policy heterogeneity dg
10a
10
Horizon H (compute at test-time)
(Left) we plot the accuracy of the verifier (black line), (black line). We also plot the performance of RL with ground-truth (GT) bi-level rewards, and compare it with RL using the trained verifier. (Right) As we vary base policy heterogeneity we plot the accuracy of the verifier on two distributions: (i) on base policy Wh. (ii) on policy learned by running RL Axb.
Figure 10: Accuracy of trained verifier:
scale the horizon
result, we observe poor accuracy on the learned policy's distribution.
E. Additional Experiments on MATH
Experiment details. We run all our training on the questions in the training set MATH (Hendrycks et al., 2021), and run our test the MATH500 evaluation benchmark. Any problem instance is determined by the data budget n and compute budget H. For fixed compute budget H, multiple turns of responses. Each response is at most 512 tokens long. A trace can thus comprise of anywhere between 1 to H/512 turns (sometimes more for shorter responses). Here, all turns except the last one are responses that result in incorrect final answers for the problem. This is exactly the recipe followed by Qu et al. (2024) and Snell et al. (2024), for learning to self-correct, revise responses, or more generally use sequential compute at test-time. See below for examples of search traces of SFT. For training the verifier, we simply use samples from the base LLM, and use 0/1 rewards to train model of the same size as the policy with cross-entropy loss. We use a batchsize of 32 and learning rate of 1e 6 for all our experiments. We run SFT and verifier training for 10000 iterations on each instance. We use weight decay of 0.01 for training both. At test-time, we measure the performance of SFT using majority voting over sequential revisions, following Snell et al. (2024). We sample rollouts with temperature 1.0.
SFT trajectories of search traces. A single search trace consists of
Verifier accuracy. In Figure 11 we plot the test accuracy of the trained verifier as we scale data. Interestingly. we find that the bigger model always generalizes better, and models of both sizes improve performance at the same rate, as we scale the data budget n.
35

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Verifier accuracy
0.91
3B
0.87
Acciracy
0.83
0.79
0.75
2
2
2
2
2
data budget (n)
Figure 11: Accuracy of veriffier: We plot the accuracy of verifier as we scale data, for Llama3-3b and 8b sized models. We find that the larger model generalizes better across data budgets.
Search trace with sequential revisions for SFT (example with 3 episodes)
Query: A rectangle's length is five than twice its width. If its perimeter is 58 cm, what is its width? Turn-1 Response: Step I: Let's assume the width of the rectangle as Step 2: According the given information, the
length is five more than twice the width. So, the length can be expressed as 2x + 5. Step 3: The perimeter of a rectangle is given by the formula:
Perimeter 2(Length + Width)
Step 4: Substituting the given perimeter of 58 cm and our expressions for length and width:
2(x + 2r + 5) 58
53
I 6
53
Answer: INCORRECT
Turn-2 Response (Subtle Error Introduced): Step 1: The width x and the length 2x + 5. Step 2: Using the perimeter formula:
2(x 2r + 58
6ar + 5 = 58
x = 7
Answer: INCORRECT
Turn-3 Response: Let's solve the problem step by step: Step 1: Let's denote the width of the rectangle Step 2: The length is five more than twice the width, so it can be expressed as 2r 5. Step 3: The perimeter formula for rectangle is:
Perimeter = 2(Length + Width)
Step 4: Substituting the given perimeter of 58 em:
2(x + 2r + 5) 58
= 8
Answer: INCORRECT
36

---

Scaling Test-Time Compute Without Verification or RL is Suboptimal
Search trace with sequential revisions for SFT (example with 2 episodes)
Query: larmer has three times as many chickens cows his farm. If he has 15 cows, how many chickens does he have?
Turn-1 Response: Step I: Let's assume the number of cows as Step 2: According to the given information, the farmer has three times as many chickens as cows. So, the number of chickens can be expressed as 3x. Step 3: We are given that there are cows, so let's substitute x 15 into the equation:
3r 3(15) 30
Answer: 30 INCORRECT
Turn-3 Response: Let's solve the problem step by step: Step 1: Let's denote the number of cows as æ. Step We are given that the farmer has three times as many chickens as cows. So, the number of chickens can expressed 3z, substitute 15 into the expression for the number of
Step 3: We are also given that there are 15 cows, chickens:
3 x 15 = 45
Answer:
45
CORRECT
37


Reviews:
[{"review_id": "kOgZHKpSph", "reviewer": "Reviewer_nSQF", "summary": "- This paper seeks to understand the best way to finetune LLMs that leads to performance that is most scalable in terms of test-time compute\n- These are split into VF methods that don't use a verifier (eg SFT on expert trajectories) and VB methods that do (eg RL on 1/0 rewards)\n- The focus is on theoretical results. First they define heterogeneity (roughly how diverse is the base policy in terms of q value) and anti-concentration (roughly a high value means there is a lump of probability mass at a reward value much higher than the average value)\n- $H$ is test time budget per answer (number of tokens) and $n$ is number of examples for finetuning phases.\n- The first main result (theorem 5.4) is sub-optimality of VF methods deteriorates with heterogeneity (which itself scales $\\Omega(H)$), which leads to overall bound $H/\\sqrt{n}$\n- The second is that sub-optimality of VB methods do not, and instead is constant (assuming $n$ is set to be linear in $H$)\n- Combining these (theorem 5.8), one gets the gap between VB and VF methods is bounded by $\\Omega(H/\\sqrt{n})$ where $n$ is set as $n=\\Omega(H)$, giving the main result that the gap grows $\\sqrt{H}$.\n- Two experimental results are presented, a didactic toy distribution (but still using real LLMs) and math reasoning.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and a positive assessment of our work! To address your concerns, we added an experiment for the didactic setup where we show an increasing performance gap between VF and VB methods, as we scale both n (the number of prompts) and H (the output length), matching our results on MATH in Fig 5c. We also answer other questions on heterogeneity, anti-concentration, and running RL followed by SFT. We will also use the extra page in the final version to uncompress Sec 7, and if needed shorten Sec 6.\n\n>> **[New Expt.] Gap between VF and VB methods in the didactic setup too scales as $\\sqrt{H}$.**\n\nSimilar to our MATH experiment (Fig 5c), we plot the performance of VB (RL) and VF (SFT) in our didactic setup here: **https://sites.google.com/view/ttcwv/home**. In Fig 5a we fix the data budget to $n=2^{10}$, and in 5a fix the compute budget $H=2^6$. Now, we scale $n$ with $H$, and note the performance gap between RL and SFT scale superlinearly (as $\\sqrt H$), in agreement with our result in Theorem 5.1.\n\n>> **Why does heterogeneity hurt VF methods?**\n\nA VF algorithm (e.g. SFT) finetunes the base LLM on expert traces (e.g. traces collected by rejection sampling correct answers from base LLM). VF methods fail under heterogeneity for the following reasons:\n\n- **Diverse solution traces**: When the base policy (and thus the expert induced by rejection sampling) is heterogeneous, the expert data consists of diverse solution traces for the same problem. Here, each trace gets to the correct answer, spending a varying number of tokens (e.g., a short solution that directly outputs the final answer, and a longer solution that is composed of a failed attempt, followed by a correct one that solves the problem). Thus, the bi-level reward carried by these traces has a high variance for each input. \n\n- **VF methods are forced to equally mimic diverse traces**: VF methods like SFT finetune the base LLM on expert traces where reward annotations are absent. Thus, VF methods cannot distinguish between the diverse expert traces, and are forced to mimic each trace equally, irrespective of their reward. Thus, the VF learned policy fails to only learn high reward solutions. Also, in practice it is challenging to collect multiple traces that are less diverse, i.e., with matching rewards, and naturally the expert data is heterogeneous (as we also show in Sec 7). On the other hand, VB methods like RL have access to reward annotations from a learned verifier or ground truth 0/1 rewards, and need only mimic or increase likelihood on high reward traces, as judged by the verifier. \n\nNote that the verifier for VB is trained on heterogeneous, and suboptimal data (includes incorrect answers) sampled from the base LLM, and the learned verifier is also forced to equally reduce estimation error on each mode of the reward distribution (low and high rewards). But, the base LLM is finetuned to *maximize* the rewards under the learned verifier. So, the heterogeneity of traces sampled from the base policy does not hurt the policy learned by VB methods. \n\nWe will add the above discussion after Theorem 5.4 in the final version. \n\n>> **Does running SFT before RL help, as done in practice?**\n\nYes, you are correct, our results imply that running SFT before RL can help improve coverage of correct solutions under the base LLM. Note that, our performance guarantee (Thm 5.7) for VB methods like RL bounds the suboptimality gap by $O(H/n)$ for the RL trained policy against the best expert in the $\\epsilon$-$\\chi^2$ ball around the base LLM. Thus, for the RL policy to have good performance in absolute terms, we need to ensure that there exists an LLM in an $\\epsilon$-$\\chi^2$ ball around the base LLM that performs well on the task. One way of ensuring this is to improve the coverage of the base LLM over high reward traces or at least correct solution traces, and SFT does exactly that. Thank you for this question; we will add the above discussion after Thm 5.7. \n\n>> **Anti-concentration felt like a very specific assumption. It is not surprising RL can seek this mode.**\n\n\nAnti-concentration is a weaker form of the trajectory level coverage assumption made in offline RL literature (e.g., Kumar et al. BC or Offline RL). The functional form of the definition (one std. dev. from mean) stems from the fact that VB methods need to improve over the best expert in $\\epsilon$-$\\chi^2$ ball around base LLM, and the reward for such an expert assumes this form. Yes, it is not surprising that online RL can seek this mode of higher rewards given access to the ground-truth bi-level reward function. The non-trivial finding of our analysis is that training a learned verifier *using only IID samples from the base policy* and optimizing it with online RL is enough for a policy to seek this mode (Alg. 1). Contrast this with prior works on reward hacking when optimizing learned verifiers (Gao et al.).", "claims_and_evidence": "fine", "methods_and_evaluation_criteria": "fine", "theoretical_claims": "I only looked at main paper content and skimmed some appendix section, but have not interrogated in depth", "experimental_designs_or_analyses": "fine", "relation_to_broader_scientific_literature": "see strengths weaknesses", "essential_references_not_discussed": "fine", "other_strengths_and_weaknesses": "Strengths\n- I'm sure much of the community would welcome this kind of deeper understanding of differences between LLM finetuning methods and their scalability\n- Precisely written, no obvious errors (although I was not able to fully interrogate all mathematical details)\n- Good job of making effort to provide intuition and link to practice, rather than solely stating results in mathematical language\n- LLM experiments in section 7 were excellent, with an attempt to even measure and visualize heterogeneity and anti-concentration\n- Tackling this kind a problem through theoretical analysis is tough, and I feel the authors have done a great job at making progress (though I am only familiar with high-level details of related work so cannot comment too precisely)\n\nWeaknesses\n- The paper is dense. The concepts took me a long time to absorb, and there are various lemmas outside of the main results I did not have time to fully process. Less content could be more from a readability perspective. \n- The didactic experiment was less informative than the math experiment. The gap between the two methods didn't seem to grow with $\\sqrt{H}$ (fig 4 a), and there was little extra intuition I felt I gained from it. \n- Anyway these didactic results are supersceded by the math experiments, which end up being cramped and rushed for the sake of space. I might suggest removing section 6 from the main paper altogether to uncompress the technical results and provide readers a deeper dive into section 7.\n- Anti-concentration felt like a very specific assumption to require -- intuitively it says we need a large amount of probability mass producing rewards that are far from the average output of the model. It's not a surprising consequence then that RL should be able to seek this mode out.\n- I did not follow the intuition for why heterogeneity harms VF methods. Did I miss this in the paper? It seemed like one of the two cornerstones leading to the main result, but I was unable to follow why it would have a detrimental affect.\n\nQuestions\n- I wonder if the results say anything about the common practice of firstly SFT finetuning followed by RL finetuning. The paper's results suggest the latter is strictly better than the former?", "other_comments_or_suggestions": "fine", "questions_for_authors": "see above", "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": "QGwigG73CN", "reviewer": "Reviewer_eEQB", "summary": "This paper studies the performance of two prevalent methods which are named as verifier-based (VB) and verifier-free (VF) methods in terms of scaling test-time compute. VB methods utilize a verifier or reward signals to improve a policy while VF approaches use expert data to supervise the policy training. They compare the performance of these two category of methods at different test-time compute by introducing a bi-level reward to represent the compute. The authors show VB methods scale test-time compute better than VF methods if the base policy satisfy heterogeneity and anti-concentration. Besides, they implement experiments to support this finding.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback! We believe that many concerns perhaps stem from a misunderstanding of the setup. We study the efficacy of different fine-tuning algorithms to train LLMs to attain better performance as they utilize more test-time compute, measured in terms of the token length. Verifier-based (VB), or verifier free (VF) are finetuning methods, like DeepSeek-R1 or SCoRe, training LLMs to use more test-time compute to solve more problems. We expand on this, provide more evidence of anti-concentration holding in practice, and explain how we can relax the worst-case (over prompts) anti-concentration to average case while arriving at the same result in Thm 5.8.\n\n>> **I am confused at what the authors refer to as test-time compute? It is applied to finetuning**\n\nAs we explain in L131-152, our goal is to compare LLMs obtained by running different finetuning algorithms that train LLMs to utilize test-time compute (measured by the length of CoT H) more effectively. So, either we finetune LLMs with VF, e.g. by running SFT on expert traces of length at most H containing behaviors like planning, search, backtracking etc., or train LLMs with a verifier based approach like RL that samples traces of length H from the base LLM, and optimizes it with 0/1 rewards (L165-175, L200-209). Our analysis is novel because it compares finetuning algorithms that train LLMs to optimize test compute efficiency, as opposed to only analyzing the efficiency of known test-time search algorithms like best-of-N.  \n\n>> **How is Fig7 plotted,is it for 1 problem. Ablations on  anticonc?**\n\nSee figure & caption in **https://sites.google.com/view/ttcwv/home**.\n\n>> **Prop. 5.6 is restrictive since it needs to hold on all problems. Consider relaxing it.**\n\nThe notion of anti-concentration can indeed be weakened to accommodate  *average-case* at the cost of a slightly weaker dependence on $n$.\n\nSee fig in **https://sites.google.com/view/ttcwv/home** for the derivation. Note that this results in the same conclusion as Thm 5.8 in the current paper, but the bound depends on a weaker notion of anti-concentration. \n\nAdditionally: \n- *Common in literature*: This style of uniform lower bound is common in RL theory (e.g., Uehara el al., Kumar et al.). Prior work assumes strong density ratio bounds, whereas we only require that base policy generates traces exceeding one std. dev. of the mean reward with constant probability.\n- *Poor anti-concentration can hurt VF too*: In practice, VF gets expert traces by running rejection sampling. However, rejecting more traces results in smaller SFT data. This tradeoff is worse for problems with poor anti-concentration. To achieve a high reward dataset, the learner would need to discard most traces, biasing the dataset and degrading SFT performance. We will add this to final version.\n\n>> **Thm 5.1: does there exist a base policy where VF > VB?**\n\nNo matter the base LLM, whenever the expert is non-heterogenous, and covers high reward traces, we expect VF algos like SFT to learn good policies. It is possible that in some cases when heterogeneity and anti-concentration are not satisfied, VF methods may outperform VB, as we also show in Fig 6 (left). In practice, however, we see the assumptions are satisfied(Figs 6, 7).\n\n>> **L281, lemma implying anti-concentration needed for VB > VF**\n\nHeterogeneity (Prp. 5.2) & anti-concentration (Prp. 5.6) are largely orthogonal conditions, which we show are sufficient to prove VB > VF. We show in Sec 7 (Fig 6, 7) that *both* conditions hold in practice. As seen in Fig 3, base LLM can satisfy these conditions separately. In L281, we are referring to the fact that a heterogeneous base LLM need not satisfy anti-concentration (3rd col in Fig 3), which is why we need both Prp. 5.6 & 5.2 to hold for the base LLM. \n \n>> **Discussion on Kumar et al**\n\nIn Remark 5.9 (L299), we already include a detailed comparison with prior work comparing BC and offline RL methods. \n\n>> **Condition on expert distribution, is it needed in theory?**\n\nYes, one may prove a result assuming the expert policy is far away from the base policy and only samples high reward traces. But this is less practically useful: 1) it is unclear how to identify and sample from such an expert; and 2) the expert needs to be close to the base policy to: a) prevent optimization and memorization issues (Kang et al., Tajwar et al.); and b) it is common to collect expert traces by running rejection sampling (Zelikman et al.).\n\n>> **Realizability assm. in Prp 5.5**\n\nYes, the true reward function is assumed to be present in reward class R. We state this in our setup (L114), and we will highlight this better.\n\n>> **Y-axis in Fig 4**\n\nTo cleanly compare performance of policies trained for different values of token length H, we divide the average reward (in [0, H]) that measures test-time compute efficiency by H (L347). Hence, the normalized rewards are in [0,1], and can be viewed as accuracy normalized by the test-time compute budget.", "claims_and_evidence": "No, the claim made is not supported clearly or solidly.\n\nThe main claim in this paper is that finetuning LLMs with VB methods is superior to VF approaches in terms of scaling the compute resources.\n\nFirst, the title of the paper is scaling test-time compute, but this paper seems talking about the fine-tuning phase. I also raised my question in the question part below.\n\nSecond, to show the advantage of VB methods, the base policy should possess some properties which are restrictive (I elaborate in the weaknesses part). And I don't think their experiments successfully show that in practice, pre-trained policies satisfy these conditions.", "methods_and_evaluation_criteria": "Yes, so the authors want to show verifier-based algorithms have advantages at scaling the test-time compute compared with verifier-free methods. They first model the scaling of test-time compute by the horizon and defining a bi-level reward. Then they show the lower bound of sub-optimality of VF algorithms and upper bound of sub-optimality of VB algorithms under certain condition of the base policy.", "theoretical_claims": "No, I didn't check the correctness of the theorems. But I think that Proposition 5.5 needs a realization assumption of the reward function class.", "experimental_designs_or_analyses": "Yes, I checked the soundness of the experimental part about didactic setup. The authors compare results at different data budget, horizon (which represents compute in their framework) and policy heterogeneity. However, policy anti-concentration is less discussed. They show and control the policy heterogeneity of their choosing base policy, but they didn't show how they control the anti-concentration which is important for the soundness of the experiments. In the experiments for math reasoning, they include a Figure 7 to show that practical pre-training policies satisfy the anti-concentration property, but this conclusion is too optimistic. At least more different policies should be tested. And I also doubt the definition of anti-concentration (please refer to the weaknesses part).", "relation_to_broader_scientific_literature": "The contributions of this paper are related to two broad directions. The first is how scaling test-time compute can improve a model. It is an active area and there are some promising results [1][2]. The second is which is better: learning from experts or learning from rewards. Some works [3] study this question in reinforcement learning, especially imitation learning, but it is relatively under-explored in language models.\n\n[1]. Snell C, Lee J, Xu K, et al. Scaling llm test-time compute optimally can be more effective than scaling model parameters[J]. arXiv preprint arXiv:2408.03314, 2024.  \n[2]. Hübotter J, Bongni S, Hakimi I, et al. Efficiently learning at test-time: Active fine-tuning of llms[J]. arXiv preprint arXiv:2410.08020, 2024.  \n[3]. Kumar A, Hong J, Singh A, et al. When should we prefer offline reinforcement learning over behavioral cloning?[J]. arXiv preprint arXiv:2204.05618, 2022.", "essential_references_not_discussed": "No, I didn't see any essential related works are not discussed.", "other_strengths_and_weaknesses": "Strengths:\n1. Comparing the methods of learning from rewards and learning from expert is a very interesting and important direction. \n\nWeaknesses:\n1. The authors show by Theorem 5.1, there exists a base policy $\\pi_b$ such that verifier-based algorithm scales better with test-time compute. But they didn't show if it is possible that there also exists another $\\pi_b$ such that verifier-free algorithm scales better. It is important to derive the final conclusion.\n2. The anti-concentration parameter which they define as $c$ in Property 5.6 depends on 'worst' problem since they define $\\min_x c_x(\\epsilon_x)\\ge c$. This a very restrictive definition/requirement. It is usually the case where we have a huge number of different problems for a specific task. The anti-concentration definition needs the base policy to have nice shape of the answer distribution over all problems. I think the authors should relax this definition. Besides, how is Figure 7 plotted, is it for just one problem? If it is for a set of problems, how are these metrics calculated?\n3. The authors should include more detailed discussions on the related work [1] since this work also models the problem as a MDP and their work is very close to this work. In the paragraph before Section 6, the authors give some discussions but are vague to a reader.\n\n\n[1]. Kumar A, Hong J, Singh A, et al. When should we prefer offline reinforcement learning over behavioral cloning?[J]. arXiv preprint arXiv:2204.05618, 2022.", "other_comments_or_suggestions": "1. Some typos: In line 183, For e.g. -> For example. On the right column in line 62, distinction -> direction. In line 305, this results in Theorem 5.7 which is an incomplete sentence.\n2. It would be better to include a lemma that can formally describe the relationship between the definition of policy heterogeneity and anti-concentration. I noticed that the authors explain in somewhere in a paragraph that 'while a non-heterogeneous base policy will not satisfy Property 5.6, hetergeoneous distributions can still be anti-concentrated'. This is crucial to derive the final conclusion in this paper which is VB algorithms can perform better than VF algorithms for some base policy. It is not very straightforward at the first glance, hence I think adding a lemma would be beneficial.", "questions_for_authors": "1. I am confused at what the authors refer as test-time compute. From my understanding, the test-time compute usually refers to the compute applied to the inference phase of the model which has been trained or fine-tuned. But in this paper, it seems to refer to the compute applied to the fine-tuning phase. Do I misunderstand something here?\n2. In line 182, the condition (b) of the expert is the expert's distribution should be 'close' to the base policy to prevent some issues, but these issues arise in practice. From the theoretical perspective (which is this paper's perspective), do we need this condition and why?\n3. In Proposition 5.5, doesn't one need realization assumption of the reward function class, i.e., the true underlying reward $R^*$ is in the set of reward functions $R^*\\in \\mathcal{R}$?\n4. What does the y-axis (efficiency) in Figure 4 refer to, accuracy?", "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": "2zuamkZk5P", "reviewer": "Reviewer_qsM1", "summary": "The paper theoretically studies inference time scaling by modeling LLM generation as a Markov process with horizon $H$ and comparing verifier-based (VB) methods to verifier-free (VF) methods. For binary and nondecreasing rewards, and under a heterogeneity assumption of the base model search trace solutions, it is shown via an information theoretic construction that any VF algorithm with access to $n$ data points from an expert has suboptimality gap $\\Omega(H/\\sqrt{n})$, in the worst-case sense over a class of alternate experts/rewards. In contrast, it is shown that a specific VB algorithm with access to $n$ annotated search traces, optimizing a pessimistic reward over a class of approximate reward functions, achieves suboptimality gap $\\widetilde{O}(H/n)$ under an anti-concentration assumption on the distribution of rewards. Hence VB can asymptotically outperform VF algorithms as test time compute $H$ is scaled. The assumptions and results are also verified experimentally on synthetic and math reasoning tasks.\n\n* Update after rebuttal: I am satisfied with the authors' response and maintain my high rating of the contribution.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and a positive assessment of our work! To address your remaining concerns, we clarify the data annotations for VB and VF methods and show that our analysis can be extended to settings beyond binary rewards, while proving a similar separation between VB and VF methods. We also point to discussion on a relaxation of uniform anti-concentration. \n\n>> **Extending our analysis to non-binary rewards**\n\nWhile our algorithms and analysis are tailored for $0$-$1$ rewards with the bilevel structure, in the non-stochastic setting (no noise in observed rewards) we can extend these results to the case of general rewards functions, while essentially preserving the final guarantees. \n\nIn general, given access to the trajectory-level reward, we can quantize the rewards to $n$ levels, and apply the same classification-based algorithm for learning the reward function. By doing so, we obtain an algorithm for learning general rewards in $L_1$ error to a test error of $H \\log(|\\mathcal{R}|) \\log(n)/n$. The only differences compared to the bilevel case are: there is an additional $\\log(n)$ blow up compared to the bilevel case, the learner can directly query the outcome reward for a trajectory directly (rather than the per-step reward).\n\nThe intuition is as follows: suppose the outcome reward belongs to some class $\\mathcal{R}$, we can consider an induced quantized reward class $\\mathcal{R}_q$, which rounds the rewards to a grid where consecutive points are $H/n$ apart. Note that $|\\mathcal{R}_q| \\le |\\mathcal{R}|$. By quantizing the reward observations, and training a multiclass classifier over the outcome space $\\mathcal{Y} = \\\\{ 0,\\frac{H}{n}, \\frac{2H}{n},\\cdots,H\\\\}$ of size $n+1$, we can train a classifier incurring $0$/$1$ error of at most $d_G (\\mathcal{H}) \\log(|\\mathcal{Y}|)/n \\lesssim \\log(|\\mathcal{R}|) \\log(n)/n$, where $d_G$ denotes the graph dimension (see definition B.29 in the submission).\nWhen the classifier is correct (in a $0$/$1$ sense), the induced reward function makes an error of at most $H/n$. If the classifier is incorrect, the induced reward function makes an error of at most $H$. Overall, this implies that the $L_1$ error of the reward function induced by the classifier (which is essentially a discretized reward $\\in \\\\{ 0, \\frac{H}{n},\\cdots,H \\\\}$) is at most $ H\\log(|\\mathcal{R}|) \\log(n)/n + H/n \\lesssim H\\log(|\\mathcal{R}|) \\log(n)/n$. Hence, the same lemma, and the same guarantees, will also apply in our setting. We will add this discussion in the paper.\n\n>> **Data annotations for VB and VF methods**\n\nFor VF methods, we simply have $n$ datapoints of the form $\\(x, \\tau)$, consisting of an input $x \\sim \\rho$, and a trace $\\tau \\sim \\pi_e(\\cdot \\mid x)$ sampled from expert $\\pi_e$. For VB methods, we have $n$ datapoints of the form $(x, \\tau, r(\\tau))$, where $x \\sim \\rho$, but the trace $\\tau \\sim \\pi_b(\\cdot \\mid x)$ is sampled from the base LLM $\\pi_b$, and $r(\\tau)$ is the reward annotation $\\in [0, H]$ under the bi-level reward $r$. We will also move details from the formal theorem statements in Appendix (e.g., the formal lower bound result in Thm. B.10) into the main paper, in our final version, which we hope will make the theorem presentation more clear.\n\n>> **Relaxing uniform anti-concentration to an average case notion.**\n\nPlease see our response to reviewer eEQB where we show that our uniform anti-concentration can be relaxed to $L_p$ concentration, and when $p>2$, we recover the same asymptotic separation of $\\Omega(H/\\sqrt{n})$ between VB and VF methods, as we obtain under uniform anti-concentration in Thm. 5.8. We show the full derivation in a figure here: **https://sites.google.com/view/ttcwv/home**.", "claims_and_evidence": "The claims are supported by convincing theoretical and empirical evidence.\n* It is shown that the suboptimality of any VF estimator scales as $\\tilde{\\sigma}_b/\\sqrt{n}$ where $\\tilde{\\sigma}_b$ measures the median (over prompts) expected variation of the Q-function under the base LLM policy. This results in a $H/\\sqrt{n}$ separation assuming $\\tilde{\\sigma}_b=\\Theta(H)$.\n* Moreover, the paper constructs a VB estimator whose suboptimality scales as $H/n$ under an anti-concentration assumption for the base policy reward distribution. (This is required to hold uniformly over prompts which is slightly stronger, but I think this is fine.)\n* Combining these establishes a $\\sqrt{H}$ separation w.r.t. the generation horizon when $n=\\Theta(H)$.\n* Moreover, experiments on the MATH benchmark confirm the assumptions and show that heterogeneity hurts VF methods as predicted by the theory.\n\nThese results provide a solid framework to theoretically understanding the effect of verifier model vs expert cloning for inference time scaling.", "methods_and_evaluation_criteria": "Yes, see Claims And Evidence", "theoretical_claims": "The proofs are correct to the best of my knowledge", "experimental_designs_or_analyses": "There do not seem to be any glaring issues with experiment design", "relation_to_broader_scientific_literature": "Test time scaling for LLM reasoning is obviously a topic of crucial importance, however the theoretical understanding of chain of thought and test time scaling is still very shallow. I think the paper is a strong contribution towards this direction, proposing an MDP framework to study generation and interpreting verifier and behavior cloning from a novel information theoretic point of view.\nFrom a theoretical perspective, the paper borrows from but expands on existing regret analyses of Markov decision processes (e.g. Foster et al, 2024).", "essential_references_not_discussed": "None in particular", "other_strengths_and_weaknesses": "See above", "other_comments_or_suggestions": "While the many intuitive explanations are appreciated, the paper could benefit from being a bit more precise in the statements (e.g. theorems) of the main text for the theoretically inclined reader. In particular, it would be helpful to mathematically describe exactly what samples the VB and VF models have access to (expert trace vs annotated trace).\n\nTypos: $r\\to r'$ in Theorem 5.4, verifier-based $\\to$ verifier-free in Theorem B.10(4)", "questions_for_authors": "Some bounds in the proofs seem to rely on the rewards being binary, such as the rounding argument; can the results be generalized to when rewards are real-valued and monotonic?", "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:

Meta-review: This paper focusing on comparing the verifier-based (VB) methods based on RL or search and verifier-free (VF) approaches based on distilling or cloning search traces for LLM finetuning, and it draws conclusion that VB methods are more reliable and scalable when the  test-time compute budget grows. 

Reviewers generally agree with the significant of this topic and the conclusion is supported by both theoretical and experimental results.
Decision: Accept (spotlight poster)