Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design Martin Anthony1,2
Kaveh Salehzadeh Nobari1,3
1
2
Data Science Institute, London School of Economics and Political Science Department of Mathematics, London School of Economics and Political Science 3 The Inclusion Initiative, London School of Economics and Political Science
arXiv:2607.21480v1 [cs.LG] 23 Jul 2026
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 N0 /m excluded-pool labels. Excludedpool 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.
1
Introduction
Many machine learning and data-engineering pipelines begin with a high-recall candidategeneration step. Given a large corpus and a latent relevance criterion, an initial candidate generator selects a subset of items for later review, labelling, or downstream modelling. The intended role of this first stage is coverage: it should capture nearly all relevant items, even at the cost of admitting many irrelevant ones. Excluding relevant observations from the training sample can induce sample-selection bias when the exclusion mechanism is non-random, because the empirical training distribution may no longer represent the target population. If the exclusions are random, the main effect is typically loss of precision rather than bias [22, 29, 30]. This class of problems has a structurally asymmetric error profile. Relevant items missed at the candidate-generation stage are irrecoverable: they cannot be reviewed, cannot be labelled, and cannot be learned by any downstream model trained on the resulting candidate set. Overinclusion, by contrast, increases review burden but does not destroy information. Examples include responsiveness review in legal discovery, study screening in systematic reviews, compliance and regulatory audit, and pipelines in which annotated training data is derived from a 1
filtered corpus. In technology-assisted legal review and systematic-review screening, for instance, an initial search or classifier returns documents or studies for human assessment. Items not returned may never be examined, so the quantity of interest is the relevant material left outside the returned set. The objective in these settings is to construct a candidate set Sb ⊆ X that captures nearly all latent relevant instances with high probability while keeping the review cost tolerable, where X denotes the population, or item, space. The candidate set is then handed to human annotators, downstream classifiers, or both. The statistical task is to certify, from audit data, that the missed relevant mass is small. Many audit summaries report estimated recall together with approximate confidence intervals. Our aim is different: we derive finite-sample one-sided certificates for missed relevant mass and recall, using binomial or hypergeometric inversion according to the sampling design. Several existing frameworks provide useful ingredients. Classical PAC learning provides distribution-free guarantees on generalisation error [3, 46]. Candidate generation asks instead for one-sided coverage of a latent relevant set. Recent distribution-free risk-control frameworks (e.g., Learn then Test [1], Conformal Risk Control [2]) provide general finite-sample machinery for controlling expected losses, including risks such as false negative rate. We specialise these ideas to high-recall candidate generation, where the central statistical design choice is where to spend labels. We first analyse fixed candidate generators, then extend the guarantees to finite families of generators chosen after seeing non-audit data. The certification audit remains untouched while the candidate generator is chosen. We may use separate design labels to choose a candidate generator from a structured class, but the final certificate uses only the held-out audit labels. In Section 7 we record the finite-class, VC, sparse-union, and Neyman–Pearson guarantees needed for this design stage, and we show how to pair them with independent audit certification. In Section 8 we give a compact numerical example using only deterministic audit calculations.
1.1
Motivating examples
We give two motivating examples drawn from opposite ends of the modelling process. The first is pre-transformer : a data-engineering pipeline that prepares a corpus for human annotation, of the kind later used to train or evaluate models. The second is post-transformer, arising at inference time: the retrieval stage of retrieval-augmented generation (RAG), in which relevant passages are supplied to a language model to ground its output. The two settings look unrelated, but both instantiate the same object, namely a filter over a corpus whose items carry a latent relevance label. In both, a relevant item missed by the filter is irrecoverable at every later stage, and this asymmetry is what the certificates in this paper are designed to control. A pre-transformer instance: building annotation data. Consider a pipeline for building labelled data on sentences related to a specified concept, such as diversity, equity, and inclusion disclosures in annual reports of publicly traded firms. The documents are long, and the relevant concept may be expressed in heterogeneous, indirect, and context-dependent language. Before any large-scale review, measurement, or downstream modelling can be carried out, the analyst must decide which sentences will be sent for human annotation. A common first step is to apply a candidate generator g, which selects sentences deemed potentially relevant. The generator may use keyword lists, regular expressions, similarity thresholds, embedding searches, supervised classifiers, or combinations of such rules. Human annotators then label the selected sentences as relevant or not. The resulting labels may be used as the final annotated dataset, or they may later be used to train a supervised classifier. The audit problem concerns the candidate generator g. If g excludes relevant sentences, those sentences are unavailable to later review, and they are absent from any labelled data built from the selected set. The purpose of the audit is therefore to certify that the relevant mass left 2
outside the candidate set is small. When the candidate generator is itself learned, the same distinction applies. We may use design labels to train or tune a classifier φ, b and then use this classifier as the candidate generator. The held-out audit labels are not used to choose φ. b They are used only to certify the missed relevant mass, or recall, of the resulting selection rule. The labelled candidates do not by themselves contain the information needed to certify missed mass: annotators see only the selected items and observe no labels for excluded ones. Proposition 3 makes the resulting impossibility precise, and motivates the finite-sample audit formulation. A post-transformer instance: retrieval-augmented generation. The same asymmetry appears in the retrieval stage of retrieval-augmented generation (RAG), in which a retriever selects a small set of passages from a large corpus and a language model conditions its answer on that selected set [28]. Here the items being evaluated are query–passage pairs (q, x), where q is a query and x is a passage from the corpus. The candidate generator g(q, x) is the retriever together with its cutoff, with g(q, x) = 1 when passage x is retrieved for query q, and the latent relevance label φ⋆ (q, x) indicates whether x contains evidence required to answer q correctly. If the retriever fails to return a relevant passage for a given query, that passage is absent from the model’s context and cannot be used as retrieved evidence to ground the subsequent answer. This is the irrecoverable false negative of the present setting, and it is distinct from the muchstudied failure in which relevant evidence is retrieved but the generator ignores or contradicts it [17]. That latter failure is a question of generation faithfulness rather than coverage, and our certificates do not address it. What an excluded-pool audit certifies is precisely the coverage side: sampling query–passage pairs for which g(q, x) = 0 and labelling whether φ⋆ (q, x) = 1 bounds the relevant evidence mass left outside the retrieved sets, with the finite-sample guarantees of Section 4. As in the pre-transformer example, relevance is a fixed property of a query– passage pair and is checkable by an oracle, while an excluded relevant passage is unavailable to the downstream generator as retrieved evidence. These two conditions are what make the missed-mass certificate meaningful. Because relevant query–passage pairs may be rare in a large retrieval corpus, conditional targets such as recall, positive-conditional audits, or per-query stratified certificates may be more operationally meaningful in this setting than absolute missed mass alone.
1.2
Contributions
Our main results characterise the label complexity of missed-mass certification. 1. Impossibility: Labels from inside the candidate set, together with the generator values and unlimited unlabelled data, cannot certify any non-trivial bound on missed mass (Proposition 3). The audit must sample the excluded pool. 2. Matching lower bound and optimality: In the finite-corpus model, any valid audit that successfully rules out m missed relevant items with high probability in the zero-miss case must inspect Ω(N0 /m) distinct excluded-pool items on average, even if the audit is adaptive, randomised, and permitted to label the entire included pool (Theorem 13). A simple uniform excluded-pool audit that observes zero relevant items achieves the same N0 /m scaling, up to a constant factor for fixed error parameters. Thus, excluded-pool auditing is minimax rate-optimal for missed-mass certification in the zero-miss regime (Corollary 15). The remaining contributions turn this principle into an exact, deployable audit workflow. 3. Exact finite-sample certification for excluded-pool, finite-corpus, two-pool recall, and prespecified prefix audits (Section 4). 3
4. Operational tools: sample-size calculations, burden-minimising stopping, shared-reference designs, and fixed-sequence certification without a multiplicity penalty (Sections 4.6, 4.8). 5. Auditable diagnostic and stress-test certificates (Sections 5, 6). 6. A learning-theoretic design layer with independent held-out certification (Section 7 and Appendix A). 7. A numerical worked example (Section 8).
1.3
Relation to existing work
Learn then Test [1] and Conformal Risk Control [2] provide general distribution-free risk-control templates. The contribution here is more specialised: the audit uses the geometry of candidate generation. Crucially, those general templates provide risk control for fixed procedures or prespecified families, but do not characterise how many labels this candidate-generation problem requires or where those labels must be drawn. The impossibility result and the lower bound are questions about the candidate-generation structure itself, and have no analogue in the general risk-control machinery. Missed items can occur only in the excluded pool, the excluded-pool mass p0 (g) is observable without relevance labels, and pre-specified prefix families give natural targets for simultaneous certification. The excluded-pool certificates exploit the decomposition r(g) = p0 (g)η(g), where η(g) is the fraction of those excluded items that are truly relevant, rather than treating misses as rare events in the whole population. The closest applied lineage is technology-assisted review and systematic-review screening. Work in e-discovery and high-recall review developed relevance feedback, continuous active learning, stopping rules, and recall validation methods [10–13, 26, 27, 31, 40, 48, 50]. The certificates here formalise the same sampling geometry with exact finite-sample one-sided statements, including excluded-pool missed-count certification, two-pool recall certification, and simultaneous certification of pre-specified prefix families. A related validation design in technology-assisted review estimates found and missed relevant items from separate samples [20]. Our results give distribution-free finite-sample versions of this idea. Webber [48] shows that the normal approximation to recall covers poorly in this setting, studies two-tailed approximate intervals that target mean rather than guaranteed coverage, and lists one-sided lower bounds and guaranteed-coverage methods as future work. The two-pool certificates of Section 4 supply guaranteed-coverage onesided bounds of exactly this kind. Closest to the finite-corpus certificates below, Callaghan and Müller-Hansen [7] use a hypergeometric test as a stopping criterion that certifies a recall target at a stated confidence in active-learning screening. Relative to that line of work, the present paper adds i) the included-pool impossibility result (Proposition 3), ii) the matching label-complexity lower bound and the resulting minimax optimality of excluded-pool auditing (Theorem 13, Corollary 15), iii) simultaneous certification of pre-specified prefix families, iv) the exact two-pool combination for recall, and v) the explicit separation of design from certification (Assumption 1). Items (i) and (ii) are specific to the candidate-generation geometry and have no counterpart in a hypergeometric stopping rule. The certificates here do not rely on a model of the rate at which relevant items appear. The design-stage material uses standard learning-theoretic tools. The bicriteria formulation is the Neyman–Pearson approach [8, 36, 38, 42] transposed to candidate generation:1 review burden is minimised subject to a one-sided missed-mass constraint. PAC and VC bounds [3, 6, 33, 46] control the selection of a candidate generator from a structured class before independent audit certification. 1
The empirical bicriteria formulation was first proposed by Cannon, Howse, Hush, and Scovel in a 2002 Los Alamos technical report (LA-UR-02-2951). The original Los Alamos host is no longer available, though the report remains retrievable through the Internet Archive. The rigorous published treatment is given by [38].
4
There is also a conceptual connection with set estimation [14, 35, 39, 43, 49]. The candidate set is asked to cover most of the latent relevant-item distribution while keeping burden small. The difference is operational: here the set being certified is fixed, or pre-specified, before the certification labels are opened, and the audit can be targeted to the excluded pool.
2
Problem setup
We use two formulations. In the i.i.d. population model, items are drawn from an underlying distribution P . In the finite-corpus model, we treat the N corpus items, the relevance labels, and the candidate generator as fixed. The probability statements refer only to the random choice of audit sample. We use the population formulation for the main theoretical statements. We use the finite-corpus formulation for sampling-without-replacement certificates and for the connection to existing technology-assisted review practice.
2.1
Population model
Let (X , F, P ) be the population probability space. We use the canonical random element X : (X , F, P ) −→ (X , F),
X(ω) = ω.
Thus the outcome ω is itself the sampled population item, and the law of X is P . Let φ⋆ : (X , F) −→ {0, 1}, 2{0,1} be a measurable latent relevance indicator, and define Y := φ⋆ (X). Equivalently, Y (x) = φ⋆ (x) for x ∈ X . The induced joint law of (X, Y ) on X × {0, 1}, F ⊗ 2{0,1} is the pushforward measure PX,Y := P ◦ T −1 ,
T (x) := (x, φ⋆ (x)) .
The function φ⋆ is fixed but unknown to the analyst. It represents the ground-truth criterion determining whether an item is relevant, for example legal responsiveness, study eligibility, or policy applicability. The analyst observes φ⋆ only through audit labels on sampled items. Write S ⋆ := {x ∈ X : φ⋆ (x) = 1}, π := P (S ⋆ ) = P (Y = 1). A candidate generator is a measurable function g : (X , F ) −→ {0, 1}, 2{0,1} , with candidate set Sb := {x ∈ X : g(x) = 1}. For population events, P always denotes the probability measure on the canonical space (X , F). Thus, for example, P (Y = 1, g(X) = 0) := P ({x ∈ X : φ⋆ (x) = 1, g(x) = 0}) . Equivalently, such probabilities may be evaluated under the induced joint law PX,Y , but we suppress that subscript throughout. 5
Audit, design-sample, and algorithmic randomness are carried on probability spaces separate from the population space. For a given audit design, let (ΩA , AA , PA ) denote the probability space carrying the random audit sample and any independent randomisation used by the audit procedure. The population objects P , φ⋆ , and the candidate generator or generator family being certified are fixed under PA . We write Paudit for the probability measure induced by the audit design and Pdesign for the probability measure induced by a separate design sample. These symbols are theorem-specific: the sampling scheme stated in each result determines the corresponding probability measure. Throughout, P denotes the population law of X, and hence the induced law of (X, Y ). We use P for probabilities over auxiliary randomness, such as audit samples, design samples, randomised procedures, and binomial or hypergeometric variables. Subscripts indicate the source of randomness when it is important, for example Paudit and Pdesign . For a candidate generator g, define r(g) := P (Y = 1, g(X) = 0), L(g) := P (g(X) = 0 | Y = 1), Recall(g) := P (g(X) = 1 | Y = 1) = 1 − L(g), b(g) := P (Y = 0, g(X) = 1), p0 (g) := P (g(X) = 0), p1 (g) ≡ B(g) := P (g(X) = 1) = 1 − p0 (g). The conditional quantities L(g) and Recall(g) are defined when π = P (Y = 1) > 0. The quantity r(g) is the absolute missed relevant mass, L(g) is the conditional miss rate (so Recall(g) = 1 − L(g) is the recall of g), b(g) is the false-positive mass (wasted review), B(g) is the review burden (the probability that an item is sent for review), and p0 (g) = 1−B(g) is the excluded-pool mass. When π > 0, r(g) = πL(g), so an upper bound u on r(g) implies L(g) ≤ u/π when π is known. Table 1 displays these quantities as probability masses in a candidate-generation confusion matrix. The distinction matters in rare-relevance settings. If π = 0.01 and an audit certifies r(g) ≤ 0.005, the implied bound is L(g) ≤ 0.5, equivalently a recall of at least 0.5, which is not a high-recall guarantee. A candidate generator may be a single rule, a single classifier, or a union of J component detectors h1 , . . . , hJ : X → {0, 1}. We use the term component detector for the primitive functions hj from which some candidate generators are built. The main object certified by the audit is always the candidate generator g. For any t ∈ {1, . . . , J}, define the prefix union gt (x) := max hj (x). j≤t
In practice, the components are often constructed sequentially, with each new hj designed to recover relevant items missed by the partial union of those built so far. In other words, the candidate set expands monotonically, i.e., Sb1 ⊆ Sb2 ⊆ . . . ⊆ SbJ . We call gt a prefix of the ordered sequence, and gJ is the full union. Adding components to a union can only reduce missed relevant mass (and conditional miss rate), at the cost of an increase in review burden. The certification theorems below treat g as an arbitrary fixed measurable function. We use the prefix structure later to define stopping rules along the ordered 6
Candidate generator Ground truth
Y =1 relevant
Y =0 not relevant
g(X) = 1
g(X) = 0
included for review
excluded from review
True positive
False negative
recovered relevant mass
missed relevant mass
P (Y = 1, g(X) = 1) = π − r(g) = π[1 − L(g)]
P (Y = 1, g(X) = 0) = r(g) = πL(g)
False positive
True negative
unnecessary review mass
correctly excluded mass
P (Y = 0, g(X) = 1) = b(g)
P (Y = 0, g(X) = 0) = p0 (g) − r(g)
Total
L(g) =
B(g)
p0 (g)
review burden
excluded-pool mass
false-negative mass r(g) = , total relevant mass π
Total
π
1−π 1
Recall(g) = 1 − L(g).
Table 1: Probability-mass confusion matrix for a candidate generator. sequence and to certify all prefixes with a single shared audit sample. We reserve J for the number of component detectors and use M for the number of pre-specified prefixes considered for certification, since the number of prefixes considered need not equal J. The subscripted counts M0 (g) and M1 (g) and the inversion bound MU defined below are distinct from M . The symbol Q always denotes the size of the audit sample under discussion.
2.2
Finite-corpus model
In applications, the population is typically a finite corpus XN = {x1 , . . . , xN }. For a fixed candidate generator g : XN → {0, 1}, write zi = g(xi ),
yi = φ⋆ (xi ),
i = 1, . . . , N.
Thus zi records whether item xi is selected by the generator, while yi records whether it is relevant. Write N0 (g) = |{i : zi = 0}|,
N1 (g) = |{i : zi = 1}|,
M0 (g) = |{i : zi = 0, yi = 1}|,
M1 (g) = |{i : zi = 1, yi = 1}|,
where |A| denotes the cardinality of set A. The candidate-generator values zi are observable for every item in XN . The relevance labels yi are observable only on items selected for audit. The finite-corpus empirical fractions, the analogues of the population probabilities, are p0,N (g) =
N0 (g) , N
BN (g) =
N1 (g) . N
Thus p0,N (g) corresponds to p0 (g) = P (g(X) = 0), and BN (g) corresponds to B(g) = P (g(X) = 1), under the i.i.d. population model. The finite-corpus recall, defined when M0 (g) + M1 (g) > 0, is M1 (g) Recall(g) = . M0 (g) + M1 (g)
7
2.3
Audit model
Operationally, an audit is the mechanism that converts selected unlabelled items into labelled items. In the finite-corpus model, before auditing, the corpus XN = {x1 , . . . , xN } is fixed. We use the notation zi = g(xi ) and yi = φ⋆ (xi ) introduced above. The values zi are known for every item, while the relevance labels yi are latent. An audit chooses a subset S ⊆ {1, . . . , N }, possibly at random according to a declared sampling design, sends those items to a labelling oracle, and returns {(xi , yi ) : i ∈ S}. In the i.i.d. population model, the same object is a labelled sample (Xi , φ⋆ (Xi )) drawn from a specified sampling distribution. Each result below uses a specified sampling design and certifies a specified error quantity. The table gives the informal content of the main guarantees. Result Theorem 7
Theorem 8
Theorem 10 Theorem 12
Corollary 16
Theorem 17
Theorem 19
Theorem 24
Theorem 29
Sampling design Independent draws from the excluded pool, that is, from the items not selected by the candidate generator. Uniform sampling without replacement from the excluded pool in a fixed finite corpus. Independent samples from the excluded pool and the included pool. Independent draws from the whole population, before conditioning on whether the generator selects the item. Separate excluded-pool audits for a pre-specified finite list of prefix generators.
Certified quantity An upper bound on the relevant mass missed by the generator. An upper bound on the number of relevant items missed by the generator. A lower bound on recall, obtained by combining the two audit samples. An upper bound on the relevant mass missed by the generator.
Simultaneous upper bounds on the missed relevant mass of all prefixes in the list. Simultaneous missed-mass A single labelled reference sample, used to guarantees for all generators in the evaluate a fixed sequence of candidate sequence. generators. Sequential audits along a pre-specified nested A valid stopping rule that returns a sequence of candidate generators. generator meeting a pre-specified missed-mass target, when such a generator is found. An audit of relevant items, used to estimate An upper bound on the conditional how often each component detector captures miss rate, equivalently a lower bound a relevant item. on recall, after combining several component detectors. An audit of relevant items together with Bounds on how often relevant items, independently generated variants of those or their variants, escape detection. items.
We obtain every entry in the table by exact binomial or hypergeometric inversion. All these designs share two assumptions. Assumption 1 (Design-Certification Separation). The candidate generator, candidate-generator family, or prefix family being certified is fixed before the certification audit labels are examined. The audit rule is likewise specified before those labels are examined. It may adaptively select which item to inspect next and when to stop as a function of labels revealed during the audit, provided that its validity has been established under that pre-specified rule. The audit rule may also depend on information available before certification, such as the candidate-generator values 8
zi = g(xi ) and hence the excluded pool {g = 0}. What is prohibited is the use of certification labels to construct, tune, order, or select the candidate generator, candidate-generator family, or prefix family being certified. Assumption 2 (Noiseless Audit Labels). The audit oracle returns the true relevance label for each audited item, with no labelling noise. Assumption 1 is the validity condition. Each certificate below is derived from a sampling distribution that holds only because the candidate generator, candidate-generator family, or prefix family is fixed before the audit labels are observed. If it were chosen after inspecting those labels, the sampling distribution would no longer apply, and the certificate would no longer be valid. Candidate-generator design may still be exploratory, heuristic, iterative, or model-based, provided the certification sample is held out from the design data.
2.4
Design, certification, and iteration
The certificates above apply only to candidate generators, or candidate-generator families, fixed independently of the certification audit. This does not prevent exploratory design. The analyst may examine misses, add rules, tune thresholds, or order components on a design split. The requirement is that the certification split remains unopened until the candidate-generator family to be certified has been fixed. In the default workflow, audit and stop, the design split builds an ordered sequence h1 , . . . , hJ , and chooses prefix cut points 1 ≤ t1 < · · · < tM ≤ J. Once the prefix family {g1 , . . . , gM } is frozen, the certification split is opened once. Corollary 16 or Theorem 17 supplies the simultaneous bounds, and the bicriteria rule of Section 3 returns the least burdensome prefix whose certified missed mass meets the target, or reports that none does. The certification then ends. If none passes, the analyst may instead audit and iterate: read the residual misses in the audit, design a better candidate generator, and certify it in a new round. The difficulty is that the original audit has now been seen. Its labels, and even the bare outcome that a prefix passed or failed, carry information about where relevant items were missed. Any candidate generator designed in response to that information depends on the opened audit labels and cannot be certified by them. Those labels may serve only as design data for the next round. Reusing them to certify a candidate generator they helped design violates Assumption 1, and voids the guarantee. A valid further round must therefore use fresh certification labels, or a pre-specified sequential-validity device. The simplest approach is to open a fresh, previously unused split and certify the new candidate generator on it. More elaborate approaches, such as pre-specified error spending [25] or anytime-valid confidence sequences [23], can also be used, but their validity must be built into the design before the labels are examined. The common principle is unchanged: labels used to design a candidate generator cannot also be used to certify it. Section 9 gives a limited extension of the i.i.d. excluded-pool missed-mass certificate to noisy audit labels under a known sensitivity floor. Extending the recall and positive-conditional certificates requires additional assumptions on the label-noise mechanism.
2.5
Why the audit must look outside the candidate set
Labels from the included pool alone do not constrain the relevance labels in the excluded pool. The next proposition makes this precise. Proposition 3 (Included-pool labels alone do not bound missed mass). Fix a candidate generator g with p0 (g) > 0, and let r(g) = P (Y = 1, g(X) = 0) 9
be the missed relevant mass. Consider any procedure which, using the candidate-generator values g(X), unlabelled data, and labels observed only on the included pool {g(X) = 1}, returns an upper bound T for r(g). Let PA denote probability over the sampling and any internal randomisation of the procedure, with P , g, and the relevance indicator fixed. Suppose that the procedure is valid for every measurable relevance indicator φ⋆ , in the sense that PA {r(g) ≤ T } ≥ 1 − δ. Then PA {T ≥ p0 (g)} ≥ 1 − δ. Thus included-pool labels alone cannot certify a non-trivial upper bound on r(g). Proof. Let A = {x : g(x) = 1},
B = {x : g(x) = 0}.
The procedure observes relevance labels only on A. Fix any relevance indicator φ⋆ , and define a second relevance indicator φ e which agrees with φ⋆ on A and is identically one on B. The procedure receives exactly the same observable information under φ⋆ and φ: e the candidate-generator values, the unlabelled data, and all observed included-pool labels are unchanged. It therefore returns the same random upper bound T in the two cases. Under φ, e every excluded item is relevant, so the missed relevant mass is rφe(g) = P {φ(X) e = 1, g(X) = 0} = P {g(X) = 0} = p0 (g). Applying the assumed validity condition under φ e therefore gives PA {T ≥ p0 (g)} ≥ 1 − δ. Hence any procedure using only included-pool labels must allow, with probability at least 1 − δ, the possibility that the entire excluded pool is relevant. Thus included-pool labels, even combined with the candidate-generator values and unlimited unlabelled data, cannot yield a non-trivial distribution-free certificate for missed relevant mass. The best universal bound remains the excluded-pool mass itself.
3
Bicriteria formulation
The burden term is necessary because the unrestricted one-sided objective is degenerate. Proposition 4 (Triviality of unrestricted coverage). The constant candidate generator g ≡ 1 selects every item. Hence r(g) = 0 for every P and every φ⋆ , and L(g) = 0 whenever L is defined (that is, whenever π = P (Y = 1) > 0). Unrestricted minimisation of r, or of L, over the space of all candidate generators is therefore degenerate: g ≡ 1 is always a minimiser. Excluding this trivial solution requires review burden to enter the formulation. Let G be a finite family of candidate generators, fixed before the audit. For each g ∈ G, the burden depends only on g and not on the relevance labels. In the finite-corpus model, BN (g) = N1 (g)/N can be computed exactly from the candidate-generator values. In the population model, B(g) = P (g(X) = 1) can be estimated from an unlabelled sample. In either case, no audit labels are needed. The audit returns an upper confidence bound U (g) on the missed relevant mass r(g). For a target ε, consider the constrained problem minimise B(g) subject to U (g) ≤ ε, 10
g ∈ G,
(1)
and report any minimiser gb. When several candidate generators are considered, the bounds are constructed simultaneously, so that Paudit (r(g) ≤ U (g) for all g ∈ G) ≥ 1 − δ, where the probability is over the random audit sample. On this event every candidate generator in G satisfies its own bound at once, so a minimiser gb of (1), selected after the bounds are computed, still satisfies r(b g ) ≤ U (b g ) with probability at least 1 − δ. The choice between controlling absolute missed relevant mass r(g) and conditional miss rate L(g) is an application decision. Legal discovery may care about the absolute amount of relevant material left outside the candidate set. Systematic-review screening usually phrases the requirement as recall among all relevant items. We support both targets, but the audit designs differ: r(g) can be certified from an excluded-pool audit alone, whereas L(g) also requires information about the positive count in the included pool. The bicriteria form is a Neyman–Pearson problem in shape [8, 36, 38, 42]: one error type is constrained, the other minimised. Classical Neyman–Pearson classification gives samplecomplexity bounds for selecting a classifier from a class subject to a one-sided constraint. We use that machinery at the design stage in Section 7. The novel content is on the certification side, where a fixed candidate generator is audited rather than designed (Section 4). The important separation in (1) is operational: the burden B(g) = P (g(X) = 1) does not require audit labels, while the missed-mass bound U (g) does. For an ordered union of J component detectors h1 , . . . , hJ , let g0 ≡ 0 and gj (x) = max hℓ (x), ℓ≤j
j = 1, . . . , J.
Define the incremental review burden ∆B j := P gj−1 (X) = 0, hj (X) = 1 , the probability that an item is newly caught by hj but not by any earlier component. The events {gj−1 = 0, hj = 1} are disjoint across j, so B(gJ ) = P (gJ (X) = 1) =
J X
∆B j .
(2)
j=1
4
Excluded-pool certification
We now give the central technical results. Proposition 3 shows why included-pool labels cannot certify missed mass. The constructive response is to direct audit labels to the only region where missed relevant items can be found, namely the excluded pool {g(X) = 0}. Remark 5 (Conventions for degenerate cases). Throughout Sections 4 to 6, conditional distributions are used only when the conditioning event has positive probability, and the degenerate cases are resolved as follows. If p0 (g) = 0, then r(g) = 0, no excluded-pool audit is required, and every excluded-pool certificate for g is read as the trivial bound 0. If p1 (g) = 0 and π > 0, then Recall(g) = 0. Statements involving recall, or sampling from P (· | Y = 1), assume π > 0. In particular, Sections 5 and 6 audit relevant items and assume π > 0 throughout, and the finite-corpus recall statements assume M0 (g) + M1 (g) > 0, as in Section 2. In the finite-corpus model, audit sizes satisfy 0 ≤ n0 ≤ N0 (g) and 0 ≤ n1 ≤ N1 (g) for every sampled candidate generator. If N0 (g) = 0, then M0 (g) = 0 is known without sampling. Empty audits are covered by the conventions U0 (0, α) = 1 and L0 (0, α) = 0 of Lemma 6 below.
11
The certificates below repeatedly reduce to the same elementary problem. We observe K relevant items in n audited draws from a pool whose unknown relevance probability is p. An upper one-sided confidence bound Un (K, α) is a number such that, with probability at least 1 − α, the true p is no larger than Un (K, α). A lower one-sided confidence bound Ln (K, α) is defined analogously. Throughout this section, 0 < α < 1 denotes the error probability allocated to one such one-sided bound. We use the exact Clopper–Pearson bounds, obtained by inverting binomial tail probabilities. For integers 0 ≤ k ≤ n and α ∈ (0, 1), define Un (k, α) := sup {q ∈ [0, 1] : P(Bin(n, q) ≤ k) ≥ α} , Ln (k, α) := inf {q ∈ [0, 1] : P(Bin(n, q) ≥ k) ≥ α} . By construction, for K ∼ Bin(n, p), Pp {p > Un (K, α)} ≤ α,
Pp {p < Ln (K, α)} ≤ α,
for every p ∈ [0, 1] [9]. Here exact means that the bounds invert exact binomial tail probabilities and carry guaranteed finite-sample coverage. It does not mean that the intervals are shortest or of exactly nominal level: as interval procedures they are conservative, in that the coverage can exceed 1 − α. The same reading of exact applies to the hypergeometric certificate below. The lower-bound symbol Ln (k, α) is unrelated to the conditional miss rate L(g). The subscript and arguments distinguish the two. In the zero-observed-event case, Un (0, α) = 1 − α1/n , for n ≥ 1. Finding no relevant items in the audited excluded sample does not imply that the excluded pool contains no relevant items. It gives a finite-sample upper bound on the excluded-pool relevance rate. The next lemma is a conditional form of the usual exact binomial inversion of Clopper and Pearson [9]. It will be used when the effective audit size is random, but the relevant count is binomial conditional on that realised size. Lemma 6 (Conditional binomial inversion). Let Q be a non-negative integer-valued random variable and suppose that, for every q with P(Q = q) > 0, K | {Q = q} ∼ Bin(q, θ) for a fixed θ ∈ [0, 1]. Then, with the convention U0 (0, α) = 1, P (θ > UQ (K, α)) ≤ α, so UQ (K, α) is a valid upper confidence bound for θ unconditionally. The analogous statement holds for LQ (K, α), with the convention L0 (0, α) = 0. Proof. Let A := {θ > UQ (K, α)}. By the law of total probability, equivalently the tower property applied to the indicator 1A , P(A) = E [P(A | Q)] X = P (θ > Uq (K, α) | Q = q) P(Q = q). q≥0
For every q ≥ 1 with P(Q = q) > 0, the conditional binomial assumption and the Clopper– Pearson property give P (θ > Uq (K, α) | Q = q) ≤ α. For q = 0, we have K = 0 almost surely conditional on Q = 0, and the convention U0 (0, α) = 1 gives P (θ > U0 (K, α) | Q = 0) = 0. 12
Consequently, P(A) ≤ α
X
P(Q = q)
q≥1
= α P(Q ≥ 1) ≤ α. The lower-bound statement follows identically by applying the same argument to {θ < LQ (K, α)}, using the convention L0 (0, α) = 0.
4.1
The binomial excluded-pool certificate
Fix a candidate generator g and write p0 (g) = P (g(X) = 0), η(g) = P (Y = 1 | g(X) = 0). The decomposition r(g) = p0 (g) · η(g) is exact. The quantity p0 (g) is observable without audit labels. The quantity η(g) requires labels from the excluded pool. Theorem 7 (Excluded-pool binomial certificate). Let G be a finite family of candidate generators, fixed independently of the audit, with p0 (g) > 0 for every g ∈ G. Generators with p0 (g) = 0 are certified trivially by the conventions above. For each g ∈ G, draw a separate sample X1 , . . . , Xn0 i.i.d. from the conditional distribution of X given g(X) = 0, observe Yi = φ⋆ (Xi ), and let n0 X K0 (g) := Yi . i=1
Then, with probability at least 1 − δ, δ and η(g) ≤ Un0 K0 (g), |G|
δ r(g) ≤ p0 (g) · Un0 K0 (g), |G|
for all g ∈ G.
If n0 ≥ 1 and K0 (g) = 0, p (g) log(|G|/δ) 0 . r(g) ≤ p0 (g) 1 − (δ/|G|)1/n0 ≤ n0
(3)
Proof. For each fixed g ∈ G, because g and G are fixed before the certification audit labels are observed, and because the audit draws i.i.d. from P ( · | g(X) = 0), each audited label satisfies Yi ∼ Bernoulli(η(g)), Hence K0 (g) =
η(g) := P (Y = 1 | g(X) = 0). n0 X
Yi ∼ Bin(n0 , η(g)).
i=1
By the defining property of Un0 , δ δ Paudit η(g) > Un0 K0 (g), ≤ . |G| |G| For each g ∈ G, define the failure event δ Eg := η(g) > Un0 K0 (g), . |G| 13
Then, by the union bound, Paudit
[ X X δ δ ∃g ∈ G : η(g) > Un0 K0 (g), = Paudit = δ. Eg ≤ Paudit (Eg ) ≤ |G| |G| g∈G
Equivalently, with probability at least 1 − δ, δ η(g) ≤ Un0 K0 (g), |G| Since r(g) = p0 (g)η(g), the same event implies δ r(g) ≤ p0 (g) Un0 K0 (g), |G|
g∈G
g∈G
for every g ∈ G.
for every g ∈ G.
The same argument permits generator-specific sample sizes and error allocations αg satisfying X αg ≤ δ. g∈G
Finally, if n0 ≥ 1 and K0 (g) = 0, then, with α = δ/|G|, Un0 (0, α) = 1 − α1/n0 . Therefore " 1/n0 # δ r(g) ≤ p0 (g) 1 − . |G| Writing u := log(|G|/δ) , we have n0 1−
δ |G|
1/n0
= 1 − e−u ≤ u,
and hence r(g) ≤ p0 (g) log(|G|/δ) . n0 The factor p0 (g) requires no audit labels, because g can be evaluated on any item without knowing its relevance, and both excluded-pool certificates, Theorem 7 and the finite-corpus Theorem 8, leave it outside the audit. Whenever the corpus is finite it is known exactly, as p0,N (g) = N0 (g)/N . In the i.i.d. population model it is a probability rather than a count, and must be known or estimated. If p0 (g) must instead be estimated, an independent unlabelled u gives sample X1u , . . . , Xm m X −1 pb0 (g) = m 1{g(Xiu ) = 0}. i=1
Hoeffding’s inequality and a union bound over G give r log(2|G|/δ) p0 (g) ≤ pb0 (g) + 2m simultaneously for all g ∈ G, with probability at least 1 − δ/2. Combining this event with the audit event, also taken at error level δ/2, gives the missed-mass certificate with confidence at least 1 − δ, with p0 (g) replaced by the displayed upper bound. Unlabelled data do not require relevance judgements, so m can be chosen large enough to make the Hoeffding correction small. The relevance labels in the excluded-pool audit are then used only to bound η(g) = P (Y = 1 | g(X) = 0). Combining this bound with the upper bound on p0 (g) gives the stated upper bound on r(g) = p0 (g)η(g). 14
4.2
The hypergeometric finite-corpus certificate
For finite corpora, the natural distributional assumption is sampling without replacement. For a fixed candidate generator g, write N0 = N0 (g) for the excluded-pool size, and let M0 (g) = |{i : g(xi ) = 0, yi = 1}| be the unknown number of missed relevant items in that pool. If the audit draws n0 items uniformly without replacement from this pool and observes K0 relevant items, the lower-tail probability m 7→ P(Hypergeom(N0 , m, n0 ) ≤ k) is non-increasing in m, so the inversion MU (k, α) := max {m ∈ {0, 1, . . . , N0 } : P (Hypergeom(N0 , m, n0 ) ≤ k) ≥ α} gives an upper confidence bound on M0 (g). Where the pool and sample sizes must be displayed, we write MU (k, α; N, n) for the inversion computed with population size N and sample size n. When they are clear from context, we abbreviate to MU (k, α). This is the exact finite-corpus analogue of the binomial upper confidence bound used in the i.i.d. population model. The binomial certificate of Theorem 7 is exact under sampling with replacement from the excluded pool. For sampling without replacement, the exact finite-corpus certificate is the hypergeometric one given below. In the zero-count case, sampling without replacement is no less favourable than independent sampling for finding at least one relevant item, so the binomial zero-count upper bound remains conservative. Classical comparisons of the hypergeometric and binomial distribution functions are given by Uhlmann [45]. The certificate primarily controls the missed relevant count M0 (g). A recall statement also needs the denominator, namely the total number of relevant items M0 (g) + M1 (g). Thus an excluded-pool audit controls the missed-positive part of recall. The included-pool contribution must be known, lower-bounded, or audited separately. Theorem 8 (Excluded-pool hypergeometric certificate). Let G be a finite family of candidate generators, fixed independently of the audit. For each g ∈ G, draw n0 items uniformly without replacement from the excluded pool {i : g(xi ) = 0}, with 0 ≤ n0 ≤ N0 (g), observe their labels, and let K0 (g) be the number of relevant items observed. Pools with N0 (g) = 0 have M0 (g) = 0 known without sampling and are certified trivially by the conventions above; when a two-pool sample is drawn, the analogous condition 0 ≤ n1 ≤ N1 (g) is likewise assumed. Then, with probability at least 1 − δ, δ M0 (g) ≤ MU K0 (g), ; N0 (g), n0 for all g ∈ G, |G| where the inversion for each g is computed with its own excluded-pool size N0 (g). If, in addition, all items in the included pool {i : g(xi ) = 1} are reviewed, so that M1 (g) is known, then Recall(g) =
M1 (g) M1 (g) ≥ . M1 (g) + M0 (g) M1 (g) + MU (K0 (g), δ/|G|; N0 (g), n0 )
Proof. By Assumption 1, G is fixed independently of the audit. The sampling design gives K0 (g) ∼ Hypergeom(N0 (g), M0 (g), n0 ). Monotonicity of m 7−→ P {Hypergeom(N0 (g), m, n0 ) ≤ k} in m implies Paudit
δ δ M0 (g) > MU K0 (g), ≤ . |G| |G|
A union bound over G gives the simultaneous statement. The recall bound follows from monotonicity of M1 (g)/(M1 (g) + M0 ) in M0 .
15
This is the finite-corpus version of the elusion-sampling argument used in technology-assisted review [19]. One samples from the unreviewed, or excluded, pool and uses the number of relevant documents found in that sample to bound the number of relevant documents remaining in the pool. In the zero-count case, the audit coincides with a classical zero-acceptance-number attributes sampling plan with lot size N0 and limiting quality m/N0 [37]. Remark 9 (Recall requires a denominator). A certificate for absolute missed mass, r(g) = P (Y = 1, g(X) = 0), does not by itself give a recall certificate unless the total prevalence π = P (Y = 1) is known or lower-bounded. Since L(g) = P (g(X) = 0 | Y = 1) =
r(g) , π
an upper bound on r(g) becomes a bound on missed-positive rate only after dividing by a certified lower bound on π. This distinction is especially important in rare-event settings: a small absolute missed mass may still be non-negligible relative to the total relevant population. A missed-mass certificate can be converted into a recall certificate when a lower bound on the total relevant mass is also available. If r(g) ≤ u and the total relevant mass is at least a > 0, then u Recall(g) ≥ 1 − . a Thus missed-mass certification controls recall only after supplying a denominator bound. A denominator lower bound may come from a known total relevant mass, a small wholepopulation audit, or domain knowledge. This gives a recall certificate from an excluded-pool audit, but the bound becomes weaker when the denominator lower bound is small. If the included pool is fully reviewed, the finite-corpus certificate above gives the sharper bound M1 (g) , M1 (g) + MU which does not require a separate denominator floor.
4.3
Two-pool recall certificate
Theorem 8 certifies the number of relevant items missed in the excluded pool. To turn that missed-count certificate into a recall certificate, one also needs information about the number of relevant items recovered in the included pool. If the included pool has been fully reviewed, this number is known. Otherwise, it must be estimated or lower-bounded. The two-pool design does this by auditing both sides of the candidate-generation boundary. The excluded-pool sample controls the missed positives, while the included-pool sample controls the recovered positives. If the goal is only to certify absolute missed relevant mass, the excludedpool certificate in Section 4 is sufficient. Theorem 10 (Two-pool recall certificate). Fix a candidate generator g with π > 0, p0 (g) > 0, and p1 (g) > 0, and write p1 (g) = 1 − p0 (g) = P (g(X) = 1), η(g) = P (Y = 1 | g(X) = 0), and η1 (g) = P (Y = 1 | g(X) = 1). By Bayes’ theorem, η1 (g) = Recall(g)π/p1 (g). Draw, independently of each other, n0 items from the excluded pool {g = 0} and n1 items from the included pool {g = 1}, each sample i.i.d. from the corresponding conditional distribution. Let K0 and K1 be the counts of relevant items observed in each audit. Since P (Y = 1, g(X) = 1) = p1 (g)η1 (g),
P (Y = 1, g(X) = 0) = p0 (g)η(g),
the law of total probability gives P (Y = 1) = p1 (g)η1 (g) + p0 (g)η(g). 16
Then, with probability at least 1 − δ0 − δ1 , Recall(g) =
p1 (g) η1 (g) p1 (g) Ln1 (K1 , δ1 ) . ≥ p1 (g) η1 (g) + p0 (g) η(g) p1 (g) Ln1 (K1 , δ1 ) + p0 (g) Un0 (K0 , δ0 )
Proof. K0 ∼ Bin(n0 , η(g)) and K1 ∼ Bin(n1 , η1 (g)), independent across pools. The Clopper– Pearson bounds give η(g) ≤ Un0 (K0 , δ0 ) with probability at least 1 − δ0 and η1 (g) ≥ Ln1 (K1 , δ1 ) with probability at least 1 − δ1 . A union bound gives the joint event. The recall ratio Recall(g) =
p1 η1 p1 η1 + p 0 η
is increasing in η1 and decreasing in η, so substituting the lower bound on η1 and the upper bound on η gives a lower bound on the recall. The factors p0 (g) and p1 (g) = 1 − p0 (g) do not require relevance judgements. In the finitecorpus model they are known exactly as N0 (g)/N and N1 (g)/N . In the population model they may be estimated from an independent unlabelled sample. Specifically, if p0 (g) and p1 (g) are simultaneous upper and lower confidence bounds satisfying p0 (g) ≤ p0 (g) and p1 (g) ≥ p1 (g), then the recall certificate remains valid after replacing p0 (g) by p0 (g) and p1 (g) by p1 (g): Recall(g) ≥
p1 (g)Ln1 (K1 , δ1 ) p1 (g)Ln1 (K1 , δ1 ) + p0 (g)Un0 (K0 , δ0 )
.
The confidence levels used to construct these bounds must be included in the overall error allocation. The audit labels are used to bound the two conditional relevance rates η(g) = P (Y = 1 | g(X) = 0) and η1 (g) = P (Y = 1 | g(X) = 1). The allocation of δ0 and δ1 need not be equal. When the excluded-pool upper bound is the main source of uncertainty, assigning it a larger share of the error budget can give a sharper recall certificate. The allocation should be fixed before the audit labels are examined. The same two-pool construction has an exact finite-corpus version. Corollary 11 (Finite-corpus two-pool recall certificate). In the finite-corpus model, draw n0 items uniformly without replacement from the excluded pool {i : zi = 0} and, independently, n1 items uniformly without replacement from the included pool {i : zi = 1}, observing K0 and K1 relevant items respectively. Let MU (·, ·) be the hypergeometric upper inversion of Theorem 8 on the excluded pool, computed with population size N0 and sample size n0 , and let ML (k, α) := min {m ∈ {0, . . . , N1 } : P (Hypergeom(N1 , m, n1 ) ≥ k) ≥ α} be the corresponding lower inversion on the included pool. Then M0 (g) ≤ MU (K0 , δ0 ) and M1 (g) ≥ ML (K1 , δ1 ) hold jointly with probability at least 1 − δ0 − δ1 . If M0 (g) + M1 (g) > 0, then on that event Recall(g) =
M1 (g) ML (K1 , δ1 ) ≥ , M0 (g) + M1 (g) ML (K1 , δ1 ) + MU (K0 , δ0 )
with the displayed lower bound interpreted as 0 when ML (K1 , δ1 ) = MU (K0 , δ0 ) = 0. Proof. The two pools are disjoint and sampled separately, so K0 ∼ Hypergeom(N0 , M0 (g), n0 ) and K1 ∼ Hypergeom(N1 , M1 (g), n1 ) are independent. Monotonicity of the hypergeometric tail in the success count gives the two one-sided bounds, and a union bound gives the joint event. The ratio M1 /(M0 + M1 ) is increasing in M1 and decreasing in M0 , so substituting the lower bound on M1 and the upper bound on M0 gives the displayed lower bound on recall.
17
4.4
Whole-population audit as an alternative
For completeness we record the whole-population certificate, which arises by sampling i.i.d. from the full distribution rather than from {g(X) = 0}. Theorem 12 (Whole-population certificate). Let G be a finite family of candidate generators, fixed independently of the audit. Let (Xi , Yi )ni=1 be an i.i.d. audit sample from P , and let Kg = P n i=1 1{Yi = 1, g(Xi ) = 0}. Then, with probability at least 1 − δ, δ for all g ∈ G. r(g) ≤ Un Kg , |G| Proof. For each fixed g ∈ G, the indicators 1{Yi = 1, g(Xi ) = 0} are i.i.d. Bernoulli(r(g)), so Kg ∼ Bin(n, r(g)). The Clopper–Pearson property gives Paudit (r(g) > Un (Kg , δ/|G|)) ≤ δ/|G|, and a union bound over G completes the proof. This is the argument of Theorem 7 with the sampling design drawing from P rather than from P (· | g(X) = 0), and with r(g) playing the role of η(g).
4.5
Optimality of excluded-pool auditing
Proposition 3 shows that included-pool labels certify nothing about missed mass. The next result is its quantitative converse: in the finite-corpus model, any valid audit, however adaptive, must label essentially as many excluded-pool items as the designs above. We state the optimality result in the finite-corpus model because this is the setting in which label complexity has its most direct interpretation: the question is how many items from a fixed excluded pool must be labelled to rule out a specified number of missed relevant items. Here an adaptive procedure may choose which item to label next, and when to stop, as a function of the labels already observed. The lower bound allows this flexibility. The theorem imposes two requirements on the audit procedure. The first is validity: when there are m or more missed relevant items, the procedure should rarely certify fewer than m. The second rules out vacuous procedures: when there are no missed relevant items, the procedure should usually be able to certify fewer than m. Theorem 13 (Lower bound on audit label complexity). Fix a corpus and a candidate generator g with excluded-pool size N0 = N0 (g) ≥ 1. Fix an integer m ∈ {1, . . . , N0 }, and let δ, β ∈ (0, 1) satisfy β + δ < 1. The audit task is to rule out the possibility that the excluded pool contains m or more relevant items, that is, to certify M0 (g) ≤ m − 1. Consider an audit procedure that labels corpus items one at a time, possibly adaptively and with external randomisation. The audit procedure is fixed independently of the labelling. At each stage, the next inspected item, the stopping decision, and the reported bound are determined by the same pre-specified rule applied to the random seed and the observed index-label history. For any fixed labelling y and any realised value of R, the pre-specified audit rule determines the complete audit trajectory recursively from the random seed and the labels revealed along that trajectory. Formally, let (ΩA , AA , PA ) carry the internal randomness of the procedure and its audit trajectory, and write EA for expectation under PA . Let R denote the initial random seed, let It be the index inspected at step t, and define F0 := σ(R),
Ft := σ (R, I1 , yI1 , . . . , It , yIt ) ,
t ≥ 1.
The procedure is non-anticipating: on the event that it has not yet stopped, the next inspected index It+1 is Ft -measurable. Its termination time τ is an almost surely finite stopping time with cU is Fτ -measurable. respect to (Ft )t≥0 , and the reported upper confidence bound M The procedure may inspect items from either the included or excluded pool. Let T := |{It : 1 ≤ t ≤ τ, g(xIt ) = 0}| 18
be the number of distinct excluded-pool items inspected. Assume that the procedure is valid at level δ, in the sense that, for every labelling with cU ≤ m − 1 with probability at most δ. Assume also that M0 (g) ≥ m, it returns an upper bound M the procedure succeeds with high probability when there are no missed relevant items: for every labelling with M0 (g) = 0, cU ≤ m − 1} ≥ 1 − β. PA {M Then, under any labelling with M0 (g) = 0, EA T ≥ (1 − β − δ)
N0 . m
In particular, if β ≤ 1/2 and δ < 1/4, then EA T ≥
N0 . 4m
Proof. In this proof, a labelling y means an assignment of relevance labels to the fixed finite corpus. We compare two possible labellings: a zero-miss labelling y 0 , under which no excludedpool item is relevant, and a planted labelling y S , under which a chosen set S of m excluded-pool items is relevant. Let y 0 be a labelling such that y 0 (x) = 0 whenever g(x) = 0. Thus M0 (g) = 0 under y 0 . Let R denote the initial random seed of the audit procedure. For any fixed labelling y and any realised value of R, the non-anticipation condition determines the complete audit trajectory recursively from the labels revealed along that trajectory. Under a fixed labelling, PA and EA therefore average over the random seed R. Joint subscripts indicate any additional sources of cU (R; y) randomness over which probability or expectation is taken. For any labelling y, write M for the upper bound returned by the procedure when it is run with randomness R and true labelling y. When the procedure is run under y 0 with randomness R, let A(R) be the set of distinct excluded-pool items inspected. Thus T = |A(R)|. Write cU (R; y 0 ) ≤ m − 1}. pass0 (R) = {M Choose a uniformly random m-subset S of the N0 excluded-pool items, independently of R. For each fixed S, define y S to agree with y 0 outside S and to label every item in S as relevant. Then M0 (g) = m under y S . Hence the validity assumption gives, for every fixed S, cU (R; y S ) ≤ m − 1} ≤ δ. PA {M Averaging this inequality over the random choice of S gives cU (R; y S ) ≤ m − 1} ≤ δ. PA,S {M Now compare the two runs with the same value of R. If pass0 (R) occurs and S ∩ A(R) = ∅, then an induction over the audit steps shows that the runs under y 0 and y S , coupled using the same random seed R, have identical trajectories. At each step, the two runs have observed the same history, so the same pre-specified non-anticipating audit rule makes them choose the same next item. Every inspected excluded-pool item lies outside S, and therefore has the same label under y 0 and y S . Consequently, the two runs stop at the same time and return the same value. Hence cU (R; y S ) = M cU (R; y 0 ) ≤ m − 1. M Consequently, for every pair (R, S), cU (R; y S ) ≤ m − 1} ≥ 1{pass0 (R)}1{S ∩ A(R) = ∅}. 1{M 19
Taking expectation over R and S, and using the preceding averaged validity bound, gives δ ≥ EA,S [1{pass0 (R)}1{S ∩ A(R) = ∅}] . Averaging first over S, conditional on R, gives EA,S [1{pass0 (R)}1{S ∩ A(R) = ∅}]
= EA [1{pass0 (R)}PS {S ∩ A(R) = ∅ | A(R)}] .
For a realised inspected set A(R), each excluded-pool item belongs to S with probability m/N0 . A union bound gives PS {S ∩ A(R) ̸= ∅ | A(R)} ≤
mT m|A(R)| = . N0 N0
Therefore PS {S ∩ A(R) = ∅ | A(R)} ≥ 1 −
mT . N0
For each realised run under y 0 , mT mT 1{pass0 (R)}PS {S ∩ A(R) = ∅ | A(R)} ≥ 1{pass0 (R)} 1 − ≥ 1{pass0 (R)} − . N0 N0 Taking expectations and using the assumption that the procedure certifies correctly under every zero-miss labelling gives m m δ ≥ PA {pass0 (R)} − EA T ≥ (1 − β) − EA T. N0 N0 Rearranging gives the claim. Remark 14 (Comparison with the simple zero-count audit). The following comparison shows that the lower bound has the right dependence on N0 and m in the favourable case M0 (g) = 0, where there are no missed relevant items in the excluded pool. It is not intended as an exact optimality statement for all possible audit outcomes. Consider the standard non-adaptive audit which samples n0 items uniformly without replacement from the excluded pool. If the excluded pool contains at least m relevant items, then the probability that the audit sees no relevant item is at most N0 −m n0 m n0 . ≤ 1− N0 N0 n 0
Thus, if n0 ≥ N0 (1 − δ 1/m ), then a zero-count outcome certifies M0 (g) ≤ m − 1 with error probability at most δ. This sufficient audit size has the same dependence on N0 and m as the lower bound. Indeed, N0 log(1/δ). m Theorem 13 shows that any valid procedure which usually certifies M0 (g) ≤ m−1 when M0 (g) = 0 must inspect at least N0 (1 − β − δ) m excluded-pool items in expectation under the zero-miss labelling. Hence the simple zero-count excluded-pool audit matches the lower-bound scale up to the constant factor N0 (1 − δ 1/m ) ≤
log(1/δ) , 1−β−δ which does not depend on N0 or m. 20
Corollary 15 (Minimax label complexity of missed-mass certification). Fix the excluded-pool size N0 and an integer m ∈ {1, . . . , N0 }, and fix error parameters β ≤ 1/2, δ < 1/4. Consider the zero-miss regime M0 (g) = 0. Among all audit procedures that are valid at level δ and certify M0 (g) ≤ m−1 with probability at least 1−β whenever M0 (g) = 0, the minimum expected number of excluded-pool labels inspected under the zero-miss labelling is N0 Θ , m where the implied constants depend only on (β, δ) and not on N0 or m. The lower bound is Theorem 13, whereas the upper bound is attained by the non-adaptive zero-count audit of the preceding remark, which inspects at most (N0 /m) log(1/δ) + 1 labels. Proof. Let Aβ,δ denote the class of audit procedures satisfying the validity and zero-miss success requirements in the statement. By Theorem 13, every A ∈ Aβ,δ satisfies EA T ≥ (1 − β − δ)
N0 . m
Under the assumed restrictions β ≤ 1/2 and δ < 1/4, this gives inf EA T ≥
A∈Aβ,δ
N0 . 4m
For the matching upper bound, consider the non-adaptive audit of Remark 14, which samples m l n0 = N0 1 − δ 1/m items uniformly without replacement from the excluded pool and certifies M0 (g) ≤ m − 1 if no relevant item is observed. If M0 (g) ≥ m, the probability of observing no relevant item is at most δ, so the procedure is valid at level δ. If M0 (g) = 0, it certifies with probability one, and hence with probability at least 1 − β. Moreover, using 1 − e−u ≤ u with u = log(1/δ)/m, n0 ≤
N0 1 log + 1. m δ
Since m ≤ N0 , the additive term is itself at most N0 /m, and therefore 1 N0 inf EA T ≤ 1 + log . A∈Aβ,δ δ m Combining the lower and upper bounds proves inf EA T = Θ
A∈Aβ,δ
N0 m
,
where the implied constants depend only on (β, δ).
4.6
Sample-size planning
The zero-observed-miss case of Theorem 7 translates targets directly into audit sizes. In the planning calculations below, δ denotes the total audit error budget. The zero-count identity is the exact form of the rule of three, namely n ≈ 3/ε at δ = 0.05 [21, 44]. To certify η(g) ≤ ε with confidence 1 − δ from zero observed misses on a single candidate generator, n0 ≥
log(1/δ) . log(1/(1 − ε)) 21
For δ = 0.05, the implied audit sizes are shown below. In the zero-count case, the required audit size is obtained from (1 − ε)n ≤ δ, so n is proportional to log(1/δ) for fixed ε. To certify M pre-specified prefixes simultaneously, we allocate error level δ/M to each prefix. This replaces log(1/δ) by log(M/δ) = log(1/δ) + log M , so the required number of labels per prefix increases only logarithmically in M . With separate excluded-pool audits, the total label cost is M times the displayed per-prefix figure. By contrast, the shared-reference design of Section 4.7 reuses one labelled reference sample across all prefixes. The third column is for an audit plan that certifies ten pre-specified candidate generators or prefixes using a union bound, so each individual bound receives error budget δ/10 = 0.005. Target ε on η(g)
Single candidate generator
10 pre-specified prefixes (labels per prefix)
29 59 149 299 598
51 104 263 528 1,058
0.10 0.05 0.02 0.01 0.005
To plan for an absolute missed-mass target r(g) ≤ εr when 0 < εr < p0 (g), use the identity r r(g) = p0 (g)η(g) and set the excluded-pool target to η(g) ≤ p0ε(g) . If εr ≥ p0 (g), the target already holds without an audit, since r(g) ≤ p0 (g). For comparison, if the target is r(g) ≤ εr , a zero-event whole-population audit requires n≥
log(1/δ) , log(1/(1 − εr ))
whereas a zero-event excluded-pool audit requires n0 ≥
log(1/δ) . log(1/(1 − εr /p0 (g)))
For certifying missed relevant mass for a fixed candidate generator, whole-population auditing is mainly a baseline. It is less label-efficient than excluded-pool auditing because many sampled items fall outside the only region where missed relevant items can occur. Whole-population auditing is useful for different targets, such as estimating overall prevalence or supplying a denominator for recall.
4.7
Certifying and choosing among pre-specified prefixes
We now address a common operational choice. A candidate generator is built by adding component detectors h1 , . . . , hJ in a fixed order, and the analyst wants to choose how far down the list to go. Each prefix length t ∈ {1, . . . , J} defines a prefix generator gt (x) := max hj (x), j≤t
with larger t usually trading higher review burden against smaller missed relevant mass. The audit goal is to certify a pre-specified collection of these prefixes simultaneously, then select the least burdensome one whose certified missed mass is below the target. The collection certified need not include every prefix. Simultaneous certification pays a union-bound penalty in the number M of prefixes certified, for example through a per-prefix allocation δ/M in Corollary 16 and Theorem 17. Hence the analyst may choose M ≪ J cut points 1 ≤ t1 < t2 < · · · < tM ≤ J 22
in advance, and certify the corresponding sub-sequence gm (x) := gtm (x) = max hj (x), j≤tm
m = 1, . . . , M.
The case M = J, tm = m, recovers certification of every prefix. The prefix-specific excluded pool is Em := {x : gm (x) = 0}. By construction the prefix unions are nested: Sb1 ⊆ Sb2 ⊆ · · · ⊆ SbM ,
E1 ⊇ E2 ⊇ · · · ⊇ EM .
Adding component detectors can only enlarge the candidate set, and hence can only shrink the excluded pool. Two sampling designs are useful. Corollary 16 (Separate excluded-pool prefix certificate). Suppose h1 , . . . , hJ and t1 , . . . , tM are fixed independently of the audit. For each m, draw nm samples i.i.d. from P (· | gm (X) = 0), observe their labels, and let Km be P the number of relevant items observed in the mth excluded-pool audit. If δ1 , . . . , δM > 0 satisfy m δm ≤ δ, then, with probability at least 1 − δ, r(gm ) ≤ p0 (gm ) · Unm (Km , δm ),
m = 1, . . . , M.
In particular, taking nm = n for all m and δm = δ/M gives simultaneous prefix certificates with audit size n per prefix. Sample sizes achieving a target εr per prefix follow from Section 4.6, with the per-prefix error level set to δ/M . Proof. Apply Theorem 7 to the finite family {g1 , . . . , gM }, allowing unequal sample sizes and confidence allocations. A union bound over m gives the result. The labelling cost depends on the sampling design. Corollary 16 uses separate excludedpool audits, so it is cleanest theoretically but may require repeated sampling from the shrinking sequence of excluded pools E1 ⊇ · · · ⊇ EM . A single held-out certification sample requires a different argument. Theorem 17 (Shared-reference prefix certificate). Suppose h1 , . . . , hJ and t1 , . . . , tM are fixed independently of the audit, and let Em = {x : gm (x) = 0}. Let R be a fixed measurable reference pool with P (R) > 0 and Em ⊆ R for every m. Examples are R = X and R = E1 , the latter exploiting that Em ⊆ E1 for every m. Draw Z1 , . . . , ZQ i.i.d. from P (· | R) and label all sampled items. Define neff m :=
Q X
1{Zi ∈ Em },
Km :=
i=1
Q X
1{Zi ∈ Em , φ⋆ (Zi ) = 1}.
i=1
With the convention U0 (0, α) = 1, with probability at least 1 − δ, δ r(gm ) ≤ p0 (gm ) · Uneff Km , , m = 1, . . . , M. m M Any stopping rule that selects a prefix using only these simultaneous certificates has confidence at least 1 − δ. The certificate is computed from the realised effective sample sizes neff m , but its validity is unconditional. The proof uses only a conditioning argument: among the reference samples that fall in a given excluded pool, the labels behave as a binomial sample from that excluded pool.
23
Proof. Fix m. If P (Em ) = 0, then p0 (gm ) = 0, and the displayed bound is trivial. Assume P (Em ) > 0. The reference sample is drawn from P (· | R), and Em ⊆ R. Conditional on the event Zi ∈ Em , the distribution of Zi is therefore P (· | Em ), which is the same as P (· | gm (X) = 0). Hence a sampled point that falls in Em is relevant with probability η(gm ) = P (Y = 1 | gm (X) = 0). Now condition on the realised effective sample size neff m = q. Given this event, the q sampled points that fall in Em are distributed as q independent draws from P (· | Em ). Therefore Km | {neff m = q} ∼ Bin(q, η(gm )). By Lemma 6,
Paudit η(gm ) > Uneff m
δ Km , M
≤
δ . M
Multiplying by p0 (gm ) gives r(gm ) = p0 (gm )η(gm ) ≤ p0 (gm )Uneff m
δ Km , M
with probability at least 1 − δ/M . A union bound over m = 1, . . . , M gives the simultaneous statement with probability at least 1 − δ. On that event, every displayed bound holds at once, so any stopping rule that selects a prefix using only these certificates selects a prefix whose corresponding bound is valid. The shared-reference design lets the analyst open one held-out certification sample and certify all pre-specified prefixes. Its cost is that the effective sample size is random. Since EM ⊆ · · · ⊆ E1 , we have eff neff M ≤ · · · ≤ n1 .
Thus later prefixes, which usually have smaller excluded pools, may have the least precise certificates. The factor p0 (gm ) in the displayed bound is known exactly in the finite-corpus model, as N0 (gm )/N . In the population model, it can be replaced by the Hoeffding upper bound following Theorem 7, computed from an independent unlabelled sample, with the corresponding confidence adjustment. In planning such an audit, the analyst should budget the total reference sample Q so that the smallest effective sample size is large enough. Under the prefix nesting above, this means controlling neff M . The finite-corpus version follows by the same conditioning argument. Corollary 18 (Finite-corpus shared-reference prefix certificate). In the finite-corpus model, suppose h1 , . . . , hJ and t1 , . . . , tM are fixed independently of the audit, and let Em = {i : gm (xi ) = 0}. Let R ⊆ {1, . . . , N } be a fixed reference pool with Em ⊆ R for every m. Draw Q items uniformly without replacement from R, where 0 ≤ Q ≤ |R|, and label them. Let neff m be the number of sampled items in Em and Km the number of those that are relevant. Then, with probability at least 1 − δ, δ M0 (gm ) ≤ MU Km , ; N0 (gm ), neff , m = 1, . . . , M. m M
24
Proof. Fix m. Conditional on {neff m = q}, the q sampled items falling in Em are, by exchangeability of the uniform reference draw, a uniform without-replacement sample from Em , so Km | {neff m = q} ∼ Hypergeom N0 (gm ), M0 (gm ), q . For each q ≥ 1, the inversion is valid at level δ/M conditionally, by the argument of Theorem 8, and for q = 0 it returns the trivial bound N0 (gm ). Averaging over the distribution of neff m , as in Lemma 6, gives unconditional validity, and a union bound over m = 1, . . . , M completes the proof.
4.8
Fixed-target stopping without a multiplicity penalty
The simultaneous certificates of Corollary 16 and Theorem 17 deliver numerical bounds for all M prefixes at a δ/M union-bound cost, and remain valid against a target chosen after the audit. When the missed-mass target ε is itself fixed before the audit, as in the bicriteria rule of Section 3, that penalty can be removed. Theorem 19 (Fixed-sequence prefix certification). Suppose that the component detectors h1 , . . . , hJ , the cut points 1 ≤ t1 < · · · < tM ≤ J, and the missed-mass target ε > 0 are fixed before the audit labels are observed. Let g1 , . . . , gM be the corresponding prefix generators. Thus EM ⊆ · · · ⊆ E1 ,
r(g1 ) ≥ · · · ≥ r(gM ).
For each m, let passm be the event that a valid level-δ excluded-pool certificate for gm certifies r(gm ) ≤ ε. Equivalently, whenever r(gm ) > ε, Paudit {passm } ≤ δ. Test the prefixes in the fixed order gM , gM −1 , . . . , g1 . If passM fails, return no prefix. Otherwise, continue down the sequence until the first failure. Return the last prefix that passed. If all tests pass, return g1 . Then, with probability at least 1−δ, either no prefix is returned, or the returned prefix satisfies r(g) ≤ ε. Proof. Suppose first that r(gM ) > ε. By monotonicity, every prefix then has missed mass greater than ε. The procedure returns a prefix only on the event passM , and validity gives Paudit {passM } ≤ δ. Hence, with probability at least 1 − δ, no prefix is returned. Otherwise, let m0 := min{m : r(gm ) ≤ ε}. By monotonicity, r(gm ) ≤ ε for all m ≥ m0 . If m0 = 1, every prefix meets the target, so any returned prefix is valid, and the conclusion holds with probability one. If m0 > 1, then r(gm0 −1 ) > ε, and the tests proceed through gM , . . . , gm0 before reaching gm0 −1 . Since the procedure stops at the first failure and returns the last prefix that passed, it returns a prefix with index below m0 only if the test at gm0 −1 is reached and passes. Hence Paudit {the returned prefix is invalid} ≤ Paudit {passm0 −1 } ≤ δ. The final inequality follows from validity at gm0 −1 . In every case, with probability at least 1 − δ, either no prefix is returned or the returned prefix satisfies r(g) ≤ ε. 25
The argument uses only the marginal level of the single boundary test, so the prefix audits may share data, as in the shared-reference design, without changing the validity argument. Remark 20 (Fixed-sequence stopping versus optional stopping). The stopping in Theorem 19 is stopping along a finite, pre-specified sequence of tests. It is not optional stopping of a confidence procedure at a data-dependent audit sample size. The proof uses only the marginal level-δ validity of the single boundary test and therefore requires no martingale or optional-stopping theorem. If the sample size or sampling distribution used to construct an individual certificate is itself chosen adaptively after examining audit labels, its level-δ validity must be established under that adaptive sampling rule. This may follow from a conditional argument, as in Lemma 6 when the required conditional binomial law holds, or from an anytime-valid procedure. Remark 21 (What is gained and what is lost). The gain is that each test runs at level δ, rather than using a δ/M allocation across all prefixes. For a pre-registered missed-mass target, this can reduce the audit size needed at each tested prefix. The cost is that the procedure certifies only the selected prefix against the fixed target. It does not deliver simultaneous numerical bounds for every prefix, and the pass/fail decisions at ε cannot be reused for a different target chosen later. When post-hoc numerical bounds or target flexibility are wanted, the simultaneous certificates remain the appropriate tool. Remark 22 (Provenance). The fixed-sequence testing principle is standard in multiple testing. It appears, for example, in ordered and stepwise testing procedures [5,24,32], and is also used in Learn then Test [1]. We use it here in a different setting: the ordered hypotheses are missed-mass certificates for nested prefix candidate generators.
5
Coverage amplification with auditable diagnostics
The excluded-pool certificate gives an upper bound on missed mass from the audit labels, but it does not explain how the components of a candidate-generator union contribute to that bound. We now give a structural result that decomposes the conditional miss rate L(gJ ) across an ordered component sequence h1 , . . . , hJ , with a diagnostic interpretation of each component’s contribution.
5.1
Incremental coverage and exponential decay
Definition 23 (Incremental coverage). Let h1 , . . . , hJ be an ordered sequence of component detectors and let gj = maxℓ≤j hℓ with g0 ≡ 0. The incremental coverage at round j is γj := P hj (X) = 1 | gj−1 (X) = 0, Y = 1 , the conditional probability that component detector hj catches a relevant item not yet caught by the previous detectors. If the conditioning event has zero probability, set γj = 1. To see how the incremental coverage probabilities determine the miss rate, first consider two component detectors. Since the union g2 misses an item exactly when both h1 and h2 miss it, {g2 (X) = 0} = {h1 (X) = 0, h2 (X) = 0}. Therefore, by the conditional-probability chain rule, L(g2 ) = P h1 (X) = 0, h2 (X) = 0 | Y = 1 = P h1 (X) = 0 | Y = 1 P h2 (X) = 0 | h1 (X) = 0, Y = 1 = (1 − γ1 )(1 − γ2 ). 26
More generally, {gJ (X) = 0} =
J \
{hj (X) = 0},
and
{gj−1 (X) = 0} =
j=1
j−1 \
{hℓ (X) = 0}.
ℓ=1
Repeated application of the conditional-probability chain rule therefore gives the exact identity L(gJ ) = P (gJ (X) = 0 | Y = 1) =
J Y
P hj (X) = 0 | gj−1 (X) = 0, Y = 1
j=1
=
J Y
(1 − γj ).
j=1
If P (gj−1 (X) = 0, Y = 1) = 0 for some j, then the previous union already misses no relevant items, so all subsequent miss rates are zero; the convention γj = 1 preserves the identity. Hence, using 1 − u ≤ exp(−u) for u ∈ [0, 1], J J Y X L(gJ ) = (1 − γj ) ≤ exp − γj . (4) j=1
j=1
This has the same informal flavour as boosting analyses [18]: later components are valuable only through the mass they recover among items not already captured by earlier components. The analogy is only structural, however. Here the union is a fixed OR-combination of candidate generators, and the identity is an exact coverage decomposition rather than a reweighting or margin argument. Identity (4) is not directly auditable because the γj are unobservable. The next theorem replaces them by Clopper–Pearson lower bounds computed on audited positives.
5.2
Auditing incremental coverage
The sharp overall bound on the conditional miss rate L(gJ ) is the direct excluded-pool-style certificate of Proposition 26 below, which pays a single confidence allocation and is what we recommend reporting. The purpose of this section is different and complementary: to attribute coverage to the individual components of an ordered union, so that an analyst can see how much each added detector contributes among items the earlier detectors still miss. The decomposition that follows is a diagnostic; as a bound on L(gJ ) it is deliberately looser than Proposition 26, for the reasons explained in Section 5.3. We now certify the per-component contributions of h1 , . . . , hJ to the coverage of the union gJ , rather than the coverage of the union as a whole. The question is how much each added component covers among relevant items that the earlier components still miss. The audited sample therefore consists of relevant items drawn according to P (· | Y = 1), rather than from the positives associated with any particular candidate generator or component. For round j, Qj is the number of audited positives not caught by the previous union gj−1 , and Hj is the number of those residual positives caught by the next component hj . A lower confidence bound on Hj /Qj gives a lower bound on the incremental coverage γj . Multiplying the resulting residual factors gives an upper bound on the conditional miss rate of the full union. Section 5.3 explains why this product bound is looser than the direct miss-rate certificate on L(gJ ), and why the decomposition is included for its per-component content rather than as the reported overall guarantee.
27
Theorem 24 (Auditable amplification). Suppose h1 , . . . , hJ and their order are fixed independently of the audit. Let Q be the number of audited positives. Conditional on Q, assume that + X1+ , . . . , XQ are independent draws from P (· | Y = 1). This includes, for example, a wholepopulation audit in which items are drawn from P , labelled, and the positives are retained. For j = 1, . . . , J, let Qj be the number of audited positives not caught by gj−1 , and let Hj be the number of these residual audited positives caught by hj . Let δ1 , . . . , δJ > 0 satisfy J X
δj ≤ δ.
j=1
With the convention L0 (0, α) = 0, define ℓbj = LQj (Hj , δj ),
j = 1, . . . , J.
Then, with probability at least 1 − δ, γj ≥ ℓbj
for all j = 1, . . . , J.
Consequently, L(gJ ) ≤
J Y
(1 − ℓbj ).
j=1
Proof. Fix j and assume P (Y = 1, gj−1 (X) = 0) > 0. Given {Qj = q} with q ≥ 1, the q audited positives with gj−1 (Xi+ ) = 0 are i.i.d. from P (· | Y = 1, gj−1 (X) = 0), and each is independently caught by hj with probability γj by Definition 23. Hence, conditional on {Qj = q}, Hj ∼ Bin(q, γj ), and Lemma 6, in its lower-bound form with the convention L0 (0, δj ) = 0, gives Paudit γj < LQj (Hj , δj ) ≤ δj . If instead P (Y = 1, gj−1 (X) = 0) = 0, then γj = 1 by convention and the lower bound is vacuously valid, so the displayed inequalityP holds for every j. A union bound over j = 1, . . . , J with Jj=1 δj ≤ δ gives the simultaneous lower bound on the γj . On the event where every γj ≥ LQj (Hj , δj ), monotonicity in each factor gives J Y
(1 − γj ) ≤
j=1
J Y
1 − LQj (Hj , δj ) ,
j=1
and identity (4) converts the left-hand side into L(gJ ). The product bound follows. Remark 25 (Sampling requirement). The conditional-i.i.d. assumption is the sampling condition needed for the binomial calculation. It allows Q, and the effective residual sizes Qj , to be random. What matters is that, conditional on the realised size, the retained positives are sampled from the appropriate conditional distribution. In particular, positives obtained only by reviewing the included pool {g(X) = 1} are distributed as P (· | Y = 1, g(X) = 1), not P (· | Y = 1), and do not satisfy the hypothesis without an additional reweighting or sampling argument. The same requirement applies to Proposition 26 and to Theorem 29. This also excludes audits in which the stopping rule, or the choice of which positives to retain, depends on whether positives are caught by particular components. Such dependence can change the conditional distribution of the residual positives and invalidate the binomial law for Hj | Qj .
28
5.3
Residual shrinkage and the direct alternative
The per-component bound LQj (Hj , δj ) on γj is informative only when Qj is large. By construction, Qj counts the audited positives that the previous union gj−1 has missed, so Q1 ≥ Q2 ≥ · · · ≥ QJ : each added component reduces the residual pool of misses, and the audit count available for the next round shrinks accordingly. In the regime where the union already catches most relevant items, Qj is small for large j, the Clopper–Pearson lower bound LQj (Hj , δj ) is correspondingly weak, often close to zero, and the per-round contribution of hj is hard to certify even when the underlying γj is large. The shrinkage is intrinsic to the decomposition: late-round detectors are exactly the ones whose contributions are hardest to demonstrate from positives alone. The product bound on L(gJ ) produced by Theorem 24 is not the tightest possible. The conditional analogue of Theorem 7, applied to the audited positives, gives a single direct certificate. Proposition 26 (Direct conditional miss-rate certificate). Under the audit design of Theorem 24, let CJ := #{i ≤ Q : gJ (Xi+ ) = 0} be the number of audited positives missed by the full union. Then, with probability at least 1 − δ, L(gJ ) ≤ UQ (CJ , δ), with the convention U0 (0, δ) = 1, so that an audit returning no positives (Q = 0) gives the trivial bound L(gJ ) ≤ 1. Proof. Conditional on Q, the audited positives are i.i.d. from P (· | Y = 1), so CJ ∼ Bin(Q, L(gJ )) with L(gJ ) = P (gJ (X) = 0 | Y = 1). Lemma 6 then gives the displayed inequality. PropositionP 26 is the natural overall guarantee: it pays a single confidence allocation δ rather than the split j δj ≤ δ, and it avoids the multiplicative accumulation of slack across rounds. When J = 1 and δ1 = δ, the two certificates coincide, since Un (k, α) = 1 − Ln (n − k, α) by the symmetry P(Bin(n, p) ≤ k) = P(Bin(n, 1 − p) ≥ n − k) of the binomial tails. The value of Theorem 24 is diagnostic: it shows how coverage accumulates across the ordered components. Late components may have small residual sample sizes Qj , making their individual lower bounds weak.
6
Stress-test cluster certificates
In many applications the candidate generator should be tested for brittleness under pre-specified perturbations: paraphrases, OCR corruptions, spelling variants, or other declared perturbation mechanisms. We now give a finite-sample certificate relative to a fixed stress-test generator A, which produces, for each item x, a set of variants A(x) ⊆ X . The certificate bounds the rate at which a relevant item has at least one variant in A(X) that g excludes. We call this event a cluster escape. The scope of the certificate is fixed by A in advance: variants produced by mechanisms outside A are not covered, and the result is not a general semantic-robustness guarantee but a certificate of g’s sensitivity to the particular perturbation mechanism the analyst has chosen to test.
6.1
Cluster generator and escape probability
Definition 27 (Stress-test generator). A stress-test generator is a measurable map A from X to finite non-empty subsets of X (or, more generally, to a distribution over finite non-empty subsets), fixed independently of the audit. The set A(x) is the stress-test cluster of x.
29
Examples include paraphrases generated by a fixed paraphrase model, OCR-corruption variants produced by a fixed corruption process, spelling variants generated by a declared rule, or perturbations produced by another pre-specified mechanism. Whether x itself belongs to A(x) is left to the modeller. A particularly relevant instance is the two-model semantic-adversarial framework of [4]. In that framework, admissible paraphrase perturbations are constrained using a proxy embedding, while their effect is evaluated through a distinct target model. For a fixed perturbation budget εpert and a fixed discrete paraphrase-generation procedure, let Aεpert (x) denote the resulting finite set, or distribution, of generated variants of x. This gives a special case of the stress-test generator A defined above. The certificates below then quantify either the probability that a relevant item has at least one generated adversarial variant excluded by g, or the expected fraction of its generated variants that are excluded. These guarantees are relative to the declared generator Aεpert . They do not by themselves certify robustness over the full continuous perturbation set; such a conclusion requires an additional covering or approximation condition. Definition 28 (Cluster escape probability). For a candidate generator g and stress-test generator A, define ρmax (g) := PX,A (∃z ∈ A(X) : g(z) = 0 | Y = 1) , X 1 ρavg (g) := EX,A 1{g(z) = 0} Y = 1 . |A(X)| z∈A(X)
The first is the probability that some variant in the cluster escapes the candidate set. The second is the expected fraction of variants in the cluster that escape. When A is randomised, the probability and expectation are taken over both X ∼ P (· | Y = 1) and an independent draw of the random cluster A(X). The two quantities answer different questions. The worst-cluster ρmax controls the probability that some variant in a sampled cluster escapes. The average ρavg controls the expected fraction of variants that escape. The worst-cluster is the more stringent guarantee and scales adversely with cluster size. The average-variant is more forgiving and is the natural quantity for clusterbalanced evaluation. Theorem 29 (Stress-test cluster certificate). Let G be a finite family of candidate generators and A a stress-test generator, both fixed independently of the audit. Let X1 , . . . , XQ be audited positives which, conditional on Q, are i.i.d. from P (· | Y = 1), and form clusters A(Xi ) independently across i (when A is randomised, its internal randomness is refreshed independently across i). For g ∈ G, define Wimax (g) = 1{∃z ∈ A(Xi ) : g(z) = 0}. Let K max (g) = realised clusters
PQ
max (g). i=1 Wi
In addition, draw Z1 , . . . , ZQ so that, conditionally on the (Xi , A(Xi ))Q i=1 ,
they are independent and each Zi is uniformly distributed on A(Xi ). The auxiliary randomisation used for these P draws is independent of the audit labels and of the internal randomness of A. Let K rand (g) = Q i=1 1{g(Zi ) = 0}. Then, with probability at least 1 − δ, simultaneously over g ∈ G, δ δ max rand ρmax (g) ≤ UQ K (g), , ρavg (g) ≤ UQ K (g), . 2|G| 2|G| Both bounds are read as the trivial value 1 when Q = 0.
30
Proof. The two bounds are handled separately. Throughout, Q is treated as fixed. All probability statements below are conditional on Q, and the unconditional statement follows by averaging, as in Lemma 6. Worst-cluster bound. For each i = 1, . . . , Q, the audited positive Xi is i.i.d. from P (· | Y = 1), and when A is randomised, its internal randomness at index i is independent across i by assumption. The indicator Wimax (g) = 1{∃z ∈ A(Xi ) : g(z) = 0} is a measurable function of Xi and of the independent cluster-generator randomness at index i. The variables {Wimax (g)}Q i=1 are therefore i.i.d., and each is Bernoulli with EX,A [Wimax (g)] = PX,A (∃z ∈ A(Xi ) : g(z) = 0 | Yi = 1) = ρmax (g), where the second equality is Definition 28. Hence K max (g) =
Q X
Wimax (g) ∼ Bin(Q, ρmax (g)).
i=1
The Clopper–Pearson upper bound for the binomial proportion satisfies, for every α ∈ (0, 1), Paudit {ρmax (g) > UQ (K max (g), α) | Q} ≤ α. Applying this with α = δ/(2|G|) for each fixed g and taking a union bound over G gives the simultaneous worst-cluster statement with failure probability at most δ/2. Average-variant bound. Conditional on Q, the triples (Xi , A(Xi ), Zi ) are i.i.d. across i: the pairs (Xi , A(Xi )) are i.i.d. by assumption, and the conditional law of Zi given the pair depends only on A(Xi ). Writing Vi (g) := 1{g(Zi ) = 0} and averaging over the uniform choice of Zi within its cluster, X 1 1{g(z) = 0} Yi = 1 = ρavg (g), EX,A [Vi (g)] = EX,A |A(Xi )| z∈A(Xi )
by Definition 28. Hence K rand (g) =
Q X
Vi (g) ∼ Bin(Q, ρavg (g)),
i=1
and the Clopper–Pearson upper bound at level δ/(2|G|) for each fixed g, with a union bound over G, gives the simultaneous average-variant statement with failure probability at most δ/2. The single draw Zi serves every g ∈ G at once, since it does not depend on g. Combining the two families of bounds gives the displayed joint statement with total failure probability at most δ. Remark 30 (Budget split between the two bounds). The error budget need not be divided evenly between the two bounds. The allocation δ/2 to each family may be replaced by any split δmax + δavg ≤ δ, fixed before the audit, with the larger share given to whichever guarantee is the operational target. Remark 31 (Why draw one variant per cluster?). The single draw Zi makes the average-variant certificate an exact binomial certificate. Indeed, 1{g(Zi ) = 0} is Bernoulli with mean ρavg (g). Thus no additive concentration term is needed.
31
This can matter in the rare-escape regime. For example, with Q = 300 and error budget 0.025, zero observed escapes gives the exact bound U300 (0, 0.025) = 0.0122. By contrast, a Hoeffding bound for the empirical mean of the within-cluster escape fractions has additive term s log(1/0.025) = 0.0784. 2Q P P −1 The empirical-mean route, based on ρbavg (g) = Q−1 Q z∈A(Xi ) 1{g(z) = 0}, is i=1 |A(Xi )| still available when all variant values have been computed, but it is usually less sharp near zero. If the seed x is included in every cluster, then ρmax (g) ≥ L(g), since an ordinary miss is a cluster escape. Otherwise the two quantities are not ordered. The certificate is relative to the declared perturbation mechanism A. It is not a general semantic-robustness guarantee: it certifies escape only for the variants produced by A. Its role is to distinguish ordinary coverage on positives drawn from P from brittleness under the specified perturbations.
7
Design-stage selection from a class
Section 2.4 allowed design choices before the certification labels are opened. We now give several formal ways to make such choices over finite, VC, and structured candidate-generator classes. Labelled design data may be used by a design-stage selector to choose a candidate generator g before certification, using standard finite-class, VC, sparse-union, and Neyman–Pearson guarantees expressed in the one-sided coverage notation used here. The selected candidate generator should then be certified on an independent held-out audit using the certificates of Sections 4–6. The design-stage selector is distinct from any downstream classifier trained or deployed after candidate generation. For this section only, let H denote a class of measurable candidate generators g : X → {0, 1}.2 A design sample from the whole population consists of i.i.d. pairs (Xi , Yi )ni=1 with Xi ∼ P and Yi = φ⋆ (Xi ). Define n
1X rbn (g) = 1{Yi = 1, g(Xi ) = 0}, n i=1
bn (g) = B
n 1X
n
1{g(Xi ) = 1}.
i=1
A candidate generator is positive-consistent on the design sample if rbn (g) = 0. It is labelconsistent if, in addition, it has no false positives on the sample.
7.1
Why unrestricted coverage selection is vacuous
The one-sided objective alone does not define a meaningful design-stage selection problem. Proposition 4 gives the degeneracy: the constant candidate generator g ≡ 1 has zero missed mass, so an unrestricted coverage objective can be satisfied with no labelled data. The two useful restrictions are the same ones used throughout the paper. First, the designstage selector may be required to output g ∈ H for a fixed class H. This is the standard proper-learning restriction, meaning that the selector must output a candidate generator in the class it is searching over. Second, review burden may enter as an objective or constraint. This is the Neyman–Pearson formulation. In applications both restrictions are usually present: the analyst searches over a structured candidate-generator class and also imposes a burden target. 2 For infinite classes we assume throughout the standard measurability conditions under which the suprema of the relevant empirical processes are measurable.
32
7.2
Proper learning: finite classes and VC classes
The following finite-class bound gives the basic sample-size rule for a design split. It is a onesided version of the standard realisable PAC bound [46] for a design-stage selector. Theorem 32 (Finite-class design bound). Let H be finite, and suppose there exists g ⋆ ∈ H with r(g ⋆ ) = 0. From a whole-population design sample of size n, let gb ∈ H be any positive-consistent candidate generator. Then, with probability at least 1 − δ, r(b g) ≤
log(|H|/δ) . n
The conversion from absolute missed mass to conditional miss rate carries a prevalence penalty. Corollary 33 (Prevalence cost for recall). Under the assumptions of Theorem 32, assume π = P (Y = 1) > 0, where π is the prevalence of relevant items. If n≥
log(|H|/δ) , πεL
then L(b g ) ≤ εL with probability at least 1 − δ. For infinite classes, the cardinality term is replaced by VC complexity. For a binary class H, its VC dimension is the largest integer d for which there exist points x1 , . . . , xd such that every binary labelling of those points is realised by some h ∈ H. If no largest finite d exists, the VC dimension is infinite. Finite VC dimension is the standard combinatorial condition that permits distribution-free uniform convergence over an infinite class. Theorem 34 (VC-class design bound). Let H have VC dimension d, suppose there exists g ⋆ ∈ H with r(g ⋆ ) = 0, and assume n ≥ d. From a whole-population design sample of size n, let gb ∈ H be any positive-consistent candidate generator. Then, with probability at least 1 − δ, r(b g) ≤ C
d log(en/d) + log(1/δ) n
for a universal constant C. The constant C can be made explicit by choosing a standard realisable VC inequality [6,47]. Its exact value is not material for the audit certificates, which are computed on an independent held-out certification sample.
7.3
Agnostic variants
The realisable bounds above are clean baselines. In text and other ambiguous domains, the design class may contain no candidate generator with zero missed mass. Empirical missed-mass minimisation then gives the agnostic guarantees below, under the rule gb ∈ arg ming∈H rbn (g). Theorem 35 (Agnostic finite-class design bound). Let H be finite and let gb ∈ arg ming∈H rbn (g). With probability at least 1 − δ, r log(2|H|/δ) r(b g ) ≤ inf r(g) + 2 . g∈H 2n Theorem 36 (Agnostic VC-class design bound). Let H have VC dimension d, assume n ≥ d, and let gb ∈ arg ming∈H rbn (g). With probability at least 1 − δ, for a universal constant C, r d log(en/d) + log(1/δ) r(b g ) ≤ inf r(g) + C . g∈H n 33
These agnostic design bounds are often the operationally relevant ones. They still describe the design-stage selector and do not replace held-out certification of the realised candidate generator. We give the proofs and brief lower-bound context in Appendix A. Theorems 32 and 34 control the design procedure, not the realised generator by itself. They give high-probability guarantees over the random design sample. A data-dependent certificate for the selected generator still requires held-out certification labels, as in the earlier audit certificates.
7.4
Burden-constrained selection
The bicriteria formulation in Section 3 suggests a Neyman–Pearson design rule: minimise review burden subject to a missed-mass constraint. Let inf B(g)
g∈H
subject to
r(g) ≤ ε
(5)
be the population problem. The design rule is the empirical version of this optimisation problem: it replaces the population probabilities by their sample estimates and chooses a candidate generator minimising the resulting empirical objective: bn (g) min B g∈H
subject to rbn (g) ≤ ε − τn ,
(6)
where τn is a uniform-convergence slack. Theorem 37 (Neyman–Pearson design bound). Let H have VC dimension d and assume n ≥ d. There is a universal constant C > 0 such that the following holds. Let r d log(en/d) + log(2/δ) τn = C . n Let gb solve (6), with gb defined arbitrarily in H if the empirical feasible set is empty. On the event used in the proof, the feasible set is non-empty. If there exists g ∈ H with r(g) ≤ ε − 2τn , then, with probability at least 1 − δ, (i) r(b g ) ≤ ε. (ii) B(b g ) ≤ inf{B(g) : g ∈ H, r(g) ≤ ε − 2τn } + 2τn . Theorem 37 is the design-stage analogue of Neyman–Pearson classification [8, 36, 38]. It applies when the analyst wants to tune a candidate generator before final certification, balancing observable review burden against a missed-mass constraint. The empirical rule in (6) searches for a low-burden candidate generator, but enforces the stricter design constraint rbn (g) ≤ ε−τn to leave room for uniform-convergence error. The theorem then gives two guarantees: the selected candidate generator satisfies the target missed-mass constraint r(b g ) ≤ ε, and its burden is within 2τn of the best population burden among candidate generators satisfying the margin condition r(g) ≤ ε − 2τn .
7.5
Sparse unions of base detectors
Candidate generators are often unions of weak detectors, such as keyword rules, regularexpression templates, embedding-neighbourhood filters, or score thresholds. If C is a base detector class, define C ∪k =
max cj : cj ∈ C , j≤k
with repetitions allowed. Because the cj are {0, 1}-valued, maxj≤k cj is the indicator of S ∪k is the class of k-fold unions of sets in C. The standard VC compo{c j≤k j = 1}, so C sition bound [6] gives VC(C ∪k ) ≤ 2 VC(C) k log2 (3k). 34
The logarithm here is to base two, and the k log k order is unavoidable: there are base classes with VC(C ∪k ) = Ω(dC k log k) [16], so no composition bound of order dC k holds in general. Theorem 38 (Sparse-union design bound). Let C have VC dimension dC ≥ 1, let k ≥ 1 be an integer, and let H = C ∪k . Suppose there exists g ⋆ ∈ H with r(g ⋆ ) = 0, and assume n ≥ D, where D = 2 dC k log2 (3k) bounds the VC dimension of H (the base of the logarithm, and the replacement of log(en/D) by log n in the displayed rate, affect only the constant C). From a whole-population design sample of size n, let gb ∈ H be any positive-consistent candidate generator. Then, with probability at least 1 − δ, r(b g) ≤ C
dC k log(3k) log n + log(1/δ) . n
Remark 39. If in addition some g ⋆ ∈ H satisfies P (g ⋆ (X) ̸= Y ) = 0 and gb is label-consistent on the design sample, then the same VC argument applied to the symmetric-difference loss controls the total error P (b g (X) ̸= Y ) at the same rate, and hence bounds both r(b g ) and the false-positive mass b(b g ). We use this statement when precision, and not only review burden, b(g) must be certified. The precision 1 − B(g) , defined when B(g) > 0, depends on both the falsepositive mass b(g) and the burden B(g). In the finite-corpus model, B(g) is known exactly from the generator values. In the population model, it must instead be estimated or lower-bounded using independent unlabelled data. Thus, an upper confidence bound b(g) and a positive lower b(g) confidence bound B(g) give the certificate Precision(g) ≥ 1 − B(g) . The missed-mass bound alone does not constrain b(g).
8
Worked example: audit planning and certification
We now illustrate how to use the preceding certificates as an audit plan and reporting template. The numbers are deterministic calculations from the stated audit outcomes. Practical audit design recipe.
A typical certification workflow is:
1. Fix the candidate generator, candidate-generator family, or prefix sequence before opening the certification labels. 2. Compute unlabelled quantities such as burden B(g), excluded-pool mass p0 (g), and pool memberships. 3. Choose the acceptable missed-mass threshold ε and the overall certificate failure probability δ. If several candidate generators are to be certified simultaneously, allocate failure probabilities δg > 0 satisfying X δg ≤ δ, g∈G
for example, δg = δ/|G|. 4. Audit according to the sampling design matched to the desired certificate: excluded pool for absolute missed mass, both sides or a population sample for recall, and a shared reference sample for pre-specified prefixes. 5. Convert the audit counts into simultaneous upper bounds U (g). 6. Report the least burdensome pre-specified candidate generator satisfying U (g) ≤ ε.
35
Suppose a corpus contains N = 100,000 sentences. A candidate generator g flags 30,000 sentences for review and excludes 70,000, so the observed burden is BN (g) = 0.30,
p0,N (g) = 0.70.
The audit target is a 95% certificate. We reserve δ0 = 0.025 for the excluded-pool missed-mass certificate and δ1 = 0.025 for the included-pool lower bound used in the recall calculation. Absolute missed mass. Draw n0 = 300 items uniformly from the excluded pool and label them. If no relevant item is found (K0 = 0), then U300 (0, 0.025) = 1 − 0.0251/300 ≈ 0.01222. The excluded-pool certificate gives r(g) ≤ 0.70 U300 (0, 0.025) ≤ 0.00856. Equivalently, in a corpus of 100,000 items, the corresponding bound is approximately 855.47 missed relevant sentences, or 856 after upward rounding to a whole sentence. Thus the same audit certifies that the absolute missed relevant mass is below one percent of the corpus. The audit draws uniformly without replacement from a finite excluded pool, yet the calculation uses the binomial bound U300 . With zero observed misses this binomial bound is conservative under sampling without replacement. The exact hypergeometric inversion of Theorem 8 gives the slightly smaller finite-corpus bound MU = 853, that is r(g) ≤ 0.00853. The certificate is sensitive to the observed audit count. Keeping n0 = 300, p0,N (g) = 0.70, N0 = 70,000, and δ0 = 0.025 fixed, the exact finite-corpus (hypergeometric) certified missedmass bound becomes: Excluded-pool positives K0 0 1 2
Exact MU (K0 , 0.025) 853 1,287 1,668
Certified upper bound on r(g) 0.00853 0.01287 0.01668
This illustrates why the zero-miss case is operationally valuable: even one or two missed relevant items in the audit can move the certificate above a one-percent missed-mass target. Two-pool recall. To translate the missed-mass certificate into a recall statement, audit the included pool as well. Suppose n1 = 500 included-pool items are labelled uniformly without replacement and K1 = 100 are relevant. The exact finite-corpus lower inversion in Corollary 11 gives ML (100, 0.025) = 4,983. The included relevant mass is therefore bounded below by 4,983/100,000 = 0.04983. Combining this lower bound with the exact excluded-pool upper bound MU = 853 gives the two-pool recall certificate M1 (g) 4,983 Recall(g) = ≥ ≥ 0.8538. M1 (g) + M0 (g) 4,983 + 853 The reported statement is therefore: with simultaneous confidence at least 95%, the candidate generator has burden 30%, absolute missed relevant mass at most 0.853% of the corpus, and recall at least 85.3%. More generally, any finite collection of the certificates in this paper can be reported jointly by allocating error shares that sum to δ and taking a union bound, so a single audit can carry burden, missed-mass, recall, and stress-test statements about one fixed candidate generator at a stated joint confidence. Once these simultaneous bounds have been constructed, they may 36
be compared with any number of targets, including targets chosen after the audit, without any further multiplicity adjustment. A fresh error allocation is required only for additional certificates concerning candidate generators or estimands not covered by the original jointly certified family. Prefix choice. Now suppose the analyst pre-specifies three prefix unions g1 , g2 , g3 before opening the certification audit. The audit goal is to choose the least burdensome prefix whose certified missed mass is at most 1% of the corpus. Use separate excluded-pool audits with nm = 300 for each prefix and allocate δm = 0.05/3. If each excluded-pool audit observes no relevant item, then U300 (0, 0.05/3) ≈ 0.01356. The burdens below are illustrative, chosen only to make the example concrete. The excluded masses are their complements p0,N (gm ) = 1 − BN (gm ), and each certified bound is the excluded mass times this factor, r(gm ) = p0,N (gm ) η(gm ) ≤ p0,N (gm ) U300 (0, 0.05/3). The simultaneous certificates are: Prefix
Burden BN (gm )
Excluded mass p0,N (gm )
Km
Certified r(gm ) ≤ p0,N (gm ) U300
g1 g2 g3
0.15 0.30 0.38
0.85 0.70 0.62
0 0 0
0.0116 0.00949 0.00841
The valid post-audit choice is g2 : it is the least burdensome pre-specified prefix whose simultaneous certificate meets the 1% missed-mass target. The third prefix gives a tighter certificate, but its additional eight percentage points of review burden are not needed for this target. This is the bicriteria formulation in operational form: the certificate controls missed mass, and burden selects among certified candidates. Comparison with a whole-population audit. To match the bound r(g) ≤ 0.00853 from the excluded-pool calculation using a whole-population audit, sampling i.i.d. from P rather than from {g = 0}, with zero observed events and the same δ = 0.025 confidence allocation, n≥
log(1/0.025) ≈ 431 log 1/(1 − 0.00853)
labels are required. The excluded-pool design achieves the same bound with n0 = 300. The ratio 300/431 ≈ 0.70 = p0,N (g) matches the planning identity from Section 4.6: at zero observed events, the whole-population audit needs about 1/p0 (g) times as many labels as the excludedpool audit at the same target. The excluded-pool gain in this example is therefore modest, because the excluded pool is large. The gain grows as the excluded pool shrinks: a hypothetical later candidate generator that flagged 80% of the corpus, leaving p0,N (g) = 0.20, would require about five times more whole-population labels than excluded-pool labels for the same target. Beyond labelling cost, the excluded-pool design has an interpretive advantage independent of p0 (g): every audited item is drawn from the only region in which missed relevant items can occur.
9
Conclusion and future directions
This paper developed finite-sample certificates for missed relevant mass and recall in high-recall candidate generation. The central point is that the excluded pool is the only place where missed relevant items can occur. Auditing that pool directly gives exact binomial and hypergeometric certificates for missed mass, and these can be converted into recall guarantees when suitable 37
denominator information is available. The same framework also supports simultaneous certification of pre-specified candidate-generator families, prefix sequences, component decompositions, and stress tests. The guarantees rely on a strict separation between design and certification. Candidate generators may be built, tuned, and ordered using design data, but the labels used for final certification must not have influenced the candidate generator being certified. Once certification labels have been opened, they can guide a later design round, but a fresh certification audit, or a pre-specified sequential-validity device, is needed for the next certificate. Stratified audits. The i.i.d. excluded-pool audit can be replaced by a stratified design that splits the excluded pool into observable subgroups, or strata, and assigns more audit labels to strata more likely to contain missed relevant items. A stratum might group items by the candidate generator’s underlying score, by document category, or by time period. For a partition of the excluded pool into strata As with known masses ws = P (As | g(X) = 0) and stratum (s) (s) conditional counts K0 ∼ Bin n0 , ηs (g) , where P ηs (g) = P (Y = 1 | X ∈ As , g(X) = 0), a union bound gives, with probability at least 1 − s δs , X X (s) η(g) = ws ηs (g) ≤ ws Un(s) K0 , δs , s
s
0
and hence the corresponding bound on r(g) = p0 (g)η(g). This permits oversampling of strata expected to contain misses while retaining a distribution-free certificate. The finite-corpus version replaces the binomial inversions by the hypergeometric inversions of Theorem 8 within each stratum. Label noise. The certification results above treat audit labels as ground truth. For the i.i.d. excluded-pool missed-mass certificate, suppose instead that the oracle returns a noisy label Ye with per-item sensitivity s(X) := P (Ye = 1 | Y = 1, X) ≥ smin for a known smin ∈ (0, 1], and that the noisy labels are realised independently across audited items conditional on the audited items. Writing ηe(g) := P (Ye = 1 | g(X) = 0), we have ηe(g) ≥ smin η(g). Moreover, e 0 ∼ Bin n0 , ηe(g) , K so the Clopper–Pearson bound gives, with probability at least 1 − δ, ( ) e 0 , δ) Un0 (K r(g) ≤ p0 (g) min 1, . smin False-positive audit labels can only increase ηe(g) and therefore make this upper bound more conservative. This argument is specific to the i.i.d. excluded-pool missed-mass certificate. The two-pool recall certificate also requires a valid lower bound on η1 (g) = P (Y = 1 | g(X) = 1). A sensitivity floor alone does not provide such a lower bound, because false-positive audit labels may inflate the observed positive rate in the included pool. Extending the two-pool recall 38
certificate therefore requires an additional assumption, such as a known specificity floor, or adjudicated labels. Likewise, Theorem 24, Proposition 26, and Theorem 29 sample conditional on true relevance Y = 1. Replacing true relevance labels by noisy labels changes that conditional sampling distribution, so those results require additional noise assumptions or adjudicated labels. Further directions. Several directions remain open. One is to develop sharper sequential methods for iterative audit-and-redesign workflows, so that certification can proceed over multiple rounds without discarding information. A second is to combine excluded-pool certification with richer models of label noise, adjudication, and reviewer disagreement. A third is to extend the stress-test certificates to structured perturbation spaces, where the declared perturbation mechanism A is replaced by geometric or semantic neighbourhoods. The component-union perspective also raises computational questions. Since coverage is naturally submodular in the selected components, one can ask for efficient algorithms for choosing low-burden, high-coverage unions under cardinality or cost constraints. This connects the certification problem to submodular optimisation and knapsack-type selection [34, 41], but we leave a systematic treatment to future work. The overall message is that high-recall candidate generation can be certified directly, without requiring a fully specified downstream classifier or a full-corpus relevance audit. The price is discipline in the audit design: the candidate generator, or the pre-specified family from which it is selected, and the audit rule must be fixed before the certification labels are examined.
A
Learning-theoretic proofs and extended statements
This appendix gives the proofs for Section 7. They are standard applications of finite-class union bounds, VC uniform convergence, and Neyman–Pearson plug-in selection. They are included to make the audit workflow self-contained.
A.1
Proof of the finite-class design bound
Proof of Theorem 32. Set ε = log(|H|/δ)/n. Fix g ∈ H with r(g) > ε. On a whole-population design sample, the probability that g is positive-consistent is Pdesign {b rn (g) = 0} = (1 − r(g))n ≤ e−nε . Therefore Pdesign {∃g ∈ H : rbn (g) = 0, r(g) > ε} ≤ |H|e−nε = δ. On the complement of this event, every positive-consistent candidate generator in H has missed mass at most ε. The assumption that some g ⋆ ∈ H has r(g ⋆ ) = 0 ensures that at least one positive-consistent member exists. Proof of Corollary 33. The identity r(g) = πL(g) holds for every candidate generator when π = P (Y = 1) > 0. Theorem 32 gives r(b g ) ≤ log(|H|/δ)/n with probability at least 1 − δ. The displayed lower bound on n therefore implies L(b g ) ≤ εL . The exact zero-observed-miss calculation gives the alternative sufficient condition n≥
log(|H|/δ) , log(1/(1 − πεL ))
which is slightly sharper for non-small πεL .
39
A.2
Proof of the VC-class design bound
Proof of Theorem 34. Consider the loss class Lr = {(x, y) 7→ 1{y = 1, g(x) = 0} : g ∈ H}. Its VC dimension is at most the VC dimension d of H, since it is the class of complements of candidate-generator sets restricted to the slice y = 1. The standard realisable VC bound [6, 47] says that, with probability at least 1 − δ, every member of Lr with zero empirical loss has population loss at most d log(en/d) + log(1/δ) C . n A positive-consistent gb has zero empirical loss in Lr , so the result follows.
A.3
Agnostic variants and lower bounds
p Proof of Theorem 35. Write s = log(2|H|/δ)/(2n). For gb ∈ arg ming∈H rbn (g), Hoeffding’s inequality and a union bound over H give, with probability at least 1 − δ, sup |r(g) − rbn (g)| ≤ s.
g∈H
On that event r(b g ) ≤ rbn (b g ) + s. Since gb minimises rbn and rbn (g) ≤ r(g) + s for every g, we have rbn (b g ) ≤ inf g∈H r(g) + s, and the stated bound r(b g ) ≤ inf g∈H r(g) + 2s follows. This controls missed mass alone. Burden can be handled by class design, by a separate burden constraint, or by the Neyman–Pearson rule of Theorem 37. Proof of Theorem 36. The same argument with the uniform-convergence inequality for a VC class of dimension d in place of the finite-class union bound gives, with probability at least 1 − δ, r d log(en/d) + log(1/δ) sup |r(g) − rbn (g)| ≤ C , n g∈H and hence r(b g ) ≤ inf g∈H r(g) + C into C.
p (d log(en/d) + log(1/δ))/n after absorbing the factor two
The confidence term cannot be improved in distribution-free zero-miss certification. Any procedure that observes zero misses in n Bernoulli trials and certifies miss probability at most ε with confidence 1 − δ must have n≥
log(1/δ) . log(1/(1 − ε))
Otherwise, under a Bernoulli law with miss probability p > ε, the zero-miss event has probability (1 − p)n > δ for p close enough to ε, making the certificate invalid. The class-complexity term (log |H|)/ε is also unavoidable in the worst case: there are finite classes of cardinality |H| with VC dimension of order log |H|, and the standard PAC lower bound of Ehrenfeucht, Haussler, Kearns, and Valiant applies to such classes [15].
A.4
Proof of the Neyman–Pearson design bound
Proof of Theorem 37. The same VC dimension controls both uniform deviations used below. For B(g), the relevant class is {x : g(x) = 1}, g ∈ H,
40
which has VC dimension d. For r(g), the relevant class is {(x, y) : y = 1, g(x) = 0},
g ∈ H.
This class has VC dimension at most d, since points with y = 0 can never be labelled 1, while on points with y = 1 it is the complement class of H. Thus a single VC uniform-convergence bound, with a union bound over the two classes, controls both r and B. By the definition of τn , with probability at least 1 − δ the event ) ( bn (g)| ≤ τn E = sup |r(g) − rbn (g)| ≤ τn , sup |B(g) − B g∈H
g∈H
holds. Work on E. The hypothesis supplies a g with r(g) ≤ ε − 2τn , hence rbn (g) ≤ r(g) + τn ≤ ε − τn , so the empirical feasible set {g : rbn (g) ≤ ε − τn } is non-empty and gb is well-defined. Since gb is empirically feasible, meaning rbn (b g ) ≤ ε − τn , r(b g ) ≤ rbn (b g ) + τn ≤ ε. Now let g ◦ be any candidate generator satisfying r(g ◦ ) ≤ ε − 2τn . Then rbn (g ◦ ) ≤ r(g ◦ ) + τn ≤ ε − τn , so g ◦ is empirically feasible. Since gb minimises empirical burden over the empirical feasible set, bn (b bn (g ◦ ) ≤ B(g ◦ ) + τn . B g) ≤ B Converting back to population burden gives bn (b B(b g) ≤ B g ) + τn ≤ B(g ◦ ) + 2τn . Taking the infimum over all g ◦ with r(g ◦ ) ≤ ε − 2τn proves the claim.
A.5
Proof of the sparse-union design bound
Proof of Theorem 38. The class C ∪k has VC dimension at most 2dC k log2 (3k) by the standard union-composition bound [6]. The missed-mass loss class {(x, y) 7→ 1{y = 1, g(x) = 0} : g ∈ C ∪k } has VC dimension at most that of C ∪k , since restricting to the slice {y = 1} cannot increase the number of realisable labellings. Positive-consistency makes the empirical missed-mass loss of gb zero, so the realisable VC bound of Theorem 34, applied to H = C ∪k with d ≤ 2dC k log2 (3k), gives dC k log(3k) log n + log(1/δ) r(b g) ≤ C n with probability at least 1−δ. For the remark, label-consistency makes the empirical symmetricdifference loss zero. The same realisable VC bound, applied to the loss class {(x, y) 7→ 1{g(x) ̸= y}} of the same VC order, controls P (b g (X) ̸= Y ), and r(b g ) and b(b g ) are its two disjoint components.
References [1] A. N. Angelopoulos, S. Bates, E. J. Candès, M. I. Jordan, and L. Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. Annals of Applied Statistics, 19(2):1641–1662, 2025. 41
[2] A. N. Angelopoulos, S. Bates, A. Fisch, L. Lei, and T. Schuster. Conformal risk control. In International Conference on Learning Representations (ICLR), 2024. [3] M. Anthony and P. L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999. [4] M. Anthony and K. Salehzadeh Nobari. Generalised eigenvalue geometry of semantic adversarial attacks. arXiv preprint arXiv:2606.19212, 2026. https://doi.org/10.48550/ arXiv.2606.19212. [5] P. Bauer. Multiple testing in clinical trials. Statistics in Medicine, 10(6):871–890, 1991. [6] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik– Chervonenkis dimension. Journal of the ACM, 36(4):929–965, 1989. [7] M. W. Callaghan and F. Müller-Hansen. Statistical stopping criteria for automated screening in systematic reviews. Systematic Reviews, 9:Article 273, 2020. [8] A. Cannon, J. Howse, D. Hush, and C. Scovel. Learning with the Neyman–Pearson and min-max criteria. Technical Report LA-UR-02-2951, Los Alamos National Laboratory, 2002. [9] C. J. Clopper and E. S. Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404–413, 1934. [10] G. V. Cormack and M. R. Grossman. Evaluation of machine-learning protocols for technology-assisted review in electronic discovery. In Proceedings of the 37th International ACM SIGIR Conference (SIGIR 2014), pp. 153–162, 2014. [11] G. V. Cormack and M. R. Grossman. Autonomy and reliability of continuous active learning for technology-assisted review. arXiv preprint arXiv:1504.06868, 2015. https://doi.org/ 10.48550/arXiv.1504.06868. [12] G. V. Cormack and M. R. Grossman. Engineering quality and reliability in technologyassisted review. In Proceedings of the 39th International ACM SIGIR Conference (SIGIR 2016), pp. 75–84, 2016. [13] G. V. Cormack and M. Mojdeh. Machine learning for information retrieval: TREC 2009 Web, Relevance Feedback and Legal Tracks. In Proceedings of the 18th Text REtrieval Conference (TREC 2009), 2009. [14] L. Devroye and G. L. Wise. Detection of abnormal behavior via nonparametric estimation of the support. SIAM Journal on Applied Mathematics, 38(3):480–488, 1980. [15] A. Ehrenfeucht, D. Haussler, M. Kearns, and L. Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247–261, 1989. [16] D. Eisenstat and D. Angluin. The VC dimension of k-fold union. Information Processing Letters, 101(5):181–184, 2007. [17] P. Elchafei, M. Swain, S. Masoudian, and M. Schedl. Facet-level tracing of evidence uncertainty and hallucination in RAG. arXiv preprint arXiv:2604.09174, 2026. https: //doi.org/10.48550/arXiv.2604.09174. [18] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997. 42
[19] M. R. Grossman and G. V. Cormack. The Grossman–Cormack glossary of technologyassisted review. Federal Courts Law Review, 7(1):1–34, 2013. [20] M. R. Grossman and G. V. Cormack. Vetting and validation of AI-enabled tools for electronic discovery. In J. Presser, J. Beatson, and G. Chan (eds.), Litigating Artificial Intelligence, chapter 13. Emond Publishing, 2021. [21] J. A. Hanley and A. Lippman-Hand. If nothing goes wrong, is everything all right? Interpreting zero numerators. Journal of the American Medical Association, 249(13):1743–1745, 1983. [22] J. J. Heckman. Sample selection bias as a specification error. Econometrica, 47(1):153–161, 1979. [23] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. Annals of Statistics, 49(2):1055–1080, 2021. [24] J. C. Hsu and R. L. Berger. Stepwise confidence intervals without multiplicity adjustment for dose-response and toxicity studies. Journal of the American Statistical Association, 94(446):468–482, 1999. [25] K. K. G. Lan and D. L. DeMets. Biometrika, 70(3):659–663, 1983.
Discrete sequential boundaries for clinical trials.
[26] M. Lease, G. V. Cormack, A. T. Nguyen, T. A. Trikalinos, and B. C. Wallace. Systematic review is e-discovery in doctor’s clothing. In SIGIR 2016 MedIR Workshop, 2016. [27] D. D. Lewis, E. Yang, and O. Frieder. Certifying one-phase technology-assisted reviews. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management (CIKM 2021), pp. 893–902, 2021. [28] P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W. Yih, T. Rocktäschel, S. Riedel, and D. Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), pp. 9459–9474, 2020. [29] R. J. A. Little and D. B. Rubin. Statistical analysis with missing data. John Wiley & Sons, 2019. [30] A. Liu and B. D. Ziebart. Robust classification under sample selection bias. Advances in Neural Information Processing Systems, 27, 2014. [31] W. Magdy and G. J. F. Jones. PRES: A score metric for evaluating recall-oriented information retrieval applications. In Proceedings of the 33rd Annual International ACM SIGIR Conference (SIGIR 2010), pp. 611–618, 2010. [32] W. Maurer, L. Hothorn, and W. Lehmacher. Multiple comparisons in drug clinical trials and preclinical assays: a priori ordered hypotheses. In J. Vollmar (ed.), Biometrie in der chemisch-pharmazeutischen Industrie, volume 6, pp. 3–18. Fischer, Stuttgart, 1995. [33] B. K. Natarajan. On learning Boolean functions. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC 1987), pp. 296–304, 1987. [34] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14:265–294, 1978. [35] W. Polonik. Measuring mass concentrations and estimating density contour clusters: an excess mass approach. Annals of Statistics, 23(3):855–881, 1995. 43
[36] P. Rigollet and X. Tong. Neyman–Pearson classification, convexity and stochastic constraints. Journal of Machine Learning Research, 12:2831–2855, 2011. [37] E. G. Schilling and D. V. Neubauer. Acceptance Sampling in Quality Control. Chapman and Hall/CRC, third edition, 2017. [38] C. Scott and R. Nowak. A Neyman–Pearson approach to statistical learning. IEEE Transactions on Information Theory, 51(11):3806–3819, 2005. [39] C. Scott and R. Nowak. Learning minimum volume sets. Journal of Machine Learning Research, 7:665–704, 2006. [40] A. Sneyd and M. Stevenson. Stopping criteria for technology-assisted reviews based on counting processes. In Proceedings of the 44th International ACM SIGIR Conference (SIGIR 2021), pp. 2293–2297, 2021. [41] M. Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41–43, 2004. [42] X. Tong. A plug-in approach to Neyman–Pearson classification. Journal of Machine Learning Research, 14:3011–3040, 2013. [43] A. B. Tsybakov. On nonparametric estimation of density level sets. Annals of Statistics, 25(3):948–969, 1997. [44] F. Tuyl, R. Gerlach, and K. Mengersen. The rule of three, its variants and extensions. International Statistical Review, 77(2):266–275, 2009. [45] W. Uhlmann. Vergleich der hypergeometrischen mit der Binomial-Verteilung. Metrika, 10(1):145–158, 1966. [46] L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. [47] V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264–280, 1971. [48] W. Webber. Approximate recall confidence intervals. ACM Transactions on Information Systems, 31(1):Article 2, 2013. [49] R. M. Willett and R. D. Nowak. Minimax optimal level-set estimation. IEEE Transactions on Image Processing, 16(12):2965–2979, 2007. [50] E. Yang, D. D. Lewis, and O. Frieder. Heuristic stopping rules for technology-assisted review. In Proceedings of the 21st ACM Symposium on Document Engineering (DocEng 2021), pp. 31:1–31:10, 2021.
44