Technical Summary: Improving Value-based Process Verifier via Structural Prior Injection

Problem Statement

In Large Language Model (LLM) reasoning scenarios, process verifiers are critical for evaluating the quality of intermediate reasoning steps. While outcome verifiers focus solely on final correctness, value-based process verifiers estimate the "state value" (the probability of reaching a correct outcome) at each step.

Currently, state values are typically annotated using Monte Carlo (MC) sampling. However, this approach faces two significant limitations due to the high cost of generating full rollouts:

1. Discrete Representation Granularity: Limited sampling (e.g., $k$ rollouts) restricts the estimated value to a discrete set of $k+1$ possible outcomes ($0, 1/k, \dots, 1$). This creates a mismatch when the ground-truth value is a continuous probability.
2. Sampling Variance: MC estimation is unbiased but inaccurate with limited samples, particularly when the true success probability $p$ is near the middle (0.5), where variance is highest.

Existing solutions often use Mean-Squared Error (MSE) to map discrete values to a continuous space or Temporal Difference (TD) methods to reduce variance. However, TD methods require large sampling quantities which are computationally expensive in LLM reasoning, and standard MSE treats the value as a scalar without explicitly modeling the underlying distribution of the sampling error.

Methodology

The authors propose Structural Prior Injection, a method that transforms the scalar state value into the expectation of a pre-defined categorical distribution. This approach reframes the MC sampling error as a distribution mismatch problem.

1. From Scalar to Categorical Distribution

Instead of predicting a single scalar value, the verifier predicts a categorical distribution $Z$ over $m$ bins. The state value $V^\pi(s)$ is defined as the expectation of this distribution:
$$V^\pi(s) = E_p[\delta_i] = \sum_{i=1}^m p_i(s)\delta_i$$
where $\delta_i$ represents the Dirac delta function at location $i$.

2. Structural Prior Definition

The method treats the result of $k$-times Monte Carlo sampling as a single sample drawn from a ground-truth Binomial distribution $Bin(k, p)$, where $p$ is the true state value.

• Expectation Regression (MSE): The model optimizes the expectation of the categorical distribution to match the MC estimate, effectively injecting the structural prior that the value is the mean of a distribution.
• Expectation Classification (Histogram Loss): The model attempts to recover the ground-truth Binomial distribution itself. The goal is to find a posterior distribution that minimizes the distance to the true Binomial distribution given the limited sampling data.

3. Statistics-based Distance Metric

To guide the selection of the posterior distribution (e.g., choosing between One-hot, Gaussian, or other shapes), the authors introduce a Statistics-based Distance metric.

• Defined as $D_T(p, q) = E_{x \sim q}[d(p(\cdot|x), q)]$, where $d$ is a distance metric like Wasserstein distance.
• This metric measures the mismatch between the estimated posterior and the ground-truth target distribution at a statistical level.
• The authors use Wasserstein distance rather than KL divergence because the categories in the distribution have sequence characteristics (weights), making Wasserstein more suitable for measuring the "distance" between probability masses.

4. Optimization

The verifier is optimized using either:

• MSE Loss: Minimizing the squared difference between the predicted expectation and the MC estimate.
• Histogram Loss (Cross-Entropy): Minimizing the cross-entropy between the predicted categorical distribution and a target distribution (e.g., a truncated Gaussian approximating the Binomial distribution).

Key Contributions

1. Structural Prior Injection: The paper proposes transferring the scalar MC sampling error into a distribution mismatch problem. By representing the value as the expectation of a categorical distribution, the method explicitly models the difficulty of recovering the ground-truth distribution from limited data.
2. Statistics-based Distance: A new metric is proposed to quantify the distance between the posterior distribution and the ground-truth target distribution. This metric serves as a guide for selecting reasonable structural priors (e.g., distribution shapes and variances) to minimize mismatch.
3. Empirical Validation: The authors demonstrate that reasonable structural prior injection improves verifier performance across different objective functions (MSE and Histogram Loss) and tasks (Best-of-N and Beam Search) with little to no additional computational cost.

Experimental Results

The method was evaluated on the MATH dataset using Best-of-N (BoN) and Beam Search tasks with base models like Qwen2.5-Math-7B and Deepseek-Math-7B.

• Performance Gains: Compared to scalar regression baselines, the expectation-based models (both MSE and Histogram Loss variants) achieved consistent improvements of approximately 1–2 percentage points in success rates.
• Task Sensitivity:
  • In Best-of-N, outcome-supervised verifiers performed well, but process-supervised verifiers (which our method enhances) showed superior robustness.
  • In Beam Search, the process-supervised verifiers significantly outperformed outcome-only verifiers, highlighting the importance of accurate intermediate state values for multi-step search.
• Prior Selection Impact: Ablation studies revealed that the choice of structural prior significantly impacts performance.
  • Distribution Shape: Using a dynamic Gaussian distribution (where variance is derived from the sampled value) yielded better results than static Gaussian or One-hot distributions, aligning with the lower Statistics-based Distance observed in experiments.
  • Category Quantity: Setting the number of categories to match the sampling size (e.g., 9 categories for 8 rollouts) proved beneficial.

Significance and Claims

The paper claims that the improvement in value-based process verifiers stems from the reasonable injection of structural priors. By shifting the perspective from scalar regression to distribution estimation, the method addresses the inherent noise and granularity issues of Monte Carlo estimation in LLM reasoning.

The authors emphasize that:

• The error in MC estimation is fundamentally a difficulty in recovering the ground-truth distribution from limited samples.
• The Statistics-based Distance provides a theoretical and practical tool to evaluate and select priors that minimize this mismatch.
• This approach offers a "promising and meaningful direction" for future work, suggesting that structural priors can significantly enhance optimization processes in value-based verification without requiring expensive increases in sampling quantities.

The work remains modest in its scope, noting limitations such as the non-differentiable nature of the Wasserstein distance (requiring prior, non-differentiable distribution modeling) and the difficulty of combining MSE and Cross-Entropy objectives linearly.