Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design
Exact excluded-pool audits certify missed mass; in the zero-miss regime, the optimal label complexity is Ω(N₀/m).
Key Findings
Methodology
The paper separates a generator g into included and excluded pools and defines missed mass r(g)=P(Y=1,g(X)=0), miss rate L(g), and Recall(g). After fixing the generator and audit rule, it uses independent sampling or finite-population sampling without replacement. Exact one-sided certificates are obtained by inverting binomial or hypergeometric distributions rather than relying on asymptotic approximations.
Key Results
- Proposition 3 proves that labels from the included pool, even with unlimited unlabelled data, cannot produce a non-trivial upper bound on missed mass, because every missed relevant item lies in the excluded pool.
- Theorem 13 shows that, on a finite corpus, any valid audit that rules out fewer than m missed relevant items with high probability under zero misses must inspect Ω(N₀/m) excluded items on average, even if it is adaptive and labels the entire included pool.
- Theorems 7, 8, 10, 12, 17, 19, and 24 provide certificates for population missed mass, finite-corpus missed counts, two-pool recall, prefix families, sequential stopping, and combined component detectors; all use exact inversion.
Significance
The work addresses an overlooked failure in high-recall pipelines: relevant items excluded at the first stage are irrecoverable by later review, labelling, or modelling. It turns the location of audit labels into a principled statistical design question. The results are directly relevant to legal discovery, systematic reviews, compliance screening, annotation-data construction, and retrieval-augmented generation, where over-inclusion costs labour but exclusion destroys information.
Technical Contribution
The main theoretical contributions are an included-pool impossibility result, a matching finite-corpus lower bound, and minimax-rate optimality of excluded-pool auditing in the zero-miss regime. The toolkit adds exact binomial and hypergeometric inversion, two-pool recall bounds, simultaneous certification for pre-specified nested prefixes, shared-reference designs, burden-minimising stopping, and perturbation stress tests. PAC, VC, sparse-union, and Neyman–Pearson methods can select generators on separate design data.
Novelty
Unlike Learn then Test and Conformal Risk Control, which offer general risk-control templates, this paper characterises the label complexity imposed by candidate-generation geometry and proves that auditing must enter the excluded pool. Relative to technology-assisted-review stopping rules, it adds a matching lower bound, minimax optimality, exact two-pool recall certification, and simultaneous prefix guarantees.
Limitations
- The theory assumes noiseless relevance labels. Legal, medical, or retrieval judgements may be subjective, so applying these bounds directly can understate uncertainty unless annotation error is modelled.
- The generator and audit rule must be fixed before certification labels are examined. Redesigning a generator after seeing audit misses and reusing the same labels invalidates the guarantee.
- The supplied paper text reports no real dataset, benchmark table, or numerical accuracy comparison; its primary evidence is theoretical and deterministic audit calculation.
Future Work
Future research should incorporate annotation noise, stratified and query-conditional audits, rare-relevance regimes, and valid adaptive budget allocation. A practical direction is joint optimisation of coverage, review cost, latency, and energy, followed by deployment studies in legal review, systematic-review screening, and RAG corpora.
AI Executive Summary
High-recall pipelines often begin with a keyword search, retrieval system, rule set, or classifier that decides which items receive human review. Their asymmetric risk is easy to miss: irrelevant inclusions consume labour, but relevant exclusions disappear from every downstream stage. Standard recall estimates and normal-approximation intervals do not solve this problem, especially when audits label only included items.
Anthony and Salehzadeh Nobari introduce an exact finite-sample Coverage Audit framework. Its central design samples the excluded pool, where missed relevant items can actually occur. Binomial inversion handles independent population sampling; hypergeometric inversion handles sampling without replacement from a finite corpus. A two-pool design combines excluded-pool evidence with included-pool evidence to produce a recall lower bound. Pre-specified nested generators can be certified simultaneously and selected by review burden.
The theory gives a sharp quantitative message. Proposition 3 establishes included-pool impossibility. Theorem 13 proves that ruling out fewer than m missed relevant items in the zero-miss regime requires Ω(N₀/m) excluded-pool inspections on average, while Corollary 15 shows that uniform excluded-pool auditing attains the same order. The framework also supports sequential stopping, learning-theoretic design, and declared perturbation stress tests. Its guarantees depend on design–certification separation, and the supplied text contains no real-dataset performance table; the contribution is a rigorous, deployable theory of coverage certification.
Deep Analysis
Background
High-recall candidate generation supports technology-assisted review, systematic-review screening, compliance audits, annotation pipelines, and RAG retrieval. PAC and VC theory control selection from structured classes, while Learn then Test and Conformal Risk Control provide distribution-free risk-control templates. However, these tools do not identify the correct audit region or establish the minimum labels required to certify missed relevant mass. This paper targets that geometric gap.
Core Problem
For generator g and latent relevance Y, missed mass is r(g)=P(Y=1,g=0), miss rate is L(g)=P(g=0|Y=1), and recall is 1-L(g). The objective is to certify that r(g), or the finite-corpus missed count, is below a target with finite-sample validity. The difficulty is structural: all false negatives lie in the excluded pool, whose labels are unobserved.
Innovation
Proposition 3 proves that included-pool labels cannot yield a non-trivial missed-mass bound. Theorem 13 establishes the matching Ω(N₀/m) lower bound for finite corpora, proving that excluded-pool auditing is minimax-rate optimal rather than merely intuitive. The paper then extends exact inversion to two-pool recall, simultaneous pre-specified prefixes, sequential stopping, component-detector aggregation, and stress tests against declared perturbations.
Methodology
- �� Fix the generator or prefix family before opening certification labels.
- �� Draw excluded items independently and invert a binomial model to upper-bound population missed mass.
- �� For a finite corpus, sample uniformly without replacement from N₀ excluded items and invert the hypergeometric distribution to bound M₀(g).
- �� Audit included and excluded pools separately; combine estimates of M₁ and M₀ to bound Recall=M₁/(M₀+M₁).
- �� Certify pre-specified nested unions using separate audits or a shared reference sample.
- �� Stop at the least burdensome prefix meeting the target, while preserving validity through a pre-declared stopping rule.
- �� Use design data with PAC, VC, sparse-union, or Neyman–Pearson methods, then certify on an independent holdout.
Experiments
Section 8 gives a numerical worked example based on deterministic audit calculations, but the supplied text does not identify a named dataset, learned model baseline, hyperparameter grid, or benchmark score. The empirical demonstrations concern sample-size calculations, exact binomial and hypergeometric bounds, burden-minimising stopping, shared-reference certification, and stress-test certificates across the population, finite-corpus, two-pool, and prefix settings.
Results
The central numerical rate is label complexity: excluding fewer than m missed relevant items under zero observed misses requires an average of order Ω(N₀/m) excluded-pool labels. Uniform excluded-pool sampling achieves this order for fixed error parameters. Theorems 7, 8, 10, and 12 establish the basic certificates; Theorems 17 and 19 extend them to simultaneous sequences and valid stopping; Theorems 24 and 29 address component capture and variant escape.
Applications
Legal-review teams can sample documents not returned by a search system and certify an upper bound on missed responsive material. Systematic-review groups can audit excluded studies; compliance teams can inspect filtered transactions; RAG developers can sample unretrieved query–passage pairs. Each application requires a frozen generator, an independent audit sample, and a sufficiently reliable relevance oracle.
Limitations & Outlook
The framework assumes noiseless labels, fixed candidate generators, declared sampling designs, and valid pre-specified stopping rules. Absolute missed mass may be weak when prevalence is rare: if π=0.01 and r(g)≤0.005, the implied recall bound is only Recall≥0.5. The text also provides no real-corpus cost comparison or benchmark performance. Extensions should address noisy labels, stratification, query-level guarantees, adaptive sampling, and joint cost–coverage optimisation.
Plain Language Accessible to non-experts
Imagine an airport that sorts passengers into two queues: people allowed into the terminal and people turned away. Staff can inspect the first queue later, but anyone turned away receives no further check. Finding few suspicious passengers inside tells you almost nothing about the people outside; the missing passengers can only be there.
The paper’s solution is to sample the outside queue directly. Inspect a random group and ask a trusted officer whether each person is important. If no important people appear, exact mathematics can state how many important people could still be hidden, with a chosen confidence level. If the outside queue has N₀ people and you want to rule out fewer than m hidden important people, the required inspection size is roughly N₀/m. This is not just a convenient shortcut: the paper proves that reliable methods cannot generally do better.
Several sorting plans can be prepared in advance, from strict to generous. The airport can then choose the smallest plan whose hidden-passenger certificate is good enough, saving staff time. But if officials inspect answers first and redesign the plan to fit them, the original guarantee no longer applies. The method therefore separates planning from final inspection.
ELI14 Explained like you're 14
Suppose you want to find every student who might join a robotics club. First, you use keywords, posts, or recommendations to make a shortlist. Teachers will train only students on that list. The dangerous mistake is not inviting a few students who are uninterested; it is missing a real robotics fan, because that student may never get another chance.
Here is the clever part: checking only the shortlist cannot prove that the missing pile is safe. You must randomly check students who were not shortlisted. If you check many and find nobody suitable, you can calculate how many suitable students might still be hiding. If there are N₀ students outside and you want to rule out fewer than m missed club members, the paper says the check must be about N₀/m in size. Even a super-smart strategy cannot magically avoid this basic cost!
You can also prepare several shortlists, from small to large, and choose the least exhausting one that is reliable enough. But there is a rule: decide the shortlists before looking at the final checking answers. Otherwise you could secretly change the rules after seeing clues, and the promise of fairness disappears.
This idea works for finding legal documents, screening scientific papers, checking suspicious transactions, or retrieving evidence for an AI. It assumes the checker labels items correctly. The paper mainly gives trustworthy mathematics, not a scoreboard showing one model beating another.
Glossary
Missed mass
The population mass that is both relevant and excluded by g. Formally, r(g)=P(Y=1,g(X)=0).
It is the primary quantity certified by excluded-pool audits.
Excluded pool
The set of items for which g(X)=0. Any relevant item missed by the generator must be in this region.
Theorem 7 and Theorem 13 establish why this is the necessary audit domain.
Recall
The fraction of all relevant items included by the generator: Recall(g)=P(g=1|Y=1)=1-L(g).
Theorem 10 derives a lower recall bound using included- and excluded-pool samples.
Binomial inversion
A finite-sample procedure that inverts the binomial sampling distribution to obtain a one-sided upper confidence bound for an unknown proportion.
It is used for independent draws from the excluded pool.
Hypergeometric inversion
Exact inversion of the without-replacement sampling distribution in a finite population. It bounds the number of relevant items in the unsampled remainder.
Theorem 8 applies it to finite-corpus missed-count certification.
Design–certification separation
The generator, family, and audit rule are fixed before certification labels are examined. Design data may train or tune a generator, but certification labels must remain held out.
Assumption 1 supports every validity guarantee in the paper.
Open Questions Unanswered questions from this research
- 1 How can exact coverage guarantees survive noisy or inconsistent relevance labels? A useful extension would combine annotation-error models with binomial and hypergeometric inversion.
- 2 Absolute missed mass can be uninformative when relevance is rare. Stratified, query-conditional, and per-group recall certificates need sharper theory.
- 3 The paper does not quantify deployment costs on real corpora. Comparative studies of adaptive allocation, audit budgets, and human review efficiency remain open.
Applications
Immediate Applications
Legal discovery validation
Freeze a search rule, randomly sample documents it excluded, and obtain reliable relevance labels. Hypergeometric inversion can certify an upper bound on missed responsive documents while the included-pool size measures review burden.
RAG retrieval coverage
Sample unretrieved query–passage pairs and label whether they contain evidence needed for the answer. The resulting excluded-pool certificate quantifies retrieval omissions, provided relevance is defined consistently and audited independently.
Long-term Vision
Auditable candidate-generation platforms
Integrate PAC or VC-based design with independent certification, automatic sample-size calculation, simultaneous prefix testing, and burden-aware selection. Such systems could generate regulator-ready coverage reports for high-stakes data pipelines.
Abstract
An initial high-recall stage in an empirical pipeline decides which items pass to later review, labelling, or modelling, and relevant items it misses are lost to every subsequent stage. We study how many audit labels are needed to certify, with finite-sample validity, that this missed relevant mass is small, and our main results characterise the label complexity of this problem. We first show that no procedure using only labels from inside the candidate set can certify any non-trivial bound on the missed mass: the audit must sample the excluded pool, the only region where unrecovered relevant items can lie. We then prove a matching finite-corpus lower bound. Any valid audit that certifies fewer than $m$ missed relevant items with high probability when none are present, even if adaptive and permitted to label the entire included pool, must inspect on the order of $N_0/m$ excluded-pool labels. Excluded-pool auditing is therefore minimax rate-optimal, not merely convenient, for missed-mass certification in the zero-miss regime. Building on this characterisation, we develop an exact finite-sample toolkit, using binomial and hypergeometric inversion rather than asymptotic approximation, that certifies missed mass, converts it to recall through a two-pool design, certifies pre-specified families of nested candidate generators simultaneously, and produces stress-test certificates against declared perturbation mechanisms. These certificates can be paired with observable review burden to select the least burdensome pre-specified candidate generator meeting a missed-mass target. Every guarantee holds under one discipline: the candidate generator, or the pre-specified family from which it is selected, and the audit rule are fixed before the certification labels are examined.