Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing
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.
Related
- HALO: Hierarchical Evidence Selection and Reinforcement Learning for Allocating Budgeted Label Optimization from Longitudinal Clinical Records
- StreamLTT: Risk Certification for Policy Selection under Stream Dependence
- Conditional-Coverage Contributor Selection for Regional Digital Twins Under Mobility
- Sequential Confidence Sets for Coverage-Constrained Conformal Model Selection
- A Unified Framework for Scenario Coverage Estimation and Representative Selection in Simulation-Based Testing of Automated Vehicles
BibTeX
@misc{serdyukova2026finitesample,
title = {{Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing}},
author = {Nora Serdyukova},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19207},
eprint = {2610.19207},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19207},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing
AU - Nora Serdyukova
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.19207
UR - https://arxiv.org/abs/2610.19207
AB - 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.
ER -