When a language model answers a hard question, a common way to spend extra compute is to sample many candidate answers and let a checker, called a verifier, pick one. Recent theory shows a hard limit on this. If each candidate is scored once by one imperfect verifier, accuracy stops improving at a ceiling set by how often the verifier wrongly approves a wrong answer. More samples cannot get past it. This proposal treats verification differently. Each check is one use of a noisy channel whose two error directions differ, as they do on the asymmetric error channels studied in coding theory. A wrong approval is catastrophic; a wrong rejection only costs another sample. Under that view, the right move is to verify sequentially. Spend checks on the current best candidate, choose among several checking methods with different error profiles, and stop once the evidence is strong enough. If the checks' errors are at least partly independent, the residual error should keep falling as verification compute grows, instead of flattening.
In two sentences: the accuracy ceiling of best-of-N and rejection sampling comes from scoring each candidate with a single verifier call, not from verification itself. A policy that repeatedly checks the leading candidate, choosing among checkers with different false-approval and false-rejection rates and stopping on a likelihood threshold, should beat that ceiling exactly to the extent that the checkers' errors are not perfectly correlated, and we can measure that extent directly.
Core Claim
ROC-n-reroll models best-of-N (sample N candidates, keep the top-scored one) and rejection sampling (sample until one passes a threshold) through the verifier's receiver operating characteristic, the curve of true-approval rate against false-approval rate. It proves that as N grows, both methods converge to an accuracy ceiling fixed by the slope of that curve at zero false-approval rate. That result motivates this work, and its assumptions define where we depart from it. It takes one score per candidate, one verifier, and an allocation in which every unit of compute buys a new sample.
Our claim is that relaxing these assumptions changes the scaling law. Suppose verification modality $j$ (an LLM judge, a code-executed back-substitution, a unit-test run, a re-derivation by a second model) approves a correct candidate with probability $t_j$ and an incorrect one with probability $f_j$. Each call then works like one use of a binary asymmetric channel. If calls are conditionally independent given the candidate's correctness, Wald's sequential test needs roughly
$$ n_j(\delta) \approx \frac{\log(1/\delta)}{D_j}, \qquad D_j = \mathrm{KL}\big(\mathrm{Bern}(f_j)\,\|\,\mathrm{Bern}(t_j)\big), $$
calls to push the probability of accepting a wrong candidate below $\delta$. Here $D_j$ measures how much evidence one call of modality $j$ gives against a wrong candidate. A checker shaped like a Z-channel (one that essentially never rejects correct answers, $t_j \approx 1$) yields effectively unlimited evidence from a single rejection. This is the coding-theoretic fact that one output of a Z-channel is noiseless.
Real verifier errors are correlated. A candidate that fools a judge once tends to fool it again. The ceiling therefore does not vanish. It moves to the probability that a wrong candidate fools every modality used, jointly. This yields the testable prediction: the gain over the ROC-n-reroll ceiling equals the gap between single-modality and joint false-approval rates, and both quantities are measurable.
Relation to Prior Work
Two test-time papers motivate the gap. Scaling Test-Time Compute Without Verification or RL is Suboptimal proves that verifier-based scaling beats verifier-free fine-tuning, with a gap growing as $\sqrt{H}$ in the compute horizon. It reports 8x compute efficiency on MATH, but also verifier exploitation at high budgets. ROC-n-reroll explains that degradation geometrically. Neither paper considers re-verifying a candidate or choosing among checkers.
Pushing Test-Time Scaling Limits of Deep Search with Asymmetric Verification uses "asymmetric" in a different sense: checking is cheaper than searching. It applies a verifier post hoc to best-of-K trajectories. We take that cost asymmetry as given and add the error-direction asymmetry, which that paper does not model.
On the coding side, Sequential Transmission Over Binary Asymmetric Channels With Feedback supplies the method template. Its variable-length scheme has a communication phase that splits posterior mass among messages and a confirmation phase that sends the most distinguishable symbol once one message dominates. It achieves capacity and the optimal error exponent. The analogy is imperfect, and we say so. In that setting the transmitter knows the message and feedback is noiseless. Here no party knows the answer, so the closer picture is a receiver choosing noisy queries. The structural lesson still carries over: allocate in two phases and confirm through the most discriminating channel. Its exponential complexity in message bits also disappears here, because the "messages" are only the handful of distinct final answers among the samples.
Density Evolution for Asymmetric Memoryless Channels shows bit error falling exponentially with decoding iterations. That proof rests on a concentration theorem requiring local neighborhoods to be cycle-free, meaning independent evidence. We use this as a lens on the contradiction the research file highlights. LLM test-time scaling saturates while iterative decoding does not, and we hypothesize the reason is that correlated verifier errors play the role of short cycles. The same paper shows that codes designed for the Z-channel beat symmetric designs (threshold 0.2731 versus 0.2305). This constrains us against symmetrizing the problem: treating approvals and rejections as equally informative throws away exactly the structure we exploit.
Research Program
Measuring channel parameters. For each task family, we estimate every checking modality's channel parameters $(t_j, f_j)$ on a held-out calibration split. We also estimate the joint false-approval probability for every subset of modalities and for repeated calls of one modality under resampled prompts.
The modalities are chosen to have deliberately different asymmetries:
- an LLM judge, which tends toward false approvals;
- code-executed checks, such as substituting a math answer back into the problem's constraints or running unit tests on code, which approximate Z-channels because failures are rarely spurious when the check is valid;
- independent re-derivation by a second model, which has roughly symmetric errors.
The research file notes that environment-grounded checking in Mei et al. prunes invalid reasoning early. We use code execution in that spirit, but as a measured channel rather than an oracle.
The allocation policy. The policy keeps a posterior over distinct candidate answers, built from sample counts and verifier outcomes. It has two phases.
- Exploration phase. While no candidate dominates, it chooses between drawing a new sample and running the cheapest high-$D_j$ check on the current leader. The choice maximizes expected log-likelihood-ratio gain per token.
- Confirmation phase. Once the leader's posterior passes a switch threshold, the policy spends checks only on that leader. It picks the unused modality that maximizes conditional divergence given which modalities have already approved. This rule automatically avoids re-querying a checker whose errors are known to be correlated with ones already used.
The policy stops when posterior error drops below $\delta$ or the budget runs out. A cost ratio $c$ between false approval and false rejection sets $\delta$; this is the single knob that encodes the asymmetry.
Theory. We prove a non-asymptotic bound on expected verification calls and residual error under a latent "deceptiveness" model, in which each wrong candidate draws a per-candidate fooling probability. The bound recovers ROC-n-reroll's ceiling when only one modality is available and calls are perfectly correlated. It recovers the Wald rate when calls are independent.
Baselines
Self-consistency. The naive reference is majority vote over N samples. It needs no verifier, treats every sample's vote equally, and on hard search tasks it lags far behind verifier-based selection. Pushing Test-Time Scaling Limits of Deep Search with Asymmetric Verification reports BrowseComp rising from 19% for vanilla GLM-4.5 to 54.0% with verification. Beating majority vote is necessary but uninformative.
Single-modality rejection sampling. The strongest existing method is rejection sampling with the best single verifier, which ROC-n-reroll proves dominates best-of-N for concave curves. We run it with each modality separately and report the best, with the threshold tuned on the calibration split under the same total token budget, verifier tokens included. ROC-n-reroll evaluates on GSM8K, MATH, HumanEval+ and GPQA with Qwen and Llama-3 models, but no reported result found on Lacuna for its exact accuracy numbers. We therefore reproduce it ourselves. As an absolute reference point on MATH500, Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning reports 91.48% accuracy for its 32B TOPS model at about 1,883 tokens per problem. Beating single-modality rejection sampling means two things: higher accuracy at matched tokens for budgets beyond its plateau, and lower false-approval rate at equal accuracy.
Fixed multi-verifier ensemble. This is the most dangerous competitor. Every candidate gets all modalities once, scores are combined by a logistic model fit on calibration data, and selection is by best-of-N or rejection sampling. It uses the same checkers as our method, but with a non-adaptive, symmetric allocation.
Ablations.
- Symmetric cost. Our policy with $c = 1$ isolates the role of asymmetric costs.
- Single repeated modality. Our policy restricted to repeated calls of one modality isolates modality diversity from mere repetition.
Beating the ensemble at matched tokens is the result that would show adaptivity matters.
Why not just…?
Why not just use self-consistency? It treats all errors as symmetric and cannot recover a correct minority answer. The deep-search results above show a large gap between at-least-one-correct and majority-correct on hard tasks. We include it as the floor, not as the threat.
Why not just tighten the rejection-sampling threshold? ROC-n-reroll proves this cannot work past a point. The ceiling is the curve's slope at the origin, and a stricter threshold only moves along the same curve while costing more samples. Our sequential method changes the curve by combining calls. The single-modality ablation shows how much is gained by repetition alone.
Why not just ensemble several verifiers with a learned combiner? This is a real threat. If verifier errors were nearly independent and checks were cheap, scoring every candidate with every checker could match our method's accuracy, conceding only token efficiency. The matched-budget comparison settles it.
- If the ensemble matches us in accuracy and tokens, the contribution reduces to the measurement of joint error rates and the corrected ceiling. We will report it as such.
- Our prediction is that adaptivity wins where checks are expensive (re-derivation, long unit-test runs) and where one Z-like rejection makes further checks wasteful.
Why not just train a better verifier, such as a generative process reward model? GenPRM scales verifier compute itself. That raises a single modality's curve, but the ceiling argument still applies to it. A GenPRM can be added as one more modality in our policy, and we test exactly that.
Proposed Experiments and Decisive Checks
Setup. We run on GSM8K, MATH500, AIME2024 and HumanEval+, using Qwen models from 1.7B to 32B and Llama-3 models as in ROC-n-reroll. We plot accuracy against total tokens from one sample up to thousands of sample-equivalents. Additional reported quantities are false-approval rate at the chosen operating point, tokens to reach fixed accuracy, and the share of budget spent in each phase.
Check 1: the ceiling prediction. For each benchmark we measure the single-modality ceiling and the joint-fooling rate over the modalities used. The theory predicts our curve's plateau should match one minus the joint-fooling mass among wrong leaders. If our plateau sits at the single-modality ceiling despite a measured joint rate well below it, the theory is wrong.
Check 2: GSM8K overthinking. On GSM8K, where Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning finds that more reasoning hurts, the stopping rule should end most queries after one sample and one Z-like check. That should give accuracy no lower than low-effort decoding at a fraction of best-of-N tokens.
Check 3: correlation as the controlled variable. We deliberately correlate modalities, for example by using the same judge model under paraphrased prompts. Gains over single-modality rejection sampling should shrink toward zero as measured error correlation rises. This dose-response curve would be the clearest evidence that independence of verification evidence, rather than raw compute, governs test-time scaling.
References
- ROC-n-reroll: How verifier imperfection affects test-time scaling
- Scaling Test-Time Compute Without Verification or RL is Suboptimal
- Pushing Test-Time Scaling Limits of Deep Search with Asymmetric Verification
- Sequential Transmission Over Binary Asymmetric Channels With Feedback
- Density evolution for asymmetric memoryless channels
- a1: Steep Test-time Scaling Law via Environment Augmented Generation
- Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning
- GenPRM: Scaling Test-Time Compute of Process Reward Models via Generative Reasoning