A common way to make a language model reason better at test time is to pause it partway through a solution, branch into several candidate next steps, and pick the branch that most often leads to a correct answer when the model finishes it many times. These random completions are called rollouts, and the fraction that succeed is a Monte Carlo estimate of the branch's value. The method is expensive, since every step pays for $M$ rollouts per branch, and it rests on a hidden assumption: that "succeeds" is judged by a reliable checker. In practice the checker is imperfect. It might be a unit-test suite that passes buggy code, or a model-based judge that accepts wrong algebra. We propose to treat each branching decision as a hypothesis test whose error probability shrinks exponentially in the rollout budget, and to compute the rate of that shrinkage (its error exponent, a concept from coding theory) as an explicit function of the checker's mistakes. That rate tells a search procedure three things: how many rollouts a given step deserves, when more rollouts are wasted, and when the checker's errors make more rollouts actively misleading.
The opportunity is that two literatures each hold half of the answer. Work on imperfect verification shows that verifier errors cap what resampling can achieve. The cap is set by the shape of the verifier's ROC curve, the curve tracing how true-positive and false-positive rates trade off as the acceptance threshold moves (ROC-n-reroll). In code generation that cap can even make utility fall as more samples are drawn (The Limits of Inference Scaling Through Resampling). But this work only studies choosing among finished answers. Work on Monte Carlo value estimation shows that per-prefix success probabilities expose real structure in reasoning, but it treats rollouts either as a clean offline labeling oracle or as too costly to run online (The Potential of CoT for Reasoning; BiRM). No existing work says how the verifier's errors propagate into step-level decisions, or how that should decide where inference latency is spent.
Core Claim
Consider a step where the search must choose between two partial solutions $i$ and $j$. Let $p_i$ be the true probability that completing prefix $i$ yields a correct answer. What the search actually observes is the probability that a completion passes the verifier:
$$q_i = \alpha_i\, p_i + \beta_i\,(1 - p_i),$$
where $\alpha_i$ is the verifier's true-positive rate and $\beta_i$ its false-positive rate on completions of prefix $i$. The search compares empirical pass rates from $M$ rollouts each. By Chernoff's bound for Bernoulli samples, it picks the wrong prefix with probability about $\exp(-M\,C(q_i,q_j))$, where $C$ is the Chernoff information between Bernoulli($q_i$) and Bernoulli($q_j$). That formula holds only when the ordering of $q$ agrees with the ordering of $p$. If it does not, the error probability tends to one as $M$ grows.
This yields two regimes, which mirror mismatched decoding in information theory. There, a receiver scores codewords with a metric that differs from the true channel, and its reliability can stay positive or collapse depending on how the metric relates to the channel (Mismatched Decoding Reliability Function at Zero Rate; Mismatched Decoding: Finite-Length Bounds, Error Exponents and Approximations).
In the first regime, the verifier's error rates do not depend on the prefix ($\alpha_i=\alpha$, $\beta_i=\beta$). Then $q_i-q_j = J\,(p_i-p_j)$, where $J=\alpha-\beta$ is Youden's index. Ordering is preserved and only the exponent shrinks. For nearby values the Chernoff information is quadratic in the gap, so the shrinkage is roughly a factor of $J^2$. In this regime more rollouts always help; they just cost about $1/J^2$ times as much.
In the second regime, some prefixes lead systematically to "fragile" completions that fool the verifier. This is the per-prefix version of the capability–reliability correlation reported for unit tests in The Limits of Inference Scaling Through Resampling. Here $\beta_i$ varies with the prefix, the ordering can flip, and the exponent for the true decision is zero. Adding rollouts then buys confidence in the wrong branch.
Our claim is that a search procedure which estimates these per-step exponents online, and spends rollouts accordingly, can cut the tokens and latency needed to reach a given true accuracy. The same procedure can detect the second regime and respond by spending a little budget on a more expensive, more reliable check rather than on more cheap rollouts.
The exponents also give a budget rule. Over a search of $T$ steps with rollout budgets $M_t$ and estimated exponents $C_t$, a union bound gives a total wrong-branch probability of at most $\sum_t \exp(-M_t C_t)$. Minimizing total rollout tokens subject to this sum staying below a target $\delta$ has a water-filling solution:
$$M_t \approx \frac{1}{C_t}\log\frac{1}{\lambda\,L_t\,C_t},$$
where $L_t$ is the expected rollout length at step $t$ and $\lambda$ is set by $\delta$. The rule gives few rollouts to steps where branches are already well separated. It also gives few rollouts where $C_t$ is so small that discrimination is hopeless, for example among near-zero-value prefixes. Those are exactly the "lucky guess" traces whose value hovers near zero until the final token (The Potential of CoT for Reasoning). The rule concentrates effort where the exponent is moderate.
One side benefit follows from the definition. Monte Carlo value measures whether a prefix can still recover, not whether each step is locally correct. So it does not penalize the non-monotonic "reasoning tangents" that most successful traces contain; that same paper finds only about 17% of Llama-3.1-70B traces are monotonic. A step-correctness reward model would prune many of these tangents.
Research Program
The first component is estimation. At each branching step we draw a small pilot set of rollouts per candidate prefix and score them with the cheap verifier: base unit tests for code, a model-based judge or final-answer extractor for math. On a small random fraction of these pilot rollouts we also run an expensive audit. For code this is extended edge-case tests; for math it is ground-truth answer matching during development, or a stronger judge at deployment.
Audited rollouts give per-prefix estimates of $\alpha_i$ and $\beta_i$. We shrink these toward a pooled estimate, using the observed pass rate as a covariate, because the capability–reliability correlation suggests false-positive rate falls as pass rate rises. From these estimates we compute an estimate of the corrected exponent $C_t$, and we also run a test for ordering flips: is the estimated true-value ordering inconsistent with the observed pass-rate ordering?
The second component is allocation. We apply the water-filling rule above to choose between two actions at each step: buy more cheap rollouts, or buy audits. We include audits because in the second regime the exponent of cheap rollouts is zero and only the audit has a positive exponent. The per-step comparison is between the exponent gained per token from each action.
The same quantities give a stopping rule. When the best branch's corrected value is separated from the rest with estimated error below the step's share of $\delta$, the search commits. When no branch is ever likely to be separated, it falls back to capped sampling in the spirit of Capped Rejection Sampling from ROC-n-reroll.
The third component is analysis. We will state and check the two-regime result formally. We will derive how the exponent under prefix-independent noise shrinks with $J$. We will characterize when prefix-dependent false positives force a zero exponent, in analogy to the balanced versus unbalanced distinction in the mismatched zero-rate theory. We do not claim that the Gallager-style formulas transfer directly; we borrow the structure of the question, namely when a mismatched score still yields exponential reliability.
Baselines
The naive reference point is uniform step-level Monte Carlo search. It uses the same branching factor and a fixed $M$ at every step, with rollouts judged by the cheap verifier only. We sweep $M$ over the same total token budgets as our method. This shows whether the allocation matters at all.
The strongest existing method for adaptive allocation is Instance-Adaptive Scaling from Know What You Don't Know. It trains a quantile-regression reward model on Monte Carlo calibration data and uses its conservative value estimate to set per-problem sample budgets. The paper reports that on MATH500 "IAS achieved similar performance to a fixed budget of 64 samples while reducing the average sample budget by up to 75%." IAS is the closest competitor because it also turns value estimates into budget decisions. It differs in two ways: it allocates per problem rather than per step, and it takes verifier labels as ground truth. Beating it means matching its true accuracy at a lower mean token budget, or exceeding it at equal budget, measured against ground-truth correctness rather than the cheap verifier.
The strongest step-level search competitor is BiRM beam search from Better Process Supervision with Bi-directional Rewarding Signals. BiRM adds a value head trained on Monte Carlo success fractions to a step-correctness head. The file reports that under step-level beam search with $K=100$ on MATH-500, BiRM "outperformed ORMs by 5.0% and PRMs by 3.8%." We retrain BiRM on rollouts from the same generator and the same cheap verifier, so its labels carry the same mismatch our method corrects. We then compare at matched generated tokens, counting BiRM's scoring passes. We also report Hista as a cheap value estimator. It is reported to match two-rollout Monte Carlo sampling (MCS@2) on its own value-estimation benchmark, SVEB, and we test it as a drop-in replacement for pilot rollouts.
For post-hoc selection we run Capped Rejection Sampling and Best-of-$N$ from ROC-n-reroll, using an outcome verifier at matched tokens. That paper reports no single scalar accuracy on these benchmarks, so we reproduce it ourselves. For code we also run the small-$K$ resampling regime of The Limits of Inference Scaling Through Resampling, which reports an optimal $K$ below 10 but no pass-rate figure in the file.
Two ablations isolate the key ingredient. The first uses exponent-based allocation computed from raw pass rates with no mismatch correction and no audits; this is a standard best-arm-identification allocation. The second uses mismatch correction and audits with uniform $M$. All methods get the same generator, the same prompts, the same cheap and expensive verifiers, and the same tuning budget of a single held-out split for choosing $\delta$ or its equivalent. Audit calls are counted in the token and wall-clock budget, weighted by their actual cost.
Why not just…?
Why not just use a best-arm-identification bandit on rollout outcomes? Fixed-confidence bandit allocation already spends samples according to divergence between arms, which is our first ablation. In the prefix-independent regime we expect it to match us. We will report that honestly, since there our contribution reduces to the stopping rule and the prediction that cost scales as $1/J^2$. The bandit cannot help in the prefix-dependent regime, because it identifies the arm the verifier prefers. Experiment two below measures how often that regime occurs on real code and math. If flips turn out to be rare, the proposal's practical value shrinks, and we will say so.
Why not just train a better value model, like BiRM or Hista, and skip online rollouts? These models are trained on rollouts labelled by the same imperfect verifier, so they learn $q$, not $p$. The calibration paper also shows that such models become overconfident when the generator differs from the training policy (Know What You Don't Know). They remain useful as cheap priors, and we test Hista in that role. The head-to-head comparison against BiRM at matched tokens shows whether online correction is worth its cost.
Why not just resample a few finished answers and stop at small $K$? The code results argue that small-$K$ resampling is nearly optimal given a fixed verifier (The Limits of Inference Scaling Through Resampling). Step-level audits change the verifier's effective reliability on exactly the branches that matter. If Capped Rejection Sampling matches our method at equal tokens on HumanEval+, then step-level search is not worth its latency, and we would report that as a negative result.
Proposed Experiments
The main testbed is HumanEval+ and MBPP+. These give a natural pair of verifiers: the original unit tests are the cheap, imperfect check, and the extended edge-case suites are the audit and the ground truth. The same pairing lets us measure per-prefix false-positive rates directly. For math we use MATH-500 and AIME, with a model-based judge as the cheap verifier and ground-truth answers for evaluation. We also create a controlled variant in which we inject judge errors that are either prefix-independent or tied to specific solution strategies.
The first decisive check tests the theory. For fixed pairs of prefixes, we plot log wrong-branch rate against $M$ and compare the measured slope with the predicted exponent. The measured slope should shrink roughly as $J^2$ under prefix-independent noise and flatten to zero or reverse under strategy-tied noise.
The second check measures prevalence. It asks what fraction of branching steps on HumanEval+ and MATH-500 show a significant ordering flip between cheap-verifier and ground-truth value. This number decides how much of the method's gain can come from mismatch correction.
The third check is the end-to-end comparison: true accuracy against total tokens and against wall-clock latency, for our method, IAS, BiRM beam search, Capped Rejection Sampling, uniform search, and the two ablations. We also report the fraction of ultimately correct non-monotonic traces that each method prunes.
The claim is confirmed if our method dominates the accuracy–token frontier over IAS and BiRM on the code benchmarks and on the strategy-tied math variant, while tying the bandit ablation on the prefix-independent variant. It is refuted if the bandit ablation matches us everywhere, or if audits never pay back their cost.
References
- ROC-n-reroll: How verifier imperfection affects test-time scaling
- The Limits of Inference Scaling Through Resampling
- The Potential of CoT for Reasoning: A Closer Look at Trace Dynamics
- Better Process Supervision with Bi-directional Rewarding Signals
- Zero-rate reliability function for mismatched decoding
- Mismatched Decoding: Finite-Length Bounds, Error Exponents and Approximations
- Know What You Don't Know: Uncertainty Calibration of Process Reward Models
- Hista and Numca: Estimate State Value Effectively for Large Language Model Reinforcement Learning