acceptodds
Under review as a conference paper at ICLR 2027

Online Verification of Language Model Responses Under Cost Constraints

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 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Online Learning, LLM Verification

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_UeoVOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Online Multi-Verifier Verification (OMVV), which selects an inexpensive verifier in an online query stream and uses two thresholds to accept, reject, or consult an expensive oracle. It combines raw verifier scores with candidate-answer agreement and uses importance-weighted threshold updates and exponential-weight routing. The paper claims finite-sample error control across the verifier pool and sublinear expected regret against the best fixed verifier.

Critical strengths

Relative verifier performance can change in online environments. Jointly learning verifier selection and oracle use, while retaining exploration in accept and reject regions, addresses an important practical problem and avoids complete feedback blind spots.

Critical weaknesses
  1. The current proofs do not fully establish the central guarantees, and their interpretation exceeds the analyzed objective. Claim 4 of Theorem 1 substitutes an adaptive random sample count into a concentration bound without identifying a supporting theorem or supplying the necessary argument. Theorem 2 applies fixed-comparator unbiasedness to a hindsight minimizer that may depend on algorithm history, without adequately distinguishing pseudo-regret from expected hindsight regret. Furthermore, the objective includes score error and weak-verifier cost but excludes oracle cost, so it does not directly guarantee separate improvements in accuracy and total cost relative to the best fixed policy.
  2. The experiments do not isolate the contribution of multi-verifier routing. OMVV combines agreement features, online logistic calibration, and adaptive routing, but it is insufficiently clear whether single-verifier baselines match the first two components and their update configurations. Improvements may therefore partly arise from additional features or calibration rather than routing.
Questions for authors
  1. Does Theorem 2 establish pseudo-regret against a fixed comparator or expected regret against a random hindsight minimizer?
  2. Does OMVV retain its advantage when single-verifier baselines use identical agreement features, logistic calibration, exploration probabilities, and threshold updates?
1 comment
AuthorsOpenReview ↗

Rebuttal by Authors

The revised manuscript has been uploaded, with changes marked in blue

Q1 & W1: We thank the reviewer for reading our proofs carefully. We revised the concentration argument in Claim 4 and clarified the comparator and the objective covered by Theorem 2.

W1. Claim 4 and Theorem 1. The number of correct or incorrect responses routed to each verifier depends on OMVV’s routing decisions. In Appendix A.1, we now apply Freedman’s inequality (Tropp, 2011, Theorem 1.1) using a fixed variance level n/qmin⁡n/q_{\min} for each n=1,…,Tn=1,\ldots,T. Taking a union bound over these counts gives a bound that applies at the count observed during the run. Theorem 1 continues to control both error rates with the revised slack in Lemma 1.

W1 and Q1. Comparator in Theorem 2. Theorem 2 establishes pseudo-regret. The proof applies to every fixed verifier and therefore to the verifier with the lowest expected cumulative routing loss. The submitted definition used the verifier with the lowest realized cumulative loss, whose identity can vary across runs. We revised the definition of k⋆k^\star in Section 5 and the final step of the proof in Appendix A.2 to make this distinction explicit. For fixed KK, λ\lambda, and qmin⁡>0q_{\min}>0, the bound remains O(T)O(\sqrt{T}).

W1. Oracle cost and the scope of Theorem 2. Theorem 2 bounds regret for the routing loss in Equation (4), which combines the verifier’s squared prediction error with the cost of calling that verifier. A bound on this combined loss does not guarantee separate improvements in accuracy and total verification cost. We revised the Introduction and Contribution II to clarify this scope. Section 6 reports both metrics empirically and includes the cost of oracle queries in the total verification cost.

Q2 & W2: We reran both single verifier baselines with the same agreement feature, online logistic calibration, exploration probabilities, and threshold update rule as OMVV, using the same hyperparameters for these components. Each baseline uses one fixed verifier throughout the stream. In the comparisons reported in Subsection B.11 of the revised manuscript, OMVV achieves higher accuracy than both baselines and is the only method to meet both error targets.

We also evaluated four variants of OMVV on Zebra Logic, changing one component at a time. We removed the agreement feature, applied the thresholds directly to the raw score, shared one threshold pair across verifiers, or replaced learned routing with uniform verifier selection. Replacing learned routing alone lowers accuracy, increases verification cost, and causes both error rates to exceed their targets. Subsection B.7 describes the variants, and Table 7 reports the results.

Reviewer_Sio4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies online verification of LLM responses under verification cost constraints. The proposed method, OMVV, maintains a pool of weak verifiers with different costs and verification capabilities, and adaptively selects one verifier for each incoming response. Each verifier uses adaptive accept/reject thresholds and queries a costly oracle when its prediction is uncertain, while an exponential-weights routing policy learns which verifier to use over time. The paper provides finite-time guarantees for controlling false-accept and false-reject rates and proves sublinear regret against the best fixed verifier in hindsight. Experiments on MATH, Zebra Logic, TriviaQA, and DeepMind Mathematics show that OMVV can achieve better accuracy and lower verification cost than using either weak verifier alone.

Critical strengths

S1: The problem is practically relevant. The paper considers the realistic setting where oracle verification is expensive and different weak verifiers may have different cost-accuracy trade-offs.

S2: The method combines adaptive verification and verifier routing in a clean framework. Maintaining verifier-specific thresholds while learning a routing distribution online is intuitive and well motivated.

S3: The paper provides theoretical guarantees. In addition to empirical results, the authors derive finite-time false-accept/false-reject control and a sublinear regret bound for the routing policy.

S4: The empirical results are fairly consistent. OMVV improves the accuracy-cost trade-off over the single-verifier baselines across several reasoning and factual QA benchmarks, including under streams with changing difficulty.

Critical weaknesses

W1: The empirical evaluation uses only two weak verifiers. Although the paper is framed as a general multi-verifier framework with K candidate verifiers, all experiments use only Qwen2-1.5B and Qwen2.5-3B. It is therefore unclear how well the method scales when the verifier pool is larger or more heterogeneous.

W2: The baseline comparison is quite limited. The main comparison is against running each verifier independently with the single-verifier selective verification method. Stronger alternatives such as simple cost-aware routing, confidence-based routing, standard bandit algorithms, or verifier ensembles would help establish whether the proposed routing and update mechanism is necessary.

W3: There is some mismatch between the non-stationary motivation and the theoretical comparator. The paper emphasizes changing query difficulty and the need to switch between verifiers, but the regret guarantee is only against the best fixed verifier in hindsight. A switching or dynamic-regret analysis would be more closely aligned with the main motivation of the paper.

W4: The experimental non-stationarity is somewhat artificial. The online streams are mainly constructed by alternating predefined easy and hard subsets. It would be useful to evaluate naturally occurring distribution shifts or heterogeneous query streams where difficulty labels are not explicitly used to construct the sequence.

W5: The contribution of the individual components is not sufficiently isolated. OMVV simultaneously introduces multi-verifier routing, verifier-specific threshold adaptation, an agreement feature, and an online logistic score combiner. An ablation study is needed to understand which components are responsible for the improvements.

Questions for authors
  1. How does OMVV perform with a larger verifier pool, e.g., K=4K=4 or K=8K=8, including verifiers with substantially different model families, costs, and calibration properties?

  2. Could the authors compare OMVV with stronger routing baselines, such as confidence-based routing, a standard EXP3-style router without the proposed threshold mechanism, or a simple policy that chooses a verifier based on estimated difficulty?

  3. Since the main motivation is adaptation to changing query difficulty, why is the theoretical comparison made only against the best fixed verifier? Can the analysis be extended to switching regret or dynamic regret?

  4. Can the authors provide ablations for the agreement feature, the online logistic score combiner, verifier-specific thresholds, and the exponential-weights routing component?

  5. How sensitive is OMVV to the hyperparameters λ\lambda, PAP_A, and ηa\eta_a? In particular, how does changing the exploration probability affect the verification cost and the finite-sample error-control slack?

  6. For MATH and TriviaQA, GPT-4o is used as the oracle. How robust are the results if the oracle itself occasionally makes mistakes, and what happens to the theoretical error-control guarantees under a noisy oracle?

  7. The experiments use synthetically constructed easy/hard blocks. Can the authors evaluate OMVV on a naturally non-stationary stream, without explicitly organizing the inputs according to known difficulty levels?

1 comment
AuthorsOpenReview ↗

Rebuttal by Authors

We sincerely thank the reviewer for carefully reading our manuscript and for their thoughtful comments. revised manuscript has been uploaded with changes marked in blue. We address the reviewer's concerns and questions below:

Q1 & W1: To evaluate OMVV with a larger and more diverse verifier pool, we conducted additional experiments by adding DeepSeek-V3-0324 and DeepSeek-V4-flash to the original Qwen2-1.5B and Qwen2.5-3B verifiers, increasing the pool size to K=4K=4. We evaluate on the easy and hard MATH subsets. OMVV achieves the highest accuracy and the lowest average error and cost among the evaluated methods. Further experimental details and results are provided in Section B.5 of the revised manuscript.

Q2 & W2: We compared OMVV with three routing baselines on DeepMind Math. OMVV met both error targets and achieved the lowest verification cost. Although all three routing baselines achieved slightly higher accuracy than OMVV (by at most 1.66 percentage points), they all queried the oracle more often and incurred higher verification costs. For example, difficulty-based routing queried the oracle more than 5 times as often as OMVV and cost more than 3 times as much. We added Subsection B.6 to the revised manuscript to describe the baselines and report the results in Table 6.

Q3 & W3: Thank you for suggesting a switching comparator. In Appendix A.3 of the revised manuscript, we added Theorem 3 and its proof to extend the analysis beyond the best fixed verifier. Theorem 3 shows that OMVV achieves sublinear expected routing regret against any verifier sequence fixed in advance with at most S switches over T rounds. The switches may occur at arbitrary rounds, and OMVV does not need to know when they occur.

Q4 & W5: We evaluated four variants of OMVV on ZebraLogic. We removed the agreement feature, removed the online logistic combiner, shared one threshold pair across verifiers, or replaced exponential-weights routing with uniform routing, changing one component at a time. Removing the agreement feature or the combiner led to drops in accuracy. Sharing thresholds and uniform routing caused error rates to exceed their targets. Full OMVV achieved the highest accuracy and the lowest verification cost and was the only method to meet both error targets. Subsection B.7 of the revised manuscript describes the variants and Table 7 reports the results.

Q5: We vary λ\lambda, η\eta, and PP one at a time on MATH. As λ\lambda increases, OMVV selects the more expensive verifier more often. Verification cost generally increases, while accuracy changes little. This routing pattern is consistent with Equation (4), since a larger λ\lambda gives less weight to verifier cost. As η\eta increases, accuracy decreases and verification cost generally decreases. A larger step makes each threshold respond more strongly when oracle feedback triggers an update. Smaller steps generally give more accurate decisions at a higher cost. As PP increases, average error decreases and verification cost increases. OMVV queries the oracle more often, which gives it more feedback for updating the thresholds. The decrease in observed error is consistent with Appendix A.1, where a larger PP reduces the finite-sample slack for fixed sample counts. Subsection B.8 of the revised manuscript reports the results.

Q6: We test OMVV on MATH by independently flipping GPT-4o’s labels at rates of 5%, 10%, and 20%. We evaluate against the original GPT-4o judgments. As the noise level increases, accuracy declines overall and average error increases. Theorem 1 bounds errors relative to the labels the oracle reports. If BIB_I is the false-accept bound under the noisy labels, then the false-accept rate against the original labels is at most BI(N~0/N0)+ρ01B_I(\widetilde N_0/N_0)+\rho_{01}. Here, N0N_0 counts responses labeled incorrect by the original oracle, and N~0\widetilde N_0 counts those labeled incorrect by the noisy oracle. The added term ρ01\rho_{01} is the fraction of originally incorrect responses whose labels flip to correct. The false-reject bound uses the corresponding counts for correct responses and adds ρ10\rho_{10}, the fraction of originally correct responses whose labels flip to incorrect. Subsection B.9 of the revised manuscript presents the results.

Q7 & W4: To address this concern, we evaluated OMVV on a heterogeneous stream of 2,200 problems from MATH, TriviaQA, Zebra Logic, and DeepMind Mathematics. We shuffled the problems within each task and randomized the order of the four task blocks. This creates changes in query type without using difficulty labels to order the stream or informing OMVV when a task changes. We also evaluated OMVV on 1,000 MATH problems shuffled across all five difficulty levels. On both streams, OMVV achieved higher accuracy, lower verification cost, and lower average error than either single-verifier baseline. Subsection B.10 of the revised manuscript describes the experimental setup.

Reviewer_yuvNOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

This paper is an extension of the weak and strong verification framework of Noorani et al. Instead of having a single cheap verifier, the authors consider a pool of (K) verifiers, each with a different fixed, known cost. They maintain a probability distribution over the verifiers and update it online based on a loss that combines the verifier's prediction error and cost. The verification algorithm and threshold updates are applied separately to each verifier.

So the contribution of the paper is an exponential-weights bandit algorithm for routing between K different verifiers on top of the prior framework, and the authors provide a sublinear regret guarantee for the routing decisions relative to the best fixed verifier in hindsight, under their combined loss. That said, I think its natural extension, its interesting and practical. The writing is also clear, and overall I am leaning positive on the paper.

Critical strengths

See above

Critical weaknesses

Some MAJOR concerns with the experiments: The paper uses only two verifiers ( which is fine) and compare their method against running prior-work SSV algorithm with either verifier fixed. But the error rates of the single-verifier baselines are way above the specified targets (e.g., false-accept rates of 0.77 and 0.84 for a target of 0.2). This doesn't make sense to me.

Technically, exceeding the target is fine because of the finite-sample slack terms, But these violations are enormous, and I don't see a clear reason why their method would be so much better at controlling the errors. The paper maintains and updates a separate threshold for each verifier, so each threshold actually receives fewer samples than it would if we used a single fixed verifier throughout. Routing could improve performance, but I wouldn't expect this dramatic difference in error control. My guess is the authors tuned the hyperparameters for each verifier''s thresholds unfairly. They also don't report the hyperparameters or provide any discussion of why the baselines perform so poorly.

Questions for authors

Overall, I think the idea is reasonable and the paper is generally well written, there are major experimental issues that need to be clarified.

Update: Thanks for the rebuttal and clarifications. Please add these details to the paper.

2 comments
AuthorsOpenReview ↗

Rebuttal by Authors

Thank you for raising these concerns and for taking a close look at our experimental results. We address each concern below.

To better understand the high false-accept rates, we examined the raw verifier scores on Zebra Logic and reran both single-verifier SSV baselines using the same scoring method as OMVV. In Table 12 of the revised manuscript, we divide the score range from 0 to 1 into four intervals and report the fraction of responses in each interval. For each verifier, we score the same responses twice, first with its raw score and then with OMVV’s online combiner, which uses the raw score and the agreement feature. The raw scores concentrate near the upper end of the range: 98.5% of responses receive a score of at least 0.8 from Qwen2-1.5B, and 93.9% do so from Qwen2.5-3B. With the combiner, the scores spread across a wider range. The last column shows why this matters. Among responses with raw scores of at least 0.8, only 60% and 67% are correct for the two verifiers, respectively. With the combined score, the corresponding figures rise to 93% and 82%. Thus, a high combined score is a more reliable indication that a response is correct. Table 13 examines the incorrect responses directly. For Qwen2.5-3B, 92.8% of incorrect responses receive a raw score of at least 0.8. When we apply the combiner to those same responses, only 22.9% remain in that range. The raw verifiers frequently give incorrect responses scores near the top of the scale. Table 14 shows what happens when we rerun SSV with the combined score and let each baseline make decisions using its online thresholds. The false-accept rate falls for both verifiers. Even when the single-verifier baselines use the same scoring method as OMVV, OMVV achieves higher accuracy than either baseline on Zebra Logic and is the only method in this comparison that meets both error targets.

For each dataset, we used grid search to tune OMVV on a held-out validation set containing both easy and hard questions. The selection rule picked the configuration with the lowest verification cost among those whose false-accept and false-reject rates were both at or below 0.20. The selected parameters were also used for the baselines. Across all datasets, OMVV and both baselines used the same initial acceptance and rejection thresholds of 0.8 and 0.2, respectively. Subsection B.13 of the revised manuscript reports the candidate grid in Table 15 and the values selected for each dataset.

Reviewer_yuvNOpenReview ↗

Response

Thanks for the rebuttal and the explanations. I have increased my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.