Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning
Authors: Amrith Setlur
Chirag Nagpal
Adam Fisch
Xinyang Geng
Jacob Eisenstein
Rishabh Agarwal
Alekh Agarwal
Jonathan Berant
Aviral Kumar
Venue: ICLR 2025 Spotlight (2025)
Keywords: LLM
Math Reasoning
Process Supervision
Reward Models
RL
Search
Primary area: foundation or frontier models, including LLMs

Abstract: 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, 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. With the goal of using PRMs to improve a *base* policy via test-time search and 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, as measured under a *prover* policy distinct from the base policy. Such progress values can {distinguish} good and bad steps generated by the base policy, even though the base policy itself cannot.  Theoretically, we show that even weaker provers can improve the base policy, as long as they distinguish steps without being too misaligned with the base policy. Our results show that process rewards defined as progress under such provers improve the efficiency of exploration during test-time search and online RL. We empirically validate our claims by training  **process advantage verifiers (PAVs)** to measure progress under such provers and show that compared to ORM, they are >8% more accurate, and 1.5-5x more compute-efficient. Equipped with these insights, our PAVs enable **one of the first results** showing a 6x gain in sample efficiency for a policy trained using online RL with PRMs vs. ORMs.

Published as a conference paper at ICLR 2025
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 1CMU, "Google Research, 'Google DeepMind
ABSTRACT
A promising approach for improving reasoning in large language models is process reward models (PRMs). PRMs provide feedback at each step of multi-step reasoning trace, 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-labele has thus far led to limited gains. With the goal of using PRMs to improve base policy via test-time search and 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 correct response in the future, before and after taking the step, measured under a prover policy distinct from the base policy. Such progress values can distinguish good and bad steps generated by the base policy, even though the base policy itself cannot. Theoretically, we show that even weaker provers can improve the base policy, as long as they distinguish steps without being too misaligned with the base policy. Our results show that process rewards defined as progress under such provers improve the efficiency of exploration during test-time search and online RL. We empirically validate our claims by training process advantage verifiers (PAVs) to measure progress under such provers and show that compared to ORM, they are 8% more accurate, and 1.5 5x more compute-efficient. Equipped with these insights, our PAVs enable one of the first results showing a 6x gain in sample efficiency for policy trained using online RL with PRMs vs. ORMs.
data
INTRODUCTION
Trained reward models verifiers are often used improve math reasoning in large language models, either by re-ranking solutions at test-time (Collins, 2000) or during reinforcement learning (RL)(Ussa))))) et al., 2022). Typically, verifiers are trained to predict the outcome of an entire reasoning trace, often referred to as outcome reward models (ORM) (Cobbe et al., 2021 Hosseini et al., 2024). However, ORMs only provide sparse signal of correctness, which is hard to learn from and inefficient to search against. This challenge is alleviated by fine-grained supervision, in theory. For reasoning. prior works train process reward models (PRMs) that assign intermediate rewards after each step of search (Snell et al., 2024) or during RL. While Lightman al. (2023) obtains PRM annotations from human raters, this approach is not scalable. More recent works (Wang et al., 2024; Luo et al., 2024) train PRMs to predict automatically- -ggeerrtd annotations that estimate future success of solving the problem, akin to value functions in RL. So far, automated PRMs, especially as dense rewards in RL, only improve by 1-2% over ORMs (Shao al., 2024), raising doubts about their utility.
To resolve these uncertainties, in this paper, our goal is to train automated PRMs that can improve a hase policy, via compute efficient test-time search, and sample-efficient online RL with PRMs as dense rewards. For this, we first ask: (i) what should the per-step process rewards measure, and (ii) what kind of automated data collection strategy should we use train PRMs that predict this measure. For (i), conventional belief (Lightman et al., 2023; Uesato et al., 2022) has been to measure mathematical correctness or relevance of steps. But, it unclear if this supervision yields the most improvement in the base policy (e.g., policy may need to generate simpler, repetitive, and even incorrect steps to explore and discover the final answer during test-time search and RL). Our key insight is that per-step, process rewards that measure notion of progress: change in the likelihood of arriving at a correct final answer before and after taking the step, are effective, for both test-time
"Equal contribution, 'Equal advising. Please send correspondence to: asetlurG andrew.cmu.edu.

---

Published as a conference paper at ICLR 2025
Search: fx Compute EMideen +10% Acconey
20%
Esteet of aquadoon
(b)
1he by
2 2
Frmmlee lase Pollcy
Start
Questen Let randycck
AL Sample PMoeer, 47% fecurecy
0.0
(A)
Rasw
Vesy capatle
poior polooy
Cladd prOVI soller. compuannnrrry tise
DONELL
[c]
Oct0l)
Figure 1: Process advantage verifier (PAV): Process reward for a step is defined progress (advantage) under the prover policy, i.e., change in prover policy's success rate before and after the step. (a): The base policy samples both correct and incorrect steps but struggles to succeed from either. A strong prover completes the solution from any step, making no progress on either or (both scored O.D). Conversely, a complementary prover policy distinguishes are 5x more compute efficient, 10% more accurate in test-time search, and 6x more sample efficient for RL.
more prominently (only succeeds from (b,c): Compared to ORMs, PAVs
beam search and online RL. Reinforcing promising steps that make progress regardless of whether they appear in a correct or incorrect trace results in overall better exploration of possible answers at initial steps, which is crucial when the approach to solve problem is not clear. Formally, such rewards correspond to per-step advantages of steps from the RL literature (Sutton & Barto, 2018). We empirically show that using advantages in conjunction with ORM rewards outperforms using future probabilities of success or Q-values (Wang et al., 2024) for both search and RL. This is because, in the combinatorial space of responses, Q-values mainly "exploit" states whereas advantages also "explore" steps that make the most progress towards the final answer.
To answer (ii) above, we first note that advantages under a poor base policy are = on most steps, and thus will not be informative for test-time search. More generally, we argue that regardless of the strength of the base policy, using its own per-step advantages as process rewards in RL will result in updates equivalent to only using outcome rewards. Hence, we propose to use advantages estimated via rollouts under a different "prover" " policy as process rewards (Fig. 1). How should we choose this prover policy? A natural guess would be to use very capable prover policy, akin to how strong reward models are found to be effective for RLHF (Gao et al., 2023). However, we show advantages under an overly capable prover, that can succeed from any step, fail to distinguish between good and bad steps. A similar argument holds for very weak provers. We formalize this intuition to define good provers as policies that are complementary the base policy, i.e., policies that can distinguish steps, while producing advantages correlated with the base policy. For example, when restricted to the special case of Best-of-K K policies corresponding to base policy, the set of good provers consists of policies for K > 1 with not too large values of K. Contrary to intuition, in general, this set also contains policies that are worse than the base policy, but can still improve it. We show that dense verifiers trained to predict advantages of these prover policies, which we call process advantage verifiers (PAVs), accelerate sample and compute efficiency of RI. and search.
With the conceptual design of PAVs in place, we prescribe practical workflows for training PAVs and demonstrate their efficacy on a series of 2B, 9B, and 27B Gemma2 models (Gemma Team et al., 2024). PAV training data is gathered by sampling "seed" solution traces from the prover and partial rollouts from the same to estimate the Q-value at each prefix of the seed trace. Our workflow prescribes favorable ratios for seed and partial rollouts. Our first set of empirical results show that for an equal budget of test-time compute, combining beam search with trained PAVs is > 8% better in accuracy, and 1.5 5x more compute efficient compared to best-of-N re-ranking against ORM. Dense rewards from PAV's improve the efficiency of step-level exploration during search by pruning the combinatorial space of solutions aggressively and honing in on diverse set of possible sequences. Finally, we demonstrate for the first time, that using PAVs as dense rewards in RL scales up data efficiency by 6x compared to only using outcome rewards. Moreover, base policies trained with PAVs also achieve 8x better Pass@N N performance (chance of sampling the correct solution in N attempts), and consequently afford a higher ceiling on the performance of any test-time re-ranker.
2 PRELIMINARIES, DEFINITIONS, AND NOTATION
Following protocols from Uesato et al. (2022); Lightman et al. (2023), a reasoning trace from an LLM consists of multiple logical steps separated by demarcation token. An outcome reward model (ORM) is a trained verifier that assigns a scalar numerical score after the last step of the trace, and a process reward model (PRM) is trained verifier that scores each step of the trace individually.
2

---

Published as a conference paper at ICLR 2025
Problem setup and notation. Given math problem E X, our goal is to improve base policy that samples a response y ~ x(- x) in the set y. A response y consists of multiple reasoning steps (maximum H), separated by delimiter ( ('next line' in our case), f.e., y (a), az..........................aa.. aH)) ) Since sampling is auto-regressive, we can view each step as an action taken by the agent π in a Markov decision process with deterministic dynamics. Specifically; we treat the prefix (x, .1......... ah-1) the current state Sn and next step ~ x( x) as the action taken by at Sn, resulting in the next state Sh+1- For problem x, with ground-truth response yi. we can evaluate the accuracy of by running a regular expression match on the final answer (Hendrycks et al., 2021): (ex + {0, 1), i.e., accuracy is given by -y-x(- y Now, given a dataset D = ( ((x), y xx)), of problem- solution pairs, the main goal is to learn good base policy by optimizing accuracy on D. Next, we see how we can leverage the final answer verifier Rex available on D to train ORMs and PRMs. Outcome reward model (ORM). Given response y, an ORM estimates the ground-truth correctness Rex(y, yz). To train such model we first take problems in D, and collect training data of the form {(x.y y ~ Z(- x), Rex(y.)))))
yr) }). Then we train an ORM that takes as input a problem-response pair (x and predicts (ex(F. At test time, when y is unknown, the ORM is used to score candidate solutions revealed by test-time search. Given a base π, a best-of-K K policy (oK( is a policy that samples K responses from π, scores them against ORM, and returns the one with the highest score. Note that, whenever ORM matches Rex, and the likelihood of π solving problem is Px, then for (z) this likelihood is 1 - (1 - Px)*, making it a policy stronger than
Typical process reward models (PRMs). A PRM scores every step an in a multi-step response y (e.g., in Lightman al. (2023) PRMs are trained to score correct steps over incorrect and irrelevant ones). But, unlike ORMs, which only require Rex for data collection, PRM training data requires expensive step-level human annotations. Prior work (Wang et al., 2024; Setlur al., 2024) attempted to scale process rewards automatically by sampling from the model to provide a heuristic understanding of when a step is actually correct. In particular, they evaluate a prefix by computing the expected future accuracy of multiple completions sampled from π, after conditioning on the prefix, i.e., value function Q* (Eq. 1) from RI. Luo al. (2024) use Qa as the PRM that assigns a score of Qa (S an) to the action a/, at state Sn. Similarly, (*))s) == Ban - (s,)) 17 QT((h;aa)) ax).
e ((x, di,...,,a-hh.. an-1),
an
==Ba Baatt x (W).aa))
Rex ((a). ((a)....,a.)) an).y;)
(1)
state Sn
action di
likelihood of future success
Using PRMs for beam search at test-time. Given a PRM, a natural way to spend test-time compute is to use it as a reranker within beam search procedure (Snell et al., 2024). For each problem, at step O, a beam of maximum width B, is initialized with a single state consisting of just the problem. At given step h, a beam contains partial responses unrolled till a set of states {st)
f From each
state s; in this set, C independent actions or steps { are sampled from x(- s;), each of which corresponds to a new state. Process rewards assign a score to every new state (si, dr.j), and only the states corresponding to the top-B values are retained in the beam for the next step.
3 How SHOULD WE DEFINE PROCESS REWARDS AND WHY?
Ultimately, we are interested in test-time search and RI. methods that can most efficiently and reliably discover solution traces with the correct final answer, thus maximizing Rex. To this end, process rewards should serve as step-level supervision to maximize outcome-level Rex. Our position contrasts with conventional belief that process rewards should mainly evaluate mathematical correctness or relevance of individual steps (Lightman et al., 2023; Uesato et al., 2022), since LLMs might need to generate trivial or repetitive intermediate steps in order to discover a trace with the correct final answer. With this insight, in this section we approach the design of dense automated step rewards as form of supervision to be used in conjunction with sparse outcome rewards in order to learn good policies.
In an MDP, a starting point to design seate-level dense feedback that is eventually meant to optimize a sparse outcome reward is the notion of reward-shaping function (Ng et al., 1999): in our case, a function that summarizes some statistic of the outcome reward attained in the future, under some policy rolled out from that state. Under this framework, in Sec. 3.1, we evaluate two different choices of the reward-shae -arard-shaping functions and show that advantages - not value functions (Wang et al., 2024; appropriate for
Luo et al., 2024) that measure notion of "progress" at each new step exploration during search and RL. Then in Sees. 3.3 and 3.4, we show that progress is measured best under policy μ. different from the base policy æ. We call this policy μ. a prover policy.
3

---

Published as a conference paper at ICLR 2025
(s, a)
0.50
0.70
0.50
0.25
Question
Q##1 on each state, trivial actions are rewarded
A (ss
-0.05
-0.1
40.00
+.20
10.05
Rephrased Quesiion
(+())
0.60
0.30
Correct solution from prover
Beam
TT
States chosen by
Sleps chosen by
Repeated
(a)
(s, a)
(s. a)
(b)
Question
Figure Issues with using Q-values as process rewards: (a): Unlike A², Qa mixes action evaluation with the Q-value of the previous state. Beam search with Q* exploits high-likelihodd states, while adding A (e.g., Q* + a in Eq. 5) aids in exploring states reached by making actions that induce progress, Le., increase likelihood of success. (b): Q" from strong prover j assign unmerited bonuses to trivial actions.
3.1 PROCESS REWARDS SHOULD BE ADVANTAGES, NOT VALUE FUNCTIONS
Setting aside how prover μ informs the reward-shaping function, we study a simplified setting of test-time beam search, and present some challenges with the reward design of Snell et al. (2024), which uses xd of the base policy to assign rewards for a state-action pair (sh. ah). Consider the example in Fig. 2(a). where from the 2 states in the beam, we sample actions. we only exploit the next states with highest values of Q", would be comparing steps sampled from different states (e.g., 11,1 vs. 42,1). Clearly, a reduction in Q* (1 - V* (s1), means that d1,1 by itself has a negative effect of -0.05 the probability of success from the 11, whereas 12,1 has a positive effect of +0.20 from 82 However, expanding the beam based on absolute values of Q retains the action that makes negative progress, and removes state $2 from the beam (as the size of the beam is 2). In other words, Q makes it hard to decouple the "evaluation" of an action (step), from the "promise" shown by the previous state. This will not be an issue for every problem, and particularly not when the beam capacity is unbounded, but under finite computational and sampling constraints, using Q" might retain states with potentially unfavorable steps that hurt the overall likelihood of success. On the other hand, when deciding what to retain in the beam, if we could also also explore the progress made by the previous step along with the likelihood of success º*,, then we can address this tradeoff.
How can measure the "progress" made by step? One approach is to consider the relative increase/decrease the likelihood of success, before and after the step. This notion is formalized by the advantage (Eq. 2) of step under policy Furthermore, since advantages can attach either positive or negative values to a step, the base policy is trained not only when it generates a step that makes progress (where A 0), but also when it fails to produce one, employing "negative gradient" that speeds up RI. training (Tajwar et al., 2024).
(2) Since we view process rewards as weward-shpping functions in the MDP, they can be computed under any policy μr, which can be the base policy. However, based on the example in Figure 2a, the reasons why Qa is sub-optimal choice for process rewards also apply to Q". Nevertheless, we can possibly use advantage under μr: A", which measures the progress made by a step to improve the likelihood of success under μu. In that case, how should we choose this policy μ, which we call the prover policy, and should it be necessarily different from base x? Before diving into the choice of μ, we discuss: how should we use A" in conjunction with outcome rewards for improving x?
A (s an) = 2 (s), an) - V (sn) = (" an)) - -Q" (=n---1.aa-))
3.2 OUR APPROACH: PROCESS ADVANTAGE VERIFIERS (PAV)
For building an approach that uses process rewards A together with the outcome reward Rex to improve the base policy æ, we situate ourselves in the context of improving æ with online RL. If all we had was access to Rex D. the standard RL objective is given by:
fORM-RI := Ex- 2. an) - (+ Rex ((x, (xx.)...... an (n).yy) ).
Inspired by how reward bonuses are additive in RL (Ng et al., 1999; Bellemare et al., 2016), one way use process rewards A is to additively combine it with the standard RL objective in this way:
e PLV-RL (Tt) fORM-RL (T) +
Bun
[A" ax)]
The term in red is the difference in likelihoods of success of the prover j., summed over consecutive steps (a notion of progress). Here, d denotes the distribution over states step h, visited by the old
4

---

Published as a conference paper at ICLR 2025
policy x' (policy at previous iterate). Following policy gradient derivations (Sutton et al., 1999);
V PAV-ARRR RL (x)) n==
n log sn) ($* an) + (sh, ax))
(5)
effective reward
At a glance, can view ("1, an) aA"(Sh; ah) as the effective reward for step aj when scored against a combination of the outcome evaluation Rex, i.e., Q*, and process rewards A". Thus, we can optimize Eq. 4 indirectly via (a) running beam-search against the effective reward; (b) online RL where the policy gradients are given by Eq. 5. For either of these, we need access to verifiers that are trained to predict the advantage A" (s), an)) under the prover. We refer these verifiers as process advantage verifiers (PAVs). In Sec. D we describe how to train PAVs, but now we use the above formulation to reason about how to choose prover I that is most effective at improving base æ.
We also remark that the term in red resembles prior work on imitation learning via policy optimiza- tion (Ross Bagnell, 2014; Sun et al., 2017), where the main aim is to learn a policy æ that imitates the prover μ4, or improve upon it minimally. Of course, this is limiting since our goal is to not just take actions that perform at similar level as f4, but to improve the base policy even further, and using combination of Q^ (exploitation) and A" (exploration) is critical towards optimizing the goal.
How should we choose the prover μr? Perhaps a natural starting point is to set the prover to be identical to the base policy, i.c., μ considered Shao et al. (2024). However, setting A = AA in Eq. results in exactly the same policy only optimizing outcome evaluation Rex. Moreover, for poor base policy æ, where Q" = 0 on most states, the term A would also be x 0, and hence running beam search with the effective rewards would not be informative all. Hence, better approach is to prover policy, but a very weak prover will likely run into similar issues as a poor base policy. We could instead use a very capable prover μ. but unfortunately even this may not be any better than optimizing (exploiting) only the outcome rewards, Qx either. To see why, consider a scenario where IT' 's response contains an intermediate step that does not help make progress towards the solution (e.g., simply restates the question, see Fig. 2(b)). Here, Q" for a capable prover before and after this irrelevant step will be identical since μ can succeed from either step. This means that μ fails to distinguish steps, resulting in A x O in most cases. Training with this process reward during RL will then lead to gradients that are equivalent to those observed when purely optimizing fORM-RL. In fact, empirically, we observe that online RL with Q" from strong provers leads to polices that only produce re- phrasings of the question (App. G) and do not succeed at solving the question. Clearly, any policy different from the base policy cannot serve prover. So, how do we identify set of good provers? Can they indeed be weaker than the base policy? We answer in the next sections.
which produces process rewards that prior works have
gradient update
different
Takeaway: What should process rewards measure during test-time search and online RL?
Process rewards should correspond to progress, or advantage, opposed to absolute Q- values, for better explore-explon tradcoff during beam search and online RL.
Advantages should be computed using a prover policy, different from the base policy.
3.3 ANALYSIS A DIDACTIC SETTING: LEARNING PLANTED SUB-SEQUENCE
In this section, we aim characterize prover policies that are effective in improving the base policy. To do so, we first introduce didactic example, representative of real reasoning scenarios to illustrate the main intuition. Then, we will formalize these intuitions the form of theoretical results.
Didactic example setup. Given an unknown sub-sequence y* consisting of tokens from vocabulary 2........ 15), we train a policy π produce a response which contains this uub-sequence. The task completion reward is terminal and sparse, i.e., ((',"")) ) for if and only if y* appears in y. By design, the reward y*) resembles outcome reward Rex y Sec. The prover policy j is procedural policy, parameterized by scalar y 0 (details in App. B). As increases, the performance of μ improves and + 1 as y - co, For simplicity, we assume oracle access to ground-truth A and Q" and alleviate errors from learned verifiers approximating these values.
V = {1,
(1) RL with effective reward Q aA" is 10x more sample-efficient than only outcome reward. In Fig. 3(a), we first note that training with this effective reward under prover μ with strength = 10, produces optimal performance (100% accuracy) in < 1k iterations, despite starting from a mediocre initialization for æ (y = 5.0). Training with only outcome reward is ineffective and requires
5

---

Published as a conference paper at ICLR 2025
RL with Different Rewards
Accuracy lavg. over iters)
Choice of Prover Policy μ
Ceiling Test-time Re-ranking
0.25
Effective Reward
0.8
0.20
Only Q"
Accuracy
0.6
Only Q"
0.6
Effective Reward
Pass @N
0.15
Initial m
Only Q
0.4
Effective Reward
0.4
for intaal
0.10
0.2
0.2
0.05
0.0
0.0
0.00
(a)
2.5k
(b)
13.0 17.0
(c)
Training iterations
N
Figure 3: Results for our didactic analysis: (a): We train base policy via RL with either the effective reward
Q aAA", the more typical º* (b): We vary the strength y of the prover policy j used to compute advantages A" in the effective reward, and plot the base policy accuracy averaged over the RL run. (c): We plot the max score out of N responses (Pass @N) sampled i..dd from an undertrained base policy (iter 100).
10k iterations. More importantly, in Fig. 3(b), note that effective rewards only help for a set of provers, in [8.0, 15.0]. Outside this range, we observed A" = 0 on most states, either because was poor (small y) and was unable to generate y* even when x got the sequence partially correct, or because was strong (large y) that it generated y" with almost equal likelihood from all prefixes.
(2) Effective reward improves Pass @N by 5x over only outcome reward. We report the "Pass @N" performance in Fig. 3()), which measures if any out of N i..dd samples from æ have reward and hence, presents the ceiling on the performance of any test-time search method that picks single response from multiple draws (e.g., as in Best-of-N), For a policy trained with the effective reward for 100 iterations, the Pass @N performance grows 5x faster with N, compared to the policy trained with only the outcome reward. Due to only sparse feedback, the latter policy does not learn to sample partially correct y* whereas a policy trained with the effective reward produces partially correct y*, and is able to sample the complete y* with higher likelihood during Pass @N.
Takeaway: Online RL with process rewards from different prover policies.
Effective rewards Q* AA from prover μ:: (i) improve sample efficiency of online RL, and (ii) yield policies with better Pass @N performance, over using only outcome rewards. But, advantages of very capable or poor μ do not improve base policy beyond outcome rewards.
3.4 THEORY: PROVERS COMPLEMENTARY TO BASE POLICY BOOST IMPROVEMENT
From our didactic analysis, it is clear that process rewards A under different provers disparately affect the base policy that optimizes Qa Al via online RL. We now present formal analysis of why this happens and characterize a class of provers that can guarantee non-trivial improvements to the base policy. For simplicity, we assume oracle access to Q _².A* AA' at every state-action pair (s an) and prove our result in the tabular RL setting, where the policy class is parameterized using the softmax parameterization in Agarwal et al. (2021). Proofs for this section are in App. F.
Main intuitions. We expect prover μ to improve base policy only when μ is able to distinguish different actions taken by æ,, by attaining sufficiently varying advantage values (8(8,. a) for actions state Sh This can be formalized under the notion of sufficiently large variance across actions, Va-n [A 4)]. In that case, can we simply use a policy with large advantage variance under any measure? No. because when the prover μ ranks actions at a given state very differently compared to the base policy x (e.g., if A" and A" are opposite), then effective rewards Q" + aA* x will be less reliable due to conflicting learning signals. Thus, we want E, [(A", A } to not be too negative, so that μ and π are reasonably aligned on their assessment of steps from π.
In Theorem 3.1, we present our result on policy improvement where the base policy is updated with natural policy gradient (Kakade, 2001): Te+ (a sa) x exp(y (A*(Sh,a) + (Sh. 4))). We note that in this idealized update rule, swapping Q values (of μ or π7) with advantages does not affect the update, since we only subtract an iatiion-iddpendden offset V(sn). Consequently, the analysis only uncovers good choices for the prover policy μ for process reward A", and is orthogonal to the design consideration of advantages or Q-values showing that policy improvement at iteration f, grows as the variance in A" values increases (higher distinguishability)) and reduces when A" and A become extremely misaligned. This will then allow us to discuss a special case for the case of Best-of-K policies as provers as an immediate corollary.
process rewards. Theorem 3.1 formalizes our intuition by

---

Published as a conference paper at ICLR 2025
Gemma-2B
Gemma-9B
Gemma-278
ORM
ORM
ORM
PAV (ours)
0.6
PAV (ours)
PAV (ours)
Accuracy
Pass @N
Accuracy
Pass @N
Accuracy
Pass @N
8%
10%
1.5
x
10%
2 x
0.5
0.1
0.4
(a)
2
2
2
2 N
2'
2
(b)
21
2
2 N
2
2
2
(c)
21
21
2
2
27
N
Figure 4: For test-time search, PAVs are 8 - 10% more accurate and 1.5 - 5x more compute efficient over ORMs: On samples from (a) Gemma-2B (b) 9B and (c) 27B SFT policies, we test-time beam search with the effective reward Q* + aA" (PAV), where μ is (x) policy. We compare beam search performance with best-of-N, re-ranking with a trained outcome verifier (ORM), or the oracle Rex (Pass @N).
Theorem 3.1 (Lower bound on policy improvement). For base policy iterate xt, after one update step with learning rate y < 1, 3 constant C > O s.t. over state distribution p the following holds:
Bx-p [V*ml (s) v (s)] 2 Cy Bs-pya-nn [A a)] + Cy -Be-pBa-n, [A a) A (s, a)] (6)
distingisshubility from P
alignment between X, and
may seem that the base policy л can only learn from an improved prover μ, but our result shows that a weak prover can also amplify stronger base policy, since weak prover z may have lower average of Q* under its own measure, but still have higher variance across Q"r (compared to @*) when evaluated under (see Proposition F. in App. F.5 for formal discussion). This tells us that rewarding progress under a prover is different from typical knowledge distillation or imitation learning algorithms (Hinton, 2015; Rusu et al., 2015) that in most cases remain upper bounded by the performance of the stronger teacher. So provers cannot be characterized purely by strength, what is a class of provers that is reasonable starting point if we were to improve any base policy s??
The policy class of "Best-ofKK (computed over base policies) contain complementary provers. good starting point to identify good provers for a base policy π, is the class of Best-of-K policies or (oK(()). Recall from Sec. 2 that the performance of BoK(T) increases monotonically with K. Thus, we can vary to obtain a class of policies with increasing strengths, starting from π. Applying Theorem 3.1 to this class, we arrive at Remark 3.1 that recommends using (oK( with K > I as prover policy for a poor base policy æT. Conversely when (s, a) then increasing too much can hurt variance on those states (see Appendix F.4). In the next section, we empirically note that the policies in the class of BoK(x)) indeed induce different performance gains when used as prover policies, and we find Bo4 to be good choice for test-time search over most base policies.
Remark 3.1. When (* a) = O(1/K), Vs, a, using BoK( as prover for base improves distinguishability (and improvement) by ((K?), and makes alignment worse at most by O(K).
Takeaway: Formal characterization of good prover policies that improve the base policy.
Provers with advantages that can distinguish actions taken by the base policy (more strongly than the base policy itself) but are not too misaligned from the base, boost improvements on each update of the base policy. We call such policies complementary provers. BoK(z) (Λ) for any base policy π for K > can provide a good starting choice of prover policies.
4 WEST-TIME EFFICIENTLY SCALING TEST-TIME COMPUTE WITH PAVS
Now, we study how process verifiers can scale up test-time compute. While our derivations from Sec. 3.2 were with RL, we can also use the effective reward Q* aR) + A" ax) for running beam search over intermediate steps sampled from base policy π. In the end, we select the final response in the beam using ORM. In practice, we need to train PRMs that predict Qx (we call these PQVs) and PAVs that predict A", procedures that we discuss in App. D. For now, we assume access to trained ORMs, PQVs and PAVs and discuss test-time search results. For clarity, we abuse notation and refer to the estimated effective reward (ORM + a PAV) as PAV directly.
Setup. We finetune Gemma 2B, 9B, and 27B (Gemma Team et al., 2024) on MATH (Hendrycks et al., 2021) via supervised fine-tuning (SFT) to get three base policies. The set provers consists of the three base SFT policies themselves as well as their best-of-K K policies for different values of K E (2....., 25). Additional details for the experiments in this section are in App. C.
7

---

Published as a conference paper at ICLR 2025
Comparing PRMs
Choice of Prover
% Improved Over ORM
Base x Praver
0.55
Provers
Accuracy
0.50
Accuracy
0.25
40
27B
0.45
0.20
ORM
0.40
PAV- as: ORM
Bo2
Bo16
10
0.35
PRM (Q
Bo4
Bo32
PAV (ours)
Bo8
100
0.30
0.10
(a)
2
2
2
2 2' 2
2
2
(b) 2
2
2
2
2
2
2
(c)
2B
98
278
N
Base Policy
Figure 5: Comparing PAVs with search baselines and ablating over the prover policy: (a): We compare beam search over Gemma 9B SFT, using either effective reward (PAV), or Q" (Snell et al., 2024), and report hest-of-N performance where the re-ranker is either the ORM or PAV-as-ORM. (b): For base Gemma 2B SFT, we run beam search with the effective reward where the prover is BoK(x) for different values of K. In both (a). (b) the x-axis scales the size the beam or N for of (c): For each base policy in the set: Gemma 2B, 9B, 27B SFTs, we run beam search with PAVs (beam size of 16) where the prover is another policy from the same set.
4.1 PAVS SCALE TEST-TIME COMPUTE BY 5 - 10x OVER ORMS
Result I: PAVs more compute efficient than ORMs. In Fig. 4, we plot the performance of beam search with PAVs for different sizes of the beam N, and compare it with best-of-N using ORMs, i.e., sampling N complete solutions from the base policy and returning the one with the highest ORM score. Our comparisons report compute efficiency of PAVs over ORMs: ratio of total compute needed by PAVs to obtain the same performance as running best- 128 with ORM. Accounting for the additional compute needed for beam search (since each element in the beam samples C = 3 next steps, before scoring and pruning the beam), PAVs scale the compute efficiency by 10x over ORMs for Gemma-2B, 9B base policies, and by 5x for Gemma- 27B. For all base policies πT, use (r)( with K 4 as the prover policy. We also compare performance with beam search using process verifiers that only predict Q*, and best-of-N where the ORM is replaced with PAV (PAV-as- -RMM)) At N = 128, similar to Luo et al. (2024), we note a similar gain of 4% for "PAV-as-ORM" Fig. 5(a) over only ORMs, for base Gemma-9B π. When comparing beam search with QT (Snell et al., 2024), we find that PAVs scale compute efficiency by 8x. Evidently, advantages from the prover in the effective reward positively impact the beam search. Why does A help, and for what choice of the prover μu?
Beam search with too weak/strong provers is sub-optimal. In Fig. 5(b), for the setting when the base policy π is a Gemma-2B SFT model, we compare beam search with PAVs where the provers are given by BoK(T), for different values of K. Recall that as K increases, BoK(T) becomes stronger. Corroborating our analysis in Sec. 3.4, our results show that neither too weak (Bo2) or too strong (Bo32) provers perform best. Instead, across all values of N, we find Bo4 to be dominant, The advantage values A" 0 on all steps for very large K, since Q" (S,, on all steps, as we increase K. Hence, in order to succeed we need an intermediate-level prover policy. We make similar observations in Figure 5(c) where we take the three base policies (Gemma 2B/9B/27B) and evaluate beam search with PAVs at N 16 with the Bo4 over the SFT policies acting as provers. We find that for the 2B and 9B base models, the 9B and 27B provers are most effective respectively, whereas for the 27B model, surprisingly weaker 9B policy is more effective than the stronger 27B model. The weaker model presumably offers a complementary signal that distinguishes between different actions taken by 27B, aligning with our theoretical observations in Sec. 3.4.
Result 2:
11-112 (s,, an))
Result 3: Advantages from the prover policy enable explo- ration. As discussed in Sec. 3.1, advantage A measures the progress made by an action agnostic of the value of the previous state, where as @a measures the promise of a particular state. Given finite capacity beam, our effective reward (Eq. 5), which linearly combines Q* and A" induces a better tradeoff between exploring new prefixes (states) from where progress can be made and exploiting currently known prefixes with high Q-values. Ex- ploration at initial steps is critical to ensure that the beam at later steps covers diverse partial rollouts each with a high likelihood of producing the correct answer. Thus wommiiiiit the beam with actions from the same state, regardless of the progress made by each can prove to be sub-optimal over selection strategy that balances rewarding previous actions A and current states
Pass @N over Gemma 2B Base Policy
0.4
Accuracy
0.3
Temp. Sempling Search: PAV (ours)
0.2
Search: PRM (0*)
2
2"
Figure 6: Beam search with PAVs improves Pass@N over typical PRMs.
8

---

Published as a conference paper at ICLR 2025
PAVS vs. ORMS
Pass @N (28)
Sample Efficiency (2B)
0.5
Accuracy
0.4
GRIM-RL
Accuracy
%
PAV
0.3
0.1
0.2
RFT
DRM-RL
0.15
PAV-RL RL.
ORM-RL
(a)
28 9B
(b) 2 21
2
2
2
D 1 4 6 a 9
Base Policy
Training Iterations (x10*)
Figure PAVs as dense rewards in RL 6x more sample efficient than ORMs, and gains +7% on accuracy: (a) We report the performance of a base policy trained using RL with effective rewards (PAV-RL), or only outcome rewards (ORM-RLC RL), and baselines SFT. RFT. (b): For the policies trained in (a) we report the best-of-N performance where the oracle reward Rex is used to rank N' candidates sampled from the base policy (Pass @N). (c): Across training iterations, we report the test performance of policies trained with PAV-RL and ORM-RI.
ºa. Indeed, we observe in Fig. 6, beam search with PAV enhances pass@ @N performance of the base Gemma 9B model over beam search with Q* and i.idd sampling.
Takeaways: Scaling test-time compute with process advantage verifiers.
Beam search with PAVs boosts accuracy by >8% & compute efficiency by 1.5-5x over ORMs.
Utilizing Best-of-K policies (corresponding to the base policy) as provers improves the performance of test-time beam search over the base policy. Optimal provers appear at K > 1.
5 TRAINING-TIME: SCALING RL CAMPLE-EFFICIENT
WITH PAVS
We can also use PAVs to train policies via online reinforcement learning (RL), by using the effective reward Q* aA" as dense, per-step rewards. In this section, we compare the sample efficiency of PAV-RL (i.c., (PAV-RL in Eq. 4) with standard ORM-RL (i.e., fORM-RL in Eq. 3) on Gemma 2B and Gemma 9B SFT models, which are further optimized via rejection finetuning (RFT) (Yuan et al., 2023), before using them to initialize RL. To our knowledge, no prior work has successfully demonstrated the use of dense per-step feedback with process reward model for RL, and we present the first significant set of results establishing the efficacy of this approach. We show that PAV-RL is much more sample-efficient, and enjoys a higher ceiling on the performance of any test-time re-ranker. Additional details for the experiments are in App. E.
Result 1: PAV-RL is > 7% better than ORM-RL in test accuracy, and 6x sample efficient. In Fig. 7(a), we report the test accuracies of Gemma 2B and 9B models trained with SFT,
Success Rate on Problemss
Unsolved by SFT SFT @225
Solving Hard Questions
0.15
ORM
PAV
RFT, ORM-RL and PAV-RL. PAV-RL improves the RFT policy by 11% for 2B, and 15% for 9B, with 7% gain over ORM- RL in both cases. Not only do the effective rewards from PAV improve the raw accuracy after RL, this accuracy is attained 6x faster (see Fig. 7(c)) for the 2B run and similarly for the 9B RL
0.10
0.05
0.00
2
2
27
2
2
26
20
run (see App. E). For both 2B and 9B, RL runs, we experiment with two options for the prover policy: (i) 2B SFT policy; and (ii) 9B SFT policy. While both of these provers rapidly become weaker than the base policy within a few gradient steps of RL, a fixed PAV trained with each of these provers is able to still sustain performance gains in RL. More interestingly, we find that the 2B SFT policy serves as the best choice of the prover for both 2B and 9B policies. This observation that a weak prover can still improve the base policy corroborates our results in the didactic setup and our analysis in Sec. 3.4.
Figure 8: Amongst hard problems that remain unsolved by Best-of-256 over SFT, we check how many are solved by Best-of-N over PAV-RL or ORM-RL.
Result 2: PAV-RL achieves higher performance ceiling on test- test-time re-ranking. In Fig. 7(b), for the Gemma 2B model, we plot the Pass @N N performance for each method, and find (i) Pass @N is higher (> 7%) for PAV-RL, compared to ORM-RL, for any N < 128; and (ii) the rate at which Pass @N improves for PAV-RL is higher than ORM-RL. Both these trends are consistent with our observations in the didactic analysis in Sec. 3.3. Notably, for N 64, ORM-RL is worse than the SFT policy, perhaps due to lower entropy over the distribution at the next step resulting in non-diverse candidates. So, why does PAV-RL deliver policy that generate more diverse candidates, and does not suffer from the low entropy problem in ORM-RL? We answer this with a key insight on how the primary henefit of PAVs is to promote efficient exploration.

---

Published as a conference paper at ICLR 2025
PAVs improve exploration and discover correct solutions to novel problems. The ORM rewards downweight all steps in an incorrect rollout equally during RL, whereas the effective reward in PAVs, up-weights steps that make progress under the prover, even when the complete rollout is incorrect. This increases the coverage over individual steps that can be proposed at a given prefix. This mechanism for exploration is analogous to test-time search in Sec. 4.1. Hence, the directed supervision from PAVs improves sample-efficiency throughout the course of training (Fig. 7(c)). In fact, we also find that combining the PAV-RL policy with test-time beam search is able to solve a substantially larger number of new problems within smaller compute budgets (N=16,32) that the SFT policy cannot solve with a much larger budget N=256 (Fig. 8).
Result 3:
Takeaway: RL with process advantage verifiers (PAVs) as dense rewards
Using trained PAVs as dense rewards in RL boosts scales sample efficiency by 6x, compared to only using sparse ORM rewards, and results in policies with a higher Pass @N performance. Advantages from a complementary prover policy improves the sample efficiency of explo- ration in RI, and produces policies that can discover solutions to hard novel questions.
RELATED WORKS
Outcome reward models (ORMs) (Cobbe et al., 2021b; Uesato et al., 2022) are used for best-of-N search where ORMs are trained to assess correctness using binary classification (Cobbe et al., 2021a; Yu et al., 2023), preference optimization (Hosseini et al., 2024), or next-token prediction (Zhang et al., 2024). In contrast, we propose process reward models (PRMs), that assign scores to intermediate solutions to improve performance with beam-search and enable online RL with dense rewards.
To address issues of sparse feedback in ORMs, recent works (Lightman et al., 2023; Uesato et al., 2022) trained process reward models (PRMs) to densely predict incorrect steps in a multi-step reasoning trace. Since human data collection for process labels is not scalable enough, recent work (Wang et al., 2024; Luo et al., 2024) used automated supervision to annotate steps with Q values under the base policy, i.e., the PRMs score step with the likelihood of future success, when continuing to sample from the step. While Q-value PRMs in Lightman et al. (2023); Luo et al. (2024) were mainly used as verifiers for re-ranking. Snell al. (2024) used them for test-time beam search. Shao et al. (2024) uses PRMs for RL but found a gain of only 1 - 2% with PRMs. In our work, we question solely relying on Q-values or advantages of the base policy, and find that measuring progress (i.c.. advantages) under a different prover policy can amplify exploration, thus boosting test-time search and RL. Our data collection strategy is similar to (Setlur et al., 2024; Hwang et al., 2024) (i.e.. identify "first pits" in traces), but these works only use it to collect preference pairs. Beyond all these, we also characterize which policy to use for computing advantages. Trained outcome or process verifiers can optimize policies similarly to RLHF (Ouyang et al., 2022). Prior works (Uesato et al., 2022; Havrilla et al., 2024; Shao et al., 2024) showed limited gains from PRMs compared to ORMs or ground tround-truthaa rewards (Rex). Notably, Havrilla et al. (2024) found expert iteration (Anthony et al., 2017) superior for exploration. In contrast, our work demonstrates that PRMs, combined with outcome rewards in online RI., improve performance by +7% and boost sample efficiency by 6x.
Finally, the idea of improving a sub-optimal expert by mixing policies, as in structured predic- tion (Chang et al., 2015), using "guide" policy for rollouts (Chang et al., 2023), relates to work. However, we show that even weak prover policies can enhance a base policy by distinguishing its steps through advantages, without needing to surpass the base directly.
7 CONCLUSION
We explore process rewards to improve outcome- correctness of a base policy, and show that defining them advantages of distinct prover policy enhances exploration and accuracy in math reasoning tasks. We formally characterize the set of good (complementary) prover policies and train process advantage verifiers (PAVs) predict their advantages. For the base policy, PAVs improved search compute-efficieng by 1.5-5x and accuracy by 8%, while dense online RL with PAV rewards boosted sample efficiency by 5-6x and accuracy by 6%. Challenges remain in designing optimal prover policies and addressing PAV fitting errors, highlighting avenues for future research, such as joint optimization of prover and base policies or alternative advantage estimation methods.
10

---

Published as a conference paper at ICLR 2025
8 REPRODUCIBILITY STATEMENT
For our experiments on the didactic setup in Section 3.3, we provide details in Appendix B. For experiments training process advantage verifiers (PAVs) provide details in Appendix D. Details for experiments that use the trained PAVs for test-time search Section 4, are provided in Appendix C. Finally, for our experiments learning (Section 5), we provide details in Appendix E. All proofs for our theoretical claims can be found in Appendix F. The pretrained model checkpoints for Gemma-2B, 9B, and 27B used in this work are available publicly at https:/hugginnfacee co/google and the MATH dataset we use from Hendrycks al. (2021) is also public here:
training the base policies with PAV' as dense rewards in reinforcement
ACKNOWLEDGEMENTS
The authors would like to thank Charlic Snell, Yi Su, Katherine Heller, and Virginia Smith for feedback on an earlier version of this paper. We also thank Ahmad Beirami, Sergey Levine, Victor Veitch, Idan Shenfeld, Arian Hosseini, Stephen Pfohl, Xiangyu Qi. Tianhe Yu, and Christina Back for technical discussions. AS and CN also thank Preston Robinette, Sho Kannan, Tianze Shi, Diana Mineu, Hritik Bansal, and Liangchen Luo for code, infrastructure and data analytics support.
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1--7, 2021.
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. Advances in neural information processing systems, 30, 2017.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pp. 1471-1479, 2016.
Xiao Bi, Deli Chen, Guanting Chen, Shanhuang Chen, Damai Dai, Chengqi Deng, Honghui Ding, Kai Dong, Qiushi Du, Zhe Fu, et al. Deepseek l1m: Scaling open-source language models with longtermism. arXiv preprint arXiv:2401.02954 2024.
Jonathan Chang, Kiante Brantley, Rajkumar Ramamurthy, Dipendra Misra, and Wen Sun. Learning to generate better than your 1lm. arXiv preprint arXiv:2306.11816 2023.
Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daumé III, and John Langford. Learning to search better than your teacher. In International Conference Machine Learning, pp. 2058- 2066. PMLR, 2015.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers solve math word problems. arXiv preprint 10.122100.1416.. 2021a.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. 14168, 2021b.
Michael Collins. Discriminative reranking for natural language parsing. In Proceedings of the International Conference on Machine Learning, 2000.
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pp. 10835- 10866. PMLR, 2023.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based gemini research and technology. arXiv preprint arXiv:2403.088295 2024.
11

---

Published as a conference paper at ICLR 2025
Mathieu Germain, Karol Gregor, lain Murray, and Hugo Larochelle. Made: Masked autoencoder for distribution estimation. In International conference on machine learning, pp. 881-889. PMLR, 2015.
Alex Havrilla, Yuqing Du, Sharath Chandra Raparthy, Christoforos Nalmpantis, Jane Dwivedi- Yu, Maksym Zhuravinskyi, Eric Hambro, Sainbayar Sukhbaatar, and Roberta Raileanu. Teaching large language models to reason with reinforcement learning. arXiv preprint arXiv:2403. 044442 2024.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. NeurIPS, 2021.
Geoffrey Hinton. Distilling the knowledge in neural network. arXiv preprint 2015.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, al. Training compute-optines large language models. arXiv preprint arXiv:2203. 15556 2022.
Arian Hosseini, Xingdi Yuan, Nikolay Malkin, Aaron Courville, Alessandro Sordoni, and Rishabh Agarwal. V-star: Training verifiers for self-taught reasoners. arXiv preprint 24X.::2402.06457, 2024.
Hyeonbin Hwang, Doyoung Kim, Seungone Kim, Seonghyeon Ye, and Minjoon Seo. Self-explore to avoid the pit: Improving the reasoning capabilities of language models with fine-grained rewards. arXiv preprint arXiv:2404. 10346, 2024.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 267-274, 2002.
Sham M Kakade. A natural policy gradient. In Advances in neural information processing systems, volume 14. Advances in neural information processing systems, 2001.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint arXiv:2305.20055 2023.
Liangchen Luo, Yinxiao Liu, Rosanne Liu, Samrat Phatale, Harsh Lara, Yunxuan Li, Lei Shu, Yun Zhu, Lei Meng, Jiao Sun, et al. Improve mathematical reasoning in language models by automated process supervision. arXiv preprint arXiv:2406.0655 2024.
Qianli Ma. Haotian Zhou, Tingkai Liu, Jianbo Yuan, Pengfei Liu, Yang You, and Hongxia Yang. Let's reward step by step: Step-level reward model as the navigators for reasoning. arXiv preprint 1rXii:2310.10080 2023.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In ICMI., volume 99, pp. 278 287, 1999.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. arXiv preprint arXiv:2305.18290 2023.
Stephane Ross and J Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint wrXiv:1406.5999 2014.
Andrei A Rusu. Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirk- patrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukeuoglu, and Raia Hadsell. Policy distillation. arXiv preprint 11.06215 2015.
12

---

Published as a conference paper at ICLR 2025
Amrith Setlur, Saurabh Garg, Xinyang Geng, Naman Garg, Virginia Smith, and Aviral Kumar. RI on incorrect synthetic data scales the efficiency of Ilm math reasoning by eight-fold. arXiv preprint 24X1::2406.14532, 2024.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Mingchuan Zhang, YK Li, Yu Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03330, 2024.
Avi Singh, John D Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Peter Liu, James Harrison, Jachoon Lee, Kelvin Xu, Aaron Parisi, et al. Beyond human data: Scaling self-training for problem-solving with language models. arXiv preprint arXiv:2312.00 2.055855, 2023a.
Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. Progprompt: Generating situated robot task plans using large language models. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 11523-11530. IEEE, 2023b.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint 4rX1v:2408..3311, 2024.
Wen Sun, Arun Venkatraman, Geoffrey Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International conference on machine learning, pp. 3309-3311 PMLR, 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. The MIT Press, second edition, 2018.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Fahim Tajwar, Anikait Singh, Archit Sharma, Rafael Rafailov, Jeff Schneider, Tengyang Xie, Stefano Ermon, Chelsea Finn, and Aviral Kumar. Preference TinnnTnnng of LLMs Should Leverage Suboptimal, On-Policy Data, 2024.
Ye Tian, Baolin Peng, Linfeng Song, Lifeng Jin, Dian Yu, Haitao Mi, and Dong Yu. Toward self- improvement of iims via imagination, searching, and criticizing. arXiv preprint 2rXiv:2404.12253: 2024.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint a:X1v 2022.
Peiyi Wang, Lei Li, Zhihong Shao, R. X. Xu, Damai Dai, Yifei Li, Deli Chen, Y. Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce Ilms step-by-step without human annotations, 2024.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. An empirical analy- sis of compute-optimal inference for problem-solving with language models. arXiv preprint Atl.:2408.007244.. 2024.
Fei Yu, Anningzhe Gao, and Benyou Wang. Outcome-supervised verifiers for planning in mathemati- cal reasoning, arXiv preprint arXiv:2311.09722 2023.
Zheng Yuan, Hongyi Yuan, Chengpeng Li, Guanting Dong, Chuanqi Tan, and Chang Zhou. Scaling relationship on learning mathematical reasoning with large language models. arXiv preprint arXiv:2308.0 01825, 2023.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35: 35:15476-15488, 2022.
Lunjun Zhang, Arian Hosseini, Hritik Bansal, Mehran Kazemi, Aviral Kumar, and Rishabh Agarwal. Generative verifiers: Reward modeling as next-token prediction. arXiv preprint arXiv:2408. 15240, 2024.
13

---

Published as a conference paper at ICLR 2025
Appendices
A ADDITIONAL RELATED WORK
In this section, we expand on the related works we discuss in Section 6. Our work is closely related to three categories of works that aim to improve the math reasoning capabilities of large language models. First, we look at works that train verifiers to provide outcome level feedback (Cobbe et al., 2021b; Hosseini et al., 2024; Zelikman et al., 2022; Singh et al., 2023b) on the correctness of the full response (ORM). Next, we look at works that alleviate issues with sparse feedback in ORMs, and instead train process reward models, that can perform credit assignment. They are trained either through human annotations (Lightman et al., 2023; Uesato et al., 2022), or automated forms of supervision (Snell et al., 2024; Wang et al., 2024; Luo et al., 2024). While most PRMs and ORMs have been used to collect supervised finetuning data or for test-time verfication, a selected set of recent works also experiment with using them for training LLMs with online RL (Wang et al., 2024; Uesato et al., 2022; Shao et al., 2024). Below, we discuss each of these categories separately.
Outcome reward models (ORMs) or verifiers (Cobbe et al., 2021b; Uesato et al., 2022) are com- monly used to improve the test-time performance using Best-of-N, where we generate multiple candidate solutions from the base policy (LLM), rank them using verifier, and pick the best one. ORMs are trained to assess correctness of a solution either using binary classification (Cobbe et al., 202 Yu et al., 2023), preference optimization using DPO (Hosseini et al., 2024), or next-token prediction (Zhang et al., 2024). Furthermore, prior works train LLMs on self-generated data using ground-trutt truth outcome rewards (Rex), either via supervised fine-tuning (Zelikman et al., 2022; Singh et al., 2023a; Yuan et al., 2023), or online RL (Bi et al., 2024). In contrast to these approaches, work focuses on process reward models (PRMs) for improving performance with beam-search at test time as well online RL where jointly maximize the effective reward in equation 5 which linearly combines both Rex (outcome supervision) and process supervision in the form of advantages under a prover policy, distinct from the base policy.
PRMs and credit assignment. Several works focus on training step-level PRMs on math reasoning tasks, either using human labels (Lightman al., 2023) or automated LLM-generated data to estimate value functions ( (Wang et al., 2024; Luo et al., 2024). Our work also focus on automated data collection for PRMs but empirically argues for additionally using the advantage function as step-level rewards, with conceptual explanation focused in Section 3.1. Several prior works have explored step-level search algorithms with PRMs, such as beam search (Snell et al., 2024), heuristic greedy search (Ma et al., 2023), and neward-balance, tree search (Wu et al., 2024). Hwang et al. (2024); Setlur et al. (2024) use advantages to identify the "first pit" in an incorrect reasoning trace. Specifically, they collect data by computing advantages at each step using Monte Carlo rollouts. Then in incorrect trace, they identify the step with the least advantage, and use the prefix of that step to construct preference pairs for offline direct preference optimization (Rafailov et al., 2023). In contrast, our work computes advantages under a prover policy, that we formally characterize, and use the computed advantages for improving test-time search and efficiency of online reinforcement learning.
Online RL for math reasoning. Once we have a trained outcome or process verifier, it is natural update policy by optimizing it against the learned signal, similar how learned reward models are optimized in RLHF (Ouyang et al., 2022). In the context of math reasoning, Uesato et al. (2022); Havrilla et al. (2024); Shao al. (2024) trained policies with RL, experimenting with both dense and sparse rewards. In all three instances, the gains observed by using PRMs trained to predict step-level correctness (similar to Lightman et al. (2023)) is quite small, compared to simply using trained ORMs, or the ground-truth outcome supervision Rex. In fact, Havrilla et al. (2024) states that the only algorithm that does well is form of expert iteration Anthony et al. (2017), which does not inhibit exploration severely as some other approaches they compare with. Our work presents one of the first results, where trained PRMs, used in conjunction with the outcome rewards during online RL, result in policies with substantially higher (+7%) performance, than the one trained only with outcome supervision. Our results also indicate a 6x sample efficiency boost for online RL, with our trained PRM (PAV).
Connections to imitation learning through RL. Finally, in addition to the above three sets of papers, note that the idea of mixing potential functions from different policies a and n, in order
14

---

Published as a conference paper at ICLR 2025
sub-eequence y":
Samples from policy corresponding to y
Samples policy corresponding to
somplem
6
14
14
14]
rewardm1.0
samp samplo-
14
reward-1.3
samplem
7
reward-0.0
sampl
14]
reward-1.a
semplem
14
13
11]
rewerdm1.0
samp
14]
reward-1.3
samples
13
11
reward=8.0
samp
reward-1.3
somple=112
8
34
5
rewerd=8.0
samplewi
24 14)
rewardel.
Figure 9: Pictorial description of our planted sub-sequence didactic setup: An example showing five samples drawn i..dd from very strong y 100, and relatively weaker y 15 policies in our didactic setup.
to improve upon sub-optimal expert μ appears in Chang al. (2015), but this work considers the structured prediction problem which is vastly different from our setting. Related to this, is the work by Chang al. (2023), which uses "guide" policy to rollout from prefixes generated by a base policy. The base policy can now imitate the guide by cloning those rollouts, and eventually surpass. Our work also uses a prover policy which can complete rollouts from states where the base policy fails. But, we also show that weak provers in many cases are able to improve the base policy, or search over its responses. better than stronger prover policy. We tie this observation to the insight that the main goal of the prover policy is to distinguish steps taken by the base policy. as measured by advantages under the prover. Thus, we do not require the prover policy to be something better than the base, that the base can rely on to clone rollouts that lead to correct final answers.
0.0
Heatmmap of 1y=100
0.2
Heatmap A" (y-iyy100
Samples
0.1
lavambage
Samples
7
Advaniage
0.0
-0.4
0.6
-02
Takens
Tokens
-0.8
-0.3
Figure 10: Comparing heat map of advantages from weak 10) and strong provers (y 100):. When the strength the prover policy increases, the magnitude step-level rewards reduces (since A" 0), as noted in the differences between the left (weak prover) and right plots (strong prover).
Magnitudes of step-level rewards for weak vs. strong prover policies. For 5 random samples drawn from the base policy, each with 10 tokens, we plot the values of the advantage A", at each token of each sample. In Figure 10, we plot heatmaps of the advantages for two different choices of the prover policy μ., one with y 10 (weak prover), and the other with y 100 (strong prover). For the weak prover, the advantage magnitudes are much higher, since the weaker prover policy is more likely complete partially correct generation over an incorrect one, i.e., generation where the last set of tokens in the prefix partially matches the planted sub-sequence. On the other hand, when the strength of the prover policy increases, the magnitude of token-level rewards reduces (A" z since it can complete the solution with nearly equal likelihood from both correct and incorrect prefixes sampled from the base policy. Thus, RL training with the effective rewards (equation 5) computed using strong provers performs similarly to RL training with only outcome rewards, noted in Figure 3b.
B DIDACTIC ANALYSIS
We consider sequences of length 10 from a 15-token vocabulary V = (0, 1, 122.....4), 14), where the end-of-sequence token is given by 14. Given unknown planted sequence y* (in Figure 9), we train a policy π with on-policy policy gradient, where the reward is terminal and sparse, i.e., for y we have y(y policy in our experiments is represented by multi-layer neural network, similar to the MADE architecture (Germain et al., 2015). The prover policy μ is parameterized by scalar y > 0. In particular, any state where the last & tokens leading up s match first & tokens of y*, then:
if and only if y* appears y, and 0 otherwise (Figure 9). The
ply (s) y.
15

---

Published as a conference paper at ICLR 2025
and uniform on all other tokens. Thus, as increases, the performance of μ improves and - 1 as y + co. For our experiments, we assume oracle access to ground truth advantage and Q-values, thus mitigating any confounding issues due to usage of learned verifier.
Training details. We use effective rewards with a = 1, and use the gradient in equation 5 to update the policy via policy gradient iterations. For the ORM runs, where we only use the outcome reward r, the policy gradient is equivalent to the case where a = 0 in equation 5. We train for 10,000 iterations in both cases, with a batch size of 64, and constant learning rate of le
for the Adam optimizer. The RL runs are initialized with a supervised finetuned policy. For this we take randomly initialized network, based on the MADE architecture (Germain et al., 2015), with layers, and 128 hidden units in each. Then we train it with supervised next-token prediction loss for 50 iterations on dataset of 3200 samples from a weak policy (y= = 5.0).
C ADDITIONAL DETAILS: EXPERIMENTS ON TEST-TIME SEARCH WITH PAVS
Implementation details. For our experiments in Sec. 4, we consider three base policies: Gemma 2B, 9B and 27B. We finetune each of these on the MATH (Hendrycks et al., 2021) dataset. The finetuning is done for 5000 iterations, with a batchsize of 32, with a maximum learning rate of 5e - 6 for 2B, 9B and 5e 7 for 27B policy. We used the Adam optimizer, with a linear warm up and cosine decay learning rate schedule. The linear warm up is done for the first 500 iterations only. Given the SFT checkpoints, we next train PAVs using the procedure in Sec. D. We do this for a class of provers, which include the base policies themselves. As we discuss in Sec. 4, the prover class also includes the best-of-K K policy for K in (2, 8, 323.
We used a hold out validation set to ascertain the value of in the effective reward. For each base policy we run beam search with a beam size of 16 on this hold out validation set, and using the base policy itself as a prover, we evaluate the value of that works best in the effective reward. We find that a = 0.5 worked best for Gemma 2B and 9B base policies, while a lower value of a = 0.2 was optimal for Gemma 27B. To tune a we ran a grid search over the range [0.0, 1.0], evaluating at an interval of 0.1. We observe that the choice of a is a relatively robust one, since for all three base policies, we saw improvements (over only Q" as the reward) for values in the range of [0.2, 0.6].
Experiment: Is the effective reward able to predict the final outcome better than Q In Fig. 11,
we describe an experiment where for both the effective reward Q aA and just Q", we compute the error of the classifier that makes prediction on the final outcome by thresholding on either reward value each step of the rollout. This threshold is computed using a validation set, and separate for each step and reward combination. The figure tells us that the outcome prediction error drops for both rewards, as the base policy is rolled out more, the effective reward dominates Q" across all steps. Thus, the effective reward is more informative signal (lower classification error) for the problem of predicting the success of a partial rollout, especially in the earlier steps of the rollout. This helps explain the better performance of beam search with finite capacity beam that re-ranks partial rollouts with the effective reward.
Explicitly comparing test-time search using our PAVs, with PRMs from prior works. Several works on automated PR.Ms, use the Q-function as the step-level reward Wang et al. (2024); Luo et al. (2024); Snell al. (2024). Each of these use the step-level rewards in different ways at test-time, and we compare with all of these approaches in Section 4. In Figure 4a, we compare the performance of PAVs with @ for test-time beam search (see the line for "PRM QT"",, as done in Snell et al. (2024). In the same figure, the line for "PAV-as-ORM" corresponds to using the trained PAVs as outcome reward models. i.e., to score the full sequence. The sequence is scored by computing the minimum over the step-level scores from the PAV model. This is similar to how Wang et al. (2024); Luo et al. (2024) use their trained PRMs during test-time search. In Figure 12, make these comparisons explicit. In addition, best-of-N search with PRM @ as done in Wang et al. (2024); Luo et al. (2024).
Experiment:
exactly the same procedure for test-time
We compute a 95% confidence interval over the true mean of the reported test-time search performance, for each algorithm in Figure 4, Figure 5 and Figure 6. This mean is computed over the randomness in the test data, and the randomness in the search algorithm. To account for both, we run each algorithm 5 times, and then use the 500 examples in the test set, to compute the confidence interval of the true performance of each independent run of the algorithm.
Confidence intervals:
16

---

Published as a conference paper at ICLR 2025
Predicting Final Outcome
0.8
PAV PQV
Error
0.4
0.2
2
3 4 5 6 7 8 9 10
Number of steps taken
Figure 11: Effective rewards at any step are able to predict the outcome rewards at the final step, better than
:Fo both the effective reward Qa + Ir and just Q*, we compute the error of the classifier that makes prediction the final outcome by thresholding
either reward value each step of the rollout. This threshold computed using validation set, and separate for each step and reward combination. The figure tells us that the outcome prediction error drops for both rewards, as the base policy is rolled out more, the effective reward dominates Q" across all steps.
PRM baselines
0.55
0.50
Accuracy
0.45
0.40
0.35
Wang et (2023), Lue et (20241 GRNI Snall al 12024) cor for beam search)
0.30
2
24
2
2
N
Figure 12: Explicit comparison with PRM baselines in prior works: We plot the performance of beam search with PRM Q run by Snell al. (2024), and best-of-N search with the same PRM run by Wang al. (2024); Luo et al. (2024). We compare both with heam search run using PAVs. Note that the search mechanism for PAVs and the one in Snell et al. (2024) is the same, with the only difference being in the re-ranking function at each step of the beam search.
Then, we average the means the confidence intervals across the 5 runs to compute the final 95% confidence interval.
Exploration--xxlootttion tradeoff in Result 3 from Section 4. For process rewards defined as our effective reward Q* aA",, as a O, the process rewards are purely exploitative, i.e. only upweight steps that are already likely to each the correct solution, under the current base policy π. the other hand, we increase 0, then we also upweight steps that are preferred under the prover policy When the prover policy and the base policy are not too misaligned i.e., F A" A sufficiently high, then in expectation, help the discovery of the correct solution, when sampling solutions from the base policy л. This is because, it is possible that some solution trace (set of steps) has low probability under but because is preferred (high A" for each step in the trace) by a complementary prover policy μ. the trace ends up getting positive reward, and gets up-weighted. This aids in the discovery of the correct solution.
expect for the the effective reward to explore new solution traces that might
D DETAILS ON COLLECTING DATA AND TRAINING PAVS
Collecting data. We predict Q= for policy by fine-tuning LLMs with cross-entropy loss triplets (s, a, Q (s. a)). Data is collected by sampling New seed rollouts from the base or prover policy (ORM PAV) for coverage, followed by aee additional rollouts per prefix to estimate Q via
17

---

Published as a conference paper at ICLR 2025
Scaling Laws: noe/
0.5
Amc/ocvv
2
Accuracy
4
0.4
8
16
0.3
32
64k
128k
256k
512k 1024k
Training Data Size
Performance of beam search over Gemma 9B SFT for PAVs trained on datasets with different Pmme/ where ficow is the number of initial seed rollouts, and Ame is the number of rollouts used compute the Monte Carlo Q-value estimate for each state in the seed rollout.
Figure 13:
Monte Carlo. As shown in Fig. 13, under low budgets, prioritizing coverage (Neov > Rme) improves performance, while higher budgets benefit from reducing label noise (Ame > neww).
We now describe the procedure for training outcome verifiers and PAVs. We can learn to predict Q" for a policy π (similar for Q") by finetuning LLMs with a cross-entropy loss on the following data with triplets (s, a. 2m a)). To collect this data, we first sample Movv "seed" rollouts from the base or prover policy respectively for ORM and PAVs, to promote coverage over prefixes and steps. Then we sample Am additional rollouts, conditioned on each prefix in the seed rollout to compute the MonteeCCrll estimate of Qa at each prefix. In Fig. 13 we plot the beam search performance of PAVs trained with different ratios of nas/n... as we scale the total dataset size. Here, the beam size is fixed to 128 and the base policy is the Gemma 9B SFT policy and prover is Bo4 policy. We find that under low sampling budgets, optimizing for coverage (Neuv Ame)) is better for performance, and when budget is higher, reducing label noise in Q.ee by setting Am > neow gets us more improvements. In addition, we also spend some initial sampling budget is spent identify "high value" states where Q is larger than a threshold, and identify the first step with low Q* on an incorrect partial rollout from this state. We found this strategy to scale better with dataset size.
In Fig. 13, our seed rollouts are i.i.d. sampled from π, but prior works (Luo et al., 2024; Setlur et al., 2024; Hwang et al., 2024) employed a "first pit" strategy for coverage. Here, some initial sampling budget is spent to identify "high value" states where Q* is larger than threshold. Then, for any incorrect sample from these high value states greater budget is spent to estimate the first step (first pit) with Qx O. All prefixes (and their estimated Q-values) until the first pit are then added to the training data. In Fig. 14, we compare beam search using PAVs trained using data from the first pit strategy, and the random sampling strategy. Both of them use the best value of mm//n from Fig. 13 for every dataset size. We find the first pit strategy to be better than random, especially when the number of seed rollouts are limited. Once get coverage over such pits, we sample a large number of partial rollouts conditioned on each prefix until the first pit. This is used to compute the Monte Carlo estimate of Q values more accurately on the path to the first pit. Each prefix and estimated Q value pair is then added to the dataset used to train PAVs.
Training details. All PAVs used in this work are trained by taking the Gemma 9B pretrained checkpoint and finetuning it on the data collected from the above strategy. The data collection uses first pit strategy for better coverage over pits in the seed rollouts. Based on findings in Fig. 13, we use a high value of n0200 to estimate the Q-values accurately for each step in the seed rollout. For each base policy, in total, we collect a dataset of over 300, 000 prefix, -=-value pairs (where Ôx is the Monte Carlo estimate) on which we finetune the Gemma 9B model with cross-entropy loss. Since the distribution of values for @x can be skewed, we split the range of -=-vuuues into two buckets, based on which we also partition the training data. The first bucket is the set of all prefixes with Ô= 0.5 and the second is the set of all prefixes with i= 2 0.5. Then, we use class-balanced sampling over these buckets to train the finetune the pretrained model for 20000 training iterations, using a batch size of 32. We use Adam optimizer with maximum learning rate of 5e - 7. We use linear warm up (till 2000 steps), and a cosine decay learning rate schedule to train the models. Since a pretrained L.LM would output matrix of logits (vocabulary size x sequence length) we fix token
18

---

Published as a conference paper at ICLR 2025
as the "scoring token" to be the end of the sequence / prefix that needs to be scored. The logits of this scoring token are then used to determine the prediction for the LLM being trained.
Scaling Laws: First Pit
0,5
First pit
Random
Accuracy
0.4
0.3
64k
128k
256k 512k 1024k
Training Data Size
Figure 14: First pit strategy from Luo et al. (2024); Settur et al. (2024): We compare the beam search performance (with beam size 128) for PAV trained on data collected using two types of seed rollouts. For the seed rollouts, either randomly sample from the distribution of state action pairs induced by the base policy. Or we improve coverage particularly using the "first pit" strategy of identifying the first state with low Q values on partial rollout that starts from a high Q Q-value state and ends with an outcome reward 0, i.e., Q value O.
Using trained PAVs: For test-time search over responses from the base policy and fixing a prover policy μr, the following is how we use PAVs for beam search at test-time. At any given time step, the beam holds partially generated responses (states) to math problem. We score each of the states using our effective reward Q* + aaA Since A" is computed using Q* (equation 2), we need only train verifiers predict Qa and Q", Finally, at the end of beam search, when only have complete responses in the beam, we pick the best response using an ORM trained only to predict the correctness of final answers, In practice, we find that using a trained ORM rate complete responses at the end of beam search is not critical, and using the PRM that predicts Q* to rank the full responses also performs similarly. So, the training of ORM model can be avoided.
E ADDITIONAL DETAILS: EXPERIMENTS ON RL TRAINING WITH PAVS
Experiment: RL training Gemma 9B SFT policy with PAV-RL. Similar to Figure 7)(c) where we compared the sample efficiency and raw performance of PAV-RL with ORM-RL for the Gemma 2 SFT base policy, in Figure 15, we compare the same for the Gemma 9B SFT base policy. Here, the prover policy for the effective reward in PAV-RL is the Gemma 2B SFT policy, which is worse than the Gemma 9B SFT policy, let alone the policy iterates during RL training. We find PAV-RL to boost sample efficiency by 5x, while being 6% better in raw accuracy.
Experiment: Discounting strong provers. In Section 5 we find that the better prover policy to train the Gemma 2B base policy is the Gemma 2B prover policy, and the stronger Gemma 9B RL policy. We attribute this finding to our discussion in Section 3.2, where we explain how very strong provers end up with advantages A" which are close most states generated by the base policy. But what happens if we account for the steps taken by the stronger prover policy to complete the solution? We test this with the following experiment
since they maybe able complete the solution from
We train PAVs to predict the advantages of discounted rewards from strong prover policies. Here, for the problem x, and the state, action pair s, a, the process rewards are given by the effective reward from equation 5: Qx + aA"", except that the advantage A" is the difference in discounted rewards, ie.:
a² = By-u( (s.a)
Ey-ut (s)
(en(())) Rex ( Re)
where the prover policy samples solution y with len(y) steps to complete the solution, from a state s, which already has len(s) steps in it.
For this setting, we train a verifier to predict discounted rewards for the Gemma 9B prover policy. We find that the discounted process rewards from the stronger 9B prover policy performs worse than
19

---

Published as a conference paper at ICLR 2025
Sample Efficiency (9B)
0.55
6%
Accuracy
0.50
5 x
0.45
ORM-RL
0.40
PAV-RL
10 18
26
34
42 50
Training Iterations (x (x10²)
Figure 15: Sample efficiency and performance gains for PAV-RL Gemma 9B SFT policy: We plot the test accuracy across PAV-RL and ORM-RL training iterations, where the base policy is the Gemma 9B SFT policy. The effective rewards PAV-RL boost sample efficiency by over outcome rewards in ORM-RL. Additionally, PAV-RL trained policy is 6% more accurate over than ORM-RL trained policy, when compared over the course of 5000 training iterations.
undiscounted rewards from the weaker Gemma 2B prover policy, when using either to train the 2B base policy with online RL (Figure 16).
The main reason for the discounted rewards to not enable the use of strong provers is because strong prover policies tend disregard states generated by the base policy (as illustrated in Figure 2b). This means, that irrespective of whether the weak prover policy generates partially correct or incorrect solution, when we rollout strong prover policy from this state generated by base policy, the strong prover directly attempts to answer the math problem with its own solution trace. Thus, from any state the strong prover expected to complete the solution with roughly the same number of steps. This means that A" 0 even in the discounted case, which reduces the ability of the strong prover policy to distinguish steps taken by the base policy.
Discounted Stronger 9B Prover vs. Undiscounted Weaker 2B prover
0.25
Accuracy
0.20
Discounted 9B prover
Undiscounted 28 prover
9 10 Training Iterations ( (x10²)
1
5
Figure 16: Comparing weaker, undiscounted 2B prover policy with discounted, stronger 9B prover: We plot the test accuracy across PAV-RL training iterations, where base policy is Gemma SFT policy, and two different options of the prover policy used in the computation of the effective rewards in equation 5. The discounted stronger 9B prover policy still under performs the weaker Gemma 2B prover policy.
Experiment: Using PRMs from prior works to assign step-level rewards during online RL. We also experiment with using the PRMs proposed in prior works Snell al. (2024); Wang al. (2024); Luo et al. (2024) as step-lever rewards in online RI. For this, we use Q base as the step-level score during RL training initialized with the base policy Tbase This step-level reward is used to reward trajectories sampled during online RL training, in addition to the outcome reward. We plot our results in Figure 17 and find that the test accuracy drops quite quickly, even though the train rewards keep improving, since the policy just learns hack the step-level Q-values, for the reasons we explain in Section 3.2. We see a similar collapse when we use Q" instead of A" (see Appendix G for qualitative examples).
20

---

Published as a conference paper at ICLR 2025
Comparing with PRM baseline Q in RL
Accuracy
0.2
Oaase Wang et, all (2023),
Lue et al. (2024).
0.1
Snell et. al. (2024))
PAVS (ours)
0.0
6 8 Training Iterations (x10²)
3
Figure 17: Using PRMs from prior works to assign step-level rewards during online RI: We take the PRM that predicts Q-values of the base policy, Le.. hase" and use it to assign step-level rewards during online RI. training, in addition to the outcome reward. Note that, Snell al. (2024); Wang et al. (2024); Luo al. (2024) used the same automated PRM Q to run test-time beam search or best-of-N search over Abase- We find that using the same for online RL leads to the step-level rewards being hacked for reasons we explain in Section 3.2.
Training details. As discussed in Section 5, the initialization for RL training the RFT (rejection finetuned) checkpoint for the corresponding base policies. More specifically, we consider two base policies Gemma 2B SFT, and Gemma 9B SFT, where the RL training is initialized with the policy obtained by further optimizing the base policy via rejection finetuning (RFT) Yuan et al. (2023). This is done to improve coverage over states and actions during the initial iterations of RL. For rejection finetuning we train the SFT model (base policy) on all correct trajectories sampled when collecting seed rollouts for training PAV' (that predict the advantage of the same base policy). The training details for RFT remain same as SFT and are detailed in Appendix C. The RI training is for 10000 iterations for the 2B model, and for 5000 iterations for the 9B model. For both we use the Adam optimizer with learning rate of 1e-7, and batchsize of 32. The maximum response length is set to 512. For both we used a learning rate schedule with a linear warm up for 10% of the total training iterations. The implementation of our policy gradient algorithm also uses a value function that is initialized to be the base policy itself. The value function is only used as baseline during RL training (REINFORCE).
Most importantly, we use validation set to identify good choice of a in the effective reward (in equation 5). For Gemma 2B this value is 5.0 and for the 9B policy a 3.0. Similar to the choice of for test-time search, we find that most values of in the range of 0.5 to 6.0 improved performance over ORM-RL, to different degrees. Both policies are also optimized with KL regularization, against the initial iterate of the RL policy, where the strength of the KL penalty is set to 0.001 for both.
We compute 95% confidence interval over the true mean the test accuracy, at each iterate of the RL training in Figure 7, Figure 15, and for each value of N in Figure 8. This mean is computed over the 500 examples in the MATH500 test set. For improved confidence intervals results with PAV-RL training in Figure 7(a), and find the performance across these runs to be 25.85, 25.77, 25.73 for the Gemma 2B SFT base policy and 55. 72, 55.89, 55.61 for the Gemma 9B SFT base policy.
Confidence intervals:
RL training with three random seeds
Tuning a in practice. In practice we arrive at the ranges for searching over the hyper-parameter through systematic procedure on hold-out validation set. This procedure can be potentially repeated for any new problem instance where PAVs need to be used. In particular, we tune ar with a two layer search strategy where the outer layer search coarse- coarse-grained and used to identify good high-level range of a values such that the performance of PAVs is comparable to ORMs (i.c., PAVs don't yield degenerate solutions). The inner layer of search more fine-grad -reiggr and used tune the performance of PAVs even more. Note that both these layers of search are carried out on a small hold out validation set. Additionally, as we state below, the outer level of coarse-grained search is already good enough for PAV' to outperform ORMs search and online RL. For both test-time search and RL we identified a "good"' range of a by running binary search. Since
the MATH benchmark, for both beam
O, we start with high value of 10., and then keep reducing it by half (10 - 5 + 2 + 1) until we see a run of test-tine time beam search or online RL that yields a non-trivial performance improvement over only using outcome rewards. During this outer level binary search,
21

---

Published as a conference paper at ICLR 2025
stopped at 5.0 for online RL and 1.0 for test-time search. Once identified the range, we rum a second level of fine- ane-grained search search, i.e. we search linearly between a E [0.0, 1.0] in intervals of 0.1 for using PAVs at test-time, and E [0.5, 6.0] in intervals of 0.5 for using PAVs as process rewards in online RI.. As we state in the paper, the choice of a within this range is quite (1.5,5.5) for online RL puts PAVs in
robust. Any (0.1, for test-time search and regime where the performance of PAVs for either is better than only using outcome rewards.
F THEORETICAL ANALYSIS: COMPLEMENTARY PROVERS AMPLIFY BASE POLICY IMPROVEMENT
In this section, we present the proofs for our theoretical results in the main paper (Sec. 3.4). We begin by describing some notation we use our proofs, the natural policy gradient algorithm we use for the policy update, followed by the proofs for Theorem 3.1, and Proposition F.I. Our results in this section are in the tabular setting, with softmax parameterization of the policies. Note, that for the deterministic Markov decision process induced by the LLM, we are indeed in a tablular setting, where the set of states and actions is discrete, but large and grows exponentially in sequence length.
Notation and preliminaries. We d7.df, d' to denote the distribution over states &4 at time step h, starting from the initial state distribution given by the empirical distribution over the questions in the dataset D, and following the base policy x, prover policy μ respectively. Mathematically,
h-1
d (s% (x. an-1))
<an
swy- (x, ..........: awr
XED
The term d denotes the distribution over future states, starting from state s, and following policy æ. Here, s can be a state at any time h E [O...., HH. For convenience, we overload the notation d (the distribution over future states induced by a policy starting from state s), and use d to denote the distribution over states de starting from random state drawn from p. and following policy æ.
The term (s,, as)) refers to the value of state-action pair Sh, ah, i.e., the expected return in the future, starting the policy from state Sn and taking action an:
2 ("h, an) = Baas - (-ssn.))) Rex
(())....a...3)))
a
Note that y known the dataset D, and state sa contains the question x as part of it. Similarly, we can define the value function V ($)) of a state sn as:
(*,,)) == Ban-r
(S
(8)
The advantage function then given by:
A 2*(sh. ax) == (*),,, (*))).
The policy gradient algorithm use update the base policy iteratively updates the base policy, and we use n, to refer to the base policy iterate at time 1. Finally, we use S to denote the set of all states and A for the set of all actions that the LLM can take at any state.
Parameterization of the base policy. We adopt the softmax parametcrization for the base policy:
exp(Osn.a)
xa(a 5n)
(10)
Ed'e (
Here 0s,.a E 2 is a class of parameters, that controls the probability of taking action a at state $h- The full set of parameters across all states and actions is denoted by 0 E Rdx[5(*( Whenever clear from context, overload the notation x, to denote both the policy iterate 1, i.e. no, and the parameter 0, itself. Similarly, the operator Vx, [-], is referring to Vo, [-]-
Defining policy improvement. Let p be a distribution over all states {sh h E 10, 1,.., HJ], then V**))) and (H give us the expected value functions over states across time steps, measured under p. for policies and respectively. We assume that d and d are both absolutely continuous with respect to p. and the expected value function over p the quantity we track before and after a policy update. A positive change in V*-PV'(s) implies a net positive improvement in the base policy. Thus, progress made at each update of the policy when:
Vy Tr (s)
Ex-p , (s) 0.
22

---

Published as a conference paper at ICLR 2025
F.1 NATURAL POLICY GRADIENT
The natural policy gradient (NPG) algorithm (Kakade, 2001) defines a Fisher information matrix (induced by the policy), and performs gradient updates in the geometry induced by the following matrix:
(T) B5 (-is) x log s) (v log s))
(11)
Typically, the NPG update does gradient updates the objective LORM-RU
x1 = = +, + FF V ( (T) n
(12)
where Mt denotes the Moore-Penrose pseudoinverse of the matrix M. We restrict using the initial state distribution in our update rule, Lee, we restrict attention to states s reachable from p. since governs the performance measure of interest when evaluating the expected value of policy. Thus, without loss of generality, we can exclude states that are not reachable under Specifically, we restrict the MDP to the set of states {Sb 3x such that d (8p) 0, h [0. ..........
F.2 USEFUL LEMMAS
Lemma F.1. [The performance difference lemma; (Kakade & Langford, 2002)] For all policies nt' and states So,
(*( - (v*)s) Bsn-dz Ban (x(pm))))))))))))
A (sh:
Proof. See proof of Lemma 6.1 in Kakade & Langford (2002).
Lemma F.2 (Natural policy gradient update). For the natural policy gradient in equation 12, the corresponding policy update is given by:
(a 5) = x s)) exp (A'(s, + a. AH a) AB,
(13)
('(s)
Z'()) y. Σ (A'(s,a)+a (s,,a))
(14)
Proof. We arguments similar to the proof of Lemma 15 in Agarwal et al. (2021), with the key difference of separately accounting for the term ("(s, 4). For the sake completeness we reproduce some of the derivation, accounting for the A term in the process. We follow compatible function
approximation in Sutton et al. (1999) and Kakade (2001). For a vector w e ddx[S|AA we define the error function
1.a (w) = Bx-dz. (a-x(-1s) (w V
v log x () (A" a) (sA((s
(15)
Let w* be the minimizer of (ww with the smallest & norm. Then by definition of Moore-Penrose pseudoinverse:
** = (((())/x-a,.onntar V logs(a)s) (A (s" +aa
=F,(x) 'v (I)
(16)
In other words, w* is precisely proportional to the NPG update direction. Note further that for the Softmax policy parameterization, we have:
w loog = =ssa"
Σ a d'ER
Since Ene (s,)s) = 0, this immediately yields that (7 + aA") However, this might not be the unique minimizer of L" which is problematic since w* (TT) defined in terms of the Moore-Penross pseudoinverse is formally the smallest norm solution to the least-squares problem, which A AA may not be. However, given any vector R [S let consider solutions of the
23

---

Published as a conference paper at ICLR 2025
form A + aA" +v. Due to the form of the derivatives of the policy for the softmax parameterization, we have for any state s, a such that s is reachable under p.
v (ag))
Σ (v ov =a'I= vs,a'((a'(ss)) = Vssaa E'EM
Σ a'EA
((a)ss
This is because π is stochastic policy with x(ass) > O for all actions in each state so that if state reachable under p. it will also be reachable using π, and hence the zero derivative conditions apply at each reachable state. For A" + aA" - B, + v to minimize L*, we would like v V log Tr( rals)) = 0 for all s so that Vx,a is independent of the action and can be written as constant for each s by the above equality. Hence, the minimizer of L L"(w) is determined up to stale-dependent offset, and
(0 ' PAV A + a' + v,
where Vs,a Cs for some Cy E R for each state and action Finally, we observe that this yields the updates
11+1 = y(A + +v and (r+l(a|s)= π, (als) exp(y (s, ya)"(s,a))
('(s)
Owing to the normalization factor (s)), the state dependent offsets cancel in the updates for π, which yields the statement of the lemma.
F.3 PROOF OF THEOREM 3.1
Proof. For some notational convenience, we use V", yr+1 to denote the value functions V V for policies at π₁ πt+1 at time r and r + 1 respectively. Similarly, we use A', A'* for A A "Ms respectively. For the distribution over states di"t' induced by the policy 44+1, starting from initial distribution of states given by p. we simplify the notation and use dz.). Similarly we use df, for d.
Next, for simplicity we set a in the natural policy gradient update in Lemma F.2. It is easy to see that the lower bound result we show holds for any value of O, and the term in the lower bound scales linearly with a. Note, that this is not a free variable, and a has to be O(1), since we increase the value of a we would have to correspondingly reduce y for our result to hold. For now, we fix 1.
From the policy difference Lemma F.1, we can write:
Bx-p vi+ (s) Bx V'(() (s) By-a,- B- [A'(s, as)
(17)
Next, from the natural policy gradient update in Lemma F.2, we can write A' as) as:
n (a (a|s) asssa))
A' A'(s. a) y log
as
(18)
r' s)
Substituting equation 18 in equation 17 we get:
1 B [KL(='+( (-1))l (-
B Bitplit Vx
y
1 - log Z' (s) -B (a))) A"
(19)
y
Recall that for a 1,
log Z' (s) log
B Ba exp exp (A'(s,a) (A A"
(20)
Applying Jensen's inequality we get:
log Z' (s(s 2 y. Eg- (18) (ss
(21)
y Bu (-bs (s)
(22)
24

---

Published as a conference paper at ICLR 2025
since Ex (s) =.
Note that in equation 19 the KL term is always non-negative. Thus, we can lower bound our policy improvement as:
-B.ppp)))) Bs-a (. x' (s,,))))""s.))
(23)
where the inner product is the standard euclidean product as our actions space A discrete.
In the following we will treat the distribution x- s) as vector denoted by л Next, from the NPG update we know that:
exp (xp(y'(ss,a)) + yA" -1)
nd (a 8) - xa (s) = a' [s)
(24)
Z'(s)
We note that for y < 1, y a)) a() = 0 + y + A"(s, ())), where the terms that grow as w)y) are being ignored. Based on this, for < 1, constants 0 < Ci C2 such that:
exp(yA'(s,.) y - (C
1 C2yBalir'( (A'(s. As) -1)
(=
x" (al (a (a ()
s)
(a'(a 5) (A' (s, a) + A - (1 5)BB [A'(s, + (")s
Czy
(25)
1+ 1+C2yBa-n [A' (a. a) + Ar)
C3y (T' (a 5) (A' (s, (s, a)) Nr (a (a [A [A)(s.))])
(26)
1 yCy [4 (s, + A)),
where we reused: Exr [A'(s, a)] O. Here, C3
a constant.
We now plug in the above lower bound into equation 23 to get the final lower bound on the policy improvement Theorem 3.1. For this, we will once again use the assumption that the learning rate < I, which allows us use + yEa-m, (als) [A'(s, a) A a)] C4 for some constant C4 0. This is because, our setting the range of the advantages is [-1, 1]. Since, advantages are bounded in [-1, 1], we know that + yC2Ba-aa (alx) [A' (s(ss)) a) a)) s 1 y, where < 1. Thus,
C3
Ex-p ((rt((() - ( 2 -
yE y (a--x(aas) a'
+yB s-d
Ba-r((ab)) (A)
(Ba-xilak) ())
yB BB
Setting from Theorem 3.1 as C3/1-y,
Bx-p (s)+((s) (s) v*)) 2 yB
Ba (als)
(s)
+ +Cy +CyBs-of1
Ba-x' (als)
(A)
-CyB-dff))
(a (A'
(27)
This gives us,
Ex-p [ (s)-v'(s)) v'((s) 2 CyE (Va-miaass) (s, - Ea-z (als) (A"(ss
(28)
25

---

Published as a conference paper at ICLR 2025
Now, for the last step note that d is component wise larger than p, and this gives the final result:
Bs-p (s) 2 CyBs-p (Va-m [A (s, a)] - -Ba-n (ats) (s'(ss (29)
F.4 DISCUSSION ON REMARK 3.1
First, note that if the value of base policy state, action pair (s,a) is (s, a), then for the prover set to the best-of-K policy (oK(x), the Q value at the same state, action pair is:
(30)
This is because, in our setup the final outcome of correctness given by Rex is random variable taking values in {0, 1}, with expectation (" when completing a rollout starting from prefix treat the outcome as a Bernoulli. Now, we can simply compute the probability
as,a). Thus, of sampling a single correct answer out of K attempts, which is also a Bernoulli random variable with mean given by Q" (s. a) in equation 30.
Next, we observe that whenever @"(s.a) a) < e.e.g. when a=) O(1KK), for all values of (s,a), we can do the taylor approximation of (" a) around and note that @" a) O(K ())ss))).
=
Next note that:
V (s,a) = (=)"(s,a)
(s,A"ssa))
= [1 - -1 -1--1Q
= =Va (=1(100ss.
This means that the first term in Theorem 3.1 which measures "distinguishabilitt"" now increases by factor of x2. Similarly, we can see that the the term which measures "misalignment" can change in magnitude by factor of OKK, since the misalignment term is linear in Q These two observations combined lead us to the final remark in Remark 3.1,
F.5 IMPROVING A STRONGER BASE POLICY WITH A WEAKER PROVER POLICY
In Proposition F.I, we consider the case where the æ and a differ in performance, as measured under the distribution of states p in the following way:
Bx-plIV"(6 - v (x)] =
Next, whenever the prover's preference over actions is complementary to the base policy, by factor of n7 i.e.,
(s, Q(n),
then the variance of A" or A th under n, should scale 172.
Thus, we see that when πi, fails to distinguish actions (i.e.. Es-p v,, (A a)] is small) regardless of the strength of prover policy μ. as long as sufficiently complementary to n,, the prover policy induces an improvement in base policy, that scales as n??
Proposition F.1 (Complementary boosts improvements in T). Under the distribution given by let prover μ and base policy at iterate 1, H,, differ in absolute performance, i.e., Ex-plIV" (s) 7T (s)]]- When Bx-p" Va-x, [A (s. a)] < Ex-p Y Va-x [A" (s, a)}, and μ is comple- mentary to n4, iee, Ba--Ba--x, =0 (s.a) Q" (Sh. a)l 2(n). then Ex-p [V (s) z (s)) ?
states
26

---

Published as a conference paper at ICLR 2025
Proof. We begin by proving upper bound on the disagreement between prover and base policy:
Ex-pEa-m 10 a) Q (s.a)
x Es Bs--pBa- (Q" a) - (*,, Ex-pBa-R, (s, - (s,
s Bs Ba- 12 (s. (s. B (1 V [s)]] Ba-x 10 (s.
I ( 4 x [A (s,a)),
where the last inequality Cauchy-Schwarde Next we apply Jensen's inequality the terms in the square root, and the conditions that Ex Ba 10 (s. a) - Q" (sn. a) 22(1)) to conclude:
Br-py V (A a)] ス 4
(s.a)) a) Invoking the result in Theorem 3.1 yields: whenever Ex-p a- [A (s,a)) < Bx-p V x- (A.
Es-pIVAin (s) yM (s)
G EXAMPLES GENERATED BY BASE POLICY TRAINED ON Q" + aQ"
When we train the base policy with reinforcement learning where the reward is Q" aQQ instead of the effective reward Q + arA we find that the policy training converges to contrived solutions with degenerate failures. For example, we see in multiple examples (like the four below), that for every question, the model learns to output "REPHRASE THE PROBLEM" as the first step. This because under Q" this trivial step achieves a positive reward. While there exists better solution where the policy outputs the correct answer and achieves higher rewards, it fails to recover from this local optima and find a better solution. Across multiple training runs, we observed similar trends when training with Q* aQ" Note that in the idealized update, where we observe advantages A or value function Q"" on all actions at a state (e.g., in the NPG update in See. 3,4), using Q" aQ equivalent to Q AA" But, in practice. A" offers significant benefits in the form of variance reduction in policy gradient iterates. It does that by not assigning reward to steps like "REPHRASE THE PROBLEM", since the likelihood of prover solving before after this step is expected be roughly the same (i.e., the prover policy makes no progress).
Example
0: My club has 23 members. In how many waya can choose members to form 4 4-person executive commit:ee?
200
RRFHRASE, PROBLAM WD NEED TO FIND THE NUMBER OF MAYS TO CHOOSE 4 MEMBERS OUT OF 25 FOR THE EXBCUTIVE THE COMDINATION
N C N! / 18! A (N !) WHERE IS THE TUTAL NUMBER DE KEMBERE AND IS
NUMBER NEMBRRS CHOOSE: 50
CASR
25 AND
PLIG THRM AND
SIMPLIFY 25 25! / (4) (25 4)1) (25 24 23 22) (4
1) 104005
Answer
104005
Example
have triangle Axtriangle ABCS and point SXS $ecS such that SAKS is an altituda of sttriangle ARCS, TF SAC 10, SRK 75, and SRC 13, then 9Xiriangle ABCS?
what
>>>
REFERASE: THE PROBLEM WD NEED TO FIND THE AREA OF eXtriangle ABCS so NE CAN USB THE FORMULA SA \frac:1 THE SDIGIT SINCE IS ALTITUDE, THAT SAX \perp #C$ so WE CAN US2 8803 AS THE BASE AND $AKS AS THE HEIGHT SO NOW KE NEED
WHERE BASE
27

---

Published as a conference paper at ICLR 2025
TO FIND 9AKS SO WE CAN USE Angwer
THE PYTHASORE THEOREM ON 9'trringle AXC3 SINCE 9AC 108
18
Example
0: suppose that Sn, n+1, n+2, n+3, n+45 are five consecutive integers.
Determine simplified expression for the of these five consecutive integers.
REPERASE THE PROBLEM
NEED FIND THE SUM OF THESE FIVE CONSECUTIVE INTEGERS CAN USE THE FORMULA $8_8 \frac(n) (n) (a_1 8 WHERE $8_n8 IS THE SUM, 8n8 IS THE NUMBER TERMB,
$a_1$ 15 THE PTRST TERM, AND $a_ns Tа CEB LAST TERK SO IN THIS CASE án 5, a_l
AnsweE
5n
Example
0: What the value of 9x"2-y"2-8"242xg when Sx--35, Symas, and $aw-68?
>>>
REFURASE PROBLEM
WE NE2D TO FIND THE VALUE OF 3x"2+""2=="2222g" WHEN 9xm-39, Sy-55, AND $2m-49
s0 WE JUST PLUG THE VALUES AND SIMPLIPY
Answer
H COMPUTATIONAL COST TRAINING AND USING PAVS OVER ORMS
The training data for PAVs is collected by running rollouts to estimate the Q-values for each step. Since learning to predict expected future success at earlier steps statistically more challenging task than predicting the final score at the end of the complete sequence (as in ORM). the training data for PAVs is larger and scales with the average number of steps in the LLM'ss output (= 10 in our case). in order be able to achieve the same level of prediction accuracy all steps in generation. With a 10x larger dataset, naturally the computational cost of training PAVs (compared to ORMs which only predict final outcomes) also scales by roughly the same factor.
Despite a larger cost for training PAVs, once trained, PAVS are much more compute-efficien than ORMs on questions. In other words, while do incur larger training cost, this cost is amortized over rounds of deployment. Concretely, as we show in Section 4.1, for test-time search, PAVs are 1.5-5x more compute efficient than ORMs, at achieving the same level of performance (Figure 4 in submission). This means that if we were to use verifier at least twice upon deployment, PAV is already more compute-effin efficient than ORM, accounting for both the training and test-time compute cost of PAVs.
For online RI,, as we show in Section 4 (Figure 7c), PAVs achieve the same level performance in 1 16th of the RL training iterations that ORMs require. But in our implementation, for each iteration, PAV' score each step by feeding each prefix in generation separately through the trained model, and ORMs only score the full trajectory. Thus, in this implementation PAVs consume 10x more compute per batch to score the generations more efficient implementation would score all prefixes in generation in single forward pass through the trained PAV. Nevertheless. the reduction in RL iteration complexity with PAVs is big enough that the overall computational cost is less, compared to ORMs. For example, using the
batch (since we have 10 steps on average per generation).
28

---

Published as a conference paper at ICLR 2025
formula for training and inference FLOPs in Hoffmann al. (2022), during online RL, to train the Gemma 2B base policy with PAVs, we need to spend about 2.5 x 10 FLOPs, but to achieve the same performance with ORMs, we need about 5.9 10 FLOPs, resulting in at least half the total computational FL.OPs.
1 CONNECTING THE EFFECTIVE REWARDS TO REWARD-SHAPPHS POTENTIAL FUNCTIONS
The effective reward we define in equation 5 matches the definition of potential-based reward shaping term, as defined in Ng et al. (1999). Before we explain why this is the case, we provide some background below.
Background on potential based reward-shaping functions: In Ng al. (1999), instead of learning a policy for reward function R, the policy trained to optimize the transformed reward R F. Here, F(S,, dh, Sh+1) is reward shaping function, that takes as input the the current state Sn, action taken by the policy ah, and next state Sh+1, and maps this to a scalar reward. particular, they show that when the shaping function F is antential-basee i.e., it is of the form:
F(Sh. ahe Si++1) ( ((s)),
for some state-dependent potential function d, then the policy that optimizes the transformed reward R + F, also optimizes the original reward F.
In Equation 5, our effective reward function is: (* an) a'A This reward function matches the functional form of the transformed reward function + F defined in Ng. et. al. (1999). Here, Q" corresponds to the reward R, and aAA' aạ) is the potential-based reward function F. To see why F satisfies this definition we use the definition of advantages from Equation 2. We can write a'A an) as:
(Q" an) - v*(ss)) = ar - V*(s)))
Following the theoretical result on potential-ban -based reward shaping functions in Ng et al. (1999), the optimal policy under our effective reward Q* + aAl also lies in the set of optimal policies which only optimize the outcome reward (final answer correctness, or )*).
J DISCUSSION, LIMITATIONS AND FUTURE WORK
We began our exposition with the following question: how to define process rewards such that optimizing the base policy against process rewards ultimately improves the outcome level correctness of the final answer? Our key finding is that process rewards defined as advantages of prover policy, distinct from the base policy improve the efficiency exploration for steps sampled from the base policy during test-time search and online RL. This improved exploration in turn leads to discovery of better solutions, resulting in a higher accuracy on the math reasoning task. We also formally characterized the set of good prover policies as policies with step-level advantages that meaningfully contrast steps generated by the base policy, while still producing step-level advantages that are al aligned with the base policy. Having trained process advantage verifiers (PAVs) to predict advantages under the prover policy, we empirically observed that test-time search against the trained PAVs improve the compute-efficiency of search by 1.5 5x, and accuracy of search by over 8% compared to running oest-of-N against an ORM. Next, we present one of the significant results that validate the use of dense supervision when optimizing the base policy with online RL. Specifically, we show that dense online RI. with rewards from our trained PAVs, improves sample efficiency of online RI. by 5 6x, and results an accuracy gain of over 6%. Despite the promise of our results, there are several limitations to our work that present important avenues for future research. First, while we can easily compute the right hand side of our result in Theorem 3.1 to understand whether given prover policy will improve a fixed base policy, it is unclear how to automatically design a flexible class of optimal (or very good) prover policies for sequence of base policy iterates. Perhaps simultaneously optimizing the prover and the base policy (in a two-player game) might provide for an approach to obtain the best prover during RL, but this is largely open question. Second, since inevitably learning process advantage verifier
Limitations.
29

---

Published as a conference paper at ICLR 2025
(PAV) will incur fitting errors and this upper bounds peformance of method. Fitting errors can be circumvented our approach if we can simply run rollouts from prover policies during online RL or search to estimate advantages without training verifiers, and extending approach to this setup is good avenue for future work.
K COMPARING PAVs WITH METHODS DESIGNED TO IMPROVE TEST-TIME EXPLORATION
In this section, we aim to explicitly evaluate the exploration capabilities of PAV. Note that our goal is not to claim that PAVs are the best approach to exploration, but instead to compare PAVs to an existing exploration method to understand if building on our approach of connecting process rewards with exploration and potential functions, and designing novel forms of process rewards could be a fruitful endeavor for future research on exploration in LLMs.
Specifically, we compare test-time beam search guided by process supervision from PAVs with the importance weighted search approach outlined in Alphal.L.M (Tian al., 2024), an approach that runs MCTS for search. We use the heuristic from AlphaLLMM and our preliminary results show that PAVs are 8x more compute efficient at test-time beam search, as outlined below.
Background on Alpha LLM: For the importance weighted search approach of AlphaLLM, we implement beam search in the following way. At any given point, the beam consists of N states $1, $2, SN These are partially unrolled solutions from the base policy π, up until state si (prefix). We then expand each node in the beam 3 times. by conditionally sampling from π (conditioned on each of the states in the beam). We get N x states, which we rank with the following scoring function and then select the top N state. Each of the new expanded states is of the form s, a, where is the previous state in the beam and a ~ x(( s) is the new sampled action (step). Following, Section 4.3 from Tian et al. (2024), the score for the new state (s, a) is e* @*((saa) a) + C U(s) where Us)) is the uncertainty bonus for the state s, which is computed as U(s) = /nis)/EN m(s)). We use C= 0.25, which we identified by tuning performance over hold out validation set use for PAVs as well. This resembles UCB or UCT-style exploration. Concretely, ((s) is the effective number of children for node (Section 4.3.2 in Tian al. (2024)). The term n(s) C' ((s) is computed by linearly scaling the importance (()) defined as ((s) = max (V*(s) - Q (s. a)l, where a is one of the 3 actions sampled from state when expanding the beam. We tune and set C' = 2.0. Intuitively, AlphaLLM chooses to explore states that can change the Q-values by a lot, when we continue to sample from them. When the Q-values deviate by lot, the I(s) term increases. Consequently, so does (s)) (effective children count) and U(s) (uncertainty bonus).
PAVS vs. AlphaLLM
0.55
8 X
0.50
Accuracy
0.45
0.40
0.35
PAV (ours)
AlphaLLM
0.30
21
23
24
2
20
N
Figure 18: Comparing the exploration capabiliiies of PAVs with AlphaLLM (Tian et al., 2024): We find that PAV' are more compute efficient. This is likely because the exploration metric in AlphaLLM (Tian et al., 2024) uses the absolute magnitude of the advantage under the base policy, vs. PAVs which use the signed advantage under the prover policy. Thus, our exploration metric prefers steps that increase the likelihood of a complementary prover to discover the correct solution, as opposed to preferring steps that simply change the previous state's value function (under the base policy) by the largest magnitude (which can also he negative).
30

---

Published as a conference paper at ICLR 2025
L
WEAKER POLICIES ARE BETTER PROVERS FOR GEMMA 9B RL TRAINING
Sample Efficiency (9B)
0.55
Accuracy
0.50
0.45
9B prover prover
0.40
18 26
34 42 50
Training Iterations (x10²)
Figure Weaker Gemma 2B Policy a better prover for Gemma 9B RL Training: train the Gemma 9B SFT policy further via online RL where the dense rewards are given by the effective rewards in equation 5. When we use the weaker Gemma 2B SFT policy as the prover, we are able improve the Gemma 9B policy much more than the effective rewards that use the stronger Gemma 9B SFT policy the prover.
In Figure 19, we provide supporting empirical evidence for our claims in Section 5, where stated that we found the weaker Gemma 2B SFT policy to be better prover for updating the stronger Gemma 9B base policy with dense rewards during online RL, as opposed using the Gemma 9B SFT policy as the prover. Furthermore, the Gemma 2B SFT prover rapidly becomes even weaker than the initial base policy (Gemma 9B SFT policy) within a few gradient steps of RL, but fixed PAV that uses the weak Gemma 2B SFT prover is able to still sustain performance gains in RL.
31


Reviews:
[{"review_id": "QBahFCXJaN", "reviewer": "Reviewer_pfy5", "summary": "This paper introduces Process Advantage Verifiers - a novel approach to training and using process reward models for improving LLM reasoning. The key contribution is showing that process rewards should measure progress, which defined as advantages under a prover policy rather than just step correctness. The authors demonstrate that PAV can lead to significant improvements in both test-time search efficiency and online rl sample efficiency.", "questions": "1. Have you explored applying PAVs to other structured reasoning domains beyond mathematics?\n2. Could you clarify the computational overhead of training and using PAVs compared to traditional ORMs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novel insight about measuring progress through advantages rather than Q-values\n2. Theoretical analysis characterizing good prover policies as those \"complementary\" to base policy\n3. Clear empirical validation showing significant improvements over baselines", "weaknesses": "1. Evaluation only on mathematical reasoning tasks\n2. Could benefit from testing on other structured reasoning domains\n3. All experiments on a single model family (Gemma)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "eCeNzDDALu", "reviewer": "Reviewer_CgRb", "summary": "The paper proposes a method for improving reasoning abilities of large language models on math problems. Given a math problem, the model generates an answer autoregressively. The reasoning steps can be considered actions in a search space. The method is based on the advantage function as a (shaped) reward, and then uses RL to further train the base policy.\nThe results are demonstrated on the MATH dataset where the final answer is a numerical one, which makes the validation of the outcome relatively straightforward.", "questions": "In Equation (5), the effective reward is added to the return in the formula for the gradient. What is the reason of this apparent contradiction?\nThe authors argue that a strong model cannot be used as a prover because a strong policy can reach the answer from any state. I think this is only true if the value function does not take the answer length into account, i.e., it is not discounted and there is no per-step cost. An interesting follow-up would be to re-evaluate, for example, Figure 3b with value functions including a per-step cost.\nWhich example does line 197 (\"based on the example\") refer to?\nLine 267 states that RL with effective reward achieves a tenfold improvement in sample efficiency, but I cannot see this is Figure 3a. What is this improvement based on?\nIn some of the figures, there is a shaded area. It should be specified what they mean (std deviation? confidence intervals?) and what sample size they are based on.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea is clear, it has appropriate theoretical foundations, and the authors empirically demonstrate the advantage of the proposed approach.", "weaknesses": "It is not clear whether they propose this as training or test time improvement. More precisely, I assume that both, but at certain places it is not evident which one the paper is talking about.\nI am not convinced by the argument that the proposed effective reward scheme improves exploration. I do not think this is properly motivated either intuitively, theoretically or empirically. Also, the suggestion of the improved exploration is not related to checking correctness and relevance.\nIn the second paragraph of Section 3, around lines 157-159, the authors reference the potential functions from Ng et al. (1999), but the description is vague, and it does not seem to match the original definition.\nThe language should be reviewed, including repeated words.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "9RyWyqOy0W", "reviewer": "Reviewer_11y4", "summary": "This work addresses the design of process reward models (PRMs) in the context of online reinforcement learning with an LLM base policy. The key problem the authors presents is that existing PRM approaches rewards only Q-score - the expected accuracy given a current state and a next action. They identify that absolute Q-score in beam search favors actions that might have high Q-score but might have little or negative improvement from the current state. Instead, they propose to use Process Advantage Verifiers (PAV) using the difference or process advantages between Q-values of a next action and the previous action to identify, using a separate prover policy to compute these process advantages rather than a base policy. They provide intuition and theory that PAV performs well with a prover policy that is not too misaligned with the base policy but can discriminate well between different actions. Their experimental results show significant accuracy and efficiency gains over both Outcome Reward Models (ORM) and other PRM baselines. The work additionally demonstrates accuracy and efficiency gains in the online RL setting.", "questions": "* As the use of a separate prover is a key part of the work's novelty, it does not seem appropriate that a key result Proposition F.1 is relegated to the Appendix, along with the explicit characterizations of what is a \"complementary\" policy. \n\n* Authors show many negative qualitative examples of inappropriate prover policies in Figure 2 and Appendix G, but do not seem to provide any positive examples of good prover policy results. \n\n* The introduction of a prover policy $\\mu$ in equation (2) of section 3.1 seems slightly confusing. The initial construction of $A$ uses the base policy $\\pi$ throughout and only later notes that $A$ can be computed under any policy. This section would flow better if these were differently ordered or reworded.  \n\n* Why was (Snell et al. 2024) chosen for a representative PRM baseline in Figure 5a)? \n\nMinor things: \n* There appears to be a typo and inconsistent notation in Appendix B as the 15-word vocabulary set only has 14 elements. The example in Figure 10 shows this set should be 0-indexed but the set in Section 3.3 and Appendix B are 1-indexed. \n\n* Figure 5b is difficult to read due to similar colors used (Similar shades of red/orange).", "limitations": "", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Methodology is mostly clear and well-elaborated on motivations by walking through didactic example in section 3.3 and intuition behind prover policy selection in 3.4. \n\n* Results in experiments is well-outlined in sections 4 and 5, and shows significant improvement over ORM and PRM baselines. \n\n* Idea of using a separate \"prover\" policy to compute advantage is interesting and novel, including the discussion on the choice of complementary policy.", "weaknesses": "* This work has some issues in communicating and emphasizing important aspects of using a separate prover policy, which is a key part to distinguish from Shao et al. 2024. \n\n* I'm concerned by the lack of comparison with other PRM baselines. The work notes there are several competing PRM approaches (Appendix A), but section 4 seems to only compare with only one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "K9v5RSYjzu", "reviewer": "Reviewer_Ys2B", "summary": "The paper looks at the the problem of training LLMs for reasoning - which in this context means, given a problem, going through multiple steps to arrive at an answer. Authors argue that training and inference in reasoning models can be improved through extending simple outcome-based reward models with a dense, advantage-based reward models. The key insight is that the advantage should be computed under a separate (\"verifier\") policy, which is neither too strong (since any action under the weak base policy would be just ignored and verifier would succeed anyway) neither too weak (the verifier policy would fail anyway).\nThe paper first motivates and elaborates on those insights with some toy experiments and theoretical formalisation, and then applies the conceptual understanding to fine-tune Gemma LLMs (2B, 9B, 27B) on the MATH dataset, obtaining significantly better results (in sample efficiency, accuracy and compute efficiency) than models fine-tuned with outcome-based rewards investigated in the prior literature.", "questions": "- How do the results change if we introduce non-unit discount factor?\n- How to situate using PAV to encourage exploration among the alternative approaches already studied in the RL literature?\n- Theorem 3.1 seems to have a typo, the second term should appear with a negative sign. In general, adding an advantage function is a form of potential shaping, as you note in the introduction, which means that the set of optimal policies should be preserved under any verifier. But the bound in Theorem 3.1 can be negative for very misaligned $\\mu$ and $\\pi$, can it? Does that mean that the update step can be negative? If yes - when can it happen?\n - In section 3.3, your reward $r$ is binary - what do you mean by \"the maximum reward $r$ across $N$ samples\" in Fig 3c)?\n - You grid-search for a good $\\alpha$. Do you think that the value you found (3.0 - 5.0) will generalise across tasks? What is the cost of the search?\n - You want $\\mu$ primarily to be able to distinguish between actions of $\\pi$. Would it help if you ran multiple verifiers at the same time?\n - Remark 3.1 did not felt sufficiently motivated by the preceding paragraph.\n - Notation in the Appendix F: it might be worth spelling out that the distribution $d^\\pi_s$ is marginalised over all future time steps (or just writing the definition). It's not clear to me why is $\\theta_{s, a}$ assumed to be in $\\mathbb{R}^d$. Typo in eq 8: it should read $a_{h+1}$. Typo above eq 18, should read $A^{t}$. Typo in line 1124, should read \"equation 23\". In general, it's not clear to me what happens in the step of moving to eq 27 from eq 26. What happens to $C_1, C_2, C_3, C_4$? What exactly is the meaning of $\\lesssim$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is very clearly written. It is full of intuition, it guides the reader through conceptual, toy-experimental, theoretical and empirical results, every step seems motivated, there are very helpful \"Takeaway\" summaries at the end of each section, the figures are clear and aid the understanding. There is a clean, coherent narrative. I enjoyed reading it a lot.\n - Formal results are not extremely complex, but they correspond to the empirical treatment well, and provide additional tools for the empirical part (such as motivating the use of best-of-k policies). The proofs (in the appendix) are formal and clearly written, and do not take shortcuts. Theoretical development includes the policy improvement framework and beam-search analysis for the best-of-k case.\n - Prior work, although in large part delegated to the attachment, is referenced extensively.\n - Experiments are convincing and done on a relatively large scale.\n - Overall, the method described in the paper seems clearly useful and promising.", "weaknesses": "- The (final) experimental section seems a bit too narrow. Although authors reference the \"conventional belief\" of using mathematical correctness or relevance of steps in the introduction, they only compare to the baseline of ORM reward. It is difficult to judge how much of an improvement we should expect in other domains, as other SOTA MATH models are only briefly referenced (and not compared to) in the appendix.\n - There are multiple places where the paper claims that the major benefit of using a correlated, high-variance verifier is to encourage exploration. But there are many ways to encourage exploration: epsilon-greedy policies, UCB, max-ent regularisation etc. It seems that the paper advocates for using the verifier only because it takes unnecessarily strong position on only using greedy beam search. This makes sense as the choice within the framework, but it again makes it difficult to judge how much of an improvement the new method really is, compared to those other techniques.\n - The insight of \"it's bad to use extremely good expert policy to judge moves\" seems a to apply less in a context where we use a discount factor $\\neq 1$. A strong move would still help even a strong expert, if it saves it time to arrive at the solution. It is not clear to me whether a \"need to generate simpler, repetitive, and even incorrect steps to explore and discover the final answer\" really applies in general.\n- I had trouble understanding when (or whether) introducing the sub-optimal verifier can result in a worse behavior, or when does $\\mathbb{E}[V^{t+1} - V^t] < 0$. Some confusion arose because the verifier is initially assumed to be just a fixed $\\mu$, while it is actually $\\mu(\\pi_t)$ (e.g. best-of-K($\\pi_t$)).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "zTJQjLoopy", "reviewer": "Reviewer_jZuo", "summary": "The paper proposes process advantage verifiers (PAVs) that provide process rewards improve the efficiency of test-time search leading to better accuracy. Outcome reward models (ORMs) and process reward models (PRMs) assign reward to the final outcome/per-step respectively. The paper proposes the use of PRMs as a dense reward generator but changing the reward allocation to provide advantage values instead so that better exploration may be encouraged. The key intuition is that reinforcing promising steps that make progress towards the goal improves exploration of possible answers and is crucial when employing search-based strategies such as beam-search.\n\nThe authors utilize a toy example to show that Q-values may be retaining unfavorable steps reducing the overall likelihood of success. Thus, the authors resort to the advantage framework (Sutton et al) and show that by considering advantages (relative increase/decreases in likelihoods of success) we can mitigate the drawbacks of only using Q-values.\n\nThe authors then introduce PAVs and introduce the optimization objective. The  authors argue that using advantage values derived from the same base policy would not be informative. The authors then propose to use a different prover policy (this lightly connects the optimization objective with off-policy learning). The paper then shows that a good process reward measure is a prover policy that provides a notion of progress. The authors analyze this hypothesis using a toy example. The authors then showcase a theoretical intuition that states that a prover can be expected to improve a base policy when it is able to distinguish different actions taken by the base policy. The authors then showcase that Best-of-K policies (sampling of K policies from $\\pi$ and then using the best one) contains complementary provers.\n\nFinally, the authors propose an empirical evaluation to showcase the advantage of PAVs over ORMs.", "questions": "Please address my concerns in the weaknesses. \n\nAlso, could you please elaborate on what you mean by lines 369-374? If I interpret the writing correctly, does it mean that PAVs cannot be used directly in beam-search without having access to PRMs and ORMs? It would be great to clarify my concerns and perhaps improve the clarity of the paper to make it more accessible.\n\nOverall it is a good paper. I hope the authors can resolve my concerns.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The paper tackles an interesting concept and the notion of using advantages is quite intuitive. The use of advantages is well known in the AI community and its application to neural verifiers is a novel contribution.\n\nS2. The analysis of showing that weak provers may amplify stronger base policies is convincing.", "weaknesses": "W1. The paper is generally well-written but is a bit confusing to follow at times. There seems to be a lot of \\vspace manipulation that conflicts with ICLR paper guidelines (example sec 3.1, ICLR guidelines stipulate that there must be 1 line of space after figure caption). This made the paper a bit hard to read. The related work is very light and the conclusion is non-existent with no future work or limitations discussed. I believe that the paper could have reduced some of the analysis and expanded on this further.\n\nW2. The paper focuses its empirical evaluation on ORMs and states that there are major advantages w.r.t. them but I believe that a fair comparison would be to use PRMs since they are the closest possible baseline. The authors do prempt this by stating that PRMs have only demonstrated 1-2% improvement w.r.t. ORMs but that is in the context of best-of-N search. There are no comparisons with PRMs except for Fig 5a. However, this improvement is not discussed nor is the setting adequately mentioned making it hard to evaluate. Are the PRM results in Fig 5a computed using beam-search or best-of-N search.\n\nW3. There are recent results of utilizing beam search or some tree-based search with PRMs [1, 2]. This would likely be more compute efficient than ORMs or PRMs utilizing best-of-N search. As a result, the compute efficiency would be best to be compared to them. Is there any reason this was not considered.\n\nW4. The paper claims to have significant improvements but lacks a comprehensive comparison of PRMs w.r.t. standard benchmarks as reported in other papers. I am unable to distill where the claims of massive improvement stem from esp considering that two different search strategies are employed and in the case where PAVs-as-ORMs are used, the improvement drops to 4%. Similar comments for results in Sec 5. PRMs are a natural fit for RL as well I would assume.\n\nCould the authors please justify their empirical evaluation. There is a lack of evaluations on GSM8k and other standard datasets and some baseline combinations that utilize beam search are not expressed. I fully appreciate the authors extensive ablations and analysis but I feel that to truly understand the utility of PAVs as neural verifiers/reward models, one would need to compare them with the same search strategy but just a different ranking scheme (PRMs vs PAVs). Could the authors please provide additional details here?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "j7jassZ1qO", "reviewer": "Reviewer_7XQD", "summary": "This paper mainly discusses how to design process rewards when using process reward models (PRMs) to improve reasoning in large language models. The authors believe that the per-step process rewards should measure progress, or advantage, instead of absolute Q-values for a better explore-exploit tradeoff  during beam search and online RL. The advantages should be computed using a prover policy different from the base policy. To boost improvement of the base policy, the prover policy should be able to distinguish actions taken by the base policy but are not too misaligned from the base. Based on this insight, the authors introduce process advantage verifiers (PAVs) and show that PAVs could largely scale test-time compute and RL sample efficiency compared to outcome reward models (ORMs).", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper is well-organized and well-written. The concepts and ideas are clear and could be easily understood.\n2. The results are promising. The proposed method (PAVs) are > 8% more accurate and 1.5-5x more compute-efficient than ORMs.\n3. The insight to define process rewards as progress (or advantage) is inspiring. The method proposed (PAV) is novel.\n4. The paper provides comprehensive analysis and guidance on how to choose prover policies and how to collect data to train PAVs, which is very beneficial to the community.", "weaknesses": "1. In the experiments, only ORM is presented as a baseline, without any inclusion of previous PRM methods. It would be more helpful if you include baseline methods such as [1] Wang et al. (2024), [2] Shao et al. (2024) or [3] Luo et al. (2024) to demonstrate how they perform poorly compare to your method. Alternatively, could you clarify if there were any particular challenges in implementing or comparing to these previous PRM approaches?\n2. Although the theoretical analysis is solid, could you provide a small, concrete example to illustrate why advantages are more effective than value functions as process rewards? This could help readers to understand your statement in Section 3.1 (Process rewards should be advantages not value functions) better.\n\n[1] Wang, P., Li, L., Shao, Z., Xu, R. X., Dai, D., Li, Y., Chen, D., Wu, Y., & Sui, Z. (2024). Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations. https://arxiv.org/abs/2312.08935\n\n[2] Shao, Z., Wang, P., Zhu, Q., Xu, R., Song, J., Bi, X., Zhang, H., Zhang, M., Li, Y. K., Wu, Y., & Guo, D. (2024). DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. https://arxiv.org/abs/2402.03300\n\n[3] Luo, L., Liu, Y., Liu, R., Phatale, S., Lara, H., Li, Y., Shu, L., Zhu, Y., Meng, L., Sun, J., & Rastogi, A. (2024). Improve Mathematical Reasoning in Language Models by Automated Process Supervision. https://arxiv.org/abs/2406.06592", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "GhieeQsWNf", "reviewer": "Reviewer_UVHt", "summary": "The paper proposes a method for designing rewards for Process Reward Models, used to improve reasoning in LLMs with step-by-step feedback rather than only outcome-based feedback. The authors relate the reward to a measure of how much a step changes the likelihood of producing a correct response in the future. They discuss their method for obtaining this measure and compare it to alternatives. They provide theoretical and empirical results to support their claims that their approach improves accuracy and efficiency.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I am not an expert in this specific area so I cannot confirm the originality or significance of the paper, but the authors do discuss related works and compare the paper with them. The paper is generally clearly written, though I suspect it is even easier to follow if you are more familiar with the topic than I am. I really like the ‘takeaways’ at the end of each section for improving intelligibility. The paper includes both theory and empirical results. I like that it discusses potential alternative solutions and why these were not pursued or would not work as well as the proposed approach.", "weaknesses": "Can you please point me to where you formally characterise what it means for the prover policy to be “too” misaligned with the base policy?\n\nDoes your work help improve the speed of reasoning by decreasing the number of steps required, or does it just improve the chances of finding the right answer eventually? I presume this relates to how long a rollout is. Related to this, you say in Line 82 that ‘advantages under an overly capable prover, that can succeed from any step, fail to distinguish between good and bad steps.’ Why do you not then consider the number of steps required to get to the solution from that point, as a way of quantifying ‘improvement’?\n\nDo you formally quantify the exploration-exploitation trade-off that feeds into Result 3, since this seems important for your findings that you can improve accuracy?\n\nLine 73 / 74 - repeated ‘the the combinatorial’.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Spotlight)