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.
Figures & tables
Figure 1: Mean probability that OMVV routes to the cheaper verifier (Qwen2-1.5B), by difficulty. On easy problems, OMVV favors the cheaper verifier with substantially higher probability than on hard problems, where it shifts toward the more expensive verifier.
Dataset
Method
Accuracy
ErrI
ErrII
Avg
Oracle freq
Cost
MATH
Qwen2-1.5B
0.6775
0.7655
0.0845
0.425
0.2713
0.3713
Qwen2.5-3B
0.6975
0.5848
0.0807
0.333
0.1425
0.3425
OMVV
0.7325
0.1649
0.1919
0.178
0.1952
0.3080
Zebra Logic
Qwen2-1.5B
0.7500
0.5562
0.1617
0.359
0.2718
0.3718
Qwen2.5-3B
0.7250
0.8361
0.0221
0.429
0.1962
0.3962
OMVV
0.8550
0.1844
0.1982
0.191
0.2461
0.3659
Table 1: OMVV versus single-verifier baselines, pooled easy and hard subsets, at αI=αII=0.2 . ErrI and ErrII values exceeding the 0.2 target are shown in red; the best value in each of Accuracy, Avg( ErrI , ErrII ), Cost, and Oracle frequency, within each dataset, is bolded.
B
Method
Accuracy
ErrI
ErrII
Avg
Oracle freq
Cost
100
Qwen2-1.5B
0.6675
0.7288
0.0396
0.3842
0.1275
0.2275
Qwen2.5-3B
0.6975
0.2000
0.2116
0.2058
0.1129
0.3129
OMVV
0.7225
0.1333
0.1581
0.1457
0.1035
0.2090
50
Qwen2-1.5B
0.6725
0.7927
0.0289
0.4108
0.1587
0.2587
Qwen2.5-3B
0.6900
0.2287
0.1862
0.2074
0.1199
0.3199
OMVV
0.7275
0.1119
0.1532
0.1326
0.1328
0.2432
Table 2: OMVV versus single-verifier baselines on the MATH stream, at αI=αII=0.2 , across block sizes B . ErrI and ErrII values exceeding the 0.2 target are shown in red; the best value in each of Accuracy, Avg( ErrI , ErrII ), Cost, and Oracle frequency, within each block size, is bolded.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 2: Empirical cumulative regret Rt(k⋆) of OMVV and the SSV baseline relative to the best fixed verifier in hindsight. OMVV exhibits flattening cumulative regret, consistent with the sublinear expected regret guarantee of Theorem 2 . In contrast, SSV shows approximately linear regret growth over the observed horizon.
B
Method
Accuracy
Err I
Err II
Avg
Cost
Oracle freq
100
qwen2_1.5b
0.9333
0.2288
0.6786
0.4537
0.2903
0.1903
qwen2.5_3b
0.9267
0.8627
0.0314
0.4471
0.2833
0.0833
OMVV
0.9433
0.1405
0.1417
0.1411
0.2214
0.1153
50
qwen2_1.5b
0.9433
0.2828
0.6419
0.4624
0.2836
0.1836
qwen2.5_3b
0.9267
0.8627
0.0365
0.4496
0.2813
0.0813
OMVV
0.9483
0.1186
0.1588
0.1387
0.2343
0.1242
Appendix
Table 3: OMVV versus single-verifier baselines on the DeepMind Math non-stationary stream, at αI=αII=0.2 , across block sizes B . ErrI and ErrII values exceeding the 0.2 target are shown in red; the best value in each of Accuracy, Avg( ErrI , ErrII ), Cost, and Oracle frequency, within each block size, is bolded.
Dataset
Method
Accuracy
Err I
Err II
Avg
Cost
Oracle freq
MATH
qwen2_1.5b
0.6775
0.7845
0.0352
0.4099
0.3367
0.2367
qwen2.5_3b
0.7000
0.4928
0.0845
0.2887
0.3794
0.1794
OMVV
0.7175
0.2018
0.2290
0.2154
0.3346
0.2114
zebra_logic
qwen2_1.5b
0.7200
0.6519
0.0880
0.3700
0.3500
0.2500
qwen2.5_3b
0.6900
0.8810
0.0243
0.4527
0.3514
0.1514
OMVV
0.8300
0.2447
0.2277
0.2362
0.3430
0.2214
Appendix
Table 4: OMVV versus single-verifier baselines, pooled easy and hard subsets, at αI=αII=0.25 . ErrI and ErrII values exceeding the 0.25 target are shown in red; the best value in each of Accuracy, Avg( ErrI , ErrII ), Cost, and Oracle frequency, within each dataset, is bolded.
Large language model reliability studies whether outputs remain correct, calibrated, robust, and controllable across prompts, contexts, and deployment conditions.
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.
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.
Multimodal large language models often generate reasoning chains containing subtle errors that lead to incorrect answers. Current verification approaches have notable limitations. Existing approaches either require expensive labelled supervision with inconsistent cross-task performance or aggregate scores from multiple sources by simple aggregations, missing a key insight: when these scores disagree, that disagreement itself carries important information about whether a reasoning step is truly valid or not. We formalise this as a coupled scoring problem among disparate, frozen verifiers, interpretable as a coordination game with a unique closed-form equilibrium where agreement signals valid steps while disagreement reveals instability. Towards this end, we propose a training-free domain-agnostic step-wise verification approach we call VERDICT: VERification via Disagreement-Informed Coupled Thresholding. To our knowledge, VERDICT is the first training-free verifier that makes the structure of cross-modal disagreement explicit and actionable. It computes consensus scores through a closed-form solution, enabling both disagreement-aware filtering and stability-conscious ranking of reasoning steps. Evaluated across six benchmarks, \method consistently improves over the base model by up to +5.95%, and performs competitively with domain-specific critics that demand extensive supervision, demonstrating that cross-modal agreement provides robust verification signals without task-specific adaptation and Training-Free Verification
Rohit Sinha, Kunal Tilaganji, Tanuja Ganu +3
Indian Institute of Technology, Hyderabad · Microsoft Research