---
title: "Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2607.21480v1"
permalink: "https://feed.astralor.com/items/itm_3b82917c630df5b48e5da48e"
published: "2026-07-23T16:21:30.000Z"
score: 78
channel: "ai"
tags: ["Candidate Generation","audit","finite-sample","certification"]
---

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

## AI commentary

> This paper's core contribution is revealing the label complexity nature of high-recall candidate set auditing, especially the counterintuitive proof that looking only within the candidate set cannot certify misses. This has significant guidance for practical system design. Practitioners in e-discovery, medical screening, and other recall-critical fields will find the exact finite-sample toolkit invaluable for improving audit credibility and efficiency. I recommend this paper to any researcher or engineer concerned with AI system reliability assessment.

## At a glance

This paper studies the label complexity of auditing high-recall candidate generation, proving that sampling only within the candidate set cannot certify the missed relevant mass; the audit must sample the excluded pool. The authors derive a minimax lower bound in the zero-miss regime and develop an exact finite-sample toolkit using binomial and hypergeometric inversion to certify missed mass, convert it to recall via a two-pool design, simultaneously certify pre-specified families of nested candidate generators, and produce stress-test certificates against declared perturbation mechanisms. All guarantees hold under the discipline that the candidate generator (or its pre-specified family) and the audit rule are fixed before examining certification labels.

## Key points

- Any audit using only labels from within the candidate set cannot certify a non-trivial bound on missed relevant items; the excluded pool must be sampled.
- In the zero-miss regime, the lower bound on the number of excluded-pool labels required for a valid audit is on the order of N0/m, and excluded-pool auditing is minimax rate-optimal.
- The toolkit employs binomial and hypergeometric inversion for exact finite-sample certification of missed mass, recall conversion, simultaneous certification of nested generators, and stress-test certificates against declared perturbations.
- All guarantees rely on the discipline that the candidate generator (or its pre-specified family) and the audit rule are fixed before examining certification labels.

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_3b82917c630df5b48e5da48e