PaperlayerView exact revision on arXiv

Source-linked AI summary

Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning

Amrith Setlur, Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Eisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, Aviral Kumar

arXiv:2410.08146v1cs.LGcs.CL

TL;DR

Process reward models offer dense feedback for reasoning but are difficult to scale because per-step human labels are expensive and automatic approaches have delivered limited gains. The paper proposes process advantage verifiers that predict progress under a prover policy distinct from the base policy, and reports improved test-time search and online RL performance over outcome reward models.

  • Problem

    Per-step human annotations for process reward models are expensive, while automatically labeled process rewards have produced limited gains over sparse outcome rewards.

  • Method

    The paper trains process advantage verifiers to predict changes in future success likelihood under prover policies distinct from the base policy.

  • Results

    >8% higher accuracy and 1.5−5× greater compute efficiency are reported for PAV-based test-time search, while online RL gains 5−6× sample efficiency and >6% accuracy over ORMs.

  • Takeaways & Limitations

    Progress rewards from suitable complementary provers improve exploration and help discover better solutions during test-time search and online RL.

  • Takeaways & Limitations

    The paper does not yet provide an automatic way to design optimal provers for a sequence of changing base-policy iterates, and verifier fitting errors bound performance.

Abstract

from arXiv · show

A promising approach for improving reasoning in large language models is to use process reward models (PRMs). PRMs provide feedback at each step of a multi-step reasoning trace, potentially improving credit assignment over outcome reward models (ORMs) that only provide feedback at the final step. However, collecting dense, per-step human labels is not scalable, and training PRMs from automatically-labeled data has thus far led to limited gains. To improve a base policy by running search against a PRM or using it as dense rewards for reinforcement learning (RL), we ask: "How should we design process rewards?". Our key insight is that, to be effective, the process reward for a step should measure progress: a change in the likelihood of producing a correct response in the future, before and after taking the step, corresponding to the notion of step-level advantages in RL. Crucially, this progress should be measured under a prover policy distinct from the base policy. We theoretically characterize the set of good provers and our results show that optimizing process rewards from such provers improves exploration during test-time search and online RL. In fact, our characterization shows that weak prover policies can substantially improve a stronger base policy, which we also observe empirically. We validate our claims by training process advantage verifiers (PAVs) to predict progress under such provers, and show that compared to ORMs, test-time search against PAVs is $>8\%$ more accurate, and $1.5-5\times$ more compute-efficient. Online RL with dense rewards from PAVs enables one of the first results with $5-6\times$ gain in sample efficiency, and $>6\%$ gain in accuracy, over ORMs.

1. Introduction

The paper proposes process advantage verifiers (PAVs), which measure step-level progress under a distinct prover policy rather than correctness alone. Experiments show that PAVs improve exploration, accuracy, and efficiency in test-time search and online RL.

  • Motivation: ORMs provide sparse final-trace correctness signals, while PRMs provide intermediate feedback but require expensive step-level human annotations.Automatically scaling dense process rewards remains challenging.
  • Core insight: Per-step rewards should measure the change in future success likelihood before and after a step, corresponding to step-level advantages.This progress-based signal reinforces useful steps even when they occur in ultimately incorrect traces, supporting exploration.
  • Prover policies: Advantages from the base policy can be uninformative, so PAVs estimate advantages from a distinct prover policy instead.Overly capable provers may succeed from both good and bad steps, while weak provers resemble poor base policies.
  • Prover policies: Good provers are complementary to the base policy: their advantages contrast base-generated steps while remaining correlated with the base policy’s advantages.The characterized set can include provers weaker than the base policy.
  • Empirical results: >8% higher accuracy and 1.5−5× greater compute efficiency are achieved by beam search against PAVs versus ORM re-ranking at equal test-time compute.The workflow trains PAVs from prover seed traces and partial rollouts estimating prefix Q-values.

2. Preliminaries, Definitions, and Notation

The paper frames reasoning traces as deterministic MDP trajectories and defines outcome and process verifiers for improving a base policy. It also describes Best-of-K selection and PRM-based beam search.

  • Verifier definitions: A reasoning trace consists of multiple logical steps separated by a demarcation token; an ORM scores the final step, whereas a PRM scores each step.These definitions distinguish sparse outcome supervision from dense process supervision.
  • Problem setup: A response is modeled as a sequence of actions in a deterministic MDP, with each prefix serving as a state and the next reasoning step as an action.The base policy samples actions autoregressively from the current prefix.
  • Outcome evaluation: Final-answer accuracy is evaluated by matching the response’s final answer against the ground-truth answer with a regular expression verifier.The resulting outcome reward is used to train and evaluate outcome-based models.
  • Outcome reward models: An ORM predicts ground-truth response correctness from problem-response pairs collected with final-answer verification.ORM training data contains sampled responses and their verified outcomes.
  • Best-of-K: Best-of-K samples K responses from a base policy, scores them with an ORM, and returns the highest-scoring response.When the ORM matches the final-answer verifier, performance is called Pass @K and success probability is 1 − (1 − p_x)^K.
  • Process reward models: Standard PRMs score each intermediate action, often distinguishing correct steps from incorrect or irrelevant ones.Unlike ORMs, PRM training data conventionally requires expensive step-level human annotations; automated methods may use Q^π as a step score.
  • PRM beam search: In PRM beam search, each beam state produces C sampled actions, and only the top B successor states by process reward continue to the next step.The beam begins from the problem-only state.

3. How Should we Define Process Rewards and Why?

Effective process rewards should measure step-level progress rather than absolute value, and should be computed under a prover policy distinct from the base policy. The resulting advantage-based rewards improve exploration, online RL, and test-time search when the prover is sufficiently complementary to the base policy.

  • Process rewards as progress: Process rewards should measure progress toward a correct final answer, not merely the mathematical correctness or relevance of each individual step.Progress is represented by the change in success likelihood before and after a step.
  • Process rewards as progress: Advantages are preferable to absolute Q-values because they compare a step’s action value with the value of its preceding state, supporting exploration of progress-inducing actions.Q-values can mix action evaluation with the previous state’s value and favor high-likelihood states or trivial actions.
  • Prover policies: The process advantage A_μ should be computed under a prover policy μ distinct from the base policy π and combined with outcome rewards for online RL.Using the base policy’s own advantages does not provide a distinct learning signal, while prover advantages can supply dense step-level supervision.
  • Empirical effects: 10× more sample-efficient online RL is achieved with effective rewards Q_π + αA_μ than with outcome rewards alone in the didactic analysis.With prover strength γ = 10, the method reached 100% accuracy in 350 iterations, while only a prover-strength range of γ∈[8.0, 15.0] helped.
  • Empirical effects: 5× faster Pass @N growth is obtained after 100 training iterations with effective rewards, because the policy samples partially correct subsequences and complete solutions more often.Very weak or very capable provers did not improve the base policy beyond outcome rewards.
  • Prover policies: Complementary provers distinguish the base policy’s actions while remaining sufficiently aligned with its advantages; Best-of-K policies with K>1 provide a practical starting class.Too-large K can reduce distinguishability when the base policy already assigns high success probability to actions.

4. Results: Scaling Test-Time Compute with PAVs

PAVs scale test-time search by combining a base policy’s state value with progress advantages estimated under a prover policy. Across Gemma policies, this improves accuracy and compute efficiency over outcome-verifier search, with intermediate-strength or complementary provers performing best.

  • Method: PAV beam search combines the base policy’s Q-value with a prover’s advantage estimate to select intermediate reasoning steps.The effective reward is Q_π + αA_μ, with candidates selected using both components.
  • Results: 8−10% higher accuracy and 1.5−5× greater compute efficiency are reported for PAV search over ORM-based best-of-N search.The comparison covers Gemma 2B, 9B, and 27B SFT policies.
  • Results: 8× compute-efficiency scaling over Q_π-only beam search shows that prover advantages improve search beyond state-value prediction alone.At N=128, PAV-as-ORM also gains 4% over ORM-only re-ranking for Gemma 9B.
  • Prover policy: Bo4 is the dominant prover for a Gemma-2B base policy, while both Bo2 and Bo32 are suboptimal across beam sizes.The results indicate that an intermediate-strength prover is preferable to one that is too weak or too strong.
  • Prover policy: A weaker 9B prover outperforms the stronger 27B prover for the Gemma-27B base policy, consistent with complementary prover signals improving action discrimination.For Gemma 2B and 9B bases, the 9B and 27B provers are most effective, respectively.
  • Exploration: PAV search improves exploration efficiency by balancing high-value states with progress made by prior actions, increasing Pass@N over typical PRMs.The effective reward trades off exploiting promising prefixes against exploring new prefixes where progress can be made.
  • Training data: PAV training data uses seed rollouts for prefix coverage and Monte Carlo partial rollouts to estimate Q-values at each prefix.At low budgets, greater coverage helps; at higher budgets, more Monte Carlo rollouts reduce label noise.

5. Results: Scaling Dense-Reward RL with PAVs

PAVs provide dense, progress-based rewards for online RL, improving sample efficiency, accuracy, and downstream test-time exploration over sparse ORM rewards. The gains include faster learning and broader discovery of solutions to hard novel problems.

  • Method: PAV-RL uses the effective reward Q_π + αA_μ as a dense per-step signal, whereas ORM-RL uses only outcome rewards.The comparison is conducted on Gemma 2B and 9B SFT policies initialized with rejection finetuning.
  • Results: PAV-RL is more than 7% better than ORM-RL in test accuracy and 6× more sample efficient.PAV-RL improves the RFT policy by 11% for Gemma 2B and 15% for Gemma 9B.
  • Test-time re-ranking: PAV-RL yields higher Pass@N than ORM-RL for every N≤128 and improves at a faster rate as N increases.For N≥64, ORM-RL falls below the SFT policy, which the paper associates with less diverse candidates.
  • Exploration: PAV-RL promotes efficient exploration by up-weighting steps that make progress even when their complete rollout is incorrect.This increases coverage of useful steps and helps the policy discover solutions to hard novel problems.
  • Exploration: Combining PAV-RL with beam search solves substantially more new problems at N=16 or 32 than the SFT policy solves at N=256.The comparison concerns problems remaining unsolved by Best-of-256 over the base SFT policy.

6. Related Work

Prior work largely uses outcome or base-policy step rewards, while this paper argues that progress measured under a distinct prover policy better supports exploration and learning.

  • Outcome reward models provide sparse final-trace correctness signals, while process reward models offer denser step-level feedback.
  • The paper questions using only base-policy Q-values or advantages and instead measures advantages under a different prover policy.
  • Unlike related methods that use first-pit detection for preference data, this work uses automated data collection to train process advantage verifiers.
  • Base-policy advantages can be uninformative under weak policies, and using them in reinforcement learning can yield updates equivalent to outcome-reward optimization.

7. Discussion and Conclusion

The paper concludes that process rewards defined as advantages under a prover distinct from the base policy improve exploration, search efficiency, and online-RL outcomes. It also identifies prover design and verifier fitting as open limitations.

  • Process rewards based on a distinct prover policy improve exploration for base-policy steps during test-time search and online reinforcement learning.
  • 1.5−5× compute-efficiency improvement and over 8% search-accuracy improvement were observed against trained PAVs compared with best-of-N using an ORM.
  • 5−6× sample-efficiency improvement and over 6% accuracy gain were observed when online RL used dense rewards from trained PAVs.
  • The paper characterizes good provers as producing advantages that contrast base-policy steps while remaining aligned with the base policy.
  • Automatically designing strong provers across changing base-policy iterates remains unclear, and verifier fitting errors upper-bound the method’s performance.

Appendices

Related work spans outcome verifiers, process-level credit assignment, online RL, and imitation through RL. The paper distinguishes its prover-policy advantages and reports stronger efficiency gains than prior PRM results.

  • Outcome reward models: Outcome reward models rank multiple base-policy solutions at test time by assessing full-response correctness.
  • PRMs and credit assignment: Process reward models use human or automated labels to estimate step-level values, while this work adds prover-policy advantages as rewards.
  • Online RL for math reasoning: Prior math-reasoning online-RL studies experimented with dense and sparse rewards, but reported small PRM gains relative to outcome supervision.
  • The didactic setup illustrates samples from very strong and relatively weaker policies using a planted sub-sequence.
  • Online RL for math reasoning: 5−6× sample-efficiency improvement and over 6% performance gain are reported for online RL using trained PAVs with outcome rewards.
  • Connections to imitation learning through RL: The paper relates its approach to methods mixing potential functions from different policies and to guide-policy rollouts for imitation learning.

B. Didactic Analysis

The didactic analysis studies policy-gradient learning on a sparse planted-sequence task, comparing outcome rewards with effective step rewards that combine base-policy values and prover advantages.

  • The experiment uses length-10 sequences over a 15-token vocabulary with an end-of-sequence token and masked subsequent tokens.
  • The terminal reward is 1 exactly when the unknown planted sequence appears in a sampled trajectory, and 0 otherwise.
  • Increasing γ improves the prover policy’s performance toward 1, and experiments assume nearly oracle ground-truth advantages and Q-values.
  • The comparison trains policies with either only the outcome reward, equivalent to Qπ step rewards, or the effective reward Qπ + αAμ.
  • Both reward settings use 10,000 iterations, batch size 64, and learning rate 1e−3; Pass@N is evaluated from independently sampled trajectories.

C. Additional: Experiments on Test-time Search with PAVs

These experiments test whether effective rewards combining Qπ with prover advantages better predict final outcomes during partial rollouts. The effective reward outperforms Qπ across rollout steps, especially early ones, supporting its use for finite-capacity beam search.

  • Experimental setup: The effective-reward coefficient α is selected on a held-out validation set, with α=0.5 for Gemma 2B and 9B and α=0.2 for Gemma 27B.
  • Predictive power: Effective reward Qπ + αAμ has lower final-outcome classification error than Qπ across all rollout steps.Both rewards become more predictive as the base policy is rolled out, but the effective reward dominates at intermediate steps.
  • Predictive power: The effective reward is especially informative during earlier rollout steps, where partial-rollout success is harder to predict.This provides a rationale for re-ranking partial rollouts with a finite-capacity beam.

D. Details on Collecting Data and Training PAVs

PAV training data combines prover-generated seed traces with partial rollouts used to estimate prefix Q-values. The workflow uses coverage strategies, Monte Carlo estimation, and a best-of-K transformation to construct effective rewards.

  • Coverage strategy: The first-pit strategy improves coverage by locating low-Q states within partial rollouts that begin from high-Q states.Figure 11 compares beam-search performance for PAVs trained with random versus first-pit seed rollouts.
  • Data collection: Seed traces are sampled from the prover, and partial rollouts from each seed estimate the Q-value at every prefix.The prescribed workflow also specifies favorable ratios between seed and partial rollouts.
  • Data collection: The dataset contains over 300,000 prefix–Q̂π-value pairs collected for training PAVs.Q̂π denotes a Monte Carlo estimate of the base policy’s Q-value under π.
  • PAV training: Q̂π-values are partitioned at 0.5, followed by class-balanced sampling across the two value buckets during finetuning.
  • Effective rewards: For a best-of-K prover, QBoK(π)(s,a) is computed as 1 − (1 − Qπ(s,a))^K, enabling effective-reward construction.

E. Additional: Experiments on RL Training with PAVs

The appendix details RL training, theoretical assumptions, and the natural-policy-gradient implementation used to optimize PAV-based rewards. It also records technical conditions governing the policy update and its least-squares formulation.

  • RL training: RL initializes Gemma 2B and 9B from rejection-finetuned checkpoints to improve initial state and action coverage.The policy is then optimized with REINFORCE.
  • RL training: RL runs for 10,000 iterations on the 2B model and 5,000 iterations on the 9B model, using learning rate 1e-7 and batch size 32.
  • RL training: The effective-reward coefficient is selected on validation data, with α=5.0 for Gemma 2B and α=3.0 for Gemma 9B.Values from 0.5 to 6.0 generally improved performance over ORM-RL to different degrees.
  • Theoretical setting: The theoretical analysis uses a tabular deterministic MDP with softmax policies and restricts attention to states reachable from the initial distribution ρ.
  • Policy update: Natural policy gradient optimizes an objective containing Qπ + αAμ, with the corresponding policy update multiplying action probabilities by exp(γ(Qt + αAμ)).
  • Policy update: The least-squares minimizer is determined only up to a state-dependent action-independent offset under the softmax parameterization.

F.3. Proof of Theorem 3.1

The proof analyzes how prover advantages affect policy improvement through distinguishability and alignment. For best-of-K provers, moderate K can amplify distinguishability, while excessive K may reduce it when base-policy values are already high.

  • F.5. Improving a Stronger Base policy with a Weaker Prover Policy: If the prover is sufficiently complementary and the base policy poorly distinguishes actions, the induced improvement scales as η^2.
  • F.5. Improving a Stronger Base policy with a Weaker Prover Policy: The proposition assumes a performance difference between the prover and base policy under state distribution ρ, together with prover complementarity.
  • F.6. Degenerate rewards: Using Qπ + αQμ instead of Qπ + αAμ can produce degenerate RL solutions such as repeatedly beginning with “REPHRASE THE PROBLEM.”The advantage-based reward avoids assigning reward when the prover’s success likelihood is unchanged by the step.
Loading 2410.08146v1…