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

arXiv: https://arxiv.org/abs/2602.17633 · HTML: https://mlsanity.com/paper/2602.17633/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 29 of its 35 references that are in the map.
- First posted on arXiv 19 Feb 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 29 of 29)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [G-Eval: NLG Evaluation using GPT-4 with Better Human Alignment](https://mlsanity.com/paper/2303.16634/) (2023)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Generative Verifiers: Reward Modeling as Next-Token Prediction](https://mlsanity.com/paper/2408.15240/) (2024)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Reinforcement Learning for Reasoning in Large Language Models with One Training Example](https://mlsanity.com/paper/2504.20571/) (2025)
- [Consistent Estimators for Learning to Defer to an Expert](https://mlsanity.com/paper/2006.01862/) (2020)
- [ARES: An Automated Evaluation Framework for Retrieval-Augmented Generation Systems](https://mlsanity.com/paper/2311.09476/) (2023)
- [MiniCheck: Efficient Fact-Checking of LLMs on Grounding Documents](https://mlsanity.com/paper/2404.10774/) (2024)
- [Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning](https://mlsanity.com/paper/2405.00451/) (2024)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [Speculative Decoding: Exploiting Speculative Execution for Accelerating Seq2seq Generation](https://mlsanity.com/paper/2203.16487/) (2022)
- [HelpSteer: Multi-attribute Helpfulness Dataset for SteerLM](https://mlsanity.com/paper/2311.09528/) (2023)
- [Fast Best-of-N Decoding via Speculative Rejection](https://mlsanity.com/paper/2410.20290/) (2024)
- [Conformal PID Control for Time Series Prediction](https://mlsanity.com/paper/2307.16895/) (2023)
- [Differentiable Learning Under Triage](https://mlsanity.com/paper/2103.08902/) (2021)
- [Who Should Predict? Exact Algorithms For Learning to Defer to Humans](https://mlsanity.com/paper/2301.06197/) (2023)
- [Calibrated Learning to Defer with One-vs-All Classifiers](https://mlsanity.com/paper/2202.03673/) (2022)
- [Archon: An Architecture Search Framework for Inference-Time Techniques](https://mlsanity.com/paper/2409.15254/) (2024)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [Verdict: A Library for Scaling Judge-Time Compute](https://mlsanity.com/paper/2502.18018/) (2025)

## Built on by (most cited first, 7 of 7)

- [Calibrate-Then-Delegate: Safety Monitoring with Risk and Budget Guarantees via Model Cascades](https://mlsanity.com/paper/2604.14251/) (2026)
- [Uncertainty Propagation in LLM-Based Systems](https://mlsanity.com/paper/2604.23505/) (2026)
- [Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification](https://mlsanity.com/paper/2605.17609/) (2026)
- [Conformal Risk-Averse Decision Making with Action Conditional Guarantee](https://mlsanity.com/paper/2606.05551/) (2026)
- [Strategic Decision Support for AI Agents](https://mlsanity.com/paper/2606.12587/) (2026)
- [More Rejective, Not More Discriminative: The Unit of Verification in Pre-Execution LLM Oversight](https://mlsanity.com/paper/2608.23941/) (2026)
- [Online Verification of Language Model Responses Under Cost Constraints](https://mlsanity.com/paper/2610.02632/) (2026)

## Abstract (arXiv)

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.