PaperlayerView exact revision on arXiv

Source-linked AI summary

Scaling Test-Time Compute Without Verification or RL is Suboptimal

Amrith Setlur, Nived Rajaraman, Sergey Levine, Aviral Kumar

arXiv:2502.12118v2cs.LGcs.CL

TL;DR

The paper asks how LLMs should learn to use increasing test-time compute when expert data is limited and both trace distillation and verification are available. It formalizes and compares verifier-free and verifier-based finetuning under heterogeneous, anti-concentrated base-model rewards, proving and empirically confirming that verification-based methods scale better. The authors conclude that verification is important for efficient test-time scaling, while noting scope limits around verifier types, reward functions, and long contexts.

  • Problem

    The paper studies which of verifier-free trace distillation and verifier-based learning or search makes better use of increasing test-time compute.

  • Method

    The paper develops an information-theoretic and second-order analysis of finetuning a base LLM with expert traces versus reward annotations, under heterogeneous and anti-concentrated reward distributions.

  • Results

    Verifier-based RL and search outperform verifier-free methods at fixed compute, with a widening gap as test-time compute and, in some settings, training data increase; experiments corroborate the theory on didactic and math reasoning tasks.

  • Takeaways & Limitations

    When pretrained LLMs are sufficiently heterogeneous and anti-concentrated, training with verification or rewards is the supported route for scaling test-time compute efficiently.

  • Takeaways & Limitations

    The analysis mainly separates algorithms by access to verification and leaves sparse versus dense verification, broader reward functions, and test-time contexts beyond 32k for future work.

Abstract

from arXiv · show

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: first, distilling successful search or thinking traces; and second, using verification (e.g., 0/1 outcome rewards, reward models, 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]. This implies a stronger result that VB methods scale better asymptotically, with the performance gap between VB and VF methods widening as test-time budget grows. We corroborate our theory empirically on both didactic and math reasoning problems with 3/8/32B-sized pre-trained LLMs, where we find verification is crucial for scaling test-time compute.

1. Introduction

The paper compares verifier-based and verifier-free approaches for scaling LLM test-time compute, showing that verification is theoretically and empirically superior when base models have heterogeneous, anti-concentrated reward distributions.

  • Approaches: Verifier-based methods use outcome rewards or verifiers for search or RL, whereas verifier-free methods distill or clone expert solution traces without verification.The comparison concerns how finetuning uses available data and test-time compute.
  • Conditions: Heterogeneity means the base LLM covers multiple correct traces with varying rewards or lengths, while anti-concentration means some sampled traces exceed the base policy’s mean reward.These properties characterize when verification-based approaches outperform verifier-free approaches.
  • Theory: When rewards are anti-concentrated and the base policy is heterogeneous, verifier-based RL and search outperform every verifier-free algorithm at fixed test-time compute.The theoretical separation holds under the paper’s stated assumptions on the pretrained policy.
  • Empirical validation: The performance gap between verifier-based and verifier-free methods grows as test-time compute increases and can widen further when training prompts scale linearly with the token budget.Experiments with S1 and Llama models corroborate this scaling behavior.
  • Theory: Any verifier-free algorithm has worst-case suboptimality scaling as Ω(H/√n), while a simple verifier-based RL method scales as O(H/n).Here H denotes the test-time token budget and n the amount of training data.
  • Implications: The results imply that verifier-free methods scale well only when base-model heterogeneity is small, a condition the authors consider uncommon in modern LLMs.The paper reports that evaluated pretrained models are heterogeneous and anti-concentrated.

2. Related Work

Related work studies test-time search, refinement, verification, and trace distillation, while this paper instead analyzes verification access as an orthogonal axis and derives a separation under weaker conditions.

  • Test-time scaling: Test-time scaling methods either train LLMs to perform search or refinement in long reasoning traces, or wrap them with external search procedures.The paper explicitly does not study this distinction between implicit and explicit search.
  • Verifier-based methods: Verifier-based work uses outcome rewards, trained verifiers, search, value functions, or generative and implicit verification signals.These approaches apply verification during training, search, or both.
  • Verifier-free methods: Verifier-free work distills search procedures or long chain-of-thought traces and often applies supervised fine-tuning to those traces.Because these traces vary in token count, reward-free methods must imitate heterogeneous solutions.
  • Positioning: Unlike prior analyses assuming verification is easier to learn than correct generation, this paper establishes a gap under weaker, realistic conditions on the pretrained LLM.The relevant conditions are properties of the base policy rather than an assumed verification-generation difficulty gap.

3. Notation and Preliminaries

The paper models language generation as a token-level MDP in which states concatenate the problem and prior tokens, actions are generated tokens, and rewards are collected over a finite horizon.

  • Language generation is modeled as a token-level MDP with state space, token action space, binary rewards, and horizon H.
  • Each initial state is an input problem x sampled from distribution ρ, while later states append generated tokens to x.
  • A solution trace is a rollout τ=(x,a_1,...,a_H) through the MDP, with trajectory reward r(τ) accumulated across the horizon.

4. What Does it Mean to Effectively Scale Test-Time Compute?

The paper evaluates test-time scaling by how effectively a finetuned policy uses a fixed output-token budget, using bi-level rewards that favor correct solutions found earlier.

  • Effective scaling means attaining the best possible performance within a fixed compute budget as the horizon grows.
  • Test-time compute is represented by a maximum output-token length H, and performance is measured under a reward capturing accuracy and solution speed.
  • A bi-level reward stays at 0 until a correct solution appears, then remains at 1 for all subsequent steps.
  • A trace is correct when it reaches the correct answer within H tokens, and higher cumulative reward reflects solving efficiently within the budget.

5. Theory: When Does Verification Enable Asymptotic Scaling of Test Compute?

The theory compares verifier-free imitation of expert traces with verifier-based learning from reward annotations, showing that verification scales better when base policies are heterogeneous and anti-concentrated.

  • Verifier-free methods imitate correct expert traces, whereas verifier-based methods use reward labels on traces sampled from the base policy.
  • The main result states that a verifier-based algorithm can scale test-time compute by ˜Ω(H) relative to any verifier-free algorithm for suitable base policies.
  • Any verifier-free method can incur suboptimality Ω(H/√n) when the base policy is sufficiently heterogeneous.
  • A simple verifier-based method has suboptimality 𝒪(H/n) and has no direct dependence on base-policy heterogeneity in the stated guarantee.
  • Anti-concentration means the base policy assigns constant mass to traces with rewards above its mean, allowing verification to discover higher-reward policies.
  • The resulting separation implies that the performance gap between verifier-based and verifier-free methods grows with test-time compute, and the paper summarizes verification as enabling test-time scaling.

6. Illustrating Theory in Practice

The didactic experiments validate the theory that verifier-free methods become increasingly suboptimal as base-policy heterogeneity and test-time compute grow, while verifier-based RL remains closer to the expert.

  • Experimental setup: The didactic setup constructs contextual planted-subsequence problems and varies GPT2-xl base-policy heterogeneity using mixtures of procedural policies.The procedural policies differ through a parameter γ, with mixtures over γ∈[1000] used to vary heterogeneity.
  • Compared methods: Verifier-free SFT trains on correct expert traces, whereas verifier-based RL trains a reward model from base-policy responses annotated with bi-level rewards.The verifier predicts H+1 reward values from 0 to H.
  • Scaling test-time compute: As test-time token budget H increases, the gap between SFT and the expert policy worsens, while RL nearly matches the expert until verifier accuracy declines.The RL gap later increases slightly, likely because higher H reduces verifier accuracy and causes reward hacking.
  • Scaling data budget: With fixed test-time compute, increasing data improves both SFT and RL, but RL has a much steeper performance slope and is more sample efficient.The passage identifies the RL advantage as consistent with a 1/n versus VF scaling result.
  • Effect of policy heterogeneity: Reducing base-policy heterogeneity narrows SFT’s suboptimality gap and can make verifier-free methods outperform verifier-based RL.The reported reversal is attributed primarily to declining verifier accuracy, with anti-concentration possibly also failing.

7. Results: Large-Scale Math Reasoning

On MATH, verifier-based search consistently scales test-time compute and data more efficiently than verifier-free SFT, especially for heterogeneous problems, while SFT can win on homogeneous ones. The experiments also show that base LLM reward distributions exhibit the heterogeneity and anti-concentration assumed by the theory.

  • Experimental scope: The experiments use Llama-3.1/3.2 8B/3B instruct models, varying test-time budgets from 2^9 to 2^13 tokens and training data from 2^12 to 2^16 samples.The large-scale evaluation focuses primarily on the MATH reasoning benchmark.
  • Scaling compute and data: 8×: BoN scales test-time compute over SFT at fixed data, while 6×: VB improves sample efficiency at fixed test compute.The comparison uses BoN with a verifier against SFT on manually stitched sequential revisions.
  • Scaling compute and data: The accuracy gap between BoN and SFT grows super linearly in log H when training data and test-time compute scale together.This empirical pattern matches the cited theoretical prediction.
  • Results with s1: In a compute-matched evaluation, verifier-based BoN improves over the budget-constrained s1 model trained by verifier-free distillation.BoN samples short responses and selects among them using a trained outcome verifier.
  • Heterogeneity: When problem heterogeneity σx is low, SFT can outperform BoN; when σx is high, BoN dominates because SFT mainly memorizes responses.The problem distribution is skewed toward higher heterogeneity, yielding better average performance for verifier-based methods.
  • Anti-concentration: With κ=0.5, roughly one quarter of correct traces on both easy and hard MATH problems exceed the marked reward threshold, indicating anti-concentration.The resulting anti-concentration coefficient is approximately accuracy × 0.25, supporting verifier-based coverage of correct answers.
  • Takeaways: The reported MATH trends match the theory: base LLMs are heterogeneous and anti-concentrated, and verifier-based methods outperform verifier-free methods as compute and data increase.The summary also notes that verifier-free methods can outperform verifier-based methods when heterogeneity is low.

8. Discussion, Limitations, and Future Work

The paper formalizes asymptotic test-time compute efficiency and compares verifier-based and verifier-free learning under heterogeneous base policies. It proves a separation favoring verification and connects the theory to experiments, while identifying extensions involving verification density, reward classes, and long contexts.

  • Discussion: The study analyzes verifier-based and verifier-free algorithms for training LLMs to use increasingly large test-time compute budgets.The comparison is organized around access to reward or verification signals.
  • Discussion: A heterogeneous base policy can make verifier-free learning fail to scale efficiently to large test-time budgets, whereas a simple verification-based approach avoids this separation.The theory uses heterogeneity and weak anti-concentration as conditions for the separation.
  • Empirical connection: The paper compares its theoretical predictions on MATH and AIME benchmarks and in a didactic setting with explicitly controlled heterogeneity.The empirical comparisons use the s1 model and a sequential self-correction model.
  • Limitations and future work: Future work should compare sparse and dense verification, extend the analysis to generative rewards, and study verifier-based scaling beyond 32k-token contexts.The authors specifically mention process-based rewards, generative rewards, and RL with outcome or dense rewards.

Appendices

The appendices establish supporting divergence, change-of-measure, variance, and concentration tools used in the paper’s lower-bound arguments. They also connect reward variance to trajectory distributions and autoregressive state transitions.

  • Supporting lemmas: The appendices define total variation, Hellinger, KL, and χ2 divergences and state inequalities relating these measures.These relationships support later changes of measure and policy-distance arguments.
  • Supporting lemmas: A change-of-measure lemma provides bounds for expectations under two probability distributions.The result is used with trajectory-level functions in the lower-bound analysis.
  • Heterogeneity: Total expert heterogeneity is characterized through the expected conditional variance of rewards under the policy.The derivation expands conditional reward variance and uses deterministic autoregressive state transitions.
  • Variance bounds: The appendix uses induction, expectation identities, and a concentration inequality for nonnegative random variables to derive variance bounds.The displayed intermediate steps include an induction over horizon steps and a bound based on mean and variance.
  • Auxiliary inequalities: The supporting calculations establish derivative and monotonicity bounds needed for the auxiliary inequalities.These steps include bounding a second derivative and comparing increasing functions of a random variable.

A.2. Lower bound on 𝜎𝑒: Proof of Lemma 5.3

This appendix derives lower bounds tied to the variance of expert rewards under policies near a base policy. It constructs an autoregressive example showing the variance scaling is attainable and extends the argument through prompt partitions and concentration.

  • Lower-bound setup: For any expert policy within a KL neighborhood of a base policy, the appendix develops a lower-bound framework for expert reward variance.The argument relates policy divergence, trajectory rewards, and variance under the base and expert policies.
  • Tightness construction: An autoregressive two-branch construction achieves base-policy variance σ_b^2 = p(1 − p)H^2, with every value up to H^2/4 attainable.The construction uses a branch yielding reward 1 at every step and another yielding reward 0 forever.
  • Multiple prompts: The proof extends single-prompt reasoning to multiple prompts by partitioning the prompt space and aggregating prompt-level variance scores.Median-based partition arguments yield bounds involving the median expert variance.
  • Concentration: A Paley-Zygmund argument shows that a substantial fraction of prompts can have expert variance above a constant threshold.The cited result states that at least 3|𝒳|/5 prompts satisfy the indicated variance condition.
  • Verifier-free lower bound: The resulting instance-dependent lower bound is stated for verifier-free algorithms and is formalized after introducing the required notation and partition score.The appendix notes that the bound scales with a median variance quantity rather than only the mean variance.

A.3.3. Lower bounds on verifier-free approaches

This appendix constructs hard instances for verifier-free learning under constrained reward classes and analyzes their policy and reward properties. It also gives an anti-concentration-based construction of a competing policy with positive rewards and no worse value.

  • Reward class: The lower-bound construction uses half-bi-level rewards, whose trajectories reach a bi-level by time floor(H/2).After that point, rewards remain 1 for the rest of the trajectory.
  • Reward-class caveat: Half-bi-level rewards can still induce high policy variance despite restricting all bi-levels to the first half of the horizon.The appendix explicitly records this as a remark about the reward class.
  • Hard-instance construction: The hard-instance theorem constructs alternate expert-policy and reward families with bounded χ2 divergence and controlled reward variance.The family is indexed by binary vectors and is designed for verifier-free lower bounds.
  • Relation to prior work: The appendix compares its construction with prior work, noting that earlier bounds assume either a single prompt or allow the initial-state distribution to change.The present construction addresses that distinction while preserving the initial-state distribution.
  • Reward transformation: A reward transformation replaces early minimal states with terminal-depth states while preserving the relevant expected reward and variance relationships.The construction is feasible because every minimal state occurs by time H/2.
  • Anti-concentration construction: Under anti-concentration, the constructed policy has strictly positive trajectory rewards, no worse value than the expert benchmark, and a bounded density ratio relative to the base policy.The policy is formed from higher-reward trajectories and agrees with the base policy after a specified horizon.

A.4.2. Analysis of Algorithm 1: Proof of Theorem 5.7

The analysis establishes verifier-based learning guarantees under anti-concentration and contrasts its scaling with verifier-free methods. It also develops verifier-learning guarantees using multiclass classification and verifier queries.

  • Setup: Verifier-based learning assumes noisy reward annotations from trajectories sampled from the base policy and analyzes a pessimism-based learner over a reward class.The formal setup allows independent Gaussian trajectory-level noise with variance bounded by σ^2.
  • Verifier-based guarantee: The verifier-based learner’s suboptimality is bounded with high probability under anti-concentration and the stated reward-estimation assumptions.The theorem’s guarantee is stated relative to a comparator policy and depends on generalization of reward estimation.
  • Scaling comparison: When base-policy reward variance scales as Ω(H), verifier-free lower bounds scale as Hlog(|Π|)/n, while anti-concentration yields a verifier-based upper bound Hlog|ℛ|/n.The bounds are stated with respect to an expert in an O(1)-χ2 neighborhood of the base policy and with constant probability for the verifier-based result.
  • Verifier accuracy: The resulting reward estimator has a high-probability accuracy guarantee obtained through multiclass empirical risk minimization.The construction relates reward-estimation error to classification error and uses a graph-dimension sample-complexity bound.
  • Verifier accuracy: A verifier can locate the first positive point of a bi-level reward using binary search, requiring n⌈log2(H)⌉ queries for n trajectories.This converts reward learning into multiclass classification over H+1 possible locations.

C. Additional Experiments in the Didactic Setup

The didactic experiments vary base-policy heterogeneity and test-time horizon, comparing supervised trace fitting with reinforcement learning guided by a trained verifier. Verifier behavior reflects both improved trajectory coverage and increasing multiclass difficulty.

  • Setup: The planted subsequence setup uses length-5 random prompts, an unknown mapping g(x)=2x+5, and a bi-level reward for matching the gold subsequence.Performance is normalized across horizon H values by the maximum attainable reward.
  • Setup: Base-policy heterogeneity is controlled by mixing procedural policies with γ∈{5, 10, 20, 50, 100, 500}.Larger γ concentrates behavior near the gold subsequence before padding-token generation, while smaller γ permits multiple attempts.
  • Training: For each token budget H, experiments train SFT on H-token traces and RL against a verifier trained as an H+1-way classifier.The RL runs use the same compute budget and initialize from the base policy.
  • Results: With n=2^14 fixed, verifier accuracy initially improves with horizon as higher-reward trajectories become better covered, then drops as classification hardness increases.The experiment attributes the later decline to the growing number of classes in the verifier’s multiclass problem.
  • Results: Verifier accuracy is poor on the learned policy’s distribution because the learned policy shifts away from the base-policy distribution, increasing susceptibility to reward hacking.The figure compares verifier accuracy on both the base-policy distribution and the policy learned with RL.

D. Additional Experiments on MATH

The MATH experiments train SFT and verifier-guided RL on MATH training questions and evaluate on MATH500. They also examine verifier accuracy as data scales for Llama3-3B and 8B models.

  • Setup: MATH experiments use training-set questions for training and MATH500 for evaluation, varying data budget n and compute budget H.SFT uses search traces, while verifier training uses samples from the base LLM.
  • Verifier accuracy: The trained verifier is evaluated as data scales for Llama3-3B and 8B models.The verifier is trained with 0/1 rewards using a model of the same size as the policy.
  • Results: The larger model generalizes better across all data budgets, while both model sizes improve at the same rate as n increases.This is the reported trend in Figure 13’s verifier-accuracy experiment.
  • SFT traces: Sequential-revision SFT traces contain initially incorrect answers followed by revised responses on elementary arithmetic and geometry problems.The examples illustrate the trace format used for SFT rather than a quantitative performance comparison.
Loading 2502.12118v2…