Not All Mislabels Are Equal: Efficient Task-Aware Auditing with Confidence Sequences

Fangyuan Lin; Noah Krever; Jakub Černý; Lily Xu

stat.MEOct 23, 2026

Not All Mislabels Are Equal: Efficient Task-Aware Auditing with Confidence Sequences

Authors: Fangyuan Lin, Noah Krever, Jakub Černý, Lily Xu

Organizations: Columbia University

Abstract

We study efficient, adaptive auditing of categorical labels in a fixed dataset, motivated by biodiversity-credit programs in which expert verification of species records is costly and downstream scores (e.g., payment) are more sensitive to errors on certain labels than on others. Our proposed ATLAS framework couples anytime-valid inference with a task-aware adaptive auditing policy. Representing label corrections through a confusion matrix, we prioritize which data points to inspect next based on both label uncertainty and the influence of potential label corrections on the downstream score function. For linear scores such as the mislabel rate, our priority-aware approach certifies the overall label error rate to $\pm 2$ percentage points with 24% and 11% fewer audits than random sampling on biodiversity data from Kenya and a widely used CIFAR-10N benchmark, respectively. For nonlinear scores such as the Hill-Shannon diversity, we exploit a linear-envelope representation that reduces inference to a family of linear-score audits; priority-aware sampling reaches the target precision with 36% fewer audits. When distribution-free guarantees are prohibitively costly, we develop a model-based Bayesian alternative that trades assumption-free validity for substantially fewer audits. Our biodiversity case study highlights a gap between statistical validity and practical feasibility: generic methods such as Serfling's bound and existing confidence-sequence procedures are rigorous but can require prohibitively many expert reviews in practice. Together, these results show task-aware auditing can significantly reduce the number of expert audits needed while providing finite-sample, anytime-valid guarantees.

Figures & tables

Figure 1: Our ATLAS framework for Anytime-valid Task-aware Label Auditing and Sampling. (A) Each step uses past audits to predict the unverified labels and the downstream score. We select a stratum

G_{t}

with probability

\pi_{G_{t},t}

, then an expert audit

V_{t}

corrects the predicted score through inverse-probability weighting to produce an unbiased score observation

Z_{t}

. (B) E-processes accumulate evidence against each candidate score value

m

, reject values with sufficient evidence, and use remaining values to form a confidence sequence

I_{t}

, stopping once the width falls below a tolerance

\tau

. (C) Our priority-aware sampling strategy directs reviews toward large strata with high predicted score uncertainty. We compare against random sampling as a baseline, but note that different sampling strategies only change the efficacy, not the validity of the confidence sequences.

			# audits to $\pm 2$ percentage points
Method	Sampling strategy	Guarantee	Kenyan biodiversity	CIFAR-10N
ATLAS-PAS (ours)	priority-aware	finite-sample, anytime	656	768
ATLAS-SRS	random	finite-sample, anytime	864	862
Wald	random	asymptotic, fixed $n$	1,481	1,434
PPR	random	finite-sample, anytime	4,118	3,973
Serfling	random	finite-sample, fixed $n$	4,154	4,332

Table 1: Audits required to certify the mislabel rate to a half-width of 2 percentage points at 95.5% nominal confidence. The Kenyan biodiversity dataset has 33,403 total data points and a true mislabel rate of 17.97%. CIFAR-10N has 50,000 data points with 17.23% mislabels. We report median stopping times over 20 audit paths.

Panel of Figure 2 — Figure 2: Audits on the Kenyan biodiversity dataset. (Left) Submitted-to-verified confusion matrix. Diagonal entries are correct labels, off-diagonal entries are mislabels. Color indicates the number of records on a log scale. (Right) Margin of error (half-width of the 95.5% mislabel-rate confidence sequence) as the number of audits increases, showing faster contraction under our ATLAS-PAS approach than four baselines in estimating uncertainty around the true mislabel rate. Curves show medians over 20 audit paths with the 25th–75th percentiles. Dots mark the audits required to reach a half-width of two percentage points. The corresponding CIFAR-10N dataset ( fig. 4 ) exhibits the same relative performances, and numerical results for both settings are reported in table 1 .

Figure 3: Anytime-valid certification of nonlinear scores under ATLAS-PAS and ATLAS-SRS. Relative margin of error is the half-width of the interval of the score estimate, expressed as a percentage of the midpoint value. (Left) Pooled diversity

P_{2}

on the Kenyan biodiversity dataset. (Middle) Worst-three precision on CIFAR-10N. (Right) Worst-three taxonomic risk on CIFAR-10N. Curves show median relative confidence-sequence half-widths. Shaded regions show interquartile ranges over 20 paired audit paths for Kenya and 10 for CIFAR-10N.

Sampling strategy	Mean	Median	Empirical coverage at stopping
	# audits to 5% relative accuracy
Priority-aware (Bayesian + PAS)	248	250	96%
Random (Bayesian + SRS)	493	500	96%

Table 2: On the Kenya biodiversity data, the number of audits required by the approximate Bayesian procedure to estimate

P_{2}

to 5% relative accuracy at 95.5% nominal credibility under the model. Results are over 100 audit paths per sampling strategy; all paths reached the target within 1,000 audits. Coverage is the fraction of audit paths whose interval contains the true

P_{2}

at stopping.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
Data and labels ( Section 2 )
$N$	Number of records, indexed by $i\in[N]$ .
$\mathcal{L}=\{1,\ldots,L\}$ , $\mathcal{R}\subseteq\mathcal{L}$	Full label vocabulary and subset of submitted labels; $R=\|\mathcal{R}\|$ .
$y_{i}\in\mathcal{R},\ v_{i}\in\mathcal{L}$	Submitted label $y_{i}$ (known) and expert-verified label $v_{i}$ (unknown until audit) of record $i$ .
$\mathbf{C^{\star}},\ \mathbf{C}$	True confusion matrix and a candidate confusion matrix. Their entries are $C^{\star}_{rs}=\#\{i:y_{i}=r,\ v_{i}=s\}$ .
$N_{r}$	Number of records submitted with label $r$ : $N_{r}=\sum_{s}C^{\star}_{rs}$ .

Appendix

Table 3: Core notation used in the main text. Symbols used exclusively in the appendix are defined where they are first introduced.

\widehat{\mu}_{g,t}=\sum_{s}q_{g,t}(s)D_{r(g),s},\qquad\widehat{\sigma}_{g,t}^{2}=\sum_{s}q_{g,t}(s)\bigl(D_{r(g),s}-\widehat{\mu}_{g,t}\bigr)^{2}.

Appendix

Algorithm 1 ATLAS Priority-Aware Sampling (PAS) for a linear score

\mathbf{\widehat{p}_{t-1}}=\frac{1}{N}\left[\mathbf{O}_{t-1}+\sum_{g}M_{g,t}\mathbf{q}_{g,t}\right],\qquad\mathbf{O}_{t-1}=\bigl(O_{t-1,s}\bigr)_{s\in\mathcal{L}}.

Appendix

Algorithm 2 ATLAS Distribution-free audit of entropy

Setting	Kenya Dataset	CIFAR-10N
Population size	$33{,}403$	$50{,}000$
Audit strata	46	40
Audit paths per policy	20	20
Maximum audits	$5{,}000$	$5{,}000$
Stored interval spacing	25	25
Target half-width	$0.02$	$0.02$

Appendix

Table 4: Frozen settings for the label-error-rate experiments. The prior column gives the prior probability that a submitted label is correct. The SRS weight is

\varepsilon

in Equation equation 7 .

Setting	Value
Audit strata	300
Paired paths	20
Seeds	$95001,\ldots,95020$
Maximum audits	$3{,}000$
Endpoint update spacing	25
Reported checkpoint spacing	100

Appendix

Table 5: Frozen settings for the Kenyan biodiversity data distribution-free diversity experiment.

Setting	Value
Audit strata	300
Audit paths per policy	100
Seeds	$8000,\ldots,8099$
Maximum audits	1,000
Evaluation schedule	$100,125,\ldots,1000$
Posterior draws per evaluation	400

Appendix

Table 6: Frozen settings for the Bayesian diversity experiment.

Figure 4: Audits on CIFAR-10N. (Left) Submitted-to-reference confusion matrix. Diagonal entries indicate agreement with the reference labels, while off-diagonal entries indicate label disagreements. Cell annotations give record counts, and color dsplays them on a log scale. (Right) Margin of error (half-width of the 95.5% mislabel-rate confidence sequence) as the number of audits increases. Methods and plotting conventions match fig. 2 ; dots mark the audits required to reach a half-width of two percentage points. The two settings exhibit similar contraction patterns and relative method performance. Numerical stopping times for both are reported in table 1 .

Setting	Value
Submitted rows	10
Tail size	3
Fixed three-row subsets	120
Scores	worst-three precision; worst-three taxonomic risk
Paired confirmation paths	10
Confirmation seeds	$2026100300,\ldots,2026100309$

Appendix

Table 7: Frozen settings for the CIFAR-10N worst-three experiments.

Setting	Value
Confirmation rows	20
Score-variable rows	4
Records per row	250
Population size	$5{,}000$
Confirmation paths	100
Confirmation seeds	$2026101000,\ldots,2026101099$

Appendix

Table 8: Frozen synthetic-experiment settings.

Figure 5: Controlled synthetic experiment isolating the benefit of priority-aware sampling. (a) Submitted-to-verified confusion matrix; asterisks identify the four rows whose possible verified labels have different score contributions. (b) Median confidence-sequence width under PAS and SRS, with interquartile ranges. (c) Terminal PAS width reduction as the total number of rows $R$ increases while the number of score-variable rows remains fixed at $k=4$ . The dotted curve shows the idealized $1-\sqrt{k/R}$ reference: SRS allocates only a fraction $k/R$ of its audits to the score-variable rows, whereas PAS concentrates on them, and confidence-sequence width scales approximately with the inverse square root of the informative audit count.

Algorithmic Auditing

Algorithmic auditing evaluates whether automated systems are fair, reliable, robust, compliant, and accountable in their intended settings.

See all 143 papers

Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design
Jul 23, 2026Martin Anthony, Kaveh Salehzadeh NobariAlgorithmic Auditing
Data Science Institute, London School of Economics and Political Science · Department of Mathematics, London School of Economics and Political Science · The Inclusion Initiative, London School of Economics and Political Science
The geometry of AI validation: From structural blindness to reusable audits
Aug 21, 2026Ricardo FitasAutomated Evaluation Algorithmic Auditing
Technical University of Darmstadt, 64289 Darmstadt, Germany
Active Learning for Biodiversity Monitoring: From Label Efficiency to Reliable Ecological Inference
Sep 23, 2026Ben McEwen, Shiqi Zhang, Dan StowellActive Learning Biodiversity Monitoring
Institute for Biodiversity and Ecosystem Dynamics (IBED), University of Amsterdam, Amsterdam, the Netherlands · Faculty of Information Technology and Communication Sciences, Tampere University, Finland · Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands +1

Jul 23, 2026J/K move · Enter open · S save

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

Martin Anthony, Kaveh Salehzadeh Nobari

Data Science Institute, London School of Economics and Political Science · Department of Mathematics, London School of Economics and Political Science · The Inclusion Initiative, London School of Economics and Political Science

Algorithmic Auditing

Open paper AskPDF arXiv

An initial high-recall stage in an empirical pipeline decides which items pass to later review, labelling, or modelling, and relevant items it misses are lost to every subsequent stage. We study how many audit labels are needed to certify, with finite-sample validity, that this missed relevant mass is small, and our main results characterise the label complexity of this problem. We first show that no procedure using only labels from inside the candidate set can certify any non-trivial bound on the missed mass: the audit must sample the excluded pool, the only region where unrecovered relevant items can lie. We then prove a matching finite-corpus lower bound. Any valid audit that certifies fewer than

m

missed relevant items with high probability when none are present, even if adaptive and permitted to label the entire included pool, must inspect on the order of

N_0/m

excluded-pool labels. Excluded-pool auditing is therefore minimax rate-optimal, not merely convenient, for missed-mass certification in the zero-miss regime. Building on this characterisation, we develop an exact finite-sample toolkit, using binomial and hypergeometric inversion rather than asymptotic approximation, that certifies missed mass, converts it to recall through a two-pool design, certifies pre-specified families of nested candidate generators simultaneously, and produces stress-test certificates against declared perturbation mechanisms. These certificates can be paired with observable review burden to select the least burdensome pre-specified candidate generator meeting a missed-mass target. Every guarantee holds under one discipline: the candidate generator, or the pre-specified family from which it is selected, and the audit rule are fixed before the certification labels are examined.

Abstract

Algorithmic Auditing

Explore similar work

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

The geometry of AI validation: From structural blindness to reusable audits

Active Learning for Biodiversity Monitoring: From Label Efficiency to Reliable Ecological Inference