- 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
- 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.
- 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
- Does Theorem 2 establish pseudo-regret against a fixed comparator or expected regret against a random hindsight minimizer?
- Does OMVV retain its advantage when single-verifier baselines use identical agreement features, logistic calibration, exploration probabilities, and threshold updates?
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 for each n=1,…,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⋆ in Section 5 and the final step of the proof in Appendix A.2 to make this distinction explicit. For fixed K, λ, and qmin>0, the bound remains O(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.