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

Source: arXiv - 2602.17633v1

Overview

Large language models (LLMs) are increasingly deployed inside verification loops that decide whether a model’s answer can be trusted. This paper formalizes the trade‑off between cheap, internal checks (e.g., self‑consistency, proxy rewards) and expensive, external validation (human feedback, gold‑standard tests). By treating these as weak and strong verification signals, the authors derive optimal policies for when to rely on the cheap check and when to fall back to the costly one, offering a principled way to balance speed, cost, and reliability.

Key Contributions

• Formal framework for weak–strong verification policies that jointly manage acceptance, rejection, and deferral decisions.
• Two‑threshold optimal policy: provably optimal policies reduce to a simple rule based on lower and upper confidence thresholds on the weak verifier’s score.
• Metrics for quantifying incorrect acceptance, incorrect rejection, and the frequency of strong verification calls.
• Theoretical analysis showing that the weak verifier’s calibration (how well its scores reflect true probabilities) and sharpness (confidence spread) dictate its usefulness.
• Online algorithm that adapts thresholds on the fly, guaranteeing bounded acceptance/rejection errors without any assumptions on the query distribution, the underlying LLM, or the weak verifier.
• Empirical validation on synthetic and real‑world LLM reasoning tasks, demonstrating substantial reductions in strong‑verification cost while keeping error rates under control.

Methodology

1. Problem Setup

   • Each query (x) yields a model answer and a weak verification score (s(x)\in[0,1]) (e.g., self‑consistency probability).
   • A strong verifier can definitively label the answer as correct or incorrect but incurs a high cost (c_s).
   • The system must decide: accept, reject, or defer to the strong verifier.

2. Policy Design

   • Define two thresholds (\tau_{\text{low}}) and (\tau_{\text{high}}).
   • If (s(x) \le \tau_{\text{low}}) → reject; if (s(x) \ge \tau_{\text{high}}) → accept; otherwise → invoke strong verification.
   • The thresholds are chosen to minimize expected strong‑verification usage while respecting user‑specified error budgets for false acceptance ((\alpha)) and false rejection ((\beta)).

3. Metrics & Objectives

   • Incorrect Acceptance Rate (IAR): probability of accepting a wrong answer.
   • Incorrect Rejection Rate (IRR): probability of rejecting a correct answer.
   • Strong‑Verification Frequency (SVF): proportion of queries sent to the expensive verifier.

4. Theoretical Guarantees

   • Prove that any optimal policy under the above constraints must be of the two‑threshold form.
   • Show that the calibration of (s) (i.e., (\Pr[\text{correct}\mid s]=s)) and its sharpness (variance of (s) across queries) determine how low SVF can be for a given (\alpha,\beta).

5. Online Adaptive Algorithm

   • Initialize thresholds conservatively.
   • As queries arrive, update empirical estimates of IAR and IRR using observed strong‑verification outcomes.
   • Adjust (\tau_{\text{low}}) and (\tau_{\text{high}}) to keep the error rates within the target budgets, while shrinking SVF over time.
   • No assumptions are made about the distribution of queries or the internal workings of the LLM/weak verifier.

6. Experiments

   • Synthetic data where ground‑truth correctness is known, allowing precise measurement of calibration effects.
   • Real LLM reasoning benchmarks (e.g., math word problems, commonsense QA) using self‑consistency as the weak verifier and human evaluation as the strong verifier.

Results & Findings

• Two‑threshold policies consistently hit the error budgets while cutting strong‑verification calls by ~30‑40 % compared to a naïve “always verify” baseline.
• Calibration matters: when the weak verifier’s scores are well‑aligned with true correctness, the algorithm can push thresholds outward, further reducing SVF.
• The online algorithm quickly converges (within a few hundred queries) to near‑optimal thresholds, even when the underlying LLM or query distribution drifts.

Practical Implications

• Cost‑Effective LLM Services: SaaS platforms can embed a cheap self‑consistency check and only invoke human review or expensive oracle calls when confidence falls in an ambiguous band, dramatically lowering operational expenses.
• Real‑Time Assistants: Voice assistants or IDE code‑completion tools can provide instant answers most of the time, falling back to a slower but reliable verification step only when needed, preserving user experience.
• Safety‑Critical Systems: In domains like medical advice or financial analysis, the framework offers a principled way to guarantee upper bounds on harmful errors while keeping human‑in‑the‑loop interventions manageable.
• Model‑Agnostic Deployment: Because the algorithm does not rely on any specific LLM architecture, it can be dropped into pipelines that already use any weak verifier (e.g., entropy, ensemble disagreement, proxy reward models).

Limitations & Future Work

• Dependence on Calibration: The approach assumes the weak verifier can be calibrated (or re‑calibrated) post‑hoc; poorly calibrated scores can inflate SVF or breach error budgets.
• Binary Correctness Model: The current formulation treats outputs as simply correct/incorrect, ignoring graded quality or partial credit, which is common in open‑ended generation tasks.
• User‑Defined Error Budgets: Selecting appropriate (\alpha) and (\beta) values may be non‑trivial for practitioners unfamiliar with the downstream risk profile.
• Scalability of Strong Verification: While the algorithm reduces the frequency of strong checks, the absolute cost may still be prohibitive for massive query streams; integrating cheaper surrogate strong verifiers (e.g., specialized classifiers) is an open direction.
• Dynamic Environments: Future work could extend the theory to handle non‑stationary query distributions more explicitly, perhaps via change‑point detection or meta‑learning of thresholds.

Bottom line: By treating cheap internal checks as weak verification and formalizing when to defer to costly external validation, this work gives developers a mathematically grounded, easy‑to‑implement recipe for building LLM‑powered systems that are both fast and trustworthy.

Authors

• Shayan Kiyani
• Sima Noorani
• George Pappas
• Hamed Hassani

Paper Information

• arXiv ID: 2602.17633v1
• Categories: cs.LG, cs.AI, stat.ML
• Published: February 19, 2026
• PDF: Download PDF