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

Sequential Fairness Auditing with Limited Output Access
Jun 29, 2026Ioannis Pitsiorlas, Martha V. Sourla, Marios KountourisAlgorithmic Fairness Group Fairness
EURECOM, France · DaSCI, University of Granada, Spain
Adaptive auditing of AI systems with anytime-valid guarantees
May 7, 2026Siyu Zhou, Patrick Vossler, Venkatesh Sivaraman +2Algorithmic Auditing Anytime-Valid Inference
University of California, San Francisco · Stanford University
Multi-Armed Sequential Hypothesis Testing by Betting
Mar 18, 2026Ricardo J. Sandoval, Ian Waudby-Smith, Michael I. JordanSequential Hypothesis Testing Statistical Hypothesis Testing
University of California, Berkeley · École Normale Supérieure & Inria, Paris

Jun 29, 2026J/K move · Enter open · S save

Sequential Fairness Auditing with Limited Output Access

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Sequential Fairness Auditing with Limited Output Access

Adaptive auditing of AI systems with anytime-valid guarantees

Multi-Armed Sequential Hypothesis Testing by Betting