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.
Figures & tables
Figure 1: The architecture of weak-strong verification for LLM reasoning.
Figure 2: Empirical Error Rate Convergence. Running-average error rates T1∑t=1Terrt for target levels α=β=0.15 . Left and Center (MATH): Convergence of Type-I and Type-II errors across three difficulty levels in the outcome level verification task. Right (Sudoku): Convergence in the sequential step-by-step reasoning task.
Figure 3: Reasoning Accuracy vs. Verification Cost Tradeoffs. SSV (Algorithm 1 ) (Adaptive: solid colored lines) interpolates between the Strong-Only Oracle (black star) and the Weak-Only baselines (colored circles). Left (MATH): Tradeoff curves for Easy, Medium, and Hard problems; Right (Sudoku): Tradeoff curve for Sudoku step-by-step reasoning task. points are labeled with nominal error targets where α=β .
Method
Accuracy
Strong/Puzzle
Weak/Puzzle
Strong Baseline (Oracle)
44.2%
5.32
–
SSV ( α=β=0.001 )
43.1%
3.31
5.22
SSV ( α=β=0.01 )
43.1%
2.87
5.19
SSV ( α=β=0.03 )
42.7%
2.14
5.20
SSV ( α=β=0.05 )
42.1%
2.06
5.22
SSV ( α=β=0.10 )
39.0%
1.24
5.18
Table 1: Performance Tradeoffs on Sudoku. Detailed comparison across different error regimes.
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Best-of- n (MATH): error convergence for α=β=0.05 .
Figure 5: Best-of- n (MATH): error convergence for α=β=0.10 .
Figure 6: Best-of- n (MATH): error convergence for α=β=0.20 .
Figure 8
Figure 9: Best-of- n (MATH): one-sided sweeps with fixed α and varying β . Reasoning accuracy vs. verification cost (strong-verification usage) for three difficulty subsets (left to right: Levels 2, 3, and 5). Each curve corresponds to a fixed value of α (type-I target), and points along a curve are obtained by sweeping β (type-II target), tracing a family of accuracy–cost tradeoffs.
Figure 10: Best-of- n (MATH): one-sided sweeps with fixed β and varying α . Reasoning accuracy vs. verification cost for three difficulty subsets (left to right: Levels 2, 3, and 5). Each curve corresponds to a fixed value of β (type-II target), and points along a curve are obtained by sweeping α (type-I target). Together with Figure 9 , these plots show how asymmetric error requirements induce different tradeoff frontiers.
Figure 11: Step-by-step (Sudoku): asymmetric accuracy–cost tradeoffs under one-sided sweeps. Decoupling (α,β) produces a family of operating curves rather than a single frontier (cf. the main-text sweeps with α=β ).
Figure 12: Sharpness distributions across MATH difficulty. Histograms of ∣w−0.5∣ : higher mass near 0.5 indicates more decisive weak scores.
Figure 13: Weak-score separation for correct vs. incorrect responses. Score distributions conditioned on g(P,R)=1 vs. g(P,R)=0 ; greater overlap implies weaker discrimination and higher reliance on strong verification.
Figure 14: Weak-score calibration on MATH. Comparing empirical correctness rates to weak scores (perfect calibration lies on the diagonal).
Difficulty
Mean
Median
Std.
Easy (Level 2)
0.467
0.496
0.084
Medium (Level 3)
0.448
0.495
0.100
Hard (Level 5)
0.358
0.342
0.120
Appendix
Table 7: Sharpness of weak verifier scores across MATH difficulty. We report summary statistics of the sharpness metric ∣w−0.5∣ (range [0,0.5] ), where larger values indicate more decisive weak scores.
Difficulty
Base Acc.
AUC
Brier
μcorrect
μincorrect
Separation
Easy (Level 2)
92.2%
0.88
0.089
0.90
0.33
0.57
Medium (Level 3)
82.7%
0.84
0.128
0.86
0.32
0.54
Hard (Level 5)
47.9%
0.74
0.203
0.64
0.26
0.37
Appendix
Table 8: Weak verifier discrimination and calibration diagnostics on MATH. AUC measures discrimination between correct vs. incorrect responses (higher is better). Brier is mean squared error between w and g (lower is better). μcorrect and μincorrect are mean scores conditioned on g=1 and g=0 , and Separation is μcorrect−μincorrect .
As large language models are increasingly deployed for multi-step reasoning, verifying the correctness of their outputs has become essential for maintaining reliability at scale. Verifying the correctness of large language model outputs is often done by querying a costly ground-truth oracle, which is impractical to invoke at every step in an online setting. Prior work addresses this by querying a single weak verifier on every step, and using its score to decide whether the costly strong verifier needs to be queried as well, reserving strong verification for only a small fraction of the steps. However, a single fixed weak verifier may not perform consistently well as the subject matter or difficulty of incoming queries changes over time, and committing to one in advance risks either overly costly or inaccurate verification. We introduce OMVV (Online Multi-Verifier Verification), an algorithm that maintains a pool of K candidate weak verifiers with differing cost and verification performance, and adaptively routes each round's decision to a verifier selected via an online score combiner and an exponential-weights routing policy. OMVV provides a distribution-free, finite-time guarantee on false-accept and false-reject rates across the full pool of verifiers, and further achieves sublinear regret against the best fixed verifier in hindsight under a combined cost and consistency objective. Experiments on reasoning dataset benchmarks show that OMVV achieves higher accuracy at lower verification cost than any single fixed verifier, across a range of operating budgets.
Erfan Hajihashemi, Yanning Shen
Department of Electrical Engineering & Computer Science University of California, Irvine
Large Language Models (LLMs) using chain-of-thought have demonstrated great potential for solving complex reasoning and planning tasks. Despite these advances, LLM-generated outputs remain susceptible to errors, making verification important for reliable reasoning systems. Learned verifiers can increase trust, enforce safety constraints, and ensure alignment with personal preferences, while also providing feedback to improve generation. This raises a central challenge: when learned verifiers are used to guide generation, the feedback loop between generator and verifier may induce a distribution shift. This is particularly salient for process reward models, a prominent class of learned verifiers that score or classify individual steps in a chain-of-thought reasoning trace. Motivated by this challenge, we propose a new online learning framework for chain-of-thought verifiers that, given a problem statement and a reasoning trace, check the correctness of each reasoning step given the preceding steps. Highlighting the asymmetric role of soundness errors (accepting an incorrect reasoning step) and completeness errors (flagging a correct step as wrong), we introduce novel notions of dimension that characterize their optimal tradeoff. We then show how our learned verifiers can boost the accuracy of a weak generator. Assuming that the generator can produce a correct next step with a small success probability, we show how to learn a strong generator with small error and abstention rates. Our results also allow learning from offline data when queries to an expert verifier can be simulated from a small set of correct reasoning traces. However, we establish a separation between our approach and learning from offline expert demonstrations: we show that learning from offline demonstrations cannot in general achieve the soundness-completeness guarantees produced by our interactive learning approach.
When an LLM supplies an argument a user could not produce, how can the user decide whether to accept its claim? Inspired by interactive proofs, we pair a computationally unbounded LLM prover with a resource-bounded human verifier. The verifier checks requested details without seeing the LLM's internals; passed checks accumulate evidence toward an acceptance threshold. Given task-supplied bounds on false passes and human checking errors, we prove anytime-valid soundness against adaptive provers: the probability of ever accepting a false claim is at most a chosen error level. For a true claim, acceptance within the budget has probability at least the product of per-round probabilities that the LLM responds adequately and the human checks correctly, provided the threshold is reachable in time. Each additional check guards against false claims but gives a true claim another chance to fail. Which review lengths meet both error targets depends on the verifier's effort, cognitive load, expertise, and fatigue. With equal resources, we identify conditions under which the bounds certify a review by local checks but not a one-shot check. In LLM-only simulations on GPQA Diamond and Humanity's Last Exam, whether answers accepted without revision were more accurate varied by task and model pair.
Baotong Zhang, Dean Foster, João Sedoc
Stern School of Business, New York University, New York, NY, USA · Amazon, New York, NY, USA