Process Reward Models (PRMs): Mathematical Foundations, Step-Level Credit Assignment, and Inference-Time Search in Large Language Models

In complex multi-step reasoning tasks such as mathematics, formal logic, and software verification, standard autoregressive language models frequently exhibit compounding logical drift. While a model may produce fluent chain-of-thought derivations, an error introduced early in the chain typically invalidates all downstream deductions. Evaluating these reasoning trajectories has traditionally relied on Outcome-Supervised Reward Models (ORMs), which assign a scalar reward solely based on the final terminal answer.

However, outcome supervision suffers from severe credit assignment ambiguity. An ORM provides identical negative feedback to a solution with a minor arithmetic slip on the final line and a solution built on invalid premises from the first step. Conversely, ORMs award full positive feedback to reasoning paths that arrive at the correct final answer through flawed logic or fortuitous cancellations.

Process Reward Models (PRMs), introduced in foundational work by Lightman et al. (2023) and extended by Wang et al. (2024), resolve this bottleneck by evaluating and supervising every intermediate reasoning step. By providing dense, step-level verification signals, PRMs enable fine-grained credit assignment, effective early pruning, and structured test-time search algorithms such as beam search and Monte Carlo Tree Search (MCTS).

1. Mathematical Formulation of Process Supervision

Let a reasoning problem be denoted by $x \in \mathcal{X}$, and let a complete reasoning trajectory $\tau$ be segmented into an ordered sequence of $K$ discrete reasoning steps:

$$\tau = (s_1, s_2, \dots, s_K)$$

where each step $s_k = (t_{k,1}, t_{k,2}, \dots, t_{k,L_k})$ represents a coherent subsequence of tokens delimited by a special delimiter (such as newline tokens \n\n or explicit step markers).

Step-Level Verification Objective

A Process Reward Model parameterized by weights $\theta$ evaluates the validity of each step $s_k$ conditioned on the problem statement $x$ and the preceding trajectory prefix $s_{<k} = (s_1, \dots, s_{k-1})$:

$$r_k = p_\theta(\text{valid} \mid x, s_1, s_2, \dots, s_k) = \sigma(W^\top h_\theta(x, s_{1:k}))$$

where:

• $h_\theta(x, s_{1:k}) \in \mathbb{R}^d$ denotes the contextual hidden representation extracted at the terminal token of step $s_k$.
• $W \in \mathbb{R}^d$ is a classification projection vector.
• $\sigma(z) = \frac{1}{1 + e^{-z}}$ is the standard logistic sigmoid function.
• $r_k \in [0, 1]$ represents the predicted probability that step $s_k$ represents mathematically and logically sound progress toward solving $x$.

Trajectory-Level Score Aggregation

To score a complete candidate trajectory $\tau$ during inference or reranking, intermediate step probabilities must be aggregated into a global trajectory score $R(\tau)$. Common aggregation formulations include:

1. Product of Step Probabilities (Joint Validity):

Assuming conditional independence of step correctness given prefix context: $$R_{\text{prod}}(\tau) = \prod_{k=1}^K r_k$$ In log-space, this corresponds to an unnormalized sum: $$\log R_{\text{prod}}(\tau) = \sum_{k=1}^K \log r_k$$

1. Minimum Step Probability (Weakest-Link Criterion):

A reasoning chain is strictly as valid as its most flawed deduction: $$R_{\text{min}}(\tau) = \min_{1 \le k \le K} r_k$$ This conservative metric guarantees that any trajectory containing an invalid step ($r_k \approx 0$) receives a low overall score, regardless of the quality of surrounding steps.

1. Length-Normalized Geometric Mean:

To prevent systemic penalties on longer, detailed proofs: $$R_{\text{geom}}(\tau) = \left( \prod_{k=1}^K r_k \right)^{1/K} = \exp\left( \frac{1}{K} \sum_{k=1}^K \log r_k \right)$$

In empirical benchmarks on the MATH dataset by Lightman et al. (2023) and Wang et al. (2024), both $R_{\text{prod}}$ and $R_{\text{min}}$ consistently outperform ORM scalar outputs and majority voting baselines.

2. Supervised Training Paradigms: Active Human Labels vs. Monte Carlo Rollouts

Training a PRM requires assigning target labels $y_k \in \{0, 1\}$ (or continuous soft targets $y_k \in [0, 1]$) to each step $s_k$. Two dominant training paradigms have emerged.

Paradigm A: Human Active Learning (PRM800K)

In the human-supervised regime (Lightman et al., 2023), human annotators inspect model-generated step sequences and label each step as positive (+1), negative (-1), or neutral (0).

To optimize labeling efficiency, annotations follow two core rules:

1. Early Termination: Annotators label steps sequentially and terminate inspection at the first incorrect step. All steps prior to the first error are labeled positive, the first erroneous step is labeled negative, and subsequent steps are left unlabelled.
2. Active Learning Selection: Rather than sampling trajectories uniformly, trajectories are sampled from the generator policy, and solutions where the current PRM exhibits high predictive uncertainty or where candidate trajectories diverge are prioritized for human review.

The PRM is trained using binary cross-entropy loss over all annotated step boundaries:

$$\mathcal{L}_{\text{BCE}}(\theta) = - \frac{1}{|\mathcal{D}|} \sum_{(x, \tau) \in \mathcal{D}} \sum_{k=1}^{K_\tau} \left[ y_k \log r_k + (1 - y_k) \log (1 - r_k) \right]$$

Paradigm B: Automated Monte Carlo Estimation (Math-Shepherd)

Because expert human step annotation is expensive and difficult to scale, Wang et al. (2024) introduced Math-Shepherd, an automated framework that estimates step validity using Monte Carlo rollouts without human intervention.

Given problem $x$, ground-truth target $y^*$, and an intermediate reasoning prefix $s_{1:k}$, a completion policy $\pi_{\text{comp}}$ generates $N$ stochastic rollouts to completion:

$$\hat{\tau}^{(i)} = (s_1, \dots, s_k, \hat{s}_{k+1}^{(i)}, \dots, \hat{s}_{M_i}^{(i)}), \quad i \in \{1, \dots, N\}$$

The state value $V(s_1, \dots, s_k)$ is approximated as the empirical success rate of these rollouts:

$$V(s_{1:k}) = \frac{1}{N} \sum_{i=1}^N \mathbb{I}\left( \text{ExtractAnswer}(\hat{\tau}^{(i)}) = y^* \right)$$

Target labels for step $s_k$ are then assigned by evaluating the transition in state value:

$$y_k = \begin{cases} 1 & \text{if } V(s_{1:k}) \ge \gamma_{\text{pos}} \text{ or } V(s_{1:k}) - V(s_{1:k-1}) \ge 0 \\ 0 & \text{if } V(s_{1:k}) = 0 \text{ and } V(s_{1:k-1}) > 0 \end{cases}$$

This automated formulation allows the construction of massive step-level datasets (such as hundreds of thousands of reasoning chains) with zero human annotation overhead while providing comparable verification fidelity.

3. Inference-Time Search Algorithms Guided by PRMs

PRMs can be deployed across several inference-time search strategies, converting raw test-time compute into substantial reasoning gains as characterized by Snell et al. (2024).

                      [ Root: Input Problem x ]
                                  │
          ┌───────────────────────┼───────────────────────┐
          ▼                       ▼                       ▼
     [ Step 1a ]             [ Step 1b ]             [ Step 1c ]
     r₁ = 0.98               r₁ = 0.95               r₁ = 0.12 (Pruned)
          │                       │
     ┌────┴────┐             ┌────┴────┐
     ▼         ▼             ▼         ▼
[ Step 2a ] [ Step 2b ] [ Step 2c ] [ Step 2d ]
r₂ = 0.96   r₂ = 0.05   r₂ = 0.92   r₂ = 0.89

1. Best-of-N (BoN) Reranking

In Best-of-N sampling, the base policy $\pi_\theta$ generates $N$ independent, complete reasoning trajectories $\{\tau_1, \tau_2, \dots, \tau_N\}$. The PRM evaluates each step in each trajectory, and the optimal trajectory $\tau^*$ is selected:

$$\tau^* = \arg\max_{\tau \in \{\tau_1, \dots, \tau_N\}} R(\tau)$$

When combined with self-consistency voting (Wang et al., 2022), trajectories are clustered by their final answer $a$, and the winning answer maximizes the aggregate PRM weight:

$$a^* = \arg\max_{a \in \mathcal{A}} \sum_{i=1}^N \mathbb{I}(\text{Answer}(\tau_i) = a) \cdot R(\tau_i)$$

2. Step-Level Beam Search

Rather than generating full trajectories blindly, step-level beam search actively prunes erroneous paths at intermediate stages:

1. At step $k$, given a beam of $B$ active partial trajectories $\{s_{1:k-1}^{(b)}\}_{b=1}^B$, the generator samples $M$ candidate continuations for each prefix.
2. The PRM scores all $B \times M$ candidate steps: $r_k^{(b, m)} = p_\theta(\text{valid} \mid x, s_{1:k-1}^{(b)}, s_{k}^{(b, m)})$.
3. Candidates with $r_k < \tau_{\text{threshold}}$ are discarded immediately.
4. The remaining candidate paths are ranked by cumulative score $\prod_{j=1}^k r_j$, retaining the top $B$ paths for step $k+1$.

Step-level pruning prevents the model from wasting computational tokens expanding trajectories that have already committed irreversible algebraic or logical errors.

3. Monte Carlo Tree Search (MCTS)

In full tree search frameworks, each state $S_k = (x, s_1, \dots, s_k)$ forms a tree node. The PRM serves as both:

• Heuristic Evaluation Function: Providing intermediate node values $Q(S_k)$ without requiring expensive full rollouts to terminal tokens.
• Prior Policy Modulator: Scaling action selection probabilities $P(S_k, s_{k+1})$ within Upper Confidence Bounds for Trees (PUCT):

$$a_{k+1} = \arg\max_{s} \left[ Q(S_k, s) + c_{\text{puct}} P(S_k, s) \frac{\sqrt{\sum_{b} N(S_k, b)}}{1 + N(S_k, s)} \right]$$

4. Key Architectural Trade-Offs: PRMs vs. ORMs

The operational differences between process and outcome supervision govern how each is deployed in production systems:

• Supervision Target: ORMs evaluate a single scalar label on terminal token sequences $y$. PRMs evaluate per-step validity probabilities $r_k \in [0, 1]$ across all intermediate steps.
• Credit Assignment: ORM feedback is diffuse, failing to isolate specific logical errors. PRM feedback is localized, directly identifying the exact step where reasoning failed.
• False-Positive Robustness: ORMs are vulnerable to accidental correct answers and guessing. PRMs penalize invalid intermediate logic regardless of final answer alignment.
• Search Capabilities: ORMs support only trajectory-level search (such as Best-of-$N$). PRMs enable dynamic step-level guidance (such as beam search, early stopping, lookahead search, and MCTS).
• Data Construction Cost: ORMs require only binary outcome labels, which can be extracted automatically via execution or answer matching. PRMs require fine-grained step labels obtained through human active learning or multi-branch Monte Carlo rollouts.
• Inference Compute Overhead: ORMs require a single evaluation pass per complete response. PRMs require scoring evaluations across every reasoning boundary, necessitating efficient prefix caching and batched forward passes.

5. Failure Modes and Methodological Challenges

Despite significant empirical gains, process verification faces several operational bottlenecks:

1. Step Delimitation and Granularity:

Reasoning steps vary in semantic complexity. Overly fine granularity (token or sub-clause level) increases scoring compute and noise, while overly coarse granularity (multi-paragraph blocks) re-introduces credit assignment ambiguity. Standard systems rely on double newlines or LaTeX environment boundaries as heuristics.

1. Verifier Goodharting and Reward Exploitation:

When searching over large candidate pools ($N > 10^3$) or executing deep tree search, generator policies can exploit false-positive artifacts in the PRM. The generator discovers degenerate syntactic structures or repetitive affirmations that yield high step probabilities from the verifier despite flawed underlying mathematics (Gao et al., 2023).

1. Step Context Window and Memory Overhead:

Evaluating $B \times M$ candidate steps across $K$ reasoning stages requires either frequent KV cache swaps or redundant prefix recomputations during generation, necessitating specialized serving kernels (such as RadixAttention or Tree-KV cache sharing).

Sources

• Lightman et al. (2023): Let's Verify Step by Step
• Wang et al. (2024): Math-Shepherd: Verify and Reinforce LLMs Step-by-Step without Human Annotations
• Cobbe et al. (2021): Training Verifiers to Solve Math Word Problems
• Uesato et al. (2022): Solving Math Word Problems with Process- and Outcome-Based Feedback
• Snell et al. (2024): Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
• Gao et al. (2023): Scaling Laws for Reward Model Overoptimization
• Wang et al. (2022): Self-Consistency Improves Chain of Thought Reasoning in Language Models