When to Trust the Cheap Check: Weak and Strong Verification for Reasoning

Shayan Kiyani; Sima Noorani; George Pappas; Hamed Hassani

cs.LGFeb 19, 2026

When to Trust the Cheap Check: Weak and Strong Verification for Reasoning

Authors: Shayan Kiyani, Sima Noorani, George Pappas, Hamed Hassani

Organizations: University of Pennsylvania

Abstract

Reasoning with LLMs increasingly unfolds inside a broader verification loop. Internally, systems use cheap checks, such as self-consistency or proxy rewards, which we call weak verification. Externally, users inspect outputs and steer the model through feedback until results are trustworthy, which we call strong verification. These signals differ sharply in cost and reliability: strong verification can establish trust but is resource-intensive, while weak verification is fast and scalable but noisy and imperfect. We formalize this tension through weak--strong verification policies, which decide when to accept or reject based on weak verification and when to defer to strong verification. We introduce metrics capturing incorrect acceptance, incorrect rejection, and strong-verification frequency. Over population, we show that optimal policies admit a two-threshold structure and that calibration and sharpness govern the value of weak verifiers. Building on this, we develop an online algorithm that provably controls acceptance and rejection errors without assumptions on the query stream, the language model, or the weak verifier.

Figures & tables

Figure 1: The architecture of weak-strong verification for LLM reasoning.

Panel of Figure 2 — Figure 2: Empirical Error Rate Convergence. Running-average error rates $\frac{1}{T}\sum_{t=1}^{T}\mathrm{err}_{t}$ for target levels $\alpha=\beta=0.15$ . Left and Center (MATH): Convergence of Type-I and Type-II errors across three difficulty levels in the outcome level verification task. Right (Sudoku): Convergence in the sequential step-by-step reasoning task.

Panel of Figure 3 — Figure 3: Reasoning Accuracy vs. Verification Cost Tradeoffs. SSV (Algorithm 1 ) (Adaptive: solid colored lines) interpolates between the Strong-Only Oracle (black star) and the Weak-Only baselines (colored circles). Left (MATH): Tradeoff curves for Easy, Medium, and Hard problems; Right (Sudoku): Tradeoff curve for Sudoku step-by-step reasoning task. points are labeled with nominal error targets where $\alpha=\beta$ .

Method	Accuracy	Strong/Puzzle	Weak/Puzzle
Strong Baseline (Oracle)	44.2%	5.32	–
SSV ( $\alpha=\beta=0.001$ )	43.1%	3.31	5.22
SSV ( $\alpha=\beta=0.01$ )	43.1%	2.87	5.19
SSV ( $\alpha=\beta=0.03$ )	42.7%	2.14	5.20
SSV ( $\alpha=\beta=0.05$ )	42.1%	2.06	5.22
SSV ( $\alpha=\beta=0.10$ )	39.0%	1.24	5.18

Table 1: Performance Tradeoffs on Sudoku. Detailed comparison across different error regimes.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: Best-of- $n$ (MATH): error convergence for $\alpha=\beta=0.05$ .

Panel of Figure 5 — Figure 5: Best-of- $n$ (MATH): error convergence for $\alpha=\beta=0.10$ .

Panel of Figure 6 — Figure 6: Best-of- $n$ (MATH): error convergence for $\alpha=\beta=0.20$ .

Panel of Figure 9 — Figure 9: Best-of- $n$ (MATH): one-sided sweeps with fixed $\alpha$ and varying $\beta$ . Reasoning accuracy vs. verification cost (strong-verification usage) for three difficulty subsets (left to right: Levels 2, 3, and 5). Each curve corresponds to a fixed value of $\alpha$ (type-I target), and points along a curve are obtained by sweeping $\beta$ (type-II target), tracing a family of accuracy–cost tradeoffs.

Panel of Figure 10 — Figure 10: Best-of- $n$ (MATH): one-sided sweeps with fixed $\beta$ and varying $\alpha$ . Reasoning accuracy vs. verification cost for three difficulty subsets (left to right: Levels 2, 3, and 5). Each curve corresponds to a fixed value of $\beta$ (type-II target), and points along a curve are obtained by sweeping $\alpha$ (type-I target). Together with Figure 9 , these plots show how asymmetric error requirements induce different tradeoff frontiers.

Panel of Figure 11 — Figure 11: Step-by-step (Sudoku): asymmetric accuracy–cost tradeoffs under one-sided sweeps. Decoupling $(\alpha,\beta)$ produces a family of operating curves rather than a single frontier (cf. the main-text sweeps with $\alpha=\beta$ ).

Figure 12: Sharpness distributions across MATH difficulty. Histograms of $|w-0.5|$ : higher mass near $0.5$ indicates more decisive weak scores.

Figure 13: Weak-score separation for correct vs. incorrect responses. Score distributions conditioned on $g(P,R)=1$ vs. $g(P,R)=0$ ; greater overlap implies weaker discrimination and higher reliance on strong verification.

Figure 14: Weak-score calibration on MATH. Comparing empirical correctness rates to weak scores (perfect calibration lies on the diagonal).

Difficulty	Mean	Median	Std.
Easy (Level 2)	0.467	0.496	0.084
Medium (Level 3)	0.448	0.495	0.100
Hard (Level 5)	0.358	0.342	0.120

Appendix

Table 7: Sharpness of weak verifier scores across MATH difficulty. We report summary statistics of the sharpness metric

|w-0.5|

(range

[0,0.5]

), where larger values indicate more decisive weak scores.

Difficulty	Base Acc.	AUC	Brier	$\mu_{\text{correct}}$	$\mu_{\text{incorrect}}$	Separation
Easy (Level 2)	92.2%	0.88	0.089	0.90	0.33	0.57
Medium (Level 3)	82.7%	0.84	0.128	0.86	0.32	0.54
Hard (Level 5)	47.9%	0.74	0.203	0.64	0.26	0.37

Appendix

Table 8: Weak verifier discrimination and calibration diagnostics on MATH. AUC measures discrimination between correct vs. incorrect responses (higher is better). Brier is mean squared error between

w

and

g

(lower is better).

\mu_{\text{correct}}

and

\mu_{\text{incorrect}}

are mean scores conditioned on

g=1

and

g=0

, and Separation is

\mu_{\text{correct}}-\mu_{\text{incorrect}}

LLM Answer Verification

Large language model answer verification checks whether generated answers are correct, supported by evidence, and safe to accept.

See all 148 papers

Online Verification of Language Model Responses Under Cost Constraints
Oct 2, 2026Erfan Hajihashemi, Yanning ShenLLM Reliability Online Learning
Department of Electrical Engineering & Computer Science University of California, Irvine
Verify to Amplify: Improving Reasoning via Learned Chain-of-Thought Verification
Mar 3, 2026Maria-Florina Balcan, Avrim Blum, Kiriaki Fragkia +2LLM Evaluation LLM Answer Verification
Carnegie Mellon University · Toyota Technological Institute at Chicago · Northwestern University
Human-LLM Deliberation as Interactive Proof: Conditions for Verifiability Without Transparency
Sep 21, 2026Baotong Zhang, Dean Foster, João SedocLLM Answer Verification Anytime-Valid Inference
Stern School of Business, New York University, New York, NY, USA · Amazon, New York, NY, USA

Oct 2, 2026J/K move · Enter open · S save

Online Verification of Language Model Responses Under Cost Constraints

Erfan Hajihashemi, Yanning Shen

Department of Electrical Engineering & Computer Science University of California, Irvine

LLM Reliability Online Learning

Open paper AskPDF arXiv

As large language models are increasingly deployed for multi-step reasoning, verifying the correctness of their outputs has become essential for maintaining reliability at scale. Verifying the correctness of large language model outputs is often done by querying a costly ground-truth oracle, which is impractical to invoke at every step in an online setting. Prior work addresses this by querying a single weak verifier on every step, and using its score to decide whether the costly strong verifier needs to be queried as well, reserving strong verification for only a small fraction of the steps. However, a single fixed weak verifier may not perform consistently well as the subject matter or difficulty of incoming queries changes over time, and committing to one in advance risks either overly costly or inaccurate verification. We introduce OMVV (Online Multi-Verifier Verification), an algorithm that maintains a pool of

K

candidate weak verifiers with differing cost and verification performance, and adaptively routes each round's decision to a verifier selected via an online score combiner and an exponential-weights routing policy. OMVV provides a distribution-free, finite-time guarantee on false-accept and false-reject rates across the full pool of verifiers, and further achieves sublinear regret against the best fixed verifier in hindsight under a combined cost and consistency objective. Experiments on reasoning dataset benchmarks show that OMVV achieves higher accuracy at lower verification cost than any single fixed verifier, across a range of operating budgets.

Abstract

LLM Answer Verification

Explore similar work

Online Verification of Language Model Responses Under Cost Constraints

Verify to Amplify: Improving Reasoning via Learned Chain-of-Thought Verification

Human-LLM Deliberation as Interactive Proof: Conditions for Verifiability Without Transparency