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 whether verifier-free trace distillation can scale test-time compute as effectively as verifier-based reinforcement learning and search. It theoretically compares the approaches and shows that, under heterogeneous and anti-concentrated base-policy rewards, verification scales better and the performance gap grows with compute.

  • Problem

    It remains unclear how to scale test-time compute efficiently between verifier-based methods and verifier-free distillation or cloning of expert traces.

    Source: §1 · p. 2, §8 · p. 16

  • Method

    The paper theoretically compares verifier-based RL and search with verifier-free approaches under heterogeneous base-policy rewards formalized through anti-concentration.

    Source: §1 · pp. 2–3

  • Results

    Verifier-based methods outperform verifier-free methods at fixed test-time budgets, with suboptimality scaling as Ω(H/√n) versus 𝒪(H/n) for a simple verifier-based method.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Without verification, learning algorithms may not scale efficiently to large test-time budgets compared with a simple verification-based approach.

    Source: §8 · p. 16

    The analysis focuses mainly on bi-level rewards and does not compare sparse and dense verification or extend fully to long-context test-time scaling beyond 32k tokens.

    Source: §8 · p. 17

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 argues that verifier-based methods scale test-time compute more effectively than verifier-free trace distillation under realistic heterogeneity and anti-concentration in pretrained LLMs. Theory and experiments show that this advantage grows with test-time compute and training data, motivating verification or rewards during finetuning.

1. Introduction

  • The motivation is that high-quality expert data is expected to diminish by 2028, while improving LLM performance often requires more data, making test-time compute an alternative scaling strategy.Test-time methods search or refine outputs to find better responses, typically producing longer answers within a token budget.Source: §1 · p. 2
  • The separation is analyzed by finetuning a base LLM using expert traces for verifier-free methods versus reward annotations on sampled responses for verifier-based methods.The setup measures test-time compute by the token budget H, gives verifier-free methods at most n correct expert traces, and lets verifier-based methods query rewards on n base-policy samples.Source: §1 · p. 2
  • The theoretical advantage requires a heterogeneous reward distribution with anti-concentration: varied correct traces coexist with nontrivial probability of sampling above-mean rewards.Heterogeneity provides coverage across correct sequences of varying lengths, while anti-concentration places mass on traces rewarded above the base policy’s mean.Source: §1 · pp. 2–3, Figure 2 · p. 3
  • Verifier-based RL and search outperform any verifier-free method at fixed test-time budget, with the performance gap widening as compute and training data scale.The theory bounds verifier-free suboptimality by Ω(H/√n), versus O(H/n) for a simple verifier-based method.Source: §1 · p. 3

Empirical results corroborating theory.

  • Experiments on 3B/8B Llama models and S1 show that verifier-based methods outperform verifier-free baselines across test-time budgets, especially for more heterogeneous base models.The studies also find that common pretrained LLMs exhibit the heterogeneity and anti-concentration assumed by the theory.Source: Empirical results corroborating theory · pp. 3–4

Implications and takeaways.

  • The results imply that verifier-based methods scale better as test-time budgets increase, and scaling verifier-finetuning prompts with the token budget can further amplify the gap.Verifier-free methods can work well when heterogeneity is small, but the paper argues that low heterogeneity is uncommon in modern LLMs.Source: Implications and takeaways · p. 4

2. Related Work

Prior work scales test-time compute through learned or wrapped search, while this paper instead distinguishes methods by access to reward signals during training or inference. It groups verification-based approaches together, contrasts them with reward-free trace distillation, and studies realistic conditions under which verification is advantageous.

Related Work

  • Test-time compute scaling has used learned search or refinement procedures and LLM-wrapped search with trained verifiers, but this paper focuses on reward access instead.The reward-access distinction is orthogonal to whether search is learned or externally wrapped.Source: §2 · p. 4
  • Verification-based methods include outcome-reward training, trained-verifier search, verification-guided RL, value-function conversion, and generative or implicit verification within one LLM.The paper groups these approaches as VB methods and argues that querying verifiers or rewards is critical for test-time scaling.Source: §2 · p. 4
  • Reward-free SFT methods distill heterogeneous search or reasoning traces with varying token counts, making generalization difficult as test-time budgets scale.This limitation is associated with prior findings [35] [69] and systematic studies [10], while some recent results use excessive data subsampling [43] [74].Source: §2 · p. 4
  • Unlike approaches assuming a verification-generation gap [58] or correctness of the most likely solution [28], this paper derives such a gap under weaker, realistic pretrained-LLM conditions.It does not assume that learning to verify is easier than learning to generate the correct trace.Source: §2 · pp. 4–5

3. Notation and Preliminaries

This section formalizes language generation as a token-level finite-horizon MDP with binary rewards, defining states, transitions, policies, and solution traces. It also establishes notation for asymptotic bounds, integer sets, and probability measures.

Notation

  • The section uses standard big-oh and soft big-oh notation, denotes {1, ..., n} by [n], and writes Δ(𝒮) for all measures over a set 𝒮.It defines a = Õ(b) using a logarithmic-polynomial factor and a ≲ b when a = O(b).Source: §3 · p. 5

Preliminaries

  • Language generation is modeled as a token-level MDP ℳ(𝒮, 𝒜, r, H) with binary rewards and horizon H representing the token budget, following prior work [32] [53].The reward function is r: 𝒮 × 𝒜 → {0, 1}.Source: §3 · p. 5
  • Each state concatenates the input problem with previously generated tokens, and the environment deterministically appends the newly produced token to form the next state.Initial problems x ∈ 𝒳 are sampled from distribution ρ, with s_h = (x, a_1, ..., a_{h−1}).Source: §3 · p. 5
  • A policy π maps states to token distributions, while d^π_h denotes the state distribution it induces at time h.At each state, π_h produces a distribution over tokens in 𝒜.Source: §3 · p. 5
  • A solution trace is a rollout τ = (x, a_1, ..., a_H) through the MDP, with total reward defined as the sum of per-token rewards.The passage defines r(τ) = ∑ over the rewards collected along the horizon.Source: §3 · p. 5

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

The section defines effective test-time scaling as maximizing success within a fixed token budget while balancing token-efficient guessing against costly repeated attempts. It formalizes this with bi-level rewards and an asymptotic comparison in which higher scaling exponents indicate greater compute savings.

Effective test-time scaling

  • Effective scaling balances low-token guessing against sequential re-attempts to maximize successes within a fixed test-time compute budget.The goal is to answer more questions as the allowable output-token budget grows, requiring efficient asymptotic scaling.Source: §4 · p. 5

Reward formulation

  • Finetuning methods are evaluated under rewards that jointly capture solution accuracy and how quickly, in output tokens, the LLM finds a solution.The base LLM is modeled as an autoregressive policy, with test-time compute represented by a maximum output length H.Source: §4 · p. 5

Bi-level reward

  • Bi-level rewards remain 0 until a correct solution appears, then become 1 and stay 1 regardless of future actions.This binary, non-decreasing structure rewards finding correct solutions as early as possible within the horizon.Source: §4 · pp. 5–6, Figure 3 · p. 5

Practical objectives

  • Length penalties [2] and curricula encourage shorter solution traces, while bi-level rewards provide a formal model of this objective.These practical methods may not directly maximize bi-level reward but implicitly or explicitly seek solutions in fewer tokens.Source: §4 · p. 6

Asymptotic test-time compute scaling

  • The asymptotic definition compares algorithms by H^α, where a larger α means succeeding with approximately H^α less average compute as the test-time horizon H grows.The comparison fixes a bi-level reward, base policy, horizon H, and data budget n = Ω(H).Source: §4 · p. 6

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

The theory shows that, under heterogeneous and anti-concentrated base-policy distributions, verifier-based methods scale test-time compute asymptotically better than every verifier-free method. Verifier-free cloning incurs horizon-dependent lower bounds, whereas verification achieves smaller suboptimality by identifying covered high-reward traces.

5.1. Lower Bounds for Verifier-Free Expert Cloning

  • Verifier-free performance depends on cloning an expert whose correct traces may vary in token efficiency, and practical rejection-sampled or distilled datasets can therefore induce heterogeneous experts.The theory constrains experts to the highest-reward policy within a χ2-divergence ball Πκ around the base policy.Source: §5 · pp. 6–7, §5.1 · p. 8

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

  • Theorem 5.1 shows that for any bi-level reward and sufficiently large data budget, some base policy admits a verifier-based method scaling test-time compute by ˜Ω(H) relative to every verifier-free method.The comparison uses n expert-policy rollouts for VF methods and n reward-annotated base-policy rollouts for VB methods.Source: §5 · p. 7
  • When base-policy traces are sufficiently heterogeneous, any verifier-free method has suboptimality scaling as H/√n, while a simple verifier-based method achieves H/n.The VB guarantee requires the base policy to cover some high-reward traces with constant probability and the reward distribution to be heterogeneous rather than sharply concentrated.Source: §5 · p. 7

5.1. Lower Bounds for Verifier-Free Expert Cloning

  • Theorem 5.4 establishes an information-theoretic lower bound showing that finite expert data cannot resolve alternate experts, yielding verifier-free suboptimality proportional to expert heterogeneity divided by √n.When base-policy heterogeneity scales as Ω(H), the lower bound grows as Ω(H/√n), even with known trivial transition dynamics.Source: §5.1 · p. 8

5.2. A Simple Verifier-Based Algorithm

  • Algorithm 1 trains a verifier on sparse 0/1 reward annotations from base-policy traces, then optimizes a pessimistic verifier-based reward without requiring an expert policy.This formalizes verification-based approaches such as outcome-reward RL and verifier-guided search.Source: §5.2 · p. 9
  • Anti-concentration ensures constant-probability coverage of traces whose rewards exceed the base policy’s mean, allowing verification to discover high-reward policies despite high heterogeneity.Unlike heterogeneity, anti-concentration concerns the reward distribution’s shape or CDF and can hold for heterogeneous pre-trained LLMs.Source: §5.2 · p. 10
  • Theorem 5.7 bounds verifier-based suboptimality by O(H log(|ℛ|/δ)/n) without direct dependence on base-policy heterogeneity, yielding O(1) suboptimality when n = Ω(H).This contrasts with verifier-free suboptimality of Ω(H) under the same scaling regime and heterogeneous conditions.Source: §5.2 · p. 11
  • Theorem 5.8 combines the bounds to show VB dominates VF under heterogeneous, anti-concentrated base policies; maintaining an O(1) gap to the best expert as H grows implies solving new problems, not merely shortening solutions.The best expert’s performance can improve with H by solving additional questions, while VF retains horizon-dependent suboptimality.Source: §5.2 · pp. 11–12

6. Illustrating Theory in Practice

Didactic experiments validate the theory: verifier-based RL scales better than verifier-free SFT as test-time compute and data increase, especially with heterogeneous base policies, while reduced heterogeneity can reverse the advantage.

Didactic setup

  • The didactic task uses contextual planted subsequences, with normalized cumulative bi-level reward enabling comparisons across response horizons H.Correctness requires a gold contiguous subsequence, and performance is normalized by the maximum reward H−4.Source: §6 · p. 12

Base policy and training methods

  • The experiment constructs heterogeneous base policies by finetuning GPT2-xl on mixtures of procedural policies with varying γ, then compares verifier-free SFT with verifier-based RL.SFT imitates rejection-sampled correct traces, whereas RL trains a GPT2-xl verifier to predict bi-level rewards.Source: §6 · pp. 12–13

Results: scaling test-time compute

  • As test-time token budget H increases, RL nearly matches the expert while SFT’s gap from the expert worsens; scaling reward-model data makes the RL–SFT gap grow superlinearly.The results match the predicted H-dependent verifier-free suboptimality and show slight high-H RL degradation from verifier inaccuracy and reward hacking.Source: §6 · p. 13

Scaling data budget

  • With test-time compute fixed at 26 tokens, increasing data improves both methods, but RL’s performance curve has a much higher slope than SFT’s.This agrees with the theory that verifier-based methods are more sample efficient than verifier-free methods.Source: §6 · p. 13

Effect of policy heterogeneity

  • Reducing base-policy heterogeneity shrinks SFT’s suboptimality gap and can make verifier-free SFT outperform verifier-based RL.The reversal is attributed primarily to declining verifier accuracy, with anti-concentration potentially unsatisfied in this regime.Source: §6 · p. 13

7. Results: Large-Scale Math Reasoning

On MATH, verifier-based best-of-N search substantially outscales verifier-free supervised finetuning in test-time compute and data efficiency, with the gap growing as both budgets increase. Verification is especially advantageous for heterogeneous, anti-concentrated base-model trace distributions, although verifier-free SFT can win on low-heterogeneity problems.

Main MATH results

  • BoN scales test-time compute 8× over SFT, improves data efficiency 6×, and its accuracy gap grows superlinearly in log H as both budgets scale.At fixed n=2^14, BoN achieves the 8× test-compute scaling; at fixed H=2^12 tokens, it achieves the 6× data-efficiency gain.Source: Figure 7 · p. 14, §7 · p. 14

Comparison with s1

  • On MATH, verifier-based BoN outperforms verifier-free s1 distillation with budget forcing when training data is fixed and test-time compute is matched.BoN samples short responses and selects the best using a trained outcome verifier, whereas s1 was trained by verifier-free supervised distillation.Source: §7 · p. 14, Figure 8 · p. 15

Heterogeneity

  • Verifier-free SFT outperforms BoN on low-heterogeneity problems, but BoN dominates at higher heterogeneity because SFT fails to generalize and mainly memorizes responses.BoN can suffer from limited coverage or verifier inaccuracies when heterogeneity is small; higher heterogeneity is common, so VB performs better on average.Source: §7 · p. 15, Figure 9 · p. 15

Anti-concentration

  • Base LLMs exhibit heterogeneous, anti-concentrated reward distributions: roughly 25% of correct traces exceed the mean-reward threshold on both easy and hard MATH problems.For κ=0.5, this implies an anti-concentration coefficient of approximately acc. × 0.25, enabling BoN to cover increasingly strong correct answers with more test compute.Source: §7 · pp. 15–16, Figure 10 · p. 16

Takeaways

  • The experiments support the theory that verifier-based methods outperform verifier-free methods at fixed test-time compute, with the advantage widening as training data and test budget increase.The reported exception is the low-heterogeneity regime, where verifier-free methods can outperform verifier-based ones.Source: §7 · p. 16

8. Discussion, Limitations, and Future Work

The paper formalizes asymptotic test-time-compute efficiency and proves that verification-based learning can scale more effectively than verifier-free learning under heterogeneous base policies and weak anti-concentration. Experiments on MATH, AIME, and a controllable didactic setting support these predictions, while future work targets richer verification regimes and longer contexts.

Discussion

  • The study formalizes test-time-compute efficiency using bi-level rewards and defines asymptotic scaling for comparing learning algorithms.These definitions address whether learned policies use increasing test-time budgets efficiently and continue improving as those budgets grow.Source: §8 · p. 16
  • Verification-based learning can scale efficiently to larger test-time budgets, whereas verifier-free methods may fail under heterogeneous base policies.No verifier-free algorithm can accurately learn experts within a χ2 ball around a heterogeneous base policy; under weak anti-concentration, a simple verifier-based algorithm can closely approximate the scaling expert.Source: §8 · p. 16
  • Theoretical conditions of base-policy heterogeneity and anti-concentration are observed in practice, linking the analysis to empirical behavior.The paper compares verifier-free and verifier-based predictions on MATH and AIME with the s1 model [43] and a sequential self-correction model [57], plus a controllable didactic setting.Source: §8 · pp. 16–17

Limitations and future work

  • Future work should compare sparse and dense verification, extend bi-level-reward analysis to generative rewards, and study verifier-based scaling beyond 32k-token contexts.The paper specifically highlights process-based rewards, generative rewards [77], and reinforcement learning with outcome or dense rewards as expensive long-context directions.Source: §8 · p. 17

Appendices … A.1. Useful Lemmas

Appendix A.1 collects technical lemmas relating probability divergences, change of measure, expert heterogeneity, and bounds for nonnegative random variables.

A.1. Useful Lemmas

  • Lemma A.1 establishes inequalities connecting total variation, Hellinger, and χ² divergences for probability measures.The appendix defines total variation and gives the stated divergence comparisons.Source: §A.1 · p. 24
  • Lemma A.2 provides a change-of-measure result for arbitrary functions over a measurable space [19].It applies to probability distributions P and Q and functions h: 𝒴→R.Source: §A.1 · p. 24
  • Lemma A.3 equates total expert heterogeneity with expected conditional reward variance under a policy.The proof expands conditional variance across autoregressive states, uses a zero conditional-expectation term, and aggregates over horizons and prompt distributions.Source: §A.1 · pp. 24–25
  • Lemma A.4 derives a bound for an almost surely non-negative random variable using its mean, variance, and a nonnegative parameter.The argument uses monotonicity of auxiliary functions and bounds a second derivative.Source: §A.1 · p. 26

A.2. Lower bound on 𝜎𝑒: Proof of Lemma 5.3 … A.3.2. Interpretations of, and bounds on 𝐿⋆

The appendix establishes a lower bound on expert reward variance under KL proximity, shows this bound is tight up to constants, and develops the complexity measure L⋆ used for instance-dependent verifier-free lower bounds. It also provides bounds and interpretations of L⋆ based on prompt partitions and the distribution of per-prompt variances.

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

  • The lower-bound proof relates expert and base-policy reward variances through KL and χ2 divergence, using a change-of-measure argument on pairs of trajectories.The argument uses H(·,·) ≤ D_KL(·,·), i.i.d. base trajectories, the KL chain rule, and bounded reward differences.Source: §A.2 · p. 27
  • Lemma 5.3’s lower bound is tight up to constants in a two-branch autoregressive MDP where one branch yields reward 1 and the other reward 0 at every step.For the base policy, σ_b^2 = p(1 − p)H^2, and varying p over [0, 1/2] realizes every σ_b^2 ≤ H^2/4.Source: §A.2 · p. 28

A.3. Proof of Theorem 5.4

  • Theorem 5.4 is prepared through a formal appendix statement and newly introduced notation before its proof is developed.The supplied passages identify this as the setup for the main theorem proof but do not state the theorem’s quantitative conclusion.Source: §A.3 · p. 29

A.3.1. Measure of complexity: 𝐿⋆

  • The complexity measure L⋆ is defined using an arbitrary partition of the prompt space into k disjoint parts and corresponding optimal partition subsets.The construction is stated in terms of the partition family {𝒳⋆_i} and is interpreted through per-prompt variance quantities.Source: §A.3.1 · p. 29

A.3.2. Interpretations of, and bounds on 𝐿⋆

  • For powers of two, L⋆ satisfies a lower bound across partition sizes, including L⋆_k′ ≥ 1 when k/2 ≤ k′ ≤ k.The proof partitions high-variance prompts into singleton parts, uses part scores s(X), and relates their median to the median per-prompt expert variance.Source: §A.3.2 · p. 29
  • A partition-merging argument shows that reducing the number of parts preserves a proportional lower bound on the sum of the worst part scores.Dissolving the bottom k − k′ parts and merging them yields a partition whose k′/4 worst scores sum to at least (k′/k)L⋆.Source: §A.3.2 · p. 30
  • Paley–Zygmund implies that at least 3|𝒳|/5 prompts satisfy σ_e,x ≥ 1, yielding the corollary L⋆_k ≥ cσ_e for an absolute constant c > 0.These results support an instance-dependent lower bound on the suboptimality of any verifier-free algorithm.Source: §A.3.2 · p. 30

A.3.3. Lower bounds on verifier-free approaches … A.4.1. Understanding the anti-concentration assumption

The appendix develops lower-bound constructions for verifier-free learning and interprets the anti-concentration assumption through candidate policies related to the base policy. It establishes feasibility, variance, value, and density-ratio properties, including for policies extended with the base policy beyond a specified horizon.

A.3.3. Lower bounds on verifier-free approaches

  • Half-bi-level rewards place every bi-level by time ⌊H/2⌋, yet can still induce high-variance policies and support alternate hard expert-policy and reward families.Theorem A.10 constructs these families under a uniform prompt distribution, with feasible policies, controlled variance, and a fixed initial-state distribution; related work [19] requires stronger single-prompt or altered-distribution assumptions.Source: §A.3.3 · pp. 30–32

A.3.4. Construction of policy class Π′ and reward class ℛ′

  • The constructed policy class Π′ contains exponentially many separated feasible policies, enabling a verifier-free lower-bound argument through indistinguishable policy–reward alternatives.The construction uses binary-indexed policies and rewards with bounded χ2-divergence, separated value gaps, controlled variance, and membership in an enlarged KL neighborhood of the base policy.Source: §A.3.3 · pp. 33, 35, §A.3.4 · pp. 35–36

A.4.1. Understanding the anti-concentration assumption

  • Anti-concentration measures the base policy’s probability of sampling rewards above their mean by a standard-deviation-scaled margin, while the corresponding deviation characterizes the best value in a χ2 ball.Lemma A.19 characterizes the optimum within the χ2 neighborhood; Lemma A.21 constructs a policy supported on sufficiently high-reward trajectories that is no worse than the expert and has bounded density ratio coverage.Source: §A.4.1 · pp. 36–37
  • For longer horizons, the high-reward policy can be extended beyond the anticoncentration horizon while retaining positive rewards and expert-level value guarantees.Lemma A.22 states that for every H > h0, an extended policy satisfies analogous conditions when deployed at horizon H.Source: §A.4.1 · p. 39
  • The proof extends π_c through horizon h_0 and then follows π_b, producing a policy that agrees with the base policy after h_0.The construction assumes π_b is defined for every t ∈ N.Source: §A.4.1 · p. 39
  • The H-horizon supremizing policy can be truncated to h_0, losing at most H−h_0 in value, while remaining a candidate in Π_κ^h0.This yields the stated lower-bound relation involving J_r^H(π) and the horizon difference H−h_0.Source: §A.4.1 · p. 39
  • Because the extended policy and π_b agree after h_0, the worst-case density ratio cannot increase as H grows beyond h_0.The proof also notes that π_c is supported only on trajectories with strictly positive reward, which collect one reward unit at every t > h_0.Source: §A.4.1 · p. 39

A.4.2. Analysis of Algorithm 1: Proof of Theorem 5.7 … B. Additional Related Work

The appendices formalize verifier-based guarantees, establish matching lower- and upper-bound scaling under anti-concentration, and analyze verifier accuracy and single-instance lower bounds. Related work distinguishes verification-enabled test-time scaling from heterogeneous verifier-free trace imitation, whose generalization is theoretically poor.

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

  • Theorem A.23 analyzes Algorithm 1 for a bi-level reward with an anti-concentrated base policy, noisy verifier annotations, and a reward class ℛvb containing the true reward.The annotations have the form y_i = r(τ_i) + Z_i, with independent standard-normal noise and trajectory-level variance at most 𝜎^2.Source: §A.4.2 · p. 39

A.4.3. Proof of Proposition 5.5

  • The proof derives a simultaneous generalization bound for all r′ ∈ ˆRγ using Bernstein concentration, a union bound over rewards in ℛvb, Lemma A.26, and solving a quadratic equation, with probability at least 1 − 2δ.Lemma A.27 is identified as a generalization bound for learning in L1-error, holding simultaneously for all r′ ∈ ˆRγ with probability 1 − 2δ.Source: §A.4.3 · pp. 41–42

A.5. Proof of Theorem 5.8

  • When 𝜎̃_b = Ω(H), verifier-free methods have suboptimality gap scaling Hlog(|Π|)/n, whereas anti-concentrated verifier-based learning achieves Hlog|ℛ|/n with constant probability as n = Ω(H).This combines the instance lower bound for verifier-free methods with the verifier-based upper bound used to prove Theorem 5.1.Source: §A.5 · p. 42

A.6. Analyzing Verifier Accuracy Under 0/1 Loss

  • Theorem A.28 shows that for any bi-level reward and base policy, an algorithm can learn a reward model using at most n reward-annotator queries with probability 1 − 𝛿.The construction sets γ = γstat so that the true reward belongs to the confidence set with probability at least 1 − 𝛿.Source: §A.6 · p. 42
  • For bi-level rewards, locating each trajectory’s first rewarding step by binary search uses n⌈log2(H)⌉ verifier calls and reduces reward estimation to multiclass classification.The classification label is the first horizon position where the reward becomes 1, or H + 1 if it remains zero throughout.Source: §A.6 · pp. 43–44

A.7. Proof of Theorem 5.4 for the single problem instance

  • The single-instance lower-bound proof constructs indistinguishable expert-policy and reward pairs, then applies Le Cam’s two-point argument with total-variation and Hellinger-distance bounds.It builds on the instance-dependent behavior-cloning lower bound in [19] and invokes the Hellinger tensorization property.Source: §A.7 · pp. 44–45

B. Additional Related Work

  • Related work separates verification-based scaling, which uses rewards or verifiers during training or search, from verifier-free imitation of heterogeneous search traces; the latter’s heterogeneity impedes supervised generalization.The paper uses a bi-level reward formulation to compare asymptotic test-compute efficiency and identifies varying trace lengths and token budgets as the source of verifier-free difficulty.Source: B. Additional Related Work · p. 46

C. Additional Experiments in the Didactic Setup

Additional didactic experiments use a generalized planted-subsequence task to compare SFT with verifier-guided RL across horizons and policy heterogeneity. Trained-verifier RL is primarily limited by verifier inaccuracies, especially off-distribution reward hacking as heterogeneity decreases.

Details on the setup

  • The didactic task plants the gold sequence defined by g(x)=2x+5 within length-H responses over vocabulary {0,...,30}, with normalized reward scaled by H−4.Inputs are length-5 sequences sampled from {1,...,10}; a response is correct when it contains the corresponding contiguous gold subsequence, and the bi-level reward records whether it has appeared.Source: C. Additional Experiments in the… · pp. 46–47
  • Base policies are created by fine-tuning GPT2-xl on mixtures of procedural policies with γ∈{5,10,20,50,100,500}, varying heterogeneity while approximately preserving average performance.As γ increases, procedural policies concentrate more strongly on the gold sequence and then emit padding tokens after completing it.Source: C. Additional Experiments in the… · p. 47

Experiment details

  • For each horizon, the experiments train SFT on H-token traces and REINFORCE-based RL against a verifier trained as an H+1-way classifier on base-policy samples.Both methods start from the base policy and use KL regularization; verifier data use n/log(H) prompts with log(H) binary-search queries, totaling n reward-annotator queries.Source: C. Additional Experiments in the… · p. 47

Accuracy of trained verifier

  • Verifier-guided RL mainly suffers from trained-verifier inaccuracy across horizons, while verifier accuracy improves initially with horizon before declining as multiclass classification becomes harder.The comparison uses RL with ground-truth staircase rewards as an upper bound; reduced base-policy heterogeneity improves in-distribution accuracy but worsens accuracy on the learned policy’s distribution, increasing reward-hacking susceptibility.Source: C. Additional Experiments in the… · pp. 47–48, Figure 12 · p. 48

D. Additional Experiments on MATH

On MATH, the experiments train SFT on sequential search traces and a same-sized verifier with 0/1 rewards, then evaluate on MATH500. Larger verifiers generalize better, while both model sizes improve at the same rate as training data increases.

Experiment details

  • The experiments train SFT on sequential search traces from MATH training questions and evaluate performance on the MATH500 benchmark.Each trace contains multiple response turns, with incorrect final-answer responses preceding the last turn; test-time SFT uses majority voting over sequential revisions.Source: D. Additional Experiments on MATH · pp. 48–49
  • Verifier training uses base-LLM samples with 0/1 rewards and cross-entropy loss, matching the policy model size.SFT and verifier training run for 10,000 iterations per instance with batch size 32, learning rate 1e-6, and weight decay 0.01.Source: D. Additional Experiments on MATH · pp. 48–49

Verifier accuracy

  • Larger verifier models generalize better across all data budgets, while Llama3-3b and 8b verifiers improve at the same rate as data scales.Figure 13 reports verifier test accuracy for Llama3-3b and 8b models as the data budget n increases.Source: D. Additional Experiments on MATH · p. 49, Figure 13 · p. 49

Related papers

Loading 2502.12118v2…