💻 computer science

Sequential Fairness Auditing with Limited Output Access

This paper proposes a tolerance-aware sequential hypothesis-testing framework that enables independent auditors to efficiently evaluate AI fairness under limited model access by dynamically accumulating evidence from query-based interactions until sufficient support for compliance or violation is reached.

Original authors: Ioannis Pitsiorlas, Martha V. Sourla, Marios Kountouris

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ioannis Pitsiorlas, Martha V. Sourla, Marios Kountouris

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 a food inspector tasked with checking if a new batch of cookies is fair. The rule is simple: the difference in the number of chocolate chips between "Group A" cookies and "Group B" cookies must be very small. If the difference is too big, the cookies are unfair and must be rejected.

However, you have a problem. You don't get to see the recipe, the mixing bowl, or the chef's notes. You can only ask the factory to bake you one cookie at a time, look at it, and then decide whether to keep asking for more or stop. This is what the paper calls "Limited Output Access."

Here is how the authors solve this problem, explained through simple analogies:

1. The Old Way vs. The New Way

The Old Way (Static Testing): Imagine you ask the factory to bake you a huge pile of 4,000 cookies all at once. You count them all, do the math, and then give your verdict. This is slow and wasteful. If the first 50 cookies are clearly unfair, you still have to wait for the whole pile to be baked.

The New Way (Sequential Auditing): The authors propose a smarter approach. You ask for one cookie, look at it, then ask for another. After every few cookies, you do a quick mental check: "Do I have enough evidence to say this is unfair? Or do I have enough to say it's fair? Or do I need to keep eating cookies to be sure?"

If the evidence is strong, you stop immediately.
If the evidence is weak, you keep going.
This saves time and resources because you don't always need to check the whole pile.

2. The "Tolerance" Rule

In the real world, perfection is impossible. The law doesn't demand zero difference in chocolate chips; it allows a tiny margin of error (a "tolerance").

The Paper's Twist: The authors designed their system to understand this. They aren't looking for "Perfectly Equal." They are looking for "Close Enough." If the difference is tiny, the system stops and says, "This is compliant." If it's huge, it stops and says, "This is a violation." If it's right in the middle (the "gray area"), the system keeps asking for more cookies until it's sure, or until it runs out of time.

3. The Three Levels of "Vision"

The paper tests three different ways the inspector might be allowed to look at the cookies. Think of this as the inspector's vision getting sharper:

Level 1: The Blindfold (Decision-Only Access): The inspector only sees the final result: "Chocolate Chip" or "No Chocolate Chip." This is the hardest job. You have to eat a lot of cookies to be sure.
Level 2: The Magnifying Glass (Score Access): The inspector can see a "score" on the cookie, like a number from 0 to 100 indicating how likely it is to have chocolate. This gives more clues, so the inspector needs fewer cookies to make a decision.
Level 3: The X-Ray (Logit Access): The inspector sees the raw, uncooked dough's internal structure before it even becomes a cookie. This is the most information-rich view. The paper found that with this "X-ray" vision, the inspector can often decide on fairness with just a fraction of the cookies needed for the blindfolded approach.

4. The Tricky Part: The "Positive" Cookie Filter

The paper highlights a specific challenge with a fairness rule called Equal Opportunity.

Statistical Parity (SP): You check all cookies.
Equal Opportunity (EO): You are only allowed to check cookies that actually have chocolate chips (the "Positive" ones).
The Problem: If only 10% of the cookies have chocolate chips, your "audit pool" is 10 times smaller. It's like trying to find a needle in a haystack, but you are only allowed to look in a tiny cup of hay. The paper found that even with the "X-ray" vision, auditing this specific rule is much harder and takes longer because there simply aren't enough "positive" cookies to look at.

5. The Big Takeaway

The paper concludes that:

Smarter stopping saves time: You don't need to check every single item if the answer becomes obvious early on.
Better vision helps, but not always: Having more information (scores or logits) usually makes the audit faster and cheaper. However, if the unfairness is very subtle (right on the edge of the legal limit), even the best vision might not give a clear answer quickly.
The rule matters: Auditing some rules (like checking only "positive" outcomes) is inherently harder than others because there is less data to work with.

In short, the authors built a statistical "smart inspector" that knows when to stop asking questions, saves money by not checking everything, and understands that sometimes, even with the best tools, a clear answer takes a long time to find.

Technical Summary: Sequential Fairness Auditing with Limited Output Access

Problem Formulation
External auditors are increasingly tasked with evaluating AI systems for regulatory compliance (e.g., EU AI Act), yet they typically lack access to model parameters, training data, or internal documentation. Instead, they must rely on query-based interactions with deployed systems. Existing fairness evaluation methods predominantly assume static datasets and fixed-sample statistical tests, which are ill-suited for real-world scenarios where evidence must be collected sequentially under strict query budgets.

This work addresses the challenge of auditing fairness under limited output access where the auditor observes only model outputs (decisions, scores, or logits) for selected inputs. The core problem is formulated as a tolerance-aware sequential hypothesis testing problem. Unlike traditional point-null tests, the regulatory context defines compliance relative to a tolerance threshold $\delta$ . The auditor seeks to determine whether a fairness metric $g(f)$ satisfies $g(f) \le \delta$ (compliance) or $g(f) > \delta$ (violation) by accumulating evidence sequentially and stopping as soon as sufficient statistical support is obtained or the query budget is exhausted.

Methodology
The authors propose a Sequential Generalized Likelihood Ratio (GLR) framework designed for finite audit pools and varying levels of model access.

Fairness Metrics and Hypotheses: The framework targets two primary metrics:
- Statistical Parity (SP): $|P(f(X)=1|A=a) - P(f(X)=1|A=b)| \le \delta$ .
- Equal Opportunity (EO): $|P(f(X)=1|Y=1, A=a) - P(f(X)=1|Y=1, A=b)| \le \delta$ .
  The null hypothesis $H_0$ represents compliance ( $g(f) \le \delta$ ), and the alternative $H_1$ represents violation ( $g(f) > \delta$ ).
Access Regimes: The methodology distinguishes between three levels of observability:
- Decision-only (Black-box): The auditor observes binary predictions $\hat{Y} \in \{0,1\}$ . The likelihood model is Bernoulli.
- Score Access (Gray-box): The auditor observes prediction scores $S(x) \in [0,1]$ . The framework treats these as proxy audits using a Gaussian likelihood model for group-conditional score means.
- Logit Access (White-box proxy): The auditor observes pre-sigmoid logits $Z(x)$ . Similar to scores, these are used for proxy audits with a Gaussian likelihood model.
Sequential Procedure:
- The auditor queries a fixed, held-out audit pool (or a filtered sub-pool for EO where $Y=1$ ) in a random order without replacement.
- At each step $t$ , a GLR statistic $\Lambda_t$ is computed based on the accumulated data.
- Stopping Rules: The audit terminates if $\Lambda_t$ crosses an upper boundary $u$ (reject $H_0$ , violation detected) or a lower boundary $\ell$ (accept $H_0$ , compliance certified). If the maximum budget $B$ is reached without crossing a boundary, the outcome is declared inconclusive.
- The boundaries are set using Wald-type approximations ( $u = \log((1-\beta)/\alpha)$ , $\ell = \log(\beta/(1-\alpha))$ ) for nominal error rates $\alpha=0.05$ and $\beta=0.2$ .

Key Contributions

Sequential Formulation: The paper formalizes fairness auditing under limited access as a sequential statistical decision problem with explicit tolerance thresholds, moving beyond static batch evaluation.
GLR Protocol: It develops a sequential GLR testing protocol with operational stopping rules for composite fairness constraints, applicable to both decision-based and proxy (score/logit) audits.
Access-Aware Analysis: The work systematically analyzes how different access regimes (decision-only vs. richer observables) affect audit efficiency, distinguishing between exact decision-based tests and proxy audits.
Empirical Insights: Through experiments on ACS and Adult datasets, the authors identify practical phenomena in sequential auditing, including the impact of metric choice (SP vs. EO) and the statistical ambiguity near regulatory thresholds.

Results
Experiments were conducted on benchmark datasets (ACS and Adult) using various neural network models (base and fairness-constrained). Key findings include:

Impact of Access Regimes: Richer output information significantly reduces the number of queries required for Statistical Parity (SP) audits. For instance, on the ACS dataset, logit access reduced the mean query count by roughly a factor of three compared to decision-only access. However, for Equal Opportunity (EO), the benefits of richer access are not uniform.
Difficulty of EO Audits: EO audits are inherently more sample-intensive than SP audits. This is attributed to the fact that EO operates on a conditional sub-pool ( $Y=1$ ), which is smaller and may have less favorable group compositions for evidence accumulation. In near-threshold cases (e.g., Adult dataset EO), richer access (scores/logits) did not consistently yield faster or more conclusive audits; many runs terminated inconclusively even with high query budgets.
Efficiency vs. Accuracy Trade-off: Sequential auditing dramatically reduces the query cost compared to fixed-sample baselines (e.g., using only ~200 queries vs. 4000 for SP on Adult). However, this efficiency comes with a trade-off: in challenging, near-threshold scenarios, sequential audits may produce more inconclusive outcomes or lower decision accuracy compared to fixed-sample testing that utilizes the full budget.
Boundary Effects: Models with fairness gaps near the regulatory tolerance $\delta$ frequently yield inconclusive outcomes within realistic budgets, highlighting the statistical difficulty of distinguishing compliance from violation in these regimes.

Significance and Claims
The paper claims to provide a practical statistical framework for sequential fairness auditing that reflects realistic deployment constraints where auditors have limited access. It demonstrates that:

Fairness audit outcomes depend not only on the model but also on the statistical protocol and the auditor's level of access.
While richer outputs can substantially improve audit efficiency for certain metrics (like SP), they do not guarantee faster audits for all metrics (like EO), particularly when disparities are close to the tolerance threshold.
The proposed framework operationalizes the concept of "tolerance-aware" auditing, acknowledging that small disparities may be legally permissible, and provides a mechanism to stop data collection once sufficient evidence is gathered.

The authors note limitations, including the focus on binary groups and binary classification, the use of proxy audits for score/logit access (which do not provide exact guarantees for hard-decision constraints), and the use of operational rather than exact finite-sample calibrations for stopping boundaries. They suggest future work could explore multi-group settings, adaptive query strategies, and confidence sequences.