Finite sample bounds measure coverage loss in budgeted document selection
Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing
Artificial Intelligence
Summary
Choosing a limited number of documents to answer lots of questions well is hard when you don’t know which questions will be asked. The authors created a way to estimate how much you might lose by not choosing the best documents, even after using the data to pick them. Their method uses mathematical bounds that work no matter what the question patterns are, and it checks how reliable these bounds are with experiments. This helps people understand and trust the quality of selected document sets in complicated situations.
What this means in practice
- •For knowledge base managers: Assess how much expected query coverage might be lost when selecting documents under a fixed budget with unknown future queries.
- •For data quality auditors: Use finite-sample bounds to certify the reliability of document relevance assessments after adaptive selection and stratified sampling.
Tested on simulated data.
Authors
Nora Serdyukova
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.