Let's Verify Step by Step

Full title: Let's Verify Step by Step Authors: Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, Karl Cobbe (OpenAI) Venue/year: arXiv preprint, May 2023 — arXiv:2305.20050 Links: arXiv · local PDF: research-papers/2305.20050-lets-verify.pdf

Why this paper matters

This is the paper that settled — at scale — the question of how to train the verifier that test-time compute strategies depend on. If you want to sample many candidate solutions and pick the best one, you need a reward model, and there are two ways to train it: grade only the final answer (outcome supervision) or grade every intermediate reasoning step (process supervision). Prior work (Uesato et al., 2022, on grade-school math) had found the two roughly tied. Lightman et al. re-ran the comparison with a stronger base model (GPT-4), far more human feedback, and a harder benchmark (MATH), and found process supervision wins decisively: their process-supervised reward model (PRM) solves 78.2% of a representative MATH test subset via best-of-N selection, versus 72.4% for the outcome-supervised model (ORM) and 69.6% for majority voting (§3, Figure 3). The paper also released PRM800K — 800K human step-level labels — which seeded the entire process-reward-model line of work (verifier-guided search, step-level RL, "PRMs" as a product category). It is the canonical citation for "verify the reasoning, not just the answer."

The problem

State-of-the-art LLMs solve multi-step problems with chain-of-thought, but "even state-of-the-art models are prone to producing falsehoods" — a single hallucinated step derails an otherwise sound solution (§1). The standard remedy is a reward model used for RLHF or for rejection sampling / best-of-N search, but "the resulting system is only as reliable as the reward model itself" (§1). Before this paper, the field lacked a careful, at-scale answer to which supervision signal makes reward models reliable:

• ORMs are cheap — final answers on MATH are auto-checkable — but suffer false positives: solutions that reach the right answer via wrong reasoning get labeled correct (§2.5), and credit assignment is hard (the model must infer where a bad solution went wrong, §6.1).
• PRMs give precise, step-located feedback but require expensive human labeling, and the one prior head-to-head (Uesato et al., 2022) had found no final-performance advantage (§1, §7.1).

The mechanism

Scope: reward models only, judged by best-of-N (§2.1)

A single fixed generator (no RL fine-tuning of the generator is done — deliberately) produces N uniformly sampled solutions per problem; the reward model picks the highest-ranked one; the picked solution is auto-graded on its final answer. A more reliable reward model picks correct solutions more often. Everything in the paper is measured through this best-of-N lens.

Two experimental regimes (§2)

• Large-scale: all models fine-tuned from base GPT-4 (no RLHF), further pretrained on MathMix, ~1.5B math-relevant tokens (§2.2, Appendix A). Goal: best possible ORM and PRM. Caveat: their training sets are not directly comparable (§3).
• Small-scale: base models with ~200× less pretraining compute than GPT-4. Human labels are replaced by a synthetic supervisor — the large PRM (PRM_large) — enabling apples-to-apples ablations that human labeling costs would forbid (§2, §4).

PRM800K: the labeling scheme (§2.4)

Human labelers see step-by-step generator solutions to MATH problems and label each step positive (correct and reasonable), negative (incorrect or unreasonable), or neutral (ambiguous — deferred, so at test time neutrals can be treated as either). The released dataset totals 800K step-level labels across 75K solutions to 12K problems. Two critical design decisions:

1. Surface convincing wrong-answer solutions. Instead of labeling uniform samples, they label solutions that (a) the current best PRM rates highly ("convincing") and (b) reach a wrong final answer — so the PRM is known to be wrong about at least one step, maximizing information per label (§2.4).
2. Label only up to the first incorrect step. This equalizes information with outcome supervision on correct solutions and keeps human cost comparable; for incorrect solutions the PRM additionally learns where the error is (§2.6).

To limit overfitting, 4.5K MATH test problems were folded into training; evaluation uses the remaining 500 held-out MATH test problems (§2.4, Appendix C).

ORM and PRM training (§2.5, §2.6)

• ORM: trained on uniform samples (100 per problem at large scale, §3) to predict correct/incorrect final answer; the final-token prediction is the solution score. Auto-grading introduces false positives.
• PRM: trained (standard LM pipeline, single token target) to predict correctness of each step after its last token. One forward pass over the whole solution yields all step predictions. The solution score is the product of the per-step correctness probabilities — the probability that every step is correct (§2.6, Appendix F for alternatives).

Cast of models (a glossary that pays for itself when reading §3–§4)

The algorithm

Reconstructed from §2.4–§2.6, §3, and §4.2. Three interlocking procedures: PRM training, best-of-N selection, and the active-learning data engine.

# ---------- 1. PRM training (§2.4, §2.6) ----------
D = {}                                   # step-labeled solutions (-> PRM800K)
for problem in MATH_train:
    S = generator.sample_solutions(problem)          # newline-delimited steps (§2.3)
    S = select_convincing_wrong_answer(S, PRM_cur)   # active surfacing (§2.4)
    for sol in S:
        labels = human_label_steps(sol)              # {+, -, neutral}, stop at 1st error
        D.add(problem, sol, labels)
PRM = finetune_LM(base_model, D)         # predict step label token after each step

# ---------- 2. Best-of-N selection at test time (§2.1, §2.6) ----------
def best_of_N(problem, N):               # paper's headline: N = 1860
    candidates = generator.sample(problem, N)        # uniform, fixed generator
    for sol in candidates:
        p_step = PRM.step_correct_probs(sol)         # one forward pass
        sol.score = product(p_step)                  # P(every step correct)
    best = argmax(candidates, key=score)
    return auto_grade_final_answer(best)             # report fraction correct

# ---------- 3. Active learning engine (§4.2, small-scale ablation) ----------
PRM_selector = train_PRM(one_sample_per_problem)
pool = generator.sample(problem, 1000)   # per problem
chosen = top(0.8*N, most_convincing_wrong_answer(pool, PRM_selector)) \
       + top(0.2*N, most_convincing_remaining(pool, PRM_selector))
scores = PRM_large.label(chosen)         # synthetic supervision stands in for humans
train_on(chosen, scores)                 # => ~2.6x more data-efficient than uniform

Line-by-line:

• select_convincing_wrong_answer — the data engine only pays humans for solutions the current PRM is fooled by: high PRM score, wrong final answer. "Wrong-answer" (not "incorrect") because grading is by final-answer check, which occasionally misgrades (§2.4). The PRM is periodically retrained during collection, and the top-K filtering is applied per-problem or globally (§2.4).
• human_label_steps — three-way labels; supervision stops at the first error, so correct solutions carry the same information under both supervision regimes (§2.6).
• product(p_step) — the paper's chosen aggregation: solution score = probability all steps are correct. Not the only option (Appendix F), but it makes the PRM's step scores compose into a single comparable scalar.
• N = 1860 — the headline evaluation samples 1,860 solutions per problem; PRM best-of-1860 reaches 78.2% vs ORM 72.4% and majority voting 69.6% (Figure 3, table inset). Crucially, the ORM/PRM gap widens as N grows — the PRM is more robust to searching a large candidate pool.
• Active learning (small-scale): 80% of surfaced samples are the most convincing wrong-answer ones, 20% the most convincing of the rest, ensuring convincingness while capping bias toward wrong answers; measured effect is a ~2.6× data-efficiency multiplier over uniform labeling by comparing best-fit-line slopes (§4.2, Figure 4a). Iteratively retraining PRM_selector between batches was unstable and gave no gains — an honest open problem (§4.2).

The small-scale head-to-head (§4.1) trains three reward-model series on identical problem sets, differing only in supervision: process labels from PRM_large, outcome labels from PRM_large, or outcome labels from final-answer checking. Two views of the same experiment:

• Data-scaling view (Figure 4a): best-of-500 accuracy as the number of labeled samples per problem grows from 1 to 200 — process supervision is above both outcome forms at every scale, and the active-learning series sits above plain process supervision.
• Test-time-compute view (Figure 4b): fixing training at 200 samples/problem and sweeping N, the process-supervised RM wins at every best-of-N budget; PRM_large-outcome beats final-answer-outcome because it doesn't reward spurious right-answer/wrong-reasoning solutions (§4.1).

One subtlety worth internalizing (§4.1): the authors debate which outcome baseline is fairer. Final-answer checking is the "purest" outcome signal but suffers false positives, which MATH arguably over-represents; PRM_large-as-outcome-supervisor is cleaner and better represents domains with reliable outcome checks. They call the latter "the more relevant baseline" — and process supervision beats both.

Results that matter

The full OOD breakdown (Table 1, best-of-100 per problem) — the PRM wins every row, and the gap is largest exactly where majority voting collapses (AMC):

Note: §5 says "224 STEM questions" while Table 1's per-test counts (45+60+45+84) sum to 234 — an internal inconsistency in the paper itself; the per-row Table 1 numbers are what's quoted above.

Limitations & how to defend the findings

• "The large-scale ORM/PRM comparison is confounded." True, and the authors say so themselves: the PRM800K training set is actively selected, wrong-answer-biased, and an order of magnitude smaller than the ORM's 100-uniform-samples-per-problem set (§4). The defense is the small-scale ablation (§4.1), where supervision type is the only difference on identical datasets — process still wins everywhere.
• "Final-answer grading unfairly handicaps the ORM (false positives)." Partly conceded: supervising outcomes with PRM_large instead of answer-checking closes some of the gap, and the authors call PRM_large-outcome "the more relevant baseline" — but process supervision still beats it (§4.1).
• "Test set contamination inflates 78.2%." MATH problems circulate online; string-matching decontamination of MathMix can't be airtight (§6.3). Defenses from the paper: no observed memorization on inspection; contamination would lift all methods similarly, preserving the relative comparison; and the OOD evaluation on post-pretraining AP/AMC exams (guaranteed uncontaminated) reproduces the same ordering (§5, §6.3).
• "This is only math." Acknowledged: "It is unknown how broadly these results will generalize beyond the domain of math" (§6.2). MATH also has easily checkable answers; in domains without them, process supervision's cost advantage actually grows (checking a solution ≈ finding its first error, §2.6), but the empirical evidence stops at math + adjacent STEM (§5).
• "Does this help RL, not just best-of-N?" Out of scope by design — the generator is never RL-trained against the reward model (§2.1). The paper claims reward-model reliability, not end-to-end RL gains.
• Alignment angle the authors emphasize: process supervision is more interpretable and directly rewards human-endorsed reasoning; here it carries a negative alignment tax (it performs better), which they argue favors its adoption (§6.2).

Connections

• Test-time compute: best-of-N with a PRM is the simplest verifier-guided test-time scaling; Figure 3's widening PRM/ORM gap with N is the seed of later "how to spend inference compute" work (samplers + verifiers beat samplers + voting).
• Verifier-guided search: the per-step scores make the PRM usable inside search (scoring partial solutions), not just after it — the bridge from this paper to step-level beam search and Tree-of-Thoughts-style deliberate search.
• Self-consistency / majority voting (Wang et al., 2022): the strong no-training baseline the PRM must and does beat (69.6% vs 78.2%); RM-weighted voting added nothing here (§3).
• Uesato et al. 2022: the prior tie on GSM8K. This paper's reconciliation: at small supervision scale the two do look similar; process supervision pulls ahead as supervision scales (§7.1, Figure 4a) — a data-scaling explanation, not a contradiction.
• FrugalGPT (sibling page): both use a learned scorer to judge generations; FrugalGPT's g(q,a) gates which model to call next (economics), the PRM gates which sample to trust (reliability).
• τ-bench (sibling page): τ-bench measures agent reliability via repeated trials (pass^k); PRM-style verification is one of the main proposed remedies for exactly the inconsistency τ-bench exposes.

Reading guide

• Read first: Abstract → §1 (contributions list) → §2.4–2.6 (labeling scheme + ORM/PRM definitions — the technical core) → §3 + Figure 3 (headline result).
• Then: §4 (the small-scale ablations that make the causal claim stick; Figure 4a/4b) and §5 (OOD table).
• Skimmable: §2.2–2.3 (base model/generator plumbing), §6 (discussion — read §6.1 credit assignment, skim the rest), §7 (related work; §7.1 is worth a careful read for the Uesato reconciliation).
• Appendices, only as needed: B (data collection detail), D (labeling instructions), F (alternative PRM scoring), G (difficulty breakdown), I (example PRM-surfaced solutions).
• The one figure to study: Figure 3 — PRM vs ORM vs majority voting as a function of N, with the best-of-1860 table inset. The whole paper's claim is legible in that single plot: higher curve, widening gap. Runner-up: Figure 2, which shows exactly what a PRM catches (a plausible-looking wrong step scored red mid-solution).