PRM variants: what a step score means

Every PRM outputs a number per step. The variants differ in what that number is trained to mean.

In Chapter 06 we met the PRM as a classifier that reads a reasoning prefix and returns a score \(q_t\). Two papers can both call their model a PRM while one predicts "a careful human would mark this step correct" and the other predicts "if we keep sampling from here, we will probably reach the right answer". Those are different quantities, they are learned from different data, and they fail in different ways.

The five variants in this chapter are:

1. Human-supervised PRM: is this step correct?
2. Rollout (Monte-Carlo) PRM: can this prefix still succeed?
3. Value-style PRM: how promising is this state, and how much did the step help?
4. Generative PRM: reason about the step in words, then judge it.
5. Search-aware PRM: use the scores to decide which partial solutions to keep.

Write the problem as \(x\) and a solution as steps \(s_1,\ldots,s_T\). The prefix after \(t\) steps is

Almost every discriminative variant is then trained with the same masked binary cross-entropy, which accepts both hard (0/1) and soft (fractional) targets:

Because the loss is the same, the architecture is the same, and even the numbers look alike, it is easy to forget that the label is what gives \(q_t\) its meaning. The rest of the chapter is about labels.

Annotators read a solution step by step and mark each step. In PRM800K the marks were positive, negative or neutral; a neutral step is acceptable but not clearly useful. How neutral maps to a training target is a design choice. The model learns local correctness:

Example. Steps \(s_1\): "\(20\%\) of \(100\) is \(20\)", and \(s_2\): "the discounted price is \(100+20=120\)". Labels \([1,0]\). A trained PRM might predict \([0.97,\,0.08]\), giving a loss of \(\tfrac12\big[-\log 0.97-\log 0.92\big]\), which is \(\tfrac12(0.030+0.083)\approx 0.057\).

The label is the closest to what we mean by "a correct step", and it does not depend on any policy. The price is human time: every label needs someone able to check the mathematics.

What label should a step get if it follows a mistake? "Therefore \(x=7\)" may be valid algebra applied to a wrong equation. Calling it correct rewards building on an error; calling it wrong punishes good algebra. The common way out is to stop labelling at the first error. Let

Under this convention \(q_t\) is read as the chance that step \(t\) is correct given that all earlier steps were. That reading gives the step scores a clean probabilistic meaning.

The first identity justifies the product aggregation of Section 11. The second turns a PRM into an error locator: the most likely first-error step is the \(t\) that maximises \(P(\tau=t)\). Benchmarks such as ProcessBench evaluate PRMs on exactly this task of finding the earliest wrong step.

Human labels do not scale. Math-Shepherd replaced them with simulation: from each prefix \(z_t\), a completer policy \(\pi\) samples \(M\) continuations, and each is checked against the answer key, giving outcomes \(R_1,\ldots,R_M\in\{0,1\}\). Two labels can be made from the outcomes:

The hard label says "at least one continuation reached the right answer". With \(M=5\) and outcomes \([1,1,1,0,0]\), the soft label is \(0.6\) and the hard label is \(1\).

A soft rollout label is an unbiased estimate of the success probability of the completer from that prefix:

This is the value function of Chapter 07, not step correctness. Three consequences matter.

• Policy dependence. The same prefix gets a high label under a strong completer and a low one under a weak completer. Labels go stale as the policy improves.
• Noise. With \(M=8\), the standard error at \(V=0.5\) is \(\sqrt{0.25/8}\approx 0.18\) (Equation 7 of Chapter 07).
• Hard labels are lenient. A prefix with \(V=0.1\) and \(M=8\) gets \(y^{\text{hard}}=1\) with probability \(1-0.9^{8}\approx 0.57\).

Labelling every prefix of a \(T\)-step solution costs \(T\cdot M\) rollouts. If we only want the first-error labels of Equation 4, we can do better. Take a solution whose final answer is wrong, so the full prefix fails, and assume that once a prefix becomes unrecoverable it stays so. Then the first error is the first prefix whose rollouts all fail:

and under the monotonicity assumption \(\hat V(z_t)=0\) holds for every \(t\ge\hat\tau\), so the search can halve the interval at each query. The OmegaPRM method builds on this idea and embeds the binary search in a Monte-Carlo tree search so that rollouts are shared across queries.

For \(T=16\) this needs \(\lceil\log_2 16\rceil=4\) queries instead of up to 16. The savings grow with solution length. The cost is that every weakness of Section 6 remains: a false zero from too few rollouts moves \(\hat\tau\) earlier, and a lucky success moves it later.

A value-style PRM accepts that rollout labels measure future success and trains for it on purpose:

Chapter 07 developed this model in full. Here we only note how it changes the meaning of a step score. Take \(37\times 19\) with two valid first steps. A: \(37(20-1)=740-37\). B: "add 37 nineteen times". A local correctness PRM gives both about \(0.95\). A value PRM gives \(V_A=0.94\) and \(V_B=0.52\), because B has many more chances to slip.

The step itself is then credited by how much it changed the value, the progress or advantage of the step:

If \(V_0=0.70\) before the first step, A earns \(+0.24\) and B earns \(-0.18\). A restatement of the problem earns about \(0\). Setlur et al. argue that progress should be measured under a separate prover policy rather than the policy being trained, so that it reflects how much a step helps rather than how well the current policy happens to continue from it.

The variants so far map a prefix straight to a number. A generative PRM first writes a verification of the step, then gives a verdict. This is the generative judge of Chapter 09 applied step by step.

Candidate step: \(3(x+2)=3x+2\). A generative PRM writes:

A score is read from the verdict. Either take the probability of the "correct" token after the critique \(c_t\), or sample \(K\) independent verifications and count:

The written check lets the verifier spend more computation on hard steps, and sampling \(K\) verifications trades cost for reliability. The verdict can still be wrong, and a fluent but mistaken check is persuasive to a human reader. Cost is the main drawback: one verification per step per candidate.

The last variant is defined by use rather than labels: the PRM decides, during generation, which partial solutions get more compute. Two settings are common.

Best-of-\(N\). Sample \(N\) complete solutions, score each with an aggregate \(S(y_i)\) of its step scores (Section 11), and return the best. A softer version, weighted voting, sums scores over solutions that reach the same final answer \(a\):

Step-level beam search. Keep \(B\) prefixes, expand each, and keep the best. With a local-correctness PRM, a branch's running score is

so one very low step score sinks the branch. With a value PRM, the current \(V_t\) is used directly. Example: three expansions score \(0.91\), \(0.18\) and \(0.77\); with \(B=2\) we keep the first and third.

Snell et al. compared best-of-\(N\), beam search and lookahead search with PRM verifiers and found that the best choice depends on problem difficulty and compute budget. The same step scores can also serve as dense rewards for RL, as in Chapter 06, where every weakness discussed below is amplified by optimisation.

Best-of-\(N\) and reranking need one number per solution. Five aggregators are common:

Compare a clean solution with \(q=[0.95,\,0.90,\,0.92,\,0.90,\,0.95]\) and the same solution with one bad middle step, \(q_3=0.10\):

Which aggregator fits depends on the label. For a local-correctness PRM under the first-error convention, the product is the probability of no error (Proposition 15.1), and the minimum is a robust stand-in. For a value-style PRM, \(q_T\) already estimates the success of the whole solution, so the last step is a natural choice, and taking the product of values would multiply overlapping estimates of the same event. The mean is the weakest detector: an error in one step of five moves it by at most a fifth of the drop.

• Rollout labels disagree with step correctness. Section 6 gave both directions: correct steps with low labels and wrong steps with high labels. A PRM trained on such labels inherits the disagreement and is weaker at locating the first error.
• Correct but useless steps are rewarded. A local-correctness PRM gives high scores to restating the problem or checking trivial facts. Append five such steps with \(q=0.99\) to the clean solution of Section 11: the mean rises from \(0.924\) to \(0.957\) and the geometric mean from \(0.924\) to \(0.956\), while the product falls from \(0.673\) to \(0.640\) and the minimum stays at \(0.90\). Under a mean, padding pays. Progress rewards (Equation 10) give such steps about zero.
• Search over-exploits PRM errors. Search selects whatever the PRM scores highest, including its mistakes. If each wrong candidate independently has a small chance \(\varepsilon\) of outscoring every correct one, then with \(N_w\) wrong candidates

With \(\varepsilon=0.02\) this is about \(0.08\) for \(N_w=4\) but about \(0.73\) for \(N_w=64\). More candidates give more chances to find a PRM error, so accuracy can stop improving, or fall, as \(N\) grows.

• Step segmentation. "Step" usually means a line or paragraph. If the PRM was trained on one segmentation and used on another, its scores drift.
• Distribution shift. A PRM trained on one policy's mistakes may miss the different mistakes of a stronger or different policy.
• Outcome leakage. A PRM may learn to guess whether the final answer looks familiar instead of checking the step in front of it.

The rows split along one line. The first and fourth rows judge a step backward, by local correctness. The second and third look forward, at future success. The last row is about what we do with either kind of score.

An 8-step solution ends with a wrong answer, so \(\hat V(z_8)=0\). We want first-error labels using \(M=8\) rollouts per query. If we estimated every prefix, we would find \(\hat V(z_1),\ldots,\hat V(z_7)=\tfrac78,\tfrac68,\tfrac68,\tfrac58,\tfrac48,\tfrac08,\tfrac08\). Binary search sees only the ones it asks for.

This chapter ends the series. Looking back, the fifteen chapters moved along a few axes. What is judged: a whole answer (scalar RM, ORM), a single step (PRM), or the future of a prefix (value model). What is output: one score, several scores, or text with a verdict (multi-objective, generative and critique-then-score models). How it is trained and used: pointwise, pairwise and listwise losses, implicit rewards inside the policy, conditioning on instructions, uncertainty from ensembles, and rules combined with learned judgement. PRM variants sit where these axes meet: the same step score can mean correctness or future success, be produced by a classifier or by a written check, and be used for training or for search.