When a language model spends extra compute at inference by sampling many reasoning steps and keeping the ones a learned scorer likes, it is running an actor-critic loop. The sampler plays the actor, the step-level value model plays the critic, and the search pushes the actor toward exactly the regions where the critic is least trustworthy. Reinforcement learning has a name for this failure: the moving target problem. The actor follows a critic whose errors it helps create. Its standard remedy, from TD-Regularized Actor-Critic Methods, is to slow the actor down wherever the critic's temporal-difference (TD) error is high. The TD error is the critic's own self-inconsistency: how far its estimate for a state disagrees with its estimates for that state's successors. We propose carrying this remedy to inference time. A step-level value model that estimates the probability a partial solution will end correctly must satisfy a consistency law: its score for a prefix should equal the average of its scores for the continuations the model would sample. Search already draws those continuations, so the violation of this law can be measured at every node, with no labels and no extra model calls. We use it as a per-state brake. It penalizes branches where the critic contradicts itself, and it halts the search when added budget mainly buys self-contradiction.
The point is practical. Verifier-guided search scales better than verifier-free approaches (Scaling Test-Time Compute Without Verification or RL is Suboptimal), but the same paper and Reward Model Generalization for Compute-Aware Test-Time Reasoning show that verifier error is what caps it. At high budgets, search exploits verifier flaws, and the samples needed grow sharply with verifier generalization error. A cheap, local, label-free detector of where the verifier is wrong would turn "more compute eventually hurts" into "more compute stops helping, and we can tell when."
Core Claim
Let $V(s)$ be a frozen step-level value model's estimate that prefix $s$ leads to a correct final answer. Let $c_1,\dots,c_K$ be $K$ next-step continuations sampled from the base model at $s$; best-of-$N$ and beam search draw these before selection anyway. If $V$ were exact, $V(s)$ would equal the expected value of $V(c)$ under the base sampler, because success probability is a martingale along the generation. We define the test-time TD residual
$$\delta(s) = V(s) - \frac{1}{K}\sum_{k=1}^{K} V(c_k),$$
which measures the critic's self-inconsistency at $s$, up to sampling noise of order $1/\sqrt{K}$. Search then ranks a partial path $s_{0:t}$ by
$$J(s_{0:t}) = V(s_t) - \lambda \sum_{u \le t} \delta(s_u)^2 ,$$
where $\lambda \ge 0$ trades value against accumulated inconsistency. This is the TD-regularized actor objective, with the search's selection step standing in for a policy gradient step.
The claim has two parts. First, $|\delta(s)|$ predicts where $V$ is actually wrong, measured against expensive Monte Carlo rollouts. Second, using it as a penalty and as a halting rule removes the late-budget decline of verifier-guided search without lowering its peak.
Relation to Prior Work
Two lines of work motivate the proposal and one supplies the method. The motivation comes from test-time scaling. Scaling Test-Time Compute Without Verification or RL is Suboptimal shows verifier-based search beats verifier-free fine-tuning but degrades through reward hacking at high compute. Inverse Scaling in Test-Time Compute shows longer reasoning can make answers worse on distractor-laden counting, spurious regression and logic puzzles. Neither offers a per-state signal of when to stop trusting the scorer.
The method comes from the RL side. TD-Regularized Actor-Critic Methods penalizes actor updates by the critic's squared TD error and prevents divergence in linear-quadratic control and MuJoCo. We reuse that penalty almost verbatim, but apply it to a search procedure rather than to parameter updates, and to a critic that is frozen. Improving Deep Reinforcement Learning by Reducing the Chain Effect of Value and Policy Churn shows critic errors concentrate off the states that were trained on, and that local trust regions such as PPO clipping do not catch them. This constrains our design: any reliability signal must be evaluated at the states search actually visits, not inherited from training-time statistics.
The closest neighbors each leave out the piece we add. CATS (Reward Model Generalization for Compute-Aware Test-Time Reasoning) adapts sampling hyperparameters using reward-model parameter sparsity. That reliability proxy is global, a property of the model rather than of each state. Our residual is local to each node and costs nothing extra. ∇-Reasoner does gradient descent on token logits against a frozen reward model and proves this is dual to single-sample policy gradient. It explicitly has no mechanism to detect when the frozen reward model is miscalibrated, which is exactly the gap a TD penalty fills. Re² trains the model to emit a restart action when a chain goes bad. Its signal is learned into the actor; ours lives in the critic and needs no retraining of the generator. DAPO avoids actor-critic instability by training a step critic offline from Monte Carlo rollouts and freezing it. We adopt its critic-training recipe to obtain $V$, and ask what happens when that frozen critic is then pushed off-distribution by search.
Research Program
We first build the critic. Following DAPO's Stage 1, we train a step-level value model for Qwen2.5-7B-Instruct on MATH training problems using Monte Carlo completions from newline-delimited steps. We also use an off-the-shelf process reward model, to test whether the residual idea transfers to a scorer not trained as a value function. For a process reward model the martingale law holds only approximately, and measuring how badly it fails is itself a finding.
Next comes the diagnostic study, which gates everything else. On held-out MATH-500 search trees, we compute $\delta(s)$ at every node. We also compute an expensive reference: the true success probability from 64 Monte Carlo completions per node. The question is whether $|\delta(s)|$ ranks nodes by actual critic error $|V(s) - V_{MC}(s)|$. We report the area under the ROC curve (AUROC) for flagging large errors. We also track how this predictive power changes along the search, from early nodes to the high-$V$ nodes that late search concentrates on.
Then we build the controller. We plug $J$ into beam search and best-of-$N$ over steps, and add a halting rule. Expansion stops when the best path's accumulated squared residual rises faster than its value as budget grows, which is the signature of exploiting the critic rather than finding better solutions. $\lambda$ and the halting threshold are tuned on a MATH training split only. A short extension asks whether the same residual, computed over final answers, acts as an overthinking brake on the inverse-scaling tasks.
Baselines
The naive reference points are greedy decoding and self-consistency majority voting at matched sample counts. They need no critic, and tell us whether any critic-guided method is worth its cost.
The main competitor in our own setting is unregularized critic-guided search: the same beam search and step-level best-of-$N$, the same critic, the same base model and the same budgets in model calls, with $\lambda = 0$ and no halting. This is also the key ablation, because it isolates the TD penalty as the only difference. Beating it means a higher accuracy maximum over budget, plus the absence of decline from that maximum up to 64× the base budget. If the peak drops by more than one point, the method fails.
The strongest reported external method on MATH-500 in the file is ∇-Reasoner, which raises Qwen-2.5-7B-Instruct from 71.2% greedy to 80.4% accuracy (∇-Reasoner). The file does not state the compute behind that number, so we will rerun ∇-Reasoner with our critic as its reward and report its accuracy against model calls on the same axis. Beating it means matching 80.4% at equal or fewer calls, or exceeding it at equal calls.
CATS is the closest adaptive-compute competitor. There is no reported MATH-500 result on Lacuna for CATS beyond the qualitative claim that it outperformed other search methods. On GSM8K it reports 98.0% with Qwen2.5-7B, which leaves little headroom, so we will reimplement it and compare mainly on MATH-500 and AIME.
Two further ablations control for cheaper uncertainty signals. The first is an ensemble of five independently trained critics, using their disagreement as the penalty. The second is the variance of $V$ across siblings, which uses the same samples as $\delta$ but ignores the parent's own estimate. All methods share data, critic-training compute where applicable, and a tuning budget of the same number of validation runs.
Why not just…?
Why not just use an ensemble of critics and penalize disagreement? This is the real threat, since ensemble disagreement is a standard uncertainty signal and may track critic error as well as $\delta$. Our case rests on cost and on what is being measured. The residual needs no extra models. It also measures inconsistency along the generation process, which disagreement among critics trained on the same data can miss when they share the same blind spot. The diagnostic AUROC study settles this directly. If the ensemble predicts error better at equal compute, including the cost of training and running five critics, we will report the residual as the cheaper but weaker option and not claim superiority.
Why not just use sibling score variance, which uses the same samples? Variance across continuations is large wherever the outcome is genuinely uncertain, even when the critic is perfectly calibrated. The residual is zero there and grows only when the parent's estimate disagrees with its children's average. The sibling-variance ablation tests whether this distinction matters in practice. If the two perform the same, the Bellman framing adds nothing and we will say so.
Why not just cap the budget at the value that does best on validation, or use majority voting? A fixed cap is tuned for the average problem. The decline in Scaling Test-Time Compute Without Verification or RL is Suboptimal and the overthinking in Inverse Scaling in Test-Time Compute both depend on the problem, so a per-instance brake should spend less on easy problems and avoid over-searching hard ones. RefCritic reports that critic filtering beats plain Maj@64 by 3.6 points on AIME 2025, so voting alone leaves headroom. We include an oracle-tuned fixed cap as a baseline. The adaptive brake must beat it at equal average compute.
Why not just relabel with Monte Carlo rollouts, as DAPO does? This gives accurate values, but at 64 completions per node it multiplies cost by orders of magnitude. We use it only as the ground-truth reference that tells us what the residual should be detecting.
Proposed Experiments
The decisive first check is the diagnostic. If $|\delta|$ fails to predict critic error measured by Monte Carlo rollouts, with AUROC below 0.65 on MATH-500 nodes, the project stops or pivots to the ensemble signal. If it succeeds, the second check is accuracy as a function of budget on MATH-500, AIME 2024/2025 and GSM8K, run from 1× to 64× calls. The prediction is that unregularized search peaks and then declines, while TD-penalized search plateaus at the same or a higher peak and halts earlier on easy problems.
The third check uses the inverse-scaling suite in safety-research/inverse-scaling-ttc (misleading math, spurious regression, Zebra puzzles). It asks whether answer-level residuals stop overthinking before accuracy falls. Here the falsifying outcome is that the brake triggers no earlier than a length cap tuned on validation data. Across all experiments we report accuracy against model calls, problems solved per thousand calls, and the correlation between the halting point and each method's own best budget.
References
- TD-regularized actor-critic methods
- Scaling Test-Time Compute Without Verification or RL is Suboptimal
- Reward Model Generalization for Compute-Aware Test-Time Reasoning
- Inverse Scaling in Test-Time Compute
- Improving Deep Reinforcement Learning by Reducing the Chain Effect of Value and Policy Churn
- $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space
- $\textbf{Re}^{2}$: Unlocking LLM Reasoning via Reinforcement Learning with Re-solving
- DAPO : Improving Multi-Step Reasoning Abilities of Large Language Models with Direct Advantage-Based Policy Optimization
- RefCritic: Training Long Chain-of-Thought Critic Models with Refinement Feedback