Scaling Test-Time Compute Without Verification or RL is Suboptimal

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.

Extending our analysis to non-binary rewards

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

In 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).

The 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). When 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.

Data annotations for VB and VF methods

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

Relaxing uniform anti-concentration to an average case notion.

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

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.

I am confused at what the authors refer to as test-time compute? It is applied to finetuning

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

How is Fig7 plotted,is it for 1 problem. Ablations on anticonc?

See figure & caption in https://sites.google.com/view/ttcwv/home.

Prop. 5.6 is restrictive since it needs to hold on all problems. Consider relaxing it.

The notion of anti-concentration can indeed be weakened to accommodate average-case at the cost of a slightly weaker dependence on $n$.

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

Additionally:

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

Thm 5.1: does there exist a base policy where VF > VB?

No 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).

L281, lemma implying anti-concentration needed for VB > VF

Heterogeneity (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.

Discussion on Kumar et al

In Remark 5.9 (L299), we already include a detailed comparison with prior work comparing BC and offline RL methods.

Condition on expert distribution, is it needed in theory?

Yes, 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.).

Realizability assm. in Prp 5.5

Yes, 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.

Y-axis in Fig 4

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

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.

[New Expt.] Gap between VF and VB methods in the didactic setup too scales as $\sqrt{H}$.

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

Why does heterogeneity hurt VF methods?

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

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

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

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

We will add the above discussion after Theorem 5.4 in the final version.

Does running SFT before RL help, as done in practice?

Yes, 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.

Anti-concentration felt like a very specific assumption. It is not surprising RL can seek this mode.

Anti-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.).