Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design
Audits cannot certify missed relevant items without sampling what the candidate generator left out.
Anthony and Salehzadeh Nobari show that labels from inside the candidate set are insufficient for any non-trivial missed-mass guarantee. Their lower bound says a valid zero-miss audit must inspect on the order of `N0/m` excluded-pool labels to certify fewer than `m` missed relevant items. The paper then builds exact finite-sample certificates using binomial and hypergeometric inversion, including recall conversion, nested generator selection, and perturbation stress tests. The guarantees require the generator family and audit rule to be fixed before certification labels are examined. ArXiv · AI/CL/LG's note
Anthony and Salehzadeh Nobari show that labels from inside the candidate set are insufficient for any non-trivial missed-mass guarantee. Their lower bound says a valid zero-miss audit must inspect on the order of `N0/m` excluded-pool labels to certify fewer than `m` missed relevant items. The paper then builds exact finite-sample certificates using binomial and hypergeometric inversion, including recall conversion, nested generator selection, and perturbation stress tests. The guarantees require the generator family and audit rule to be fixed before certification labels are examined. ArXiv · AI/CL/LG's note
score 4