Efficient Active Auditing of Multi-Group Fairness with Bias Probes
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.
Related
- Tolerance-Based Fairness Auditing: Violation Certification and Sensitivity Screening
- Multi-Task Active Learning with Efficient Resource Allocation
- Detectability without Interference: Efficient Canary Design for Privacy Auditing in One Run
- Not All Mislabels Are Equal: Efficient Task-Aware Auditing with Confidence Sequences
- Fairness in multi-class multi-group classification problems via contextial coherent risk measures
BibTeX
@misc{ajarra2026efficient,
title = {{Efficient Active Auditing of Multi-Group Fairness with Bias Probes}},
author = {Ayoub Ajarra and Debabrota Basu},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40034},
eprint = {2609.40034},
archivePrefix = {arXiv},
url = {https://inria.hal.science/hal-05829024v1},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Efficient Active Auditing of Multi-Group Fairness with Bias Probes
AU - Ayoub Ajarra
AU - Debabrota Basu
PY - 2026
DA - 2026/09/30
PB - HAL
DO - 10.48550/arxiv.2609.40034
UR - https://inria.hal.science/hal-05829024v1
AB - 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.
ER -