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

Paper: 2602.17633 Authors: Shayan Kiyani, Sima Noorani, George Pappas, Hamed Hassani Categories: cs.LG, cs.AI, stat.ML

Abstract

This paper addresses a fundamental challenge in LLM-based reasoning systems: how to balance cheap but imperfect verification methods with expensive but reliable ones. The authors formalize the distinction between weak verification (internal checks like self-consistency) and strong verification (external human feedback or rigorous testing). They introduce weak-strong verification policies that optimally decide when to trust weak signals and when to escalate to strong verification. The work proves that optimal policies follow a two-threshold structure and develops an online algorithm that provably controls both false acceptance and false rejection rates without requiring assumptions about the query distribution, model behavior, or verifier characteristics.

Key Contributions

• Formal framework for verification policies: Introduces a mathematical model distinguishing weak verification (fast, scalable, noisy) from strong verification (costly, reliable) with explicit cost-reliability tradeoffs
• Two-threshold optimality: Proves that optimal policies admit a simple two-threshold structure where decisions depend on weak verifier confidence scores
• Calibration and sharpness analysis: Shows that the value of weak verifiers is governed by two key properties—calibration (accuracy of confidence estimates) and sharpness (ability to discriminate between correct and incorrect outputs)
• Online error control algorithm: Develops a provably correct algorithm that maintains user-specified bounds on incorrect acceptance and rejection rates without distributional assumptions

Methodology and Theoretical Framework

The paper models the verification problem as a sequential decision process. For each query, a language model produces an output, and a weak verifier assigns a confidence score. The policy must decide whether to accept, reject, or defer to strong verification based on this score.

The authors define three key metrics:

• Incorrect acceptance rate $\alpha$: frequency of accepting wrong outputs
• Incorrect rejection rate $\beta$: frequency of rejecting correct outputs
• Strong verification frequency $\gamma$: proportion of queries requiring expensive verification

The optimal policy minimizes $\gamma$ subject to constraints $\alpha \leq \alpha_{\text{max}}$ and $\beta \leq \beta_{\text{max}}$. The paper proves this optimal policy takes the form:

where $s$ is the weak verifier’s confidence score and $\tau_{\text{accept}}, \tau_{\text{reject}}$ are learned thresholds.

The theoretical analysis reveals that weak verifier quality depends on:

• Calibration: whether $P(\text{correct} \mid s) \approx s$
• Sharpness: the variance of the score distribution, with sharper (more concentrated) distributions enabling better discrimination

Online Algorithm with Provable Guarantees

A key practical contribution is an online algorithm that adapts thresholds dynamically without knowing the query distribution or verifier properties in advance. The algorithm:

1. Maintains running estimates of acceptance and rejection error rates
2. Adjusts thresholds using a multiplicative update rule when error rates exceed targets
3. Provides theoretical guarantees on long-run error control

The algorithm is distribution-free and model-agnostic, making it applicable across different LLMs, tasks, and weak verification methods. The authors prove that with probability $1-\delta$, the algorithm maintains:

with similar guarantees for rejection errors, where $\epsilon$ depends on $\delta$ and vanishes as more queries are processed.

Implications for LLM Systems

This work has significant implications for deploying LLM reasoning systems in practice:

Cost-quality tradeoffs: The framework provides a principled way to navigate the tension between system cost (strong verification frequency) and output quality (error rates). Organizations can specify acceptable error tolerances and minimize verification costs accordingly.

Verifier design insights: The calibration-sharpness decomposition offers concrete guidance for improving weak verifiers. Self-consistency methods, for instance, may be well-calibrated but lack sharpness, while learned reward models might be sharp but poorly calibrated.

Adaptive deployment: The online algorithm enables systems to adapt to shifting query distributions and model updates without retraining, crucial for production environments where conditions change continuously.

Human-in-the-loop optimization: By formalizing when to request human feedback, the framework helps optimize the use of expensive human verification resources, potentially reducing annotation costs while maintaining quality guarantees.

Takeaways

1. Optimal verification policies follow a simple two-threshold structure, making them practical to implement and interpret in real systems
2. Weak verifier quality decomposes into calibration (accuracy of confidence) and sharpness (discrimination ability), providing actionable targets for improvement
3. Online algorithms can provably control error rates without assumptions about queries, models, or verifiers, enabling robust deployment
4. The framework applies broadly across reasoning tasks, from mathematical problem-solving to code generation to factual question answering
5. Balancing weak and strong verification is essential for scaling LLM systems—pure reliance on either is suboptimal in cost-quality space