When we ask whether a verifier (a model or signal that scores a reasoning trace and predicts whether its answer is correct) really detects correctness, the honest answer is often "we can't tell." Hard problems produce both wrong answers and unusual traces, such as long ones with high uncertainty. A verifier can score well simply by recognizing hard problems. The cleanest current fix compares correct and incorrect solutions to the same problem and calibrates the result against a label-shuffling baseline. That fix works, but it keeps only problems where the model sometimes succeeds and sometimes fails. In practice that leaves about 64 problems per model and drops the easy and hard extremes entirely.
We propose to borrow the logic of the epidemiologist's matched case-control study and pair it with a permutation test. Correct traces are the "cases" and incorrect traces the "controls." Each case is matched to controls from other problems that have similar difficulty (measured independently of the traces being scored) and similar length. We then test whether the verifier separates cases from controls by shuffling the correct/incorrect labels only within each matched set. Before shuffling, we subtract a held-out prediction of the verifier score from difficulty and length. The test therefore remains approximately valid if the matching is loose but that prediction is good, and it is exact if the matching is exact. The result is a confounder-controlled significance test for verifiers that uses most of the benchmark instead of a thin middle slice.
Core Claim
Restricting permutations to matched sets built on continuous confounders gives a test of "verifier score carries information about correctness beyond difficulty and length." We expect this test to have three properties. First, it should hold nominal Type I error when the score is a pure function of the confounders. Second, it should agree with the within-problem protocol on the problems where that protocol applies. Third, it should retain several times more problems, which gives tighter confidence intervals and covers the difficulty extremes that within-problem matching cannot reach. The new ingredients are matched sets formed across problems on continuous covariates, together with a residualization step that protects validity when matches are imperfect. Neither appears in the closest prior work.
Where This Sits
The motivating evidence comes from Token-Level Verification under Controlled Evaluation. That paper evaluates entropy and log-probability verifiers on MATH and BigMath. It shows that pooling across problems inflates AUROC by 0.04 to 0.18, and that final-token entropy drops to 0.47–0.48 under fixed-direction scoring. Its remedy is exact matching on problem identity plus a within-problem permutation null. We keep the permutation null but replace exact problem matching with covariate matching across problems. That change directly targets the paper's own stated limitation, the reduction to roughly 64 problems.
Two papers supply the method we generalize. A Permutation Approach to Assess Confounding in Machine Learning Applications for Digital Health permutes labels only within discrete confounder strata. On the mPower Parkinson's data it shows that observed AUCs above 0.81 shrink to an unconfounded estimate of about 0.66. It also finds that matching removes confounding (p > 0.51) where logistic propensity weighting fails (p < 10⁻¹⁶). Its strata must be categorical, so continuous confounders like difficulty must be binned, and we remove that requirement. The conditional permutation test handles continuous confounders by permuting non-uniformly according to an estimated conditional density, sampled with a pairwise MCMC procedure. It stays near 5% Type I error where the conditional randomization test inflates to 15–30%. We avoid both the density model and the MCMC by conditioning on the outcome through matching, as a case-control design does. In return we must control matching quality, which the conditional permutation test does not need to do.
The case-control precedent in computational social science is Causal Factors of Effective Psychosocial Outcomes in Online Mental Health Communities. It matches improving and non-improving users with k-means clustering and reports parametric effect sizes. It provides neither a balance guarantee nor finite-sample inference, and our design addresses both gaps. When LLMs get significantly worse shows the payoff of paired designs for LLM evaluation: unpaired tests overstate uncertainty about 2.2×. Its pairs are the same prompt under two models, so it never confronts confounding between prompts. That cross-prompt confounding is exactly the problem we address.
Research Program
The null hypothesis is that the verifier score $S$ is independent of correctness $Y$ given confounders $Z$. Here $Z$ is problem difficulty plus trace length and step count. Difficulty is never computed from the traces under test. We use solve rates from a separate reference model, which is how BigMath is already stratified using Llama-3.1-8B, or from held-out rollouts that are cross-fitted (computed on a different split of the data than the one being tested).
Matching. We form 1:k matched sets, each containing one correct trace and k incorrect traces, using optimal matching on a scaled distance in $Z$ with a caliper (a maximum allowed distance). Traces from the same problem are allowed in a matched set but are not required.
Residualization. On a held-out split we fit a flexible regressor $\hat{m}(Z)$ of $S$ on $Z$. The test then uses residuals $R = S - \hat{m}(Z)$.
Test statistic. The statistic is the average, over matched sets, of the case residual minus the mean control residual:
$$T = \frac{1}{M}\sum_{j=1}^{M}\Big(R_{j,\text{case}} - \tfrac{1}{k}\textstyle\sum_{c} R_{j,c}\Big).$$
Here $M$ is the number of matched sets and $R_{j,c}$ is the residual of control $c$ in set $j$. The null distribution comes from reassigning, uniformly within each set, which member is labeled the case.
Why this should be valid. When matching is exact, the members of a set are exchangeable under the null and the test is exact. When matching is approximate, any leftover bias enters only through how much $S - \hat{m}(Z)$ still varies with $Z$ inside a set. That product structure makes validity hinge on whichever of the two is good: tight matching or an accurate $\hat{m}$.
Diagnostics and outputs. We will characterize empirically, and bound where possible, how Type I error grows with the caliper. We will report standardized covariate imbalance after matching as a mandatory diagnostic. We will report a matched AUROC and its permutation interval as the effect size.
Baselines
The naive reference point is global-pooled AUROC with an unrestricted label shuffle. Token-Level Verification under Controlled Evaluation reports that it inflates AUROC by 0.04–0.18. We expect it to reject on our pure-confounder null scores, and it serves to show the problem exists in our rollouts. It runs on the identical set of traces.
The strongest existing method is that paper's within-problem leave-one-out protocol with its within-problem permutation null. On the problems it retains, controlled shallow token methods fall in 0.60–0.75 AUROC and P(True) reaches up to 0.91. The paper does not report Type I error rates for its permutation null, and we found no other reported result on Lacuna for that quantity. We run it on the same rollouts, models, and verifier scores. Our method beats it if two things hold: at matched or better Type I error it retains substantially more problems (target: at least 3× the retained problems), and its AUROC intervals are narrower. On the overlap of problems both methods can use, the two estimates must agree within their intervals. A large disagreement would mean our matching has introduced bias.
Binned restricted permutation follows A Permutation Approach to Assess Confounding. We bin difficulty and length into quantiles and shuffle within bins, sweeping the bin count with the same tuning budget we give our caliper.
The conditional permutation test follows The conditional permutation test. It is applied with the verifier score as $X$, correctness as $Y$, and the same $Z$, using a Gaussian location model for $q(S \mid Z)$ and an equal number of null draws.
Ablations isolate our ingredients. The first removes residualization, keeping matching only. The second removes matching, keeping residualization only, so it is effectively a global shuffle of residuals. The third matches on difficulty alone, without length.
Why not just…?
Why not just regress correctness on the verifier score plus difficulty and length, and read off the coefficient's p-value? This is the cheapest competitor and we include it. Its validity depends on the logistic functional form being right. The digital health paper's failure of logistic propensity weighting (p < 10⁻¹⁶ residual confounding) and the 15–30% Type I error of misspecified models in the conditional permutation test paper both suggest that form fails exactly when difficulty acts nonlinearly. Our semi-synthetic null, in which the score is a nonlinear function of difficulty, will show directly whether regression holds 5% error. If it does, the regression is a fine answer and we will say so.
Why not just sample more rollouts per problem so within-problem matching keeps more problems? This is the real threat. With many rollouts, mid-difficulty problems become mixed and usable. Very easy and very hard problems stay all-correct or all-wrong, however, so the within-problem estimate describes verifier quality only in the middle of the difficulty range. We will run an equal-compute comparison: within-problem matching with k× more rollouts against our method with the original budget. We will compare the number of retained problems, interval width, and difficulty coverage. If more rollouts match our precision at equal cost, our contribution narrows to covering the extremes, and we will report it that way.
Why not just bin the confounders and use the existing restricted permutation test? Binning is our ablation. With few bins, the remaining within-bin difficulty gradient should leak into the test and inflate Type I error. With many bins, strata contain only correct or only incorrect traces and the test loses power. The bin-count sweep on the semi-synthetic null will show whether any bin count matches matched sets on both error and power.
Proposed Experiments
We generate rollouts from Llama-3.1-8B and Qwen2.5-Coder-7B on MATH and BigMath, the models and benchmarks used in Token-Level Verification under Controlled Evaluation. We score them with final-token entropy, mean log-probability, P(True), and one generative reward model trained with the RM-R1 codebase.
The first decisive check is validity. We construct "verifiers" whose scores are fixed nonlinear functions of reference difficulty and length plus noise. Such scores carry no information about correctness beyond the confounders. Over many resampled benchmark subsets, every method's rejection rate at 5% must stay near 5%. We also track rejection rate as a function of caliper width, and with and without residualization.
The second check is power. We inject a known correctness-dependent shift into those scores and trace power curves against effect size.
The third check is agreement and gain on real verifiers. We compare matched AUROC with the within-problem estimate on overlapping problems, and we report retained problems, interval widths, and verdicts for each verifier. A particular question is whether entropy's near-chance fixed-direction result also holds at the difficulty extremes that within-problem matching cannot see.
The fourth check is the equal-compute rollout comparison described above.
As a short transfer test, we apply the same design to length confounding in RewardBench chosen/rejected pairs, using cross-pair length matching. The goal is to see whether the test flags the length dependence that Post-hoc Reward Calibration corrects. That paper reports an average gain of 3.11 points across 33 reward models.
The proposal fails if residualized matching cannot hold nominal error at calipers loose enough to retain many more problems than the within-problem protocol.
References
- Token-Level Verification under Controlled Evaluation: Protocol Sensitivity Shapes Apparent Performance
- A Permutation Approach to Assess Confounding in Machine Learning Applications for Digital Health
- The conditional permutation test
- Causal Factors of Effective Psychosocial Outcomes in Online Mental Health Communities
- When LLMs get significantly worse: A statistical approach to detect model degradations
- Post-hoc Reward Calibration: A Case Study on Length Bias