CoVeR: Coverage-Based Routing of Verifier Calls in Agentic Retrieval
Daeyoung Roh, Donghee Han
cs.CL, cs.IR
2026-09-03
A frozen embedding coverage margin skips plainly incomplete retrieval states, cutting 62–68% of verifier calls on HotpotQA and 2Wiki with EM within 0.3 points of always-verify.
A multi-hop search agent issues queries in a loop and must decide, after each retrieval, whether the evidence is enough to stop. Handing that decision to an LLM verifier or a prompt judge is reliable, and expensive: the decider rereads the growing evidence after every step. In the Self-Ask setup here, that is about nine to eleven claim verdicts per question, each a full read of the accumulated context.
Most of those calls are not close calls. If a required hop has not been retrieved yet, the verifier will almost always say keep searching. CoVeR uses that observation. A frozen sentence-embedding check detects states that are plainly incomplete and skips the verifier there, paying for a verdict only on the ambiguous remainder. A skip can only defer stopping. It cannot issue a stop of its own.
Each question is decomposed into about two expected hop claims. A frozen E5 encoder embeds the claims and the retrieved sentences. The per-claim coverage margin is one minus the best cosine similarity to any retrieved sentence; the state margin is the worst of those. A large margin means some claim still has no nearby sentence.
A single threshold τ routes the decider. Leave-one-dataset-out selection yields τ=0.16 on all three folds. If the margin is above τ, skip the call and continue; otherwise call the decider and follow its verdict. The rule is one-sided by design. Geometry is good at spotting unfinished search and poor at proving support. A second, lower early-exit threshold would break that guarantee, so the primary system uses one threshold.
A 921k-parameter MLP can replace claim generation on the gate path by mapping the question embedding to k slot embeddings. A decider that still consumes claim text pays for generation when it is actually called, the same cost always-verify pays. When claims are scored sequentially, evaluating them in descending-margin order short-circuits earlier; the verdict is order-invariant.
The primary run uses a trained coverage verifier (cached trajectories from concurrent work HALT), LODO thresholds, and about 1,000 questions each on HotpotQA, 2WikiMultihopQA, and MuSiQue.
| Dataset | EM range of the three systems | Verifier-call cut |
| HotpotQA | 0.304–0.306 | 62.2% |
| 2Wiki | 0.184–0.187 | 67.8% |
| MuSiQue (saturated) | 0.080–0.081 | 93% |
The three systems are full-budget, always-verify, and CoVeR. EM differs by at most 0.3 points; every 95% CI on ΔEM lies within ±1.2 points. On HotpotQA and 2Wiki the gated agent also runs 9.8–11.9% fewer retrieval loops than full-budget. MuSiQue is a different regime: the verifier fires on 2.6% of loops, most trajectories hit the loop cap, and the 93% cut tests safety rather than transferable savings.
The margin cannot replace verification. With oracle supporting sentences it separates covered from uncovered claims at AUROC 0.89/0.90/0.83; the deployable generated-claim margin falls to 0.69/0.68/0.76. Forced to match the verifier's coverage-safety, a margin-only stopping rule never stops. Matching a claim is easier than deciding the claim is supported.
Cheaper routers do not match the same frontier. At stop-loop agreement ≥0.90, the embedding cut on HotpotQA is 0.622, versus 0 for evidence count, 0.512 for lexical overlap, 0.202 for BM25, and 0.435 for a learned mix of the cheap signals. Random skipping at CoVeR's exact call cut loses 6.4/7.0 points of agreement on HotpotQA/2Wiki. The same untuned threshold routes a public prompt judge, a 7B agent, and a DeBERTa-v3 MNLI cross-encoder. On open-corpus HotpotQA Setting-B it cuts 92.1% of calls with EM statistically indistinguishable from both references, in a saturated 6.4%-fire setting.
For retrieval agents that already use an LLM to decide when to stop, this is a near-zero-training filter. Embed the claims the agent already generates, pick a threshold on a small training split, and route. The gate-side drafter can drop below 11M parameters. CoVeR does not invent a new stopping policy. It lowers the cost of delivering an existing one.
The saving is verifier workload, not a stack-independent latency claim: 62–68% fewer calls, 62–68% fewer claim-verdict pairs, and 72/73/97% fewer verifier input tokens. Gating defers stops by at most half a retrieval loop per question. Whether that is a win depends on the relative cost of a verifier call and a generation loop.
The evidence is one scaffold (Self-Ask) and a closed distractor pool, plus one saturated open-corpus point. Absolute EM is 0.08–0.31, so a 1-point HotpotQA loss is not excluded. The gate inherits the verifier's premature stops and cannot veto them: both signals are driven by claim–evidence similarity, so a deceptive near-match fools both. E5 is Wikipedia-heavy. Each trajectory is a single seed-13 run. Claim decomposition can fail on comparison and aggregation questions, and that failure is not quantified.