Language model verification improves by using multiple checkers online
Online Verification of Language Model Responses Under Cost Constraints
Machine Learning
Summary
Ensuring a language model’s reasoning is correct often requires checking with expensive, trusted methods, which is slow and costly to do all the time. The authors propose a way to pick from several cheaper and imperfect checkers dynamically based on performance and cost as new queries arrive. Their method balances accuracy with cost more effectively than relying on one fixed checker. Experiments show it reduces verification expenses while keeping results accurate.
What this means in practice
- •For ai service operators: Reduce verification costs while maintaining accuracy in large language model deployments that require multi-step reasoning checks.
- •For automated quality assurance teams: Dynamically optimize the use of multiple verification tools for AI-generated responses to balance time and accuracy under budget limits.
Authors
Erfan Hajihashemi, Yanning Shen
Abstract
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.