CS Paper Radar

Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing

Nora Serdyukova

cs.AI math.ST ·submitted 2026-10-13 21:17 UTC · v1
theory

Abstract

Selecting a budget-constrained set of documentary fragments, for instance the knowledge base of a retrieval-augmented generation system, raises a statistical question: how much expected query coverage is lost relative to the best feasible selection when the query distribution is unknown? We construct finite-sample, distribution-free upper confidence bounds for this coverage regret that remain valid after data-dependent selection. A pilot stage may select the document set, screen competitors, build comparison networks and learn an annotation policy. Then an independent audit acquires relevance labels with probabilities that are constant within observable strata. The main result is a simultaneous bound for all retained coverage contrasts. The bound is made observable by empirical-Bernstein variance calibration or by a one-stage construction without calibration, and it accounts for estimated stratum proportions. For maximum-type coverage we prove variance contractions for swaps of redundant fragments, give a condition under which multiscale radii improve on a direct union bound, and show that such redundancy cannot be certified from samples alone. A simulation study confirms validity and quantifies the gains from variance calibration and certified redundancy.

Comment
23 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Re:CAP - Auditing Retrieval Coverage in Production RAG Pipelines

cs.CL ·2026-09-21 ·Aviral Joshi, Hanoz Bhathena, Max Nelson, Saket Sharma
top venue similarity 0.64
Abstract

Retrieval-augmented generation (RAG) is hard to monitor in production: exhaustive relevance labels do not exist for non-stationary multi-million-passage corpora that re-index in real time. As a result, retrieval quality is generally understudied and often deprioritised in favour of generation-oriented metrics. In this work, we propose auditing retrieval coverage by probing for evidence of missing documents rather than enumerating every relevant one. Our method Re:CAP (REtrieval Coverage Audit by iterative Probing) is a reference-free audit loop applied to a deployed RAG pipeline's initial answer and retrieved context: it identifies the topics already covered, generates probing questions for plausibly missing topics, retrieves candidate documents, and applies an LLM-as-judge to retain only those that introduce previously-unretrieved information. On four public benchmarks, Re:CAP recovers 9-29% of gold labels that flat BM25 top-500 cannot reach, rising to 48% on TREC-COVID. On MuSiQue Re:CAP beats flat hybrid top-500 by +12.9 pp on recall at less than half the document budget. An ensemble BM25, dense, and hybrid baseline (top-500 each) still leaves out 21.2% of gold docs on TREC-COVID that Re:CAP recovers; human annotators judge that 78.9% of those structurally distinct documents add new information to the baseline answer (Fleiss $κ$ = 0.79, n = 123), and 73.9% on live production traffic (n = 180). End-to-end recall is reproducible to within $\pm$1% across three independent runs, making Re:CAP a stable instrument for periodic retrieval audits.

0.29

Incremental Pooled LLM Evaluation for Cost-Effective Retrieval Model Selection

cs.IR cs.CL ·2026-09-02 ·Max Nelson, Hanoz Bhathena, Aviral Joshi, Saket Sharma
benchmark similarity 0.62
Abstract · 10 pages, 1 figure

Selecting a retrieval model for a production RAG system requires reliable comparative evaluation, but obtaining relevance judgments at scale is expensive and difficult to repeat as new candidate systems arrive. We study pooled LLM evaluation, in which an LLM judges the union of documents retrieved by the current set of candidate systems, and the pool is then expanded incrementally as new systems are introduced by judging only the new documents they contribute. These judgments are reused to evaluate all systems on a common basis. We validate this approach on four retrieval benchmarks with 11 systems spanning dense, sparse, and hybrid configurations, and deploy it to compare 62 retrieval configurations for a financial news QA system. Pooled LLM rankings correlate strongly with gold-standard evaluation across datasets, and 97% of pairwise system orderings are preserved once bootstrap uncertainty in the qrels is taken into account. In production, document overlap yields 65-80% judgment reuse and up to 4.9x lower evaluation cost, allowing teams to benchmark new retrieval candidates without re-judging previously assessed documents. These results suggest pooled LLM evaluation is a practical and cost-effective workflow for incremental retrieval model selection in deployed systems.

0.15

Decompose, Estimate, Select: Coverage-Aware Context Construction for Long-Form RAG

cs.IR ·2026-10-29 ·He Tu, Aleena Bosco Kurumthottam, Torsten Suel
theory similarity 0.62
Abstract

Retrieval-augmented generation (RAG) grounds a language model's output in retrieved evidence, but for complex questions spanning multiple aspects of an information need, relevance-based retrieval may return redundant evidence while leaving some aspects unsupported. We propose a coverage-aware retrieval pipeline that decomposes queries into subquestions, ranks candidates with a coverage-trained bi-encoder, predicts a document\,$\times$\,subquestion coverage matrix with a cross-encoder, and selects documents by greedy maximum-marginal coverage. On TREC RAG 2024, our approach improves $α$-nDCG@10, which rewards newly covered nuggets and discounts redundant evidence, from $0.625$ to $0.702$, approaching the $0.718$ gold-nugget upper bound without sacrificing relevance. We then find that ground-truth oracle retrieval, despite substantially higher retrieval coverage, delivers no more nugget coverage to the answer than our estimated selection. This suggests that answer completeness depends not only on what evidence is retrieved, but also on how effectively the generator uses it. To address this, we introduce a \emph{grounded self-feedback loop} in which the model identifies underused evidence from its first answer and generates again without gold supervision, raising $V_{\mathrm{strict}}$, the fraction of vital reference nuggets fully supported by the answer, by $0.086$ over two passes while largely preserving faithfulness.

0.23

Learning Marginal Viewpoint Utility for Budgeted Evidence Selection in RAG

cs.IR ·2026-10-21 ·Yiyang Duan, Ziqi Yu, Tiantong Wu, Yebo Wu, Wei Yang Bryan Lim
benchmark similarity 0.62
Abstract · 30 pages, 8 figures, including appendices

Retrieval-augmented generation over multi-viewpoint queries must preserve distinct answers and positions from the retrieved evidence while operating under a fixed context budget. We introduce LMVU, a lightweight ranker that learns to prioritize candidates by the marginal viewpoint coverage they add to the current selection. Training uses viewpoint annotations from each benchmark's development split to compare candidates within the same selection state. At inference, LMVU repeatedly scores budget-feasible candidates as the context grows, without accessing these annotations. We evaluate two forms of recovered viewpoint coverage: RVC$_1$ assigns each viewpoint full credit for at least one supporting source unit, while RVC$_2$ assigns half credit for one and full credit for two or more distinct source units. Exact oracles measure achievable coverage under the same evidence pool and budget. Across four viewpoint-annotated benchmarks at a 1,024-token budget, LMVU achieves gains of up to 0.047 and 0.052 points in RVC$_1$ and RVC$_2$, respectively, over the strongest non-oracle baseline for each benchmark and metric, and reaches the exact viewpoint-breadth ceiling on two benchmarks.

0.18

Query-Aware Token Budgeting for Efficient Late-Interaction Visual Document Retrieval

cs.IR cs.AI ·2026-09-07 ·PS Rishi, Rajeev Ranjan Dwivedi, Vinod K Kurmi
top venue similarity 0.60
Abstract · Accepted at IEEE International Conference on Data Mining (ICDM)

Late-interaction visual document retrievers preserve fine-grained page evidence by storing many token embeddings per page, but the resulting storage and query-time interaction costs make large-scale deployment expensive. Pooling document tokens before indexing offers a natural remedy, yet static pooling must decide which visual evidence to preserve before the query is known. We study an alternative: a heavily compressed hot-path index generates candidates, after which query-aware token budgeting operates on the original token sets of the shortlisted pages. We formulate this stage-two selection as a budgeted MaxSim coverage problem, show that a clipped version is monotone submodular, and compare coverage-only, cluster-guided, token-wise, and marginal-gain policies. On ten ViDoRe tasks with ColModernVBERT, direct static pooling reduces macro normalized discounted cumulative gain at rank five from 0.6309 without compression to 0.4738 at a thirty-two-fold pool factor. Under the same candidate-generation regime and a pool-factor-eight-equivalent reranking budget, token top-k recovers 93.93 percent of the full-token score, while greedy marginal-gain selection recovers 98.39 percent. Held-out and leave-one-dataset-out evaluations yield positive greedy improvements over token top-k on every dataset. The latency analysis reveals two useful operating points: token top-k for interactive retrieval and the naive greedy implementation as a quality upper envelope. Together, these results show that late-interaction visual retrieval benefits from query-aware allocation rather than query-agnostic pooling alone.

0.51

Coverage Under Contradiction: A Benchmark for Negation-Aware Retrieval

cs.IR cs.CL ·2026-10-27 ·Pasha Abrishamchian, Eugene Yang, Andrew Yates, Nazli Goharian, Ophir Frieder
top venuebenchmark similarity 0.60
Abstract · 5 pages, 1 figure. Accepted at CIKM 2026

Coverage-evaluation benchmarks quantify whether retrieved evidence covers the different pieces of information needed to satisfy an information need. Existing benchmarks mostly consider factual claims that may already be known to pretrained retrieval components, leaving open whether retrievers find corpus evidence when it contradicts those priors. We study how retrievers behave when their parametric knowledge and the information in a corpus disagree. To do so, we develop a process to augment a nugget-based coverage benchmark with controlled contradictions. For each nugget, we create a negated counterpart and edit its supporting documents to support that negation while preserving the context. Applying this process to CoverageBench, a benchmark measuring information coverage, we create CoverageBench-Negate, spanning six datasets and roughly 63,000 original-edited evidence pairs (one per nugget-document link). We attach rich construction metadata to every pair and additionally provide out-of-family LLM judgments over all pairs and a human audit of a sample. In baseline experiments, BM25 separates original from edited near-twin evidence substantially better than dense retrievers (Qwen3 and Jina), which stay near chance. We release the benchmark on Hugging Face Datasets (nuggets, documents, pairs) together with the construction materials, including the prompts used to create it.

0.45

The Impact of Scenario Representation in Scenario-based Optimization Certification

eess.SY cs.ROmath.OC ·2026-11-16 ·Stephen Crawford, Nora Ayanian
similarity 0.60
Abstract

Scenario-based optimization provides finite-sample guarantees for decisions constructed from sampled uncertainty, but its certification procedures can be sensitive to how those samples are represented. We investigate this sensitivity under lossless scenario regrouping, which preserves the sampled information, feasible region, optimizer, and primitive violation probability. For an equal-allocation support-subsample certificate, we derive the distortion factor \(k^2(1-ε)^{k-1}\), establish certification reversals between equivalent representations, and provide sufficient conditions for acceptance dominance under nested coarsening. We further apply nondegeneracy-free Wait-and-Judge theory to coordinatewise scenario envelopes, enabling stronger certification directly from the primitive observations. In paired scenario-MPC experiments, exact regrouping increases certification availability from 318 to 471 of 480 attempts without changing the samples, numerical proposals, or requiring any reduction in witness cardinality. Primitive Wait-and-Judge certification accepts the same 471 attempts without regrouping. These results demonstrate that apparent scenario sample-efficiency gains can arise from certificate accounting rather than additional information or reduced decision risk.

0.27

Contract-Explicit Evaluation: From Auditing Learned Readers to Scoped Certificates

cs.CL ·2026-11-17 ·Hao Lu, Weixing Zhu, Ruiyang Li
benchmarktheorycode/data similarity 0.60
Abstract · 50 pages, 4 figures. Supplementary material (Online Resource 1, 14 pages) included as ancillary file. Artifact repository: https://github.co…

Evaluation readings of document-level relation extraction (DocRE) systems depend jointly on the model and the evaluation contract: gold version, scoring function, threshold. Rankings reverse across contracts, yet no existing method determines which comparisons survive the reversal. We address this gap with contract-explicit evaluation: a preregistered five-step protocol (Declare, Measure, Scope, Certify, Hedge), operationalizing the classical concordance decomposition of Kendall's rank correlation, that scopes certifiable regions and delivers distribution-free census certificates across two ecosystems. In the DocRE audit (44 training runs of one in-house architecture family), the scoring dimension scopes to a census certificate (three flagged instances, Clopper--Pearson upper bound 0.146); the confirmatory record includes registered negatives, and the audit prices its own simplification finding---the calibration dial's entire margin is one withdrawn commit. In an LLM-judge census (17 judges, 49,938 battles), 12.25% of leaderboard comparisons require hedging at the pre-declared split criterion (bound 0.124; panel-robust 0.143), with an exploratory two-tier reading certifying 69% at a bound \le 0.072 and a validity decomposition against released human labels (65% of contested battles are judge error, not ambiguity). The cross-model certificate is withdrawn on real confidence scores; the failure spectrum maps the boundary. The protocol, map, ledger, and per-instance artifacts are released.

0.49