📊 statistics

Global Sequential Testing for Multi-Stream Auditing

This paper proposes efficient global sequential testing methods for multi-stream auditing that utilize merging martingales to achieve faster stopping times and greater statistical power compared to traditional Bonferroni-based approaches, particularly under dense alternative hypotheses.

Original authors: Beepul Bharti, Ambar Pal, Jeremias Sulam

Published 2026-07-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Beepul Bharti, Ambar Pal, Jeremias Sulam

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the head security guard for a massive, futuristic hospital. This hospital doesn't just have one camera; it has k different streams of data monitoring everything from X-rays to MRI scans and even different patient groups. Your job is to spot a glitch immediately. If the machine starts making mistakes on any single stream, you need to sound the alarm right away.

The big question is: How do you check all these streams at once without wasting time?

The Old Way: The "Max-It-Out" Strategy

Traditionally, security guards used a method called Bonferroni correction. Think of this like a guard who only looks at the single loudest scream in a crowded room. If 250 people are talking, the guard waits until the loudest one yells, but because there are so many people, the guard has to wait for a really loud scream to be sure it's not just a false alarm.

The paper shows that this old method works okay if only one person is screaming (a "sparse" situation). But if many people start screaming at once (a "dense" situation), the old guard is too slow. They are ignoring the fact that 75% of the room is yelling, focusing only on the one loudest voice. The math proves that this method takes a long time to stop, specifically growing with the logarithm of the number of streams ( $O(\ln k/\alpha)$ ).

The New Players: The "Product" and the "Average"

The authors, Beepul Bharti, Ambar Pal, and Jeremias Sulam, decided to try two new strategies using a clever math trick called "merging martingales" (which is just a fancy way of saying "accumulating evidence like betting chips").

The Product Team (The Multiplication Squad): This team multiplies the evidence from every stream together.
- How it works: If everyone is slightly suspicious, multiplying those small suspicions together creates a massive, undeniable mountain of evidence.
- The Catch: If only one person is suspicious and everyone else is quiet, the multiplication gets crushed by the quiet ones. The paper shows that in a "sparse" world (where only a few streams are bad), this team is terrible. It might take forever to stop, or even fail to stop after 1,000 time steps in their simulations.
- The Win: However, when the alternative is "dense" (many streams are bad), this team is a superstar. In their experiments with 75% of streams being bad, they stopped in under 50 time steps, way faster than the old guard.
The Average Team (The Additive Squad): This team adds up the evidence and divides by the number of streams.
- How it works: It's like taking a vote. If one person is screaming, their vote counts, and the team doesn't get drowned out by the quiet ones.
- The Catch: If everyone is screaming, this team is slower than the Product Team because it doesn't get that explosive "multiplication" boost.
- The Win: In "sparse" situations (where only a few streams are bad), this team performs just as well as the old Bonferroni guard.

The Hero: The "Balanced" Test

Here is the paper's main discovery: You don't have to choose.

The authors created a new test called $\phi_{balance}$ . Imagine this as a super-guard who carries a clipboard that is half "Product" and half "Average."

If the hospital is in a "sparse" crisis (only a few bad streams), the Balanced Guard acts like the Average Team, stopping just as fast as the best possible method.
If the hospital is in a "dense" crisis (many bad streams), the Balanced Guard switches to the Product Team's logic, stopping incredibly fast.

The math proves that this Balanced Guard achieves the best of both worlds:

In sparse cases: It stops in $O(\ln k/\alpha)$ time (matching the best).
In dense cases: It stops in $O(1/k \ln 1/\alpha)$ time (much faster than anyone else).

Did They Prove It?

The authors didn't just guess; they ran the numbers.

The Math: They provided rigorous proofs showing exactly how long these tests should take to stop under different conditions.
The Simulations: They ran 1,000 simulations with synthetic data (250 streams).
- When only 5% of streams were bad, the Balanced Guard matched the speed of the Average team, while the Product team failed to stop even after 350 steps.
- When 75% of streams were bad, the Balanced Guard matched the Product team, stopping in under 50 steps, while the Average team was much slower.
The Real World: They tested this on a real medical AI model called ConceptCLIP, which looks at different types of medical images (like lung CTs and retinal scans).
- When the model was biased across many groups (dense), the Product and Balanced tests flagged the error fastest.
- When they tweaked the data to simulate a bias in only one group (sparse), the Average and Balanced tests flagged it fastest.

The Bottom Line

The paper argues that the standard "Bonferroni" method is often too slow because it doesn't adapt to how many streams are actually broken. The Balanced Test is the new champion because it automatically adapts to the situation, whether the problem is isolated to one stream or spread across many, ensuring we catch errors in machine learning systems as quickly as possible without raising false alarms.

Technical Summary: Global Sequential Testing for Multi-Stream Auditing

Problem Formulation
The paper addresses the challenge of continuously auditing machine learning (ML) systems across multiple data streams (e.g., different demographic groups, geographic locations, or imaging modalities). The goal is to detect as soon as possible if the system is performing sub-optimally on any of the $k$ streams. This is formalized as a sequential hypothesis testing problem with a global null hypothesis, $H_{global}^0$ , which asserts that the system operates as intended across all $k$ streams (i.e., the mean of the deviation variable is zero for all streams). The alternative hypothesis, $H_{global}^1$ , posits that at least one stream has a non-zero mean.

The authors focus on the efficiency of these tests, specifically the expected stopping time ( $E[\tau]$ ), which measures how quickly a test can reject the null hypothesis when the alternative is true. The standard approach uses a Bonferroni correction, which tracks the maximum wealth (evidence) across streams and adjusts the significance threshold. While this method guarantees a level- $\alpha$ test, the paper argues it is inefficient in "dense" scenarios where many streams deviate from the null, as it fails to aggregate evidence from multiple streams effectively.

Methodology
The authors utilize the "testing-by-betting" framework, constructing non-negative supermartingales (wealth processes) for each stream. For a single stream $i$ , they employ the Online Newton Step (ONS) algorithm to update betting fractions, ensuring the wealth process grows exponentially under the alternative hypothesis while remaining a martingale under the null.

To test the global null, the paper investigates three strategies for merging evidence from the $k$ individual wealth processes ( $W_i$ ):

Bonferroni ( $\phi_{bonf}$ ): Tracks the maximum wealth, $\max_i W_i$ , with a threshold of $k/\alpha$ .
Product ( $\phi_{prod}$ ): Merges evidence via the product of wealth processes, $W_t^{prod} = \prod_{i=1}^k W_{i,t}$ .
Average ( $\phi_{ave}$ ): Merges evidence via the arithmetic mean, $W_t^{ave} = \frac{1}{k} \sum_{i=1}^k W_{i,t}$ .

The authors derive new theoretical bounds for the expected stopping times of the Product and Average tests under both sparse alternatives (few non-null streams) and dense alternatives (many non-null streams).

Key Contributions and Theoretical Results
The paper provides rigorous stopping time guarantees for merging-based sequential tests, highlighting their complementary strengths:

Product Test ( $\phi_{prod}$ ): In dense regimes (where many streams are non-null), the product test achieves an expected stopping time of $O(\frac{1}{k} \ln \frac{1}{\alpha})$ . This is significantly faster than the Bonferroni rate of $O(\ln k / \alpha)$ . However, in sparse regimes, its performance degrades to $O(k \ln k)$ , making it inefficient when only a few streams are non-null.
Average Test ( $\phi_{ave}$ ): In sparse regimes, the average test matches the Bonferroni rate of $O(\ln k / \alpha)$ . In dense regimes, it improves to $O(\ln 1/\alpha)$ , though it does not achieve the $O(1/k)$ acceleration of the product test.
Balanced Test ( $\phi_{balance}$ ): To address the uncertainty of whether the alternative is sparse or dense, the authors propose a simple balanced test that averages the product and average wealth processes ( $W_t^{balance} = \frac{1}{2}W_t^{ave} + \frac{1}{2}W_t^{prod}$ $W_{t}^{ba l an ce} = \frac{1}{2} W_{t}^{a v e} + \frac{1}{2} W_{t}^{p r o d}$ ).
- Theorem 4.3 establishes that this balanced test achieves the best of both worlds: it attains the $O(\ln k / \alpha)$ rate in sparse regimes and the $O(\frac{1}{k} \ln \frac{1}{\alpha})$ rate in dense regimes, without requiring prior knowledge of the sparsity level.

Experimental Validation
The authors validate their theory using both synthetic and real-world data:

Synthetic Data: Experiments with $k=250$ streams demonstrate that $\phi_{prod}$ fails to reject in sparse settings (1% non-null) but excels in dense settings (75% non-null). Conversely, $\phi_{ave}$ and $\phi_{bonf}$ perform well in sparse settings but are slower in dense ones. The balanced test consistently matches the performance of the best-performing strategy in each regime.
Real-World Data: The methods were applied to audit ConceptCLIP, a medical vision-language model, across 10 groups defined by imaging modalities and anatomical regions.
- In a zero-shot setting (where the model showed bias in most groups), the product and balanced tests rejected the null fastest.
- In a post-processed setting (simulating a sparse alternative where bias existed in only one group), the average and balanced tests rejected fastest, confirming the theoretical adaptability of the balanced approach.

Significance
The paper claims that while the Bonferroni correction is a standard, simple approach for global sequential testing, it is not always efficient, particularly when evidence against the null is distributed across many streams. By leveraging merging martingales via averaging and product rules, the authors demonstrate that it is possible to construct tests with significantly improved stopping times. The primary contribution is the balanced test, which provides a robust solution that adapts to the unknown sparsity of the alternative, offering faster detection of erroneous model behavior in multi-stream auditing scenarios while maintaining strict control over Type-I error.