Part XVII — LLM Post-Training: SFT, DPO, GRPO & Reasoning / Test-Time Compute · Chapter 9

Process Reward Models (PRM) & Monte Carlo Tree Search

Hook

RLVR's reward only looks at the FINAL answer — correct or not, after the whole reasoning chain is already written. That's late feedback: a promising-looking first step can lead nowhere, and nothing catches it until the very end. What if each individual step could be scored on its own?

Intuition

first step A — PRM score 0.9

A reasoning tree: 3 possible first steps, each branching into 2 possible second steps. Step through each branch and see the two numbers that make up a path's score — a Process Reward Model (PRM) score for each individual step, not just one score for the finished answer.

Formalize

A path's overall score is the PRODUCT of its per-step PRM scores — exactly like chaining conditional probabilities:

score(path)=∏tPRM(stept)\text{score}(\text{path}) = \prod_{t} \text{PRM}(\text{step}_t)
  • score(path)\text{score}(\text{path}) — the overall score for one complete root-to-leaf reasoning path.
  • PRM(stept)\text{PRM}(\text{step}_t) — the process reward model's score for step tt: how likely this partial derivation is to still be on track to a correct final answer.
  1. Scoring steps, not just outcomes

    An Outcome Reward Model (ORM) — RLVR's verifier from the previous chapter — only ever sees the finished response. A PRM scores every intermediate step, giving a signal before the reasoning is finished.

  2. Per-step scores enable a search, not just a rating

    Once every candidate step has its own score, a search procedure can branch: expand several candidate next steps, score each with the PRM, and keep pursuing only the promising ones — instead of committing to one linear chain and hoping.

  3. Full-path evaluation beats greedy, step-by-step commitment

    A greedy search that locks in whichever first step scores highest, then only looks at that branch's children, can miss the actual best path entirely — evaluating full paths (as a real tree search does) is what catches that.

Play

Branch A's first step scores highest in isolation (0.90.9) — the most tempting one to commit to greedily. But its best second step only reaches 0.30.3, for a final path score of just 0.270.27: the WORST of the three branches. Branch C's first step looks weakest (0.350.35) yet leads to an excellent second step (0.950.95), landing the best overall path at 0.33250.3325. A search that only looked one step ahead would never have found it.

Worked example

The full tree, all six paths:

  1. Branch A (first-step score 0.9 — the tempting one)
    • A→A1: 0.9×0.3=0.270.9 \times 0.3 = 0.27
    • A→A2: 0.9×0.2=0.180.9 \times 0.2 = 0.18

    Best in this branch: 0.270.27.

  2. Branch B (first-step score 0.5)
    • B→B1: 0.5×0.6=0.300.5 \times 0.6 = 0.30
    • B→B2: 0.5×0.4=0.200.5 \times 0.4 = 0.20

    Best in this branch: 0.300.30.

  3. Branch C (first-step score 0.35 — the weakest-looking one)
    • C→C1: 0.35×0.2=0.070.35 \times 0.2 = 0.07
    • C→C2: 0.35×0.95=0.33250.35 \times 0.95 = 0.3325

    Best in this branch: 0.33250.3325 — the best path in the ENTIRE tree, despite starting from the lowest first-step score of the three branches.

Checkpoint

Find the single best-scoring path through the whole tree — it is not the branch whose first step looks most promising.

Pick a path to try it
Summary
score(path)=∏tPRM(stept)\text{score}(\text{path}) = \prod_{t} \text{PRM}(\text{step}_t)

A Process Reward Model turns "is this answer right?" into "is this STEP still on track?" — a signal available before the reasoning chain is even finished. That per-step signal is what makes tree search over reasoning paths possible at all, and it's what catches exactly the failure mode this chapter's tree demonstrated: the step that looks most promising in isolation isn't always the one that leads anywhere good. The next chapter turns back to alignment training itself, with two DPO variants that each drop one of DPO's own requirements.