acceptodds
Under review as a conference paper at ICLR 2027

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Multi-group fairness, Minimax active audits, Interpretability

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_oqX2OpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies post-hoc auditing of multi-group fairness for black-box ML models. It proposes “bias probes” based on cross-group relational queries and further considers model-extraction resistance and auditing against a fairness-aware adversarial model owner.

Critical strengths
  • The topic is relevant, and the paper provides a fairly comprehensive theoretical treatment rather than only an empirical auditing method.

  • The paper attempts to connect efficient fairness estimation, interpretability and model confidentiality within one framework, and evaluates the method on several standard fairness datasets and classifiers.

Critical weaknesses
  • The core idea is to replace ordinary model queries with Cross-Group Queries, where the auditor submits one example from each protected group and receives only relational comparisons rather than the underlying predictions. While technically interesting, I am not fully convinced that this represents a sufficiently substantial advance over the existing active auditing/active learning literature for ICLR. The paper needs to have a much clearer explanation of what fundamentally becomes possible with bias probes that cannot be achieved by adapting existing active fairness auditing approaches.

  • The main experiments use COMPAS, German Credit and Student Performance, with linear models, random forests and MLPs. For claims concerning practical black-box auditing, model confidentiality and adversarial model owners, stronger evaluation on larger and more realistic modern ML systems would make the contribution more convincing.

Questions for authors
  • How would Cross-Group Queries be implemented in a realistic auditing scenario where the auditor has access only to a conventional prediction API?

  • Could the authors clarify more sharply the technical novelty relative to existing active fairness auditing and comparison-query/disagreement-based active learning?

  • How well does the approach scale to modern high-dimensional models, multiple or intersecting protected attributes, and larger numbers of groups?

2 comments

We appreciate the reviewer’s time and effort in carefully reading our paper and for providing constructive feedback. We respond to each point below and describe the clarifications and corrections made to the manuscript.

  • Implementation of Cross-Group Queries. Cross-Group Queries (CGQ) can be implemented through a middleware layer around a standard prediction API. A conventional API returns individual predictions, whereas our approach requires comparisons across protected groups. This functionality can be provided by an additional inference wrapper connected to the model owner's prediction API. Given a coupled set of samples, the wrapper queries the underlying model for each sample, computes the corresponding cross-group comparison, and returns only the comparison result to the auditor. Individual predictions remain internal to the wrapper and are not disclosed. The auditor can therefore interact with this wrapper through a dedicated CGQ endpoint, without access to the model under audit or its prediction API.

  • Technical novelty relative to existing literatture. Our work provides a general framework for actively auditing multi-group fairness with an arbitrary number of protected groups, while accounting for an adaptive adversarial model owner. The framework provides guarantees on audit accuracy and produces interpretable reports, even when the model owner attempts to conceal unfair behavior.A key distinction between our approach and existing fairness-auditing methods concerns the object of the auditor's learning task. While existing approaches typically assess discriminatory behavior through statistical parity between two groups, our formulation generalizes the problem to an arbitrary number of groups. Moreover, existing methods broadly follow two strategies: direct estimation of the fairness measure or model reconstruction followed by plug-in estimation. The former estimates group-dependent quantities from sampled queries, while the latter learns an approximation of the model to evaluate its fairness properties. A summary of these approaches are in Appendix B. Our approach is different: instead of estimating the fairness measure directly or reconstructing the entire model, the auditor learns a probe that captures the model's discriminative behavior across protected groups. At each round, the auditor requests a comparison across groups on a selected coupled sample. These responses progressively refine the probe space until the auditor identifies a probe that witnesses a significant group discrepancy. This approach has two main advantages. First, the learned probes provide interpretable audit report of the detected group discrepancies. Second, learning the relevant relative behavior can be substantially easier than reconstructing the underlying model, as established by our information-theoretic separation result. Overall, our framework provides a distinct approach to active multi-group fairness auditing and establishes a foundation for studying robustness against adaptive adversarial model owners. We have updated the contribution section clarifying this in the revised draft (line 107).

  • Scalability to high-dimensional models and groups sizes. The scalability of our framework depends primarily on the complexity of the probe class, rather than on the input dimension or the number of protected groups alone. First, input dimension does not directly enter the definition of multi-group fairness which is defined in terms of protected groups (the unique feature relevant to estimate multi-group fairness). However, our auditor also identifies regions of the input space that exhibit substantial unfairness, providing interpretable audit reports. The complexity of this search is captured by the statistical complexity of the probe class, through quantities such as the multi-star number and the Daniely-Shwartz dimension. Second, our framework does not require protected groups to be disjoint. It therefore also covers intersecting protected groups. The dependence on the number of groups kk is appears in the multi-star number and the Daniely-Shwartz dimension. We provide a more detailed discussion in Appendix E.2 (paragraph beginning at line 1879). Finally, scalability to modern high-dimensional models depends on the complexity of their induced probe classes. These classes may be substantially more complex than those arising from the restricted linear models used in our illustrative separation result. Consequently, our theoretical guarantees remain applicable, but the resulting sample complexity depends on the structure of the induced probe class.

AuthorsOpenReview ↗

Follow up on our response

Dear Reviewer,

Thank you again for your constructive feedback on our work. We submitted our responses a few days ago and updated the manuscript. We wanted to kindly follow up, as the discussion period is coming to an end. We would very much appreciate it if you could revisit your evaluation in light of our responses, should they have addressed your concerns. If you have any further questions or concerns, please do not hesitate to let us know. We look forward to hearing your thoughts.

Kind regards,

Authors,

Reviewer_HF3vOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes to audit group fairness by querying tuples across sensitive demographic groups for comparing disparities while limiting what the auditors can learn about the model. They introduce the ALeBi algorithm, which queries only tuples where candidate comparison functions still disagree and uses them to estimate the statistical parity. They characterize the query complexity through the multi-star number and argue that learning the comparison function is cheaper than model reconstruction. Experiments are conducted on three datasets and show the estimated statistical parity is close to the true one, with errors comparable to or lower than three baselines (model reconstruction, direct audit, and the active fairness auditing method of Yan & Zhang, 2022).

Critical strengths

The idea of auditing fairness by comparing predictions across groups, rather than reconstructing the model, is original. It is relevant in practice, where auditors can only have black-box access to the model and owners want to keep it confidential. I also find the extension to a fairness-aware adversary original, with the proposed Robust k-ALeBi remaining robust in this setting.

Critical weaknesses
  • Requiring the real model to be in a finite candidate class seems difficult in practice. The paper does not explain how this class is built for random forests or MLPs and the number of candidates is never given.
  • The theoretical guarantees require a finite multi-star number, which is only shown for simple classes such as linear classifiers in a restricted setting, not for other models like random forests or MLPs.
Questions for authors
  1. How is the candidate class built for random forests and MLPs, and how does the method behave when the true model is not in this class?
  2. Can the theoretical guarantee be extended to more general settings than the restricted linear case?
2 comments

We appreciate the reviewer’s time and effort in carefully reading our paper and for providing constructive feedback. We respond to each point below.

  • Requirement of a finite candidate class and Multi-context class for known models. Our results and contributions do not require the candidate multi-context class to be finite. Indeed, the classes considered in our paper including those induced by linear classifiers can be infinite. Our main contribution is a characterization of active PAC learnability in the minimax setting through the multi-star number of the candidate multi-context class. In particular, a finite multi-star number guarantees active PAC learnability under our framework, regardless of whether the class itself is finite or infinite. Thus, the relevant condition is the finiteness of the multi-star number, not the finiteness of the class. Establishing a finite multi-star number can nevertheless be challenging for more expressive model classes like neural networks. If their multi-star number is infinite, our characterization implies that they are not actively PAC learnable under the framework considered here. However, determining suitable group representations for controlling the number of multi-stars in highly expressive models remains an interesting open direction for future investigation.

  • Probe class construction for random forests and MLPs and extension to agnostic settings. The candidate probe class can be constructed using the same principle across different model architectures. It captures differences in model predictions across combinations of protected groups. For random forests and MLPs, we define the relative probe class through differences in their prediction scores across these combinations. Since our setting considers probe classes constructed with respect to a predefined model class under audit (e.g., MLPs or random forests), our current theoretical guarantees are established under the realizability assumption, where the true probe belongs to the candidate probe class. Extending these guarantees to the agnostic setting would allow the auditor to choose an arbitrary probe class and obtain guarantees relative to its best approximation of the true probe. This requires a different theoretical analysis, which we leave as an interesting direction for future work.

  • Extension to general settings beyond the restricted linear case. We would like to clarify the distinction between our general theoretical characterization and the specific construction used to establish the statistical separation between auditing approaches. Our theoretical results apply to general probe classes. We do not assume that these classes are induced by linear classifiers. Instead, we characterize active PAC auditability through the multi-star number. The resulting guarantees therefore apply to an arbitrary probe class with a known multi-star number.

AuthorsOpenReview ↗

Follow up on our response

Dear Reviewer,

Thank you again for your constructive feedback on our work. We submitted our responses a few days ago and updated the manuscript. We wanted to kindly follow up, as the discussion period is coming to an end. We would very much appreciate it if you could revisit your evaluation in light of our responses, should they have addressed your concerns. If you have any further questions or concerns, please do not hesitate to let us know. We look forward to hearing your thoughts.

Kind regards,

Authors,

Reviewer_HxziOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces bias probes based on cross-group prediction differences and k-ALEBI, a disagreement-based active learner for auditing multi-group statistical parity. It also develops feature-conditioned disparity profiles, query-complexity bounds, and a neighborhood-voting robust variant, with evaluations on three benchmark datasets.

Critical strengths
  • The combination of relational access, multi-group fairness estimation, and localized disparity reports is an interesting auditing formulation. Its contribution appears strongest at the interface and application level rather than in the underlying disagreement-based learning method.
  • Proposition 1's coupling-invariance identity is correct and provides a useful foundation for constructing cross-group queries. The neighborhood-voting approach also has a sound concentration argument when the combined noise rate is below one half.
Critical weaknesses
  1. The central learnability characterization is incorrect as stated. Corollary 4 claims that finite star number is necessary for PAC active learnability. However, singleton indicators together with the zero function have DS dimension 1 and infinite star number, yet are PAC learnable. This is an admissible CGQ instance when the second group consists of an anchor whose prediction is always zero. The same example contradicts Claim 13's inequality sk≤DSks_k \leq DS_k; under the intended sample-restricted star definition, its argument establishes the reverse inequality. Finite star number may characterize a label-complexity improvement, but it does not characterize ordinary PAC learnability as defined here. Additionally, Theorem 3's proof invokes a passive learner without explicitly connecting it to Algorithm 1's version-space output; this requires clarification rather than implying that no suitable learner could achieve the proposed rate.

  2. The principal reconstruction–probing separation is not established by the supplied example. Appendix B.3 assumes that homogeneous linear classifiers in R2\mathbb{R}^2 have infinite star number. Their standard star number is actually 3 under the stated ≥0\geq 0 boundary convention, or 2 when boundary ties are excluded. Consequently, this example does not establish the advertised infinite-versus-finite separation. A structured coupling such as (x,Rx)(x,Rx) is not inherently problematic; the decisive issue is the incorrect reconstruction-complexity premise. This does not rule out a separation for another instance, but a valid replacement argument is needed for this central contribution.

  3. The extraction-hardness proof supports a narrower conclusion than the stated confidentiality claim. Theorem 15's Test Cover reduction establishes hardness of deciding whether a small, nonadaptive query set can distinguish all candidate models. This differs from recovering a particular target after its probe has been learned. In the reduction's explicitly represented finite hypothesis class, matching a fully known probe-response vector against the candidate models is polynomial-time. The query-selection hardness result may be useful, but it does not by itself establish the claimed general model-extraction resistance. The paper needs a precise confidentiality guarantee and an argument addressing that guarantee under the actual query protocol.

  4. The robustness theorem requires an additional combined-noise condition. Assumptions 5–6 separately require p<1/2p<1/2 and ρ<1/2\rho<1/2, but these do not imply

    β=p+ρ−pρ<12.\beta = p+\rho-p\rho < \frac{1}{2}.

    For example, p=ρ=0.4p=\rho=0.4 gives β=0.64\beta=0.64. An admissible neighborhood can then produce a majority of the same incorrect response, causing voting to converge to the wrong label. Theorem 7 therefore needs an explicit condition β<1/2\beta<1/2. With that restriction, the concentration argument is valid. Importantly, the experiments' stated ρ=0.05\rho=0.05 and p≤0.4p\leq0.4 satisfy this condition, so this objection concerns the theorem's stated scope rather than automatically invalidating the tested noise regimes.

Questions for authors
  1. What corrected learning and separation results remain after addressing the singleton counterexample and the finite star number of homogeneous 2-D halfspaces?
  2. What precise confidentiality guarantee is established under the actual query protocol, and how does Theorem 15 support that guarantee?
2 comments

We appreciate the reviewer’s time and effort in carefully reading our paper and for providing constructive feedback. We respond to each point below and describe the clarifications and corrections made to the manuscript.

  • Offline PAC Vs Active PAC auditability. We agree that there is a typo in Claim 13. It should be $ \mathrm{DS}(\mathcal F) \leq \mathfrak{s}_k(\mathcal F) $. We rectify it in the revised draft, while noting that the proof is correct. The finiteness of the multi-star number is a necessary and sufficient condition for PAC active auditability but is not necessary for PAC offline auditability. When the multi-star number is infinite but the DS dimension remains bounded, then \textsc{kk-ALeBi} falls back to using an offline PAC learner, and achieves the bounds on Theorem 3, where the bounds remain finite even when the multi-star number explodes. We note that this is not evident from the pseudo-code of Algorithm 1, we have included the pseudo code for the optimal offline PAC probe learner and an explanation in the revised draft (line 1540).

  • Reconstruction-probing information-theroetic separation. Our original argument relied on the fact that non-homogeneous linear classifiers have an infinite star number, even in dimension two. The construction places points on a circle and selects, for each point, a separating line that isolates it from the others. This yields star sets of arbitrarily large size. A proof appears in Claim 1 (page 4) of [2]. We adapted this construction to represent the protected groups. However, we overlooked an important distinction between homogeneous and non-homogeneous linear classifiers. In particular, the zero bias case creates a singularity: homogeneous linear classifiers in dimension two have star number exactly 3. Therefore, our original construction did not establish the claimed separation. We resolve this issue by replacing the circle with a parabola. The new construction avoids the zero bias difficulty and preserves the desired separation. The model class has infinite star number, while the associated probe class has dual star number exactly one. We provide the full proof in the updated draft (line 1031).

  • The extraction-hardness proof. We believe there is a misunderstanding regarding the threat model of the extraction attack on bias probes. Our theoretical hardness result concerns the information available to an auditor after the interaction with the model owner has ended. We agree that this differs from interactive model extraction, where the auditor attempts to extract the model during the auditing procedure. This is a different objective from multi-group fairness auditing and falls outside the scope of our theoretical analysis. We have clarified the scope of the theorem in the revised manuscript (line 1243). We would also like to point out how we evaluate information leakage empirically, which is done interactively. We measure model extraction through identity leakage, as defined in Appendix D (Definition 8). The identity-leakage results show that reconstruction-based auditing reveals significantly more information about the model owner than our approach.

  • Additional combined-noise assumption for the robustness theorem. The robustness guarantee depends on a joint condition on the two corruption parameters described by β(ρ,p)\beta(\rho,p). The admissible value of each depends on the value of the other. β<12\beta <\frac 12 defines a curvilinear triangular region in the (ρ,p)(\rho,p)-plane. We have added Figure 1 to the revised manuscript to illustrate this feasible region. The condition also has a direct interpretation. A higher attack-probability bound pp requires a smaller disagreement probability ρ\rho (distinguishability evidence) for the guarantee to hold. Similarly, a smaller attack-probability bound allows a larger disagreement probability (lower evidence). In other words, a higher attack probability must be compensated by stronger agreement with the model owner's predictions. We have clarified this assumption and its interpretation in the revised manuscript (line 390).

    [1] Pabbaraju, C. (2026). The optimal sample complexity of multiclass and list learning. arXiv preprint arXiv:2604.24749.

    [2] Dasgupta, S. (2004). Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17.

AuthorsOpenReview ↗

Follow up on our response

Dear Reviewer,

Thank you again for your constructive feedback on our work. We submitted our responses a few days ago and updated the manuscript. We wanted to kindly follow up, as the discussion period is coming to an end. We would very much appreciate it if you could revisit your evaluation in light of our responses, should they have addressed your concerns. If you have any further questions or concerns, please do not hesitate to let us know. We look forward to hearing your thoughts.

Kind regards,

Authors,

Comments on the paper

1 comment

Dear Reviewers,

As the discussion period is approaching its deadline, we would appreciate your feedback on our rebuttal. We would be grateful if you could let us know whether our responses have adequately addressed your concerns, we have also revised the manuscript accordingly to incorporate the reviewers' suggestions. If any questions or issues remain unresolved, we would be more than happy to clarify them and engage in further discussion.

Thank you for your time and consideration.

Best regards,

Authors,

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.