Efficient Active Auditing of Multi-Group Fairness with Bias Probes

Ayoub Ajarra; Debabrota Basu

cs.LGSep 30, 2026

Efficient Active Auditing of Multi-Group Fairness with Bias Probes

Authors: Ayoub Ajarra, Debabrota Basu

Organizations: ´Equipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRIStAL

Abstract

Over the past decade, Machine Learning (ML) has been trained under dual objectives: minimizing prediction error via Empirical Risk Minimization (ERM) while controlling unfairness bias. In practice, however, fairness-aware training often yields limited improvements over standard ERM, making reliable post hoc auditing essential. Existing auditing approaches for black-box models either rely on model reconstruction --exposing systems to extraction attacks-- or directly estimate fairness metrics, offering limited insight into which regions of the data distribution drive bias. More fundamentally, property-specific auditing --aimed at extracting only targeted fairness information without reconstructing the model-- remains poorly understood. In this work, we introduce the bias probe framework, which enables targeted and adaptive querying to reveal bias structure while preserving model confidentiality. Building on this framework, we propose ALeBi, an active auditor that learns such probes to efficiently estimate multi-group fairness metrics. We establish novel sample complexity guarantees governed by a property-specific complexity measure, resolving a previously posed open question, and extend our analysis to adversarial settings where the model owner may strategically obscure bias. Our results uncover a fundamental trade-off between model confidentiality and reliable auditing, and show that property-specific probing enables both accurate estimation and interpretable identification of high and low-bias regions. Extensive experiments support our theoretical findings and demonstrate the practical effectiveness of our approach.

Figures & tables

Figure 1 : Interactive fairness auditing against a fairness-aware adversary.

V_{0}=\mathcal{H}.

Algorithm 1 ReconAudit

\widehat{\mu}_{T}^{(i)}=\frac{1}{T}\sum_{t=1}^{T}\mathbf{M}_{t}^{(i)}.

Algorithm 2 DirectAudit

Figure 2 : Interactive Fairness Auditing via Group-Based Pool Partitioning.

Figure 3 : Interactive Fairness Auditing: Setting and Interaction Protocol

\mathbf{X}^{(t)}=(X_{1}^{(t)},\ldots,X_{k}^{(t)})\sim\nu

Algorithm 3

k

-ALeBi

R\leftarrow\left\lceil\frac{2}{(1-2\beta)^{2}}\log\frac{2N}{\delta}\right\rceil

Algorithm 4 Robust

k

-ALeBi

Probe-CAL

Reconstruction-CAL

Direct

Audit-CAL

Finite-H CAL

Dataset

Groups

Model

Probe error

Fairness error

COMPAS

Linear

0.0004\pm 0.0008

0.0165\pm 0.0108

101.4

0.0003\pm 0.0006

6.1

0.0984\pm 0.0865

0.5

\mathbf{0.0000\pm 0.0000}

237.2

\mathbf{0.0000\pm 0.0000}

187.4

MLP

0.0004\pm 0.0008

0.0178\pm 0.0101

240.3

\mathbf{0.0000\pm 0.0000}

6.8

0.1126\pm 0.0949

0.5

–

0.0000\pm 0.0000

0.0217\pm 0.0144

77.6

\mathbf{0.0000\pm 0.0000}

5.6

0.1282\pm 0.0759

0.5

–

German Credit

Linear

0.0000\pm 0.0000

0.0277\pm 0.0235

260.2

\mathbf{0.0000\pm 0.0000}

2.1

0.2258\pm 0.1148

0.5

\mathbf{0.0000\pm 0.0000}

39.1

\mathbf{0.0000\pm 0.0000}

26.9

MLP

0.0000\pm 0.0000

0.0098\pm 0.0028

661.7

\mathbf{0.0000\pm 0.0000}

2.0

0.1326\pm 0.0571

0.4

–

Table 1 : Clean-audit summary at budget

B=60

and

H=500

. Error entries are mean

\pm

95% CI over five seeds. Runtime is mean audit-only wall-clock time in milliseconds, excluding model fitting, data loading, and plotting. Bold values indicate the best (lowest) value among directly comparable baselines within each dataset–model row; ties are all bolded. Probe error is reported only for Probe-CAL and is therefore not ranked across methods.

Figure 4 : Estimation Error of Multi-group fairness under limitted budget.

Figure 5 : Estimation Error of DiamAudit under Its Applicable Setting

Figure 6 : Feature-wise ranking of probe-derived disparity scores.

Figure 7 : Feature-wise visualization of learned probes on the COMPAS dataset.

Figure 8 : Feature-wise visualization of learned probes on the Student dataset.

Figure 9 : Identity leakage, measured by the number of individual model responses revealed to the auditor, comparing

k

-ALeBi with ReconAudit .

Figure 10 : Model-extraction behavior under

k

-ALeBi and DiamAudit : extraction surrogate fidelity to the target model and the number of absolute labels revealed to the attacker.

Figure 11 : Local CGQ budget of Robust

k

-ALeBi across cells as a function of the attack probability.

Figure 12 : Estimation error for statistical parity as a function of the attack probability.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 13 : General Property-specific Audit Framework.

Figure 14 : 2D of linear classifier counterexample in the active leanring setting: the blue dots $x_{i}$ represent covariates, the dark lines represent classifiers $h_{i}.$

Figure 15 : Illustration of Dasgupta, (2004) counterexample in the context of fairness auditing. Red dots represent samples from the first protected group while green dots represent sampless from the second protected group.

Figure 16 : Bias canvases of $h$ in feature 1 (right) and in feature 2 (left).

Figure 17 : Illustration of the dual star number for the dual class relative to $\mathcal{H}^{\text{lin}}_{\mathbb{R}^{2}}$ .

Figure 18 : Illustration of the dual star number for the dual class relative to $\mathcal{H}^{\text{rec}}_{\mathbb{R}^{2}}$ .

\mathcal{V}\leftarrow\mathcal{V}_{S}.

Appendix

Algorithm 5 Probes Membership-Halving

Explore similar work

Jun 29, 2026cs.AI

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

Fairness Audits Algorithmic Fairness Model Auditing Limited Data

Ask PDF

Jan 6, 2026cs.LG

Audit Me If You Can: Query-Efficient Active Fairness Auditing of Black-Box LLMs

Large Language Models (LLMs) exhibit systematic biases across demographic groups. Auditing is proposed as an accountability tool for black-box LLM applications, but suffers from resource-intensive query access. We conceptualise auditing as uncertainty estimation over a target fairness metric and introduce BAFA, the Bounded Active Fairness Auditor for query-efficient auditing of black-box LLMs. BAFA maintains a version space of surrogate models consistent with queried scores and computes uncertainty intervals for fairness metrics (e.g.,

Δ

AUC) via constrained empirical risk minimisation. Active query selection narrows these intervals to reduce estimation error. We evaluate BAFA on two standard fairness dataset case studies: \textsc{CivilComments} and \textsc{Bias-in-Bios}, comparing against stratified sampling, power sampling, and ablations. BAFA achieves target error thresholds with up to 40

\times

fewer queries than stratified sampling (e.g., 144 vs 5,956 queries at

\varepsilon=0.02

for \textsc{CivilComments}) for tight thresholds, demonstrates substantially better performance over time, and shows lower variance across runs. These results suggest that active sampling can reduce resources needed for independent fairness auditing with LLMs, supporting continuous model evaluations.

David Hartmann, Lena Pohlmann, Lelia Hanslik +3

Weizenbaum Institut Berlin · Technische Universität Berlin · FIZ Karlsruhe +2

Fairness Audits Large Language Model Bias Model Auditing

Ask PDF

Aug 5, 2026cs.LG

Manipulation-Proof Oblivious Audits against Deceptive Model Providers

Audits have emerged as a critical instrument for algorithmic governance, providing a mechanism for external scrutiny and governance of machine learning models. However, ensuring the integrity of such assessments remains a challenging issue. For instance in regulatory contexts, audits are typically declared or easily detected, thus enabling model providers to manipulate the process, whether intentionally or inadvertently. This vulnerability is particularly acute in the context of fairness evaluations, in which providers can often infer sensitive attributes and strategically equalize allocation rates between groups to satisfy fairness metrics. In this paper, we introduce a novel audit protocol designed to significantly increase the post-audit detectability of such manipulations by enabling the auditor to query the model in an oblivious manner. Our approach leverages a Private Information Retrieval mechanism to require the provider to label a large set of instances, while preventing it from knowing which subset will ultimately be used for the audit. The protocol is efficient, imposes minimal overhead on the auditor, and requires no modification to the audited model, its training procedure, or its inference pipeline. We provide theoretical guarantees showing that, under this protocol, a provider attempting to hide unfairness must falsify a significantly larger number of responses, thereby increasing both the difficulty and the likelihood of detection of manipulation. Experimental results across representative audit scenarios confirm the effectiveness and practicality of our approach.

Augustin Godinot, Sofiane Azogagh, Julien Ferry +1

1INRIA Centre de l’Universit´e de Rennes, France · 2EURECOM, Sophia Antipolis, France · 3CIRRELT & SCALE-AI Chair in Data-Driven Supply Chains, Department of Mathematics and Industrial Engineering, Polytechnique Montr´eal, Canada +1

Fairness Audits Model Auditing Algorithmic Fairness Governance

Ask PDF