Paper deep dive
Efficient Active Auditing of Multi-Group Fairness with Bias Probes
Ayoub Ajarra, Debabrota Basu
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2609.40034v1
- Canonical: https://arxiv.org/abs/2609.40034v1
Trouble viewing inline? Open PDF directly →
Full Text
172,520 characters extracted from source content.
Expand or collapse full text
_set:Ne resultbox Efficient Active Auditing of Multi-Group Fairness with Bias Probes Ayoub Ajarra Debabrota Basu Affiliation: Équipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRIStAL Email: ayoub.ajarra@inria.fr 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. Contents 1 Introduction 1.1 Related Work 1.2 Summary of contributions 2 Problem Formulation: Auditing Multi-group Fairness 2.1 Audit via Model Reconstruction 2.2 Audit via Direct Estimation 3 Interpretable, Manipulation-Proof and Reconstruction-Free Audits with Bias Probes 3.1 Interpretable Audits via Bias Probes 3.2 Information Complexities For Learning Probes 3.3 Information-Theoretic Separation of Reconstruction and Probe Auditing 3.4 Manipulation-free Regime 3.4.1 Hardness Results on Sample Complexity and Model Extraction 3.4.2 Hardness of Model Extraction Attacks 3.4.3 Algorithm Design: k-ALeBi and Upper Bounds 3.5 Fairness-aware Adversarial Regime 3.5.1 Adaptive Fairness-aware Adversary: Algorithm and Upper Bounds 3.5.2 Global Information-theoretic Hardness 4 Experimental Analysis 4.1 Accuracy 4.2 Interpretability 4.3 Protection Against Model Extraction Attacks 4.4 Robustness against Fairness-Aware Adversaries 5 Conclusion References A Extended Framework Description A.1 General Framework for Property Specific Audits A.2 Information-theoretic and combinatorial separation between active learning and active auditing in the presence of protected groups A.3 Examples of relative dual classes and their star numbers from known hypothesis classes A.4 Mutli-star number of multi-context class relative to linear classifiers B Protection against Model Extraction C Proofs for Manipulation-free Regime C.1 Lower Bound on Sample Complexity C.2 Proof of ALeBi Upper Bounds D Proofs for Fairness-aware Manipulation Regime E Auxiliary Definitions and Lemmas F Additional Experiments Results and Details F.1 Fairness-aware Adversarial Regime F.2 Auditors Baselines 1 Introduction Assessing ML models has become increasingly critical, as mounting evidence shows that deployed systems may exhibit harmful biases across a wide range of domains, including medical imaging (Seyyed-Kalantari et al.,, 2021; Daneshjou et al.,, 2022; Vrudhula et al.,, 2024; Banerjee et al.,, 2021), hiring and job screening (Harwell,, 2022; Wilson and Caliskan,, 2024), credit lending (Garcia et al.,, 2024), and online platforms (Biswas and Rajan,, 2020). Among these concerns, discriminatory bias has received particular attention, giving rise to the field of algorithmic fairness (Barocas and Selbst,, 2016; Hardt et al.,, 2016). A central line of work focuses on designing fair learning procedures, where fairness constraints are incorporated directly into the training process, typically as optimization constraints trading off predictive accuracy and fairness guarantees (Zafar et al.,, 2017; Agarwal et al.,, 2018). However, empirical evidence suggests that such approaches may yield limited improvements over standard ERM in practice (Zong et al.,, 2022). These limitations, combined with increasing regulatory pressure, have shifted attention toward post-deployment auditing. In the United States, regulations such as New York City’s Local Law 144 New York State Senate, (2024) mandate bias audits of automated decision systems. In Europe, the Digital Services Act European Commission, 2024a () and the AI Act European Commission, 2024b (); Ebers, (2025) impose transparency, risk management, and auditing requirements for large-scale and high-risk ML systems in online platforms. These developments reflect a broader shift, where auditing is becoming a central requirement for deploying ML systems in high-stakes settings. In this post-deployment regime, the model is typically treated as a black box. An external auditor seeks to assess the model’s behavior without access to its internal structure, interacting with the model owner through queries. This setting introduces a fundamental tension: the auditor aims to extract sufficient information to reliably evaluate fairness, while the model owner may wish to limit disclosure in order to protect model’s sensitive information. A large body of work has studied fairness auditing under this paradigm. Existing approaches typically fall into two categories. The first relies on model reconstruction, using tools from active learning (Angluin,, 1988; Balcan et al.,, 2012) to learn the model –or an accurate surrogate– before estimating fairness metrics. The second relies on direct estimation of a difference of means, using labeled samples. However, both approaches exceed the auditing objective: reconstruction attempts to recover the full model, while direct estimation is as costly as replicating the learning process and do not produce explanations, making it impractical in realistic auditing scenarios. Moreover, reconstruction-based approaches may expose the model to extraction attacks, compromising confidentiality. This tension raises the following question: Q1: Can we obtain distribution-free guaranties for fairness auditing that avoid both full model reconstruction and large-scale labeled data requirements? Beyond estimation, interpretability is also a critical component of auditing. In the context of machine learning regulation, Article 86 of the AI Act European Commission, 2024b () underscores the right to explanation in automated decision-making. For example, an individual denied a bank loan by an ML system is entitled to receive an explanation for that decision. While standard audit methods provide quantitative summaries of bias (Goldreich et al.,, 1998; Yan and Zhang,, 2022; Chugg et al.,, 2023), they do not yield interpretable representations of the model’s discriminatory behavior. In parallel, the literature on representation learning has introduced probes as simple functions used to extract specific properties from learned representations (Alain and Bengio,, 2016). Inspired by this perspective, we introduce bias probes – structured comparison functionals that capture relational disparities between protected groups. Unlike feature attribution methods, which operate at the level of individual inputs, bias probes focus on intergroup comparisons and provide an interpretable summary of discriminatory behavior. To the best of our knowledge, this is the first work to formalize fairness auditing with explicit interpretability guarantees in this sense. Finally, we must account for the security of the auditing process. Existing auditing methods, particularly those that rely on membership queries (Yan and Zhang,, 2022), may render the model vulnerable to extraction attacks, effectively reducing auditing to model reconstruction. This highlights a second fundamental challenge: ensuring that auditing procedures do not compromise model confidentiality. This leads to our second question: Q2: Can we design sample-efficient and interpretable auditing procedures while preserving model confidentiality against extraction attacks? Beyond the accuracy and interpretability of the audit report, we further extend our setting by considering a model owner who may behave adversarially, with the goal of concealing unfairness across groups. The adversarial behavior we consider differs from the adversarial models commonly studied in the literature, such as Huber contamination models Chen et al., (2016), adversarial distribution shifts Croce et al., (2020), or adversarial input perturbations Montasser et al., (2021); Goodfellow et al., (2018). In these settings, the adversary typically manipulates the data or the input distribution, whereas our adversary is fairness-aware: the model owner may strategically manipulate the model’s behavior to make unfairness harder to detect by the auditor. This leads to our second research question: Q3: How can we design fairness auditors that are accurate and interpretable while remaining robust to fairness-aware adversaries? Figure 1: Interactive fairness auditing against a fairness-aware adversary. In Figure 1, the auditor is given the task to audit a property of interest μ, has access to a pool of unlabeled instances Q sampled from the marginal input distribution, providing information about the regions of the input space relevant to the audit. The auditor then selectively queries the model owner with samples that are informative with respect to μ. At round t+1t+1, the auditor constructs a query qt+1q_t+1 and sends it to the model owner M, who returns a response t+1=(qt+1)M_t+1=M(q_t+1). We assume a powerful, fairness-aware adversary that may strategically alter its responses to conceal disparities across groups. Based on the history (q1,1),…,(qt+1,t+1)\(q_1,M_1),…,(q_t+1,M_t+1)\, the auditor produces an estimate μ^t+1 μ_t+1 of the property under audit, together with regions of the input space in which the model exhibits larger fairness disparities. In this work, we address these challenges in the setting of multi-group fairness. We consider an interactive auditing framework in which an auditor queries a black-box model through carefully designed inputs drawn from a pool of unlabeled data. Our approach focuses on learning comparison functionals that capture the model’s discriminative behavior across protected groups, rather than reconstructing the model itself. This perspective enables both statistical efficiency and interpretability while inherently limiting the information exposed to the auditor, thereby protecting the model owner from reconstruction attacks. 1.1 Related Work Fairness Auditing. Algorithmic fairness has been widely studied from both the learning and auditing perspectives. A large body of work focuses on learning fair models via constrained optimization or reduction-based approaches (Zafar et al.,, 2017; Agarwal et al.,, 2018). In addition, post hoc audit methods aim to assess the fairness properties of a model deployed under limited access (Kearns et al.,, 2018; Yan and Zhang,, 2022; Chugg et al.,, 2023). Recent works have proposed active auditing strategies for estimating fairness metrics under distributional assumptions (Yan and Zhang,, 2022). These approaches often reduce auditing to model reconstruction within a hypothesis class, leading to guarantees that scale with the complexity of learning. Other related works propose frameworks, where bias audit reduces to a binary objective via testing approaches (Chugg et al.,, 2023; Goldreich et al.,, 1998). In contrast, our work treats fairness auditing as a property estimation problem, focusing on the intrinsic combinatorial structure of intergroup comparisons rather than recovering the full model. Interpretability and Probing Methods. Post hoc interpretability methods, including feature attribution techniques (Ribeiro et al.,, 2016; Lundberg and Lee,, 2017) and counterfactual explanations (Kusner et al.,, 2017), aim to provide descriptive summaries of model behavior. In parallel, probing methods have been developed in representation learning to extract specific properties from learned representations using simple models (Vafa et al.,, 2025; Alain and Bengio,, 2016) or alternatively explaining biases in Large Language Models Immer et al., (2022); Morehouse et al., (2025); Guo et al., (2022); Manerba et al., (2024). Our notion of bias probes is conceptually related but differs in both objective and scope. Rather than analyzing internal representations, bias probes capture relational disparities between protected groups and are directly tied to fairness properties. Moreover, our probes are equipped with statistical guarantees, bridging interpretability and rigorous auditing. Active Learning and Disagreement-Based Complexity. Disagreement-based active learning characterizes label complexity through geometric and combinatorial quantities such as the disagreement coefficient in distribution-dependent settings (Balcan et al.,, 2006; Dasgupta et al.,, 2007) and the star number in distribution-free regimes (Hanneke,, 2014; Hanneke and Yang,, 2015). These parameters capture the ability of a hypothesis class to isolate individual instances via localized perturbations around a reference hypothesis. Our analysis is inspired by this framework but departs from it in a fundamental way. In classical active learning, disagreement regions are subsets of the instance space. In contrast, the auditing setting we consider induces disagreement over cross-group tuples, leading to a multipartite geometry rather than a pointwise one. To capture this structure, we introduce the intergroup star number, which extends the classical notion of star number to relational settings between sub-populations. This quantity measures the capacity of a comparison class to isolate cross-group configurations, and serves as the key complexity parameter governing sample efficiency in our setting. Preference Learning. Preference learning is closely related to our setting, as it also relies on pairwise comparisons. In its classical formulation, a collection of users provides pairwise preferences over a finite set of items, and the goal is to predict unseen preferences. Many approaches aim to estimate a score matrix of size (number of users) × (number of items), often under low-rank assumptions and solved via convex optimization Park et al., (2015). Several works consider active querying in this setting. For instance, Ailon, (2012) studies adaptive pairwise comparisons over a finite set of items and returns a total order whose disagreement is competitive with the optimal ranking. However, their guarantees concern approximation to the best ranking with bounded query complexity, rather than uniform learning over a general function class. Similarly, methods based on convex relaxations, such as SVM-rank, operate within a fixed parametric class and focus on ranking performance rather than learning comparison functionals. Mao et al., (2023) provides finite-sample guarantees linking surrogate losses to target ranking losses. However, this line of work focuses on bipartite ranking and misranking loss, rather than recovering structure from pairwise comparisons in a general interactive setting. In contrast, our approach does not aim to learn a ranking over a finite set of items. Instead, we learn a class of comparison functionals that capture the discriminative behavior of a black-box model over the input distribution. This shifts the problem from ranking to distributional estimation, where the goal is to approximate the induced comparison structure with uniform guarantees over a function class. Model Extraction Attacks. Model extraction attacks have emerged as a major threat to ML systems deployed through black-box interfaces. In these attacks, an adversary interacts with a model via query access and trains a surrogate model that replicates the functionality of the original model (Tramèr et al.,, 2016; Orekondy et al., 2019a, ; Yuan et al.,, 2024; Orekondy et al., 2019b, ). Early work demonstrated that even simple query strategies can recover models such as logistic regression, decision trees, and neural networks with high fidelity (Tramèr et al.,, 2016). Subsequent work has shown that extraction is possible even without access to real data, by generating synthetic queries or by using knowledge distillation techniques (Orekondy et al., 2019a, ; Yuan et al.,, 2022). From a broader perspective, model extraction raises both intellectual property and security concerns, as stolen models can be reused or further exploited for downstream attacks (Jagielski et al.,, 2020). In the context of large language models (LLMs), model owners with API access are highly vulnerable to model extraction attacks, posing significant security risks. In particular, Liu and Moitra, (2025) show that any low-rank language model can be learned in polynomial time using conditional queries. We design auditing mechanisms that intentionally restrict the information revealed through queries, and show that recovering the underlying model from our bias probes is computationally hard (under standard assumptions). 1.2 Summary of contributions Our main contributions are as follows: • A comparison-based framework for fairness auditing. We introduce a novel framework based on bias probes, which capture the discriminative behavior of a model through structured inter-group comparisons. We formalize fairness auditing as the problem of learning comparison functionals and establish distribution-free guarantees for estimating multi-group fairness. • A new complexity measure and optimal query-complexity bounds. We introduce the k-inter-group star number k s_k (Definition 3.6), extending the classical star number (Hanneke and Yang,, 2015) to the multi-group setting and addressing an open question raised by (Yan and Zhang,, 2022) in the case k=2k=2, that we generalize for arbitrary to arbitrary k. We characterize the query complexity of auditing in terms of this parameter, proving the lower bound Ω(max1−2δ1−δmink,⌊12ϵ⌋,[1−2ϵ−2δ(1−ϵ)]+DSk) ( \ 1-2δ1-δ \ s_k, 12ε \,\; [1-2ε-2δ(1-ε) ]_+DS_k \ ). We further propose k-ALeBi, an active auditing algorithm achieving the upper bound (minn,(e−1)mink,nlogenmink,n+log2δ+1,mink,n1∨logmink,nDSklog(en(2k−2)DSk))O ( \n,\;(e-1) \ s_k,n\ en \ s_k,n\+ 2δ+1,\; \ s_k,n\1 \ s_k,n\\,DS_k ( en(2^k-2)DS_k ) \ ) where n=⌈DSk+log(4/δ)ϵ⌉n= DS_k+ (4/δ)ε , and DSkDS_k is the Daniely-Shwartz dimension (Daniely et al.,, 2015) (Definition 3.5). • Hardness of model extraction from bias probes. We distinguish accurate fairness auditing from recovery of the underlying classifier and show that selecting a bounded set of relational queries sufficient to identify all candidate models is NP-complete. Empirically, accurate fairness estimates can be obtained while multiple underlying models remain observationally compatible. • Auditing under a fairness-aware manipulation model. We introduce a fairness-aware adversary that activates based on the auditor’s current disparity estimate and may adaptively corrupt individual relational coordinates in CGQ responses. Under conditionally bounded corruption with p<1/2p<1/2, we propose Robust k-ALeBi, which achieves the same asymptotic bounds as k-ALeBi, up to additional terms that depend on the corruption level. • Empirical evaluation. We empirically evaluate ALeBi along four dimensions: estimation accuracy, interpretability of the resulting audit reports, protection against model extraction attacks, and robustness to fairness-aware manipulation. We compare our approach against two baselines, ReconAudit, which reconstructs the underlying model before performing the audit, and DirectAudit, which directly estimates the fairness property. Our experiments illustrate the trade-offs between these auditing paradigms and evaluate their behavior under both honest and adversarial model-owner interactions. 2 Problem Formulation: Auditing Multi-group Fairness Let ℋH denote a hypothesis class. The model owner M trains a model h:⊆ℝp+1→~h:Z ^p+1→ Y from ℋH on a dataset which then deploys. We assume that the first p coordinates correspond to unprotected features, while the (p+1)(p+1)-th coordinate represents a protected attribute A. This attribute partitions the input space Z into k≥2k≥ 2 disjoint subpopulations 1,…,kZ_1,…,Z_k (e.g., when A represents gender, k=2k=2). We denote by [⋅] 1_[·] the indicator function. Finally for a∈ℝa , [a]+:=max(a,0)[a]_+:= (a,0). We study group-level properties of h. In particular, we consider the maximum disparity of h across protected groups, captured by multi-group statistical parity. Definition 2.1 (Multi-Group Fairness). Let h:→~h:Z→ Y and let D be a distribution over Z. For a pair of groups (i,j)∈[k]2(i,j)∈[k]^2, define μi,j(,h)=X∼[h(X)∣X∈i]−X∼[h(X)∣X∈j]. _i,j(D,h)= X E[h(X) X _i]- X E[h(X) X _j]. The multi-group fairness violation of h is μ(,h)=maxi,j∈[k]μi,j(,h).μ(D,h)= _i,j∈[k] _i,j(D,h). The functional μ(,h)μ(D,h) depends jointly on the model and the data distribution. In particular, disparities in regions of Z with negligible probability mass under D do not contribute substantially to μ. Therefore, as illustrated in Figure 1, estimating μ requires access to the marginal distribution over Z, which motivates an active audit setting in which information about D is obtained through a pool of unlabeled points P. Remark 2.1. Unlike previous auditing studies (Yan and Zhang,, 2022; Ajarra and Basu,, 2026), which consider properties defined in terms of an absolute difference, our fairness property is signed and therefore preserves the direction of the disparity. In particular, identifying which group is favored and which group is disadvantaged is an essential part of the audit for interpretability. This directional information must be preserved for every pair of groups, as reflected in our definition, which takes the maximum over group pairs. More generally, we consider an auditing setting in which an auditor A has access to a pool of unlabeled samples Q and interacts with a model owner M by issuing queries q1,…,qmq_1,…,q_m in order to estimate a property μ of a model h. Formally, μ:()×ℋ→ℝμ:P(Z)×H is a functional that quantifies a distributional property of models in ℋH. An auditing problem is defined by the tuple ⟨,~,,I(h),μ,ℓμ⟩ , Y,P,I_M(h),μ, _μ , where Z and ~ Y denote the input and output spaces, P is a class of probability measures over Z, and I(h)I_M(h) represents the information about h available to the auditor. In the white-box setting, I(h)=hI_M(h)=h, while in the black-box setting it corresponds to oracle access to h, possibly augmented with side information such as the hypothesis class ℋH. The functional μ captures a property of h under distributions in P, and ℓμ:ℝ×ℝ→ℝ _μ:R×R is a bounded loss function. Additional details about the general auditing framework are provided in Appendix A.1. We now introduce the notion of PAC auditing in the interactive setting. We focus on auditing multi-group properties, which introduce additional challenges as reliable estimation requires uniform information across subpopulations. In particular, we study the auditing of multi-group fairness (Definition 2.1). To date, several approaches have been proposed to audit statistical parity. Broadly, these methods fall into two categories: 2.1 Audit via Model Reconstruction In this setting, the auditor has access to the hypothesis class ℋH and query access to the model h, i.e., I(h)=ℋ,(h)I_M(h)=\H,M(h)\. The goal is to reconstruct a surrogate model by emulating the training process within ℋH. For instance, Yan and Zhang, (2022) use disagreement queries to identify a subclass of ℋH whose elements share the same statistical parity on a given unlabeled pool. Interaction Protocol for Reconstruction-based Audit. The interaction between the auditor ReconAudit and the model owner (h)M(h) proceeds as follows: • The auditor is given the hypothesis class ℋH and access to the unlabeled pool Q, and a query budget T. • Round t=1t=1. The auditor selects a query X1∈∩DIS(ℋ)X_1 (H) and sends it to the model owner. The model owner returns the response h(X1)h(X_1). • Round t=2,⋯,Tt=2,·s,T. Based on the history of previous queries and responses, the auditor updates its current hypothesis class VtV_t and selects a query Xt∈∩DIS(Vt)X_t (V_t). It sends XtX_t to the model owner and receives the response h(Xt)h(X_t). • Reconstruction. After T rounds, the auditor selects any h^∈VT h∈ V_T to reconstruct a surrogate model of h. • Audit. The auditor applies a plug-in estimator to h h to estimate the multi-group fairness property using the history of queries collected during the interaction. However, such approaches rely on queries designed for learning rather than for estimating the target property. As a result, their sample complexity scales with that of learning, typically (d/ε2log1δ)O(d/ ^2 1δ), where d denotes a complexity measure of ℋH (e.g., VC dimension). This dependence not only leads to inefficiency but also raises model confidentiality concerns, as it may enable model extraction. We design our first baseline, ReconAudit, inspired by the reconstruction-based auditing approach.11 1 We note that the algorithm of Yan and Zhang, (2022) is restricted to the class of linear separators. We therefore develop a general reconstruction-based algorithm that does not rely on a specific model class. Algorithm 1 ReconAudit 1: I(h)=ℋ,(h)I_M(h)=\H,M(h)\, query pool Q, budget T 2: Initialize V0=ℋ.V_0=H. 3: for t=1,…,Tt=1,…,T do 4: Select Xt∈DIS(Vt)X_t (V_t) 5: Query t=h(Xt).M_t=h(X_t). 6: Update Vt=h′∈Vt−1:h′(Xt)=t.V_t= \h ∈ V_t-1:h (X_t)=M_t \. 7: end for 8: Reconstruct h^∈VT h∈ V_T 9: return h h and μ^T=μ1:T(h^). μ_T= _Q_1:T( h). Remark 2.2. We first observe that model learning does not depend on the protected groups represented in the data. In particular, ReconAudit does not account for group membership during the learning procedure, which may lead to higher reconstruction errors for some groups than for others. Second, once the model has been reconstructed, the auditor effectively has white-box access to the model, and the subsequent audit can therefore employ any white-box procedure, including procedures for producing interpretable audit reports. Whether such a reconstruction-based strategy remains robust in the presence of a fairness-aware adversary, however, is not clear a priori. We investigate this question in Section 4. 2.2 Audit via Direct Estimation In this setting, the auditor samples (1/ε2log1μ)O(1/ ^2 1μ) from each group in the pool P, and perform membership queries 22 2 or alternatively has access to a random query oracle. The objective is to estimate the target property μ directly from these samples, without reconstructing the model. While the sample complexity still scales as (k/ε2log1μ)O(k/ ^2 1μ), it no longer depends on the complexity of ℋH. This avoids the need for uniform approximation over the hypothesis class and mitigates risks associated with model reconstruction. Interaction Protocol for Direct-Estimation Audit The interaction between the auditor DirectAudit and the model owner (h)M(h) proceeds as follows: • The auditor is given access to an unlabeled pool Q and a query budget T. • Rounds t=1,…,Tt=1,…,T. At each round, for each group i∈[k]i∈[k], the auditor samples points from Q and queries the model owner. It uses the responses to estimate the expected positive-label rate for each group. • Estimation. After T rounds, the auditor obtains estimates of the pairwise disparities μ^ij:i,j∈[k],i<j, \ μ_ij:i,j∈[k],\,i<j \, forming a vector of size k(k−1)2=(k2) k(k-1)2=O(k^2). • Audit. The auditor outputs the maximum estimated pairwise disparity as its estimate of the multi-group fairness property. Remark 2.3. The reconstruction-based audit can be viewed as a search-then-estimate procedure: the auditor first searches for a surrogate model consistent with its observations and only then extracts the audit report from the reconstructed model. In contrast, the direct-estimation approach estimates the fairness property directly from queried responses, without first reconstructing the model. This distinction is particularly relevant when the auditor is used to verify whether a model update changes the property under audit. In the reconstruction-based approach, the learned surrogate can be used to check whether the updated model agrees with the pre-audit model on the set of points used for the plug-in estimation. However, this set is also used during model reconstruction and has size scaling as (dε2log1μ).O\! ( d ^2 1μ ). Consequently, requiring the updated model to agree with the original model on this large set of points can impose a substantially stronger constraint than requiring the fairness property itself to remain unchanged. In this sense, the reconstruction-based audit may effectively constrain the model update over a large portion of the input space, rather than merely verifying the stability of the property under audit. Algorithm 2 DirectAudit 1: I(h)=(h)I_M(h)=M(h), Query distribution D, budget T 2: for i=1,…,ki=1,…,k do 3: for t=1,…,Tt=1,…,T do 4: Sample Xt(i)∼⋅|iX_t^(i) _· _i ⊳ ⋅|iD_· _i: marginal distribution conditioned on group i. 5: Membership Query t(i)=h(Xt(i))M_t^(i)=h(X_t^(i)) ⊳ Alternatively, use random queries from the joint distribution. 6: end for 7: Estimate model behavior on every group μ^T(i)=1T∑t=1Tt(i). μ_T^(i)= 1T _t=1^TM_t^(i). 8: end for 9: Compute every pairwise component μ=(μ^T(i)−μ^T(j))1≤i<j≤kμ= ( μ_T^(i)- μ_T^(j) )_1≤ i<j≤ k 10: Return μ^=‖μ‖∞ μ=||μ||_∞ Organization. In Section 3, we introduce our setting for auditing multi-group fairness and formalize the intermediate step in which our proposed algorithm processes the given pool of unlabeled samples before issuing queries to the model owner. In Section 3.4, we derive upper and lower bounds for the auditing problem in the manipulation-free regime. In Section 3.5, we extend our analysis to the presence of a fairness-aware adversary and study the auditing problem under model manipulation. Finally, in Section 4, we provide an empirical evaluation of our proposed approach and compare its performance with the two baselines discussed above, ReconAudit, DirectAudit, as well as the auditing procedure proposed by Yan and Zhang, (2022) 33 3 The interaction protocol for (Yan and Zhang,, 2022) algorithm is given in Appendix F.2.. 3 Interpretable, Manipulation-Proof and Reconstruction-Free Audits with Bias Probes In this section, we introduce the auditing setting that will be used throughout the remainder of the paper. Rather than extracting audit-relevant information directly from the input space Z, we consider a conceptual framework in which such information is extracted over the product space of protected groups. This perspective allows us to design an auditing framework that focuses exclusively on the fairness property under audit, while providing interpretable audit information and mitigating the risk of model extraction. Lifting the Sample Pool to the Product Space. Let ≜∏i=1kiX _i=1^kZ_i denote the product space induced by the k protected subpopulations. An element =(x1,…,xk)∈x=(x_1,…,x_k) consists of one sample from each protected group, and X serves as the query space for auditing multi-group fairness (Definition 2.1). This perspective motivates a new auditing formulation in which the relevant information is represented by a class of functions defined directly on the query space, as introduced below: Definition 3.1 (Multi-Context Class). For a hypothesis class ℋH. The relative multi-context class induced by ℋH is defined as: ℱk(ℋ)=fh:→ℝ|fh()=k(h(x1),…,h(xk)),h∈ℋ,F_k(H)= \f_h:X \; |\;f_h(x)=M_k (h(x_1),…,h(x_k) ),\;h \, where kM_k is a fixed operator that depends on the property under audit. Remark 3.1. In fact, the operator kM_k performs a preliminary processing of the unlabeled pool, reorganizing and structuring the available information according to group membership for the auditing task. In our setting, this preprocessing is specific to the multi-group fairness property under audit, as illustrated in Figure 2, hence kM_k is a comparison operator. That is for every ∈x , fh()=(h(xi)−h(xj))1≤i<j≤kf_h(x)= (h(x_i)-h(x_j) )_1≤ i<j≤ k The resulting partition of available information is further depicted in Figure 3, which provides an overview of our auditing setting. h being a fixed model under audit, we will relax the notation and use f instead of fhf_h. This perspective naturally induces an interaction model between the auditor A and the model owner M. Unlike standard membership-query access, the auditor cannot query the model on individual points or observe its absolute predictions. Instead, the auditor submits a structured query ∈X , consisting of one sample from each protected group. The auditor’s access to the model is mediated by the oracle I()=k()I_M(X)=M_k(X), which, for our multi-group fairness property, returns only comparative evaluations across groups: k()=(fi,j())i≠jM_k(X)= (f_i,j(X) )_i≠ j. Thus, the auditor observes relative disparities between groups rather than the model’s absolute predictions. Definition 3.2 (Cross-Group Queries (CGQ)). Given access to a pool of unlabeled samples, a Cross-Group Query consists of selecting a tuple ∈X formed by choosing one sample from each protected group. The response to X is the collection of pairwise comparisons (fi,j())i≠j (f_i,j(X) )_i≠ j. Kane et al., (2017) proposed a related type of query in the context of active classification with linear separators. Their comparison queries consist of presenting a pair of points to an oracle, which indicates which point lies closer to the decision boundary. In our setting, instead, the auditor presents a pair of points from different groups to the model owner, who identifies the pair exhibiting the largest fairness disparity. Figure 2: Interactive Fairness Auditing via Group-Based Pool Partitioning. Coupling and Sampling Invariance. We now formalize the role of the operator kM_k in Definition 3.1, in other words, the role of sampling strategies over the product space from the pool Q. Let ν be any probability measure on X whose marginals satisfy νi(⋅)=(⋅∣i) _i(·)=D(· _i) for every i∈[k]i∈[k]. Let νi,j _i,j denote the corresponding pairwise marginal on i×jZ_i×Z_j. The following result shows that the choice of coupling does not affect the value of μ. Proposition 3.1 (Coupling Invariance). Let μ denotes multi-group fairness defined in 2.1. Let ν∈Π(ν1,…,νk)ν∈ ( _1,…, _k) be any coupling measure on X whose iith marginal satisfies νi(⋅)=(⋅∣i), _i(·)=D(· _i), for all i∈[k]i∈[k]. The following holds: μ(h,)=‖∼ν[fh()]‖∞μ(h,D)= \|E_X ν[f_h(X)] \|_∞ This invariance implies that auditing multi-group fairness can be carried out without modeling the joint distribution across groups, and justifies the use of arbitrary coupling strategies when constructing queries from the sample pool. Proof Let ν∈Π(ν1,…,νk)ν∈ ( _1,…, _k) be any coupling measure on X whose iith marginal satisfies νi(⋅)=(⋅∣i), _i(·)=D(· _i), for all i∈[k]i∈[k] For i≠ji≠ j, let νij _ij denote the (i,j)(i,j) marginal of ν on i×jZ_i×Z_j. By definition, fh()=(h(Xi)−h(Xj))1≤i<j≤k.f_h(X)= (h(X_i)-h(X_j) )_1≤ i<j≤ k. Since expectation of a finite-dimensional random vector is taken componentwise, ∼ν[fh()] _X ν [f_h(X) ] =(∼ν[h(Xi)−h(Xj)])1≤i<j≤k = (E_X ν [h(X_i)-h(X_j) ] )_1≤ i<j≤ k =((Xi,Xj)∼νij[h(Xi)−h(Xj)])1≤i<j≤k = (E_(X_i,X_j) _ij [h(X_i)-h(X_j) ] )_1≤ i<j≤ k =(∫i×j(h(xi)−h(xj))dνij(xi,xj))1≤i<j≤k = ( _Z_i×Z_j (h(x_i)-h(x_j) )\,d _ij(x_i,x_j) )_1≤ i<j≤ k =(∫i×jh(xi)dνij(xi,xj)−∫i×jh(xj)dνij(xi,xj))1≤i<j≤k. = ( _Z_i×Z_jh(x_i)\,d _ij(x_i,x_j)- _Z_i×Z_jh(x_j)\,d _ij(x_i,x_j) )_1≤ i<j≤ k. Because the marginals of νij _ij are νi _i and νj _j, respectively, ∼ν[fh()] _X ν [f_h(X) ] =(∫ih(x)dνi(x)−∫jh(x)dνj(x))1≤i<j≤k = ( _Z_ih(x)\,d _i(x)- _Z_jh(x)\,d _j(x) )_1≤ i<j≤ k =(X∼(⋅∣i)[h(X)]−X∼(⋅∣j)[h(X)])1≤i<j≤k. = (E_X (· _i)[h(X)]-E_X (· _j)[h(X)] )_1≤ i<j≤ k. And because μij(h,):=X∼(⋅∣i)[h(X)]−X∼(⋅∣j)[h(X)], _ij(h,D):=E_X (· _i)[h(X)]-E_X (· _j)[h(X)], we therefore obtain ∼ν[fh()]=(μij(h,))1≤i<j≤kE_X ν[f_h(X)]= ( _ij(h,D) )_1≤ i<j≤ k Consequently, ‖∼ν[fh()]‖∞=max1≤i<j≤k|μij(h,)| \|E_X ν[f_h(X)] \|_∞= _1≤ i<j≤ k| _ij(h,D)| Therefore μ(h,)=‖∼ν[fh()]‖∞μ(h,D)= \|E_X ν[f_h(X)] \|_∞ ■ This reformulation shows that auditing multi-group fairness can be viewed as estimating expectations of pairwise comparison functionals under the product distribution. In particular, it shifts the objective from learning the model h itself to estimating the structured family of functional defined on X. The resulting interaction model differs fundamentally from reconstruction-based approaches: rather than approximating h over the hypothesis class ℋH, the auditor directly probes the relational structure induced by h across protected groups. Remark 3.2. Although the value of the audited property is invariant to the choice of coupling, the coupling determines the distribution of the relational queries observed by the auditor and therefore the information available during the audit. We therefore treat the coupling as part of the audit design: a coupling ν∈Π(1,…,k)ν∈ (D_1,…,D_k) is selected before interaction and remains fixed throughout the auditing procedure, with CGQs sampled i.i.d. from ν. The auditor may adaptively decide which sampled CGQs to query, but may not adapt the coupling itself in response to previous oracle outputs. This restriction does not constrain the value of the fairness functional, which depends only on the protected-group marginals, but it fixes the statistical experiment through which that functional is learned. Allowing the coupling to change adaptively would define a strictly stronger query model in which the auditor can modify the distribution of future CGQs based on past responses, rather than merely perform active selection from a fixed data-generating distribution. 3.1 Interpretable Audits via Bias Probes To obtain interpretable insights into the model’s behavior, we introduce bias probes, which localize the comparative behavior of h across protected groups. Definition 3.3 (Bias Probes). Let =(x1,…,xk)∈x=(x_1,…,x_k) . • Global bias probe. The global bias probe is defined as f:↦(fi,j())i≠j.f (f_i,j(x) )_i≠ j. • Feature-wise bias profile. Let q∈[p]q∈[p] denote an unprotected feature, and Pq()=(X1(q),…,XK(q))P_q(X)= (X_1^(q),…,X_K^(q) ) the the projection of the CGQ query on the qthq^th feature. For each pair (i,j)(i,j), we define the conditional feature-wise probe q,i,j(z):=∼K[fi,j()∣Pq()=z] e_q,i,j(z):=E_X ^K [f_i,j(X) P_q(X)=z ] The vector q(z)=(q,i,j(z))i<j e_q(z)= ( e_q,i,j(z) )_i<j describes how the expected relational response of the deployed model varies with feature q. • Feature-wise bias magnitude. We summarize the conditional relational disparity by f~q(z):=maxi<j|q,i,j(z)|=maxi<j|[fi,j()∣Pq()=z]| f_q(z):= _i<j | e_q,i,j(z) |= _i<j |E [f_i,j(X) P_q(X)=z ] | Example 3.1 (Interpretable Audit Report via Unprotected Feature-wise Bias Probes). Consider a credit-lending setting in which a bank deploys a binary classifier h:→0,1h:X→\0,1\ to decide whether to grant a loan. Suppose that each client is represented by three unprotected input features, with monthly income and age corresponding to the first and second coordinates, respectively, and let gender be the protected attribute. For simplicity, assume two protected groups. A cross-group query is Q=(X1,X2)∈1×2,Q=(X_1,X_2) _1×X_2, where X1X_1 and X2X_2 are sampled from the two protected groups. The associated relational bias probe is f1,2(Q)=h(X1)−h(X2)∈−1,0,+1f_1,2(Q)=h(X_1)-h(X_2)∈\-1,0,+1\. The auditor observes this relational response rather than the two individual predictions separately. For an unprotected feature q, let Pq(Q):=(X1(q),X2(q)).P_q(Q):= (X_1^(q),X_2^(q) ). For example, P1(Q)=(X1(1),X2(1))P_1(Q)= (X_1^(1),X_2^(1) ) contains the monthly incomes of the two queried clients, while P2(Q)=(X1(2),X2(2))P_2(Q)= (X_1^(2),X_2^(2) ) contains their ages. The feature-wise bias profile is q(z1,z2):=[f1,2(Q)∣Pq(Q)=(z1,z2)], e_q(z_1,z_2):=E\! [f_1,2(Q) P_q(Q)=(z_1,z_2) ], and its unsigned magnitude is f~q(z1,z2):=|q(z1,z2)|. f_q(z_1,z_2):= | e_q(z_1,z_2) |. Thus, q e_q records the direction and magnitude of the conditional group prediction disparity, while f~q f_q records only its magnitude. The resulting audit report can combine the following complementary summaries: • Global bias probe. The global statistical-parity disparity is obtained from μ(h)=|[f1,2(Q)]|.μ(h)= |E[f_1,2(Q)] |. This provides an overall measure of the prediction-rate difference between the two protected groups. • Feature-wise bias profile. For a feature such as age or monthly income, the function mqm_q describes how the signed relational disparity varies across values of that feature. For example, 1(z1,z2) e_1(z_1,z_2) gives the expected relational response among cross-group queries whose two clients have monthly incomes near (z1,z2)(z_1,z_2). • Expected feature-wise bias magnitude. The quantity f~q(z1,z2)=|q(z1,z2)| f_q(z_1,z_2)=| e_q(z_1,z_2)| identifies regions of the projected feature space in which the conditional group disparity is large. For monthly income, it can therefore reveal income combinations for which the model exhibits particularly pronounced group-relative prediction differences; the same construction applies to age. Importantly, these quantities provide probe-level interpretability: they are estimable from projected CGQ feature values and relational probe responses. They should not be interpreted as ordinary predictive feature importance or as causal effects of the corresponding features on the classifier. Together, these three quantities provide complementary levels of evidence: the global probe establishes whether the model exhibits discrimination overall, the feature-wise probes indicate where disparities vary across the input space, and the expected feature-wise probes identify regions in which the disparities are most pronounced. The resulting audit report therefore provides the model owner not only with evidence of unfairness, but also with interpretable information about where and along which features that unfairness manifests itself. Bias probes thus provide a localized view of the model’s discriminative behavior, isolating how differences across groups manifest at specific feature configurations. While, the expected feature-wise bias probe represents the average intergroup comparison induced by h among all inputs sharing the same configuration on the unprotected feature q, providing a low-dimensional summary of the model’s discriminative behavior. We now formalize interpretable active auditing for general properties μ through the lens of comparison function learning. Definition 3.4 (Interpretable Active Auditing). Let P be a class of distributions over Z, and let ℱF be an intergroup context class defined over X. We say that ℱF is actively learnable under P if there exists a sample complexity function mℱ:(0,1)2→ℕm_F:(0,1)^2 , such that for all (ε,δ)∈(0,1)2( ,δ)∈(0,1)^2, for all ∈D , and for all m≥mℱ(ε,δ)m≥ m_F( ,δ), there exists an algorithm mA_m which, based on m queries 1,…,mQ_1,…,Q_m, outputs an estimate f^m∈ℱ f_m satisfying ℙ1,⋯m[ℰ(f^m)−inff∈ℱℰ(f)>ε]<δ, Q_1,·sQ_m P [E_D( f_m)- _f E_D(f)> ]<δ, where the risk ℰ(f)E_D(f) is defined as ℰ(f):=ℙ∼k[f()≠fh()]E_D(f):= X ^k P [f(X)≠ f_h(X) ], and fhf_h denotes the comparison functional induced by the model h. The minimax sample complexity of the auditing problem is defined as infmℱsup∈mℱ(ε,δ) _m_F _D m_F( ,δ), where the infimum is taken over all valid active auditing strategies. This formulation reduces the auditing problem for μ to the problem of learning the comparison functional fhf_h, from which μ(,h)μ(D,h) can be estimated as a functional of fhf_h. 3.2 Information Complexities For Learning Probes In the following section, we define the information-complexities relevant for characterizing the auditing problem of multi-group fairness. We begin with Natarajan dimension Daniely et al., (2015), that will serve to characterize global probe learning in the passive setting: Definition 3.5 (k-Daniely-Shwartz Dimension (Daniely et al.,, 2015)). • Pseudo-cube. Let B⊆mB ^m be finite and non-empty. Two vectors b,b′∈Bb,b ∈ B are called i-neighbors if bi≠bi′b_i≠ b _i and for every j≠ij≠ i, bj=bj′b_j=b _j. The set B is an m-dimensional pseudo-cube if for every b∈Bb∈ B and every i∈[m]i∈[m], b has an i-neighbor in B. • Daniely-Shwartz dimension. A sequence S=(1,…,m)∈kmS=(x_1,…,x_m) _k^m is DS-shattered by the k-context class ℱkF_k if the set ℱk|S=(f(1),…,f(m)):f∈ℱkF_k|_S=\(f(x_1),…,f(x_m)):f _k\ contains an m-dimensional pseudo-cube. Define Daniely-Shwartz dimension DSk(ℱ)DS_k(F) as the largest DS-shattered dimension, or ∞ if no finite largest dimension exists. For a fixed multi-context class ℱF, the disagreement set is defined as follows: DIS(ℱ)≜∈:∃f,f′∈ℱ:f()≠f′()DIS(F) \x :∃ f,f :f(x)≠ f (x)\. The disagreement sets arising in learning and auditing are objects of a different nature. In standard learning, the disagreement region is a subset of the sample space Z, reflecting uncertainty about the label of individual instances. In contrast, for multi-group fairness auditing, the disagreement set consists of pairs of elements drawn from distinct protected groups, encoding comparative uncertainty rather than pointwise ambiguity. This distinction originates from two structural differences: First, the input space in the auditing setting carries additional organization through the presence of a protected attribute, which induces a partition into groups. Second, the underlying model classes differ in purpose: in learning, the hypothesis class represents candidate models themselves, whereas in auditing it represents surrogate preference functionals capturing only the discriminative behavior of the fixed black-box model. Definition 3.6 (Multi-star Number). Let ℱF be a class of bias probes defined on X. The multi-star number k s_k is the largest value of m for which there exist distinct points i:i∈[m]\X_i:i∈[m]\, and functions f0∈ℱ,fi∈ℱf_0 , f_i , such that for all i∈[m]i∈[m], DIS(f0,fi)=iDIS(\f_0,f_i\)=\X_i\, and each component p of the multi-context vector X belongs to the protected group pZ_p, for p∈[k]p∈[k]. If no finite maximum exists, we set k=∞ s_k=∞. Examples of multi-star number for multi-context classes is given in Appendix A.3. We prove the following result for the linear classifiers induced multi-context class. Relationship between multi-star number and Daniely-Shwartz dimesnion. The following claim establishes that the multi-star number is upper bounded by the DS dimension. Consequently, when the DS dimension is infinite, passive learning of the probe class is impossible, and hence active learning is impossible as well. Later, we characterize active learnability of probes in the interactive setting induced by CGQs in terms of both these information complexities. In particular, we show that the finiteness of the multi-star number provides a necessary and sufficient condition for learning probes in this interactive setting. Claim 3.1. For an arbitrary multiclass ℱF, the following holds: k(ℱ)≤DSk(ℱ) s_k(F) _k(F) Proof Let S=1,2,⋯,mS=\x_1,x_2,·s,x_m\ denotes a DS-shattered set, B⊆ℱ[S]B [S] an m-dimensionnal cube, and fix b0∈Bb_0∈ B realizable by f0∈ℱf_0 in S. For every i in [m][m], by the pseudo-cube definition, there exists an i-neighbor bib_i in B of b. We have for every j∈[m]∖ij∈[m] \i\, bii≠bi0b^i_i≠ b^0_i and bji=bj0b^i_j=b^0_j. Let fif_i in ℱF a probe that realizes bib_i. That is fi|S=bif_i|_S=b^i. Since f0|S=b0f_0|_S=b^0, we obtain fi(i)=bii≠bi0=f0(i),f_i(x_i)=b^i_i≠ b^0_i=f_0(x_i), and for every j∈[m]∖ij∈[m] \i\, fi(j)=bji=bj0=f0(j).f_i(x_j)=b^i_j=b^0_j=f_0(x_j). Then for every i in [m][m], DIS(f0,fi)∩S=iDIS(\f_0,f_i\)∩ S=\x_i\. Hence S is also a star set of size m. By taking the supremum over DS-shattered S, we obtain the desired property. ■ 3.3 Information-Theoretic Separation of Reconstruction and Probe Auditing It is known that linear classifiers, even in low dimension input space (e.g., d=2d=2), the star number is unbounded, implying that active reconstruction-based auditing cannot improve over passive reconstruction and therefore requires a large number of queries, increasing the risk of model extraction. Proposition 3.2 establishes a separation between auditing via active reconstruction and bias probing, the latter avoiding this intrinsic complexity barrier by focusing on property-specific queries. Proposition 3.2 (Information-Theoretic Separation of Reconstruction and Probe Auditing). There exists an audit instance problem, where auditing via model reconstruction is strictly harder than auditing via probe learning. This establishes an information-theoretic separation between the two approaches: while reconstruction has unbounded combinatorial complexity for the underlying model class, the corresponding probe-learning problem admits a finite k-multi-star complexity. This aligns with the intuition that multi-group fairness is a global property driven primarily by the protected attribute, rather than the ambient feature space. The proof is given in Appendix A.4. 3.4 Manipulation-free Regime In this section, we focus on the manipulation-free regime, in which the model owner is honest and does not attempt to conceal unfairness. Figure 3: Interactive Fairness Auditing: Setting and Interaction Protocol 3.4.1 Hardness Results on Sample Complexity and Model Extraction We begin by establishing a lower bound on the sample complexity required to learn bias probes. Theorem 3.1 (Sample Complexity Lower Bound). Fix ε∈(0,1/4),δ∈(0,1/2) ∈(0,1/4),δ∈(0,1/2). For any (possibly randomized) active auditor making at most m≤Ω(max1−2δ1−δmink,⌊12ϵ⌋,[1−2ϵ−2δ(1−ϵ)]+DSk)m≤ ( \ 1-2δ1-δ \ s_k, 12ε \,\; [1-2ε-2δ(1-ε) ]_+DS_k \ ) CGQ queries, there exists a distribution D over X and a target comparison functional fh∗∈ℱf_h^* such that, with probability at least δ, ℙ1:m∼mk[ℙ∼k[f^1:m()≠fh()]>ε]>δ. Q_1:m ^mk P [ X ^k P [ f_Q_1:m(X)≠ f_h(X) ]> ]>δ. Theorem 3.1 shows that learning bias probes is fundamentally limited by the complexity of the comparison class ℱF. In particular, even in the active setting, the sample complexity must scale with intrinsic structural parameters such as k s_k. This highlights that auditing through comparison functionals does not circumvent statistical hardness, but rather shifts it to the geometry of the induced comparison class. The proof is given in Appendix C.1. 3.4.2 Hardness of Model Extraction Attacks In this section, we characterize the hardness of extracting the model underlying M from both computational and information-theoretic perspectives. Computational Hardness. We now show that, beyond the statistical limitations established in Proposition 3.2, extracting the underlying model from bias probes is computationally hard. Our probe-based auditing procedure induces an interactive protocol in which the auditor interacts with the model owner through at most B cross-group queries (CGQs). We formalize the corresponding model-extraction problem through the following notion of B-Bounded Relational Extraction, that consists of: • Finite hypothesis class ℋ0=h1,…,hm,H_0=\h_1,…,h_m\, • Finite collection of admissible relational queries =1,…,r⊆,Q=\x_1,…,x_r\ , • The query budget of k-ALeBi B. Model owner’s model extraction corresponds to whether there exists a subset of queries ′⊆Q , such that |′|≤B|Q |≤ B and such that the answers to the queries in ′Q uniquely identify the unknown hypothesis in ℋ0H_0. Equivalently, the question is whether for any two different models h and g in ℋ0H_0 there exists CGQ queries ′Q that distinguish fhf_h from fgf_g. Thus, the goal is to make the map h⟼(fh(q))q∈Q′h (f_h(q) )_q∈ Q injective on ℋ0H_0. Theorem 3.2 (Hardness of Model Extraction via Bias Probes). Given a learned probe fh∈ℱℋf_h _H from a (black-box) interaction with a model owner M of h∈ℋh , recovering h is NP hard. Theorem 3.2 establishes a computational barrier to model extraction from bias probes. Recovering the underlying model h from CGQ-based queries is intractable. More precisely, finding a small set of CGQ sufficient for universal model extraction is NP-complete. This formalizes a separation between auditing and reconstruction: while bias probes suffice to estimate properties such as multi-group fairness, they do not reveal enough information to reconstruct the model efficiently. The proofn is given in Appendix B. Information-Theoretic Hardness. In this section, we quantify the information revealed about the model owner’s identity through interactions with the auditor. We assume that ℋH is finite and that the induced multi-context class relative to ℋH, denoted by ℱ=ℱℋF=F_H, is therefore also finite. We further assume a uniform prior over ℋH. Before the audit procedure begins, the uncertainty about the model identity is ℐ~0:=log2|ℋ| I_0:= _2|H| bits. After t interactions with M, the observed responses induce a version space t⊆ℋV_t containing the hypotheses consistent with all interactions observed so far. Under the uniform prior, the remaining model identity uncertainty is therefore ℐ~t:=log2|t| I_t:= _2|V_t|. This motivates the following definition of identity leakage. Definition 3.7 (Identity Leakage). For a hypothesis class ℋH, the identity leakage after t interactions between the auditor and the model owner is defined as ℐt:=ℐ~0−ℐ~t=log2|ℋ||t|.I_t:= I_0- I_t= _2 |H||V_t|. For example, suppose the auditor knows that the model belongs to a hypothesis class of size |ℋ|=1000|H|=1000. If, after t interactions with the model owner, only |t|=20|V_t|=20 hypotheses remain consistent with the observed responses, then the identity leakage is ℐt=log2100020≈5.64bits.I_t= _2 100020≈ 5.64~bits. Thus, the audit interactions have reduced the uncertainty about the model identity by approximately 5.645.64 bits. In Section 4, we design an experimental protocol to evaluate model extraction through identity leakage. We compare our proposed auditor with three baselines: ReconAudit, DirectAudit, and the auditing method proposed by (Yan and Zhang,, 2022). 3.4.3 Algorithm Design: k-ALeBi and Upper Bounds Algorithm 3 k-ALeBi 1: Access to I(h)=k(h)I_M(h)=M_k(h), CGQ fixed coupling distribution ν, multi-context probe class ℱF, pool budget n 2: Initialize version space 0←ℱV_0 3: for t=1t=1 to n do 4: Draw independently (t)=(X1(t),…,Xk(t))∼νX^(t)=(X_1^(t),…,X_k^(t)) ν 5: t←t−1V_t _t-1 6: if (t)∈DIS(t−1)X^(t) (V_t-1) then 7: Query the relational oracle (t)←k(h,(t))=fh((t))Y^(t) _k(h;X^(t))=f_h(X^(t)) ⊳ (t)∈−1,0,1(k2)Y^(t)∈\-1,0,1\ k2 8: Update the version space t←f∈t−1:f((t))=(t)V_t← \f _t-1:f(X^(t))=Y^(t) \ 9: end if 10: end for 11: Select a global relational probe f^∈n f _n 12: Compute (fq,f~q)q∈[p]\(f_q, f_q)\_q∈[p] for all unprotected features q 13: return =(f⏟^global bias probe,fqq∈[p]⏟feature-wise bias probes,f~qq∈[p]⏟expected feature-wise bias probes) AuditReport= ( f_global bias probe, \f_q\_q∈[p]_feature-wise bias probes, \ f_q\_q∈[p]_expected feature-wise bias probes ) Theorem 3.3 (Upper bounds of ALeBi). k-ALeBi is a PAC active auditor: with probability at least 1−δ1-δ, it outputs f f satisfying ℙf^(Z)≠fh∗(Z)≤ϵ P \ f(Z)≠ f_h^*(Z) \≤ε using at most (minn,(e−1)mink,nlogenmink,n+log2δ+1,mink,n1∨logmink,nDSklog(en(2k−2)DSk))O ( \n,\;(e-1) \ s_k,n\ en \ s_k,n\+ 2δ+1,\; \ s_k,n\1 \ s_k,n\\,DS_k ( en(2^k-2)DS_k ) \ ) queries. where n=⌈DSk+log(4/δ)ϵ⌉.n= DS_k+ (4/δ)ε . For fixed sufficiently small δ, the lower bound in Theorem 3.1 becomes Ω(maxDSk,mink,1/ϵ) ( \DS_k, \ s_k,1/ε\\ ), while the upper bound becomes O~(mink,DSkϵ) O ( \ s_k, DS_kε\ ). If m denotes the sample complexity, and if ϵ≲1/kε 1/ s_k, then k≲m≲klogeDSkϵk, s_k m s_k eDS_kε s_k, and the bounds match up to logarithmic factors. If 1/k≲ϵ≲1/DSk1/ s_k ε 1/DS_k, then 1ϵ≲m≲DSkϵ, 1ε m DS_kε, with a smaller logarithmic gap whenever ϵk=(1)ε s_k=O(1). Finally, if ϵ≳1/DSkε 1/DS_k, then DSk≲m≲DSk/ϵ,DS_k m _k/ε,. In particular m reduces to Θ(DSk) (DS_k) for constant accuracy. Thus the only potentially substantial gap occurs in the intermediate regime and is controlled by the separation between sks_k and DSkDS_k; in particular, if DSk=O(1)DS_k=O(1) or k=Θ(DSk) s_k= (DS_k), the upper and lower bounds match up to logarithmic factors throughout the accuracy range. Theorem 3.3 further reveals two distinct regimes. When k=∞ s_k=∞, the active learning component of the bound vanishes, and the complexity is governed by the passive learning term DSk(ℱ)DS_k(F). In this regime, the auditing problem effectively reduces to passive learning of the probe class, as established by Claim 3.1. The proof of Theorem 3.3 is given in Appendix C.2. The following corollary characterizes the learnability of the probe class in the interactive setting in terms of the multi-star number. Corollary 3.1. A multi-class ℱF is PAC actively learnable (Definition 3.4) if and only if k(ℱ)<∞ s_k(F)<∞. Corollary 3.1 derives from Theorems 3.1 and 3.3. In Section 4, we evaluate the accuracy of k-ALeBi in estimating multi-group fairness (Definition 2.1) and compare its performance with three baselines: ReconAudit, DirectAudit, and the auditing method proposed by (Yan and Zhang,, 2022). 3.5 Fairness-aware Adversarial Regime We now consider an adaptive adversarial model owner M whose decision to attack depends on the auditor’s current estimate of multi-group disparity. The robust version of k-ALeBi requires that each CGQ admits a sufficiently homogeneous neighborhood of nonnegligible probability mass. For any CGQ X in Q 44 4 Hereafter, Q denotes the pool of unlabeled CGQs., ()J(X) denotes a cell from the input space containing X. Assumption 3.1 (Local ℱF replicability). There exists a measurable neighborhood map ↦J()⊆X J(X) chosen independently of the unknown target f⋆f and before observing any M oracle response, such that every requested CGQ X by A satisfies a probability mass of: ℙ(())≥γ P (J(X))≥γ and supf∈ℱℙ(f(′)≠f()|′∈())≤ρ _f P \! (f(X )≠ f(X)\, |\,X (X) )≤ρ for some γ>0γ>0 and 0≤ρ<12.0≤ρ< 12. Assumption 3.1 means that a draw from ()J(X) has the same clean query response as X uniformly over ℱF with probability at least 1−ρ1-ρ. The cells do not need to form a partition and may overlap. We assume that the learner can sample ′∼Q(⋅∣())X _Q(· (X)) from the i.i.d unlabeled pool 55 5 this can be implemented via rejection sampling.. Since ℙ(())≥γ P (J(X))≥γ, each accepted local CGQ requires at most 1/γ1/γ unlabeled draws in expectation. Algorithm 4 Robust k-ALeBi 1: k-ALeBi, attack bound p, fixed cell map ↦()X (X) 2: if p=0p=0 then 3: Run subroutine k-ALeBi 4: Whenever k-ALeBi requests CGQ tX_t, query tX_t directly and return the clean response to k-ALeBi 5: return the output of k-ALeBi 6: end if 7: Configure k-ALeBi with confidence δ/2δ/2 8: N←N0(ϵ,δ/2)N← N_0(ε,δ/2) 9: R←⌈2(1−2β)2log2Nδ⌉R← 2(1-2β)^2 2Nδ 10: while k-ALeBi has not terminated do 11: Let tX_t be the next CGQ requested by k-ALeBi 12: Y^t←LocalLabel(t,(t),R) Y_t← LocalLabel(X_t,J(X_t),R) 13: Feed tY_t to k-ALeBi as the simulated clean response f⋆(t)f (X_t) 14: end while 15: return the output of k-ALeBi 16: 17: 18: Subroutine LocalLabel 19: 20: Input: CGQ q, fixed cell grid J(q)J(q), local budget R 21: for r=1,…,Rr=1,…,R do 22: Sample independently r′∼Q(⋅∣())X _r _Q(· (X)) 23: Query the attacked oracle at r′X _r and receive r∈kY_r _k 24: end for 25: return Y^(q)∈argmaxy∈k∑r=1Rr=y Y(q)∈ _y _k _r=1^R1\Y_r=y\ 3.5.1 Adaptive Fairness-aware Adversary: Algorithm and Upper Bounds For the r-th local query r′X _r, let Ar∈0,1A_r∈\0,1\ denote whether its response is attacked. Let ℍr−1H_r-1 denote the complete history before that response. If Ar=0A_r=0, then r=f⋆(r′).Y_r=f (X _r). If Ar=1A_r=1, the adversary may return any r∈kY_r _k, possibly as an adaptive function of the history, the queried CGQ r′X _r and its clean response. Definition 3.8 (Conditional probabilistic attack). There exists p<1/2p<1/2 such that ℙ(Ar=1|ℍr−1,r′,f⋆(r′))≤p P \! (A_r=1\, |\,H_r-1,X _r,f (X _r) )≤ p for every local query. In particular, the conditional bound is stronger than the nonadaptive assumption ℙ(Ar=1)≤p P (A_r=1)≤ p. We introduce the quantity β≜ρ+(1−ρ)p=p+ρ−pρβ ρ+(1-ρ)p=p+ρ-pρ, that accounts for both sources of error: the local clean response may differ from the response at q, or a locally correct response may be corrupted. By Definition 3.8, β<12.β< 12. We derive upper bounds for Algorithm 4. Theorem 3.4 (Neighborhood robustification). Let N0(ε,δ0)N_0( , _0) denote the upper bounds derived in Theorem 3.3. Under assumptions 3.1 and the assumption that p<1/2p<1/2 (Definition 3.8), Robust k-ALeBi is a (Robust) PAC-active auditor For p>0p>0, a sample complexity of (N0(ε,δ/2)⌈2(1−2β)2log2N0(ε,δ/2)δ⌉)O (N_0( ,δ/2) 2(1-2β)^2 2N_0( ,δ/2)δ ) suffices in the presence of fairness-aware adversarial model owner. If the neighborhood samples are obtained by rejection sampling from an i.i.d unlabeled stream, the expected number of unlabeled draws is at most ⌈2N0(ϵ,δ/2)γ(1−2β)2log2N0(ε,δ/2)δ⌉ 2N_0(ε,δ/2)γ(1-2β)^2 2N_0( ,δ/2)δ Theorem 3.4 characterizes the additional query cost incurred when the model owner is adversarial and attempts to conceal the unfairness of the model. This cost is governed by the corruption parameters, in particular the corruption level β and the probability mass γ of the cells that reveal the corruption mechanism. Together, these quantities determine how difficult it is for the auditor to obtain sufficiently informative observations to detect the model owner’s concealment of unfairness. The proof is given in Appendix D. The dependence of the query complexity on these parameters is intuitive. In particular, the sample complexity increases as the corruption parameter β decreases: when the model owner has a greater ability to manipulate the oracle responses, the auditor requires additional queries to dilute the effect of these corruptions and recover reliable information about the property under audit. Similarly, when the probability mass γ of the informative cells is small, the auditor encounters such cells less frequently. Consequently, the rejection-sampling procedure requires more queries to obtain a sufficient number of samples from these low-probability regions. Thus, the query overhead captures two complementary difficulties faced by the auditor: the extent to which the model owner can corrupt the observations and the rarity of the regions in which such corruption can be revealed. For every unlabeled CGQ ∈x , we associate a cell ()J(x), where the collection of distinct cells satisfies |()∈|≪|| |J(x)_x | |Q|. This collection of cells is constructed before any interaction takes place between the auditor and the model owner; in particular, its construction does not depend on the current active version space or on any target responses observed during the audit. Robust k-ALeBi proceeds by first running k-ALeBi to select a query x that induces disagreement over the probe space. It then invokes an additional sampling subroutine that independently draws multiple queries from the same cell ()J(x) and submits them to the model owner’s oracle. The auditor subsequently aggregates the oracle responses within this cell, and uses it as the effective label associated with ()J(x). The rationale behind this construction is that it exploits regularities of the model class (e.g., finite VC dimension, linearity) that allow the model owner to generalize from observed data in the first place. Consequently, a sufficient number of CGQs within the same cell are expected to exhibit consistent model behavior. This dilutes the effect of adversarial corruption during the interaction, and further exposes the model owner’s unfairness allowing the auditor to obtain information about the target property. 3.5.2 Global Information-theoretic Hardness The star number in Definition 3.6 alone does not necessarily yield a property-specific lower bound for multi-group fairness. In particular, distinct probe functions may disagree substantially while inducing the same statistical-parity functional across all (k2) k2 group pairs. To capture the information complexity that is specific to multi-group fairness, we introduce the following notion. Definition 3.9 (Fairness-effective star number). The fairness-effective star number μ(ℱ) s_μ(F) is the supremum of all integers m, for which there exist distinct CGQs 1,…,mx_1,…,x_m and functions f0,…,fm∈ℱf_0,…,f_m such that for every j∈[m]j∈[m], f0(j)=f_0(x_j)=0 and, for every i∈[m]i∈[m], fi(i)≠f_i(x_i) 0, and j≠ij≠ i, fi(j)=f_i(x_j)=0. Definition 3.9 introduces a property-specific notion of disagreement. Rather than distinguishing probes according to whether they favor or disadvantage particular group pairs, as in the standard disagreement-based formulation, we distinguish only between probes that are fair and those that are unfair on the star set. This formulation captures the information that is directly relevant to the fairness property, while abstracting away disagreements that do not affect the fairness functional of interest. Now, we state an assumption required to derive the lower bound for robust fairness estimation with CGQs under conditional probabilistic attack. Assumption 3.2 (Cell-replicability on the star set). The fairness-effective star set has pairwise disjoint measurable cells 1,…,mJ_1,…,J_m such that, for every witness fif_i and every cell jJ_j, fif_i is constant on jJ_j and equals its value at jx_j. Assumption 3.2 captures a regularity condition on the probe induced by the black-box model h∗h^*. Specifically, it assumes that the model exhibits sufficiently consistent behavior within each cell: conditional on a cell, the model’s responses do not vary substantially across queries. Thus, queries belonging to the same cell tend to preserve the relevant regularities of the underlying model behavior, which enables the auditor to replicate the probe’s response from multiple samples within that cell. Theorem 3.5 (Fairness lower bound under probabilistic attack). Under Assumption 3.2 and p<1/2p<1/2. A set of CGQs of size Ω(minμ(ℱ),1ε) \! ( \ s_μ(F), 1 \ ) is necessary to learn the undelrying probe. In Section 4, we evaluate Robust k-ALeBi and compare its performance with k-ALeBi, ReconAudit and the auditing method proposed by Yan and Zhang, (2022) in the fairness-aware adversarial regime. 4 Experimental Analysis We empirically evaluate our framework along three axes: the accuracy of learned bias probe, multi-group fairness estimation via bias probes and the sample and computation efficiency of the proposed interactive procedure. Given a dataset D, we first train three classifiers h —linear model, random forest, or multi-layer perceptron (MLP). We then generate a labeled dataset by querying h on unlabeled samples. Using this dataset, we perform interactive learning of bias probes associated with multi-group fairness. From the learned probes, we estimate the fairness metric μ(,h)μ(D,h) and report the estimation error along with explanations for the audit report. Datasets and experimental details. We evaluate our theoretical results on three well-known benchmark datasets: COMPAS, German Credit and Student. For the COMPAS dataset, introduced in the context of recidivism risk assessment Angwin et al., (2022), the number of groups is fixed to k=2k=2, while for the German Credit dataset, originating from the Statlog German Credit benchmark dataset Hofmann, (1994)., we consider k=4k=4 groups. In Appendix F, we further extend our analysis to synthetic datasets with multiple values of k. Evaluation details and reproducibility. As a benchmark, we compare k-ALeBi against the two baselines, DirectAudit and ReconAudit. For each binary classifier, we construct a dataset and use it as a pool of unlabeled samples, which we partition into k group-specific pools. k-ALeBi uses these pools to selectively construct informative CGQ queries. Each experiment is run with 10 random seeds to ensure reproducibility. Table 1: Clean-audit summary at budget B=60B=60 and H=500H=500. Error entries are mean ± 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. Probe-CAL Reconstruction-CAL Direct Audit-CAL Finite-H CAL Dataset Groups Model Probe error Fairness error ms Fairness error ms Fairness error ms Fairness error ms Fairness error ms COMPAS 2 Linear 0.0004±0.00080.0004± 0.0008 0.0165±0.01080.0165± 0.0108 101.4 0.0003±0.00060.0003± 0.0006 6.1 0.0984±0.08650.0984± 0.0865 0.5 0.0000±0.00000.0000± 0.0000 237.2 0.0000±0.00000.0000± 0.0000 187.4 MLP 0.0004±0.00080.0004± 0.0008 0.0178±0.01010.0178± 0.0101 240.3 0.0000±0.00000.0000± 0.0000 6.8 0.1126±0.09490.1126± 0.0949 0.5 – – – – RF 0.0000±0.00000.0000± 0.0000 0.0217±0.01440.0217± 0.0144 77.6 0.0000±0.00000.0000± 0.0000 5.6 0.1282±0.07590.1282± 0.0759 0.5 – – – – German Credit 4 Linear 0.0000±0.00000.0000± 0.0000 0.0277±0.02350.0277± 0.0235 260.2 0.0000±0.00000.0000± 0.0000 2.1 0.2258±0.11480.2258± 0.1148 0.5 0.0000±0.00000.0000± 0.0000 39.1 0.0000±0.00000.0000± 0.0000 26.9 MLP 0.0000±0.00000.0000± 0.0000 0.0098±0.00280.0098± 0.0028 661.7 0.0000±0.00000.0000± 0.0000 2.0 0.1326±0.05710.1326± 0.0571 0.4 – – – – RF 0.0000±0.00000.0000± 0.0000 0.0285±0.00910.0285± 0.0091 37.5 0.0000±0.00000.0000± 0.0000 1.9 0.1790±0.05700.1790± 0.0570 0.4 – – – – Student 2 Linear 0.0000±0.00000.0000± 0.0000 0.0162±0.01160.0162± 0.0116 38.5 0.0000±0.00000.0000± 0.0000 0.8 0.0414±0.02810.0414± 0.0281 0.4 0.0000±0.00000.0000± 0.0000 12.3 0.0000±0.00000.0000± 0.0000 10.7 MLP 0.0000±0.00000.0000± 0.0000 0.0172±0.00600.0172± 0.0060 179.7 0.0000±0.00000.0000± 0.0000 1.0 0.1110±0.07540.1110± 0.0754 0.5 – – – – RF 0.0000±0.00000.0000± 0.0000 0.0227±0.01010.0227± 0.0101 14.3 0.0000±0.00000.0000± 0.0000 0.8 0.0954±0.04990.0954± 0.0499 0.4 – – – – Notes. Probe error is defined only for Probe-CAL because the other baselines do not directly learn the relational probe. Audit-CAL is the finite-H fairness-targeted Yan–Zhang adaptation; it and the corresponding Finite-H CAL baseline were evaluated only for linear models. The shared continuous-linear experiment is not merged into this table because it uses a different hypothesis family and budget (B=500B=500). Runtime was benchmarked after the original experiments using the saved prediction matrices, so it measures auditing cost rather than training cost. Boldface compares fairness-estimation error and runtime separately within each row; it does not imply an overall ranking across accuracy and computational cost. 4.1 Accuracy Across the three datasets, k-ALeBi is competitive with the baselines of DirectAudit and ReconAudit in the accuracy of multi-group fairness estimation while requiring only few CGQs. As Figure 4 shows, after 10001000 queries k-ALeBi generally achieved substantially smaller estimation error than the the baselines, although reconstruction could achieve essentially zero error when it successfully recovered the target within the finite candidate class. Figure 4: Estimation Error of Multi-group fairness under limitted budget. We further evaluate k-ALeBi against DiamAudit, the auditing method proposed by Yan and Zhang, (2022), in its applicable setting of k=2k=2 protected groups and a linear hypothesis class, corresponding to statistical parity. Figure 5 shows that k-ALeBi achieves lower statistical parity estimation error than DiamAudit on both datasets. On COMPAS, k-ALeBi achieves an estimation error of 0.00002130.0000213, compared with 0.0000460.000046 for DiamAudit. On the Student dataset, k-ALeBi achieves an estimation error of 0.0069470.006947. Figure 5: Estimation Error of DiamAudit under Its Applicable Setting 4.2 Interpretability In addition to estimating multi-group fairness, k-ALeBi provides an interpretation of the measured unfairness that can’t be obtained from a scalar fairness estimate alone. Its interpretability outputs decompose the learned probe across non-protected features and characterize how different feature configurations affect the CGQs response. For a feature q, let Zq(Q)=(X1(q),…,XK(q))Z_q(Q)=(X_1^(q),…,X_K^(q)) and recall q,ij(z)=[fij(Q)∣Zq(Q)=z] e_q,ij(z)=E[f_ij(Q) Z_q(Q)=z], f~q(z)=maxi<j|mq,ij(z)|. f_q(z)= _i<j|m_q,ij(z)|. We estimate these conditional means using independent i.i.d CGQs and K-nearest-neighbor regression at the observed ZqZ_q configurations. For K=2K=2, we additionally visualize f~q(z1,z2) f_q(z_1,z_2) using Gaussian-kernel surfaces. Importantly, k-ALeBi observes CGQs responses rather than individual model predictions. Figure 6 ranks features according to the mean across used seeds of the 90th90^th percentile of the estimated f~q(Zq) f_q(Z_q). The corresponding feature-pair visualizations retain information about the direction and configuration of group disparities with respect to M that would otherwise be lost by reducing them to a single unsigned score. Thus the analysis identifies not only the features associated with larger measured disparities, but also the group pairs and feature configurations under which the learned model exhibits different CGQd responses. For the COMPAS dataset, Figure 7 indicates larger estimated disparities for individuals of non-Caucasian race who had been arrested multiple times, with the disparity varying across the number of prior arrests (n∈1,2,5n∈\1,2,5\). For the Student dataset, past-class failures and the amount of time spent going out are associated with larger gender-related disparities, with the estimated disparity being larger for females than for males. The feature ”father’s education” also exhibits a disparity pattern: higher levels of paternal education are associated with larger estimated differences in the model’s group disparities for males. 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. 4.3 Protection Against Model Extraction Attacks We next examine the distinction between accurately auditing fairness and revealing sufficient information to reconstruct the underlying model. At limited query budgets, Cross Group Queries can preserve a large version space of models with similar discriminative behavior while still providing accurate fairness estimates. This demonstrates an empirical separation between audit utility and immediate model identification: useful fairness information can be obtained without necessarily exposing the individual predictions required for direct model reconstruction. Figure 9: Identity leakage, measured by the number of individual model responses revealed to the auditor, comparing k-ALeBi with ReconAudit. Figure 9 compares the identity leakage induced by k-ALeBi and ReconAudit. ReconAudit uses membership queries by default, which directly expose individual model labels to the auditor. In contrast, k-ALeBi operates through relational CGQs and therefore does not directly reveal the corresponding individual labels. We quantify this information exposure using the identity-leakage measure defined in Definition 3.7. Across the evaluated query budgets, the results show substantially lower identity leakage for k-ALeBi than for ReconAudit, while retaining the ability to perform fairness auditing. 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 10 further compares k-ALeBi with DiamAudit. The first panel measures the fidelity of an extraction surrogate to the target model as individual predictions are exposed, while the second reports the number of absolute labels revealed to the attacker. These results illustrate the information advantage of relational auditing: k-ALeBi can provide useful fairness information through CGQs without requiring the same level of exposure of individual model predictions as membership-query-based extraction. Overall, the results indicate that CGQs can reduce the amount of model-identifying information exposed during auditing. This allows fairness properties to be investigated while limiting direct access to individual model responses, thereby separating the utility of fairness auditing from the immediate reconstruction of the underlying model. 4.4 Robustness against Fairness-Aware Adversaries Finally, we evaluate the robustness of Robust k-ALeBi against a fairness-aware adversary. On COMPAS-linear, for example, under a high corruption regime of p=0.40p=0.40, the adversary induces an average of 41.4 raw coordinate corruptions, of which only 6.2 result in corrupted queries after filtering. Despite these corruptions, the fairness estimation error increases only marginally, from 0.019 to 0.021, with no observed concealment across the five runs. In comparison, the reconstruction error of ReconAudit increases from 0, corresponding to exact model identification in the absence of corruption, to 0.074 under attack, with a concealment rate of 0.20. Figure 11: Local CGQ budget of Robust k-ALeBi across cells as a function of the attack probability. The Yan and Zhang, (2022) baseline exhibits an estimation error of 0.03 in the absence of attack, which increases to 0.05 under the strongest feasible attack probability, capped at 0.12. The same qualitative stability of Robust k-ALeBi is observed on the German-linear and Student-linear models. Figure 12: Estimation error for statistical parity as a function of the attack probability. 5 Conclusion In this work, we established an explicit separation between reconstruction-based and probe-based approaches to fairness auditing. We characterized the probe-learning problem through the multi-context star number and showed that, even when reconstruction-based auditing is infeasible for linear classifiers, the corresponding probe-based approach remains learnable, addressing Q1. Building on this formulation, we designed an auditing algorithm based on learning interpretable bias probes, providing audit information directly in terms of the fairness property of interest and addressing Q2. Finally, we analyzed the auditing problem in the presence of a fairness-aware adversary and established both upper and lower bounds on the resulting audit complexity, addressing Q3. Acknowledgments This work is supported by the Regalia project of Inria and French Ministry, ANR JCJC project REPUBLIC (ANR-22-CE23-0003-01), and the PEPR project FOUNDRY (ANR23-PEIA-0003). D. Basu would also like to acknowledge the Inria- ISI Kolkata associate team SeRAI for relevant motivation and discussions. References Agarwal et al., (2018) Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. (2018). A reductions approach to fair classification. In International conference on machine learning, pages 60–69. PMLR. Ailon, (2012) Ailon, N. (2012). An active learning algorithm for ranking from pairwise preferences with an almost optimal query complexity. Journal of Machine Learning Research, 13(1). Ajarra and Basu, (2026) Ajarra, A. and Basu, D. (2026). On the hardness of auditing model properties under updates: Complexity of property-preserving updates. In The 29th International Conference on Artificial Intelligence and Statistics. Alain and Bengio, (2016) Alain, G. and Bengio, Y. (2016). Understanding intermediate layers using linear classifier probes. arXiv preprint arXiv:1610.01644. Angluin, (1988) Angluin, D. (1988). Queries and concept learning. Machine learning, 2(4):319–342. Angwin et al., (2022) Angwin, J., Larson, J., Mattu, S., and Kirchner, L. (2022). Machine bias. In Ethics of data and analytics, pages 254–264. Auerbach Publications. Balcan et al., (2006) Balcan, M.-F., Beygelzimer, A., and Langford, J. (2006). Agnostic active learning. In Proceedings of the 23rd international conference on Machine learning, pages 65–72. Balcan et al., (2012) Balcan, M.-F., Blais, E., Blum, A., and Yang, L. (2012). Active property testing. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 21–30. IEEE. Banerjee et al., (2021) Banerjee, I., Bhimireddy, A. R., Burns, J. L., Celi, L. A., Chen, L.-C., Correa, R., Dullerud, N., Ghassemi, M., Huang, S.-C., Kuo, P.-C., et al. (2021). Reading race: Ai recognises patient’s racial identity in medical images. arXiv preprint arXiv:2107.10356. Barocas and Selbst, (2016) Barocas, S. and Selbst, A. D. (2016). Big data’s disparate impact. Calif. L. Rev., 104:671. Biswas and Rajan, (2020) Biswas, S. and Rajan, H. (2020). Do the machine learning models on a crowd sourced platform exhibit bias? an empirical study on model fairness. In Proceedings of the 28th ACM joint meeting on European software engineering conference and symposium on the foundations of software engineering, pages 642–653. Chen et al., (2016) Chen, M., Gao, C., and Ren, Z. (2016). A general decision theory for huber’s ϵε-contamination model. Electronic Journal of Statistics. Chugg et al., (2023) Chugg, B., Cortes-Gomez, S., Wilder, B., and Ramdas, A. (2023). Auditing fairness by betting. Advances in Neural Information Processing Systems, 36:6070–6091. Croce et al., (2020) Croce, F., Andriushchenko, M., Sehwag, V., Debenedetti, E., Flammarion, N., Chiang, M., Mittal, P., and Hein, M. (2020). Robustbench: a standardized adversarial robustness benchmark. arXiv preprint arXiv:2010.09670. Crowston et al., (2012) Crowston, R., Gutin, G., Jones, M., Saurabh, S., and Yeo, A. (2012). Parameterized study of the test cover problem. In International Symposium on Mathematical Foundations of Computer Science, pages 283–295. Springer. Daneshjou et al., (2022) Daneshjou, R., Vodrahalli, K., Novoa, R. A., Jenkins, M., Liang, W., Rotemberg, V., Ko, J., Swetter, S. M., Bailey, E. E., Gevaert, O., et al. (2022). Disparities in dermatology ai performance on a diverse, curated clinical image set. Science advances, 8(31):eabq6147. Daniely et al., (2015) Daniely, A., Sabato, S., Ben-David, S., and Shalev-Shwartz, S. (2015). Multiclass learnability and the erm principle. J. Mach. Learn. Res., 16(1):2377–2404. Dasgupta, (2004) Dasgupta, S. (2004). Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17. Dasgupta et al., (2007) Dasgupta, S., Hsu, D. J., and Monteleoni, C. (2007). A general agnostic active learning algorithm. Advances in neural information processing systems, 20. Ebers, (2025) Ebers, M. (2025). Truly risk-based regulation of artificial intelligence how to implement the eu’s ai act. European Journal of Risk Regulation, 16(2):684–703. (21) European Commission (2024a). The digital services act package. Technical report, European Union. (22) European Commission (2024b). Regulation on artificial intelligence (ai act). Final text adopted by the European Parliament. Freedman, (1975) Freedman, D. A. (1975). On tail probabilities for martingales. the Annals of Probability, pages 100–118. Garcia et al., (2024) Garcia, A. C. B., Garcia, M. G. P., and Rigobon, R. (2024). Algorithmic discrimination in the credit domain: what do we know about it? AI & society, 39(4):2059–2098. Garey et al., (1990) Garey, M. R., Johnson, D. S., et al. (1990). A guide to the theory of np-completeness. Computers and intractability, pages 37–79. Goldreich et al., (1998) Goldreich, O., Goldwasser, S., and Ron, D. (1998). Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653–750. Goodfellow et al., (2018) Goodfellow, I., McDaniel, P., and Papernot, N. (2018). Making machine learning robust against adversarial inputs. Communications of the ACM, 61(7):56–66. Guo et al., (2022) Guo, Y., Yang, Y., and Abbasi, A. (2022). Auto-debias: Debiasing masked language models with automated biased prompts. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1012–1023. Hanneke, (2014) Hanneke, S. (2014). Theory of disagreement-based active learning. Foundations and Trends in Machine Learning, 7(2-3):131–309. Hanneke and Yang, (2015) Hanneke, S. and Yang, L. (2015). Minimax analysis of active learning. The Journal of Machine Learning Research, 16(1):3487–3602. Hardt et al., (2016) Hardt, M., Price, E., and Srebro, N. (2016). Equality of opportunity in supervised learning. Advances in neural information processing systems, 29. Harwell, (2022) Harwell, D. (2022). A face-scanning algorithm increasingly decides whether you deserve the job. In Ethics of Data and Analytics, pages 206–211. Auerbach Publications. Hofmann, (1994) Hofmann, H. (1994). Statlog (german credit data). UCI Machine Learning Repository, 10:C5NC77. Immer et al., (2022) Immer, A., Hennigen, L. T., Fortuin, V., and Cotterell, R. (2022). Probing as quantifying inductive bias. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1839–1851. Jagielski et al., (2020) Jagielski, M., Carlini, N., Berthelot, D., Kurakin, A., and Papernot, N. (2020). High accuracy and high fidelity extraction of neural networks. In 29th USENIX security symposium (USENIX Security 20), pages 1345–1362. Kane et al., (2017) Kane, D. M., Lovett, S., Moran, S., and Zhang, J. (2017). Active classification with comparison queries. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 355–366. IEEE. Kearns et al., (2018) Kearns, M., Neel, S., Roth, A., and Wu, Z. S. (2018). Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International conference on machine learning, pages 2564–2572. PMLR. Kusner et al., (2017) Kusner, M. J., Loftus, J., Russell, C., and Silva, R. (2017). Counterfactual fairness. Advances in neural information processing systems, 30. Liu and Moitra, (2025) Liu, A. and Moitra, A. (2025). Model stealing for any low-rank language model. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1755–1761. Lundberg and Lee, (2017) Lundberg, S. M. and Lee, S.-I. (2017). A unified approach to interpreting model predictions. Advances in neural information processing systems, 30. Manerba et al., (2024) Manerba, M. M., Stańczak, K., Guidotti, R., and Augenstein, I. (2024). Social bias probing: Fairness benchmarking for language models. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 14653–14671. Mao et al., (2023) Mao, A., Mohri, M., and Zhong, Y. (2023). h-consistency bounds for pairwise misranking loss surrogates. In International conference on Machine learning, pages 23743–23802. PMLR. Montasser et al., (2021) Montasser, O., Hanneke, S., and Srebro, N. (2021). Adversarially robust learning with unknown perturbation sets. In Conference on Learning Theory, pages 3452–3482. PMLR. Morehouse et al., (2025) Morehouse, K. N., Swaroop, S., and Pan, W. (2025). Rethinking llm bias probing using lessons from the social sciences. arXiv preprint arXiv:2503.00093. New York State Senate, (2024) New York State Senate (2024). S8612: An act to regulate automated decision-making tools. (46) Orekondy, T., Schiele, B., and Fritz, M. (2019a). Knockoff nets: Stealing functionality of black-box models. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4954–4963. (47) Orekondy, T., Schiele, B., and Fritz, M. (2019b). Prediction poisoning: Towards defenses against dnn model stealing attacks. arXiv preprint arXiv:1906.10908. Pabbaraju, (2026) Pabbaraju, C. (2026). The optimal sample complexity of multiclass and list learning. arXiv preprint arXiv:2604.24749. Park et al., (2015) Park, D., Neeman, J., Zhang, J., Sanghavi, S., and Dhillon, I. (2015). Preference completion: Large-scale collaborative ranking from pairwise comparisons. In International Conference on Machine Learning, pages 1907–1916. PMLR. Ribeiro et al., (2016) Ribeiro, M. T., Singh, S., and Guestrin, C. (2016). ” why should i trust you?” explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144. Seyyed-Kalantari et al., (2021) Seyyed-Kalantari, L., Zhang, H., McDermott, M. B., Chen, I. Y., and Ghassemi, M. (2021). Underdiagnosis bias of artificial intelligence algorithms applied to chest radiographs in under-served patient populations. Nature medicine, 27(12):2176–2182. Tramèr et al., (2016) Tramèr, F., Zhang, F., Juels, A., Reiter, M. K., and Ristenpart, T. (2016). Stealing machine learning models via prediction \APIs\. In 25th USENIX security symposium (USENIX Security 16), pages 601–618. Tropp, (2011) Tropp, J. (2011). Freedman’s inequality for matrix martingales. Electronic Communications in Probability, 16(none):262 – 270. Vafa et al., (2025) Vafa, K., Chang, P. G., Rambachan, A., and Mullainathan, S. (2025). What has a foundation model found? using inductive bias to probe for world models. arXiv preprint arXiv:2507.06952. Vrudhula et al., (2024) Vrudhula, A., Kwan, A. C., Ouyang, D., and Cheng, S. (2024). Machine learning and bias in medical imaging: opportunities and challenges. Circulation: Cardiovascular Imaging, 17(2):e015495. Wilson and Caliskan, (2024) Wilson, K. and Caliskan, A. (2024). Gender, race, and intersectional bias in resume screening via language model retrieval. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, volume 7, pages 1578–1590. Yan and Zhang, (2022) Yan, T. and Zhang, C. (2022). Active fairness auditing. In International Conference on Machine Learning, pages 24929–24962. PMLR. Yao, (1977) Yao, A. C.-C. (1977). Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222–227. IEEE. Yuan et al., (2024) Yuan, X., Chen, K., Huang, W., Zhang, J., Zhang, W., and Yu, N. (2024). Data-free hard-label robustness stealing attack. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38(7), pages 6853–6861. Yuan et al., (2022) Yuan, X., Ding, L., Zhang, L., Li, X., and Wu, D. O. (2022). Es attack: Model stealing against deep neural networks without data hurdles. IEEE Transactions on Emerging Topics in Computational Intelligence, 6(5):1258–1270. Zafar et al., (2017) Zafar, M. B., Valera, I., Rogriguez, M. G., and Gummadi, K. P. (2017). Fairness constraints: Mechanisms for fair classification. In Artificial intelligence and statistics, pages 962–970. PMLR. Zong et al., (2022) Zong, Y., Yang, Y., and Hospedales, T. (2022). Medfair: benchmarking fairness for medical imaging. arXiv preprint arXiv:2210.01725. Appendix Appendix A Extended Framework Description A.1 General Framework for Property Specific Audits Auditing ML models concerns a broad range of properties, including algorithmic fairness, robustness, etc. In a black-box setting, auditing a given property requires carefully designing the queries submitted to the model. Ideally, these queries should be informative about the property under audit while minimizing the amount of information they reveal about the model itself, thereby reducing the risk of model extraction. This principle can be applied to properties involving multiple groups, but we argue that it extends more generally to arbitrary classes of properties. For example, robustness can be interpreted as a two-group property, where an original input and its perturbed counterpart can be viewed as samples from two related groups (perturbed samples come from a ghost group). Figure 13: General Property-specific Audit Framework. More generally, as illustrated in Figure 13, the model owner can construct a pool of candidate samples that is designed to avoid leaking sensitive information about the model while remaining informative with respect to the property being audited. The auditor A can then select, from this pool, the samples that are most informative for the property of interest and submit the corresponding queries to the model owner M. This separation between sample pool construction and query selection allows the auditor to retain flexibility in designing the audit while giving the model owner control over the information exposed through the available queries. A.2 Information-theoretic and combinatorial separation between active learning and active auditing in the presence of protected groups Active learning of linear classifiers. It is known that the linear classifier learnability in the active setting fails even in 2 dimensions. Sangupta came up with a simple counterexample of why this happens; as Figure 14 shows, when considering a circular representation of data points there exists a strategy to construct an infinite star set. To see this, let h0h_0 be the center of the star set, one can observe that for all i∈[q]i∈[q], DIS(h0,hi)=xiDIS(h_0,h_i)=\x_i\. It is also easy to see that this occurs while q can go to infinity. This construction shows that the star number of linear classifiers class explodes to infinity just in two dimensions. Figure 14: 2D of linear classifier counterexample in the active leanring setting: the blue dots xix_i represent covariates, the dark lines represent classifiers hi.h_i. Active auditing in the presence of protected groups. In the presence of protected groups, an additional feature (protected feature) needs to be added to the setting. Therefore to reproduce this counter-example for the auditing problem, we add an additional feature, therefore ⊆ℝ3X ^3 as shown in Figure 15. We consider the scenario where =0×1×2X=X^0×X^1×X^2, 0X^0 denotes the protected feature while 1X^1 and 2X^2 denote the unprotected features. 10⊆X^0_1 (resp. 10X^0_1) denotes the first (resp. second) protected group. 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. It is easy to see that, in this setting the counterexample of Dasgupta, (2004) still applies in 3D. and therefore the star number is infinite. However, when we focus on solely extracting the discriminative behavior of h instead of the whole h (through active learning approaches), we avoid unnecessary information in the subspace of X where h is fair. In other words, the information h(x1)−h(x2)=0h(x_1)-h(x_2)=0 is equivalent to both h(x0)=h(x1)=0h(x_0)=h(x_1)=0 and h(x0)=h(x1)=1h(x_0)=h(x_1)=1 in the context of fairness auditing but not in the context of learning, this shows that auditing problem reduces significantly the number of dichotomies used in learning. To see why the dual-number corresponding to the audit problem illustrated in Figure 15, we reduce learning the overall bias canvas to learning canvas biases in each unprotected direction. The problem now reduces to the one explained in Example A.1, and the bias canvas in each direction is illustrated in Figure 16. Figure 16: Bias canvases of h in feature 1 (right) and in feature 2 (left). In this example the overall bias canvas is defined on the space 11×21×12×22⊆ℝ4X^1_1×X^1_2×X^2_1×X^2_2 ^4. A.3 Examples of relative dual classes and their star numbers from known hypothesis classes When the original model class is known, the dual context class can be defined explicitly based on the model class. In this scenario, we refer to relative dual context classes, where instead of searching for arbitrary preference functions modeling the discriminative behavior of the model, we restrict our search within dual classes that depend on the original model class. We provide two examples to compute the dual star number, one for linear classifiers and the other for axis-parallel rectangles. Example A.1 (Linear Classifiers as relative dual-context classes.). For the relative dual class of linear separators in dimension 2, ℱ2linF^lin_2, the dual star number is 22. To convince ourselves of that, consider the figure below. The preference function f0f_0 represents the center of the star set. It acts discriminatively on both the blue and red samples. For the red (resp. blue) sample, it prefers the one in 0X_0 (resp. the one in 1X_1). As the figure shows, f0,f1,f2\f_0,f_1,f_2\ consists of a star set for the dual-class ℱ(ℋℝ2lin)F(H^lin_R^2), since DISdualrel(f0,fi)=x(i)DIS^rel_dual(\f_0,f_i\)=\x^(i)\, for i∈1,2i∈\1,2\. It is easy to see that any new point of couples added to the partition of 0×1X_0×X_1 will increase the disagreement, therefore the star dimension is 22. Figure 17: Illustration of the dual star number for the dual class relative to ℋℝ2linH^lin_R^2. By the symmetry of ℱ2linF^lin_2, the same reasoning apply for points chosen on the fair region (green area) of the center preference f0f_0. Example A.2 (Axis-parallel rectangles as relative dual-context classes.). When the original model class consists of axis-parallel rectangles. The set of possible discriminative dichotomies increases. Consider the classification problem illustrated in Figure 18. One can observes that the same pattern of the previous examples repeats itself four times ( two times along Figure 18: Illustration of the dual star number for the dual class relative to ℋℝ2recH^rec_R^2. A.4 Mutli-star number of multi-context class relative to linear classifiers See 3.2 Proof Let ℋ=hw(X)=wX≥0:w∈ℝ∗2H= \h_w(X)= 1_wX≥ 0:w ^*2 \ be the class of homogeneous linear classifiers. Let R=(0−110)R= pmatrix0&-1\\ 1&0 pmatrix denote rotation by π/2π/2, and consider the following representation of protected groups domain R=1×2=(x,Rx):x∈ℝ∗2.X_R=Z_1×Z_2=\(x,Rx):x ^*2\. For h∈ℋh , we have the bias probe for our audit instance problem k=2k=2, fh(x,Rx)=h(x)−h(Rx)∈−1,0,+1,f_h(x,Rx)=h(x)-h(Rx)∈\-1,0,+1\, and let ℱR,ℋ=fh:h∈ℋF_R,H=\f_h:h \. We show that (ℋ)=∞,2(ℱℋ,R)=3. s(H)=∞, s_2(F_H,R)=3. The fact that (ℋ)=∞ s(H)=∞ for homogeneous linear separators in ℝ2R^2 is standard (Hanneke,, 2014). Thus it remains to compute the star number of the induced relational class ℱℋ,R F_H,R. Step 1: Angular representation of the 22-context class. Since the classifiers are homogeneous, only the directions of w and x matter. Let wθ=(cosθ,sinθ)w_θ=( θ, θ) and xϕ=r(cosϕ,sinϕ)x_φ=r( φ, φ), where r>0.r>0. Then wθxϕ=rcos(θ−ϕ).w_θx_φ=r (θ-φ). Since RxϕRx_φ has angle ϕ+π/2φ+π/2, wθ⊤Rxϕ=rcos(θ−ϕ−π2)=rsin(θ−ϕ).w_θ Rx_φ=r (θ-φ- π2 )=r (θ-φ). Consequently, fθ(ϕ)=sign(cos(θ−ϕ))−sign(sin(θ−ϕ)).f_θ(φ)=sign ( (θ-φ) )-sign ( (θ-φ) ). (1) We choose all probe and witness angles away from the transition points, so the value assigned to angle 00 is irrelevant. Let β=θ−ϕ(mod2π).β=θ-φ 2π. Then, fθ(ϕ)=+1,β∈(−π/2,0),0,β∈(0,π/2),−1,β∈(π/2,π),0,δ∈(π,3π/2).f_θ(φ)= cases+1,&β∈(-π/2,0),\\[2.84526pt] 0,&β∈(0,π/2),\\[2.84526pt] -1,&β∈(π/2,π),\\[2.84526pt] 0,&δ∈(π,3π/2). cases (2) Thus the 22-context class becomes the β translation class obtained by rotating the four-sector cyclic labeling +1,0,−1,0,+1, 0, -1, 0, with each sector having angular width π/2π/2. Step 2: Agreement sets relative to a probe. Fix a reference orientation θ0 _0. By rotational invariance, we may assume without loss of generality that θ0=0. _0=0. For every probe angle ϕφ, define its agreement set in parameter space by Aϕ=θ∈1:fθ(ϕ)=f0(ϕ).A_φ= \θ ^1:f_θ(φ)=f_0(φ) \. By construction, 0∈Aϕ0∈ A_φ for every ϕφ. Equation (2) shows that there are exactly two possible forms for AϕA_φ. • Discriminatory Probe: f0(ϕ)∈−1,+1f_0(φ)∈\-1,+1\: In this case the reference label occurs on exactly one sector of length π/2π/2. Hence Aϕ=Iϕ,A_φ=I_φ, where IϕI_φ is an arc of length π/2π/2 containing 00. • Fair Probe: f0(ϕ)=0f_0(φ)=0. The label 00 occurs on two antipodal sectors, each of length π/2π/2. Therefore Aϕ=Iϕ∪(Iϕ+π),A_φ=I_φ∪(I_φ+π), where again IϕI_φ is the unique component containing 00 and has length π/2π/2. Thus every probe has a local agreement interval IϕI_φ of length π/2π/2 containing the reference parameter 00. A Fair probe additionally has an antipodal copy of this interval on the two dimensional sphere. Step 3: An interval lemma. We use the following elementary fact. Lemma A.1. Let Ii=(ℓi,ri),i=1,…,m,I_i=( _i,r_i), i=1,…,m, be intervals on the real line satisfying ℓi<0<ri _i<0<r_i for every i. Suppose that, for an index i, there exists a point tit_i such that ti∈⋂j≠iIjbutti∉Ii.t_i∈ _j≠ iI_j t_i∉ I_i. Then i must be either an index attaining the largest left endpoint or an index attaining the smallest right endpoint. Consequently, at most two indices can satisfy this property. Proof Suppose ti∈⋂j≠iIj∖Ii.t_i∈ _j≠ iI_j I_i. Since every interval contains 00, either ti<ℓi<0t_i< _i<0 or ti>ri>0t_i>r_i>0. If ti<ℓit_i< _i, then ti∈Ijt_i∈ I_j for every j≠ij≠ i, so ℓj<ti<ℓi _j<t_i< _i for all j≠i.j≠ i. Hence ℓi>ℓj _i> _j for all j≠i,j≠ i, so i is the unique index with largest left endpoint. Similarly, if ti>rit_i>r_i, then ri<ti<rjr_i<t_i<r_j for all j≠ij≠ i, and therefore i is the unique index with smallest right endpoint. There can be at most one unique largest left endpoint and at most one unique smallest right endpoint. Hence at most two indices can possess such a private point. ■ Step 4: Upper bound (ℱair)≤3 s(Fair)≤ 3. Suppose that ϕ1,…,ϕm _1,…, _m form a star centered at f0f_0. By the definition of the star number, for every i∈[m]i∈[m] there exists an orientation θi _i such that fθi(ϕi)≠f0(ϕi),fθi(ϕj)=f0(ϕj)for all j≠i.f_ _i( _i)≠ f_0( _i), f_ _i( _j)=f_0( _j) all j≠ i. (3) Equivalently, θi∈⋂j≠iAϕj∖Aϕi. _i∈ _j≠ iA_ _j A_ _i. (4) We distinguish cases according to the number of discriminatory probes. • Case 1: There are no discriminatory probes. Then every probe is fair: Aϕi=Ii∪(Ii+π).A_ _i=I_i∪(I_i+π). Since this family is invariant under translation by π, we may project the parameter circle modulo π. Under this projection, each agreement set becomes a single interval IiI_i of length π/2π/2 containing the reference point 00. Condition (4) therefore reduces exactly to the private-point condition in Lemma A.1. Consequently, m≤2.m≤ 2. • Case 2: There is exactly one discriminatory probe. Let this probe have index q. For every i≠qi≠ q, a witness θi _i satisfying (4) must in particular belong to Aϕq=Iq.A_ _q=I_q. Since IqI_q is the local interval of length π/2π/2 containing 00, θi _i cannot lie in the antipodal component Ij+πI_j+π of any Fair agreement set. Hence, for all i≠qi≠ q, the star condition reduces locally to θi∈⋂j≠iIj∖Ii. _i∈ _j≠ iI_j I_i. By Lemma A.1, at most two of the Fair probes can possess such witnesses. Since there is only one discriminatory probe, this yields m≤1+2=3.m≤ 1+2=3. • Case 3: There are at least two Discriminatory probes. For every i, the intersection ⋂j≠iAϕj _j≠ iA_ _j contains a Discriminatory agreement interval, except possibly when i is one of the Discriminatory probes and there is exactly one other Discriminatory probe. In either case, because there is at least one Discriminatory agreement set among the sets indexed by j≠ij≠ i, every witness θi _i is confined to the local component containing 00. Thus all relevant agreement sets may be replaced by their local intervals IjI_j, and condition (4) again reduces to θi∈⋂j≠iIj∖Ii. _i∈ _j≠ iI_j I_i. Lemma A.1 then implies m≤2.m≤ 2. Combining the three cases gives 2(ℱℋ,R)≤3. s_2( F_H,R)≤ 3. Step 5: Lower bound 2(ℱℋ,R)≥3 s_2(F_H,R)≥ 3. It remains to exhibit an explicit 33-star on the 2-context class. To this end, consider the reference orientation θ0=0 _0=0 and choose the three probe angles ϕ1=π20,ϕ2=21π40,ϕ3=23π40. _1= π20, _2= 21π40, _3= 23π40. Using (1), their labels under the reference orientation are (f0(ϕ1),f0(ϕ2),f0(ϕ3))=(+1,0,0). (f_0( _1),f_0( _2),f_0( _3) )=(+1,0,0). Now choose the three witnessing orientations θ1=4π5,θ2=3π80,θ3=25π16. _1= 4π5, _2= 3π80, _3= 25π16. Direct substitution into (1) gives (fθ1(ϕ1),fθ1(ϕ2),fθ1(ϕ3))=(−1,0,0), (f_ _1( _1),f_ _1( _2),f_ _1( _3) )=(-1,0,0), (fθ2(ϕ1),fθ2(ϕ2),fθ2(ϕ3))=(+1,+1,0), (f_ _2( _1),f_ _2( _2),f_ _2( _3) )=(+1,+1,0), and (fθ3(ϕ1),fθ3(ϕ2),fθ3(ϕ3))=(+1,0,−1). (f_ _3( _1),f_ _3( _2),f_ _3( _3) )=(+1,0,-1). Therefore, j:fθ1(ϕj)≠f0(ϕj)=1, \j:f_ _1( _j)≠ f_0( _j) \=\1\, j:fθ2(ϕj)≠f0(ϕj)=2 \j:f_ _2( _j)≠ f_0( _j) \=\2\ and j:fθ3(ϕj)≠f0(ϕj)=3 \j:f_ _3( _j)≠ f_0( _j) \=\3\ Hence (ℱℋ,R)≥3. s( F_H,R)≥ 3. Together with the upper bound, we get 2(ℱℋ,R)=3. s_2( F_H,R)=3. Finally, since (ℋ)=∞, s(H)=∞, we obtain the desired information-theoreticseparation. ■ Remark A.1 (The protected groups domain restriction is essential). The finite-star conclusion on the 2-context class relies essentially on restricting the allowable cross-group probes to R=(x,Rx):x≠0.Z_R=\(x,Rx):x≠ 0\. It does not hold for the unrestricted product-space class ℱ~=(x1,x2)↦h(x1)−h(x2):h∈ℋ. F= \(x_1,x_2) h(x_1)-h(x_2):h \. Indeed, for every homogeneous linear classifier and every x away from its decision boundary, h(−x)=−h(x),h(-x)=-h(x), and hence fh(x,−x)=h(x)−h(−x)=h(x).f_h(x,-x)=h(x)-h(-x)=h(x). Thus the restriction of ℱ~ F to pairs of the form (x,−x)(x,-x) contains an exact copy of ℋH, implying 2(ℱ~)≥(ℋ)=∞. s_2( F)≥ s(H)=∞. Therefore the separation in Proposition 3.2 arises from the combination of relational predictions and the structured protected groups domain, rather than from taking prediction differences alone. Appendix B Protection against Model Extraction See 3.2 Proof We reduce from the Minimum Test Cover problem (Definition E.2), known to be NP-complete. We begin by showing that B-Bounded-Relational-Extraction is NP-hard via a polynomial-time reduction from Minimum-Test-Cover, even when the multi-context class and the set of admissible queries are finite and every query uses two points that occur in no other admissible query. Membership in NP is immediate: given a candidate ′⊆Q , one can verify |′|≤B|Q |≤ B and, for each of the at most (m2) m2 pairs of hypotheses, check whether some query in ′Q distinguishes the pair. By assumption, every relational response is polynomial-time computable. For NP-hardness, we reduce from Minimum Test-Cover. Let (U,,K)(U,T,K) be an instance, where U=u1,…,um,=T1,…,Tr.U=\u_1,…,u_m\, =\T_1,…,T_r\. A subcollection ′⊆T is a test cover if for every pair ui≠uju_i≠ u_j, there exists Tℓ∈′T_ containing exactly one of uiu_i and uju_j. First, we can observe that if some pair ui≠uju_i≠ u_j is not distinguished by any test in T, then the Test-Cover instance is necessarily a NO instance. Such instances may therefore be mapped in polynomial time to any fixed NO instance of the target problem. Hence, for the remainder of the reduction, we may assume that every pair of objects is distinguished by at least one test. For every test TℓT_ , introduce two fresh domain points aℓ,bℓa_ ,b_ . All such points are distinct, so aℓ,bℓ∩aℓ′,bℓ′=∅,\a_ ,b_ \∩\a_ ,b_ \= , for ℓ≠ℓ′ ≠ . For every object uj∈Uu_j∈ U, define a hypothesis hj:→0,1h_j:X→\0,1\ by hj(aℓ)=1h_j(a_ )=1 and hj(bℓ)=1−uj∈Tℓ.h_j(b_ )=1- 1\u_j∈ T_ \. Since every pair of objects is distinguished by at least one test, the resulting hypotheses h1,…,hmh_1,…,h_m are pairwise distinct. For every TℓT_ , define the relational query qℓ=(aℓ,bℓ)q_ =(a_ ,b_ ) and let fh(qℓ)=h(aℓ)−h(bℓ).f_h(q_ )=h(a_ )-h(b_ ). Then fhj(qℓ)=hj(aℓ)−hj(bℓ)=uj∈Tℓ.f_h_j(q_ )=h_j(a_ )-h_j(b_ )= 1\u_j∈ T_ \. Consequently, for every i≠ji≠ j, fhi(qℓ)≠fhj(qℓ) f_h_i(q_ )≠ f_h_j(q_ ) ⇔ui∈Tℓ≠uj∈Tℓ 1\u_i∈ T_ \≠ 1\u_j∈ T_ \ ⇔Tℓ distinguishes ui and uj. T_ distinguishes u_i and u_j. Now set B=KB=K. For any subcollection ′⊆T , define ′=qℓ:Tℓ∈′.Q =\q_ :T_ \. The correspondence Tℓ↔qℓT_ q_ is one-to-one, so |′|=|′|.|Q |=|T |. Moreover, by the equivalence above, ′ distinguishes every pair in U⇔′ distinguishes every pair in ℋ0.T distinguishes every pair in U distinguishes every pair in H_0. Therefore, (U,,K)∈Test-Cover⇔(ℋ0,,B)∈Bounded-Relational-Extraction.(U,T,K)∈ Test-Cover (H_0,Q,B)∈ Bounded-Relational-Extraction. The construction uses 2r2r domain points, m hypotheses, and r queries, and its explicit representation can be constructed in O(mr)O(mr) time. Hence the reduction is polynomial. Finally, since every qℓq_ uses the fresh pair aℓ,bℓ\a_ ,b_ \, distinct queries have disjoint supports. Therefore the NP-completeness result holds even under this restriction. ■ Appendix C Proofs for Manipulation-free Regime C.1 Lower Bound on Sample Complexity See 3.1 Proof Step 1: Active bound. Let αϵ=mink,⌊12ϵ⌋. _ε= \ s_k, 12ε \. Let S=1,…,αϵS=\x_1,…,x_ _ε\ be a k-star with center f0f_0 and witnesses f1,…,fαϵf_1,…,f_ _ε, and define the fixed coupling ν=1αϵ∑i=1αϵδiν= 1 _ε _i=1 _ε _x_i. We have, ν(i)=1αϵ≥2ϵ>ϵ.ν(\x_i\)= 1 _ε≥ 2ε>ε. Consider any randomized auditor using at most q queries. We begin by observing : supf∗∈ℱkℙ[ℙ∼ν[f^()≠f∗()]>ϵ]≥maxi∈[αϵ]ℙ[ℙ∼ν[f^()≠fi()]>ϵ] f^* _k P [ X ν P [ f(X)≠ f^*(X)]>ε ]≥ i∈[ _ε] P [ X ν P [ f(X)≠ f_i(X)]>ε ] We proceed by coupling the audit process with targets f0,f1,…,fαϵf_0,f_1,…,f_ _ε using the same unlabeled stream and the same internal randomness for the audit. Let Q0Q_0 denote the distinct star points queried under target f0f_0, and if ℙ[ℙ∼ν[f^0()≠f0()]>ϵ]>δ P [ X ν P [ f_0(X)≠ f_0(X)]>ε ]>δ f0f_0 is already hard. Otherwise, for all i∈[αϵ]i∈[ _ε] with probability at least 1−δ1-δ, we have f^0(i)=f0(i) f_0(x_i)=f_0(x_i) (5) Let E0E_0 denotes that event, that is E0=f^0(i)=f0(i):∀i∈[αϵ]E_0= \ f_0(x_i)=f_0(x_i):∀ i∈[ _ε] \ We have ℙ|E0]≥1−δ P |E_0]≥ 1-δ (6) If i∉Q0,x_i∉ Q_0, then all queries lie in some jx_j, where j≠ij≠ i. By the star definition, we know that fi(j)=f0(j)f_i(x_j)=f_0(x_j), and a simple induction over the interaction wxith the model owner therefore gives f^i=f^0. f_i= f_0. Hence, on the event in 5, every non-queried ix_i produces f^i f_i such that ℙ∼ν[f^i()≠fi()]>ϵ X ν P [ f_i(X)≠ f_i(X)]>ε. Let FiF_i denote the event Fi=ℙ∼ν[f^i()≠fi()]F_i= \ X ν P [ f_i(X)≠ f_i(X)] \ We have shown that E0∩i∈Q0⊆FiE_0∩\x_i∈ Q_0\ F_i Therefore, E0i∉Q0≤Fi 1_E_0 1_x_i∉ Q_0≤ 1_F_i (7) On the other hand, by definition |Q0|≤q|Q_0|≤ q. Since there αϵ _ε star points, ∑i∈[αϵ]i∉Q0≥αϵ−q i∈[ _ε]Σ 1_x_i∉ Q_0≥ _ε-q (8) maxi∈[αϵ]ℙ[ℙ∼ν[f^i()≠fi()]>ϵ] i∈[ _ε] P [ X ν P [ f_i(X)≠ f_i(X)]>ε ] ≥1αϵ∑i∈[αϵ]ℙ[ℙ∼ν[f^i()≠fi()]>ϵ] ≥ 1 _ε i∈[ _ε]Σ P [ X ν P [ f_i(X)≠ f_i(X)]>ε ] =1αϵ∑i∈[αϵ][Fi] = 1 _ε i∈[ _ε]ΣE[ 1_F_i] ≥1αϵ∑i∈[αϵ][E0i∉Q0] ≥ 1 _ε i∈[ _ε]ΣE[ 1_E_0 1_x_i∉ Q_0] ≥αϵ−qαϵℙ[E0] ≥ _ε-q _ε P [E_0] ≥(αϵ−q)(1−δ)αϵ ≥ ( _ε-q)(1-δ) _ε Where step 3 follows from 7, step 4 follows from 8 , and the last step follows from 6. The right part is bigger than δ when αϵ−qαϵ(1−δ)>δ, _ε-q _ε(1-δ)>δ, which is equivalent to q>1−2δ1−δαϵ.q> 1-2δ1-δ _ε. Step 2: Passive bound. Let m=DSk(ℱ)m=DS_k(F), S=(1,…,m)S=(x_1,…,x_m) DS-shattered CGQs, and B⊆ℱ[S]B [S] an m-dimensional pseudo-cube. Let ν the coupling be defined as: ν=1m∑i=1mδi.ν= 1m _i=1^m _x_i. For the lower bound we strengthen the learner by granting it direct membership query access to any of the m ν-support points. We can note that a lower bound in this stronger model is also a lower bound for the pool-based auditor. Let the target f∗f^* be uniformly random from B. By Yao’s minimax principle (Yao,, 1977), it suffices to analyze a deterministic auditor. Suppose the auditor has made r distinct queries, with r≤qr≤ q. Condition on an arbitrary resulting interaction history, which we denote T. Let BT=∈B:b is consistent with T.B_T=\b∈ B:b is consistent with T\. Because the prior on B is uniform and the auditor is deterministic, the conditional target is uniform on BTB_T. Fix an non-queried coordinate i∈[m].i∈[m]. For every ∈BTb∈ B_T, the pseudo-cube property gives an i-neighbor ′∈Bb ∈ B satisfying bi′≠bib _i≠ b_i, and bj′=bjb _j=b_j for j≠ij≠ i and since coordinate i has not been queried, ′b agrees with b on every queried coordinate hence ′∈BTb ∈ B_T. For =(b1,b2,⋯,bi−1,bi,bi+1,⋯,bm)b=(b_1,b_2,·s,b_i-1,b_i,b_i+1,·s,b_m), let πi()=(b1,b2,⋯,bi−1,bi+1,⋯,bm) _i(b)=(b_1,b_2,·s,b_i-1,b_i+1,·s,b_m) denote the projection removing the ithi^th coordinate from b. For g∈πi(BT)g∈ _i(B_T), we define a fiber Fg=∈BT:πi()=gF_g=\b∈ B_T: _i(b)=g\ Partition BTB_T into these fibers. Every such fiber contains at least two traces and within one fiber, all labels at coordinate i are distinct; if two traces had the same value at coordinate i and agreed on all other coordinates, they would be identical. Therefore, for any label iy_i predicted by the auditor at ix_i, in every fiber at most one trace has bi=i.b_i=y_i. By definition of the pseudo-cube, every fiber has cardinality at least two and since conditioned on T , the target f∗f^* is uniform on BTB_T, it is also uniform within each fiber conditioned on membership of that fiber, by total law of probability we obtain ℙ[f^(i)≠f∗(i)∣T]≥12. P [ f(x_i)≠ f^*(x_i) T ]≥ 12. There are at least m−r≥m−qm-r≥ m-q non-qeried coordinates. Hence [ℙ∼ν[f^()≠f∗()∣T] [ X ν P [ f(X)≠ f^*(X) T ] =1m∑i=1mℙ(f^(i)≠f∗(i)∣T) = 1m _i=1^m P ( f(x_i)≠ f^*(x_i) T ) ≥m−q2m. ≥ m-q2m. Taking expectation over history, [ℙ∼ν[f^()≠f∗()]≥m−q2m.E [ X ν P [ f(X)≠ f^*(X) ]≥ m-q2m. (9) Now suppose the auditor were (ϵ,δ)(ε,δ)-PAC for every target in the pseudo-cube. Averaging over the uniform prior on B gives ℙ∼ν[f^()≠f∗()]>ϵ≤δ P \ X ν P [ f(X)≠ f^*(X)]>ε \≤δ Since 0≤ℙ∼ν[f^()≠f∗()]>ϵ≤δ)≤1,0≤ P \ X ν P [ f(X)≠ f^*(X)]>ε \≤δ)≤ 1, we then have [ℙ∼ν[f^()≠f∗()]] [ X ν P [ f(X)≠ f^*(X)]] ≤ϵℙ∼ν[f^()≠f∗()]≤ϵ+ℙ∼ν[f^()≠f∗()]>ϵ ≤ε P \ X ν P [ f(X)≠ f^*(X)]≤ε\+ P \ X ν P [ f(X)≠ f^*(X)]>ε\ ≤ϵ(1−δ)+δ ≤ε(1-δ)+δ =ϵ+δ(1−ϵ). =ε+δ(1-ε). Combining with 9, m−q2m≤ϵ+δ(1−ϵ). m-q2m≤ε+δ(1-ε). Therefore q≥m[1−2ϵ−2δ(1−ϵ)]q≥ m [1-2ε-2δ(1-ε) ] ■ C.2 Proof of ALeBi Upper Bounds See 3.3 Proof We organize the proof as follows: we begin by showing the active terms in the upper bound by adapting the proof of Hanneke, (2014) to the multi-class learning problem, since the probe learning problem reduces to multiclass learning where the size of labels depend on the cardinal of groups k. Step 1: The passive term. Here, the passive learner is allocated failure probability δ/2δ/2. Fix n=⌈DSk+log(4/δ)ϵ⌉.n= DS_k+ (4/δ)ε . By Theorem E.1, the passive term derives directly by drawing n CGQ queries 1:m=(1,…,n)Q_1:m=(X_1,…,X_n) from the fixed coupling ν and obtaining their probe labels via M, which guarantees: By the choice of n, the multiclass passive algorithm proposed in Pabbaraju, (2026) outputs f^1:n f_Q_1:n such that: ℙ1:n[ℙ∼ν[f^1:n()≠f∗()]>ϵ]≤δ2<δ Q_1:n P [ X ν P [ f_Q_1:n(X)≠ f^*(X)]>ε]≤ δ2<δ In the following, fix S≜1,2,⋯,nS \x_1,x_2,·s,x_n\ as the sample set used for passive learning, with n=⌈DSk+log(4/δ)ϵ⌉n= DS_k+ (4/δ)ε . Step 2: First active term. We assume that pool of CGQ queries is index by some set I. If I⊆[N]I [N] denotes the set of indices that A have seen in the history of interaction with M, the corresponding version space is given by I=f∈ℱk:f(j)=f⋆(j),∀j∈I,V_I= \f _k:f(x_j)=f (x_j),∀ j∈ I \, where f⋆=fh⋆f =f_h , h⋆h being the black-box model under audit. For a nonempty set I, we say that i∈Ii∈ I is an effective (informative) index if it exhibits disagreement within the multi-context class with respect to f⋆f , meaning there exists fi∈ℱkf_i _k such that for all j∈I∖ij∈ I \i\, fi(j)=f⋆(j)f_i(x_j)=f (x_j) while fi(i)≠f⋆(i).f_i(x_i)≠ f (x_i). Let E(I)E(I) denote such set of effective coordinates. It is straightforward to see that |E(I)|≤mink,|I||E(I)|≤ \ s_k,|I|\ Let f0,fii∈If_0,\f_i\_i∈ I be such that they exhibit this disagreement within ℱkF_k, where f0=f⋆f_0=f For i≠j∈E(I)i≠ j∈ E(I), we have fi(j)=f⋆(j)f_i(x_j)=f (x_j) while fi(i)≠f⋆(i)f_i(x_i)≠ f (x_i) If i=jx_i=x_j for i≠ji≠ j, then a witness for coordinate i would have to both agree and disagree with f⋆f at the same CGQ. Therefore the CGQs indexed by the effective set E(I)E(I) must be distinct. which shows that i:i∈E(I)\x_i:i∈ E(I)\ is a multi-star set for ℱkF_k centered at f0=f⋆f_0=f . By definition of k s_k, |E(I)|≤k|E(I)|≤ s_k. For an integer n 77 7 n here is arbitrary, we’l later use n as the sample complexity for passive learning probes., let sn≜mink,n.s_n \ s_k,n\. For I⊆[n]I [n], let N(I)N(I) be the cardinal of CGQ queries when the coordinates of I are processed in a uniformly random order, and let Ψ(I)≜[eλN(I)|S], (I) [e^λ N(I)\, |\,S ], where λ≥0λ≥ 0. We show by induction on m=|I|m=|I| that the following holds Ψ(I)≤∏r=1m[1+(eλ−1)min1,snr] (I)≤ _r=1^m [1+(e^λ-1) \1, s_nr \ ] For m=0m=0 the resulting identity is trivial. Let |I|=m≥1|I|=m≥ 1. In a uniformly random ordering of I, the last coordinate is uniformly distributed over I. Conditionned on coordinate i being last. After all coordinates in I∖iI \i\ have been processed, the current version space is f:f(j)=f⋆(j)∀j∈I∖i \f:f(x_j)=f (x_j)\ ∀ j∈ I \i\ \ Therefore the final CGQ cooreponding to index i is queried if and only if i∈E(I)i∈ E(I). Hence N(I)=N(I∖i)+i∈E(I)N(I)=N(I \i\)+ 1\i∈ E(I)\ Averaging over the uniformly random last coordinate yields Ψ(I)=1m∑i∈Ieλi∈E(I)Ψ(I∖i). (I)= 1m _i∈ Ie 1\i∈ E(I)\ (I \i\). Applying the induction hypothesis to each I∖iI \i\ yields Ψ(I)≤(∏r=1m−1[1+(eλ−1)min1,snr])(1m∑i∈Ieλi∈E(I)) (I)≤ ( _r=1^m-1 [1+(e^λ-1) \1, s_nr \ ] ) ( 1m _i∈ Ie 1\i∈ E(I)\ ) On the other hand, 1m∑i∈Ieλi∈E(I)=1+(eλ−1)|E(I)|m 1m _i∈ Ie 1\i∈ E(I)\=1+(e^λ-1) |E(I)|m and since |E(I)|≤mink,|I||E(I)|≤ \ s_k,|I|\, we have |E(I)|m≤min1,snm |E(I)|m≤ \1, s_nm \ we conclude the induction. For I=[n]I=[n] with the fact that 1+t≤et,1+t≤ e^t, we have [eλNn|S]≤exp((eλ−1)∑r=1nmin1,snr),E [e^λ N_n\, |\,S ]≤ ((e^λ-1) _r=1^n \1, s_nr \ ), where Nn≜N([n])N_n N([n]). For λ=1λ=1, and by Markov’s inequality, ℙNn>b|S P \N_n>b\, |\,S \ =ℙeNn>eb|S = P \e^N_n>e^b\, |\,S \ ≤exp((e−1)min1,snr−b). ≤ ((e-1) \1, s_nr \-b ). Taking b=(e−1)min1,snr+log2δb=(e-1) \1, s_nr \+ 2δ, for every realized pool S, ℙNn>b|S≤δ2 P \N_n>b\, |\,S \≤ δ2 The auditor A runs k-ALeBi for a budget of b under the condition that if it is about to make query number b+1b+1, it halts. Thus the truncated procedure makes at most b oracle queries on every execution. If truncation does not occur, k-ALeBi has reconstructed every response in the original i.i.d. sample S used for the probe passive leaning, and hence has recovered exactly the target probe. The passive term in Step 1 is then applied to this completed labeled sample and requires no additional oracle queries. The failure events are therefore Zalebi=k-ALeBi is truncatedZ_alebi=\$k$-ALeBi is truncated\ for interactive setting and Zpass=ℙ∼ν[f^S()≠f∗()]>ϵZ_pass= \ X ν P [ f_S(X)≠ f^*(X)]>ε \ for passive setting. In step 1, we have shown that ℙ(Zpass)≤δ2 P (Z_pass)≤ δ2 And in step 2, we have shown that: ℙ(Zalebi)≤δ2 P (Z_alebi)≤ δ2 Therefore, by the union bound, ℙ1:n[ℙ∼ν[f^1:n()≠f∗()]>ϵ]<δ Q_1:n P [ X ν P [ f_Q_1:n(X)≠ f^*(X)]>ε]<δ Finally 1≤sn≤n,1≤ s_n≤ n, then ∑r=1nmin1,snr _r=1^n \1, s_nr \ =∑m=1sn1+∑m=sn+1Nsnm = _m=1^s_n1+ _m=s_n+1^N s_nm ≤sn+snlognsn ≤ s_n+s_n ns_n =snlogensn. =s_n ens_n. In particular, for k≤n s_k≤ n, this yields a sample complexityb of (e−1)klogenk+log2δ+1(e-1) s_k en s_k+ 2δ+1 (10) with n=⌈DSk+log(4/δ)ϵ⌉.n= DS_k+ (4/δ)ε . Step 3: Second active term. We next obtain a deterministic exact-completion procedure on the same finite pool using the same fixed coupling over groups marginals. Let S=(f(1),…,f(n)):f∈ℱkV_S= \(f(x_1),…,f(x_n)):f _k \ denote the version space consistent with S. Recall the definitions of specifying sets and extended teaching dimension in DEfinition E.1. For an arbitrary labeling g∈kn,g _k^n, S is a specifying set for g with respect to SV_S if |v∈S:v|S=g|S|≤1. |\v _S:v|_S=g|_S\ |≤ 1. The extended teaching dimension is XTD(S)=maxg∈knmin|S|:S specifies g with respect to S.XTD(V_S)= _g _k^n \|S|:S specifies g with respect to V_S \. We first establish the relation between XTD and the multiclass star number that is needed in the algorithm: XTD(S)≤mink(S)+1,n≤mink+1,nXTD(V_S)≤ \ s_k(V_S)+1,n\≤ \ s_k+1,n\ The bound by n is trivial since all n coordinates specify any labeling with respect to SV_S. To prove the first inequality, fix an arbitrary g∈kng _k^n and let S=i1,…,imS=\i_1,…,i_m\ be a specifying set of minimum cardinality. If m=0m=0 the bound terms become trivial. For every r∈[m]r∈[m], minimality implies that S∖irS \i_r\ is not specifying. Consequently there exist at least two distinct traces in SV_S agreeing with g on S∖irS \i_r\. Because S itself is specifying, at most one of those traces can also agree with g at iri_r. We can therefore choose vr∈Sv_r _S such that vr(ir)≠g(ir)v_r(i_r)≠ g(i_r) and for all ℓ≠r ≠ r, vr(iℓ)=g(iℓ)v_r(i_ )=g(i_ ). If m≥2m≥ 2, let v1v_1 as a center and the m−1m-1 indices i2,…,im.i_2,…,i_m. For every r≥2r≥ 2, vr(ir)≠g(ir)=v1(ir),v_r(i_r)≠ g(i_r)=v_1(i_r), while for every ℓ≥2 ≥ 2 with ℓ≠r ≠ r, vr(iℓ)=g(iℓ)=v1(iℓ).v_r(i_ )=g(i_ )=v_1(i_ ). Hence i2,…,imi_2,…,i_m is a multi-star set for SV_S, centered at v1v_1, and consequently, m−1≤(S),m-1≤ s(V_S), Therefore m≤(S)+1.m≤ s(V_S)+1. The same inequality is trivial for m=1m=1. Since g was arbitrary XTD(S)≤(S)+1.XTD(V_S)≤ s(V_S)+1. Finally, a star in SV_S lifts to a star on the corresponding CGQs in ℱkF_k, and therefore (S)≤k s(V_S)≤ s_k This proves XTD(S)≤mink+1,nXTD(V_S)≤ \ s_k+1,n\ Algorithm 5 Probes Membership-Halving 1: Budget m, finite trace SV_S. 2: Intialization: ←S.V _S. 3: while |V|>1|V|>1 do 4: for i=1,…,mi=1,…,m do 5: Choose a maximizing response ϕ(i)∈argmaxy∈k|v∈:v(i)=y|. _V(i)∈ _y _k|\v :v(i)=y\|. 6: ai:=|v∈:v(i)=ϕ(i)|.a_i:=|\v :v(i)= _V(i)\|. 7: end for 8: Choose a smallest specifying set S for ϕ _V with respect to V. 9: Choose i⋆∈argmaxi∈S(|V|−ai).i ∈ _i∈ S(|V|-a_i). 10: Query y⋆←f⋆(i⋆).y ← f (X_i ). 11: Update ←v∈:v(i⋆)=y⋆.V←\v :v(i )=y \. 12: end while 13: Let v⋆v denote the unique surviving trace in V. 14: return ((,,,))i=1n. ((X_i,v (i)) )_i=1^n. Next we show that Algorithm 5 uses at most m=1+XTD(S)log|S|m=1+XTD(V_S) |V_S| CGQs. Let V⊆SV _S denote the current trace version space. With the initialization step =S,V=V_S, for every index i∈[n]i∈[n], Algorithm 5 chooses a maximizing response ϕ(i)∈argmaxy∈k|v∈:v(i)=y| _V(i)∈ _y _k|\v :v(i)=y\| and let ai=|v∈:v(i)=ϕ(i)|.a_i=|\v :v(i)= _V(i)\|. Since restricting a class cannot increase XTD, XTD()≤XTD(S).XTD(V) (V_S). Hence there exists a set S⊆[n]S [n] such that |S|≤XTD(S)|S| (V_S) that specifies the labeling ϕ _V. At most one trace in V agrees with ϕ _V on all coordinates in S thus every other trace disagrees with ϕ _V somewhere in S, yielding ∑i∈S(||−ai)≥||−1 _i∈ S(|V|-a_i)≥|V|-1 Thus there exists i⋆∈Si ∈ S such that ||−ai⋆≥||−1XTD(S).|V|-a_i ≥ |V|-1XTD(V_S). (11) Algorithm 5 queries y⋆=f⋆(i⋆)y =f (x_i ) and retain ′=v∈:v(i⋆)=y⋆.V =\v :v(i )=y \. We distinguish between two cases; If y⋆=ϕ(i⋆),y = _V(i ), then |′|=ai⋆|V |=a_i and inequality 11 gives |′|−1≤(1−1XTD(S))(||−1)|V |-1≤ (1- 1XTD(V_S) )(|V|-1) On the other hand, if y⋆≠ϕ(i⋆)y ≠ _V(i ) then the surviving response cell isn’t a maximizing cell. Since a maximizing cell has cardinality at least that of every other cell |′|≤||2|V |≤ |V|2 When XTD(S)≥2XTD(V_S)≥ 2, ||2−1≤(1−1XTD(S))(||−1) |V|2-1≤ (1- 1XTD(V_S) )(|V|-1) If XTD(S)=1XTD(V_S)=1, one specifying coordinate leaves at most one surviving trace, so exact identification occurs after one query. Thus, whenever ||>1|V|>1, |′|−1≤(1−1XTD(S))(|V|−1)|V |-1≤ (1- 1XTD(V_S) )(|V|-1) After q queries, |q|−1≤(1−1XTD(S))q(|S|−1)≤e−q/XTD(S)(|S|−1)|V_q|-1≤ (1- 1XTD(V_S) )^q(|V_S|-1)≤ e^-q/XTD(V_S)(|V_S|-1) If q>XTD(S)log(|S|−1),q>XTD(V_S) (|V_S|-1), then the right-hand side is strictly smaller than 11. Since |q|−1|V_q|-1 is a nonnegative integer, it must equal zero. Therefore qV_q contains exactly one trace. Since the target trace is maintained via consistency with version space, that unique trace is exactly (f⋆(1),…,f⋆(n)).(f (x_1),…,f (x_n)). Hence the sample complexity of Algorithm 5 is bounded by 1+XTD(S)log|S|1+XTD(V_S) |V_S|, and sinceXTD(S)≤mink+1,nXTD(V_S)≤ \ s_k+1,n\, the sample complexity is bounded by 1+mink+1,nlog|S|1+ \ s_k+1,n\ |V_S| If Πℱk(n) _F_k(n) denotes the growth function over n CGQs, using the fact that |S|≤Πℱk(n),|V_S|≤ _F_k(n), uniformly over every possible pool, we get a sample complecity of (1+mink+1,nlogΠℱk(n))O(1+ \ s_k+1,n\ _F_k(n)) (12) ALgorithm 5 has no truncation failure as it reconstructs the CGQ pool exactly. Thus the only failure event is that of the passive multiclass learner whose probability is already at most δ/2δ/2 from step 1. A sharper result presented below is derived to improve the dependence on the extended teaching dimension by a logarithmic factor. Lemma C.1 (Refined bounds for Algorithm 5). For every finite trace class ⊆nV ^n there exists a deterministic query procedure that exactly identifies every target v⋆∈v using (XTD()1∨logXTD()log||)O\! ( XTD(V)1 (V) |V| ) queries. Proof For arbitrary label spaces XTD(S)≤(S)XTD(V_S)≤ s(V_S) and restricting on consitency with S doesn’t increase the star number (S)≤sk. s(V_S)≤ s_k. Since XTD(S)≤nXTD(V_S)≤ n, then XTD(S)≤s¯k.XTD(V_S)≤ s_k. We now apply the refined multiclass Membership Halving procedure. At the beginning of interaction, let V be the current version space and let ϕ(i)∈argmaxy|v∈:v(i)=y| _V(i)∈ _y|\v :v(i)=y\| be its maximizing labeling. Fix a specifying set S for ϕ _V of size at most XTD(S)XTD(V_S), query the remaining coordinate maximizing |v∈V:v(i)≠ϕ(i)|,|\v∈ V:v(i)≠ _V(i)\|, keeping ϕ _V fixed throughout the phase. Suppose a phase starts with n traces and the first contradiction to the fixed plurality labeling occurs on its q-th query. Let AjA_j be the set of traces eliminated by a maximizing-consistent answer at the j-th queried coordinate. The sets A1,…,AqA_1,…,A_q are pairwise disjoint, and by construction of algorithm 5, we end up constraining a chain |A1|≥|A2|≥⋯≥|Aq|.|A_1|≥|A_2|≥·s≥|A_q|. Therefore q|Aq|≤∑j=1q|Aj|≤n.q|A_q|≤ _j=1^q|A_j|≤ n. After the contradiction, the surviving exact response cell is a subset of AqA_q, therefore |′|≤nq.|V |≤ nq. If no contradiction occurs on the entire specifying set, the target trace is uniquely identified. Suppose algorithm 5 performs P phases. For phase p, let np−1n_p-1 be the size of the version space at the beginning of the phase, let npn_p be its size at the end of the phase, and let qpq_p be the number of queries made during that phase.Then there exists a universal constant c>0c>0 such that lognp−1np≥cLog(qp), n_p-1n_p≥ c\,Log(q_p), (13) where Log(t)≜1∨logt.Log(t) 1 t. Moreover, since the phase queries only coordinates from a specifying set, qp≤XTD(p−1)≤XTD(S)q_p (V_p-1) (V_S) The function t⟼tLog(t)t tLog(t) is nondecreasing for t≥1t≥ 1. Hence, from qp≤XTD(S)q_p (V_S), qpLog(qp)≤XTD(S)Log(XTD(S)). q_pLog(q_p)≤ XTD(V_S)Log(XTD(V_S)). Equivalently, qp≤XTD(S)Log(XTD(S))Log(qp).q_p≤ XTD(V_S)Log(XTD(V_S))Log(q_p). With the result of 13, qp≤1cXTD(S)Log(XTD(S))lognp−1np.q_p≤ 1c XTD(V_S)Log(XTD(V_S)) n_p-1n_p. Summing over all P phases gives sample complexity of ∑p=1Pqp _p=1^Pq_p ≤1cXTD(S)Log(XTD(S))∑p=1Plognp−1np ≤ 1c XTD(V_S)Log(XTD(V_S)) _p=1^P n_p-1n_p =1cXTD(S)Log(XTD(S))logn0nP. = 1c XTD(V_S)Log(XTD(V_S)) n_0n_P. The algorithm starts from n0=|S|n_0=|V_S| and terminates when a unique trace remains, that is nP=1.n_P=1. Therefore a sample complexity of XTD(S)LogXTD(S)log|S| XTD(V_S)LogXTD(V_S) |V_S| suffices ■ Applying lemma C.1 with |S|≤Πℱk(n),|V_S|≤ _F_k(n), and therefore a set of size O(mink,n1∨logmink,nlogΠℱk(n))O\! ( \ s_k,n\1 \ s_k,n\ _F_k(n) ) suffices. On the other hand, a binary point v=(v1,…,vk)v=(v_1,…,v_k) from the cube 0,1k\0,1\^k induces probe response T(v)=(vi−vj)i<jT(v)=(v_i-v_j)_i<j If for two points v,wv,w, one has T(v)=T(w)T(v)=T(w), then for all i<ji<j, vi−wi=vj−wjv_i-w_i=v_j-w_j, making v−wv-w constant. The only distinct pair with this property is (v,w)=(0k,1k)(v,w)=(0^k,1^k). Hence the CGQ response alphabet has size 2k−1.2^k-1. We have DSk(S)≤minDSk(ℱ),nDS_k(V_S)≤ \DS_k(F),n\, applying the multiclass Sauer lemma to the finite class S⊆[2k−1]NV_S [2^k-1]^N yields |S|≤∑j=0minDSk,n(nj)(2k−1−1)j=∑j=0minDSk,n(nj)(2k−2)j.|V_S|≤ _j=0 \DS_k,n\ nj(2^k-1-1)^j= _j=0 \DS_k,n\ nj(2^k-2)^j. Consequently, for minDSk,n≥1 \DS_k,n\≥ 1, log|S|≤minDSk,nlog(en(2k−2)minDSk,n) |V_S|≤ \DS_k,n\ ( en(2^k-2) \DS_k,n\ ) Implement this result over 12 gives the sample complexity of mink,nminDSk,nlog(en(2k−2)minDSk,n) \ s_k,n\ \DS_k,n\ ( en(2^k-2) \DS_k,n\ ) With n=⌈DSk+log(4/δ)ϵ⌉.n= DS_k+ (4/δ)ε . Combining the bounds derived in step1,2 and 3 yields the result. ■ Appendix D Proofs for Fairness-aware Manipulation Regime We begin by showing the following lemma Lemma D.1 (Accuracy of one neighborhood simulation). Under Assumptions 3.1 and 3.8, ℙq∼ν(f^(q)≠f⋆(q))≤exp(−R(1−2β)22). q ν P \! ( f(q)≠ f (q) )≤ \! (- R(1-2β)^22 ). Proof Fix q a CGQ query and define Zr≜Y~r≠f⋆(q).Z_r 1\ Y_r≠ f (q)\. Step 1: bound the conditional error probability. Let mr≜P(f⋆(qr′)≠f⋆(q)|ℍr−1)m_r P\! (f (q _r)≠ f (q)\, |\,H_r-1 ) Since qr′q _r is a fresh draw from PQ(⋅∣J(q))P_Q(· J(q)), Assumption 3.1 gives mr≤ρ.m_r≤ρ. If the clean local response differs from f⋆(q)f (q), the prob error is bounded by 11. Otherwise an error can occur only through an attack, whose conditional probability is at most p. Hence [Zr∣ℍr−1] [Z_r _r-1] ≤mr+(1−mr)p ≤ m_r+(1-m_r)p ≤ρ+(1−ρ)p=β ≤ρ+(1-ρ)p=β Step 2: Failure mode vs the number of errors. If ∑r=1RZr<R2 _r=1^RZ_r< R2 then strictly more than half of the responses equal f⋆(q)f (q). Therefore f⋆(q)f (q) is the unique mode. Thus Y^(q)≠f⋆(q)⊆∑r=1RZr≥R2\ Y(q)≠ f (q)\ \ _r=1^RZ_r≥ R2 \ Step 3: Concentration of bad events. Fix μr:=[Zr∣ℍr−1] _r:=E[Z_r _r-1] and Dr:=Zr−μr.D_r:=Z_r- _r. We have [Dr∣ℍr−1]=0,E[D_r _r-1]=0, and, conditionally on ℍr−1H_r-1, DrD_r lies in an interval of length one. The conditional Hoeffding lemma therefore gives [eλDr|ℍr−1]≤eλ2/8.E\! [e^λ D_r\, |\,H_r-1 ]≤ e^λ^2/8. Iterating this bound and applying Chernoff yields ℙ(∑r=1RDr≥t)≤exp(−2t2R) P \! ( _r=1^RD_r≥ t )≤ \! (- 2t^2R ) (14) Since μr≤β _r≤β, ∑r=1RZr≥R2⊆∑r=1RDr≥R(12−β). \ _r=1^RZ_r≥ R2 \ \ _r=1^RD_r≥ R ( 12-β ) \. Replacing t=R(12−β)t=R ( 12-β ) in 14 yields ℙ(∑r=1RZr≥R2)≤exp(−R(1−2β)22). P \! ( _r=1^RZ_r≥ R2 )≤ \! (- R(1-2β)^22 ). Combining this with step 2 proves the result. ■ See 3.4 Proof Fix p>0p>0 and set N=N0(ϵ,δ/2).N=N_0(ε,δ/2). Consider the t-th CGQ requested by k-ALeBi, conditionned on all previous CGQ responses being uncorrupted. By Lemma D.1 and the definition of R, ℙ(Y^t≠f⋆(qt)|all previous CGQs are clean)≤δ2N P \! ( Y_t≠ f (q_t)\, |\,all previous CGQs are clean )≤ δ2N There are at most N requested CGQs. Therefore ℙ(at least one CGQ response is corrupted)≤δ2 P \! (at least one CGQ response is corrupted )≤ δ2 When running Robust k-ALeBi and k-ALeBi with the same unlabeled sample and the same internal randomization, on the event that every CGQ response is correct, and both executions receive the same interaction history with M and therefore return the same output. Let F0F_0 be the failure event of this clean execution. By assumption, we have ℙ(F0)≤δ2. P (F_0)≤ δ2. Hence the failure event of the robust algorithm is contained in there exists CGQ response that was corrupted∪F0.\there exists CGQ response that was corrupted\∪ F_0. A union bound proves the (ϵ,δ)(ε,δ)-PAC guarantee of learning the probe. Finally, by definition of N, at most N clean CGQ requests are sent to M, each using exactly R oracle attacks. This proves the upper bounds sample complexity. Each accepted local CGQ requires at most 1/γ1/γ unlabeled draws in expectation, which gives a sample complexity of ⌈2N0(ϵ,δ/2)γ(1−2β)2log2N0(ε,δ/2)δ⌉ 2N_0(ε,δ/2)γ(1-2β)^2 2N_0( ,δ/2)δ . ■ See 3.5 Proof We first prove the lower bound when the M is honest. We fix a fairness-effective star of size m with center f0f_0, witnesses f1,…,fmf_1,…,f_m, and support q1,…,qmq_1,…,q_m, and let ν=1m∑j=1mδqjν= 1m _j=1^m _q_j. Since f0f_0 is zero on the entire support, μ(f0)=0.μ(f_0)=0. For every i, fif_i is zero except at qiq_i. Since fi(qi)≠f_i(q_i) 0 and individual coordinates belong to −1,0,1\-1,0,1\, at least one coordinate has one in abs. Thus μ(fi)=1m.μ(f_i)= 1m. By the choice of m, 1m≥4ε. 1m≥ 4 . Now fix i and couple executions under f0f_0 and fif_i using the same unlabeled sample and the same internal randomness. Until qiq_i is queried, the two histories are identical. Let AiA_i be the event that qiq_i is never queried. On AiA_i, both executions return the same estimate. But 1m≥4ε 1m≥ 4 , thus ϵε-accuracy intervals around 00 and 1/m1/m are disjoint. Therefore the common estimate cannot be correct under both targets. Since each execution fails with probability at most δ, νf0(Ai)≤2δ. _f_0(A_i)≤ 2δ. Thus νf0(qi is queried)≥1−2δ _f_0(q_i is queried)≥ 1-2δ Summing over queries, f0[|distinct queried support points|]≥m(1−2δ).E_f_0 [|\distinct queried support points\| ]≥ m(1-2δ). The number of distinct queried CGQs is at most the total number of oracle requests, proving the desired result. To prove the resulting lower bound in the fairness aware adversarial regime, one can observe that the first term follows from the same indistinguishability argument as in Lemma D.1. We prove the attack-dependent term. Step 1: construct two attacked environments. Fix i∈[m]i∈[m]. Under P0P_0, the target is f0f_0. On JiJ_i, the clean response is 0, and the attack returns fi(qi)f_i(q_i) with probability p. Under PiP_i, the target is fif_i. On JiJ_i, the clean response is fi(qi)f_i(q_i), and the attack returns 0 with probability p. Outside JiJ_i, use the same observation law under both environments. After identifying the two possible responses on JiJ_i with 0,1\0,1\, one observation from CiC_i has law Bern(p)under P0,Bern(1−p)under Pi.Bern(p) P_0, (1-p) P_i. Step 2: compute the history divergence. Let NiN_i be the number of oracle requests in JiJ_i. Since the two environments differ only there, the chain rule for adaptive KL divergence gives DKL(P0∥Pi)=0[Ni]DKL(Bern(p)∥Bern(1−p))D_ KL(P_0\|P_i)=E_0[N_i]D_ KL (Bern(p)\, \|\,Bern(1-p) ) (15) Step 3: Distinguish the environments. As proved previously, μ(f0)=0,μ(f_0)=0, and μ(fi)=1m≥4ε.μ(f_i)= 1m≥ 4 . Thresholding μ μ at 1/(2m)1/(2m) gives a binary test between P0P_0 and PiP_i with both error probabilities at most δ. By data processing, DKL(P0∥Pi)≥DKL(Bern(δ)∥Bern(1−δ))D_ KL(P_0\|P_i)≥ D_ KL (Bern(δ)\, \|\,Bern(1-δ) ) With 15 gives 0[Ni]≥DKL(Bern(δ)∥Bern(1−δ))DKL(Bern(p)∥Bern(1−p)).E_0[N_i]≥ D_ KL (Bern(δ)\, \|\,Bern(1-δ) )D_ KL (Bern(p)\, \|\,Bern(1-p) ). Summing over cells for i=1,…,mi=1,…,m, 0[T]≥mDKL(Bern(δ)∥Bern(1−δ))DKL(Bern(p)∥Bern(1−p)).E_0[T]≥ m D_ KL (Bern(δ)\, \|\,Bern(1-δ) )D_ KL (Bern(p)\, \|\,Bern(1-p) ). Combining this with the indistinguishability lower bound proves [T]≥mmax1−2δ,DKL(Bern(δ)∥Bern(1−δ))DKL(Bern(p)∥Bern(1−p))E[T]≥ m \1-2δ, D_ KL (Bern(δ)\, \|\,Bern(1-δ) )D_ KL (Bern(p)\, \|\,Bern(1-p) ) \ [T]≥mmax1−2δ,(1−2δ)log1−δ(1−2p)log1−pE[T]≥ m \1-2δ, (1-2δ) 1-δ(1-2p) 1-pp \ . ■ As the corruption increases and p gets closer to 1/21/2, DKL(Bern(p)∥Bern(1−p))=2(1−2p)2+O((1−2p)4),D_ KL (Bern(p)\, \|\,Bern(1-p) )=2(1-2p)^2+O((1-2p)^4), while for δ close to O DKL(Bern(δ)∥Bern(1−δ))=Θ(log(1/δ))D_ KL (Bern(δ)\, \|\,Bern(1-δ) )= ( (1/δ)) THus, in the high-noise regime and high-confidence regime, the sample complexity becomes comparable to the one derived in Theorem 3.1 Ω(minμ(ℱ),1εlog(1/δ)(1−2p)2) \! ( \ s_μ(F), 1 \ (1/δ)(1-2p)^2 ) Appendix E Auxiliary Definitions and Lemmas Theorem E.1 (Distirbution-free realizable multiclass learning Pabbaraju, (2026)). Let ℱkF_k be a multiclass hypothesis class of Daniely-Shwartz dimension DSkDS_k. Then there exists a learning algorithm A such that, a sample complexity of (DSk+log(1/δ)ϵ) ( DS_k+ (1/δ)ε ) is sufficient to learn ℱkF_k in the distirbution-free setting under realizability. Definition E.1 (Extended Teaching Dimension). Let ⊆mV ^m be a finite hypothesis class over the finite domain [m]=1,…,m.[m]=\1,…,m\. For an arbitrary labeling g∈m,g ^m, a set S⊆[m]S [m] is said to specify g with respect to V when |v∈:v|S=g|S|≤1. | \v :v|_S=g|_S \ |≤ 1. The extended teaching dimension of V is XTD()≜maxg∈mmin|S|:S⊆[m] specifies g with respect to .XTD(V) _g ^m \|S|:S [m] specifies g with respect to V \. Lemma E.1 (Freedman’s inequality Freedman, (1975); Tropp, (2011) ). Suppose that Dt≤bD_t≤ b almost surely for every t. Then, for every s≥0s≥ 0 and v>0v>0, ℙ(ST≥s,VT≤v)≤exp(−s22(v+bs/3)). P (S_T≥ s,\;V_T≤ v )≤ (- s^22(v+bs/3) ). More generally, the original Freedman inequality is uniform over time.. Definition E.2 (Minimum Test Cover (Crowston et al.,, 2012; Garey et al.,, 1990)). Let V=v1,…,vnV=\v_1,…,v_n\ be a set of objects and let =T1,…,TmT=\T_1,…,T_m\ be a collection of subsets of V, called tests. A test T∈T separates two distinct items vi,vj∈Vv_i,v_j∈ V if exactly one of them belongs to T, i.e., |vi,vj∩T|=1.|\v_i,v_j\∩ T|=1. A subcollection ′⊆T is called a test cover if every pair of distinct items in V is separated by at least one test in ′T . The Minimum Test Cover problem consists of finding a test cover ′T of minimum cardinality: min′⊆|′| _T |T | subject to ∀vi,vj∈V,i≠j,∃T∈′:|vi,vj∩T|=1.∀\,v_i,v_j∈ V,\ i≠ j, ∃\,T :|\v_i,v_j\∩ T|=1. Theorem E.2. The Minimum Test Cover problem is NP-hard. Appendix F Additional Experiments Results and Details F.1 Fairness-aware Adversarial Regime The finite-pool implementation follows the neighborhood mechanism above, but constructs the cells using a concrete target-independent pseudometric. Let G be a fixed reference panel of candidate probe hypotheses, selected without knowledge of the deployed target. Define dG(q,q′):=1|G|∑f∈Gf(q)≠f(q′)d_G(q,q ):= 1|G| _f∈ G1\f(q)≠ f(q )\ For every candidate CGQ q, its cell J(q)J(q) is fixed before any oracle interaction and consists of the 256256 nearest distinct CGQs under dGd_G. Neither the current version space nor observed target responses are used to construct these cells. For p>0p>0, the implementation in the experimental section uses β=p+ρ−pρ,ρ=0.05,δ=0.05,β=p+ρ-pρ, ρ=0.05, δ=0.05, and R(p)=⌈2(1−2β)2log2Nδ⌉,R(p)= 2(1-2β)^2 2Nδ , where N bounds the number of clean CGQ decisions allowed by budget? When Robust k-ALeBi requests qtq_t, it also samples R(p)R(p) distinct CGQs from J(qt)J(q_t) without replacement and receives response Y~t,1,…,Y~t,R. Y_t,1,…, Y_t,R. Then , Y^t=modeY~t,1,…,Y~t,R, Y_t=mode\ Y_t,1,…, Y_t,R\, and uses this as the estimated response of qtq_t. If the remaining exposure budget cannot pay for all R(p)R(p) local queries, Robust k-ALeBi abstains rather than using a smaller block. When p=0p=0, the cell size is consummed, so Robust k-ALeBi coincides with k-ALeBi. The implemented attacks use independent Bernoulli-p attack, which are a special case of Assumption 3.8. When an attack occurs, the experiment chooses an incorrect relational response that increases the current absolute statistical-parity estimation error. F.2 Auditors Baselines The supplied Yan and Zhang, (2022) implementation DiamAudit performs a search in the current linear version space for hypotheses with high and low statistical-parity values and queries a point on which they disagree. The Yan curves use the original version-space average statistical-parity error computed by a hit-and-run evaluation protocol on the model class. For k-ALeBi, we use a Monte-Carlo approximation of the same linear-model family. A CGQ contains one individual from each group and therefore may cost up to two exposed individual predictions per coordinate i≤ki≤ k. The horizontal axis measures these individual predictions exposed allowing model extraction attacks. The original implementation of Yan and Zhang, (2022) baseline is not run on German Credit. The supplied implementation assumes a binary protected attribute, whereas our German Credit setup contains four status_and_sex groups, for a total of k=6k=6 groups. For the plotted comparison where k=2k=2, k-ALeBi and DiamAudit are evaluated using the same statistical-parity unfairness μ=|P(h=1∣A=1)−P(h=1∣A=0)|μ= |P(h=1 A=1)-P(h=1 A=0) | with absolute value estimation error |μ^−μ⋆|| μ-μ |. The original saved Yan and Zhang, (2022) endpoint appears only in the validation table because it retains the evaluation convention of their implementation. All our computations are performed on an 11th Gen Intel® Core™ i7-1185G7 processor (3.00 GHz, 8 cores) with 32.0 GiB of RAM.