When to Trust the Cheap Check: Weak and Strong Verification for Reasoning
Shayan Kiyani, Sima Noorani, George Pappas, Hamed Hassani
cs.LG, cs.AI, stat.ML
2026-02-20
SSV uses two adaptive thresholds on cheap scores to accept, reject, or escalate. On Sudoku: 43.1% vs 44.2% oracle accuracy, 2.87 vs 5.32 strong calls per puzzle.
Reasoning stacks already run two kinds of checks. Cheap ones scale: self-consistency, proxy rewards, LLM-as-judge scores, local tool checks. The paper calls these weak verification. Expensive ones establish trust: a human reading line by line, a domain oracle, or a stronger model scored against ground truth. That is strong verification. Cheap checks are noisy. Strong checks do not scale.
Most recent work either treats the cheap signal as fixed and searches harder (sampling, trees, longer chains), or trains a better cheap signal (process reward models, judge-time scaling). The missing layer is the dispatcher: given a weak score, when is it safe to accept or reject, and when must the expensive check run? This paper, from the University of Pennsylvania, formalizes that dispatcher as a weak-strong verification policy and gives an online algorithm, Selective Strong Verification (SSV).
The design question is blunt. If strong verification ran on every step, how close can you get while calling it only on a small, chosen fraction of steps?
A language model produces a response R. A weak verifier scores it with w in [0, 1]. A strong verifier returns a binary label g. A policy maps w to one of three actions: accept without asking the strong verifier (A), reject without asking (R), or query the strong verifier (SV) and follow g. The query stream can be full solutions (outcome-level, ORM-style) or single reasoning steps (process-level, PRM-style), and may depend arbitrarily on past decisions. No distributional assumption is placed on how prompts arrive.
Three metrics. Type-I is the rate of incorrect accepts among rounds where g=0. Type-II is the rate of incorrect rejects among rounds where g=1. SV frequency is how often the expensive check is called. Quality vs cost, with a hard tradeoff: small Type-I and Type-II usually force more SV calls.
Under a population model, if the weak score is calibrated (when w=p, the chance g=1 is p), an optimal policy uses two thresholds. Reject when w is low, accept when w is high, call SV in the band between. Two properties of the weak verifier then decide how cheap this can be. Calibration makes the score readable as a probability. Sharpness, how often scores sit near 0 or 1, decides whether accept/reject is actually cheap. A verifier that always emits the marginal accuracy is perfectly calibrated and useless; the policy has to call SV almost always.
In the sequential setting those population assumptions drop. SSV keeps two adaptive thresholds τR ≤ τA:
Thresholds update only on rounds where g is observed, with importance weights for the random probes. The probes are required. If the high-score region never reveals g, a Type-I blow-up is invisible. Theorem 5.1 gives distribution-free, uniform-in-time bounds: Type-I ≤ α plus slack, Type-II ≤ β plus slack. The slack depends on sample size, step size η, and the minimum probe rate qmin, in the same family as online conformal and quantile tracking.
The setup is a cousin of selective prediction and learning-to-defer, with deferral meaning "call the strong verifier." The extra pieces are online operation, partial feedback, and separate Type-I/II knobs.
Two tasks. MATH is outcome-level: GPT-4o-mini writes a full solution, DeepSeek-Chat scores it, GPT-4o checks answer equivalence against the gold label. Difficulty levels 2, 3, and 5. Sudoku is process-level: 4×4 mini boards, one cell at a time, same generator and weak verifier, but the strong check is a deterministic lookup against the unique solution. Baselines sit at the two extremes: Strong-Only (oracle, every step) and Weak-Only (greedy best-of-n on the weak score).
Error control holds. With targets α=β=0.15, running-average Type-I and Type-II sit on the target for both MATH and Sudoku. The appendix repeats this at 0.05, 0.10, and 0.20; on MATH Level 5 with α=β=0.05 the final Err A/R is 0.047/0.047.
Accuracy vs cost:
| Method | Accuracy | Strong calls | Weak calls |
| Sudoku Oracle | 44.2% | 5.32 / puzzle | n/a |
| SSV α=β=0.01 | 43.1% | 2.87 | 5.19 |
| SSV α=β=0.10 | 39.0% | 1.24 | 5.18 |
| Sudoku Weak-Only | 33.6% | 0 | 6.00 |
| MATH L5 Oracle | 63.5% | 2.8 / problem | n/a |
| MATH L5 SSV | 60% | 2.0 | n/a |
On Sudoku, α=β=0.01 loses 1.1 points of accuracy and cuts strong calls by 46%. On the hardest MATH split the curve is closer to linear: 2.0 calls for 60%, versus 2.8 calls for 63.5%. Appendix Table 8 explains the shape. Easy MATH has AUC 0.88 and a 0.57 gap between mean scores on correct vs incorrect answers. Hard drops to AUC 0.74 and a 0.37 gap. Mean sharpness |w-0.5| falls from 0.467 (Easy) to 0.358 (Hard). Steep Pareto when the cheap signal is decisive; pay roughly in proportion when it is not.
Sudoku also uses fewer weak calls than Weak-Only: 4.8 to 5.2 per puzzle against 6.00. The thresholds accept early or escalate early, skipping extra cheap scoring rounds that would not have changed the decision.
Production reasoning stacks already live between two bad defaults: trust the LLM-as-judge and leak errors, or call GPT-4o / a human on every step and burn budget. SSV turns that threshold into two knobs, α and β, with a finite-sample guarantee that does not need assumptions on the query stream, the language model, or the weak verifier.
The useful setting is any pipeline with a cheap score and occasional access to a gold check: best-of-n math, step-level PRMs, tool-checked code. Gains are largest when the weak signal is sharp. On Sudoku that is almost half the expensive calls for a 1.1-point drop. When the weak signal is mushy, SSV does not invent information; it spends more on the strong verifier.
This is a dispatcher, not a better verifier. A bad cheap check stays a bad cheap check. The painful part of deployment is often this layer: which steps are worth the expensive call.
The paper's own caveat: the policy looks only at w, not at the rest of (P, R). Error control is therefore marginal, averaged over rounds, not conditional on problem type. Context-dependent thresholds are left for later.
On MATH the "strong" verifier is GPT-4o doing answer equivalence, so the gold path still goes through another LLM. Sudoku is 4×4, not 9×9, and even the oracle only reaches 44.2% accuracy; the generator is the bottleneck. What SSV saves is verification count, not solving skill. The only baselines are Weak-Only and Strong-Only. No comparison with other learning-to-defer or conformal methods. Probe rates qA and qR themselves cost extra strong calls, and the paper does not offer a default schedule.
The guarantee bounds disagreement with the strong verifier on rounds where g is 0 or 1, not the end-to-end accuracy a user sees. Final accuracy still depends on the generator, the sampling budget n, and whether a rejection triggers another sample.