Research map / Large language models / Reasoning and chain of thought

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

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Efficient and adaptive thinking · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formalizes weak (cheap proxy) vs strong (costly user) verification as accept/reject/defer policies, shows a two-threshold optimal structure under calibration, and gives an online distribution-free algorithm (SSV) that controls type-I/II errors while reducing strong-verification calls.

Problem

Reasoning systems rely on cheap weak verifiers (self-consistency, proxy rewards) that are noisy, while strong verification (human or domain execution) is costly; there is no principled way to decide when to trust the weak check and when to defer to strong verification while controlling incorrect acc

Approach

Weak-strong verification policies map weak scores to accept, reject, or query-strong actions; population analysis gives a two-threshold optimal policy governed by calibration and sharpness, and an online importance-weighted threshold-tracking algorithm (SSV) with exploration queries in decisive regions yields finite-sample, distribution-free type-I/II error control.

Key results

• On Sudoku, SSV at alpha=beta=0.01 reaches 43.1% accuracy with 2.87 strong calls per puzzle versus 44.2% and 5.32 calls for the strong-only oracle (about 46% fewer strong calls).
• Running-average type-I and type-II errors stabilize near the nominal target alpha=beta=0.15 on MATH and Sudoku.
• On MATH level 5, SSV reaches 60% accuracy with 2 strong calls per problem versus the oracle's 63.5% with 2.8 calls.

Limitations

• Guarantees are marginal over rounds; the strong-verification decision depends only on the weak score, not on the prompt-response context.
• Exploration probabilities add strong-verification cost and must be tuned.
• Population analysis assumes calibration of the weak verifier, which SSV does not rely on.

Experimental setup

Datasets: MATH Sudoku puzzles

Benchmarks: MATH Sudoku

Metrics: type-I error type-II error strong verification frequency accuracy

Baselines: Strong-Only (Oracle) Weak-Only (Greedy) best-of-n

Builds on: online conformal prediction learning to defer outcome reward modeling process reward modeling

Closest papers by meaning

• Measuring Weak-to-Strong Legibility of Reasoning Models (NeurIPS 2026 · similarity 0.88)
• Variation in Verification: Understanding Verification Dynamics in Large Language Models (ICLR 2026 · similarity 0.87)
• Incentivizing LLMs to Self-Verify Their Answers (NeurIPS 2025 · similarity 0.85)
• V1: Unifying Generation and Self-Verification for Parallel Reasoners (ICML 2026 · similarity 0.85)
• APOLLO: Automated LLM and Lean Collaboration for Advanced Formal Reasoning (NeurIPS 2025 · similarity 0.85)
• THE PATH OF LEAST RESISTANCE: GUIDING LLM REASONING TRAJECTORIES WITH PREFIX CONSENSUS (ICLR 2026 · similarity 0.85)