Source-linked AI summary
Online Verification of Language Model Responses Under Cost Constraints
Erfan Hajihashemi, Yanning Shen
TL;DR
Ground-truth verification at every step is often too costly, and a single weak verifier may not suit a changing query stream. OMVV routes responses among candidate weak verifiers, and experiments report higher accuracy at lower cost than single-verifier baselines while maintaining target error rates.
Problem
Ground-truth verification at every step is often impractical, while one fixed weak verifier may not perform consistently as query subject matter or difficulty changes.
Source: §1 · pp. 1–2Method
OMVV adaptively routes each response among weak verifiers with differing costs and performance, using an online routing policy and a combined score.
Source: §1 · p. 2, §4.1 · p. 4Results
Across multiple benchmarks and stream conditions, OMVV achieves higher accuracy and lower verification cost than single-verifier baselines while maintaining target error rates.
Source: §6.1 · p. 7, §7 · p. 8Takeaways & Limitations
OMVV provides distribution-free finite-time error control and sublinear expected regret relative to the best fixed verifier in hindsight.
Source: §1 · p. 2, §7 · p. 8OMVV is framed for sequential query-response streams with K candidate verifiers and a higher-cost ground-truth oracle.
Source: §3 · p. 3
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Because queries arrive over time and ground-truth checking every response is often impractical, OMVV routes responses among weak verifiers instead of relying on one fixed verifier. It provides error-rate and regret guarantees, and experiments report better accuracy and cost than single-verifier selective verification.
1 INTRODUCTION
- In online query streams, an unflagged error can propagate into later queries and responses, while querying an oracle at every step is often impractical.Subject matter and difficulty can shift during the stream, making reliance on one weak verifier limiting.Source: §1 · pp. 1–2
- Across mathematical reasoning, logic, and factual tasks, OMVV outperforms single-verifier selective verification on accuracy and cost simultaneously.The comparison runs the baseline separately with each of the two candidate weak verifiers.Source: §1 · p. 2
- OMVV maintains a pool of weak verifiers with differing costs and verification performance, routing each response based on historical performance.It queries the oracle only when the selected verifier is uncertain.Source: §1 · p. 2
- OMVV guarantees distribution-free finite-time control of false accepts and false rejects, with routing regret relative to the best fixed verifier in hindsight.Its accuracy and cost approach those of that verifier.Source: §1 · p. 2
2 RELATED WORKS
Prior work improves individual verifiers, combines multiple verifiers for response selection, and studies selective prediction and learning to defer. OMVV differs by learning online how to route among weak verifiers with different costs and optionally escalate to an oracle.
2 RELATED WORKS
- Verifier research includes LLM-as-judge, document-grounded claim checking, next-token-trained verifiers, and process-level reward models.These approaches improve individual verification mechanisms.Source: §2 · p. 2
- Weaver and Multi-Agent Verification combine multiple verifiers using fixed inference-time procedures rather than routing each query adaptively or escalating to an oracle.Weaver uses weak supervision; Multi-Agent Verification combines best-of-n sampling with equal-weight voting.Source: §2 · p. 2
- Selective prediction studies reject options and risk-coverage tradeoffs, while learning to defer routes instances to a model or human expert.OMVV instead routes online among heterogeneous weak verifiers and can escalate to a costly oracle.Source: §2 · p. 2
3 PROBLEM SETUP
The setup considers sequential query-response pairs, a pool of candidate verifiers, and an oracle that supplies ground-truth labels at higher cost. The goal is to select verifiers online for accuracy and low cost while controlling false-accept and false-reject rates.
3 PROBLEM SETUP
- At each time step, a query-response pair is presented for verification, and the stream's subject matter or difficulty may change over time.No assumption requires the incoming query distribution to remain fixed.Source: §3 · p. 3
- A selected verifier maps each pair to accept, reject, or query the oracle, with the oracle determining the action when queried.Verifier selection at each round is based on historical performance.Source: §3 · p. 3
- The setup provides K candidate verifiers and a higher-cost oracle that returns the ground-truth verification label when queried.The oracle label is binary, indicating whether the response is correct.Source: §3 · p. 3
- The objective is high accuracy at low cost while keeping false-accept and false-reject rates below their respective targets.The setup denotes these target rates αI and αII.Source: §3 · p. 3
4 METHODOLOGY
OMVV routes each round to one of several weak verifiers, balancing verification cost against agreement with the oracle. It combines verifier-specific decisions and adaptive routing with feedback-driven updates.
4 METHODOLOGY
- OMVV maintains K verifiers with differing costs and performance, then learns online which verifier to select using feedback over time.The objective balances verifier cost against consistency with the oracle.Source: §4 · p. 3
- The per-round loss combines distance from the oracle’s label with the verifier’s fixed cost, weighted by a tradeoff parameter λ.A smaller distance from the oracle label reflects a more reliable decision.Source: §4 · p. 4
- OMVV samples one verifier per round and receives its score alone; consistency feedback is available only when the oracle is queried.Verifier costs are known for every candidate, while consistency uses importance-weighted estimates from partial feedback.Source: §4 · p. 4
4.1 ALGORITHM
- Each selected verifier combines its raw confidence score with same-query response agreement through logistic regression.Agreement is the fraction of other candidate responses for that query that match the current response.Source: §4.1 · p. 4
- Verifier-specific thresholds reject low scores, accept high scores, and send intermediate scores to the oracle; exploration also queries the oracle in accept and reject regions.Separate threshold pairs account for differences in score scales and their relation to correctness.Source: §4.1 · pp. 4–5
- Oracle feedback updates the sampled verifier’s thresholds, while inverse-probability weighting corrects for selective feedback in the routing loss estimates.Threshold updates target false-accept and false-reject rates; routing weights are updated for every verifier each round.Source: §4.1 · p. 5
5 THEORETICAL ANALYSIS
The analysis establishes finite-horizon control of both error rates and sublinear expected routing regret against the best fixed verifier in hindsight.
5 THEORETICAL ANALYSIS
- With probability at least 1−δ, OMVV controls false-accept and false-reject rates at every finite horizon, without assumptions on the stream, generator, or verifiers.The bounds include finite-sample slack terms that decrease as relevant per-verifier sample counts increase, for fixed exploration and algorithm parameters.Source: §5 · p. 6
- For fixed K, λ, and q_min > 0, OMVV’s expected regret against the best fixed verifier in hindsight is sublinear in T.The regret compares cumulative routing loss with that of the best fixed verifier under the combined cost-consistency objective.Source: §5 · p. 6
6 EMPIRICAL PERFORMANCE
OMVV is evaluated on four reasoning tasks against fixed-verifier baselines, with a stream alternating between easy and hard problems. Across datasets, it improves accuracy and verification cost while meeting both error targets, and its routing shifts with difficulty.
6 EMPIRICAL PERFORMANCE
- The evaluation covers mathematical reasoning, logic puzzles, factual question answering, and algebra, using four datasets and streams alternating between easy and hard problems.Each problem has five candidate responses; the verifier pool comprises Qwen2-1.5B-Instruct and Qwen2.5-3B-Instruct, with normalized costs 0.10 and 0.20 against oracle cost 1.0.Source: §6 · pp. 6–7
6.1 RESULTS
- Across all four datasets, OMVV achieves the highest accuracy, lowest average error, and lowest verification cost while meeting both target error rates.Both single-verifier baselines exceed the ErrI target on every dataset at αI = αII = 0.2.Source: §6.1 · p. 7, Table 1 · p. 8
- OMVV updates verifier-selection probabilities each round from observed verification loss, with verifier-specific score combiners and threshold pairs.The combined improvements reflect adaptive routing, verifier-specific score adaptation, and selective oracle use.Source: §6.1 · pp. 7–8
- Oracle-query frequency alone does not determine overall verification cost, because the selected weak verifier also incurs a per-round cost.OMVV may query the oracle more often than a more expensive single verifier on some datasets yet still have lower overall verification cost.Source: §6.1 · p. 8
- On MATH, the probability of routing to the cheaper verifier falls from 0.551 on easy problems to 0.190 on hard problems.The routing policy shifts toward the more expensive verifier as harder problems enter the stream, without explicit difficulty labels.Source: Figure 1 · p. 7, §6.1 · p. 8
- At B = 1, OMVV achieves 0.7250 accuracy and 0.1493 average error as stream difficulty alternates every problem; both single-verifier baselines violate at least one error target.Across block sizes, OMVV has the highest accuracy and lowest average error and verification cost while satisfying both targets.Source: §6.1 · p. 8
7 CONCLUSION
The paper concludes that OMVV adaptively routes responses among weak verifiers with different costs and performance. Its guarantees and experiments support error control and lower-cost, higher-accuracy verification than single-verifier baselines.
7 CONCLUSION
- Experiments across benchmarks and stream conditions show higher accuracy and lower verification cost than single-verifier baselines while maintaining target error rates.The conclusion describes the result across multiple benchmarks and stream conditions.Source: §7 · p. 8
- OMVV provides distribution-free finite-time error control and sublinear expected regret against the best fixed verifier in hindsight.The regret comparison concerns the routing decision.Source: §7 · p. 8
- Table 2 compares OMVV and single-verifier baselines on the MATH stream across block sizes at αI = αII = 0.2.It marks error rates above the 0.2 target and identifies the best accuracy, average error, cost, and oracle frequency for each block size.Source: Table 2 · p. 9
A.1 Proof of Theorem 1
The proof controls errors first within each verifier’s routed substream, then extends the bounds to the full pool. Its argument uses oracle-query randomization and simultaneous bounds across verifiers.
A.1 Proof of Theorem 1
- Per-verifier error control is extended simultaneously across all K verifiers by a union bound, then combined through the pooled error definitions.Every round is routed to exactly one verifier.Source: §A.1 · pp. 11, 13
- The per-verifier argument assumes a positive fixed threshold step size and exploration probabilities bounded away from zero over the finite horizon.The stated condition is qmin > 0.Source: §A.1 · p. 11
- The proof conditions on the selected verifier, score, and latent label before oracle randomization; the latent label is not observed unless the oracle is queried.The analysis filtration includes the latent label only for proof purposes.Source: §A.1 · p. 11
- The proof uses unbiased importance weighting and zero-mean martingale increments to control the accept- and reject-side errors.The two sides are bounded together with probability at least 1 − δ.Source: §A.1 · pp. 11, 13
A.2 Proof of Theorem 2
The empirical regret comparison shows OMVV’s cumulative regret flattening while the single-verifier baseline continues to grow. The proof derives a sublinear expected-regret bound using unbiased loss estimates, a Hedge inequality, and a second-moment bound.
A.2 Proof of Theorem 2
- The regret proof combines an unbiased loss estimate, a deterministic Hedge weight-update inequality, and a second-moment bound.Combining these steps yields the stated sublinear rate.Source: §A.2 · pp. 14–15
- Theorem 2 bounds OMVV’s expected regret against the best fixed verifier in hindsight by a quantity that grows sublinearly in T.The proof treats each verifier’s score and query probability as defined for analysis even when that verifier is not selected.Source: §A.2 · pp. 14–15
B.1 Empirical Validation of Sublinear Regret
- The empirical comparison computes realized regret using a verifier fixed from full-horizon losses and compares it with SSV, whose verifier remains fixed throughout the stream.The evaluation uses the same two-verifier pool as the main reported results.Source: §B.1 · p. 15
- Across MATH, DeepMind Math linear_2d, and TriviaQA, OMVV’s cumulative regret flattens after an early rise, while SSV’s grows approximately linearly.The observed OMVV trajectory is consistent with the sublinear expected-regret guarantee.Source: §B.1 · p. 15
B.2 Block size Experiment: DeepMind Math (linear_2d)
Across block sizes, OMVV leads the single-verifier baselines on DeepMind Math and meets both error targets, while the regret comparison shows flatter growth than SSV.
B.2 Block size Experiment: DeepMind Math (linear_2d)
- OMVV’s cumulative regret flattens, consistent with sublinear expected regret, while SSV’s grows approximately linearly over the observed horizon.The regret is measured relative to the best fixed verifier in hindsight.Source: Figure 2 · p. 16
- Across all block sizes, OMVV has the highest accuracy, lowest average error, lowest verification cost, and lowest ErrI, and alone meets both error targets.The comparison is on the DeepMind Math non-stationary stream at αI = αII = 0.2.Source: §B.2 · p. 15, Table 3 · p. 16
- Table 3 compares OMVV with single-verifier baselines by block size, marking target-exceeding ErrI and ErrII values in red and metric leaders in bold.Its reported metrics include Accuracy, Avg(ErrI, ErrII), Cost, and Oracle frequency.Source: Table 3 · p. 16
B.3 Evaluation at a Different Error-Rate Target
At the 0.25 error-rate target, OMVV leads single-verifier baselines across four datasets; the section also specifies the generation, weak-verification, and oracle prompts used in the evaluation.
B.4 Verifier Implementation Details and Prompt Specifications
- The pipeline uses GPT-4o-mini to generate solutions, two Qwen models as weak verifiers, and either GPT-4o or a deterministic grader as the task oracle.MATH and TriviaQA use GPT-4o as oracle; Zebra Logic and DeepMind Math use deterministic programmatic grading.Source: §B.4 · p. 16
B.3 Evaluation at a Different Error-Rate Target
- Across all four datasets, OMVV has the highest accuracy, lowest verification cost, and lowest ErrI, and meets both error targets when neither single-verifier baseline does.Table 4 pools easy and hard subsets at αI = αII = 0.25.Source: §B.3 · p. 16, Table 4 · p. 17
B.4.1 Generator
- Generator prompts request step-by-step math reasoning with a final answer, or a Zebra Logic deduction ending in a completed answer table.The Zebra Logic prompt asks for the unique correct arrangement.Source: §B.4.1 · p. 17
B.4.2 Weak Verifier
- The MATH weak-verifier prompt scores correctness from 0 to 1 using reasoning soundness, calculation accuracy, and whether the answer follows; TriviaQA also receives a 0-to-1 correctness rating.The MATH prompt is reused verbatim for DeepMind Math.Source: §B.4.2 · p. 18
B.4.3 Oracle
- The MATH oracle prompt compares the generated and ground-truth answers for equivalence, treating formats such as 5, 5.0, and 5/1 as equivalent.It returns a correctness judgment and brief explanation.Source: §B.4.3 · pp. 18–19