Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective

Zeyu Jia, Alexander Rakhlin, Tengyang Xie

Abstract

As large language models have evolved, it has become crucial to distinguish between process supervision and outcome supervision—two key reinforcement learning approaches to complex reasoning tasks. While process supervision offers intuitive advantages for long-term credit assignment, the precise relationship between these paradigms has remained an open question. Conventional wisdom suggests that outcome supervision is fundamentally more challenging due to the trajectory-level coverage problem, leading to significant investment in collecting fine-grained process supervision data. In this paper, we take steps towards resolving this debate. Our main theorem shows that, under standard data coverage assumptions, reinforcement learning through outcome supervision is no more statistically difficult than through process supervision, up to polynomial factors in horizon. At the core of this result lies the novel Change of Trajectory Measure Lemma—a technical tool that bridges return-based trajectory measure and step-level distribution shift. Furthermore, for settings with access to a verifier or a rollout capability, we prove that any policy's advantage function can serve as an optimal process reward model, providing a direct connection between outcome and process supervision. These findings suggest that the empirically observed performance gap—if any—between outcome and process supervision likely stems from algorithmic limitations rather than inherent statistical difficulties.

Introduction

In the effort to enhance Large Language Models (LLMs) for complex reasoning tasks like mathematics and programming, researchers have converged on two primary feedback mechanisms: Outcome Supervision and Process Supervision.

Outcome Supervision provides feedback only on the final result of a reasoning chain. While easy to collect, it is often criticized for "sparse rewards," making it difficult for models to identify which specific step in a long Chain-of-Thought (CoT) led to a mistake. Conversely, Process Supervision involves human or model-based labeling of every individual step. While considered the "gold standard" for performance, it is prohibitively expensive and difficult to scale.

The prevailing belief in the field has been that outcome supervision is statistically harder because it requires covering an exponential number of possible reasoning paths (trajectories). This research challenges that assumption, investigating whether the perceived necessity of process supervision is a statistical reality or an algorithmic artifact.

Theoretical Framework: Bridging the Gap

The study utilizes the framework of Markov Decision Processes (MDPs) and offline reinforcement learning to analyze these supervision styles. The authors introduce three primary theoretical contributions to bridge the gap between coarse outcome data and fine-grained process steps.

1. The Change of Trajectory Measure Lemma

This novel technical tool serves as the paper's "secret sauce." It allows researchers to bound the error of a trajectory-level reward (the outcome) using only state-action level distribution shifts. This effectively bridges the gap between the "coarse" final reward and the "fine-grained" steps, proving that we can control trajectory-level errors by managing step-level variance.

2. The "Locking In" Property

A key insight of the analysis is the "Locking In" property. The authors demonstrate that if a reward model's variance can be controlled at the start (prefixes) and end (suffixes) of a reasoning chain, the intermediate steps become predictable and "lock in." This prevents the estimation error from exploding as the reasoning chain grows longer, a common fear in outcome-based learning.

3. Advantage Function Analysis

The paper explores using Advantage functions ($A^\mu$) as reward models. In many industry applications, practitioners use Q-functions (total expected future reward) to supervise steps. However, the authors prove that using Q-functions is theoretically flawed and can lead to sub-optimal policies. In contrast, they prove that the advantage function of any policy can serve as an optimal process reward, providing a robust mathematical foundation for process-level supervision derived from outcome data.

Key Results

Statistical Equivalence

The main theorem establishes that RL via outcome supervision is no more difficult than process supervision, up to polynomial factors of the horizon ($H$, the number of steps). This suggests that the "Curse of Trajectory Coverage" is a myth; one does not need data for every possible path ($C_{traj}$), but only standard state-action coverage ($C_{sa}$).

Error Bounds and Sample Complexity

The authors provide a concrete error bound for learned reward models:

$$|J_{\hat{r}}(\pi) - J(\pi)| \lesssim H^{3/2} \cdot \sqrt{\frac{C_{sa} \cdot \log(|\mathcal{R}|/\delta)}{|D_O|}}$$

Crucially, this bound depends on $C_{sa}$ rather than the exponentially larger $C_{traj}$. This implies that Direct Preference Optimization (DPO) and similar methods may offer exponential improvements in sample efficiency over what previous trajectory-based analyses suggested.

The Failure of Q-Supervision

Through Theorem 7, the authors prove the existence of an MDP where a Q-function-based reward model results in a performance gap of at least 1/3. This confirms that Q-values are a fundamentally flawed signal for process supervision, whereas the Advantage function consistently recovers the optimal policy.

Discussion and Limitations

While this work removes the exponential difficulty barrier for outcome supervision, it acknowledges a remaining polynomial overhead related to the horizon ($H$). Future research is needed to tighten these factors. Additionally, the current proofs focus on the offline setting (learning from fixed datasets). The transition of these results to online settings, where models explore and receive real-time feedback, remains an open question.

Conclusion

This research suggests that the performance gap between outcome and process supervision observed in practice likely stems from current algorithmic limitations rather than an inherent lack of information in outcome-based data. By shifting the focus from expensive data collection to more sophisticated reward modeling—specifically utilizing Advantage functions and leveraging state-action coverage—the field may be able to achieve high-level reasoning performance without the prohibitive costs of manual step-by-step verification.

Summary updated

Abstract

As large language models have evolved, it has become crucial to distinguish between process supervision and outcome supervision -- two key reinforcement learning approaches to complex reasoning tasks. While process supervision offers intuitive advantages for long-term credit assignment, the precise relationship between these paradigms has remained an open question. Conventional wisdom suggests that outcome supervision is fundamentally more challenging due to the trajectory-level coverage problem, leading to significant investment in collecting fine-grained process supervision data. In this paper, we take steps towards resolving this debate. Our main theorem shows that, under standard data coverage assumptions, reinforcement learning through outcome supervision is no more statistically difficult than through process supervision, up to polynomial factors in horizon. At the core of this result lies the novel Change of Trajectory Measure Lemma -- a technical tool that bridges return-based trajectory measure and step-level distribution shift. Furthermore, for settings with access to a verifier or a rollout capability, we prove that any policy's advantage function can serve as an optimal process reward model, providing a direct connection between outcome and process supervision. These findings suggest that the empirically observed performance gap -- if any -- between outcome and process supervision likely stems from algorithmic limitations rather than inherent statistical difficulties, potentially transforming how we approach data collection and algorithm design for reinforcement learning.
BibTeX
@inproceedings{jia2025do,
  author = {Zeyu Jia and Alexander Rakhlin and Tengyang Xie},
  title = {{Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=4BfaPHfhJ0},
}
Figure