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

arXiv: https://arxiv.org/abs/2607.21480 · HTML: https://mlsanity.com/paper/2607.21480/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 51 references that are in the map.
- First posted on arXiv 23 Jul 2026.

## Builds on (most cited first, 9 of 9)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Autonomy and Reliability of Continuous Active Learning for Technology-Assisted Review](https://mlsanity.com/paper/1504.06868/) (2015)
- [Heuristic Stopping Rules For Technology-Assisted Review](https://mlsanity.com/paper/2106.09871/) (2021)
- [Certifying One-Phase Technology-Assisted Reviews](https://mlsanity.com/paper/2108.12746/) (2021)
- [Facet-Level Tracing of Evidence Uncertainty and Hallucination in RAG](https://mlsanity.com/paper/2604.09174/) (2026)
- [Generalised Eigenvalue Geometry of Semantic Adversarial Attacks](https://mlsanity.com/paper/2606.19212/) (2026)

## Built on by (most cited first, 1 of 1)

- [When May a Model Replace the Experiment? Audits, Licenses, and the Price of Trust in Surrogate-Driven Design](https://mlsanity.com/paper/2608.01378/) (2026)

## Abstract (arXiv)

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 N0/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.