Training Verifiers for the Budget They Will Be Searched At

When a language model answers a hard math problem, a common trick is to sample many candidate solutions and let a second model, called a verifier, pick the one it scores highest. This is called Best-of-N. Verifiers are trained the way world models in reinforcement learning usually are: to predict correctness as accurately as possible on average. Best-of-N does not use the average, though. It uses only the single top-scored candidate out of N. As N grows, that top slot fills with the rare wrong solutions the verifier happens to overrate. Accuracy then stalls or falls even as compute rises. This is objective mismatch, the same failure model-based reinforcement learning studied for a decade. A dynamics model with low prediction error can still steer a planner into hallucinated high-reward states, because its errors are not spread evenly across the states the planner actually visits.

We propose to carry the fix from that literature to inference-time compute scaling, meaning methods that buy accuracy by spending more computation when the model answers. The fix is to weight errors by how much they change the decision. Concretely, we train a verifier whose loss on each wrong candidate is weighted by that candidate's probability of winning a Best-of-N selection at a target budget N. Candidates are drawn from the generator's own output distribution, and that pool is re-mined as the verifier changes. The core prediction is falsifiable. A verifier trained this way should move or remove the U-shaped accuracy-versus-N curve seen with ordinary verifiers. It should also be budget-specific: a verifier trained for N=256 should beat one trained for N=4 at N=256, and lose to it at N=4.

Core Claim

Value-aware model learning, introduced in Value-Aware Loss Function for Model-based Reinforcement Learning, replaces likelihood with a loss that counts transition errors only through their effect on the value function. Iterative Value-Aware Model Learning makes this tractable by regressing against the current value iterate rather than a worst case over all value functions. The analogue for a verifier is direct. The "decision" is the argmax over N samples, and the only verifier errors that matter are those that change the argmax.

Let $s_\phi(x,y)$ be the verifier's score for candidate $y$ on prompt $x$. Let $F_x$ be the cumulative distribution of scores over the generator's candidates for $x$. For independent draws, a candidate with score $s$ is the maximum of $N$ draws with probability roughly $N\,F_x(s)^{N-1}$; this is a standard result about the largest of N independent samples. Our loss is a pairwise ranking loss between wrong candidates $y^-$ and correct candidates $y^+$ from the same pool, with each wrong candidate weighted by its chance of winning:

$$\mathcal{L}_N(\phi)=\mathbb{E}_{x}\,\mathbb{E}_{y^-,y^+}\Big[\,N\,\hat F_x\big(s_\phi(y^-)\big)^{N-1}\;\log\big(1+e^{\,s_\phi(y^-)-s_\phi(y^+)}\big)\Big],$$

Here $\hat F_x$ is the empirical score distribution estimated from a pool of $M \ge N$ samples per prompt. The weight is held fixed (stop-gradient) within each round. For small $N$ the weight is nearly uniform and the loss reduces to ordinary pairwise verifier training. For large $N$ it concentrates almost all gradient on the extreme upper tail, which is where reward hacking lives.

Between rounds we regenerate or re-score the candidate pool and recompute the weights. This mirrors the iterative structure of IterVAML. It also mirrors the reweighting toward the current policy's state distribution in Live in the Moment: Learning Dynamics Model Adapted to Evolving Policy, applied here to the distribution of candidates the verifier currently ranks highest.

One consequence is deliberate. The resulting verifier may be worse calibrated and less accurate pointwise than one trained with cross-entropy, yet better at selection. That is the "wrong yet useful" model property that A Unified View on Solving Objective Mismatch in Model-Based Reinforcement Learning documents for decision-aware world models. We will measure it explicitly rather than treat it as a bug.

Relation to Prior Work

Three papers motivate the gap. Demystifying LLM-as-a-Judge: Analytically Tractable Model for Inference-Time Scaling uses a Bayesian linear regression model to show two things. With a misspecified judge, error versus $k$ is U-shaped with a finite optimum $k^*$. And the best judge is not the true objective but one shifted to compensate for the generator's biases. That paper proposes no training procedure; our loss is one concrete way to learn such a generator-compensating judge. Scaling Test-Time Compute Without Verification or RL is Suboptimal proves verifier-based search beats verifier-free scaling. It also reports empirically that verifier inaccuracy causes reward hacking at extreme compute, and leaves open how to prevent it. Reward Model Generalization for Compute-Aware Test-Time Reasoning bounds search efficiency by the generalization error of the process reward model (a verifier that scores each intermediate step). It then controls the search itself (branching, temperature) using parameter sparsity as a stand-in for that error. Their response is to adapt the search to a fixed verifier; ours is to change the verifier's training objective, and the two compose.

Two papers sit closest in method and constrain the design. Entropy-Regularized Process Reward Model derives step labels from an entropy-regularized objective, using a soft-max aggregation when completions come from a weak policy. That aligns the verifier's labels with the generator's training objective, not with the selection rule at a budget. It also still shows reward hacking at large N and costs 16 completions per step. Maximum Likelihood Reinforcement Learning builds a family of objectives indexed by rollout budget and reports up to 20x test-time sampling efficiency over GRPO. It does this on the generator side and treats the verifier as an oracle. Our proposal is its mirror image: a budget-indexed objective for the verifier. Combining the two is a natural later step.

Helping or Herding? Reward Model Ensembles Mitigate but do not Eliminate Reward Hacking supplies both a baseline and a warning. Ensembles help Best-of-n, but errors shared across members are still exploited. This suggests the remedy has to target the specific candidates the search surfaces, not just reduce variance.

Research Program

The primary setting is outcome-level Best-of-N on math with checkable answers, where correctness labels are free. We sample pools of $M=1024$ candidates per training prompt from each generator on the GSM8K and MATH training splits. We fine-tune verifiers initialized from a public process reward model, Qwen2.5-Math-PRM-7B, which the Demystifying paper used as a judge, applying $\mathcal{L}_N$ for target budgets $N \in \{4, 16, 64, 256\}$. Each verifier gets three re-mining rounds.

Generators are Mistral-7B, Llama-3-8B-Instruct, Qwen2.5-7B and DeepSeek-R1-Distill-Qwen-1.5B. This lets us test whether the learned shift is generator-specific, as the Demystifying analysis predicts. A secondary arm extends the weighting to step-level beam search. There, a wrong prefix is weighted by its estimated probability of surviving the beam at width $B$. This tests whether the idea survives the move from independent samples to sequential search, which the CATS bound does not model.

Baselines

The naive reference point is majority voting over the same N samples, together with the frozen Qwen2.5-Math-PRM-7B used unchanged for Best-of-N. Majority voting uses no verifier and so cannot be reward-hacked. A curve that bends below it at large N is the clearest symptom of mismatch.

The strongest existing verifiers are Math-Shepherd and ER-PRM retrained on our generators. Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations labels steps by Monte Carlo rollouts. It reports that reranking 256 samples from an RL-tuned Mistral-7B gives 89.1% on GSM8K and 43.5% on MATH. Our Mistral-7B arm at N=256 is designed to match that setup, and beating 43.5% on MATH there under matched generator compute is the target. ER-PRM reports a 2–3% Best-of-N gain over prior verifiers on MATH and about 1% on GSM8K. The strongest search-level method is CATS, which reports 98.0% on GSM8K with Qwen2.5-7B. Because GSM8K is near ceiling there, we treat CATS mainly as a composition test: CATS run with its original verifier versus CATS run with ours. No reported result on AIME24 or MATH500 was found on Lacuna for CATS beyond qualitative claims of beating Best-of-N, beam search and majority voting.

Fairness comes from matching budgets in three places. Total generator tokens spent building verifier training data are equalized; ER-PRM's 16 completions per step are converted to a token budget, and our pool size M is set to match it. Fine-tuning steps and hyperparameter search trials are the same for every verifier. Test-time sample budgets are identical.

We also run a Pretrain-style ensemble of three verifiers, following Helping or Herding, given the same total training compute.

Two ablations isolate the key ingredient. The first is uniform hard-negative mining: the same pool, the same pairwise loss and the same re-mining, but each wrong candidate weighted equally whenever it scores above some correct candidate. The second is the order-statistic weighting with a single round and no re-mining. Beating the uniform ablation is what would show the budget weighting itself matters. Beating the single-round ablation is what would show the distribution correction matters.

Why not just…?

Why not just stop at the optimal budget $k^*$ and tune the temperature? The Demystifying analysis shows that a finite $k^*$ and a nonzero temperature $T^*$ exist, so tuning both is a legitimate fix for the U-shape. It is not a fix for the ceiling: it caps accuracy at the peak of a mismatched curve. We will tune $k$ and $T$ for every baseline on held-out data and report accuracy at each method's own best budget. Our claim survives only if the peak itself is higher, or occurs at a larger N, with the trained verifier. If tuned truncation matches us, the honest conclusion is that budget-aware training buys nothing beyond choosing N well.

Why not just ensemble reward models? Helping or Herding reports that at n=64 on TL;DR, Pretrain Ensembles reach a 90% win rate against 85.3% for single reward models. They also show that blind spots shared by every member are still exploited. An ensemble lowers variance but leaves those shared biases in place. Our loss aims directly at the specific wrong candidates that reach the top under the current generator. The matched-compute ensemble baseline settles which approach does more. The two are also compatible, and we will report the combination.

Why not just do ordinary hard-negative mining? This is the most serious threat. Our method is a form of hard-negative mining, and a uniformly weighted version with re-mining may capture most of the gain. The uniform ablation exists to test exactly this. The order-statistic weighting makes a sharper prediction than uniform mining: verifiers become budget-specific. If the cross-budget test below shows no specificity, and uniform mining matches us at every N, we will report the contribution as a diagnostic plus a recipe rather than a new objective.

Decisive Checks

All evaluations run on MATH500 and the GSM8K test set, plus AIME24 as an out-of-distribution transfer set. For every verifier we trace accuracy against N from 1 to 1024 and record where each curve peaks. Using the metrics of To aggregate or Not to Aggregate? Test-Time Aggregation Beyond Verifier-Friendly Benchmarks, we also report the diversity window (pass@N minus pass@1) and the fraction of that window converted into correct answers.

Four results would be decisive. First, baseline verifiers should show a downturn at large N on at least one generator while ours stay monotone or peak later. Second, the cross-budget matrix of verifiers trained at N against those evaluated at N′ should show a winning diagonal. Third, pointwise calibration error (expected calibration error) and AUROC should get worse while selection accuracy improves, which is the "wrong yet useful" signature. Fourth, a verifier trained against one generator should degrade on another, as the generator-compensation argument predicts.

A null result on the second check, combined with parity with uniform mining, would falsify the central claim.