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

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. Experiments on mathematical reasoning and sequential decision-making demonstrate that our algorithm achieves reliability comparable to exhaustive strong verification while significantly reducing verification cost.

Large language models increasingly solve problems by reasoning step by step, but how do we know when to trust their reasoning process? In practice, systems lean on cheap automatic checks, like using another model to score the work, which are fast but unreliable. Truly dependable checking, such as expert review or testing an answer in the real world, is trustworthy but slow and expensive. We asked: can we get the reliability of always checking carefully while paying for it only rarely? We developed a method that watches how confident the cheap check is and decides, on the fly, whether to accept an answer, reject it, or escalate to the expensive check. It comes with a mathematical guarantee: it keeps the two spectrum of costly mistakes, approving wrong answers and throwing away correct ones, below limits the user chooses, without assuming anything about the problems, the model, or how good the cheap check is. On various reasoning tasks, including math problems and Sudoku puzzles, our method matched the reliability of checking everything carefully while calling the expensive checker far less often, roughly halving its use on Sudoku. This gives developers a principled dial to balance trustworthiness against cost.