Introduction
Large labeled datasets are routinely used in consequential inference tasks, from model evaluation to scientific analysis. However, the labels in these datasets are not always correct, with annotation errors documented in settings ranging from healthcare ([38 ] (Rädsch et al. 2023)) to remote sensing ([27 ] ). Even widely used machine-learning benchmarks contain nontrivial label noise, with one study estimating an average error rate of 3.3% ([26 ] ). Especially in consequential settings, practitioners may want rigorous uncertainty quantification for downstream quantities computed from the true labels, but doing so requires verifying at least some of the labels. When expert verification of an entire dataset is impractical, two natural questions arise: How many data points must be audited to certify a downstream quantity with a desired level of confidence? Which records should be audited to reduce that uncertainty as efficiently as possible?
When audits are costly, confidence sequences are useful as they provide confidence intervals that are simultaneously valid over all sample sizes (i.e., anytime-valid), allowing the auditor to inspect data sequentially and stop adaptively without invalidating the coverage guarantee. Recent work develops such guarantees for sampling without replacement ([43 , 32 ] ) to certify finite-population quantities, e.g., population mean, but these methods were not designed for the precision and affordability that audits need in practice: on our data of 33,403 labels, the prior–posterior-ratio confidence sequence of [43 ] needs a median of 4,021 audits to certify the mislabel rate to ± 2 \pm2 ± 2 percentage points at 95.5% confidence, against 603 for our method, over 100 paired paths. Adaptive sampling without replacement, importance weighting, and control variates already support efficient weighted-average audits [37 ] . Our question is how to make these tools effective for categorical corrections and their downstream scores. We use Bayesian predictions of label corrections to decide where expert review would tell us the most about the downstream score. This rule approximates the variance-minimizing audit allocation, and our confidence sequence remains valid whenever the auditor stops, even if the predictions are inaccurate. We also extend the audit to structured nonlinear scores. For example, we use a linear-envelope representation of entropy to certify the Hill–Shannon biodiversity score. Empirically, our method typically reached the target precision with substantially fewer audits than competing methods (Table 1 and Figure 3 ).
Table 1. Median audits to reach an interval half-width of 2 percentage points at 95.5% nominal confidence over 100 paired paths. Counts are rounded to the nearest audit. A budget of 5,000 audits was used for the anytime-valid methods. # audits to ± 2 \pm2 ± 2 percentage points. Median [25th, 75th percentiles]. Bold: smallest median among anytime-valid methods. † Oracle population variance. ‡ Analytic fixed-n n n count using variance bound 1 / 4 1/4 1/4 .
Figure 3. Anytime-valid certification of nonlinear scores on four datasets: (A) pooled diversity P 2 P_2 P 2 on the Kenya biodiversity dataset, (B) worst-three precision on CIFAR-10N, and (C,D) F1 score on ReImageNet and CleanCoNLL. Curves show median interval half-widths over 100 paired audit paths; shaded regions show interquartile ranges. Panels (A,B) express half-width as a percentage of the interval midpoint; panels (C,D) use percentage points. We compare ATLAS-PAS, ATLAS-SRS, PPR with projection, and adapted Manole–Ramdas stitching. Dashed horizontal lines indicate the precision targets. Full results, including for an uncertainty-only policy ablation, are in section D.5.
Motivation: Auditing for biodiversity credits. Biodiversity credits are purchased by companies and investors to fund nature conservation and restoration worldwide, compensating individual landowners for measurable improvements in ecosystem health [47 ] . The market is estimated to grow from US$8M annually to $69B by 2050 [46 ] , but credits are burdened by high overhead costs and concerns about trust and verification [1 ] . Each project may generate tens or hundreds of thousands of sensor records documenting wildlife presence and abundance, making full expert audit impractical. Automated species classifiers reduce labeling cost but can have substantial error: one widely used classifier had an 18.2% error rate on an out-of-sample dataset [39 ] . Because credit payments depend on these metrics, label errors have direct financial consequences, creating a need for efficient expert auditing. In our biodiversity credit data from Kenya, the submitted labels imply a pooled Hill–Shannon diversity of 8.16, compared with only 4.94 after expert validation—a 65% inflation in the downstream score. An aggregate mislabel rate (e.g., “13% of labels are incorrect”) is insufficient because the direction of an error determines its downstream consequence. Incorrectly labeling cattle as lion, for example, may falsely introduce a rare species and substantially inflate estimated richness and taxonomic diversity (and therefore payment), whereas confusing two common, closely related species may have little effect. An effective audit should therefore account not only for where errors are likely, but also for how potential corrections affect the downstream scoring function.
The same structure arises in myriad settings. In model evaluation, for example, noisy benchmark labels impact downstream quantities such as F 1 F_1 F 1 score, balanced accuracy, or model rankings [26 ] , each of which may depend nonlinearly on the corrected labels. In epidemiology, label corrections may change prevalence estimates [12 ] , while in content moderation they may alter policy-compliance rates.
To address these challenges, we make the following contributions:
A general framework for efficient label auditing (fig. 1). We introduce an anytime-valid task-aware label auditing and sampling framework (ATLAS) for fixed categorical datasets. It uses Bayesian predictions of label corrections to guide expert review and e-processes to certify the downstream score. In our experiments, ATLAS typically reached the target precision with substantially fewer audits than competing anytime-valid methods.
Efficient anytime-valid inference for structured nonlinear scores. For nonlinear scores such as Hill–Shannon diversity, we exploit linear-envelope representations to build score-specific confidence sequences from our linear auditing framework. The resulting confidence sequences retain anytime-valid guarantees while supporting efficient adaptive auditing.
A model-based Bayesian alternative using the same task-aware sampling strategy. When distribution-free guarantees require an impractically large number of audits, we retain the same task-aware strategy but use a Bayesian model of the confusion matrix for uncertainty quantification, trading assumption-free validity for greater statistical efficiency.
Problem Formulation
A provided dataset contains N N N records. Record i ∈ [ N ] i \in[N] i ∈ [ N ] has a submitted label y i y_i y i (known) and verified label v i v_i v i (unknown until verification). Let L : = { 1 , … , L } \mathcal{L} := \{1,\ldots,L\} L := { 1 , … , L } be the full normalized label vocabulary, and let R : = { y i : i ∈ [ N ] } ⊆ L \mathcal{R} := \{y_i : i \in[N]\} \subseteq\mathcal{L} R := { y i : i ∈ [ N ]} ⊆ L be the set of submitted labels with R : = ∣ R ∣ R := |\mathcal{R}| R := ∣ R ∣ elements. Thus y i ∈ R y_i \in\mathcal{R} y i ∈ R and v i ∈ L v_i \in\mathcal{L} v i ∈ L .
Confusion matrix. A scalar mislabel rate records how often y i ≠ v i y_i \ne v_i y i = v i across the entire dataset; it does not capture error rates across different classes. We therefore track a full confusion matrix , which counts records for each pair of submitted and verified labels (Figure 2 ). The diagonal represents how many records are correctly labeled. The unknown finite-population confusion matrix is C ⋆ ∈ Z ≥ 0 R × L C^\star\in\mathbb{Z}_{\ge0}^{R \times L} C ⋆ ∈ Z ≥ 0 R × L , where each entry C r s ⋆ : = # { i : y i = r , v i = s } C^\star_{rs} := \#\{i : y_i = r, v_i = s\} C r s ⋆ := # { i : y i = r , v i = s } indicates the number of data points submitted with row r r r and verified with column s s s . Row r r r contains records submitted as label r r r , while column s s s contains records verified as label s s s . The row sums N r : = ∑ s ∈ L C r s ⋆ = # { i : y i = r } N_r := \sum_{s \in\mathcal{L}} C^\star_{rs} = \#\{i : y_i = r\} N r := ∑ s ∈ L C r s ⋆ = # { i : y i = r } are known before auditing.
Figure 2. Audits on the Kenya biodiversity dataset. (Left) Submitted-to-verified confusion matrix (input data). Diagonal entries are correct labels, off-diagonal entries are mislabels. Color indicates counts on a log scale. (Right) 95.5% confidence sequence half-width as the number of audits increases. Curves show medians over 100 audit paths with the 25th–75th percentiles. Annotated dots mark the audits to reach a two percentage point precision. Corresponding results for CIFAR-10N (section D.2.2), ReImageNet (section D.3.2), and CleanCoNLL (section D.4.2) are reported in table 1.
Score functions. We use score function to denote any downstream quantity computed from the corrected labels. Formally, a score function maps the submitted-to-verified confusion matrix C \mathbf{C} C to a scalar outcome of interest, such as an error rate, model-evaluation metric, or biodiversity score. Importantly, we are interested in finite-population inference. When auditing labels we are only interested in the score for the particular submitted dataset, unlike in conventional superpopulation inference where we seek to estimate a parameter of an underlying distribution from which the data are assumed to be i.i.d. draws. For the biodiversity credits setting, the relevant score function is challenging as it is nonlinear and nonsmooth; details in appendix § 13 .
Strata: splitting rows by metadata. Records often carry metadata, such as the source, location, device, or time period, that may be associated with different correction patterns. Splitting each row by these metadata creates smaller groups of records which we call strata . We write g = ( r , a ) g = (r, a) g = ( r , a ) for the stratum containing records with submitted label r r r and metadata value a a a . In our biodiversity application, a a a refers to a camera station, where corrections are strongly clustered. Then r ( g ) r(g) r ( g ) is the submitted label shared by records in stratum g g g . The size of each stratum is known before any audit, and each row is the union of its strata. When no metadata is used, each row is its own stratum. Stratification is useful when correction behavior varies across metadata-defined subgroups, because it allows the audit to focus more precisely on where uncertainty remains.
Confidence Sequences for Auditing Linear Score Functions
We first explore how to turn expert audits into a confidence sequence , illustrated in Figure 1 b. Confidence sequences provide uncertainty intervals that are valid after every audit, allowing the auditor to monitor uncertainty and stop as soon as desired precision is reached. In this section, we instantiate the auditing workflow in Figure 1 for scores that are linear in the confusion matrix.
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 G_t G t with probability π G t , t \pi_{G_t,t} π G t , t , then an expert audit V t V_t V t corrects the predicted score through inverse-probability weighting to produce an unbiased score observation Z t Z_t Z t . (B) E-processes accumulate evidence against each candidate score value m m m , reject values with sufficient evidence, and use remaining values to form a confidence sequence I t I_t 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.
Let D ∈ R R × L \mathbf{D} \in\mathbb{R}^{R \times L} D ∈ R R × L be a deterministic contribution matrix , where the ( r , s ) (r,s) ( r , s ) element D r s ∈ [ 0 , 1 ] D_{rs} \in[0,1] D r s ∈ [ 0 , 1 ] is the contribution to the score from a data point submitted as label r r r and verified as label s s s and is known in advance. For example, when the score function is the mislabel rate, D \mathbf{D} D is a binary matrix with D r , s = 1 { r ≠ s } D_{r,s} = \mathbb{1}\{r \ne s\} D r , s = 1 { r = s } . We denote the r r r -th row of this matrix as d r T \mathbf{d}_r^{\mathsf{T}} d r T .
A score is linear if it can be expressed as θ ⋆ = 1 N ∑ i = 1 N D y i , v i = 1 N ∑ r ∈ R ∑ s ∈ L C r s D r s \theta^\star= \frac{1}{N}\sum_{i=1}^{N}D_{y_i,v_i} = \frac{1}{N}\sum_{r\in\mathcal{R}}\sum_{s\in\mathcal{L}}C_{rs}D_{rs} θ ⋆ = N 1 ∑ i = 1 N D y i , v i = N 1 ∑ r ∈ R ∑ s ∈ L C r s D r s . With linear scores, each record contributes a fixed, known amount determined by its submitted and verified labels. If all verified labels were known, the true score θ ⋆ \theta^\star θ ⋆ could be computed exactly. During the audit, however, only a subset of the data have been reviewed.
A starting point: Serfling’s inequality. For a fixed number of labels sampled uniformly without replacement, Serfling’s inequality Serfling, [35 ] sharpens the standard Hoeffding bound and gives a finite-sample, distribution-free confidence interval for the mislabel rate. Even so, on the Kenyan dataset, certifying the mislabel rate to ± 2 \pm2 ± 2 percentage points at 95.5% confidence requires 4,154 reviews, about one in eight records (Table 1 and Figure 2 ). A Wald interval reaches the same precision in 1,481 reviews, but relies on an asymptotic approximation and, in this comparison, the true population variance. We therefore seek greater efficiency while retaining rigorous finite-sample validity.
Constructing an unbiased audit observation. We first construct a quantity Z t Z_t Z t whose conditional mean, given everything observed before audit t t t , is the downstream score θ ⋆ \theta^\star θ ⋆ :
E [ Z t ∣ F t − 1 ] = θ ⋆ for every labeling (1) \mathbb{E}[Z_t \mid\mathcal{F}_{t-1}] = \theta^\star\qquad\text{for every labeling} \tag*{(1)} E [ Z t ∣ F t − 1 ] = θ ⋆ for every labeling (1)
where F t − 1 \mathcal{F}_{t-1} F t − 1 denotes the audit history available before audit t t t . Let A t − 1 A_{t-1} A t − 1 denote the records audited so far. For each stratum g g g , let M g , t = ∣ ( g ∖ A t − 1 ) ∣ M_{g,t} = |(g \setminus A_{t-1})| M g , t = ∣ ( g ∖ A t − 1 ) ∣ be the number of unaudited records remaining. Their score contributions have mean μ g , t = 1 M g , t ∑ i ∈ g ∖ A t − 1 D y i , v i \mu_{g,t} = \frac{1}{M_{g,t}}\sum_{i\in g\setminus A_{t-1}}D_{y_i,v_i} μ g , t = M g , t 1 ∑ i ∈ g ∖ A t − 1 D y i , v i and variance σ g , t 2 = 1 M g , t ∑ i ∈ g ∖ A t − 1 ( D y i , v i − μ g , t ) 2 \sigma^2_{g,t} = \frac{1}{M_{g,t}}\sum_{i\in g\setminus A_{t-1}}(D_{y_i,v_i}-\mu_{g,t})^2 σ g , t 2 = M g , t 1 ∑ i ∈ g ∖ A t − 1 ( D y i , v i − μ g , t ) 2 . The linear score can be split into:
N θ ⋆ = ∑ i ∈ A t − 1 D y i , v i + ∑ g M g , t μ g , t . (2) N\theta^\star= \sum_{i\in A_{t-1}}D_{y_i,v_i} + \sum_g M_{g,t}\mu_{g,t}. \tag*{(2)} N θ ⋆ = i ∈ A t − 1 ∑ D y i , v i + g ∑ M g , t μ g , t . (2)
After t − 1 t-1 t − 1 audits, the first sum is known and the second must be learned (or estimated) by the auditor. Before audit t t t , using only F t − 1 \mathcal{F}_{t-1} F t − 1 , the auditor fixes sampling probabilities { π g , t } g \{\pi_{g,t}\}_g { π g , t } g (where ∑ g π g , t = 1 \sum_g\pi_{g,t}=1 ∑ g π g , t = 1 ) and a predicted verified-label distribution q g , t ∈ Δ L − 1 \mathbf{q}_{g,t}\in\Delta^{L-1} q g , t ∈ Δ L − 1 for each nonempty stratum g g g . Using these predictions, we predict the downstream score θ ⋆ \theta^\star θ ⋆ via the estimator:
θ ^ t − 1 = 1 N ( ∑ i ∈ A t − 1 D y i , v i + ∑ g M g , t d r ( g ) T q g , t ) . (3) \widehat{\theta}_{t-1} = \frac{1}{N}\left(\sum_{i\in A_{t-1}}D_{y_i,v_i}+\sum_g M_{g,t}\,\mathbf{d}_{r(g)}^{\mathsf{T}}\mathbf{q}_{g,t}\right). \tag*{(3)} θ t − 1 = N 1 i ∈ A t − 1 ∑ D y i , v i + g ∑ M g , t d r ( g ) T q g , t . (3)
The first term uses the verified contributions of audited records, while the second predicts the contributions of the remaining records. The auditor then draws a stratum G t G_t G t according to Pr ( G t = g ∣ F t − 1 ) = π g , t \Pr(G_t=g\mid\mathcal{F}_{t-1})=\pi_{g,t} Pr ( G t = g ∣ F t − 1 ) = π g , t , selects a record J t J_t J t uniformly from G t ∖ A t − 1 G_t\setminus A_{t-1} G t ∖ A t − 1 , and reveals its verified label V t = v J t V_t=v_{J_t} V t = v J t . Thus an unaudited record in stratum g g g is selected with probability π g , t / M g , t \pi_{g,t}/M_{g,t} π g , t / M g , t .
Because strata may be sampled nonuniformly, simply replacing the predicted contribution with the newly verified one would generally introduce bias. To update this prediction with the next audit, we therefore use an inverse-probability-weighted residual correction Horvitz & Thompson, [14 ] :
Z t = θ ^ t − 1 + M G t , t N π G t , t ( D r ( G t ) , V t − d r ( G t ) T q G t , t ) . (4) Z_t = \widehat{\theta}_{t-1} + \frac{M_{G_t,t}}{N\pi_{G_t,t}}\left(D_{r(G_t),V_t}-\mathbf{d}_{r(G_t)}^{\mathsf{T}}\mathbf{q}_{G_t,t}\right). \tag*{(4)} Z t = θ t − 1 + N π G t , t M G t , t ( D r ( G t ) , V t − d r ( G t ) T q G t , t ) . (4)
The residual compares the newly verified contribution D r ( G t ) , V t D_{r(G_t),V_t} D r ( G t ) , V t with its prediction d r ( G t ) T q G t , t \mathbf{d}_{r(G_t)}^{\mathsf{T}}\mathbf{q}_{G_t,t} d r ( G t ) T q G t , t , while the inverse-probability weight M G t , t N π G t , t \frac{M_{G_t,t}}{N\pi_{G_t,t}} N π G t , t M G t , t corrects for nonuniform sampling. Consequently, Z t Z_t Z t is an unbiased estimate for θ ⋆ \theta^\star θ ⋆ for any predictable predictions and sampling probabilities, as formalized in theorem 1. The prediction term acts as a control variate, analogous to Särndal et al. [33 ] , and improves efficiency while preserving validity.
Lemma 1 (One audit, one unbiased observation). If q ⋅ , t \mathbf{q}_{\cdot,t} q ⋅ , t and π ⋅ , t \boldsymbol{\pi}_{\cdot,t} π ⋅ , t are predictable and π g , t > 0 \pi_{g,t}>0 π g , t > 0 whenever M g , t > 0 M_{g,t}>0 M g , t > 0 , then E [ Z t ∣ F t − 1 ] = θ ⋆ \mathbb{E}[Z_t\mid\mathcal{F}_{t-1}]=\theta^\star E [ Z t ∣ F t − 1 ] = θ ⋆ for every labeling. Define the stratum-level prediction error as b g , t = μ g , t − d r ( g ) T q g , t b_{g,t}=\mu_{g,t}-\mathbf{d}_{r(g)}^{\mathsf{T}}\mathbf{q}_{g,t} b g , t = μ g , t − d r ( g ) T q g , t , then the conditional variance is:
Var ( Z t ∣ F t − 1 ) = 1 N 2 [ ∑ g M g , t 2 π g , t ( σ g , t 2 + b g , t 2 ) − ( ∑ g M g , t b g , t ) 2 ] . (5) \operatorname{Var}(Z_t\mid\mathcal{F}_{t-1})=\frac{1}{N^2}\left[\sum_g\frac{M_{g,t}^2}{\pi_{g,t}}\left(\sigma_{g,t}^2+b_{g,t}^2\right)-\left(\sum_g M_{g,t}b_{g,t}\right)^2\right]. \tag*{(5)} Var ( Z t ∣ F t − 1 ) = N 2 1 g ∑ π g , t M g , t 2 ( σ g , t 2 + b g , t 2 ) − ( g ∑ M g , t b g , t ) 2 . (5)
Better predictions reduce variance (hence improving efficiency), while unbiasedness holds regardless of prediction quality. In experiments, q g , t \mathbf{q}_{g,t} q g , t is the posterior mean under a hierarchical Dirichlet model ([10 ] ), updated using only the audits observed before time t t t .
E-processes. For each candidate score value m m m , we construct two e-processes that accumulate evidence against the null hypothesis θ ⋆ = m \theta^\star=m θ ⋆ = m . The confidence sequence is then obtained by retaining candidate values for which neither e-process has crossed the rejection threshold. Ville’s inequality gives simultaneous coverage (i.e., anytime validity) over all audit times.
Following Waudby-Smith & Ramdas [44 ] , let λ i ± ( m ) ≥ 0 \lambda_i^\pm(m)\geq0 λ i ± ( m ) ≥ 0 be predictable betting stakes. Under this null hypothesis, theorem 1 implies that each factor below has conditional mean one:
E t + ( m ) = ∏ i ≤ t { 1 + λ i + ( m ) ( Z i − m ) } , E t − ( m ) = ∏ i ≤ t { 1 − λ i − ( m ) ( Z i − m ) } . (6) E_t^+(m)=\prod_{i\leq t}\left\{1+\lambda_i^+(m)(Z_i-m)\right\},\qquad E_t^-(m)=\prod_{i\leq t}\left\{1-\lambda_i^-(m)(Z_i-m)\right\}. \tag*{(6)} E t + ( m ) = i ≤ t ∏ { 1 + λ i + ( m ) ( Z i − m ) } , E t − ( m ) = i ≤ t ∏ { 1 − λ i − ( m ) ( Z i − m ) } . (6)
Thus at the true value m = θ ⋆ m=\theta^\star m = θ ⋆ , both processes are nonnegative martingales with initial value one.
The only requirement on the stakes λ ± \lambda^\pm λ ± is that they are predictable and keep every factor nonnegative, for every possible revealed label. This is always achievable because D r s ∈ [ 0 , 1 ] D_{rs}\in[0,1] D r s ∈ [ 0 , 1 ] , so the range of Z t Z_t Z t is known before each audit, and such stakes can be chosen. Section F.1 gives this range and the stakes used in our experiments.
Theorem 2 (Confidence sequence for a linear score). Let I t = { m : E s + ( m ) < 2 / α , E s − ( m ) < 2 / α for all s ≤ t } I_t=\{m:E_s^+(m)<2/\alpha,E_s^-(m)<2/\alpha\text{ for all }s\leq t\} I t = { m : E s + ( m ) < 2/ α , E s − ( m ) < 2/ α for all s ≤ t } . Then Pr { θ ⋆ ∈ I t ∀ t } ≥ 1 − α \Pr\{\theta^\star\in I_t\ \forall t\}\geq1-\alpha Pr { θ ⋆ ∈ I t ∀ t } ≥ 1 − α for every labeling.
Proof sketch. Applying Ville’s inequality (theorem 4) to the two martingales at m = θ ⋆ m=\theta^\star m = θ ⋆ , each crosses 2 / α 2/\alpha 2/ α with probability at most α / 2 \alpha/2 α /2 , uniformly over time. A union bound over the two tails gives total error at most α \alpha α . Details in section F.1.
The same e-process construction extends to ratios of linear scores: the recall ρ ⋆ = C s s ⋆ / ∑ r C r s ⋆ \rho^\star=C^\star_{ss}/\sum_r C^\star_{rs} ρ ⋆ = C ss ⋆ / ∑ r C r s ⋆ of species s s s and the F1 score are handled the same way in appendix H.
Priority-Aware Sampling
The confidence sequence in section 3 determines when an audit may stop. We now consider what to audit next. Because different label corrections can vary greatly in their impact on the downstream score, we aim to prioritize expert audits toward strata whose unresolved labels contribute most to uncertainty in that score, a process illustrated in fig. 1a.
Under exact predictions (b g , t = 0 b_{g,t}=0 b g , t = 0 and μ g , t = d r ( g ) T q g , t \mu_{g,t}=\mathbf{d}_{r(g)}^{\mathsf{T}}\mathbf{q}_{g,t} μ g , t = d r ( g ) T q g , t ), eq. (5) reduces to Var ( Z t ∣ F t − 1 ) = 1 N 2 ∑ g M g , t 2 σ g , t 2 π g , t \operatorname{Var}(Z_t\mid\mathcal{F}_{t-1})=\frac{1}{N^2}\sum_g\frac{M_{g,t}^2\sigma_{g,t}^2}{\pi_{g,t}} Var ( Z t ∣ F t − 1 ) = N 2 1 ∑ g π g , t M g , t 2 σ g , t 2 . This is minimized by π g , t ∝ M g , t σ g , t \pi_{g,t}\propto M_{g,t}\sigma_{g,t} π g , t ∝ M g , t σ g , t , suggesting we prioritize strata in proportion to their remaining (unaudited) size times uncertainty in their score contributions.
Proposition 3 (Priority-aware allocation). If the predictions are exact, equation 5 is minimized subject to floors π g , t ≥ ℓ g , t > 0 \pi_{g,t}\geq\ell_{g,t}>0 π g , t ≥ ℓ g , t > 0 by π g , t = max { ℓ g , t , M g , t σ g , t / ν } \pi_{g,t}=\max\{\ell_{g,t},M_{g,t}\sigma_{g,t}/\nu\} π g , t = max { ℓ g , t , M g , t σ g , t / ν } , where ν > 0 \nu>0 ν > 0 normalizes the probabilities. Without floors, the minimum is N − 2 ( ∑ g M g , t σ g , t ) 2 N^{-2}(\sum_g M_{g,t}\sigma_{g,t})^2 N − 2 ( ∑ g M g , t σ g , t ) 2 , the Neyman variance ([25 ] ).
In practice, we estimate the standard deviation σ g , t \sigma_{g,t} σ g , t from the predicted verified-label distribution q g , t \mathbf{q}_{g,t} q g , t . When the scoring function is the mislabel rate, each contribution is Bernoulli. If ϵ ^ g , t = d r ( g ) T q g , t = Pr ^ ( verified label ≠ r ( g ) ∣ F t − 1 ) \hat{\epsilon}_{g,t}=\mathbf{d}_{r(g)}^{\mathsf{T}}\mathbf{q}_{g,t}=\widehat{\Pr}(\text{verified label}\ne r(g)\mid\mathcal{F}_{t-1}) ϵ ^ g , t = d r ( g ) T q g , t = Pr ( verified label = r ( g ) ∣ F t − 1 ) is the predicted error rate in stratum g g g , then the estimated standard deviation is σ ^ g , t = ϵ ^ g , t ( 1 − ϵ ^ g , t ) \hat{\sigma}_{g,t}=\sqrt{\hat{\epsilon}_{g,t}(1-\hat{\epsilon}_{g,t})} σ ^ g , t = ϵ ^ g , t ( 1 − ϵ ^ g , t ) .
Then to ensure continued exploration, we mix the resulting priority allocation with sampling proportional to the number of remaining records in each stratum g g g :
π g , t = ε M g , t ∑ k M k , t + ( 1 − ε ) M g , t σ ^ g , t ∑ k M k , t σ ^ k , t . (7) \pi_{g,t}=\varepsilon\frac{M_{g,t}}{\sum_k M_{k,t}}+(1-\varepsilon)\frac{M_{g,t}\hat{\sigma}_{g,t}}{\sum_k M_{k,t}\hat{\sigma}_{k,t}}. \tag*{(7)} π g , t = ε ∑ k M k , t M g , t + ( 1 − ε ) ∑ k M k , t σ ^ k , t M g , t σ ^ g , t . (7)
The first term guarantees continued exploration of all remaining records, while the second approximates the variance-minimizing allocation of theorem 3. The end-to-end priority-aware sampling procedure is presented as algorithm 1 in appendix § 15 .
Experimental Results: Certifying the Mislabel Rate
Table 1 compares methods for certifying the overall mislabel rate using corrected records from the Kenya biodiversity, CIFAR-10N ([45 ] ), ReImageNet ([41 ] ), and CleanCoNLL ([31 ] ) datasets. ATLAS-PAS and ATLAS-SRS use the same confidence sequence from § 3 and theorem 2 and differ only in the selection of the next record. We also compare with Prop-MS and Prop-M + CV implementations of the risk-limiting financial audit (RLFA) methodology in [37 ] , using the authors’ code, 5 the prior–posterior-ratio (PPR) confidence sequence ([43 ] ), and fixed-sample Wald, Serfling, and Chebyshev references.
ATLAS-PAS reduces the median audit count relative to random sampling across all four datasets and achieves the lowest median among anytime-valid methods on three. On CleanCoNLL, the RLFA control-variate baseline has a lower median, but reaches the target precision on only three-quarters of paths within budget, compared with every path for ATLAS-PAS. Among the fixed-sample references, Serfling and Chebyshev baselines require more audits than ATLAS-PAS in every setting. On ReImageNet and CleanCoNLL, the Wald baseline reaches the target precision with fewer audits, but it is an asymptotic approximation and uses the true variance.
Figure 2 shows the confusion matrix of the Kenyan biodiversity dataset and the audit curves for ATLAS and each baseline, with a target precision of ± 2 \pm2 ± 2 percentage points for the mislabel rate at a nominal confidence level of 95.5%. For each linear score, appendix § 16 reports audit curves and stopping-time distributions. We describe the baselines in section D.7 and examine when priority-aware allocation saves the most audits through a controlled experiment (section D.6) and sensitivity analyses (section D.8).
Auditing Nonlinear Scores via Linear Envelopes
In practice, downstream scores are often nonlinear, so the linear construction of § 3 cannot be applied directly with a single fixed contribution matrix. For concave scores, we show they nevertheless admit an anytime-valid audit by exploiting their representation as envelopes of linear scores: a single predictable tangent direction yields a valid upper confidence bound, while the lower bound requires ruling out every plausible label composition, which we certify by convex optimization for Shannon entropy. We develop the linear envelope construction for Shannon entropy, yielding a confidence sequence for the nonlinear Hill–Shannon biodiversity score. The same envelope principle applies to worst-three precision and worst-three taxonomic risk on CIFAR-10N. More generally, one can bound a nonlinear score by taking its range over a confidence region for the confusion matrix. We include this projection approach as a baseline in Figure 3 . We can also use the structure of a score directly, as we do below for concave scores. For the F1 score on ReImageNet and CleanCoNLL, we use its representation as a ratio of linear scores (appendix § 20 ).
Concave scores are envelopes of linear scores.
Let p ⋆ ∈ Δ L − 1 \mathbf{p}^{\star} \in\Delta^{L-1} p ⋆ ∈ Δ L − 1 denote the true corrected label proportions, with p s ⋆ = 1 N ∑ r C r s r p_{s}^{\star} = \frac{1}{N} \sum_{r} C_{rs}^{r} p s ⋆ = N 1 ∑ r C r s r . Then define H : Δ L − 1 → R H : \Delta^{L-1} \to\mathbb{R} H : Δ L − 1 → R as a concave, differentiable (on its relative interior) score function of a label proportion p \mathbf{p} p . For any reference composition p ˉ ∈ Δ L − 1 \bar{\mathbf{p}} \in\Delta^{L-1} p ˉ ∈ Δ L − 1 , concavity implies that the tangent plane to H H H at p ˉ \bar{\mathbf{p}} p ˉ upper bounds H H H . Using ∑ s p s = 1 \sum_{s} p_{s} = 1 ∑ s p s = 1 , this tangent plane can be written as a linear score:
H ( p ) ≤ ∑ s ∈ L p s ψ s ( p ˉ ) , where ψ s ( p ˉ ) = H ( p ˉ ) + ∂ s H ( p ˉ ) − ∑ j p ˉ j ∂ j H ( p ˉ ) . (8) H(\mathbf{p}) \le\sum_{s \in\mathcal{L}} p_{s} \psi_{s}(\bar{\mathbf{p}}), \qquad\text{where } \psi_{s}(\bar{\mathbf{p}}) = H(\bar{\mathbf{p}}) + \partial_{s} H(\bar{\mathbf{p}}) - \sum_{j} \bar{p}_{j} \partial_{j} H(\bar{\mathbf{p}}). \tag*{(8)} H ( p ) ≤ s ∈ L ∑ p s ψ s ( p ˉ ) , where ψ s ( p ˉ ) = H ( p ˉ ) + ∂ s H ( p ˉ ) − j ∑ p ˉ j ∂ j H ( p ˉ ) . (8)
with equality at p ˉ = p \bar{\mathbf{p}} = \mathbf{p} p ˉ = p . Thus H ( p ) = inf p ˉ ∑ s p s ψ s ( p ˉ ) H(\mathbf{p}) = \inf_{\bar{\mathbf{p}}} \sum_{s} p_{s} \psi_{s}(\bar{\mathbf{p}}) H ( p ) = inf p ˉ ∑ s p s ψ s ( p ˉ ) is the infimum of these linear upper bounds over reference compositions p ˉ \bar{\mathbf{p}} p ˉ . So a record verified as s s s contributes the known amount ψ s ( p ˉ ) \psi_{s}(\bar{\mathbf{p}}) ψ s ( p ˉ ) to the linear score indexed by p ˉ \bar{\mathbf{p}} p ˉ . Specializing H H H to Shannon entropy, H ( p ) = − ∑ s ∈ L p s log p s H(\mathbf{p}) = - \sum_{s \in\mathcal{L}} p_{s} \log p_{s} H ( p ) = − ∑ s ∈ L p s log p s gives ψ s ( p ˉ ) = log ( 1 / p ˉ s ) \psi_{s}(\bar{\mathbf{p}}) = \log(1/\bar{p}_{s}) ψ s ( p ˉ ) = log ( 1/ p ˉ s ) , so the tangent plane is the cross-entropy CE ( p , p ˉ ) : = ∑ s p s log ( 1 / p ˉ s ) = H ( p ) + KL ( p ∥ p ˉ ) \operatorname{CE}(\mathbf{p}, \bar{\mathbf{p}}) := \sum_{s} p_{s} \log(1/\bar{p}_{s}) = H(\mathbf{p}) + \operatorname{KL}(\mathbf{p}\Vert\bar{\mathbf{p}}) CE ( p , p ˉ ) := ∑ s p s log ( 1/ p ˉ s ) = H ( p ) + KL ( p ∥ p ˉ ) . Equation 8 is therefore Gibbs’ inequality KL ≥ 0 \operatorname{KL} \ge0 KL ≥ 0 ([6 ] ).
Upper bound: one linear audit. Any predictable reference p ˉ \bar{\mathbf{p}} p ˉ defines a linear score that upper bounds H ( p ⋆ ) H(\mathbf{p}^{\star}) H ( p ⋆ ) ; its choice affects only the confidence width but not validity. We therefore take the best guess of p ⋆ \mathbf{p}^{\star} p ⋆ available before the audit, i.e., the plug-in composition p ^ t − 1 \hat{\mathbf{p}}_{t-1} p ^ t − 1 , which counts audited records at their verified labels and unaudited records at their predicted distributions q g , t \mathbf{q}_{g,t} q g , t . Applying the linear auditing procedure of § 3 to this linear tangent score yields the upper confidence sequence U t U_t U t (appendix § 19 ).
Lower bound: ruling out every composition. A tangent plane lies above H H H , so a single cross-entropy cannot certify a lower bound. Let H ⋆ : = H ( p ⋆ ) H^\star:= H(\mathbf{p}^\star) H ⋆ := H ( p ⋆ ) . To show H ⋆ > h H^\star> h H ⋆ > h , we must rule out every composition p \mathbf{p} p still consistent with the audits that could yield entropy at most h h h . Thus the lower-bound problem becomes a composite hypothesis test: we must reject the entire set of feasible compositions whose entropy is at most h h h . Let P t = { p ∈ Δ L − 1 : p s ≥ O t , s / N } P_t = \{\mathbf{p} \in\Delta^{L-1}: p_s \ge O_{t,s}/N\} P t = { p ∈ Δ L − 1 : p s ≥ O t , s / N } , where O t , s O_{t,s} O t , s counts audited records verified as s s s after t t t audits. Following Manole & Ramdas [23 ] , for each candidate composition p \mathbf{p} p we form an e-process E t L ( p ; h ) E_t^L(\mathbf{p};h) E t L ( p ; h ) whose factors have conditional mean at most one at ( p ⋆ , H ⋆ ) (\mathbf{p}^\star,H^\star) ( p ⋆ , H ⋆ ) , using a single predictable stake shared by all candidates. We rule out h h h once min p ∈ P t log E t L ( p ; h ) ≥ log ( 1 / α − ) \min_{\mathbf{p}\in P_t}\log E_t^L(\mathbf{p};h) \ge\log(1/\alpha_-) min p ∈ P t log E t L ( p ; h ) ≥ log ( 1/ α − ) , where α − \alpha_- α − is the error budget of the lower end. Sharing one stake and one prediction correction across all candidates makes this objective convex in p \mathbf{p} p , so this minimum can be certified by convex optimization rather than enumeration (appendix § 19 ). Splitting the total budget as α = α + + α − \alpha= \alpha_+ + \alpha_- α = α + + α − , the resulting interval [ L t , U t ] [L_t,U_t] [ L t , U t ] forms the desired confidence sequence. The end-to-end procedure is presented as algorithm 2 in appendix § 15 .
Experimental Results: Certifying Nonlinear Scores
We measure uncertainty using the relative margin of error . For an interval [ a , b ] [a,b] [ a , b ] , we define this as the interval half-width of the confidence sequence divided by the average of its two endpoints: ( b − a ) / 2 ( a + b ) / 2 = b − a a + b \frac{(b-a)/2}{(a+b)/2} = \frac{b-a}{a+b} ( a + b ) /2 ( b − a ) /2 = a + b b − a . Thus, a 5% target means that the confidence-sequence interval half-width is at most 5% of its midpoint. For the biodiversity credits application (see appendix § 13 ), we specialize H H H to Shannon entropy H ( p ) = − ∑ s ∈ L p s log p s H(\mathbf{p}) = -\sum_{s\in\mathcal{L}} p_s \log p_s H ( p ) = − ∑ s ∈ L p s log p s , and consider pooled Hill–Shannon diversity P 2 : = exp H ( p ⋆ ) P_2 := \exp H(\mathbf{p}^\star) P 2 := exp H ( p ⋆ ) . On the CIFAR-10N dataset, we test a different class of nonlinear scores. We define worst-three precision as the mean precision of the three least precise submitted classes g p r e c ( C ) = 1 3 ∑ r ∈ B 3 p r e c ( C ) C r r N r g_{\mathrm{prec}}(C) = \frac{1}{3}\sum_{r\in B^{\mathrm{prec}}_3(C)} \frac{C_{rr}}{N_r} g prec ( C ) = 3 1 ∑ r ∈ B 3 prec ( C ) N r C r r , where B 3 p r e c ( C ) B^{\mathrm{prec}}_3(C) B 3 prec ( C ) indexes the three smallest classwise precision values C r r / N r C_{rr}/N_r C r r / N r . We similarly define worst-three taxonomic risk (see section D.2.3). We additionally evaluate artifact-class micro-F1 on ReImageNet and token-level NER micro-F1 on CleanCoNLL. Their score definitions and settings are given in sections D.3.3 and D.4.3. The prespecified targets are 5% relative margin of error for Kenya diversity and CIFAR-10N worst-three precision, 25% for CIFAR-10N worst-three taxonomic risk, and two percentage points for the two F1 scores.
We compare against two score-specific adaptations of recent confidence-sequence methods: PPR with projection (Waudby-Smith & Ramdas, [43 ] ) and adapted Manole–Ramdas stitching (Manole & Ramdas, [23 ] ). Construction details and an uncertainty-only ablation policy are discussed in greater detail in section D.5. Across all five nonlinear settings, ATLAS-PAS has the smallest median audit count to reach the target precision. Relative to ATLAS-SRS, it requires 36–71% fewer audits. ATLAS-PAS also reduces the median audit count by 6–38% relative to the adaptive uncertainty-only ablation (section D.5), showing that downstream-score information adds value beyond label uncertainty alone. PPR with projection reaches the target precision only for ReImageNet F1, while Manole–Ramdas stitching does not attain the target in any of the five settings within 10,000 audits. The four main comparisons are displayed in Figure 3 , and the CIFAR-10N taxonomic-risk comparison is in Figure 5 . The numerical results are reported in appendix § 16 , especially Table 8 and Table 9 .
Figure 5. Certification of worst-three taxonomic risk on CIFAR-10N at 95.5% nominal confidence. Curves show median audits to attain each relative half-width over 100 paired paths; shaded regions show interquartile ranges. Dotted guides mark median stopping times at the 25% target for ATLAS-PAS and ATLAS-SRS.
Table 8. Median [25th, 75th percentiles] audits to first attain the stated precision at 95.5% nominal confidence over 100 paired paths. Precision is evaluated every 25 audits. > B > B > B denotes nonattainment within budget: B = 3,000 B = 3{,}000 B = 3 , 000 for Kenya ATLAS and uncertainty-only, and B = 10,000 B = 10{,}000 B = 10 , 000 otherwise. Quantiles include all paths, with unreached targets treated as censored. Counts are rounded to the nearest audit.
Table 9. Whole-path coverage counts out of 100 paths. Budgets match Table 8 .
A Bayesian, Model-Based Alternative for Efficient Auditing
Sections 3 and 5 provide distribution-free guarantees but can require an impractically large number of expert audits. We therefore consider a model-based alternative that shares information across related labels and strata when inferring the composition of unaudited records, trading robustness to model specification for greater statistical efficiency. Importantly, the same task-aware auditing framework accommodates both settings.
We use an approximate hierarchical Dirichlet–multinomial update. For a submitted label r r r and stratum g g g , let θ r \theta_r θ r denote the overall correction distribution and let θ g \theta_g θ g denote the stratum-specific correction distribution. We use a hierarchical Dirichlet–multinomial model (Kim & Ghahramani, [19 ] ): θ r ∼ Dirichlet ( κ r { β e r + ( 1 − β ) g } + A r , t ) \theta_r \sim\operatorname{Dirichlet}(\kappa_r\{\beta\mathbf{e}_r + (1-\beta)\mathbf{g}\} + \mathbf{A}_{r,t}) θ r ∼ Dirichlet ( κ r { β e r + ( 1 − β ) g } + A r , t ) , and θ g ∣ θ r ( g ) ∼ Dirichlet ( κ g θ r ( g ) + A g , t ) \theta_g \mid\theta_{r(g)} \sim\operatorname{Dirichlet}(\kappa_g\theta_{r(g)} + \mathbf{A}_{g,t}) θ g ∣ θ r ( g ) ∼ Dirichlet ( κ g θ r ( g ) + A g , t ) , with the remaining verified-label counts in stratum g g g modeled as Multinomial ( M g , t , θ g ) \operatorname{Multinomial}(M_{g,t}, \theta_g) Multinomial ( M g , t , θ g ) . Here, A r , t \mathbf{A}_{r,t} A r , t and A g , t \mathbf{A}_{g,t} A g , t are vectors of verified-label counts audited so far, M g , t M_{g,t} M g , t is the number of unaudited records remaining in stratum g g g , e r e_r e r places prior mass on the submitted label r r r being correct, and g ˉ \bar{\mathbf{g}} g ˉ summarizes the smoothed share of verified labels observed across all labels. The concentration parameters κ r \kappa_r κ r and κ c \kappa_c κ c control how strongly information is shared across labels and strata. As audits accumulate within a stratum, its local counts increasingly dominate the shared prior (appendix § 18 ).
We use the same priority-aware sampling policy as in § 4 . At audit t t t , we select a stratum G t G_t G t , sample one unverified record uniformly from that stratum, reveal its verified label V t V_t V t , and update the observed correction counts. Beginning after audit 100 and every 25 audits thereafter, we propagate posterior uncertainty to the downstream score by drawing stratum-level correction distributions from the posterior and, conditional on each draw, imputing verified labels for all remaining unaudited records. Each posterior draw defines a complete, corrected dataset consistent with all audits observed so far. We compute P 2 P_2 P 2 on each of 400 datasets, yielding a posterior distribution over the nonlinear downstream score without relying on the linear-envelope construction of § 5 . We report the 2.25th and 97.75th empirical quantiles as a 95.5% credible interval and stop once the interval satisfies the prespecified 5% relative-accuracy target.
Table 2 shows substantial empirical savings on the Kenyan dataset: the approximate Bayesian approach with PAS requires a median of only 250 audits compared with 500 under random sampling. Under both PAS and SRS, the credible intervals covered the true diversity at stopping on 96 of 100 paths, despite having no anytime-valid coverage guarantee. These results illustrate the potential efficiency gains from modeling assumptions and motivate developing less conservative, distribution-free confidence sequences that retain anytime-valid guarantees at practical auditing budgets.
Table 2. On the Kenya biodiversity data, the number of audits required by the approximate Bayesian procedure to estimate the entropy score P 2 P_2 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 score θ ∗ \theta^* θ ∗ at stopping time. More details in section D.1.4.
Related Work
Anytime-valid auditing. Classical concentration bounds such as Serfling’s inequality provide finite-sample guarantees for sampling without replacement at a fixed sample size ([35 Bardenet] & Maillard, 2015). More recently, Shekhar & Ramdas [36 ] sharpened fixed-sample intervals for the population mean. Confidence sequences, introduced by Darling & Robbins [8 ] , remain valid simultaneously over time and permit adaptive stopping [15 , 30 ] . Waudby-Smith & Ramdas [43 ] develop confidence sequences for uniform sampling without replacement, and Shekhar et al. [37 ] construct them for weighted means under adaptive, nonuniform sampling. For label audits, our ATLAS-PAS uses Bayesian predictions of label corrections to approximate the variance-minimizing allocation for the downstream score. Across mislabel-rate benchmarks, ATLAS-PAS typically reached the target precision with substantially fewer audits than these baselines (Table 1 ). For nonlinear scores such as entropy, one can exploit the convexity of negative entropy [23 ] or bound the score over a confidence region for the distribution of verified labels in the full dataset [43 , 32 ] . Such projections can be conservative, as Kaido et al. [16 ] discuss in partially identified models. We use the structure of each score directly. We certify the Hill–Shannon biodiversity score using a linear-envelope representation of entropy and the F1 score by expressing it as a ratio of two linear scores. In our experiments, our method typically reached the target precision with substantially fewer audits than competing anytime-valid methods (Table 8 ).
Prediction-assisted inference. Verified labels can correct for prediction error in regression [42 ] and in prediction-powered inference more broadly [2 ] . Kilian et al. [18 ] use prior information about prediction accuracy to sharpen asymptotic confidence sequences as labeled and unlabeled samples accumulate. Csillag et al. [7 ] give a general construction for incorporating predictions into e-processes and show that it preserves anytime validity. In our audit, Bayesian predictions of categorical label corrections guide which records to verify in a fixed dataset and, together with the verified labels, yield a finite-sample confidence sequence for the downstream score.
Active evaluation. Active evaluation selects test points to label to estimate or compare model performance [34 , 20 , 21 ] . Approaches include sequential planning [24 ] , active statistical inference [49 ] , and sampling rules robust to inaccurate uncertainty estimates [22 ] . Xu et al. [48 ] acquire labels for anytime-valid risk control, while Ashouriktia et al. (2026) use predictions to decide which test point to label next and derive asymptotically valid confidence intervals for the model’s average loss. Kay et al. [17 ] choose which records to label to determine which classifier performs best, and in biodiversity surveys, Haucke et al. [13 ] select records for expert review to estimate species occupancy. Every record in our fixed dataset already has a submitted label. We choose which labels to verify based on how correcting them could affect the downstream score.
Conclusion
Our work challenges a common assumption within machine learning communities: that the labels we treat as ground truth are reliable, even when labeling errors can materially distort the resulting conclusions. When these labels feed into complex downstream score functions, we show that the structure of these score functions can be leveraged to guide priority-aware auditing, substantially reducing the number of expert audits needed to obtain narrow confidence sequences while retaining finite-sample, distribution-free, and anytime-valid guarantees. Our real-world case study highlights the gap between statistical validity and practical feasibility: classical tools such as Serfling’s inequality provide rigorous finite-sample guarantees, but may require prohibitively many audits and their fixed-sample guarantees need not hold under data-dependent stopping.
Methodologically, we represent label corrections with a confusion matrix and use Bayesian predictions to guide audits toward corrections that matter most for the downstream score. ATLAS provides finite-sample guarantees under adaptive sampling and stopping and, in our experiments, typically reached the target precision with fewer audits than competing anytime-valid methods. The efficiency and validity of our approach is relevant to many high-stakes settings, including the original motivation of auditing wildlife observations to determine payments in biodiversity credit programs.
Limitations and future work. The gains from priority-aware sampling scale with increasing heterogeneity in score-relevant uncertainty across strata, and are therefore limited on highly homogeneous data. Additionally, we treat expert-verified labels as ground truth, although expert verification may itself be subject to error. An open direction is to develop direct sequential estimators for nonlinear scores that support valid e-processes and further reduce audit costs. Our model-based Bayesian alternative (section 6) provides a useful efficiency benchmark: an open question is how closely distribution-free, anytime-valid procedures can approach this empirical efficiency, and under what conditions. Further extensions include heterogeneous audit costs, multiple auditors, and nonstationary confusion patterns.
Acknowledgments
We are grateful to the Natural State Research & Monitoring team for providing the biodiversity monitoring data and expertise that made this work possible, and to their partners at the Lewa Wildlife Conservancy, Borana Conservancy, and Lolldaiga Conservancy who supported their work.
Reproducibility Statement
The appendices document the proofs and experimental settings. The supplementary repository provides the implementation, frozen seeds, processed Kenya, CIFAR-10N, and CleanCoNLL input datasets, saved results, and table- and figure-generation scripts. For ReImageNet, whose source data are governed by upstream access terms, we provide download and preprocessing instructions with verification checksums.
Ethics Statement
The biodiversity study is a retrospective replay and does not independently validate any credit or payment. Released biodiversity data exclude locations, timestamps, record identifiers, and other sensitive ecological metadata. Reference labels in CIFAR-10N, ReImageNet, and CleanCoNLL are treated as designated comparison labels and are not infallible ground truth. Prospective use must prespecify the eligible label vocabulary, preserve the randomized design, and account for expert error when verified labels are not definitive.
AI Use Statement
Generative AI tools assisted the sketching and checking of some proofs, literature searches, implementation of experiment and figure generation code, and refining this manuscript.
Audits for Biodiversity Credit Programs
To establish market credibility and prevent greenwashing, voluntary biodiversity credit schemes require standardized monitoring frameworks, robust baseline metrics, and transparent verification processes [47 , 11 ] . A project site is a landowner enrolled in a biodiversity credits program, such as a cattle rancher in rural Kenya. Each project site collects data using sensors placed on their landscape, recording wildlife observations. These data points are labeled with the specific species observed, which determine the biodiversity index for the landscape.
As a representative application, we consider the Plan Vivo “multimetric” [28 ] which includes three species-based pillars6 : species richness P 1 P_1 P 1 (number of unique species), species diversity P 2 P_2 P 2 (relative abundance of species), and taxonomic diversity P 3 P_3 P 3 (dissimilarity in the taxonomic tree). The multimetric determines the number of biodiversity certificates that the landowner is awarded, which then determines their payment.
For a candidate confusion matrix C \mathbf{C} C , let m s ( C ) : = ∑ r ∈ R C r s m_s(\mathbf{C}) := \sum_{r \in\mathcal{R}} C_{rs} m s ( C ) := ∑ r ∈ R C r s and p s ( C ) : = m s ( C ) / N p_s(\mathbf{C}) := m_s(\mathbf{C})/N p s ( C ) := m s ( C ) / N denote the corrected abundance and population proportion of species s s s , respectively, and let p ( C ) : = ( p s ( C ) ) s ∈ L \mathbf{p}(\mathbf{C}) := (p_s(\mathbf{C}))_{s \in\mathcal{L}} p ( C ) := ( p s ( C ) ) s ∈ L .
Species are categorized into disjoint groups G = { G 1 , … , G K } \mathcal{G} = \{G_1, \ldots, G_K\} G = { G 1 , … , G K } , where each group G k ⊆ L G_k \subseteq\mathcal{L} G k ⊆ L is a category such as birds, bats, or medium-to-large mammals. The within-group relative abundance of species s ∈ G k s \in G_k s ∈ G k is
p s ( G k ) ( C ) = m s ( C ) ∑ j ∈ G k m j ( C ) , s ∈ G k . (9) p_s^{(G_k)}(\mathbf{C}) = \frac{m_s(\mathbf{C})}{\sum_{j \in G_k} m_j(\mathbf{C})}, \qquad s \in G_k. \tag*{(9)} p s ( G k ) ( C ) = ∑ j ∈ G k m j ( C ) m s ( C ) , s ∈ G k . (9)
Let z s ( C ) = 1 { m s ( C ) > 0 } z_s(\mathbf{C}) = \mathbb{1}\{m_s(\mathbf{C}) > 0\} z s ( C ) = 1 { m s ( C ) > 0 } indicate whether species s s s is present in the corrected labels, S k ( C ) = ∑ s ∈ G k z s ( C ) S_k(\mathbf{C}) = \sum_{s \in G_k} z_s(\mathbf{C}) S k ( C ) = ∑ s ∈ G k z s ( C ) denote the number of species in group k k k , and S ( C ) = ∑ G k ∈ G S k ( C ) S(\mathbf{C}) = \sum_{G_k \in\mathcal{G}} S_k(\mathbf{C}) S ( C ) = ∑ G k ∈ G S k ( C ) denote the total number of present species. The three pillars of the multimetric can then be expressed as:
P 1 ( C ) = S ( C ) , (10) P_1(\mathbf{C}) = S(\mathbf{C}), \tag*{(10)} P 1 ( C ) = S ( C ) , (10)
P 2 ( C ) = D 1 ( p ( C ) ) , D 1 ( p ) = exp ( − ∑ s ∈ L p s log p s ) , (11) P_2(\mathbf{C}) = D_1(\mathbf{p}(\mathbf{C})), \qquad D_1(\mathbf{p}) = \exp\left(-\sum_{s \in\mathcal{L}} p_s \log p_s\right), \tag*{(11)} P 2 ( C ) = D 1 ( p ( C )) , D 1 ( p ) = exp ( − s ∈ L ∑ p s log p s ) , (11)
P 3 ( C ) = ∑ i < j ω i j z i ( C ) z j ( C ) ∑ i < j z i ( C ) z j ( C ) + ∑ G k ∈ G S k ( C ) S ( C ) Δ ( p ( G k ) ( C ) ) . (12) P_3(\mathbf{C}) = \frac{\sum_{i<j} \omega_{ij}z_i(\mathbf{C})z_j(\mathbf{C})}{\sum_{i<j} z_i(\mathbf{C})z_j(\mathbf{C})} + \sum_{G_k \in\mathcal{G}} \frac{S_k(\mathbf{C})}{S(\mathbf{C})}\Delta\left(p^{(G_k)}(\mathbf{C})\right). \tag*{(12)} P 3 ( C ) = ∑ i < j z i ( C ) z j ( C ) ∑ i < j ω ij z i ( C ) z j ( C ) + G k ∈ G ∑ S ( C ) S k ( C ) Δ ( p ( G k ) ( C ) ) . (12)
Here, the within-group taxonomic dissimilarity is Δ ( p ) = ∑ i < j ω i j p i p j / ∑ i < j p i p j \Delta(\mathbf{p}) = \sum_{i<j} \omega_{ij}p_i p_j/\sum_{i<j} p_i p_j Δ ( p ) = ∑ i < j ω ij p i p j / ∑ i < j p i p j , where ω i j ∈ [ 0 , Ω ] \omega_{ij} \in[0,\Omega] ω ij ∈ [ 0 , Ω ] denotes taxonomic distance and Ω \Omega Ω is some maximal taxonomic distance. The multimetric then aggregates the three pillar values, e.g., as a weighted sum: M ( C ) = Φ ( P 1 ( C ) , P 2 ( C ) , P 3 ( C ) ) M(\mathbf{C}) = \Phi(P_1(\mathbf{C}), P_2(\mathbf{C}), P_3(\mathbf{C})) M ( C ) = Φ ( P 1 ( C ) , P 2 ( C ) , P 3 ( C )) . Notably, this scoring function is both nonlinear (P 2 P_2 P 2 and P 3 P_3 P 3 ) and nonsmooth (P 1 P_1 P 1 and P 3 P_3 P 3 ).
Notation
As a convention, we use boldface for vectors (e.g., p ⋆ \mathbf{p}^{\star} p ⋆ ) and matrices (e.g., C ⋆ \mathbf{C}^{\star} C ⋆ ) and use ordinary type to refer to scalar quantities including individual entries (e.g., C r s ⋆ C^{\star}_{rs} C r s ⋆ , p s ⋆ p^{\star}_{s} p s ⋆ ).
Table 3. Core notation used in the main text. Symbols used exclusively in the appendix are defined where they are first introduced.
Algorithm Pseudocode
Reading algorithm 1. All predictions, priorities, sampling probabilities, and betting stakes are computed before the next verified label is observed; this predictability is what permits adaptive allocation without sacrificing validity. Verified strata are removed and the sampling distribution is renormalized over the remaining records. Prediction quality affects efficiency only: an inaccurate predictor may slow contraction but does not invalidate the confidence sequence.
Reading algorithm 2. The two entropy endpoints require different certificates. The upper endpoint uses a predictable linear cross-entropy direction, whereas the lower endpoint must rule out every composition still compatible with the audits through a conservative convex optimization. Both endpoints use the same audit stream, with tail budgets satisfying α + + α − ≤ α \alpha_{+}+\alpha_{-}\le\alpha α + + α − ≤ α ; the reported interval is valid only when the numerical lower-end optimization returns a certified bound rather than an unconstrained approximate solution.
Algorithm 1 ATLAS Priority-Aware Sampling (PAS) for a linear score
Require: Strata g g g , contribution matrix D \mathbf{D} D , predictor PREDICT(), miscoverage α \alpha α , SRS weight ε \varepsilon ε , target half-width τ \tau τ
while confidence-sequence half-width > τ >\tau > τ do
Predict: For each nonempty stratum g g g , estimate q g , t q_{g,t} q g , t and
μ ^ g , t = ∑ s q g , t ( s ) D r ( g ) , s , σ ^ g , t 2 = ∑ s q g , t ( s ) ( D r ( g ) , s − μ ^ g , t ) 2 . \widehat{\mu}_{g,t}=\sum_s q_{g,t}(s)D_{r(g),s},\qquad
\widehat{\sigma}^{2}_{g,t}=\sum_s q_{g,t}(s)\left(D_{r(g),s}-\widehat{\mu}_{g,t}\right)^2. μ g , t = s ∑ q g , t ( s ) D r ( g ) , s , σ g , t 2 = s ∑ q g , t ( s ) ( D r ( g ) , s − μ g , t ) 2 .
Estimate score:
θ ^ t − 1 = 1 N [ ∑ i ∈ A t − 1 D y i , v i + ∑ g M g , t μ ^ g , t ] \widehat{\theta}_{t-1}=\frac{1}{N}\left[\sum_{i\in A_{t-1}}D_{y_i,v_i}+\sum_g M_{g,t}\widehat{\mu}_{g,t}\right] θ t − 1 = N 1 i ∈ A t − 1 ∑ D y i , v i + g ∑ M g , t μ g , t
Update sampling probabilities:
π g , t = ε M g , t ∑ k M k , t + ( 1 − ε ) M g , t σ ^ g , t ∑ k M k , t σ ^ k , t . \pi_{g,t}=\varepsilon\frac{M_{g,t}}{\sum_k M_{k,t}}+(1-\varepsilon)\frac{M_{g,t}\widehat{\sigma}_{g,t}}{\sum_k M_{k,t}\widehat{\sigma}_{k,t}}. π g , t = ε ∑ k M k , t M g , t + ( 1 − ε ) ∑ k M k , t σ k , t M g , t σ g , t .
▷ Mix residual-record SRS with variance-based priority.
Set stakes: Compute the predictable range of the next Z t Z_t Z t over all possible strata and verified labels; choose capped stakes λ t ± ( m ) \lambda_t^{\pm}(m) λ t ± ( m ) for each candidate m m m .
Audit: Draw G t ∼ π t G_t\sim\pi_t G t ∼ π t and uniformly audit one unaudited record in G t G_t G t , revealing V t V_t V t .
Observe:
Z t = θ ^ t − 1 + M G t , t N π G t , t ( D r ( G t ) , V t − μ ^ G t , t ) . Z_t=\widehat{\theta}_{t-1}+\frac{M_{G_t,t}}{N\pi_{G_t,t}}\left(D_{r(G_t),V_t}-\widehat{\mu}_{G_t,t}\right). Z t = θ t − 1 + N π G t , t M G t , t ( D r ( G t ) , V t − μ G t , t ) .
Update e-processes:
E t + ( m ) = E t − 1 + ( m ) [ 1 + λ t + ( m ) ( Z t − m ) ] , E_t^{+}(m)=E_{t-1}^{+}(m)\left[1+\lambda_t^{+}(m)(Z_t-m)\right], E t + ( m ) = E t − 1 + ( m ) [ 1 + λ t + ( m ) ( Z t − m ) ] ,
E t − ( m ) = E t − 1 − ( m ) [ 1 − λ t − ( m ) ( Z t − m ) ] . E_t^{-}(m)=E_{t-1}^{-}(m)\left[1-\lambda_t^{-}(m)(Z_t-m)\right]. E t − ( m ) = E t − 1 − ( m ) [ 1 − λ t − ( m ) ( Z t − m ) ] .
Report:
I t = { m : E s ± ( m ) < 2 / α ∀ s ≤ t } , \mathcal{I}_t=\left\{m:E_s^{\pm}(m)<2/\alpha\ \forall s\le t\right\}, I t = { m : E s ± ( m ) < 2/ α ∀ s ≤ t } ,
and update the audited set and remaining stratum sizes.
end while
return $\mathcal{I}_t
Algorithm 2 ATLAS Distribution-free audit of entropy
Require: Strata g g g , predictor PREDICT(), tail budgets α ± \alpha_{\pm} α ± , smoothing η \eta η , target log-width τ = log ( 21 / 19 ) \tau= \log(21/19) τ = log ( 21/19 )
while Current endpoint width U t − 1 − L t − 1 > τ U_{t-1}-L_{t-1}>\tau U t − 1 − L t − 1 > τ do
Predict composition: Estimate q g , t \mathbf{q}_{g,t} q g , t for each nonempty stratum and form
p ^ t − 1 = 1 N [ O t − 1 + ∑ g M g , t q g , t ] , O t − 1 = ( O t − 1 , s ) s ∈ L . \widehat{\mathbf{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}=(O_{t-1,s})_{s\in\mathcal{L}}. p t − 1 = N 1 [ O t − 1 + g ∑ M g , t q g , t ] , O t − 1 = ( O t − 1 , s ) s ∈ L .
Compute cross-entropy weights:
r t = ( 1 − η ) p ^ t − 1 + η L 1 , ψ t = − log r t . \mathbf{r}_t=(1-\eta)\widehat{\mathbf{p}}_{t-1}+\frac{\eta}{L}\mathbf{1},\qquad\boldsymbol{\psi}_t=-\log\mathbf{r}_t. r t = ( 1 − η ) p t − 1 + L η 1 , ψ t = − log r t .
Estimate stratum influence:
μ ^ g , t = q g , t T ψ t , σ ^ g , t 2 = ∑ s q g , t ( s ) ( ψ t , s − μ ^ g , t ) 2 . \widehat{\mu}_{g,t}=\mathbf{q}_{g,t}^{\mathsf{T}}\boldsymbol{\psi}_t,\qquad\widehat{\sigma}_{g,t}^{2}=\sum_s q_{g,t}(s)(\psi_{t,s}-\widehat{\mu}_{g,t})^2. μ g , t = q g , t T ψ t , σ g , t 2 = s ∑ q g , t ( s ) ( ψ t , s − μ g , t ) 2 .
Update sampling probabilities:
π t = 0.4 π t p r o p + 0.3 π t f l o o r + 0.3 π t p r i , \boldsymbol{\pi}_t=0.4\boldsymbol{\pi}^{\mathrm{prop}}_t+0.3\boldsymbol{\pi}^{\mathrm{floor}}_t+0.3\boldsymbol{\pi}^{\mathrm{pri}}_t, π t = 0.4 π t prop + 0.3 π t floor + 0.3 π t pri ,
where
π g , t p r o p ∝ M g , t , π g , t f l o o r ∝ M g , t ( 1 + μ ^ g , t ) , π g , t p r i ∝ M g , t σ ^ g , t . \pi^{\mathrm{prop}}_{g,t}\propto M_{g,t},\qquad\pi^{\mathrm{floor}}_{g,t}\propto M_{g,t}(1+\widehat{\mu}_{g,t}),\qquad\pi^{\mathrm{pri}}_{g,t}\propto M_{g,t}\widehat{\sigma}_{g,t}. π g , t prop ∝ M g , t , π g , t floor ∝ M g , t ( 1 + μ g , t ) , π g , t pri ∝ M g , t σ g , t .
Set stakes: Choose predictable upper/lower stakes from the range of ψ t \boldsymbol{\psi}_t ψ t , the possible Horvitz–Thompson weights, and current endpoints L t − 1 , U t − 1 L_{t-1},U_{t-1} L t − 1 , U t − 1 .
Audit: Draw G t ∼ π t G_t\sim\boldsymbol{\pi}_t G t ∼ π t and uniformly audit one unaudited record in G t G_t G t , revealing V t V_t V t .
Upper endpoint: Form the prediction-corrected directional observation Z t U Z_t^{U} Z t U using contributions ψ t \boldsymbol{\psi}_t ψ t , update
E t U ( h ) = E t − 1 U ( h ) [ 1 − λ t U ( Z t U − h ) ] , E_t^{U}(h)=E_{t-1}^{U}(h)[1-\lambda_t^{U}(Z_t^{U}-h)], E t U ( h ) = E t − 1 U ( h ) [ 1 − λ t U ( Z t U − h )] ,
and set U t U_t U t to the smallest h h h ruled out by the upper e-process.
Lower endpoint: For each candidate composition p \mathbf{p} p , form Z t ( p ) Z_t(\mathbf{p}) Z t ( p ) using the smoothed composition p ~ = ( N p + 1 ) / ( N + L ) \widetilde{\mathbf{p}}=(N\mathbf{p}+\mathbf{1})/(N+L) p = ( N p + 1 ) / ( N + L ) and update
F t ( p ; h ) = F t − 1 ( p ; h ) + log [ 1 + λ t L { Z t ( p ) − h − c } ] , c = log ( 1 + L / N ) . F_t(\mathbf{p};h)=F_{t-1}(\mathbf{p};h)+\log[1+\lambda_t^{L}\{Z_t(\mathbf{p})-h-c\}],\qquad c=\log(1+L/N). F t ( p ; h ) = F t − 1 ( p ; h ) + log [ 1 + λ t L { Z t ( p ) − h − c }] , c = log ( 1 + L / N ) .
Profile over feasible compositions: For each h h h , compute a certified lower bound on
min p ∈ P t F t ( p ; h ) \min_{\mathbf{p}\in\mathcal{P}_t}F_t(\mathbf{p};h) p ∈ P t min F t ( p ; h )
by projected gradient plus a supporting-plane bound; use bisection in h h h to obtain L t L_t L t .
Report:
P 2 ∈ [ e L t , e U t ] , P ^ 2 , t = 2 e L t + U t e L t + e U t , P_2\in[e^{L_t},e^{U_t}],\qquad\widehat{P}_{2,t}=\frac{2e^{L_t+U_t}}{e^{L_t}+e^{U_t}}, P 2 ∈ [ e L t , e U t ] , P 2 , t = e L t + e U t 2 e L t + U t ,
then update counts and remaining records.
end while
return [ e L t , e U t ] [e^{L_t},e^{U_t}] [ e L t , e U t ] and P ^ 2 , t \widehat{P}_{2,t} P 2 , t
Experiment Settings and Additional Results
All error-rate experiments use nominal confidence 95.5% (α = 0.045 \alpha= 0.045 α = 0.045 ). PAS and SRS use the same prediction-corrected betting confidence sequence and differ only in their predictable sampling probabilities. Records are sampled uniformly within the selected stratum. Paired policies use identical randomized within-stratum record orders.
The mislabel-rate experiments use 100 paired paths with seeds 2026110900, . . . , 2026110999. Predictors start from a common, flat correctness probability of 0.5 and are updated using audited labels only. Sampling decisions are made before the selected reference label is revealed. Intervals are evaluated after every audit, and target attainment is recorded from audit 100 onward. Runs continue through 5,000 audits even after reaching the target, allowing us to evaluate subsequent interval widths and whole-path coverage.
For each precision level, we record the first eligible update at which a nonempty interval attains that precision. The real-data audit curves plot the median of these per-path attainment times against precision and shaded regions show their interquartile ranges. Paths that do not attain a target within budget remain censored and are included when computing quantiles. Empty intervals do not count as precision attainment, and paths with coverage failures are not discarded.
ATLAS allocation mixtures are fixed within each experimental setting. Mislabel-rate and F1 experiments use a 0.30 SRS component. The Kenya diversity and CIFAR nonlinear experiments use proportional components 0.40 and 0.70, respectively, together with score-dependent range and variance components. The Bayesian experiment uses a 0.20 proportional component.
Kenya Biodiversity Setting
Data
Camera-trap records supplied by our NGO partner, pair submitted identifications with expert corrections. We merge label variants into broad categories (e.g., zebra subspecies into Zebra), retaining all 33,403 records and a shared vocabulary of 50 categories.
Linear Score: Mislabel Rate
Submitted labels define 46 audit strata. The predictive error model starts from error probability 0.5 in every stratum, with row and secondary shrinkage strengths 2 and 1. PAS combines 30% remaining-record SRS with 70% predicted Neyman allocation. PAS and SRS share the same initialization, prediction updates, and confidence-sequence construction. Full results are presented in Table 1 and displayed in Figure 2 .
Nonlinear Score: Pillar 2 Diversity
As in the main text, let
m s ( C ) = ∑ r C r s , p s ( C ) = m s ( C ) N m_s(\mathbf{C}) = \sum_r C_{rs}, \qquad p_s(\mathbf{C}) = \frac{m_s(\mathbf{C})}{N} m s ( C ) = r ∑ C r s , p s ( C ) = N m s ( C )
denote the corrected abundance and population proportion of species s s s induced by a candidate confusion matrix C \mathbf{C} C . Pillar 2 is the Hill–Shannon diversity of this corrected composition:
H ( p ( C ) ) = − ∑ s ∈ C p s ( C ) log p s ( C ) , P 2 ( C ) = exp { H ( p ( C ) ) } . H(\mathbf{p}(\mathbf{C})) = -\sum_{s\in\mathcal{C}} p_s(\mathbf{C}) \log p_s(\mathbf{C}), \qquad P_2(\mathbf{C}) = \exp\{H(\mathbf{p}(\mathbf{C}))\}. H ( p ( C )) = − s ∈ C ∑ p s ( C ) log p s ( C ) , P 2 ( C ) = exp { H ( p ( C ))} .
Thus, P 2 P_2 P 2 is the effective number of species implied by the corrected labels: it increases when the composition contains more species or distributes mass more evenly among them. Label corrections affect P 2 P_2 P 2 through the column totals of C \mathbf{C} C , and its nonlinearity makes uncertainty in rare or poorly audited species especially consequential.
The distribution-free P 2 P_2 P 2 experiment uses 300 nonempty strata obtained by crossing submitted label with camera station. The prediction hierarchy shrinks station-level distributions toward their submitted-label row with strength 1, and row distributions toward a pooled composition with strength 2. The row-level predictive base is 0.8 e r + 0.2 p ˉ t − 1 0.8e_r + 0.2\bar{p}_{t-1} 0.8 e r + 0.2 p ˉ t − 1 , where e r e_r e r concentrates on the submitted label and p ˉ t − 1 \bar{p}_{t-1} p ˉ t − 1 is the smoothed composition estimated from previously audited labels. This composition is uniform before the first audit. Row and stratum shrinkage strengths are 2 and 1, respectively. The predictable reference composition used in the entropy direction is
r t = 0.99 p ^ t − 1 + 0.01 L 1. \mathbf{r}_t = 0.99\hat{\mathbf{p}}_{t-1} + \frac{0.01}{L}\mathbf{1}. r t = 0.99 p ^ t − 1 + L 0.01 1 .
The experimental score is evaluated over the full cleaned annotation vocabulary, including the non-species categories retained in the audit population.
PAS uses the frozen mixture
π t P A S = 0.4 π t p r o p + 0.3 π t r a n g e + 0.3 π t N e y m a n . \boldsymbol{\pi}^{\mathrm{PAS}}_t = 0.4\boldsymbol{\pi}^{\mathrm{prop}}_t + 0.3\boldsymbol{\pi}^{\mathrm{range}}_t + 0.3\boldsymbol{\pi}^{\mathrm{Neyman}}_t. π t PAS = 0.4 π t prop + 0.3 π t range + 0.3 π t Neyman .
The proportional component samples according to remaining stratum size, the range component controls the possible range of the importance-weighted observation, and the Neyman component uses predicted within-stratum variation in the current entropy direction.
Table 5. Frozen settings for the Kenyan biodiversity data distribution-free diversity experiment.
The entropy interval is transformed outward to the P 2 P_2 P 2 scale. The stopping criterion ( e U t − e L t ) / ( e U t + e L t ) ≤ 0.05 (e^{U_t}-e^{L_t})/(e^{U_t}+e^{L_t}) \leq0.05 ( e U t − e L t ) / ( e U t + e L t ) ≤ 0.05 requires the confidence-sequence half-width to be at most 5% of its midpoint. SRS and PAS use the same lower convex-profile certificate, upper affine certificate, prediction hierarchy, and stake rules.
Results. The median audits to reach 5% relative half-width are 1,625 for ATLAS-PAS, 1,913 for uncertainty-only allocation, and 2,550 for ATLAS-SRS. All 100 PAS paths and 87 of 100 SRS paths reach the target within 3,000 audits. Neither PPR projection nor MR stitching reaches the target within 10,000 audits on any path. Full results are reported in Table 8 and displayed in Figure 3 (a).
Bayesian Settings
Setting. We evaluate the model-based procedure of § 6 on the Kenyan biodiversity dataset. PAS and SRS use the same hierarchical Dirichlet–multinomial model, posterior computation, credible interval, and stopping rule; they differ only in audit allocation. Records are sampled uniformly within the selected stratum, and paired PAS and SRS paths use the same randomized within-stratum record orders.
The computation uses an empirical-Bayes-style hierarchical approximation. At each update, the pooled label composition is re-estimated from audited counts with add-one smoothing and treated as fixed in the subsequent Dirichlet updates. Its estimation uncertainty is not integrated through a full joint posterior. Completed-population draws preserve all audited labels and impute only the remaining records. The resulting intervals have nominal credibility under this approximation and carry no distribution-free anytime-valid coverage guarantee.
The model hyperparameters are fixed at β = 0.5 \beta= 0.5 β = 0.5 , κ r = 2 \kappa_r = 2 κ r = 2 , and κ c = 0.5 \kappa_c = 0.5 κ c = 0.5 , with add-one smoothing of the pooled verified-label composition. Posterior intervals are evaluated every 25 audits beginning at audit 100. Each evaluation uses 400 completed-population draws. We take the 2.25th and 97.75th percentiles of their entropy values and exponentiate these endpoints to obtain the interval for P 2 P_2 P 2 .
PAS uses the frozen allocation
π t P A S = 0.2 π t p r o p + 0.8 π t N e y m a n , π g , t N e y m a n ∝ M g , t σ ^ g , t \pi_t^{\mathrm{PAS}} = 0.2\pi_t^{\mathrm{prop}} + 0.8\pi_t^{\mathrm{Neyman}}, \qquad\pi_{g,t}^{\mathrm{Neyman}} \propto M_{g,t}\hat{\sigma}_{g,t} π t PAS = 0.2 π t prop + 0.8 π t Neyman , π g , t Neyman ∝ M g , t σ ^ g , t
where σ ^ g , t \hat{\sigma}_{g,t} σ ^ g , t is the predicted within-stratum standard deviation of the entropy influence direction. Its variance includes the light-audit adjustment 1 + 1 / ( n g , t + κ c ) 1 + 1/(n_{g,t} + \kappa_c) 1 + 1/ ( n g , t + κ c ) , where n g , t n_{g,t} n g , t denotes the number of records audited in stratum g g g before audit t t t . Consequently, the adjustment inflates predicted uncertainty only in lightly audited strata. SRS samples uniformly from all unaudited records. Neither policy uses a pilot phase.
Coverage. Coverage at stopping records whether the interval contains the true score at the first checkpoint satisfying the precision target. Whole-path coverage requires inclusion at every evaluated checkpoint, starting at audit 100 and ending at that path’s stopping time. Runs terminate when the target is reached. Coverage at stopping is 96/100 for both policies, whereas whole-path coverage is 71/100 for PAS and 53/100 for SRS. Thus, favorable coverage at the selected stopping time coexists with substantially lower simultaneous coverage along the audit.
Table 6. Frozen settings for the Bayesian diversity experiment.
Results. Median stopping counts are 250 [225, 250] for Bayesian PAS and 500 [450, 550] for Bayesian SRS, where brackets give the 25th and 75th percentiles. Coverage at stopping is 96/100 for both policies, while coverage at every checked update through stopping is 71/100 and 53/100, respectively.
CIFAR-10N Setting
Data
CIFAR-10N adds noisy human annotations to the ten-class CIFAR-10 image dataset [45 ] . We retain all 50,000 training images, pairing random_label1 as the submitted label with clean_label as the reference; no records are filtered. The 40 strata combine the ten submitted classes with four agreement patterns: both auxiliary annotations support the submitted label, exactly one supports it, both agree on another label, or all three annotations differ.
Linear Score: Mislabel Rate
The additional noisy annotations, random_label2 and random_label3, are assumed available before auditing and define agreement-based strata together with the submitted label. All strata start with the same predicted error probability of 0.5; predictions are subsequently updated using only audited records. No audit-reference labels are used for pre-audit calibration or configuration selection.
The experiment uses the frozen settings in Table 4 . Audit-reference labels are revealed only when their records are audited and are otherwise used solely for evaluating the completed experiments. Reported audit counts exclude the collection of the pre-existing auxiliary annotations. Full results are presented in Table 1 , and Figure 4 shows the mislabel rate certification curves across ATLAS and baselines.
Table 4. Frozen ATLAS settings for the four mislabel-rate experiments. Comparator-specific settings are given in section D.7.
Figure 4. Audits on CIFAR-10N. (Left ) Confusion matrix. Diagonal entries indicate agreement with the reference labels, while off-diagonal entries indicate label disagreements. Cell annotations give record counts, and color displays 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 with 25th–75th percentile shaded bands. Methods and plotting conventions match Figure 2 ; dots mark the audits required to reach a half-width of two percentage points. Numerical results are reported in Table 1 .
Nonlinear Score: Worst-Three Scores
For a confusion matrix C \mathbf{C} C , let N r = ∑ s = 1 10 C r s N_r = \sum_{s=1}^{10} C_{rs} N r = ∑ s = 1 10 C r s denote the number of records submitted as class r r r . The classwise precision is p r ( C ) = C r r / N r p_r(\mathbf{C}) = C_{rr}/N_r p r ( C ) = C r r / N r . We define worst-three precision as the mean precision of the three least precise submitted classes:
g p r e c ( C ) = min S ⊆ [ 10 ] ∣ S ∣ = 3 1 3 ∑ r ∈ S C r r N r . g_{\mathrm{prec}}(\mathbf{C}) = \min_{\substack{S \subseteq[10] \\ |S|=3}} \frac{1}{3} \sum_{r \in S} \frac{C_{rr}}{N_r}. g prec ( C ) = S ⊆ [ 10 ] ∣ S ∣ = 3 min 3 1 r ∈ S ∑ N r C r r .
To define taxonomic risk, we map each CIFAR-10 class to a fixed noun synset in Princeton WordNet 3.0 [9 ] . For each pair of classes r , s r, s r , s , we compute the unweighted shortest-path distance between their synsets in the undirected WordNet hypernym graph and normalize it by the largest distance among the ten classes. This gives a fixed semantic-distance matrix D t a x = ( d r s ) \mathbf{D}^{\mathrm{tax}} = (d_{rs}) D tax = ( d r s ) , with d r r = 0 d_{rr} = 0 d r r = 0 and d r s ∈ [ 0 , 1 ] d_{rs} \in[0, 1] d r s ∈ [ 0 , 1 ] .
The classwise taxonomic risk is the average semantic severity of corrections from submitted class r r r ,
τ r ( C ) = 1 N r ∑ s = 1 10 C r s d r s . \tau_r(\mathbf{C}) = \frac{1}{N_r} \sum_{s=1}^{10} C_{rs}d_{rs}. τ r ( C ) = N r 1 s = 1 ∑ 10 C r s d r s .
We define worst-three taxonomic risk as the mean risk of the three highest-risk submitted classes:
g t a x ( C ) = max S ⊆ [ 10 ] ∣ S ∣ = 3 1 3 ∑ r ∈ S τ r ( C ) = max S ⊆ [ 10 ] ∣ S ∣ = 3 1 3 ∑ r ∈ S 1 N r ∑ s = 1 10 C r s d r s . g_{\mathrm{tax}}(\mathbf{C}) = \max_{\substack{S \subseteq[10]\\ |S|=3}} \frac{1}{3} \sum_{r \in S} \tau_r(\mathbf{C}) = \max_{\substack{S \subseteq[10]\\ |S|=3}} \frac{1}{3} \sum_{r \in S} \frac{1}{N_r} \sum_{s=1}^{10} C_{rs}d_{rs}. g tax ( C ) = S ⊆ [ 10 ] ∣ S ∣ = 3 max 3 1 r ∈ S ∑ τ r ( C ) = S ⊆ [ 10 ] ∣ S ∣ = 3 max 3 1 r ∈ S ∑ N r 1 s = 1 ∑ 10 C r s d r s .
Confidence-sequence construction. Both scores are extrema over the ( 10 3 ) = 120 \binom{10}{3} = 120 ( 3 10 ) = 120 triples of submitted classes. For each fixed triple S S S , its average precision θ S \theta_S θ S is linear in the confusion matrix because the submitted class counts N r N_r N r are known. Lemma 1 therefore gives an audit observation with conditional mean θ S \theta_S θ S .
Consider worst-three precision, g = min S θ S g = \min_S \theta_S g = min S θ S . To establish that g > m g > m g > m , we need evidence that every triple has precision above m m m . We test θ S ≤ m \theta_S \le m θ S ≤ m for each triple and reject g ≤ m g \le m g ≤ m once all 120 tests have crossed 2 / α 2/\alpha 2/ α , possibly at different audit times. If g ≤ m g \le m g ≤ m , at least one fixed minimizing triple satisfies θ S ≤ m \theta_S \le m θ S ≤ m . Rejecting the overall null requires that triple’s test to cross, which has probability at most α / 2 \alpha/2 α /2 by Ville’s inequality.
To establish that g < m g < m g < m , we can focus on the classes predicted to have the lowest precision. Before each audit, we select the three such classes and use their audit observation to update a single downward betting process. Under g ≥ m g \ge m g ≥ m , every triple has precision at least m m m . Thus the selected observation has conditional mean at least m m m , even when the selected triple changes between audits. The betting process is a nonnegative supermartingale, so its probability of ever crossing 2 / α 2/\alpha 2/ α is at most α / 2 \alpha/2 α /2 . Combining the two tests gives a 1 − α 1 - \alpha 1 − α confidence sequence.
For worst-three taxonomic risk, the target is a maximum. We use all 120 triples for the upper bound and the three classes with the highest predicted risk for the lower bound. The same proof applies with the inequalities reversed.
Numerical endpoints. We evaluate candidate scores on a grid with spacing 0.001. We take the interval from the smallest to the largest surviving grid point, expand it by one grid step at each end, and clip it to [ 0 , 1 ] [0, 1] [ 0 , 1 ] . If the grid is empty, we retain the last nonempty interval, starting from [ 0 , 1 ] [0, 1] [ 0 , 1 ] . This outward rounding preserves coverage: the upward test rejects a lower tail of grid values, and the downward test rejects an upper tail. Except on the two crossing events bounded above, the grid ceiling of the true score survives the upward test and its grid floor survives the downward test. The expanded interval therefore contains the true score.
Predictor and sampling policy. Before incorporating a class’s own audit results, the predictor gives 80% weight to its submitted label and 20% to the label frequencies estimated from all audits so far. Before the first audit, these frequencies are initialized uniformly across the ten classes. The row and secondary shrinkage strengths are 2 and 1, respectively.
Because the worst three classes are unknown, PAS assigns 70% of its sampling probability to simple random sampling among the remaining records. This ensures that classes outside the predicted worst three continue to receive audits. The remaining probability is split equally between the range-based and Neyman allocations. Both prioritize classes predicted to be among the worst three and classes belonging to triples that still limit the confidence bound, giving equal weight to the two criteria. Tied classes share predicted membership weight equally, and the triple weights are smoothed using a softmax with temperature 1.
Development and confirmation use separate randomized audit paths on the same fixed population. On each confirmation path, we record the first checkpoint at which the relative half-width ( U t − L t ) / ( U t + L t ) (U_t-L_t)/(U_t+L_t) ( U t − L t ) / ( U t + L t ) is at most 5% for precision or 25% for taxonomic risk. Table 7 gives the full experimental settings.
Table 7. Frozen settings for the CIFAR-10N worst-three experiments.
Results. For worst-three precision, the median audit counts were 3,850 for ATLAS-PAS and 6,550 for ATLAS-SRS. For worst-three taxonomic risk, the corresponding counts were 3,450 and 5,588. Neither PPR projection nor MR stitching reached either target on any path within 10,000 audits. Table 8 gives the full comparison. The precision and taxonomic-risk curves appear in Figure 3 (b) and Figure 5 , respectively.
ReImageNet Setting
Data
ReImageNet provides revised annotations for the ImageNet-1K validation set ([41 ] ). We retain 30,908 records having exactly one valid original label and one valid corrected label, excluding multilabel and unresolved cases. In the nonlinear score setting, we compute micro-F1 over 351 artifact classes (human-made objects such as tools, clothing, and furniture). However, we audit all 30,908 records across 964 nonempty submitted-label classes, including those originally labeled outside this group, so the score captures both non-artifacts incorrectly labeled as artifacts and artifacts incorrectly labeled as non-artifacts.
Linear Score: Mislabel Rate
We audit the binary disagreement between the original and corrected labels over all 30,908 retained records. The population mislabel rate is 8.09%, and the 964 nonempty submitted-label classes define the audit strata. All methods use the shared protocol in Table 4 . Median stopping counts are 1,394 for ATLAS-PAS and 1,539 for ATLAS-SRS; the additional comparator results are reported in Table 1 . Figure 6 shows the ReImageNet mislabel rate certification curves across ATLAS and baselines.
Figure 6. Audits on ReImageNet. (Left) Confusion matrix for 13 feline classes, selected for visualization from the 964 nonempty submitted-label classes. The Other column collects corrections outside the displayed subset. Cell annotations give record counts, shown on a logarithmic color scale. This display restriction does not change the audit population. (Right) Margin of error (half-width of the 95.5% mislabel-rate confidence sequence) as the number of audits increases with 25th–75th percentile shaded bands. Methods and plotting conventions match Figure 2 ; dots mark the audits required to reach a half-width of two percentage points. Numerical results are reported in Table 1 .
Nonlinear Score: Artifact-Class Micro-F1
The target is micro-F1 over a fixed set A \mathcal{A} A of 351 artifact classes, including tools, clothing, and furniture. For submitted-to-reference confusion counts C r s C_{rs} C r s , we define
F 1 , A ( C ) = 2 ∑ k ∈ A C k k ∑ r ∈ A ∑ s C r s + ∑ r ∑ s ∈ A C r s . F_{1,\mathcal{A}}(\mathbf{C}) = \frac{2\sum_{k\in\mathcal{A}} C_{kk}}{\sum_{r\in\mathcal{A}}\sum_s C_{rs}+\sum_r\sum_{s\in\mathcal{A}} C_{rs}}. F 1 , A ( C ) = ∑ r ∈ A ∑ s C r s + ∑ r ∑ s ∈ A C r s 2 ∑ k ∈ A C k k .
A true positive requires an exact match of the original and corrected fine-grained class. Confusing two different artifact classes therefore contributes both a false positive and a false negative. Records crossing the artifact/non-artifact boundary also contribute to the score.
The restriction applies to the scored classes; all 30,908 records remain eligible for auditing. Sampling uses the same 964 submitted-label strata as the mislabel-rate experiment. The target half-width is 2 percentage points at 95.5% nominal confidence, with the shared F1 settings in section D.5.
Results. Median stopping counts are 2,250 for ATLAS-PAS, 3,363 for uncertainty-only allocation, 7,138 for PPR projection, and 7,638 for ATLAS-SRS. MR stitching does not reach the target within 10,000 audits on any path. Full results are reported in Table 8 and displayed in Figure 3 (c).
CleanCoNLL Setting
Data
CleanCoNLL corrects named-entity annotations in English CoNLL-2003 news text [31 ] . We pool all splits, standardize labels to BIO2, and retain 301,353 exactly aligned token pairs, excluding edited or unalignable tokens. The O class remains in the audit population but is excluded from the token-level F1 target.
Linear Score: Mislabel Rate
The mislabel-rate experiment includes all 301,353 retained tokens, including tokens labeled O. Any disagreement between the submitted and corrected BIO2 tags counts as an error. The nine submitted tags define the audit strata, and the population mislabel rate is 1.20%. We use the shared settings in Table 4 .
Median stopping counts are 281 for ATLAS-PAS and 293 for ATLAS-SRS. Prop-M + CV has a smaller median of 233, but reaches the target on 75/100 paths within 5,000 audits, compared with 100/100 for ATLAS-PAS. Table 1 contains full numerical results and Figure 7 shows the CleanCoNLL mislabel rate certification curves across ATLAS and baselines.
Figure 7. Audits on CleanCoNLL. (Left ) NER Confusion matrix of tokens. Diagonal entries indicate agreement with the reference labels, while off-diagonal entries indicate label disagreements. Cell annotations give record counts, and color displays 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 with 25th–75th percentile shaded bands. Methods and plotting conventions match Figure 2 ; dots mark the audits required to reach a half-width of two percentage points. Numerical results are reported in Table 1 .
Nonlinear Score: Token-Level NER Micro-F1
We compute token-level micro-F1 over the eight named-entity BIO2 tags: the B- and I- forms of PER, ORG, LOC, and MISC. The score uses the definition in section D.3.3, with A A A equal to these eight tags. A true positive requires an exact tag match, including both entity type and B/I status. This is a token-level score rather than an entity-span score.
The O tag denotes the absence of a named entity and is therefore excluded from the scored classes. All O tokens remain in the audit population: corrections from O to an entity tag contribute false negatives, and corrections from an entity tag to O contribute false positives. Correctly labeled background tokens do not contribute true positives.
Results. We retain the full population and its nine submitted-tag strata, using the shared F1 settings in section D.5. The target is an absolute half-width of 2 percentage points. Median stopping counts are 2,638 for ATLAS-PAS and 2,800 for uncertainty-only allocation. The medians for ATLAS-SRS, PPR projection, and MR stitching exceed the 10,000-audit budget. Full results are reported in Table 8 and displayed in Figure 3 (d).
Nonlinear Scores: Supplemental Details and Results
Shared F1 settings. Both F1 experiments use 100 paired paths with seeds 96201, . . . , 96300, a 10,000-audit budget, and precision evaluation every 25 audits. The confidence level is 95.5%, and the target absolute half-width is 0.02.
The ATLAS predictive base initially mixes 0.8 mass on the submitted label with 0.2 mass on the uniform distribution over the full label vocabulary. The pooled distribution is subsequently updated from audited labels, with row and secondary shrinkage strengths 2 and 1. PAS mixes 0.30 proportional-to-remaining-size sampling with 0.70 score-aware Neyman allocation. The candidate-score grid spacing is 0.0005, the stake effective horizon is 800, and the stake cap fraction is 0.90. ATLAS-SRS uses the same inference and predictor with uniform sampling.
Results. Table 8 presents full numerical precision-attainment results for the ATLAS policies, the uncertainty-only ablation policy, and baselines.
Auditing policies: inference and allocation
We compare five methods at 95.5% confidence for each score. All methods sample without replacement. The three ATLAS policies use the same predictor and confidence sequence within each experiment. They differ only in how they choose the next record.
ATLAS confidence sequences. After each audit, we use the verified label and its sampling probability to update the evidence against candidate score values. The construction depends on the score.
Hill–Shannon biodiversity score. We construct a confidence sequence for Shannon entropy as in § 5 . For the upper endpoint, the predicted label proportions determine a linear upper bound on entropy before each audit. We use this bound to test whether entropy is at least a candidate value h h h . For the lower endpoint, we test whether entropy is at most h h h . We reject this hypothesis only when the evidence reaches the rejection threshold for every label composition consistent with the audits so far. Appendix § 19 shows how to check this condition by convex optimization. Exponentiating the two entropy endpoints gives the interval for Hill–Shannon diversity.
Worst-three precision and taxonomic risk. For each of the 120 triples of CIFAR-10N classes, average precision is linear in the confusion matrix. Worst-three precision is the minimum of these averages. To establish that the minimum exceeds m m m , we require every triple’s upward test to cross its threshold. To establish that the minimum is below m m m , we update one downward test using the triple predicted before each audit to have the lowest precision. This is valid because, if the minimum is at least m m m , every selected triple has average precision at least m m m . Worst-three taxonomic risk is a maximum, so the directions
reverse: all triples determine the upper endpoint, and the triple predicted to have the highest risk is used to update the lower endpoint.
F1. Write the score as ∑ i u i / ∑ i w i \sum_i u_i/\sum_i w_i ∑ i u i / ∑ i w i , where u i u_i u i and w i w_i w i are record i i i ’s contributions to the numerator and denominator. For each candidate f f f , the score equals f f f exactly when the population mean of u i − f w i u_i - f w_i u i − f w i is zero. We apply the two one-sided e-processes of appendix H to this linear score and retain f f f while neither process has reached 2 / α 2/\alpha 2/ α .
Uncertainty-only allocation. This policy favors strata whose verified labels are difficult to predict, regardless of how those labels affect the score. Let q g k , t q_{gk,t} q g k , t be the predicted probability of verified label k k k in stratum g g g and define s g , t 2 = 1 − ∑ k q g k , t 2 s_{g,t}^2 = 1 - \sum_k q_{gk,t}^2 s g , t 2 = 1 − ∑ k q g k , t 2 . This quantity is zero when the predictor assigns all its mass to one label and increases as the predictions become more dispersed. Using the same uniform sampling weight ϵ \epsilon ϵ as PAS, we select stratum g g g with probability
π g , t = ϵ M g , t ∑ h M h , t + ( 1 − ϵ ) M g , t s g , t ∑ h M h , t s h , t . \pi_{g,t} = \epsilon\frac{M_{g,t}}{\sum_h M_{h,t}} + (1-\epsilon) \frac{M_{g,t}s_{g,t}}{\sum_h M_{h,t}s_{h,t}}. π g , t = ϵ ∑ h M h , t M g , t + ( 1 − ϵ ) ∑ h M h , t s h , t M g , t s g , t .
If the second denominator is zero, we sample uniformly. Relative to this policy, PAS reduced median audit counts by 15% for diversity, 38% for worst-three precision, 37% for worst-three taxonomic risk, 33% for ReImageNet F1, and 6% for CleanCoNLL F1. For the binary mislabel indicator, s g , t s_{g,t} s g , t is proportional to the predicted standard deviation of that indicator, so the two allocation rules coincide.
PPR with projection. We first construct simultaneous confidence sequences for the counts that determine each score. For each count, we use a uniform working prior over possible population counts and update it using the hypergeometric likelihood. At each audit, we retain candidate counts whose prior-to-posterior probability ratio has stayed below the reciprocal of the error budget assigned to that count. The budgets sum to α \alpha α , so all retained count intervals cover simultaneously with probability at least 1 − α 1-\alpha 1 − α . We then bound the score over the counts that remain possible.
For diversity, the verified-label counts must also sum to N N N . We bound entropy over the resulting set of label proportions using chords and tangents, then exponentiate the endpoints. For worst-three precision, we bound each class’s precision and average the three smallest lower bounds and the three smallest upper bounds. For taxonomic risk, we use the row-label count bounds to bound each class’s risk and average the three largest bounds on each side. For F1, let A A A be the known number of records submitted as a target class. Among records whose submitted and verified labels differ, let FP count those submitted as a target class and FN count those verified as a target class. A correction between two target classes contributes to both counts. The number of true positives is therefore A − F P A-\mathrm{FP} A − FP , giving
F 1 = 2 ( A − F P ) 2 A − F P + F N . F_1 = \frac{2(A-\mathrm{FP})}{2A-\mathrm{FP}+\mathrm{FN}}. F 1 = 2 A − FP + FN 2 ( A − FP ) .
We construct a confidence sequence for each count at error level α / 2 \alpha/2 α /2 . Since F 1 F_1 F 1 decreases as either count increases, substituting both upper bounds gives the lower F1 endpoint, and substituting both lower bounds gives the upper endpoint.
MR stitching. We follow the stitching schedule and constants of Manole and Ramdas [23 ] .7 Within each time window, we use concentration bounds for uniform sampling without replacement. For diversity, we use the convexity of negative entropy to bound Shannon entropy, then exponentiate the endpoints. For CIFAR-10N, we bound the average score for each triple of classes and take the minimum for worst-three precision or the maximum for worst-three taxonomic risk. For F1, we retain each candidate f f f for which the interval for the population mean of u i − f w i u_i-f w_i u i − f w i contains zero. At each update, we intersect the interval with all earlier intervals and with the range of scores consistent with the labels verified so far.
Empirical coverage. Table 9 counts a path as covered if its interval contains the true score at every evaluated update through the full audit budget, including updates after the target precision is first reached. All paths contribute to the efficiency summaries, including those with a coverage failure.
Synthetic Data: A Priority Mechanism Study
The synthetic experiment isolates the acquisition advantage produced by heterogeneous score relevance. Its confirmation population contains 20 equal-sized submitted-label rows with 250 records per row, for N = 5,000 N = 5{,}000 N = 5 , 000 . Four rows have equal numbers of records with score contributions 0 and 1. The other 16 rows each have two possible verified destinations, both with score contribution 0.25. Their verified labels remain uncertain, but that uncertainty does not affect the chosen score.
Let D r s s y n D^{\mathrm{syn}}_{rs} D r s syn denote the fixed score contribution associated with submitted row r r r and verified destination s s s . The target is the population-wide linear risk
g ( C ) = 1 N ∑ r , s D r s s y n C r s . g(\mathbf{C}) = \frac{1}{N} \sum_{r,s} D^{\mathrm{syn}}_{rs} C_{rs}. g ( C ) = N 1 r , s ∑ D r s syn C r s .
The score equals 0.30 in the confirmation population. To isolate the allocation mechanism, PAS uses the known population row standard deviations in the remaining-size-aware Neyman rule
π r , t P A S ∝ M r , t σ r , \pi^{\mathrm{PAS}}_{r,t} \propto M_{r,t}\sigma_r, π r , t PAS ∝ M r , t σ r ,
where σ r = 0.5 \sigma_r = 0.5 σ r = 0.5 for the four score-variable rows and zero for the constant-contribution rows. These standard deviations remain fixed throughout the experiment, and no SRS floor is used. Rows with constant score contributions receive no PAS audits. SRS remains uniform over all unaudited records. Both policies use the same prediction-assisted linear betting confidence sequence.
Table 10. Frozen synthetic-experiment settings.
The scaling screen fixes four score-variable rows and varies the total number of rows over
R ∈ { 8 , 12 , 20 , 32 , 48 } . R \in\{8, 12, 20, 32, 48\}. R ∈ { 8 , 12 , 20 , 32 , 48 } .
Each configuration uses five development seeds and an 800-audit budget. This screen tests the predicted increase in PAS advantage as the number of score-invariant nuisance rows grows. Confirmation fixes R = 20 R = 20 R = 20 and uses the 100 fresh paths reported above.
Figure 8. Controlled synthetic experiment isolating the benefit of priority-aware sampling. (a) 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 R R increases while the number of score-variable rows remains fixed at k = 4 k = 4 k = 4 . The dotted curve shows the idealized 1 − k / R 1 - \sqrt{k/R} 1 − k / R reference: SRS allocates only a fraction k / R k/R 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.
Additional Mislabel-Rate Comparators
The default prior–posterior-ratio confidence sequence is evaluated on the same 100 SRS audit orders used by our betting confidence sequence. It uses a uniform BetaBinomial(N N N , 1, 1) working prior on the population error count and reports the running intersection of its candidate sets.
The Wald reference uses the true population error variance, no finite-population correction, and nominal confidence 95.5%. It is an oracle-variance, fixed-sample asymptotic reference. The Serfling reference is the corresponding finite-population, fixed-sample bound. Wald and Serfling therefore provide benchmark sample sizes rather than anytime-valid stopping rules.
The Chebyshev reference uses the Bernoulli variance bound 1 / 4 1/4 1/4 with the finite-population correction. Its required audit count is computed analytically. Like the Serfling reference, it is a fixed-sample benchmark rather than an anytime-valid stopping rule.
Fixed-sample benchmark counts are computed from their deterministic half-width formulas and therefore have no across-path interquartile range. In particular, the CleanCoNLL Serfling result uses the unclipped radius, which reaches 0.02 at 4,670 audits.
We evaluate two implementations of Shekhar et al. [37 ] , aligned with the authors’ code at commit a834e459. For mislabel-rate estimation, all records have equal weight and the audited outcome is the binary error indicator. Prop-MS samples in proportion to predicted error probability. Prop-M + CV samples uniformly and uses the error predictor as a centered control variate. Both variants receive the same initially flat predictor, updated only from paid audits.
We retain the reference approximate-Kelly betting rules and use α = 0.045 \alpha= 0.045 α = 0.045 with candidate-grid spacing 0.0005. The implementation supplies predictable, audit-updated side information and conservatively certifies rejection over grid cells for continuous-parameter reporting. Both variants use the same 100 seeds and 5,000-audit budget as ATLAS.
Whole-path coverage for Prop-M + CV is 90/100 on Kenya, 98/100 on CIFAR-10N, and 97/100 on both ReImageNet and CleanCoNLL, evaluated at every audit through the full 5,000-audit budget. Coverage failures are retained in all reported summaries. On CleanCoNLL, its smaller median stopping count is accompanied by target attainment on 75/100 paths, compared with 100/100 for ATLAS-PAS.
Sensitivity Studies and Robustness
Sensitivity to the SRS mixing weight ϵ \epsilon ϵ
ATLAS-PAS mixes its priority-aware allocation with simple random sampling:
π r , t ( ϵ ) = ( 1 − ϵ ) π r , t N e y m a n + ϵ π r , t S R S , \pi_{r,t}^{(\epsilon)} = (1-\epsilon)\pi_{r,t}^{\mathrm{Neyman}} + \epsilon\pi_{r,t}^{\mathrm{SRS}}, π r , t ( ϵ ) = ( 1 − ϵ ) π r , t Neyman + ϵ π r , t SRS ,
where the Neyman component is proportional to remaining stratum size times predicted error standard deviation.
The mixing weight ϵ \epsilon ϵ ensures continued exploration of every stratum. We evaluated
ϵ ∈ { 0.05 , 0.1 , 0.2 , … , 0.9 , 1.0 } , \epsilon\in\{0.05, 0.1, 0.2, \ldots, 0.9, 1.0\}, ϵ ∈ { 0.05 , 0.1 , 0.2 , … , 0.9 , 1.0 } ,
where ϵ = 1 \epsilon= 1 ϵ = 1 is ATLAS-SRS and ϵ = 0.3 \epsilon= 0.3 ϵ = 0.3 is the default used in the mislabel-rate experiments. All other settings were fixed. Each value was evaluated on the same 100 seeds and within-stratum record orderings for Kenya, CIFAR-10N, ReImageNet, and CleanCoNLL.
For each path, we recorded the first audit at or after 100 at which the nonempty 95.5% confidence interval had half-width at most 2 percentage points. Each path continued through 5,000 audits. Figure 9 reports the median and interquartile range of these first-crossing counts. To place datasets with different audit requirements on one scale, each dataset is divided by its largest median over the ϵ \epsilon ϵ grid.
Figure 9. Sensitivity of mislabel-rate certification to the SRS mixing weight ε \varepsilon ε . Points show the median number of audits required to reach a 2-percentage-point half-width, and shaded regions show the 25th–75th percentiles over 100 paired paths. Results are normalized separately for each dataset by its largest median over the tested grid. The dotted lines mark the default ε = 0.3 \varepsilon= 0.3 ε = 0.3 and ATLAS-SRS at ε = 1 \varepsilon= 1 ε = 1 .
Results. The default ϵ = 0.3 \epsilon= 0.3 ϵ = 0.3 is optimal on CIFAR-10N and lies within 22 audits of the best tested value on Kenya and within 6 audits on ReImageNet. At the default, the median audit counts are 603, 790, and 1,394, compared with 814, 980, and 1,539 under SRS. CleanCoNLL favors greater exploration, with its best result near ϵ = 0.7 \epsilon= 0.7 ϵ = 0.7 , although the default still improves slightly over SRS. This behavior is consistent with its highly imbalanced label distribution: early priority estimates can concentrate audits too strongly, while additional random exploration stabilizes the allocation. Overall, the results show that the main gains persist across a broad range of mixing weights and do not strongly depend on dataset-specific tuning of ϵ \epsilon ϵ .
Sensitivity to predictive initialization
PAS uses a working predictive distribution to estimate which strata are most uncertain. Its formal guarantee holds for every predictable initialization, and this experiment measures how those initializations affect efficiency and verification of empirical coverage. We varied the initialization in the Kenya mislabel-rate and Hill–Shannon diversity experiments while keeping the confidence sequences, sampling rules, and all other parameters fixed.
For mislabel rate, the initial probability that a submitted label is correct was varied from 0% to 100% in increments of 10 percentage points. The default is 50%. For diversity, we used
( 1 − w ) e y r + w p ˉ t − 1 , (1-w)e_{y_r} + w\bar{p}_{t-1}, ( 1 − w ) e y r + w p ˉ t − 1 ,
where e y r e_{y_r} e y r places all mass on the submitted label and p ˉ t − 1 \bar{p}_{t-1} p ˉ t − 1 is the pooled distribution formed from previously audited labels, initialized uniformly. Thus w w w controls the initial uniform mixture and subsequently the weight on the audit-updated pooled distribution.
We ran 100 paired paths at each of the 11 initialization settings for each score, with budgets of 5,000 audits for mislabel rate and 3,000 for diversity. This gives 4,400 policy paths in total, reusing the same 100 seeds across initializations within each score. Precision is evaluated after every audit for mislabel rate, with attainment eligible from audit 100, and every 25 audits for diversity. Targets are a 2-percentage-point half-width and a 5% relative half-width, respectively. Whole-path coverage is the fraction of paths whose intervals contain the true score at every checked update through the full budget, including updates after target attainment.
Results. For mislabel rate, PAS requires between 603 and 631 median audits across initial correctness probabilities from 20% to 80%. Extreme initializations are less efficient: the 0% and 100% settings require 1,566 and 2,352 median audits, respectively, and perform worse than SRS under the same initializations. For diversity, PAS requires between 1,550 and 1,625 median audits for mixture weights from 10% through 100%, while the all-submitted-label initialization requires 1,888. Whole-path coverage ranges from 94–97% for linear PAS and 99–100% for diversity PAS. These results support stable efficiency over a broad range of initializations while also showing the cost of severely misspecified initial predictions.
Sensitivity to predictor misspecification
We evaluate how errors in the predictive distribution affect the efficiency of ATLAS-PAS on the Kenya mislabel-rate task. Each condition uses 100 paired audit paths, the same 30% SRS exploration component, and the same 95.5% confidence sequence as the main experiment. The endpoint is the first audit after audit 100 at which the interval half-width reaches two percentage points. PAS and SRS use the same predictor transformation within each condition, applied to their respective audit histories. All transformations are predictable and therefore preserve the validity of the confidence sequence.
Let p r , t p_{r,t} p r , t denote the error probability predicted for stratum r r r before audit t t t . Calibration is varied using
q r , t = p r , t k p r , t k + ( 1 − p r , t ) k , q_{r,t} = \frac{p_{r,t}^{k}}{p_{r,t}^{k} + (1 - p_{r,t})^{k}}, q r , t = p r , t k + ( 1 − p r , t ) k p r , t k ,
where k < 1 k < 1 k < 1 produces underconfident predictions and k > 1 k > 1 k > 1 produces overconfident predictions while preserving the uncertainty ranking across strata. We also test a constant predictor, q r , t = 0.5 q_{r,t} = 0.5 q r , t = 0.5 , and a deliberately adversarial transformation that reverses the learned ranking of p r , t ( 1 − p r , t ) p_{r,t}(1 - p_{r,t}) p r , t ( 1 − p r , t ) . reversal is applied for the first 25, 50, or 100 audits, or throughout the complete audit. After a temporary reversal, the ordinary learned predictor resumes while retaining the preceding audit history.
Figure 10. Sensitivity to predictive initialization on the Kenya dataset. The top row shows median audits to the target precision, with 25th–75th percentile bands over 100 paired paths. The bottom row shows empirical whole-path coverage through the full audit budget. The left column varies the initial correctness probability for mislabel-rate certification; the right column varies the uniform-mixture weight for Hill–Shannon diversity. Vertical dotted lines mark the defaults, and the horizontal dashed line marks 95.5% nominal coverage.
Results. Moderate misspecification degrades efficiency without eliminating the benefit: doubling the predicted log-odds reduces the PAS savings from 25.9% to 7.8%. Underconfidence has little effect, whereas stronger overconfidence makes PAS 42.7% slower than SRS despite preserving the uncertainty ranking. With a constant predictor, PAS reduces exactly to allocation by remaining stratum mass and therefore matches SRS.
Incorrect early rankings have a persistent cost. Reversing the learned uncertainty ranking for the first 25, 50, and 100 audits changes the relative savings to −1.0%, −9.1%, and −17.4%, respectively. Persistent reversal is substantially more damaging, with only 65 of 100 PAS paths attaining the target within budget. These results characterize the practical limit of the efficiency claim: validity is retained under predictable misspecification, but audit savings depend on the predictive distribution providing useful estimates of score-relevant uncertainty, particularly during the early audit. The whole-path coverage counts are included as finite-run diagnostics; the formal coverage guarantee follows from predictability rather than from these empirical frequencies.
Computational Environment
All experiments were executed on a local machine with 15 CPU cores and 24 GB of unified memory. Computation was CPU-only; no GPU or external computing cluster was used. Independent score-policy-seed tasks were distributed across four local worker processes.
The final runs used macOS 26.5 and Python 3.14.7. Principal numerical and reporting dependencies were NumPy 2.5.2, SciPy 1.18.1, pandas 3.0.5, and Matplotlib 3.11.1. Each worker wrote an independent result shard, and aggregation began only after all expected shards for that experiment had completed.
Table 11. Sensitivity of ATLAS to predictor misspecification for mislabel-rate certification on the Kenya biodiversity dataset. Audit counts are medians and [25th,75th] percentiles over 100 paths to reach a two-percentage-point margin of error. Negative savings indicate that PAS was slower than SRS. Coverage entries give PAS/SRS counts, each out of 100, for containing the true value at every audit through 5,000. All paths reach the target except 35 PAS paths under ranking reversal.
Linear scores
Lemma 4 (Ville’s inequality Ville [40 ] ). Let ( W t ) t ≥ 0 (W_t)_{t\geq0} ( W t ) t ≥ 0 be a nonnegative supermartingale with respect to ( F t ) (\mathcal{F}_t) ( F t ) with W 0 = 1 W_0 = 1 W 0 = 1 . Then Pr { ∃ t : W t ≥ c } ≤ 1 / c \Pr\{\exists t : W_t \geq c\} \leq1/c Pr { ∃ t : W t ≥ c } ≤ 1/ c for every c > 0 c > 0 c > 0 .
Predictions. Any predictable q g , t \mathbf{q}_{g,t} q g , t keeps Lemma 1 valid; good predictions only reduce the variance equation (5) . We use a two-level shrinkage estimator, built only from the audits before audit t t t . Let A r , t ( s ) \mathbf{A}_{r,t}(s) A r , t ( s ) and A g , t ( s ) \mathbf{A}_{g,t}(s) A g , t ( s ) be the numbers of audited records in row r r r and in stratum g g g that were verified as s s s , and n r , t = ∑ s A r , t ( s ) n_{r,t} = \sum_s A_{r,t}(s) n r , t = ∑ s A r , t ( s ) , n g , t = ∑ s A g , t ( s ) n_{g,t} = \sum_s A_{g,t}(s) n g , t = ∑ s A g , t ( s ) the numbers audited. Then
g ˉ t ( s ) = 1 / L + ∑ r A r , t ( s ) 1 + ( t − 1 ) \bar{g}_t(s) = \frac{1/L + \sum_r A_{r,t}(s)}{1 + (t - 1)} g ˉ t ( s ) = 1 + ( t − 1 ) 1/ L + ∑ r A r , t ( s )
(pooled verified labels)
q r , t = A r , t + κ r { β e r + ( 1 − β ) g ˉ t } n r , t + κ r \mathbf{q}_{r,t} = \frac{\mathbf{A}_{r,t} + \kappa_r\{\beta\mathbf{e}_r + (1-\beta)\bar{\mathbf{g}}_t\}}{n_{r,t} + \kappa_r} q r , t = n r , t + κ r A r , t + κ r { β e r + ( 1 − β ) g ˉ t }
(submitted label r r r ) (13)
q g , t = A g , t + κ c q r ( g ) , t n g , t + κ c \mathbf{q}_{g,t} = \frac{\mathbf{A}_{g,t} + \kappa_c\mathbf{q}_{r(g),t}}{n_{g,t} + \kappa_c} q g , t = n g , t + κ c A g , t + κ c q r ( g ) , t
(stratum g g g within row r ( g ) r(g) r ( g ) ), (14)
where e r \mathbf{e}_r e r is the unit vector at r r r . Before any audit in row r r r , the prediction puts weight β \beta β on “the submitted label is correct” and spreads the rest over the labels verified so far. As audits accumulate, each row moves toward its own verified-label frequencies, and each stratum toward its own frequencies within its row. Each level is the posterior mean of a Dirichlet–multinomial model whose prior is centered on the level above. This is the same structure as the Bayesian model of § 6 , but here it is used only for prediction, never for inference. On the Kenya data we use β = 0.8 \beta= 0.8 β = 0.8 , κ r = 2 \kappa_r = 2 κ r = 2 and κ c = 1 \kappa_c = 1 κ c = 1 , fixed before the audit and not tuned.
Proofs for sec:linear
Proof of theorem 1. Unbiasedness. Given F t − 1 \mathcal{F}_{t-1} F t − 1 , G t = g G_t = g G t = g , and J t ∈ [ N ] J_t \in[N] J t ∈ [ N ] as the record selected for expert audit at time t t t , J t J_t J t is uniform on g ∖ A t − 1 g \setminus\mathcal{A}_{t-1} g ∖ A t − 1 , so E [ D y t ∣ F t − 1 , G t = g ] = μ g , t \mathbb{E}[D_{y_t} \mid\mathcal{F}_{t-1}, G_t = g] = \mu_{g,t} E [ D y t ∣ F t − 1 , G t = g ] = μ g , t . Averaging over G t G_t G t ,
E [ M G t , t N π G t , t ( D y J t V t − q G t , t T D r ( G t ) ) | F t − 1 ] = ∑ g : M g , t > 0 π g , t M g , t N π g , t ( μ g , t − q g , t T d r ( g ) ) = 1 N ∑ g M g , t ( μ g , t − q g , t T d r ( g ) ) . \mathbb{E}\left[\frac{M_{G_t,t}}{N\pi_{G_t,t}}\left(D_{y_{J_t}}V_t-\mathbf{q}_{G_t,t}^{\mathsf{T}}D_r(G_t)\right)\middle|\mathcal{F}_{t-1}\right]
=
\sum_{g:M_{g,t}>0}\pi_{g,t}\frac{M_{g,t}}{N\pi_{g,t}}\left(\mu_{g,t}-\mathbf{q}_{g,t}^{\mathsf{T}}\mathbf{d}r(g)\right)
=
\frac{1}{N}\sum_g M_{g,t}\left(\mu_{g,t}-\mathbf{q}_{g,t}^{\mathsf{T}}\mathbf{d}r(g)\right). E [ N π G t , t M G t , t ( D y J t V t − q G t , t T D r ( G t ) ) F t − 1 ] = g : M g , t > 0 ∑ π g , t N π g , t M g , t ( μ g , t − q g , t T d r ( g ) ) = N 1 g ∑ M g , t ( μ g , t − q g , t T d r ( g ) ) .
The condition π g , t > 0 \pi_{g,t}>0 π g , t > 0 whenever M g , t > 0 M_{g,t}>0 M g , t > 0 lets the probabilities cancel. Adding θ ^ t − 1 \hat{\theta}_{t-1} θ ^ t − 1 , the predicted terms cancel and equation (2) gives θ ⋆ \theta^\star θ ⋆ . Variance. Only the correction is random. Its conditional second moment is ∑ g π g , t ( M g , t / N π g , t ) 2 E [ ( D y J t V t − q g , t T d r ( g ) ) 2 ∣ G t = g ] = N − 2 ∑ g ( M g , t 2 / π g , t ) ( σ g , t 2 + b g , t 2 ) \sum_g\pi_{g,t}(M_{g,t}/N\pi_{g,t})^2\mathbb{E}[(D_{y_{J_t}}V_t-\mathbf{q}_{g,t}^{\mathsf{T}}\mathbf{d}r(g))^2\mid G_t=g]=N^{-2}\sum_g(M_{g,t}^2/\pi_{g,t})(\sigma_{g,t}^2+b_{g,t}^2) ∑ g π g , t ( M g , t / N π g , t ) 2 E [( D y J t V t − q g , t T d r ( g ) ) 2 ∣ G t = g ] = N − 2 ∑ g ( M g , t 2 / π g , t ) ( σ g , t 2 + b g , t 2 ) . Subtracting the square of its mean, N − 1 ∑ g M g , t b g , t N^{-1}\sum_gM_{g,t}b_{g,t} N − 1 ∑ g M g , t b g , t , gives equation (5) .
Proof of theorem 3. With exact predictions b g , t = 0 b_{g,t}=0 b g , t = 0 and equation (5) is N − 2 ∑ g γ g 2 / π g N^{-2}\sum_g\gamma_g^2/\pi_g N − 2 ∑ g γ g 2 / π g with γ g = M g , t σ g , t \gamma_g=M_{g,t}\sigma_{g,t} γ g = M g , t σ g , t . This is convex on { π ≥ ℓ , ∑ g π g = 1 } \{\pi\ge\ell,\sum_g\pi_g=1\} { π ≥ ℓ , ∑ g π g = 1 } , and the KKT conditions give π g = max { ℓ g , γ g / ν } \pi_g=\max\{\ell_g,\gamma_g/\nu\} π g = max { ℓ g , γ g / ν } . Without floors, Cauchy–Schwarz gives ∑ g γ g 2 / π g ≥ ( ∑ g γ g ) 2 \sum_g\gamma_g^2/\pi_g\ge(\sum_g\gamma_g)^2 ∑ g γ g 2 / π g ≥ ( ∑ g γ g ) 2 with equality when π g ∝ γ g \pi_g\propto\gamma_g π g ∝ γ g . For refinement, split g g g into g 1 , … , g J g_1,\ldots,g_J g 1 , … , g J with shares ρ j \rho_j ρ j ; by the law of total variance and Jensen, σ g 2 ≥ ∑ j ρ j σ g j 2 ≥ ( ∑ j ρ j σ g j ) 2 \sigma_g^2\ge\sum_j\rho_j\sigma_{g_j}^2\ge(\sum_j\rho_j\sigma_{g_j})^2 σ g 2 ≥ ∑ j ρ j σ g j 2 ≥ ( ∑ j ρ j σ g j ) 2 , so M g σ g ≥ ∑ j M g j σ g j M_g\sigma_g\ge\sum_jM_{g_j}\sigma_{g_j} M g σ g ≥ ∑ j M g j σ g j .
The range of one observation. The stake caps need predictable bounds valid for every stratum that could be drawn and every unobserved label:
Z t = θ ^ t − 1 + min g : M g , t > 0 M g , t N π g , t ( min v D r ( g ) v − q g , t T D r ( g ) ) , Z_t=\hat{\theta}_{t-1}+\min_{g:M_{g,t}>0}\frac{M_{g,t}}{N\pi_{g,t}}\left(\min_vD_r(g)v-\mathbf{q}_{g,t}^{\mathsf{T}}D_r(g)\right), Z t = θ ^ t − 1 + g : M g , t > 0 min N π g , t M g , t ( v min D r ( g ) v − q g , t T D r ( g ) ) ,
Z ‾ t = θ ^ t − 1 + max g : M g , t > 0 M g , t N π g , t ( max v D r ( g ) v − q g , t T D r ( g ) ) . \overline{Z}_t=\hat{\theta}_{t-1}+\max_{g:M_{g,t}>0}\frac{M_{g,t}}{N\pi_{g,t}}\left(\max_vD_r(g)v-\mathbf{q}_{g,t}^{\mathsf{T}}D_r(g)\right). Z t = θ ^ t − 1 + g : M g , t > 0 max N π g , t M g , t ( v max D r ( g ) v − q g , t T D r ( g ) ) .
For the error rate, min v D r v = 0 \min_vD_rv=0 min v D r v = 0 and max v D r v = 1 \max_vD_rv=1 max v D r v = 1 in every row.
Proof of theorem 2. Consider E t + E_t^+ E t + at m = θ ⋆ m=\theta^\star m = θ ⋆ . If θ ⋆ > Z t \theta^\star>Z_t θ ⋆ > Z t the stake is at most 0.9 / ( θ ⋆ − Z t ) 0.9/(\theta^\star-Z_t) 0.9/ ( θ ⋆ − Z t ) , so 1 + λ t + ( Z t − θ ⋆ ) ≥ 1 − 0.9 = 0.1 1+\lambda_t^+(Z_t-\theta^\star)\ge1-0.9=0.1 1 + λ t + ( Z t − θ ⋆ ) ≥ 1 − 0.9 = 0.1 ; if θ ⋆ ≤ Z t \theta^\star\le Z_t θ ⋆ ≤ Z t the factor is at least one. By theorem 1 its conditional mean is one. So E t + ( θ ⋆ ) E_t^+(\theta^\star) E t + ( θ ⋆ ) is a nonnegative martingale with E 0 + = 1 E_0^+=1 E 0 + = 1 , and theorem 4 gives Pr { ∃ t : E t + ( θ ⋆ ) ≥ 2 / α } ≤ α / 2 \Pr\{\exists t:E_t^+(\theta^\star)\ge2/\alpha\}\le\alpha/2 Pr { ∃ t : E t + ( θ ⋆ ) ≥ 2/ α } ≤ α /2 . The same holds for E t − ( θ ⋆ ) E_t^-(\theta^\star) E t − ( θ ⋆ ) with the cap 0.9 / ( Z t − θ ⋆ ) 0.9/(Z_t-\theta^\star) 0.9/ ( Z t − θ ⋆ ) . The sequence misses θ ⋆ \theta^\star θ ⋆ only if one of the two reaches 2 / α 2/\alpha 2/ α .
Evaluating the sequence on a grid. In the experiment, candidates are evaluated on the grid m j = j / 2000 m_j=j/2000 m j = j /2000 , j = 0 , … , 2000 j=0,\ldots,2000 j = 0 , … , 2000 . On each interval [ m j , m j + 1 ] [m_j,m_{j+1}] [ m j , m j + 1 ] each side’s stake is held constant at the more constrained endpoint: λ + \lambda^+ λ + capped at 0.9 / ( m j + 1 − Z t ) 0.9/(m_{j+1}-Z_t) 0.9/ ( m j + 1 − Z t ) and λ − \lambda^- λ − at 0.9 / ( Z t − m j ) 0.9/(Z_t-m_j) 0.9/ ( Z t − m j ) . Then 1 + λ + ( Z t − m ) 1+\lambda^+(Z_t-m) 1 + λ + ( Z t − m ) decreases and 1 − λ − ( Z t − m ) 1-\lambda^-(Z_t-m) 1 − λ − ( Z t − m ) increases in m m m on the interval, so if θ ⋆ ∈ [ m j , m j + 1 ] \theta^\star\in[m_j,m_{j+1}] θ ⋆ ∈ [ m j , m j + 1 ] is not rejected, neither are m j + 1 m_{j+1} m j + 1 by the upward test nor m j m_j m j by the downward test. Retaining every grid interval whose right end survives the upward test and whose left end survives the downward test therefore preserves coverage exactly, and differs from the hull of surviving grid points by at most one grid step (only 0.05 percentage points).
Choosing the stakes. Within the caps, the stake decides how fast evidence accumulates. Suppose the observations have mean m + δ m+\delta m + δ and variance v v v . Expanding log ( 1 + x ) ≈ x − x 2 / 2 \log(1+x)\approx x-x^2/2 log ( 1 + x ) ≈ x − x 2 /2 , each review adds about λ δ − λ 2 v / 2 \lambda\delta-\lambda^2v/2 λ δ − λ 2 v /2 to log E t + ( m ) \log E_t^+(m) log E t + ( m ) , so after n n n reviews the sum is ruled out once n ( λ δ − λ 2 v / 2 ) ≥ log ( 2 / α ) n(\lambda\delta-\lambda^2v/2)\ge\log(2/\alpha) n ( λ δ − λ 2 v /2 ) ≥ log ( 2/ α ) , that is, once δ ≥ log ( 2 / α ) / ( n λ ) + λ v / 2 \delta\ge\log(2/\alpha)/(n\lambda)+\lambda v/2 δ ≥ log ( 2/ α ) / ( nλ ) + λ v /2 . The stake that makes this smallest is
λ = 2 log ( 2 / α ) n v , giving δ = 2 v log ( 2 / α ) n . \lambda=\sqrt{\frac{2\log(2/\alpha)}{nv}},
\qquad\text{giving}\qquad
\delta=\sqrt{\frac{2v\log(2/\alpha)}{n}}. λ = n v 2 log ( 2/ α ) , giving δ = n 2 v log ( 2/ α ) .
A large stake is safe when the observations are quiet and dangerous when they are noisy. Neither ν \nu ν nor the number of reviews is known in advance, so we use the predictable plug-in rule of Waudby-Smith & Ramdas (2024) in its fixed-horizon form: we replace v v v by a running estimate computed from past reviews only, and n n n by a planned horizon n ⋆ n^\star n ⋆ ,
λ t = 2 log ( 2 / α ) n ⋆ v ^ t , λ t + ( m ) = min { λ t , 0.9 m − Z t } , λ t − ( m ) = min { λ t , 0.9 Z t − m } , (13) \lambda_t=\sqrt{\frac{2\log(2/\alpha)}{n^\star\hat v_t}},\qquad\lambda_t^+(m)=\min\left\{\lambda_t,\frac{0.9}{m-Z_t}\right\},\qquad\lambda_t^-(m)=\min\left\{\lambda_t,\frac{0.9}{Z_t-m}\right\}, \tag*{(13)} λ t = n ⋆ v ^ t 2 log ( 2/ α ) , λ t + ( m ) = min { λ t , m − Z t 0.9 } , λ t − ( m ) = min { λ t , Z t − m 0.9 } , (13)
where a cap is dropped when its denominator is nonpositive and
v ^ t = 1 t { 1 4 + ∑ i < t ( Z i − θ ^ i − 1 Z ) 2 } , θ ^ i Z = 1 i ∑ j ≤ i Z j , θ ^ 0 Z = θ ^ 0 . \hat v_t=\frac{1}{t}\left\{\frac{1}{4}+\sum_{i<t}(Z_i-\hat\theta_{i-1}^Z)^2\right\},\qquad\hat\theta_i^Z=\frac{1}{i}\sum_{j\le i}Z_j,\qquad\hat\theta_0^Z=\hat\theta_0. v ^ t = t 1 { 4 1 + i < t ∑ ( Z i − θ ^ i − 1 Z ) 2 } , θ ^ i Z = i 1 j ≤ i ∑ Z j , θ ^ 0 Z = θ ^ 0 .
The term 1 4 \frac{1}{4} 4 1 , the largest variance of a [0, 1] variable, keeps early stakes small before any variance has been observed. The horizon n ⋆ n^\star n ⋆ is the number of reviews at which the stakes are sharpest. The half-width of the interval is insensitive to n ⋆ n^\star n ⋆ , and we use n ⋆ = 800 n^\star=800 n ⋆ = 800 throughout without tuning.
This is what separates the e-process from Serfling’s bound. Serfling’s width is set by the largest possible variance, 1 / 4 1/4 1/4 ; here the width { 2 v ^ t log ( 2 / α ) / n } 1 / 2 \{2\hat v_t\log(2/\alpha)/n\}^{1/2} { 2 v ^ t log ( 2/ α ) / n } 1/2 is set by the variance actually observed, which is 0.147 for the raw error indicator and far smaller once the predictions of equation (4) have learned the rows.
Entropy and linear envelopes: construction and proofs
Target and guarantee
We write p ⋆ = p ( C ⋆ ) \mathbf{p}^\star=\mathbf{p}(C^\star) p ⋆ = p ( C ⋆ ) for the corrected composition, H ⋆ = H ( p ⋆ ) H^\star=H(\mathbf{p}^\star) H ⋆ = H ( p ⋆ ) for its entropy, and Δ L − 1 \Delta^{\mathcal{L}-1} Δ L − 1 for the set of compositions on the vocabulary L \mathcal{L} L , with 0 log 0 = 0 0\log0=0 0 log 0 = 0 . The audit reports a lower end L t L_t L t and an upper end U t U_t U t after every audit. We split the total level as α = α − + α + \alpha=\alpha_-+\alpha_+ α = α − + α + , and require
Pr { L t ≤ H ⋆ ≤ U t for all t ≥ 0 } ≥ 1 − α − − α + (14) \Pr\{L_t\le H^\star\le U_t\text{ for all }t\ge0\}\ge1-\alpha_- -\alpha_+ \tag*{(14)} Pr { L t ≤ H ⋆ ≤ U t for all t ≥ 0 } ≥ 1 − α − − α + (14)
for every labeling.
Here α − \alpha_- α − bounds the probability that the lower end ever exceeds H ⋆ H^\star H ⋆ , and α + \alpha_+ α + bounds the probability that the upper end ever falls below it. The experiments use α − = α + = 0.0225 \alpha_-=\alpha_+=0.0225 α − = α + = 0.0225 .
The diversity interval is P 2 ∈ [ e L t , e U t ] P_2\in[e^{L_t},e^{U_t}] P 2 ∈ [ e L t , e U t ] . We stop once the report is within 5% of every value in the interval, which by theorem 5 means U t − L t ≤ log ( 21 / 19 ) U_t-L_t\le\log(21/19) U t − L t ≤ log ( 21/19 ) .
Proposition 5 (Reporting a point value). For 0 < P ≤ P ‾ 0<P\le\overline{P} 0 < P ≤ P , the report minimizing max P ∈ [ P , P ‾ ] ∣ x − P ∣ / P \max_{P\in[P,\overline{P}]}|x-P|/P max P ∈ [ P , P ] ∣ x − P ∣/ P is x ⋆ = 2 P P ‾ / ( P + P ‾ ) x^\star=2P\overline{P}/(P+\overline{P}) x ⋆ = 2 P P / ( P + P ) . Its worst-case relative error is ( P ‾ − P ) / ( P ‾ + P ) (\overline{P}-P)/(\overline{P}+P) ( P − P ) / ( P + P ) , which equals tanh { ( U t − L t ) / 2 } \tanh\{(U_t-L_t)/2\} tanh {( U t − L t ) /2 } for P = e L t P=e^{L_t} P = e L t and P ‾ = e U t \overline{P}=e^{U_t} P = e U t . So 5% relative accuracy holds if and only if U t − L t ≤ 2 artanh ( 0.05 ) = log ( 21 / 19 ) U_t-L_t\le2\operatorname{artanh}(0.05)=\log(21/19) U t − L t ≤ 2 artanh ( 0.05 ) = log ( 21/19 ) .
Proof. For x ∈ [ P , P ‾ ] x\in[P,\overline{P}] x ∈ [ P , P ] the worst case is at an endpoint, giving max { x / P − 1 , 1 − x / P ‾ } \max\{x/P-1,1-x/\overline{P}\} max { x / P − 1 , 1 − x / P } . A report outside the interval is worse at the nearer endpoint. The first term increases in x x x and the second decreases; they meet at x ⋆ x^\star x ⋆ with value ( P ‾ − P ) / ( P + P ‾ ) (\overline{P}-P)/(P+\overline{P}) ( P − P ) / ( P + P ) . Writing W = U t − L t W=U_t-L_t W = U t − L t , this equals ( e W − 1 ) / ( e W + 1 ) = tanh ( W / 2 ) (e^W-1)/(e^W+1)=\tanh(W/2) ( e W − 1 ) / ( e W + 1 ) = tanh ( W /2 ) , and tanh ( W / 2 ) ≤ 0.05 \tanh(W/2)\le0.05 tanh ( W /2 ) ≤ 0.05 if and only if W ≤ log ( 1.05 / 0.95 ) W\le\log(1.05/0.95) W ≤ log ( 1.05/0.95 ) .
The reference composition and the observation from each audit
Gibbs’ inequality. For a reference r \mathbf{r} r with every r s > 0 r_s>0 r s > 0 , CE ( p , r ) − H ( p ) = KL ( p ∥ r ) \operatorname{CE}(\mathbf{p},\mathbf{r})-H(\mathbf{p})=\operatorname{KL}(\mathbf{p}\Vert\mathbf{r}) CE ( p , r ) − H ( p ) = KL ( p ∥ r ) . By Jensen’s inequality,
− KL ( p ∥ r ) = ∑ s : p s > 0 p s log ( r s / p s ) ≤ log ∑ s : p s > 0 r s ≤ 0 , -\operatorname{KL}(\mathbf{p}\Vert\mathbf{r})=\sum_{s:p_s>0}p_s\log(r_s/p_s)\le\log\sum_{s:p_s>0}r_s\le0, − KL ( p ∥ r ) = s : p s > 0 ∑ p s log ( r s / p s ) ≤ log s : p s > 0 ∑ r s ≤ 0 ,
with equality if and only if r = p \mathbf{r}=\mathbf{p} r = p [6 Theorem 2.6.3] . Since ∂ s H ( r ) = − log r s − 1 \partial_sH(\mathbf{r})=-\log r_s-1 ∂ s H ( r ) = − log r s − 1 , formula equation 8 gives d s ( r ) = log ( 1 / r s ) d_s(\mathbf{r})=\log(1/r_s) d s ( r ) = log ( 1/ r s ) .
The plug-in composition and the reference. Let O t , s O_{t,s} O t , s be the number of the first t t t audited records verified as s s s , and let q g , t ( s ) q_{g,t}(s) q g , t ( s ) be the predicted share of label s s s among the unaudited records of stratum g g g (the predictions of § 3 ). Before audit t t t ,
p ^ t − 1 , s = 1 N ( O t − 1 , s + ∑ g M g , t q g , t ( s ) ) , r t = ( 1 − η ) p ^ t − 1 + η L , ψ t , s = log 1 r t , s , (15) \hat{p}_{t-1,s}=\frac{1}{N}\left(O_{t-1,s}+\sum_g M_{g,t}q_{g,t}(s)\right),\qquad r_t=(1-\eta)\hat{p}_{t-1}+\frac{\eta}{L},\qquad\psi_{t,s}=\log\frac{1}{r_{t,s}}, \tag*{(15)} p ^ t − 1 , s = N 1 ( O t − 1 , s + g ∑ M g , t q g , t ( s ) ) , r t = ( 1 − η ) p ^ t − 1 + L η , ψ t , s = log r t , s 1 , (15)
with η = 0.01 \eta=0.01 η = 0.01 . Four properties follow:
∑ s p ^ t − 1 , s = 1 \sum_s\hat{p}_{t-1,s}=1 ∑ s p ^ t − 1 , s = 1 , because ∑ s O t − 1 , s = t − 1 \sum_s O_{t-1,s}=t-1 ∑ s O t − 1 , s = t − 1 and ∑ g M g , t = N − t + 1 \sum_g M_{g,t}=N-t+1 ∑ g M g , t = N − t + 1 ;
p ^ t − 1 \hat{p}_{t-1} p ^ t − 1 equals p ⋆ p^\star p ⋆ once every record has been audited;
mixing in the uniform distribution gives η / L ≤ r t , s ≤ 1 \eta/L\le r_{t,s}\le1 η / L ≤ r t , s ≤ 1 , so every contribution ψ t , s \psi_{t,s} ψ t , s lies in [ 0 , log ( L / η ) ] [0,\log(L/\eta)] [ 0 , log ( L / η )] , even for labels not yet seen;
any predictable reference gives a valid upper end, and the choice of r t r_t r t affects only the width, through KL ( p ⋆ ∥ r t ) \operatorname{KL}(p^\star\mathbin{\|}r_t) KL ( p ⋆ ∥ r t ) , which is second order in the error of p ^ t − 1 \hat{p}_{t-1} p ^ t − 1 .
The predicted contribution of stratum g g g is μ ^ g , t = ∑ s q g , t ( s ) ψ t , s \hat{\mu}_{g,t}=\sum_s q_{g,t}(s)\psi_{t,s} μ ^ g , t = ∑ s q g , t ( s ) ψ t , s .
The observations. Audit t t t gives the upper-end observation, which is equation (4) with every row of the contribution matrix equal to ψ t \psi_t ψ t :
Z t U = ∑ s p ^ t − 1 , s ψ t , s + M G t , t N π G t , t ( ψ t , V t − μ ^ G t , t ) . (16) Z_t^U=\sum_s\hat{p}_{t-1,s}\psi_{t,s}+\frac{M_{G_t,t}}{N\pi_{G_t,t}}\left(\psi_{t,V_t}-\hat{\mu}_{G_t,t}\right). \tag*{(16)} Z t U = s ∑ p ^ t − 1 , s ψ t , s + N π G t , t M G t , t ( ψ t , V t − μ ^ G t , t ) . (16)
For a candidate composition p \mathbf{p} p , let p ~ = ( N p + 1 ) / ( N + L ) \tilde{\mathbf{p}}=(N\mathbf{p}+\mathbf{1})/(N+L) p ~ = ( N p + 1 ) / ( N + L ) . The same audit gives the lower-end observation
Z t ( p ) = 1 N ( ∑ i ∈ A t − 1 log 1 p ~ v i + ∑ g M g , t μ ^ g , t ) + M G t , t N π G t , t ( log 1 p ~ V t − μ ^ G t , t ) . (17) Z_t(\mathbf{p})=\frac{1}{N}\left(\sum_{i\in A_{t-1}}\log\frac{1}{\tilde{p}_{v_i}}+\sum_g M_{g,t}\hat{\mu}_{g,t}\right)+\frac{M_{G_t,t}}{N\pi_{G_t,t}}\left(\log\frac{1}{\tilde{p}_{V_t}}-\hat{\mu}_{G_t,t}\right). \tag*{(17)} Z t ( p ) = N 1 i ∈ A t − 1 ∑ log p ~ v i 1 + g ∑ M g , t μ ^ g , t + N π G t , t M G t , t ( log p ~ V t 1 − μ ^ G t , t ) . (17)
This is equation (16) with log ( 1 / p ~ s ) \log(1/\tilde{p}_s) log ( 1/ p ~ s ) in place of ψ t , s \psi_{t,s} ψ t , s . The prediction term μ ^ g , t \hat{\mu}_{g,t} μ ^ g , t is kept the same for every candidate, which is what makes the computation in section G.5 convex. The smoothing keeps every contribution finite, at most log ( N + L ) \log(N+L) log ( N + L ) .
Lemma 6 (One audit, every cross-entropy). If π g , t > 0 \pi_{g,t}>0 π g , t > 0 whenever M g , t > 0 M_{g,t}>0 M g , t > 0 , then E [ Z t U ∣ F t − 1 ] = CE ( p ⋆ , r t ) = H ⋆ + KL ( p ⋆ ∥ r t ) ≥ H ⋆ \mathbb{E}[Z_t^U\mid\mathcal{F}_{t-1}]=\operatorname{CE}(p^\star,r_t)=H^\star+\operatorname{KL}(p^\star\mathbin{\|}r_t)\ge H^\star E [ Z t U ∣ F t − 1 ] = CE ( p ⋆ , r t ) = H ⋆ + KL ( p ⋆ ∥ r t ) ≥ H ⋆ , and E [ Z t ( p ) ∣ F t − 1 ] = CE ( p ⋆ , p ~ ) \mathbb{E}[Z_t(\mathbf{p})\mid\mathcal{F}_{t-1}]=\operatorname{CE}(\mathbf{p}^\star,\tilde{\mathbf{p}}) E [ Z t ( p ) ∣ F t − 1 ] = CE ( p ⋆ , p ~ ) for every composition p \mathbf{p} p .
Proof. Let ϑ ∈ ( 0 , 1 ] L \vartheta\in(0,1]^L ϑ ∈ ( 0 , 1 ] L be predictable, let the μ ^ g , t \hat{\mu}_{g,t} μ ^ g , t be any predictable numbers, and set
Y t = 1 N ( ∑ i ∈ A t − 1 log 1 ϑ v i + ∑ g M g , t μ ^ g , t ) + M G t , t N π G t , t ( log 1 ϑ V t − μ ^ G t , t ) . Y_t=\frac{1}{N}\left(\sum_{i\in A_{t-1}}\log\frac{1}{\vartheta_{v_i}}+\sum_g M_{g,t}\hat{\mu}_{g,t}\right)+\frac{M_{G_t,t}}{N\pi_{G_t,t}}\left(\log\frac{1}{\vartheta_{V_t}}-\hat{\mu}_{G_t,t}\right). Y t = N 1 i ∈ A t − 1 ∑ log ϑ v i 1 + g ∑ M g , t μ ^ g , t + N π G t , t M G t , t ( log ϑ V t 1 − μ ^ G t , t ) .
Given F t − 1 \mathcal{F}_{t-1} F t − 1 and G t = g G_t=g G t = g , the audited record is uniform over the M g , t M_{g,t} M g , t unaudited records of g g g . Averaging over G t G_t G t cancels π g , t \pi_{g,t} π g , t exactly as in the proof of theorem 1, and the μ ^ \hat{\mu} μ ^ terms cancel. So E [ Y t ∣ F t − 1 ] = N − 1 ∑ i = 1 N log ( 1 / ϑ v i ) = CE ( p ⋆ , ϑ ) \mathbb{E}[Y_t\mid\mathcal{F}_{t-1}]=N^{-1}\sum_{i=1}^N\log(1/\vartheta_{v_i})=\operatorname{CE}(p^\star,\vartheta) E [ Y t ∣ F t − 1 ] = N − 1 ∑ i = 1 N log ( 1/ ϑ v i ) = CE ( p ⋆ , ϑ ) . The argument uses only that μ ^ g , t \hat{\mu}_{g,t} μ ^ g , t is predictable.
With ϑ = r t \vartheta=r_t ϑ = r t we get Y t = Z t U Y_t=Z_t^U Y t = Z t U , because equation (15) gives
1 N ( ∑ i ∈ A t − 1 ψ t , v i + ∑ g M g , t μ ^ g , t ) = ∑ s p ^ t − 1 , s ψ t , s . \frac{1}{N}\left(\sum_{i\in A_{t-1}}\psi_{t,v_i}+\sum_g M_{g,t}\hat{\mu}_{g,t}\right)=\sum_s\hat{p}_{t-1,s}\psi_{t,s}. N 1 i ∈ A t − 1 ∑ ψ t , v i + g ∑ M g , t μ ^ g , t = s ∑ p ^ t − 1 , s ψ t , s .
With ϑ = p ~ \vartheta=\tilde{\mathbf{p}} ϑ = p ~ we get Y t = Z t ( p ) Y_t=Z_t(\mathbf{p}) Y t = Z t ( p ) .
The upper end
For each candidate value h h h , the upper-end e-process is
E t U ( h ) = ∏ i ≤ t { 1 − λ i U ( Z i U − h ) } , E_t^U(h)=\prod_{i\le t}\{1-\lambda_i^U(Z_i^U-h)\}, E t U ( h ) = i ≤ t ∏ { 1 − λ i U ( Z i U − h )} ,
the downward e-process of § 3 applied to equation (16) . The stake λ i U ≥ 0 \lambda_i^U\ge0 λ i U ≥ 0 is predictable and does not depend on h h h . Range and cap. Before audit t t t , everything in equation (16) is known except the stratum drawn and the label revealed. The stratum can be any g g g with M g , t > 0 M_{g,t}>0 M g , t > 0 , and the label can be any label in L \mathcal{L} L , including one not yet seen. So the largest possible value is
Z ‾ t U = ∑ s p ^ t − 1 , s ψ t , s + max g : M g , t > 0 M g , t N π g , t ( max s ψ t , s − μ ^ g , t ) . (18) \overline{Z}^{U}_{t}=\sum_s\widehat{p}_{t-1,s}\psi_{t,s}+\max_{g:M_{g,t}>0}\frac{M_{g,t}}{N\pi_{g,t}}\left(\max_s\psi_{t,s}-\widehat{\mu}_{g,t}\right). \tag*{(18)} Z t U = s ∑ p t − 1 , s ψ t , s + g : M g , t > 0 max N π g , t M g , t ( s max ψ t , s − μ g , t ) . (18)
Let h t min h_t^{\min} h t m i n be the smallest candidate tested at audit t t t : 0 0 0 in the basic version and last lower endpoint L t − 1 L_{t-1} L t − 1 with cross-capping (theorem 10). We require
0 ≤ λ t U ≤ 0.9 Z ‾ t U − h t min , (19) 0\leq\lambda_t^U\leq\frac{0.9}{\overline{Z}_t^U-h_t^{\min}}, \tag*{(19)} 0 ≤ λ t U ≤ Z t U − h t m i n 0.9 , (19)
dropping the cap when its denominator is nonpositive.
Proposition 7 (Upper confidence sequence). Let U t U_t U t be the smallest h ≥ h t min h\geq h_t^{\min} h ≥ h t m i n with E s U ( h ) ≥ 1 / α + E_s^U(h)\geq1/\alpha_+ E s U ( h ) ≥ 1/ α + for some s ≤ t s\leq t s ≤ t , or U t = log L U_t=\log L U t = log L if there is none, with h t min = 0 h_t^{\min}=0 h t m i n = 0 . Then Pr { H ⋆ ≤ U t ∀ t } ≥ 1 − α + \Pr\{H^\star\leq U_t\ \forall t\}\geq1-\alpha_+ Pr { H ⋆ ≤ U t ∀ t } ≥ 1 − α + for every labeling.
Proof. Positivity. For h ≥ h i min h\geq h_i^{\min} h ≥ h i m i n , the cap equation (19) gives 1 − λ i U ( Z i U − h ) ≥ 1 − λ i U ( Z ‾ i U − h i min ) ≥ 0.1 1-\lambda_i^U(Z_i^U-h)\geq1-\lambda_i^U(\overline{Z}_i^U-h_i^{\min})\geq0.1 1 − λ i U ( Z i U − h ) ≥ 1 − λ i U ( Z i U − h i m i n ) ≥ 0.1 .
Supermartingale. At h = H ⋆ ≥ 0 h=H^\star\geq0 h = H ⋆ ≥ 0 , theorem 6 gives each factor conditional mean 1 − λ i U KL ( p ⋆ ∥ r i ) ≤ 1 1-\lambda_i^U\operatorname{KL}(p^\star\mathbin{\|}r_i)\leq1 1 − λ i U KL ( p ⋆ ∥ r i ) ≤ 1 . So E t U ( H ⋆ ) E_t^U(H^\star) E t U ( H ⋆ ) is a nonnegative supermartingale starting at one. By Ville’s inequality (theorem 4) it ever reaches 1 / α + 1/\alpha_+ 1/ α + with probability at most α + \alpha_+ α + .
Monotonicity. Each factor is positive and nondecreasing in h ≥ 0 h\geq0 h ≥ 0 . So if some h < H ⋆ h<H^\star h < H ⋆ were ruled out at audit s s s , then E s U ( H ⋆ ) ≥ E s U ( h ) ≥ 1 / α + E_s^U(H^\star)\geq E_s^U(h)\geq1/\alpha_+ E s U ( H ⋆ ) ≥ E s U ( h ) ≥ 1/ α + .
Start. log L ≥ H ( p ) \log L\geq H(\mathbf{p}) log L ≥ H ( p ) for every composition p \mathbf{p} p .
The lower end
Smoothing. For any composition p \mathbf{p} p , 1 / ( N + L ) ≤ p ~ s ≤ 1 1/(N+L)\leq\widetilde{p}_s\leq1 1/ ( N + L ) ≤ p s ≤ 1 . At the truth:
if p s ⋆ > 0 p_s^\star>0 p s ⋆ > 0 , then p ~ s ⋆ ≥ p s ⋆ / ( 1 + L / N ) \widetilde{p}_s^\star\geq p_s^\star/(1+L/N) p s ⋆ ≥ p s ⋆ / ( 1 + L / N ) , so log ( 1 / p ~ s ⋆ ) ≤ log ( 1 / p s ⋆ ) + c \log(1/\widetilde{p}_s^\star)\leq\log(1/p_s^\star)+c log ( 1/ p s ⋆ ) ≤ log ( 1/ p s ⋆ ) + c with c = log ( 1 + L / N ) c=\log(1+L/N) c = log ( 1 + L / N ) ;
if p s ⋆ = 0 p_s^\star=0 p s ⋆ = 0 , no record is verified as s s s , so label s s s never enters Z t ( p ) Z_t(\mathbf{p}) Z t ( p ) .
By theorem 6,
E [ Z t ( p ⋆ ) ∣ F t − 1 ] ≤ H ⋆ + c . (20) \mathbb{E}\left[Z_t(\mathbf{p}^\star)\mid\mathcal{F}_{t-1}\right]\leq H^\star+c. \tag*{(20)} E [ Z t ( p ⋆ ) ∣ F t − 1 ] ≤ H ⋆ + c . (20)
On the Kenyan data, c = log ( 1 + 50 / 33,403 ) = 0.0015 c=\log(1+50/33{,}403)=0.0015 c = log ( 1 + 50/33 , 403 ) = 0.0015 nats.
Candidates. Every audited record verified as s s s belongs to p s ⋆ p_s^\star p s ⋆ , so p ⋆ ∈ P t = { p ∈ Δ L − 1 : p s ≥ O t , s / N } \mathbf{p}^\star\in\mathcal{P}_t=\{\mathbf{p}\in\Delta^{L-1}:p_s\geq O_{t,s}/N\} p ⋆ ∈ P t = { p ∈ Δ L − 1 : p s ≥ O t , s / N } for every t t t , whatever happens in the audit.
The e-processes and the lower end. With a predictable stake λ i L ≥ 0 \lambda_i^L\geq0 λ i L ≥ 0 shared by all candidates and all h h h , let
E t L ( p ; h ) = ∏ i ≤ t { 1 + λ i L ( Z i ( p ) − h − c ) } , F t ( p ; h ) = log E t L ( p ; h ) . E_t^L(\mathbf{p};h)=\prod_{i\leq t}\left\{1+\lambda_i^L\left(Z_i(\mathbf{p})-h-c\right)\right\},\qquad F_t(\mathbf{p};h)=\log E_t^L(\mathbf{p};h). E t L ( p ; h ) = i ≤ t ∏ { 1 + λ i L ( Z i ( p ) − h − c ) } , F t ( p ; h ) = log E t L ( p ; h ) .
At audit t t t , a value h h h is ruled out if min p ∈ P t F t ( p ; h ) ≥ log ( 1 / α − ) \min_{\mathbf{p}\in\mathcal{P}_t}F_t(\mathbf{p};h)\geq\log(1/\alpha_-) min p ∈ P t F t ( p ; h ) ≥ log ( 1/ α − ) , or if a certified lower bound on this minimum is (section G.5). The lower end L t L_t L t is the largest value ruled out so far, and L 0 = 0 L_0=0 L 0 = 0 .
How Z i ( p ) Z_i(\mathbf{p}) Z i ( p ) depends on p \mathbf{p} p . Collecting terms in equation (17) ,
Z i ( p ) = ∑ s χ i , s log 1 p ~ s + ϱ i , χ i , s = 1 N ( O i − 1 , s + M G i , i π G i , i 1 { V i = s } ) ≥ 0 , (21) Z_i(\mathbf{p})=\sum_s\chi_{i,s}\log\frac{1}{\widetilde{p}_s}+\varrho_i,\qquad\chi_{i,s}=\frac{1}{N}\left(O_{i-1,s}+\frac{M_{G_i,i}}{\pi_{G_i,i}}\mathbb{1}\{V_i=s\}\right)\geq0, \tag*{(21)} Z i ( p ) = s ∑ χ i , s log p s 1 + ϱ i , χ i , s = N 1 ( O i − 1 , s + π G i , i M G i , i 1 { V i = s } ) ≥ 0 , (21)
where ϱ i = N − 1 ( ∑ g M g , i μ ^ g , i − M G i , i μ ^ G i , i / π G i , i ) \varrho_i=N^{-1}\left(\sum_gM_{g,i}\widehat{\mu}_{g,i}-M_{G_i,i}\widehat{\mu}_{G_i,i}/\pi_{G_i,i}\right) ϱ i = N − 1 ( ∑ g M g , i μ g , i − M G i , i μ G i , i / π G i , i ) does not depend on p \mathbf{p} p , and ∑ s χ i , s = N − 1 ( i − 1 + M G i , i / π G i , i ) \sum_s\chi_{i,s}=N^{-1}\left(i-1+M_{G_i,i}/\pi_{G_i,i}\right) ∑ s χ i , s = N − 1 ( i − 1 + M G i , i / π G i , i ) .
The cap. Let h t max h_t^{\max} h t m a x be the largest candidate tested at audit t t t : log L \log L log L in the basic version and last upper endpoint U t − 1 U_{t-1} U t − 1 with cross-capping. We require λ t L ( ∑ s χ t , s − ϱ t + h t max + c ) ≤ 1 \lambda_t^L\left(\sum_s \chi_{t,s}-\varrho_t+h_t^{\max}+c\right)\le1 λ t L ( ∑ s χ t , s − ϱ t + h t m a x + c ) ≤ 1 for every stratum that can be drawn; the label revealed does not affect the left side. Substituting,
λ t L [ t − 1 N + M g , t N π g , t ( 1 + μ ^ g , t ) − 1 N ∑ k M k , t μ ^ k , t + h t max + c ] ≤ 1 for every g with M g , t > 0. (22) \lambda_t^L\left[\frac{t-1}{N}+\frac{M_{g,t}}{N\pi_{g,t}}\left(1+\hat{\mu}_{g,t}\right)-\frac{1}{N}\sum_k M_{k,t}\hat{\mu}_{k,t}+h_t^{\max}+c\right]\le1 \quad\text{for every }g\text{ with }M_{g,t}>0. \tag*{(22)} λ t L [ N t − 1 + N π g , t M g , t ( 1 + μ ^ g , t ) − N 1 k ∑ M k , t μ ^ k , t + h t m a x + c ] ≤ 1 for every g with M g , t > 0. (22)
The π t \pi_t π t -weighted average of these brackets is at least 1 + h t max + c 1+h_t^{\max}+c 1 + h t m a x + c . It grows when a large stratum, or one with a large predicted contribution, is drawn with small probability. Priority-aware sampling does exactly this for large, well-known strata, which is why the allocation in section G.6 includes a floor.
Theorem 8 (Lower confidence sequence). Suppose each λ i L \lambda_i^L λ i L is predictable and satisfies equation 24 with h i max = log L h_i^{\max}=\log L h i m a x = log L . Then Pr { L t ≤ H ⋆ ∀ t } ≥ 1 − α − \Pr\{L_t\le H^\star\ \forall t\}\ge1-\alpha_- Pr { L t ≤ H ⋆ ∀ t } ≥ 1 − α − for every labeling. Together with theorem 7, the interval [ L t , U t ] [L_t,U_t] [ L t , U t ] satisfies equation 16.
Proof. Fix i i i , h ≤ log L h\le\log L h ≤ log L and a composition p p p . Write χ s = χ i , s \chi_s=\chi_{i,s} χ s = χ i , s , λ = λ i L \lambda=\lambda_i^L λ = λ i L , ς = 1 + λ ( ϱ i − h − c ) \varsigma=1+\lambda(\varrho_i-h-c) ς = 1 + λ ( ϱ i − h − c ) and J ( p ) = ∑ s χ s log ( 1 / p ~ s ) ≥ 0 J(p)=\sum_s\chi_s\log(1/\tilde{p}_s)\ge0 J ( p ) = ∑ s χ s log ( 1/ p ~ s ) ≥ 0 , so that the factor is ς + λ J ( p ) \varsigma+\lambda J(p) ς + λ J ( p ) .
Positivity. By equation 24, ς ≥ λ ∑ s χ s > 0 \varsigma\ge\lambda\sum_s\chi_s>0 ς ≥ λ ∑ s χ s > 0 when λ > 0 \lambda>0 λ > 0 , so every factor is positive.
Monotonicity. Each factor decreases in h h h , and the stake does not depend on h h h . So F t ( p ; h ) F_t(p;h) F t ( p ; h ) is nonincreasing in h ≤ log L h\le\log L h ≤ log L .
Validity. By equation 22, at p = p ⋆ p=p^\star p = p ⋆ and h = H ⋆ h=H^\star h = H ⋆ every factor has conditional mean at most one. So E t L ( p ⋆ ; H ⋆ ) E_t^L(p^\star;H^\star) E t L ( p ⋆ ; H ⋆ ) is a nonnegative supermartingale starting at one, and by theorem 4 it ever reaches 1 / α − 1/\alpha_- 1/ α − with probability at most α − \alpha_- α − .
Suppose L t > H ⋆ L_t>H^\star L t > H ⋆ . Then some h ∈ ( H ⋆ , log L ] h\in(H^\star,\log L] h ∈ ( H ⋆ , log L ] was ruled out at some audit s ≤ t s\le t s ≤ t , by a statistic no larger than min p ∈ P s F s ( ⋅ ; h ) \min_{p\in\mathcal{P}_s}F_s(\cdot;h) min p ∈ P s F s ( ⋅ ; h ) . Since p ⋆ ∈ P s p^\star\in\mathcal{P}_s p ⋆ ∈ P s and F s F_s F s is nonincreasing in h h h , log ( 1 / α − ) ≤ F s ( p ⋆ ; h ) ≤ F s ( p ⋆ ; H ⋆ ) \log(1/\alpha_-)\le F_s(p^\star;h)\le F_s(p^\star;H^\star) log ( 1/ α − ) ≤ F s ( p ⋆ ; h ) ≤ F s ( p ⋆ ; H ⋆ ) . This has probability at most α − \alpha_- α − .
Two sides. A union bound with theorem 7 gives equation 16.
Computing the lower end: the convex profile
Ruling out h h h requires the minimum of F t ( ⋅ ; h ) F_t(\cdot;h) F t ( ⋅ ; h ) over P t \mathcal{P}_t P t . The cap that keeps the factors positive also makes this a convex problem.
Proposition 9 (Convex profile). Under equation 24, p ↦ F t ( p ; h ) p\mapsto F_t(p;h) p ↦ F t ( p ; h ) is convex on Δ L − 1 \Delta^{L-1} Δ L − 1 for every h ≤ h t max h\le h_t^{\max} h ≤ h t m a x . For any trial point p ∘ ∈ P t p^\circ\in\mathcal{P}_t p ∘ ∈ P t , the value F ‾ t ( h ) \underline{F}_t(h) F t ( h ) in equation 25 is a lower bound on min p ∈ P t F t ( ⋅ ; h ) \min_{p\in\mathcal{P}_t}F_t(\cdot;h) min p ∈ P t F t ( ⋅ ; h ) . Using it in place of the minimum preserves theorem 8.
Proof. Keep the notation of the previous proof and let υ s ( p ) = N / ( N p s + 1 ) \upsilon_s(p)=N/(Np_s+1) υ s ( p ) = N / ( N p s + 1 ) . The derivatives of log ( 1 / p ~ s ) \log(1/\tilde{p}_s) log ( 1/ p ~ s ) in p s p_s p s are − υ s -\upsilon_s − υ s and υ s 2 \upsilon_s^2 υ s 2 , with no cross terms. For ζ ( p ) = log { ς + λ J ( p ) } \zeta(p)=\log\{\varsigma+\lambda J(p)\} ζ ( p ) = log { ς + λ J ( p )} and any direction y \mathbf{y} y ,
y T ∇ 2 ζ y = λ ∑ s χ s υ s 2 y s 2 ς + λ J − λ 2 ( ∑ s χ s υ s y s ) 2 ( ς + λ J ) 2 . \mathbf{y}^{\mathsf{T}}\nabla^2\zeta\,\mathbf{y}=\frac{\lambda\sum_s\chi_s\upsilon_s^2y_s^2}{\varsigma+\lambda J}-\frac{\lambda^2\left(\sum_s\chi_s\upsilon_sy_s\right)^2}{(\varsigma+\lambda J)^2}. y T ∇ 2 ζ y = ς + λ J λ ∑ s χ s υ s 2 y s 2 − ( ς + λ J ) 2 λ 2 ( ∑ s χ s υ s y s ) 2 .
By Cauchy–Schwarz, ( ∑ s χ s υ s y s ) 2 ≤ ( ∑ s χ s ) ( ∑ s χ s υ s 2 y s 2 ) \left(\sum_s\chi_s\upsilon_sy_s\right)^2\le\left(\sum_s\chi_s\right)\left(\sum_s\chi_s\upsilon_s^2y_s^2\right) ( ∑ s χ s υ s y s ) 2 ≤ ( ∑ s χ s ) ( ∑ s χ s υ s 2 y s 2 ) . So this is nonnegative whenever ς + λ J ≥ λ ∑ s χ s \varsigma+\lambda J\ge\lambda\sum_s\chi_s ς + λ J ≥ λ ∑ s χ s . Summing over i i i preserves convexity.
The lower bound is the supporting-plane inequality below. The proof of theorem 8 never uses how the minimum was computed.
The supporting-plane bound. For a convex differentiable function, F ( p ) ≥ F ( p ∘ ) + ∇ F ( p ∘ ) T ( p − p ∘ ) F(p)\ge F(p^\circ)+\nabla F(p^\circ)^{\mathsf{T}}(p-p^\circ) F ( p ) ≥ F ( p ∘ ) + ∇ F ( p ∘ ) T ( p − p ∘ ) [5 ] . Over P t \mathcal{P}_t P t , the linear part is smallest with every coordinate at its lower limit O t , s / N O_{t,s}/N O t , s / N and the free mass 1 − t / N 1-t/N 1 − t / N on the label with the smallest gradient coordinate. Writing ∇ = ∇ F t ( p ∘ ; h ) \nabla=\nabla F_t(p^\circ;h) ∇ = ∇ F t ( p ∘ ; h ) ,
F ‾ t ( h ) = F t ( p ∘ ; h ) − ∇ T p ∘ + 1 N ∑ s ∇ s O t , s + ( 1 − t N ) min s ∇ s ≤ min p ∈ P t F t ( p ; h ) , (23) \underline{F}_t(h)=F_t(p^\circ;h)-\nabla^{\mathsf{T}}p^\circ+\frac{1}{N}\sum_s\nabla_sO_{t,s}+\left(1-\frac{t}{N}\right)\min_s\nabla_s\le\min_{p\in\mathcal{P}_t}F_t(p;h), \tag*{(23)} F t ( h ) = F t ( p ∘ ; h ) − ∇ T p ∘ + N 1 s ∑ ∇ s O t , s + ( 1 − N t ) s min ∇ s ≤ p ∈ P t min F t ( p ; h ) , (23)
where
∂ s F t ( p ; h ) = − ∑ i ≤ t λ i L χ i , s υ s ( p ) 1 + λ i L { Z i ( p ) − h − c } . \partial_sF_t(\mathbf{p};h)=-\sum_{i\le t}\frac{\lambda_i^L\chi_{i,s}\upsilon_s(\mathbf{p})}{1+\lambda_i^L\{Z_i(\mathbf{p})-h-c\}}. ∂ s F t ( p ; h ) = − i ≤ t ∑ 1 + λ i L { Z i ( p ) − h − c } λ i L χ i , s υ s ( p ) .
In practice. We take p ∘ p^\circ p ∘ from projected gradient descent on P t \mathcal{P}_t P t , with at most 60 iterations, and rule out h h h when F t ( h ) ≥ log ( 1 / α − ) F_t(h) \ge\log(1/\alpha_-) F t ( h ) ≥ log ( 1/ α − ) . The gap F t ( p ∘ ; h ) − F t ( h ) F_t(p^\circ;h)-F_t(h) F t ( p ∘ ; h ) − F t ( h ) is lost evidence, not lost validity, so an inexact optimizer can only widen the interval.
If several stake sequences each satisfy equation (22) , the logarithm of their weighted average, log ∑ j w j exp F t ( j ) \log\sum_j w_j \exp F_t^{(j)} log ∑ j w j exp F t ( j ) with w j ≥ 0 w_j \ge0 w j ≥ 0 and ∑ j w j = 1 \sum_j w_j=1 ∑ j w j = 1 , is again convex in p \mathbf{p} p and nonincreasing in h h h . This holds because log-sum-exp is convex and increasing in each argument. Mixtures of stake scales are therefore allowed.
Allocation and cross-capped stakes
Allocation. Strata are submitted label × \times × camera station (300 strata). In our experiment, PAS draws stratum g g g with probability
π g , t = 0.4 M g , t ∑ k M k , t + 0.3 M g , t ( 1 + μ ^ g , t ) ∑ k M k , t ( 1 + μ ^ k , t ) + 0.3 M g , t σ ^ g , t ∑ k M k , t σ ^ k , t , σ ^ g , t 2 = ∑ s q g , t ( s ) ( ψ t , s − μ ^ g , t ) 2 . (24) \pi_{g,t}=0.4\frac{M_{g,t}}{\sum_k M_{k,t}}+0.3\frac{M_{g,t}(1+\hat{\mu}_{g,t})}{\sum_k M_{k,t}(1+\hat{\mu}_{k,t})}+0.3\frac{M_{g,t}\hat{\sigma}_{g,t}}{\sum_k M_{k,t}\hat{\sigma}_{k,t}},\qquad\hat{\sigma}_{g,t}^{2}=\sum_s q_{g,t}(s)(\psi_{t,s}-\hat{\mu}_{g,t})^{2}. \tag*{(24)} π g , t = 0.4 ∑ k M k , t M g , t + 0.3 ∑ k M k , t ( 1 + μ ^ k , t ) M g , t ( 1 + μ ^ g , t ) + 0.3 ∑ k M k , t σ ^ k , t M g , t σ ^ g , t , σ ^ g , t 2 = s ∑ q g , t ( s ) ( ψ t , s − μ ^ g , t ) 2 . (24)
The priority. The last term is the priority of theorem 3 applied to the influence ψ t \psi_t ψ t .
The floor. The middle term implies M g , t ( 1 + μ ^ g , t ) / π g , t ≤ ∑ k M k , t ( 1 + μ ^ k , t ) / 0.3 M_{g,t}(1+\hat{\mu}_{g,t})/\pi_{g,t}\leq\sum_k M_{k,t}(1+\hat{\mu}_{k,t})/0.3 M g , t ( 1 + μ ^ g , t ) / π g , t ≤ ∑ k M k , t ( 1 + μ ^ k , t ) /0.3 for every g g g , which bounds the stratum-dependent term of equation (22) .
The baseline. SRS sets π g , t = M g , t / ∑ k M k , t \pi_{g,t}=M_{g,t}/\sum_k M_{k,t} π g , t = M g , t / ∑ k M k , t .
Every nonempty stratum has positive probability, so theorem 1 applies.
Proposition 10. Run both ends on the same audits with h t min = L t − 1 h_t^{\min}=L_{t-1} h t m i n = L t − 1 in equation (19) and h t max = U t − 1 h_t^{\max}=U_{t-1} h t m a x = U t − 1 in equation (22) , testing only candidates in [ L t − 1 , U t − 1 ] [L_{t-1},U_{t-1}] [ L t − 1 , U t − 1 ] . Then equation (14) holds.
Proof. The endpoints only move inward, and they start at 0 ≤ H ⋆ ≤ log L 0\leq H^\star\leq\log L 0 ≤ H ⋆ ≤ log L . Let t 0 t_0 t 0 be the first audit after which H ⋆ ∉ [ L t 0 , U t 0 ] H^\star\notin[L_{t_0},U_{t_0}] H ⋆ ∈ / [ L t 0 , U t 0 ] . The modified stakes
λ i U = λ i 1 { H ⋆ ≥ L i − 1 } , λ i L = λ i 1 { H ⋆ ≤ U i − 1 } \lambda_i^{U}=\lambda_i\mathbf{1}\{H^\star\geq L_{i-1}\},\qquad\lambda_i^{L}=\lambda_i\mathbf{1}\{H^\star\leq U_{i-1}\} λ i U = λ i 1 { H ⋆ ≥ L i − 1 } , λ i L = λ i 1 { H ⋆ ≤ U i − 1 }
are predictable, since H ⋆ H^\star H ⋆ is a fixed number. With them, the factors at the truth are positive and have conditional mean at most one, so both modified processes are nonnegative supermartingales. They reach 1 / α + 1/\alpha_+ 1/ α + and 1 / α − 1/\alpha_- 1/ α − with probabilities at most α + \alpha_+ α + and α − \alpha_- α − .
For i ≤ t 0 i\leq t_0 i ≤ t 0 , H ⋆ ∈ [ L i − 1 , U i − 1 ] H^\star\in[L_{i-1},U_{i-1}] H ⋆ ∈ [ L i − 1 , U i − 1 ] , so the modified stakes equal the actual ones up to audit t 0 t_0 t 0 . A failure at t 0 t_0 t 0 is one of two events:
some h ∈ [ L t 0 − 1 , H ⋆ ) h\in[L_{t_0-1},H^\star) h ∈ [ L t 0 − 1 , H ⋆ ) has E t 0 U ( h ) ≥ 1 / α + E_{t_0}^{U}(h)\geq1/\alpha_+ E t 0 U ( h ) ≥ 1/ α + , which forces E t 0 U ( H ⋆ ) ≥ 1 / α + E_{t_0}^{U}(H^\star)\geq1/\alpha_+ E t 0 U ( H ⋆ ) ≥ 1/ α + ;
some h ∈ ( H ⋆ , U t 0 − 1 ] h\in(H^\star,U_{t_0-1}] h ∈ ( H ⋆ , U t 0 − 1 ] is ruled out by the lower end, which forces F t 0 ( p ⋆ ; H ⋆ ) ≥ log ( 1 / α − ) F_{t_0}(\mathbf{p}^\star;H^\star)\geq\log(1/\alpha_-) F t 0 ( p ⋆ ; H ⋆ ) ≥ log ( 1/ α − ) .
Either is a crossing of a modified process, and a union bound finishes the proof.
The proof uses only that the ceiling h t max h_t^{\max} h t m a x is predictable and never increases, not that it is an upper confidence bound. So a one-sided lower bound can use any such ceiling, for example one set near the current plug-in entropy.
Scores beyond the biodiversity pillars
Ratios. Recall and the F1 score are both ratios of two linear scores. For each submitted label r r r and verified label s s s , let U r s U_{rs} U r s be the contribution of one such record to the numerator and W r s W_{rs} W r s its contribution to the denominator. Since C r s ⋆ C_{rs}^\star C r s ⋆ is the number of records with that label pair, the score is
ρ ⋆ = ∑ r , s U r s C r s ⋆ ∑ r , s W r s C r s ⋆ , \rho^\star=\frac{\sum_{r,s}U_{rs}C_{rs}^\star}{\sum_{r,s}W_{rs}C_{rs}^\star}, ρ ⋆ = ∑ r , s W r s C r s ⋆ ∑ r , s U r s C r s ⋆ ,
where we assume the denominator is positive. For a candidate ratio ρ \rho ρ , let D r s = U r s − ρ W r s D_{rs}=U_{rs}-\rho W_{rs} D r s = U r s − ρ W r s . Then ρ ⋆ = ρ \rho^\star=\rho ρ ⋆ = ρ exactly when the linear score N − 1 ∑ r , s D r s C r s ⋆ N^{-1}\sum_{r,s}D_{rs}C^\star_{rs} N − 1 ∑ r , s D r s C r s ⋆ equals zero. The entries of D D D may be negative, but the proof of Theorem 2 applies unchanged: their known range gives predictable bounds on Z t Z_t Z t , so we can choose the stakes to keep both betting factors nonnegative. We therefore use the two e-processes in (6) at m = 0 m=0 m = 0 , one for detecting a positive score and the other for detecting a negative score. At each audit, we retain every ρ \rho ρ for which neither process has reached 2 / α 2/\alpha 2/ α . The retained values form a 1 − α 1-\alpha 1 − α confidence sequence for ρ ⋆ \rho^\star ρ ⋆ .
Bounded curvature. If ∇ 2 g \nabla^2g ∇ 2 g is bounded by γ g \gamma_g γ g on the relevant region, then g ( p ⋆ ) = g ( r ) + ∇ g ( r ) ⊤ ( p ⋆ − r ) + R g(p^\star)=g(r)+\nabla g(r)^\top(p^\star-r)+R g ( p ⋆ ) = g ( r ) + ∇ g ( r ) ⊤ ( p ⋆ − r ) + R with ∣ R ∣ ≤ γ g 2 ∥ p ⋆ − r ∥ 2 \lvert R\rvert\leq\frac{\gamma_g}{2}\lVert p^\star-r\rVert^2 ∣ R ∣ ≤ 2 γ g ∥ p ⋆ − r ∥ 2 ; a linear confidence sequence for the first-order term and a composition region for the remainder, at a separate budget, certify g g g . Shannon entropy is not of this type, because ∂ 2 H / ∂ p s 2 = − 1 / p s \partial^2H/\partial p_s^2=-1/p_s ∂ 2 H / ∂ p s 2 = − 1/ p s is unbounded near zero.
Support-based scores. Richness changes by one when a single record reveals a new species. If a procedure declares an eligible species absent after T T T reviews and errs with probability at most α \alpha α under every alternative in which one record carries it, then E [ T ] ≥ ( 1 − α ) N \mathbb{E}[T]\geq(1-\alpha)N E [ T ] ≥ ( 1 − α ) N : couple with each single-record alternative, which agrees until that record is reviewed, and sum over records. Presence, by contrast, is certified by one verified record.