Global Sequential Testing for Multi-Stream Auditing

Beepul Bharti; Ambar Pal; Jeremias Sulam

stat.MLFeb 25, 2026

Global Sequential Testing for Multi-Stream Auditing

Authors: Beepul Bharti, Ambar Pal, Jeremias Sulam

Organizations: Johns Hopkins University · Amazon Responsible AI

Abstract

Across many risk-sensitive areas, it is critical to continuously audit machine learning systems as we receive more data to quickly determine if they are performing as designed. This auditing task can be modeled as a sequential hypothesis testing problem with $k$ data streams and a global null hypothesis that asserts the system operates as intended across all $k$ streams. Under the alternative, the standard global sequential test, which uses a Bonferroni correction, has an expected stopping time of $O\left(\ln \frac{k}α\right)$ for large $k$ and significance level $α$ . In this work, we demonstrate that efficient sequential tests, relying on merging martingales via averaging and products rules, provide improved stopping times, and thus more powerful tests against the null. Using these results, we show that a balanced test can match the Bonferroni rate of $O\left(\ln \frac{k}α\right)$ in the sparse regime (just a few non-null streams) while achieving $O\left(\frac{1}{k}\ln \frac{1}α\right)$ under dense alternatives (many non-null steams). We validate our theory through experiments on both synthetic and real-world data.

Figures & tables

Test	Alternative
	Sparse $\gamma=1$	Dense $\gamma=k$
Bonferroni $\phi^{\textsf{bonf}}$ ( Proposition 3.1 )	$\ln\nicefrac{{1}}{{\alpha}}+\ln k$	$\ln\nicefrac{{1}}{{\alpha}}+\ln k$
Product $\phi^{\textsf{prod}}$ ( Theorem 4.1 )	$\ln\nicefrac{{1}}{{\alpha}}+k\ln k$	$\nicefrac{{1}}{{k}}\ln\nicefrac{{1}}{{\alpha}}$
Average $\phi^{\textsf{ave}}$ ( Theorem 4.2 )	$\ln\nicefrac{{1}}{{\alpha}}+\ln k$	$\ln\nicefrac{{1}}{{\alpha}}$
Balanced $\phi^{\textsf{balance}}$ ( Theorem 4.3 )	$\ln\nicefrac{{1}}{{\alpha}}+\ln k$	$\nicefrac{{1}}{{k}}\ln\nicefrac{{1}}{{\alpha}}$

Table 1: Comparison of the expected stopping time upper bounds, showing the dominating terms and their dependence on

k

and

\alpha

for large

k

and small

\alpha

Panel of Figure 1 — Figure 1: Top: Distribution of stopping times, over 1,000 simulations, for various sequential tests across settings with varying proportions of streams with nonzero means. A test rejects when its corresponding wealth process exceeds $\nicefrac{{1}}{{\alpha}}$ for $\alpha=0.01$ . The dashed vertical line is the empirical mean of the stopping times. Bottom: Trajectories of various wealth processes across settings with different amounts of nonzero means. Each line represents the median trajectory of a wealth process over 1,000 simulations, with shaded areas indicating the 25% and 75% quantiles. The y-axis is presented on a logarithmic scale. Wealth processes are clipped to $10^{-3}$ for visualization purposes.

Panel of Figure 2 — Figure 2: Left plot of each figure: Distribution of stopping times, over 1,000 runs, for various sequential tests. A test rejects when its corresponding wealth process exceeds $\nicefrac{{1}}{{\alpha}}$ for $\alpha=0.01$ . The dashed vertical line is the empirical mean of the stopping times. Right plot of each figure: Various wealth process trajectories. Each line represents the median trajectory of a wealth process over 1,000 runs, with shaded areas indicating the 25% and 75% quantiles.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

\text{proj}^{H_{j}}_{\|v\|_{1}\leq\nicefrac{{1}}{{2}}}(y)=\underset{\|v\|_{1}\leq\nicefrac{{1}}{{2}}}{\text{argmin}}~\langle H_{j}(v-y),v-y\rangle

Appendix

Algorithm 1 Online Newton Step (ONS)

Panel of Figure 3 — Figure 3: Top: Distribution of stopping times, over 1,000 simulations, for various sequential tests across settings with varying proportions of streams with nonzero means. A test rejects when its corresponding wealth process exceeds $\nicefrac{{1}}{{\alpha}}$ for $\alpha=0.01$ . The dashed vertical line is the empirical mean of the stopping times. Bottom: Trajectories of various wealth processes across settings with different amounts of nonzero means. Each line represents the median trajectory of a wealth process over 1,000 simulations, with shaded areas indicating the 25% and 75% quantiles. The y-axis is presented on a logarithmic scale. Wealth processes are clipped to $10^{-3}$ for visualization purposes.

Panel of Figure 4 — Figure 4: Top: Distribution of stopping times, over 1,000 simulations, for various sequential tests across settings with varying proportions of streams with nonzero means. A test rejects when its corresponding wealth process exceeds $\nicefrac{{1}}{{\alpha}}$ for $\alpha=0.01$ . The dashed vertical line is the empirical mean of the stopping times. Bottom: Trajectories of various wealth processes across settings with different amounts of nonzero means. Each line represents the median trajectory of a wealth process over 1,000 simulations, with shaded areas indicating the 25% and 75% quantiles. The y-axis is presented on a logarithmic scale. Wealth processes are clipped to $10^{-3}$ for visualization purposes.

Group Name	Dataset	Description	Classes
brain CT	Brain Tumor CT	High-resolution CT scans for brain tumor detection.	Healthy Tumor
brain MRI	Brain Tumor MRI	Similar to the Brain Tumor CT dataset but with MRIs.	Healthy Tumor
covid X-ray	Covid-CXR2	16,000 chest X-ray images including 2,300 positive COVID-19 images/	No finding Covid-19
breast mammogram	Breast Cancer	3,383 annotated mammogram images focused on breast tumors.	Normal Tumor
breast ultrasound	UBIBC	Ultrasound images related to breast cancer.	Benign Malignant
colon pathology	LC2500	10,000 pathology images from colon tissues.	Normal Adenocarcinomas

Appendix

Table 2: Additional details about the datasets used in the zero-shot medical classification experiment. The first and second classes listed in the table correspond to

Y=0

and

Y=1

, respectively. Most of the information provided in this table is derived from Nie et al. [19] .

Group	${\mathbb{E}}_{P_{i}}[Z]$
brain CT	$0.31$
brain MRI	$0.07$
covid X-ray	$0.28$
breast mammogram	$-0.19$
breast ultrasound	$-0.07$
colon pathology	$0.09$

Appendix

Table 3:

{\mathbb{E}}_{P_{i}}[Z]

across different groups defined by modality and anatomical region

Explore similar work

Jun 29, 2026

Sequential Fairness Auditing with Limited Output Access

External evaluations are becoming increasingly central to the governance of AI systems. In practice, however, independent auditors often have limited access to deployed models and must rely on query-based interactions. Most existing fairness evaluation methods assume static datasets and fixed-sample statistical tests, making them poorly suited to real-world auditing scenarios in which evidence must be collected sequentially under query constraints. In this work, we formulate fairness auditing as a tolerance-aware sequential hypothesis-testing problem under limited model output access. We develop a sequential generalized likelihood-ratio framework that allows auditors to accumulate evidence from a finite audit pool and stop once sufficient support for compliance or violation has been obtained. The framework is instantiated for decision-based Statistical Parity and Equal Opportunity audits, and extended to score- and logit-based proxy audits when richer observables are available. Our results show that both the fairness metric and the level of model access significantly affect audit efficiency, and that the benefits of richer output information are not uniform across auditing settings. In particular, richer outputs can substantially reduce the number of queries required for some fairness metrics and operating regimes, while offering limited gains in near-threshold cases. This work provides a practical statistical framework for sequential fairness auditing under realistic deployment constraints.

Ioannis Pitsiorlas, Martha V. Sourla, Marios Kountouris

EURECOM, France · DaSCI, University of Granada, Spain

Algorithmic Fairness Group Fairness Sequential Hypothesis Testing Black-Box Model Auditing

Ask PDF

May 7, 2026

Adaptive auditing of AI systems with anytime-valid guarantees

A major bottleneck in characterizing the failure modes of generative AI systems is the cost and time of annotation and evaluation. Consequently, adaptive testing paradigms have gained popularity, where one opportunistically decides which cases and how many to annotate based on past results. While this framework is highly practical, its extreme flexibility makes it difficult to draw statistically rigorous conclusions, as it violates classical assumptions: the number of observations is typically limited (often 10 to 50 cases) and decisions regarding sampling and stopping are made in the midst of data collection rather than based a pre-specified rule. To characterize what statistical inferences can be drawn from highly adaptive audits, we introduce a hypothesis testing framework from two 'dueling' perspectives: (i) the model's null that asserts there is no failure mode with performance below a target threshold versus (ii) the auditor's null that asserts they have a sampling strategy that will uncover a failure mode. Leveraging Safe Anytime-Valid Inference (SAVI), we formalize the auditor as conducting 'testing by betting', which translates into simultaneous e-processes for testing the dueling null hypotheses. Furthermore, if the auditor is sufficiently powerful, we prove that these two hypotheses are asymptotically inverses of each other, in that passage of a stringent audit does in fact certify the AI system as being globally robust. Empirically, we demonstrate that our proposed testing procedures maintain anytime-valid type-I error control, outperform pre-specified testing methods, and can reach statistically rigorous conclusions sometimes with as few as 20 observations.

Siyu Zhou, Patrick Vossler, Venkatesh Sivaraman +2

University of California, San Francisco · Stanford University

Algorithmic Auditing Anytime-Valid Inference Sequential Hypothesis Testing

Ask PDF

Mar 18, 2026

Multi-Armed Sequential Hypothesis Testing by Betting

We consider a variant of sequential testing by betting where, at each time step, the statistician is presented with multiple data sources (arms) and obtains data by choosing one of the arms. We consider the composite global null hypothesis

\mathscr{P}

that all arms are null in a certain sense (e.g. all dosages of a treatment are ineffective) and we are interested in rejecting

\mathscr{P}

in favor of a composite alternative

\mathscr{Q}

where at least one arm is non-null (e.g. there exists an effective treatment dosage). We posit an optimality desideratum that we describe informally as follows: even if several arms are non-null, we seek

e

-processes and sequential tests whose performance are as strong as the ones that have oracle knowledge about which arm generates the most evidence against

\mathscr{P}

. Formally, we generalize notions of log-optimality and expected rejection time optimality to more than one arm, obtaining matching lower and upper bounds for both. A key technical device in this optimality analysis is a modified upper-confidence-bound-like algorithm for unobservable but sufficiently "estimable" rewards. In the design of this algorithm, we derive nonasymptotic concentration inequalities for optimal wealth growth rates in the sense of Kelly [1956]. These may be of independent interest.

Ricardo J. Sandoval, Ian Waudby-Smith, Michael I. Jordan

University of California, Berkeley · École Normale Supérieure & Inria, Paris

Sequential Hypothesis Testing Statistical Hypothesis Testing Multi-Armed Bandits

Ask PDF