Winner's Curse in Step-Level Reasoning Judges

When a language model solves a math problem by search, it proposes many candidate next steps and keeps the one that an automated judge scores highest. The usual judge is a process reward model, meaning a network trained to score each intermediate step by how likely it is to lead to a correct answer. Offline reinforcement learning, where an agent learns only from a fixed dataset, has long known a failure of this pattern. When a learned value estimate is maximized over options the dataset never covered, the maximum lands disproportionately on options whose value was overestimated by chance. That overestimation is called extrapolation error. We argue that step-level judges suffer the same thing at test time. A plausible but wrong reasoning step, a hallucination in the logic, is typically an out-of-distribution option for the judge. The more candidates the search compares, the more reliably it selects exactly those steps. This would explain why verifier-guided search degrades at large sampling budgets, as reported for Entropy-Regularized Process Reward Model. It would also explain why reinforcement learning on reasoning produces coherent-looking but invalid traces, as reported in Local Coherence or Global Validity?.

The proposal has two parts. First, we measure this selection bias directly, as a function of how many candidates are compared and how far a step lies from the judge's training data. Second, we correct it with a support-aware pessimistic score. The correction borrows the idea behind the in-sample softmax of The In-Sample Softmax for Offline Reinforcement Learning: trust value estimates only where the data-generating policy put probability. That method's main weakness in control is that the data-generating policy must be estimated. For process reward models this weakness largely disappears. Their training labels come from rollouts of a known "completer" language model, so the probability that model assigns to any candidate step can be computed exactly.

Core Claim

Our claim has three parts. Process reward models used as step-level judges systematically overestimate out-of-distribution steps. Search turns this overestimation into a selection bias that grows with the number of candidates. And the bias can be removed at the scoring stage, without retraining the policy, by penalizing a step's score in proportion to how far it lies outside the support of the completer that generated the judge's training labels.

The growth-with-N claim has a simple source. Suppose each of $N$ candidates' judge scores equals its true value plus independent noise of scale $\sigma$. Then the expected score of the selected candidate exceeds its true value by roughly $\sigma\sqrt{2\log N}$. This is the standard expected-maximum-of-Gaussians result. If $\sigma$ is larger off-support, the gap concentrates on off-support steps.

Relation to Prior Work

Three lines of work motivate the gap without closing it.

Process Reward Model with Q-value Rankings (PQM) recasts step scores as Q-values, meaning the probability of eventually reaching a correct answer after taking a step, and trains them with a ranking loss. Math-Shepherd supplies the rollout-based labels that PQM trains on. Both treat the judge as a fixed function to be maximized over, which is exactly the regime where offline RL predicts overestimation. Neither measures how scores behave off their training support.

Adversarial Training for Process Reward Models is the closest competitor. It trains a generator to produce fooling wrong steps and reports gains on out-of-distribution SciBench. But it attacks the problem by enlarging the training support at considerable compute cost. It does not correct the selection mechanism itself, and it notes that its generator fails to produce some error types.

Learning a Pessimistic Reward Model in RLHF (PET) shows that pessimistic reward models resist reward hacking. It works only at the whole-response level and only on summarization and sentiment tasks.

The offline RL literature supplies the method and constrains it. Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction establishes the mechanism of maximization over poorly supported actions. The in-sample softmax supplies the support-restricted operator. Conservative State Value Estimation is a warning: blanket pessimism, as in conservative Q-learning, suppresses genuinely good actions. Any penalty we add must be targeted rather than uniform.

Value-based reasoning optimizers are the downstream consumers of such judges. These include OREO, Trajectory Bellman Residual Minimization, and the frozen value model of Decoupled Value Policy Optimization. The last of these explicitly states that its guidance fails when the policy drifts outside the offline data. We treat these as a later application, not the core test.

Research Program

The first stage is diagnostic. We take PQM and a standard cross-entropy judge, both trained on Math-Shepherd labels, together with Math-Shepherd's own judge. We let generators of increasing distance from the completer propose candidate steps on MATH500, GSM-Plus, SciBench and the Hungarian national exam. The generators range from the completer itself to Llama-3-70B and Qwen2.5-Math-7B.

For each step we compute two quantities:

  • Reference value. A Monte Carlo estimate of the step's true value, obtained from many completions by a strong reference completer.
  • Human-audited correctness label. This handles cases where a rollout reaches the right answer through flawed logic, the false-positive problem that Math-Shepherd acknowledges. We audit a sample against PRM800K-style step labels.

We then plot two things against N and against the support distance: the overestimation gap (judge score minus reference value) of the step the search selects, and the error rate of selected steps. The winner's-curse hypothesis makes a specific prediction. The gap should grow roughly logarithmically in N and be concentrated in low-support steps.

The second stage builds the corrected judge. Let $R_\phi(s,a)$ be the process reward model's score for step $a$ after partial solution $s$. Let $\pi_D$ be the completer that produced its training labels. Let $\ell(s,a) = -\tfrac{1}{|a|}\log \pi_D(a\mid s)$ be the per-token negative log-likelihood of the step under that completer. We score

$$S(s,a) = R_\phi(s,a) - \beta \,\big[\ell(s,a) - c(s)\big]_+ ,$$

The terms in this score are defined as follows:

  • $c(s)$ is a per-state threshold. It is set to a high quantile of $\ell$ over the completer's own samples at $s$, so the penalty applies only to steps that are atypical for the data-generating model.
  • $[x]_+ = \max(x,0)$.
  • $\beta$ scales the penalty. It is calibrated on a held-out split so that the selected-step overestimation gap is flat in N.

The per-state threshold is the targeted part of the design, aimed at avoiding the over-pessimism that the conservative state value paper warns about. Ordinary low-probability steps that the completer itself sometimes produces pay nothing. A variant replaces the hinge with a bonus shrinking as $\sqrt{\log N}$, matching the predicted form of the bias.

The third stage asks whether the corrected judge also helps when it is used as a reward. We use it for step-wise PPO in the style of Math-Shepherd. We then rerun the coherence-versus-validity audit from the RLVR traces paper, with a GPT-4o step tagger spot-checked by humans, to test whether trace validity improves and not just local coherence.

Baselines

The naive reference point is majority voting over sampled full solutions, together with the uncorrected judge at small N. These tell us whether larger search budgets help at all.

The strongest reported uncorrected judge is PQM. It reaches 51.4% on MATH500 when verifying Llama-3-70B, against 39.8% for the cross-entropy judge, as reported in Process Reward Model with Q-value Rankings. Math-Shepherd's Best-of-256 figures, 43.5% on MATH and 89.1% on GSM8K for Mistral-7B, give a second anchor.

The strongest method aimed at the out-of-distribution problem is the adversarially trained process reward model. It reports an average of +3.4 points over ReST-MCTS on math and +5.3 points on SciBench. We will train it on the same Math-Shepherd data with the same backbone. We will report its training compute next to ours; ours adds only one forward pass of the completer per step.

We also include a deep-ensemble judge of five process reward models scored by mean minus standard deviation. It will receive the same total inference budget as our method.

All judges share backbone, training data, candidate pools, N values and hyperparameter search budget. Beating the field means two things:

  1. Higher Best-of-N accuracy than PQM and the adversarial judge at N of 64 and above on MATH500 and SciBench, with accuracy that no longer declines as N grows.
  2. A selected-step overestimation gap that stays flat in N.

Two ablations isolate the key ingredient:

  • Likelihood alone. Score steps by the completer's log-likelihood with no judge.
  • Uniform penalty. Apply the penalty with a global rather than per-state threshold.

Why not just…?

Why not just use an ensemble's disagreement as the uncertainty signal? This is the most serious alternative, and we treat it as a real threat. Ensembles trained on the same Math-Shepherd labels share the same blind spots. A fluent wrong step that none of the members saw can receive confidently high scores from all of them. Support distance under the completer measures unfamiliarity directly. The matched-compute ensemble baseline settles the question. If it matches our method on the off-support slice of the diagnostic plots, we will report that the cheaper, exact support signal is merely equivalent, not better.

Why not just train on more adversarial negatives? The adversarial judge does this and gains on SciBench. Its authors note, however, that the generator cannot target some error types, and every new generator shifts the support again. Enlarging support shrinks the region where overestimation happens. It does not remove the maximization bias. The N-sweep will show whether the adversarial judge's accuracy still decays at large N while ours does not.

Why not just ask a frontier LLM judge to check each step? Step-level judging by GPT-4o is reliable in some settings: AgentEval reports Cohen's κ of 0.84 on agent workflow steps. On mathematical logic errors, though, the RLVR traces study measured only 57.8% tagging accuracy against humans. Such a judge is also far more expensive per candidate at N of 256. We will include GPT-4o step checking at small N on a subset as a quality ceiling rather than a scalable competitor.

Why not just route uncertain steps to retrieval or abstention? Judge, Retrieve, or Abstain controls the false discovery rate for binary factual verdicts, but it offloads unresolved cases to humans and needs judge logits. Our score is complementary. A natural extension calibrates $\beta$ with the same risk-control machinery, but that paper's guarantees do not transfer to step-level search without new analysis.

Decisive Checks

The idea stands or falls on three results.

  1. The bias must exist. On generators far from the completer, the selected step's overestimation gap must grow with N and concentrate in high-$\ell$ steps. If the gap is flat, the winner's-curse framing is wrong, and the work reduces to a negative result about judge robustness.
  2. The correction must beat both simple alternatives. It must outperform likelihood alone and the uniform penalty. Otherwise the gain is just a fluency prior, or blanket pessimism that happens to help.
  3. The correction must not over-penalize correct novelty. On SciBench and the Hungarian exam, where correct steps are also often off-support, our method must not fall below the uncorrected PQM judge at small N. Falling below it would reproduce the over-pessimism that the conservative state value paper warns against.