OMVV routes among multiple weak verifiers online, beating any single fixed verifier in accuracy at lower verification cost on reasoning benchmarks
Related research and updates
Synopsis
The work introduces 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 achieves sublinear regret against the best fixed verifier in hindsight under a combined cost and consistency objective, and experiments on reasoning dataset benchmarks show higher accuracy at lower verification cost than any single fixed verifier across a range of operating budgets.
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.
arXivInterpretation
It proposes OMVV, which replaces a single fixed weak verifier with a pool of verifiers and adaptively selects a verifier each round via an online score combiner and an exponential-weights routing policy. Prior work queries a single weak verifier at every step and uses its score to decide whether the costly strong verifier must also be queried; OMVV extends this decision to K candidate weak verifiers with differing cost and verification performance, addressing the case where a single fixed weak verifier performs inconsistently as subject matter or difficulty of incoming queries changes over time. The abstract states the algorithm structure and motivation, noting that a single fixed weak verifier may not perform consistently well as subject matter or difficulty changes and that committing to one in advance risks overly costly or inaccurate verification.
OMVV provides a distribution-free, finite-time guarantee on false-accept and false-reject rates across the full pool of verifiers. The guarantee covers the entire verifier pool rather than a single verifier, constituting a theoretical reliability characterization. The abstract explicitly states a 'distribution-free, finite-time guarantee on false-accept and false-reject rates across the full pool of verifiers'.
Under a combined cost and consistency objective, OMVV achieves sublinear regret against the best fixed verifier in hindsight. It brings online-learning regret bounds into verifier routing, so that adaptive routing is not substantially worse over time than the best fixed verifier in hindsight. The abstract states it 'achieves sublinear regret against the best fixed verifier in hindsight under a combined cost and consistency objective'.
On reasoning dataset benchmarks, OMVV achieves higher accuracy at lower verification cost than any single fixed verifier across a range of operating budgets. The experiments directly compare multi-verifier online routing against single fixed verifiers along both accuracy and cost. The abstract reports that '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'; specific dataset names, budget values, and effect sizes are not given in the abstract.
Perspective
The work targets online, multi-step reasoning settings where invoking a costly ground-truth oracle at every step is impractical but multiple weak verifiers with differing cost and performance are available; OMVV pools them and adaptively routes under a given operating budget. Its theoretical results concern false-accept and false-reject rates across the full verifier pool and a combined cost and consistency objective relative to the best fixed verifier in hindsight. The reported experiments are limited to reasoning dataset benchmarks and a range of operating budgets.
The abstract does not give specific dataset names, operating budget values, the size of K, concrete false-accept/false-reject rates, or the form of the regret bound, so the tightness of the guarantee and the experimental effect size cannot be judged from the abstract. How the verifier pool is constructed, how the cost and performance differences among weak verifiers are set, and the exact form of the 'combined cost and consistency objective' require the main text. The abstract also does not state the conditions on correlation among verifiers that the guarantee relies on.