Back to paper library
arXiv 2023ICLR 2024Model adaptationPaper notes

Let's Verify Step by Step

Which step went wrong?

Original paper

Let's Verify Step by Step

Paper authors

Hunter Lightman · Vineet Kosaraju · Yura Burda …

Show all 10 authors

Hunter Lightman · Vineet Kosaraju · Yura Burda · Harri Edwards · Bowen Baker · Teddy Lee · Jan Leike · John Schulman · Ilya Sutskever · Karl Cobbe

Publication
ICLR 2024Conference
First submitted to arXiv
arXiv:2305.20050
Cite this paper · BibTeX

The citation identifies the linked source version. It cites the original paper and its authors.

@misc{modeltuningletsverify2023,
  title = {{Let's Verify Step by Step}},
  author = {Hunter Lightman and Vineet Kosaraju and Yura Burda and Harri Edwards and Bowen Baker and Teddy Lee and Jan Leike and John Schulman and Ilya Sutskever and Karl Cobbe},
  year = {2023},
  eprint = {2305.20050},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.20050}
}
On this page

A solution to a math problem is often a dozen or more steps of derivation strung together. Get one step wrong and the answer is wrong, no matter how nicely the rest is written; worse, sometimes a step in the middle is wrong and the answer still happens to come out right.

A common way to make models more reliable is to train a reward model that tells good solutions from bad ones. It can be used for reinforcement learning, or at inference time to pick the best of many candidates. Either way, the whole system is at most as reliable as its reward model.

How should the reward model be taught? In 2022, Uesato et al. at DeepMind compared two approaches: outcome supervision, which only checks whether the final answer is right, and process supervision, which checks every step. On GSM8K, grade-school math, the two ended up performing about the same.

Lightman et al. at OpenAI ran the comparison again, this time with a stronger model (GPT-4), far more human labels, and much harder problems (MATH, at the level of high school competitions). The conclusion came out differently.

Defining the problem

The two kinds of reward model differ in their training signal:

  • Outcome-supervised reward model (ORM): learns to predict whether an entire solution is right or wrong. The labels can be generated automatically, because every MATH problem has a final answer that can be checked automatically. At inference time, the model's prediction at the last token is taken as the solution's score.
  • Process-supervised reward model (PRM): learns to predict whether each step is right or wrong. This can't be judged automatically; people have to label it step by step.

ORM labels have a built-in loophole. A solution with faulty reasoning whose answer happens to be correct gets labeled as right.

This paper studies only the reward model itself; it doesn't use the reward model for reinforcement learning on the model that writes the solutions. The evaluation is best-of-N: fix a model that produces solutions (the generator), sample N solutions per problem, let the reward model pick the highest-scoring one, and see what fraction of problems end up solved. The more reliable the reward model, the more often it picks a correct solution.

Solving the problem

Models at two scales

The large-scale models are all fine-tuned from the GPT-4 base model. This base model was only pretrained to predict the next token and never went through RLHF. The goal is to build the best possible ORM and PRM.

The small-scale models have a GPT-4-like architecture but used roughly 200 times less pretraining compute. They serve for controlled experiments that would be unaffordable at large scale.

Every model first gets an extra round of training on MathMix, roughly 1.5 billion tokens of math-related data that improves mathematical reasoning.

The model that generates solutions is fine-tuned as well. The authors had the model solve MATH training problems with few-shot prompting, kept the ones it got right, and trained for one epoch on those solutions. The only purpose is to teach it a one-step-per-line format so steps are easy to split; it isn't meant to teach it new skills.

Labeling step by step

Original Figure 1. A screenshot of the labeling interface. The problem asks: the denominator of a fraction is 7 less than 3 times the numerator, and the fraction equals 2/5; what is the numerator? (Answer: 14.) The solution is split into six steps, each with three buttons beside it for labeling it negative, neutral or positive: Let's call the numerator x., So the denominator is 3x-7., We know that x/(3x-7) = 2/5., So 5x = 2(3x-7). and 5x = 6x - 14. are all labeled positive, and the last step, So x = 7., is labeled negative.
Original Figure 1, Lightman et al., from PDF page 4, arXiv license, scholarly quotation.

Labelers read solutions written by the large-scale generator and give every step one of three labels:

  • Positive: the step is correct and reasonable, and it makes progress toward the answer.
  • Negative: the step is wrong or unreasonable.
  • Neutral: ambiguous, for example slightly misleading, or technically correct but not a good direction.

Keeping the neutral option defers the decision on how to handle ambiguous cases; at inference time, neutral can be treated as either positive or negative. Labelers are given the correct final answer but not a reference solution, so they don't favor one particular way of solving the problem.

The result is PRM800K: 800,000 step labels from 75,000 solutions to 12,000 problems. With not enough problems to go around, the authors also used 4,500 problems from the MATH test set as training problems and evaluated only on the remaining 500, drawn at random. The appendix confirms that the difficulty and subject distribution of these 500 are close to those of the full test set.

Which solutions to show labelers

Labeling is expensive, so it pays to pick informative solutions. A solution that is obviously wrong teaches little even after it's labeled.

The authors' strategy is to pick "convincing wrong-answer solutions": ones the current best PRM scores highly but whose final answer is wrong. Since the answer is wrong, the PRM misjudged at least one step, and having a person mark which step it was patches the PRM's blind spot. During data collection, the PRM is retrained several times on the latest labels before the next batch is picked.

How the PRM is trained and how it scores

After the last token of each step, the PRM predicts a token that stands for right or wrong, and training maximizes the log-likelihood of this token the way an ordinary language model is trained; no special architecture is needed. At inference time, one forward pass over the whole solution gives the score for every step.

A solution's overall score is defined as the probability that "every step is correct," that is, the product of the per-step probabilities of being correct. In the problem from the labeling interface, the first five steps are right, and from 5x = 6x − 14 you should get x = 14, but the last step says x = 7. If even one step has a low probability, the product is low, and the PRM can point to the step where it went wrong.

The product has a side effect, too. The more steps there are, the smaller the product. A twelve-step solution at 0.95 per step scores about 0.54, lower than a two-step solution at 0.8 per step (0.64). In the appendix, the authors compare four scoring schemes (neutral counted as positive or negative, combined by product or minimum), and the differences are all small:

Neutral stepsProductMinimum
Counted as positive78.277.6
Counted as negative77.477.8

Compiled from Table 4 in the paper's appendix; % solved, best-of-1860.

The whole paper uses the best-performing cell: neutral counted as positive, combined by product. The authors also acknowledge that the product slightly penalizes solutions with many steps.

Labeling only up to the first mistake

Process supervision labels only up to the first wrong step and leaves the rest unlabeled. This keeps the comparison between the two kinds of supervision fairer.

For a correct solution, both kinds of supervision give the same information, namely that every step is right. For a wrong solution, both know there's a mistake somewhere, and process supervision also knows which step it is. If labeling continued past the first mistake, process supervision would have even more of an information advantage.

It also keeps the human cost about the same. Without a ready-made final answer to check against, deciding whether a solution is right already amounts to finding its first mistake. MATH problems all have answers that are easy to check, and the authors expect this condition won't always hold in more complex domains.

Discussion

Large scale: the PRM clearly wins

Original Figure 3. The small table at the top gives the best-of-1860 solve rates: ORM 72.4%, PRM 78.2%, majority vote 69.6%. Below, the solve rate is plotted against N, the number of solutions per problem (log axis, from 10 to about 2,000). The orange PRM line leads throughout and keeps rising, reaching about 78% at the far right; the blue ORM line levels off around 72%; the gray majority-vote line is lowest, stalling at about 69% to 70%. The gaps between the three lines widen as N grows.
Original Figure 3, Lightman et al., from PDF page 7, arXiv license, scholarly quotation.

To make the ORM as strong as possible, the authors trained it on 100 solutions sampled uniformly per problem. That's an order of magnitude more data than PRM800K, and the two datasets don't overlap at all.

Picking one of 1,860 solutions per problem, the PRM solves 78.2%, the ORM 72.4%, and majority vote 69.6%. The ORM is only a little better than majority vote, while the PRM clearly beats both, and the larger N gets, the wider the gap. For picking the correct solution out of a large pool of candidates, the PRM is the most reliable.

The authors also tried weighting majority vote by the reward model's scores, hoping to get the best of both, but it didn't help noticeably.

Small scale: separating the confounders

The large-scale results have two confounders. First, the two models are trained on different data: the PRM's data was actively selected, skews toward wrong answers, and is an order of magnitude smaller. Second, judging correctness by the final answer labels solutions with "wrong reasoning, right answer" as correct, which drags the ORM down; whether that should be blamed on outcome supervision is debatable.

Human labeling is too expensive for these controlled experiments. Instead, the authors used the large-scale PRM (called PRMlarge below) as the labeler, producing labels for the small-scale models and simulating large-scale data collection cheaply.

Original Figure 4. (a) Best-of-500 solve rates for four groups of reward models against the number of labeled solutions per problem (1 to about 200, log axis). From highest to lowest: PRM with active learning, PRM (labeled by PRM large), ORM (labeled by PRM large), ORM (labeled by final answer); both PRM groups are clearly above both ORM groups. (b) For three reward models trained on 200 solutions per problem, solve rate against N at inference time (1 to 1,000): the PRM leads throughout, reaching about 60%; the ORM labeled by PRM large reaches about 53%, and the ORM labeled by final answer about 48%.
Original Figure 4, Lightman et al., from PDF page 8, arXiv license, scholarly quotation.

With 1 to 200 solutions sampled per problem, the same data gets three kinds of supervision: process supervision with step-by-step labels from PRMlarge, outcome supervision where PRMlarge only judges whether the whole solution is right, and outcome supervision by checking the final answer. The only difference among the three groups of models is how they're supervised.

Whatever the amount of data, process supervision clearly beats both kinds of outcome supervision. Between the two kinds of outcome supervision, judging with PRMlarge beats checking the final answer, because it can mark "wrong reasoning, right answer" solutions as wrong.

The authors consider the group judged by PRMlarge the more appropriate baseline. In domains where this kind of false positive is rare, outcome supervision would behave more like this group; on MATH, the false-positive problem may be exaggerated.

Active learning: first train a small PRM on 1 solution per problem and have it score 1,000 solutions per problem. Then pick N per problem, 80% of them the wrong-answer solutions it scores highest and 20% the highest-scoring of the rest (right or wrong), and hand them to PRMlarge for labeling. Comparing the slopes of the two fitted lines, this kind of active learning is about 2.6 times as data-efficient as uniform selection.

At 200 solutions per problem, performance falls slightly below the trend line. The authors' explanation is that 200 is already a fifth of the 1,000 candidates, so there isn't enough diversity left to choose from. They also tried repeatedly retraining the selecting PRM during collection, but ran into an instability they couldn't diagnose, and the results were no better.

New problems it hasn't seen

MATH problems circulate widely online and may show up in pretraining data. The authors also gathered the latest AP Physics, AP Calculus, AP Chemistry, AMC10 and AMC12 exams, all released after the pretraining data was collected. They sampled 100 solutions per problem:

ExamORMPRMMajority voteProblems
AP Calculus68.9%86.7%80.0%45
AP Chemistry68.9%80.0%71.7%60
AP Physics77.8%86.7%82.2%45
AMC10/1249.1%53.2%32.8%84
Aggregate63.8%72.9%61.3%234

Compiled from Table 1 of the paper.

As on MATH, the PRM beats the ORM and majority vote. On hard problems like AMC, majority vote gets only 32.8%, while the PRM gets 53.2%.

Why process supervision works better

The authors' explanation is credit assignment. Outcome supervision only tells the model "this solution is wrong," and the model has to guess where; on harder problems, nearly every solution the model writes contains a mistake somewhere, so the label "wrong" carries less and less information. Process supervision tells the model directly that the earlier steps are right and which step went wrong, a much richer signal.

The authors also discuss it from the alignment angle. Process supervision rewards reasoning that people endorse rather than looking only at the outcome, so it's easier to interpret and less likely to teach the model to exploit loopholes in the reward. Safer approaches often cost some performance, which is called the alignment tax; here, the safer process supervision actually works better, and the authors call this a negative alignment tax. They also caution that whether this conclusion generalizes beyond math is still unknown.

Limitations

  • Test set contamination: the authors used string matching to remove MATH problems from MathMix, but paraphrased versions that are hard to detect may exist online, so it can't be guaranteed to be fully clean. They inspected the model's solutions and saw no obvious signs of memorized answers; even if there is a little contamination, it should affect all methods in a similar way, leaving the relative comparisons largely intact. The PRM often picks out correct solutions that the generator itself writes with only a single-digit percentage chance, which also supports this.
  • Only the reward model is studied: the PRM isn't used for reinforcement learning to train the generator; the authors leave that to future work.
  • Human cost: PRM800K's 800,000 step labels rely on a large amount of human labeling, and it has only been done for math.

What came next

Those 500 test problems were later packaged as MATH-500, which became one of the most common benchmarks for reasoning models. DeepSeek-R1's pass@1 on MATH-500 is 97.3%.

Someone soon found a way around the cost of human labeling. Math-Shepherd, from December 2023, uses no human labelers. Instead, from each step onward it has the model write several more complete solutions, checks how many of them reach the correct answer, and uses that fraction as the quality of the step. Its authors overlap with those of DeepSeekMath.

The PRM also became the main tool for search at inference time, scoring the candidates at each step to decide where to expand. Still, in its section on "unsuccessful attempts," DeepSeek-R1 also recorded three problems with PRMs: in general reasoning tasks, it's hard to define each step clearly; automatic labels for whether intermediate steps are correct aren't accurate enough, while human labeling is hard to scale; and using a model as the reward invites reward hacking in large-scale reinforcement learning. In the end, they used a rule-based reward that only checks whether the answer is right.

Conclusion

On hard problems like MATH, a reward model trained with step-by-step process supervision is clearly more reliable than one trained with outcome supervision that only looks at the answer. Picking one of 1,860 solutions, the PRM solves 78.2%, the ORM 72.4%, and majority vote 69.6%; the small-scale controlled experiments also confirm that on the same data, process supervision leads throughout.

The price is 800,000 human labels. Active learning saves some of that; labeling "wrong solutions the PRM misjudged" is about 2.6 times as efficient, but in the end someone still has to look at every step.

The parts of this paper that left the biggest mark may be two byproducts: the PRM800K dataset and those 500 test problems. The first has been used to train countless reward models; the second became MATH-500 and still shows up on the report card of every reasoning model.