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

Nora Serdyukova

math.STOct 13, 2026

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

Authors: Nora Serdyukova

Organizations: Department of Statistics, University of Concepcion, Chile

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.

Figures & tables

Symbol	Meaning
$\mathcal{H}_{B},\mathcal{C},\widehat{S},S^{\star}$	feasible, retained, selected, optimal document sets
$h_{S},F(S),R_{B}(S)$	query coverage, mean coverage, population regret
$D_{T},\Delta_{T}$	contrast against $\widehat{S}$ and its population mean
$H,\pi_{h},\widehat{\pi}_{h},P_{h}$	number, true/estimated weights, conditional query law
$n_{h},\overline{D}_{h,T},\mu_{h,T}$	audited count, sample/conditional contrast means
$Z_{T}$	weighted, centered audit error

Table 1: Main notation. All candidate-dependent objects may be random through pre-audit pilot information.

Certificate	$n_{h}=100$	$n_{h}=200$	$n_{h}=400$	$n_{h}=800$	$n_{h}=1600$
Hoeffding, flat	0.550	0.381	0.265	0.187	0.134
One-stage EB, flat (Thm. 3 )	0.930	0.507	0.276	0.156	0.092
One-stage EB, two-level	0.744	0.409	0.224	0.129	0.077
One-stage EB, two-level, $\bar{b}_{h,e}=2$	1.000	0.723	0.381	0.208	0.117
Calibrated Bernstein, flat (Thm. 2 )	0.340	0.186	0.101	0.061	0.037
Calibrated Bernstein, two-level	0.293	0.161	0.088	0.053	0.033

Table 2: Mean regret certificate

\overline{R}

over 200 replications,

\varepsilon=0.05

, as a function of the number

n_{h}

of audited queries per stratum. Standard errors are below

0.003

in all cells. The last rows give the mean true regret

R_{B}(\widehat{S})

and the mean largest weight-correction term

\max_{T}e_{\pi}\sum_{h\geq 1}\rho_{h,T}

, common to all certificates.

Figure 1: Mean regret certificate $\overline{R}$ (logarithmic scales) over 200 replications at $\varepsilon=0.05$ , as a function of the number of audited queries per stratum. The pooled Bennett certificate (dashed, open marks) nearly coincides with the flat calibrated Bernstein certificate. The dashed black line is the mean true regret.

Certificate	$\varepsilon=0$	$\varepsilon=0.02$	$\varepsilon=0.05$	$\varepsilon=0.1$	$\varepsilon=0.2$	$\varepsilon=0.4$
Calibrated Bernstein, flat	0.101	0.104	0.101	0.104	0.107	0.109
Calibrated Bernstein, two-level	0.082	0.087	0.088	0.097	0.113	0.139
ratio	0.81	0.84	0.87	0.93	1.05	1.27
One-stage EB, flat	0.278	0.280	0.276	0.278	0.280	0.276
One-stage EB, two-level	0.209	0.218	0.224	0.243	0.277	0.337
One-stage EB, two-level, $\bar{b}_{h,e}=2$	0.374	0.380	0.381	0.391	0.409	0.436

Table 3: Mean regret certificate

\overline{R}

over 200 replications at

n_{h}=400

, as a function of the redundancy envelope

\varepsilon

. Rows marked “ratio” divide the two-level certificate by the corresponding flat one.

Figure 2: Ratio of the mean two-level certificate to the mean flat certificate at $n_{h}=400$ , as a function of the redundancy envelope $\varepsilon$ ; values below $1$ indicate a gain from the multiscale network.

Regret Minimization

Regret minimization studies how to make sequential decisions whose cumulative loss or reward approaches the best available comparator in hindsight.

See all 111 papers

The Price of Choice in Selective Prediction
Oct 21, 2026Daniel Cieślak, Andrzej CzyżewskiSelective Prediction Algorithmic Auditing
Gdańsk University of Technology Gdańsk, Poland
Re:CAP - Auditing Retrieval Coverage in Production RAG Pipelines
Sep 21, 2026Aviral Joshi, Hanoz Bhathena, Max Nelson +1RAG Evaluation IR Evaluation
Machine Learning Center of Excellence, JPMorgan Chase & Co.
Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design
Jul 23, 2026Martin Anthony, Kaveh Salehzadeh NobariAlgorithmic Auditing
Data Science Institute, London School of Economics and Political Science · Department of Mathematics, London School of Economics and Political Science · The Inclusion Initiative, London School of Economics and Political Science

Oct 21, 2026J/K move · Enter open · S save

The Price of Choice in Selective Prediction

Daniel Cieślak, Andrzej Czyżewski

Gdańsk University of Technology Gdańsk, Poland

Selective Prediction Algorithmic Auditing Sample Complexity Multiple Hypothesis Testing

Open paper AskPDF arXiv

A selective classifier may be claimed to satisfy a risk-coverage contract if some rule from a predeclared menu (a threshold or a union of

K

score intervals) attains coverage at least

κ

and error at most

α

. Refuting this existential claim requires ruling out every permitted rule. The intersection-union test (IUT) achieves validity without a multiplicity correction, but its sample cost can increase with menu richness. We characterize this cost and compare it with the optimal audit. For a fixed interior risk target

α

and gap

γ

, the minimax sample size for K-interval menus at coverage floor

κ

K(1-κ)/(κγ^2)

, up to logarithmic factors, in the stated small-gap, large-menu regime; exact IUT attains this rate. The lower bound holds even with a known score distribution, while the upper bound extends to menus of VC dimension

d

. Procedures that refuse to reject whenever any rule appears feasible on the audit sample can pay a linear

K

cost even when a square-root rate is possible. Reference-free testing reaches a smaller scale under constant-risk alternatives, whereas unknown heterogeneous risks can make the linear cost unavoidable. In simulations with

K=4

, the raw menu cost varies 7.7-fold between

κ=.5

and

κ=.95

; after theorem-motivated normalization the endpoint values differ by approximately 5%. Held-out experiments with three VLM judges show positive exact-hiding windows in all 60 split-specific confidence-gate families, with 28/30 contracts chosen on audit-A remaining hidden on untouched audit-B. On a cleaner multi-annotator target, hiding is weaker and transfers in 3/10 resplits. Frozen image and multimodal classifiers show boundary behavior consistent with the IUT guarantee and strong power relative to practical certificates.

Abstract

Regret Minimization

Explore similar work

The Price of Choice in Selective Prediction

Re:CAP - Auditing Retrieval Coverage in Production RAG Pipelines

Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design