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

AI summary

Overview

Research area: Fairness auditing of black-box large language models; active learning and query-efficient evaluation; algorithmic fairness measurement.

Technical level: Advanced. The paper assumes familiarity with ROC-AUC, group fairness metrics, constrained optimisation, and version-space reasoning, though the core intuition is accessible.

Scope: This paper introduces BAFA (Bounded Active Fairness Auditor), an active-sampling method that estimates group-wise ROC-AUC disparities in black-box LLMs within a fixed query budget by maintaining bounded surrogate models and querying the points where those bounds disagree most.

What This Paper Is About

Fairness audits of black-box LLM services are expensive because each evaluation requires paid API calls, and comprehensive audits can conflict with data-minimisation obligations such as the GDPR. The authors reframe auditing as uncertainty estimation over a target fairness metric — here the group-wise ROC-AUC difference, Δ_AUC — rather than as one-shot benchmarking or failure discovery. Their goal is to reach a target estimation accuracy with as few black-box queries as possible, so that independent auditors with limited budgets can run continuous fairness evaluations.

Key Contributions

1. Methodological: The authors present BAFA, which they describe as the first active learning approach for black-box LLM fairness auditing that works with threshold-invariant ranking metrics (rather than threshold-dependent classification metrics used in prior active auditing work).

2. Practical: They introduce a query-efficient framework suitable for independent audits under limited access, budget, and regulatory constraints, built around a version space of BERT-based surrogates and constrained empirical risk minimisation.

3. Empirical: They compare active auditing against stratified sampling, power sampling, and two ablations (constrained optimisation with a stratified sample, and Bayesian optimisation without active querying) across two realistic LLM auditing case studies, reporting substantial query-efficiency gains.

4. Conceptual: They argue for treating auditing as uncertainty reduction over a target metric rather than hypothesis testing or failure discovery, and show empirically that BAFA's bound width correlates strongly with the true absolute estimation error.

Main Findings

• Large query savings at tight thresholds: On CivilComments at ε = 0.02, BAFA with disagreement-based selection needed 144 queries on average versus 5,956 for stratified sampling — a reduction of approximately 41×. BAFA with Bayesian optimisation needed 256 queries.

• Savings at looser thresholds are smaller: On CivilComments at ε = 0.05, BAFA required 80 queries (disagreement) and 132 (BO), against 452 for stratified sampling and 932 for power sampling. The authors report reductions of about 5.7× (disagreement) and 3.4× (BO) relative to stratified sampling.

• Second case study also shows gains: On Bias-in-Bios at ε = 0.02, BAFA reached the target in 340 queries (disagreement) and 356 (BO), versus 1,748 for stratified sampling and more than 5,300 for power sampling — roughly 5× and 16× reductions respectively.

• BO ablation can win at loose thresholds: On Bias-in-Bios at ε = 0.05, the BO-only ablation reached the target in 100 queries, beating both BAFA variants (148 and 180), though it needed about 2.3× more queries than BAFA at ε = 0.02.

• Better over-time performance: Measured by area under the error curve (AUEC) over the first 1,000 queries, BAFA with disagreement achieved the lowest mean AUEC on both datasets (0.019 on CivilComments; 0.025 on Bias-in-Bios) compared with stratified sampling (0.066 and 0.042) and power sampling (0.093 and 0.045). The authors report active methods reduce error roughly 3–4× over time on CivilComments.

• Lower variance at mid-budget: At 250 queries on CivilComments, BAFA with disagreement had a mean error of 0.020 [0.015, 0.026], versus 0.064 [0.046, 0.083] for stratified sampling and 0.108 [0.080, 0.135] for power sampling. On Bias-in-Bios at the same budget, BAFA variants achieved 0.022 each, versus 0.065 for power sampling and 0.043 for stratified.

• Versus the C-ERM ablation: The constrained-optimisation-only ablation needed 457 queries on CivilComments at ε = 0.02 and 512 on Bias-in-Bios, more than BAFA but fewer than the sampling baselines. The authors note C-ERM already outperforms both passive baselines.

• Domain mismatch is tolerated: In Case Study B, GPT-4.1-mini was audited with a comparatively small BERT-base surrogate. BAFA still converged faster than baselines after an initial phase of high variance in the first 100–120 queries. Replacing the surrogate with DistilBERT increased AUEC by less than 5% (across 3 seeds).

• Bound width tracks error: BAFA's uncertainty interval contained the ground-truth metric in over 95% of queries on CivilComments — 99.9% for BAFA-BO and 95.4% for disagreement-based selection. On Bias-in-Bios coverage was lower due to surrogate–target mismatch, but average bound violation remained below ε = 0.02.

• Threshold for surrogate fidelity: The authors report that a surrogate only reliably mimics the black box after roughly 500–750 queries in their setting, which is why they use top-k disagreement ranking rather than the ε-driven disagreement loop of Yan and Zhang (2022).

Methodology in Plain English

The auditor wants to know how differently a black-box model ranks positive versus negative examples for two demographic groups — the difference between the two groups' ROC-AUCs. The auditor has labelled data with group attributes and true labels, but can only send inputs to the model and read back scores.

BAFA starts with a small stratified seed set of inputs that get queried. From these observed scores, it trains a set of BERT-based surrogate models that are consistent with what has been observed, allowing each surrogate's prediction to deviate from the observed black-box score by at most a tolerance λ. Within that "version space," it solves two constrained optimisation problems: one that maximises Δ_AUC and one that minimises it. The results give a lower and an upper bound on the fairness metric — a certificate interval. Because ROC-AUC is not differentiable, the authors optimise a sigmoid pairwise ranking surrogate instead.

If the interval's half-width is within the target tolerance ε, the audit stops and reports the interval midpoint. Otherwise, BAFA scores every unqueried candidate by how much the two extremal surrogates disagree about it, and queries the top-k most disagreeable inputs. Those new scores shrink the version space, narrowing the interval. Two selection rules are tested: bound-disagreement sampling, and Bayesian optimisation over acquisition features including bound disagreement, LoRA-surrogate diversity, and surrogate–black-box disagreement. Both use distributional regularisation based on subgroup and label marginals to limit selection-induced bias.

The evaluation covers two case studies. Case Study A audits hate speech detection using CivilComments, with a HateBERT model fine-tuned on SBIC and labels systematically flipped for comments targeting marginalised groups, creating a known disparity of approximately Δ_AUC ≈ 0.14 over roughly 50,000 comments. Case Study B audits occupation inference from biographies using Bias-in-Bios and GPT-4.1-mini as the black-box scorer, with a non-injected disparity of approximately 0.02–0.045 across roughly 50,000 biographies. Both are run with identical budgets and batch sizes and averaged across 20 random seeds.

Why This Matters

Impact on research. The paper shifts auditing from a benchmarking or red-teaming paradigm toward uncertainty estimation over a measurable property. It supplies the extension to threshold-invariant ranking metrics that both Yan and Zhang (2022) and Singh et al. (2023) explicitly called for, and it tests active auditing for the first time against a commercial black-box model whose architecture differs from the surrogate.

Real-world applications:

• Independent audits by NGOs, journalists, and academic researchers of commercial model APIs under budget constraints.
• Continuous fairness monitoring after model updates, policy changes, or language evolution, particularly in hate speech moderation.
• Auditing automated hiring and CV screening systems, where the paper's Bias-in-Bios case study directly targets gender-based occupation inference disparities.
• Extending to other group metrics (TPR/FPR gaps at fixed thresholds, equalised odds) and to privacy, robustness, and safety audits.

Industry relevance. The EU Code of Practice on Generative AI (Appendix 3.5) and various governance proposals reference independent black-box auditing. Query-efficient methods reduce the cost and legal friction (GDPR data minimisation) of compliance-oriented evaluation, and the paper notes that smaller budgets let auditors cover more groups, domains, and languages.

Future Directions

• Better-matched surrogates: The authors suggest trying GPT-2 or GPT-3 as surrogates when auditing GPT-4.1-mini, since matching architectures could yield more accurate results and faster convergence, though they consider this out of scope here.

• Reducing compute cost: The end-to-end pipeline is resource-intensive due to repeated in-loop optimisation. Proposed directions include caching and more efficient data pipelines, algorithmic warm-starting across rounds, better batching, and hybrid protocols that switch to simpler sampling once the interval is already narrow.

• From prototype to auditor-facing tool: Turning BAFA into deployable infrastructure would require multi-metric support, transparent uncertainty reporting, dataset and budget management, and human-centered interfaces for configuring audits with uncertainty visualisation.

• Interpreting query selection as a signal: The sequence of selected inputs reveals which examples the method considers most informative. Characterising which regions of the input space different selection rules emphasise — borderline cases, specific linguistic patterns such as AAE or counterspeech, identity tokens, or subpopulations — could guide qualitative review.

• Auditing as information gain over time: The authors propose treating each new label as an update to the auditor's understanding of fairness and possible distribution shifts, making better use of past audit data for monitoring.

Target Audience

This paper is most useful to fairness and accountability researchers, AI auditors and independent evaluation organisations, and machine learning practitioners responsible for compliance with fairness or regulatory requirements. Policy analysts working on generative-AI codes of practice will find the framing of audits as calibrated uncertainty estimates relevant. Readers without a background in constrained optimisation or ranking metrics will find the conceptual framing accessible, but the methodological details require an intermediate-to-advanced level.

Authors’ abstract

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.