acceptodds
Under review as a conference paper at ICLR 2027

Shapley Data Auditing Certificates: Bounding Downstream Fairness Without Model Access

Abstract

Alignment auditing is organizationally separated from model development: those who assemble and curate data, those who train models, and third parties who assess the system for fairness and privacy compliance, rarely hold the same information. We take this role separation as our design constraint and ask what an auditor can certify using only the information its role grants. We formalize a staged pipeline in which each block consumes the output of the previous one, and attach to a data block a stage-local certificate: a Shapley attribution of downstream accuracy and group-fairness violation to that block's input features, computed from dependence measures over data variables alone, with no access to the model or its predictions. A tight one-sided guarantee makes the certificate meaningful under restricted access: the mutual-information and conditional-mutual-information certificates upper-bound the sensitive-attribute leakage—hence the statistical-parity and equalized-odds (EO) gaps—of every predictor built downstream, with equality exactly when the downstream model realizes all of that leakage. By benchmarking 26 measures on seven datasets, with robustness across seven downstream predictors, we quantify the pre-hoc attribution gap—the fidelity a data auditor forfeits by not holding model access—and trace it to whether a measure's scale moves with coalition size. A final study prices the audit itself: permutation sampling brings a 20-feature certificate whose exact evaluation costs 71–150 hours down to sub-1% error in 30–70 minutes, while declared causal constraints move fidelity non-monotonically, so the constraint set must be reported. When a biased upstream annotator emits a stage's supervision, a two-stage study on 26 U.S. states shows that label-dependent certificates register the upstream block, the statistical-parity certificate is blind to it, and an EO certificate on inherited labels does not decisively reveal whether downstream harm rises or falls. Our results yield construction guidelines indexed by access regime—rather than by objective, bounding the price of the information asymmetry that alignment governance is built on.

Primary area:
interpretability and explainable AI
Keywords:
Shapley-based data auditing, fairness and privacy alignment, explainable machine learning, information measures, PID

Reviews

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

This paper proposes a framework for auditing downstream model fairness without requiring access to the trained model or its predictions. It introduces stage-local Shapley certificates based on information-theoretic dependence measures and establishes one-sided guarantees bounding sensitive-attribute leakage and downstream fairness violations. The authors evaluate 26 measures across seven datasets and multiple downstream predictors, examining attribution fidelity, computational efficiency, and robustness to model choice. Additional experiments investigate scalable Shapley approximation and the effects of biased upstream supervision on fairness auditing.

Critical strengths
  1. The paper addresses an important and practical limitation of fairness auditing, where auditors may not have access to downstream models. The formalization of information-access constraints and the one-sided theoretical guarantees provide a useful foundation for model-independent auditing.
  2. The empirical evaluation is extensive, covering multiple dependence measures, datasets, and downstream predictors. The computational cost analysis and experiments on inherited supervision provide valuable insights into the limitations and practical applicability of the proposed certificates.
Critical weaknesses
  1. The theoretical novelty is somewhat limited, as the main fairness guarantees follow from established information-theoretic inequalities. Furthermore, these guarantees are one-sided and apply to specific MI/CMI measures rather than all evaluated certificates, limiting their ability to predict actual downstream fairness violations.
  2. The attribution evaluation relies on leave-one-out feature effects rather than ground-truth Shapley attributions, making it difficult to fully establish attribution fidelity. Additionally, most experiments use low-dimensional tabular datasets, the main benchmark averages only three seeds, and the applicability to high-dimensional learned representations remains unclear.
  3. The multi-stage evaluation is relatively limited, relying on a controlled upstream label-bias mechanism. While the experiments demonstrate sensitivity to inherited supervision, the certificates cannot reliably determine the direction of downstream fairness harm when true labels are unavailable.
Questions for authors
  1. Can the authors quantify how tight or informative the proposed MI/CMI fairness bounds are for the actual downstream predictors, rather than primarily evaluating attribution agreement?
  2. Can the authors evaluate attribution fidelity against model-based Shapley references instead of relying only on leave-one-out feature effects?
  3. How well would the framework scale to high-dimensional learned representations or more complex multi-stage pipelines, where exact Shapley computation becomes infeasible?
  4. How should auditors interpret certificates computed from potentially biased inherited supervision when reliable reference labels are unavailable?
2 comments
AuthorsOpenReview ↗

Official Rebuttal to Reviewer TZdx

We thank the reviewer for their time and detailed feedback and for finding our work valuable. We respond below.

New numbers use the paper's pipeline on Adult + COMPAS (7predictors x 5seeds); our revision will extend them to all 7 datasets

W1 + Q1 (Novelty, One-sided guarantee + Tightness): We agree with the reviewer's assessment and clarify 3 points:

  • What is new in the guarantee? The inequality behind Prop.1 is the standard data-processing inequality in information theory (Cover & Thomas), as the reviewer notes; what we claim as new here is its use <-- It turns a measure into a certificate for every downstream predictor (cf. Sec4)
  • Why one-sided, and MI/CMI only? This is inherent in our formulation; a data-side quantity cannot know which part of the available dependence a model will use (cf. Remark2). A small certificate rules out a large gap for every downstream model; a large one does not predict harm. "Certificate" is now kept for the set-level MI/CMI values + measures with no guarantee (PID, kernel, product) are renamed "attribution scores"
  • Q1 again, Tightness for actual predictors? Bound vs Realized SP-gap ΔSP\Delta_{SP} on the full feature set: On Adult, cap 0.66-0.91 and realized 0.17-0.19. On COMPAS, cap 0.28-0.36 and realized 0.20-0.24 -> Loose on Adult (1 feature carries 86% of I(A;X)I(A;X); AA is the sensitive attribute), while within 1.1-1.4x on COMPAS. Across feature sets, a larger certificate goes w/ a larger realized gap (Spearman 0.74-0.84) -- see more details in response to Reviewer 7enP

W2 + Q2 (LOO Ref vs Shapley Ref + Seeds): Done; answering to the concern of "model-based Shapley references":

  • Shapley value (SV) Ref? Certificate error (accuracy/SP/EO, %) is 9.3/5.5/7.5 (LOO Ref) vs 9.3/6.3/5.0 (SV Ref) on Adult; 6.2/15.9/18.7 vs 5.5/9.2/11.2 on COMPAS; random attributions score 33-36% -> Conclusions hold & SV Ref will be the main one in our revision
  • Why this matters? With a duplicated proxy, LOO Ref gives both copies exactly 0 while SV Ref + the certificate split the value (please also see W3 in response to Reviewer 1ewa)
  • Seeds? These runs use 5 seeds + 7 predictors; our revision raises the main benchmark from 3 to 5 seeds. S.d. over the 35 runs is 0.9-3.0 points on SV Ref vs 1.0-6.6 on LOO Ref

W2 + Q3 (Dimension + Learned representations):

  • Why about 20 features is our limit? A feature-level audit targets interpretable attributes on which a human or a pipeline stage can act (e.g. drop, repair or justify a feature). Runtime already binds at this size as well; Exact SVs cost 71h (accuracy, SP) and 150h (EO) at 20 features, while sampling reaches <1% error in 30-70min, a >72x speedup (Sec5.4)
  • Does the guarantee need SVs? No. The set-level certificate is ONE MI estimate -> it scales with the estimator, not with 2m2^m (m=m=#features)
  • Learned representations? Single coordinates are not interpretable -> the actionable unit is a group of coordinates, so we would audit groups. We do not claim this yet; it goes to our Discussion/Limitations section
  • Longer pipelines? Prop.1 applies stage by stage and Remark3 tells what each stage's certificate is relative to

W3 + Q4 (Multi-stage study + Biased inherited labels): We see Sec5.5 as a first controlled study of this question; we state its limits clearly as follows:

  • What is tested? Hypotheses were fixed before the runs (cf. App.I) on 26 states + a synthetic pipeline, with one upstream block and one label-bias mechanism
  • What does it establish? The SP-certificate is identical under inherited labels YkY_k & true labels YY in all 26 states. The accuracy certificate falls in all 26 (by 42-56% at the strongest label bias). The EO certificate bounds EO relative to YkY_k only (cf. Remark3). The direction of harm against YY cannot be identified from (X,A,Yk)(X, A, Y_k), by a certificate or by a surrogate (see also, W4 in response to Reviewer 1ewa)
  • Q4: How should auditors read a certificate w/o reference labels? (i) Use the SP-certificate as the label-free screen; (ii) Read the EO certificate as a bound relative to YkY_k + record which block emitted YkY_k (cf. P5); (iii) Compare the accuracy certificate with an earlier one of the same stage to detect whether the supervision changed. Beyond this, we need an explicit model of the label noise (e.g., a bound on group-wise flip rates), which adds an uncertainty band around the EO certificate. We note that as a natural next step in our Discussion

Summary. (1) The guarantee is a standard inequality used as a set-level certificate; we now also measure its tightness. (2) SV Ref is adopted; same conclusions hold. (3) The 20-feature limit matches actionable audits. (4) On inherited labels, the limit + how to read the certificate are stated. We hope these clarifications address the soundness concerns and the reviewer will consider raising the score.

AuthorsOpenReview ↗

Rebuttal reminder; PDF uploaded (all 4 points addressed)

Dear Reviewer TZdx,

With the discussion closing on Nov 18 (AoE), we would kindly ask you to check whether our responses address your concerns.

The 4 points of our summary (from our rebuttal above) are in the revised PDF:

  • W1 + Q1 (Tightness). The bound is reported next to the realized gap on all 7 datasets (new Sec5.3, Tbl3 + Tbl17; table in our most recent reply to 7enP): the TV cap is within 1.1-1.4x of the realized gap on COMPAS, 1.1-1.3x on ACS Emp. and 1.8-1.9x on ACS Income, and loose elsewhere
  • W2 + Q2 (SV Ref + seeds). The SV Ref is the main one in Sec5.3 + AppJ, now on all 7 datasets (Tbl17), with 5 seeds throughout
  • W2 + Q3 (Dimension + learned representations). Sec5.5 + Discussion/Limitations
  • W3 + Q4 (Inherited labels). Sec5.6 + Limitations, with how to read certificates without reference labels

Corrections to our rebuttal above; random signed 33-37%, not 33-36%; speedup over 60x, not >72x

If any part remains unclear, we would be glad to clarify it right away.

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

This paper proposes Shapley values as a "certificate" for fairness by data auditors, when those auditors may not know the downstream model. Proposition 1 states that a model that relies only on features cannot reveal more about a sensitive attribute than the features do. The paper uses seven datasets (e.g., ACS Income, COMPAS) to test five research questions, with a leave-one-out reference proxy. Q1 reports results of certificates across these datasets, with the certificate based on how informative each feature is about the sensitive attribute performing best. Q2 shows that these findings are comparable across model types. Q3 shows that knowing the model helps. Q4 shows what happens when features expand to 20. Q5 shows that the certificate becomes less meaningful when there is label bias.

Critical strengths

Developing better audit tools for the full pipeline of modeling is valuable.

Critical weaknesses

Much of the technical contribution is already in the Aldarmini & Nafea (2025) workshop paper (https://openreview.net/pdf?id=ZsqigefFO8). That paper is cited, but it would be helpful to articulate the distinctions.

Proposition 1 bounds the value function, but that doesn't directly connect to the certificates, so I'm unclear about the practical relevance of the proposition.

I'm really not sure how to think about the LOO reference. What if there is redundant encodings of sensitive attributes (a longstanding concern)?

The Q5 results seem most challenging for the idea of the certificate.

The language of "certificate" seems stronger than what the actual measure is.

Questions for authors

Can you address the weaknesses above?

2 comments
AuthorsOpenReview ↗

Official Rebuttal to Reviewer 1ewa

We thank the reviewer for their time and focused feedback, and for finding our work valuable. We respond below.

Throughout; New numbers use the paper's pipeline on Adult + COMPAS (7predictors x 5seeds); our revision will extend them to all 7 datasets

W1 (vs Aldarmini & Nafea, 2025): The reviewer is correct; we will highlight the following lines in Sec1, answering to the suggestion of "articulate the distinctions":

  • Taken from that paper--The MI/CMI/PID measures (cited w/ their definitions). The inequality behind Prop.1 is the standard data-processing inequality in information theory (Cover & Thomas); what we claim is its use <-- It turns a measure into a certificate for every downstream predictor (cf. Sec4)
  • New here--(i) Roles, access sets + admissibility, and who may compute what (Sec3); (ii) Certificates w/ a guarantee for every downstream predictor + what they cannot establish (Sec4); (iii) A benchmark read by role against 7 predictors, not ONE network (Sec5); (iv) The price of role separation, the cost of issuing a certificate + 5 guidelines (Sec5.3-6); (v) What a stage can certify on inherited labels, on 26 states (Sec5.5)

W2 (Prop.1 -> Certificates): The reviewer is correct; this link was missing & we add it to our revision, answering to the question of "practical relevance of the proposition" as follows:

  • Prop.1 holds for every feature set SS -> v(XS)v(X_S) caps the leakage of ANY predictor that uses XSX_S. The certificate is now this set-level MI/CMI value, issued ∀S\forall S. This is to say Each set value is a bound
  • Shapley values (SVs) split it as ϕi\phi_i sum to the 'Full-Set' certificate, ∑iϕi=v(X[m])\sum_i \phi_i = v(X_{[m]}) (m=m=#features) -> we report them as how the certificate splits across features, not as per-feature guarantees
  • How to read it? A small certificate rules out a large gap for every downstream model; a large one does not predict harm (cf. Remark2)
  • How tight in practice? Bound vs Realized SP-gap ΔSP\Delta_{SP} on the full feature set: On Adult, cap 0.66-0.91 and realized 0.17-0.19. On COMPAS, cap 0.28-0.36 and realized 0.20-0.24 -> Loose on Adult (1 feature carries 86% of I(A;X)I(A;X); AA is the sensitive attribute), while within 1.1-1.4x on COMPAS -- see a more detailed comment in response to Reviewer 7enP

W3 (LOO Ref + Redundancy): This is certainly valid and we tested it directly for our revision, answering to the question on "redundant encodings of sensitive attributes":

  • The Test. We duplicated the strongest proxy of AA (NN, HGB, LR; 3 seeds on Adult). LOO Ref gives both copies exactly 0 (from 0.09-0.10 on Adult, 0.04-0.07 on COMPAS) -> it calls the main proxy irrelevant
  • How do Shapley value (SV) Ref and our certificates respond? SVs of the realized gap split the value between the 2 copies & so does the certificate's allocation; the set-level certificate is unchanged
  • Certificate SP error? 22-29% (LOO Ref) vs 14-17% (SV Ref) on Adult; 15-19% vs 6-7% on COMPAS
  • Our FIX: SV Ref becomes the main one. On it, certificate error (accuracy/SP/EO, %) is 9.3/6.3/5.0 on Adult and 5.5/9.2/11.2 on COMPAS vs 33-36% for random attributions -> Conclusions hold

W4 (Q5): We agree it is "most challenging" as it marks a limit that no data-side method can cross; yet:

  • What does Q5 show? The bound is not violated. Prop.1 holds with the inherited label YkY_k in place of the true label YY (cf. Remark3). What failed is the reading <-- A falling EO certificate on YkY_k says nothing about EO against YY (on the synthetic pipeline, the certificate falls 35% while the realized gap rises 8.9 points)
  • Why do we claim no data-side method escapes it? The downstream auditor sees (X,A,Yk)(X, A, Y_k) only. This is consistent with both an unbiased and a biased YkY_k -> EO against YY cannot be identified from the stage's data, by a certificate or by a surrogate
  • What can a stage still certify? The SP certificate uses no labels -> identical under YkY_k & YY in all 26 states. The accuracy certificate falls in all 26 states (by 42-56% at the strongest label bias) -> compared with an earlier certificate of the same stage, it detects that the supervision changed (cf. Sec5.5)
  • Our FIX: We state this limit explicitly in the abstract; the record of which block emitted YkY_k already belongs in the certificate (cf. P5)

W5 (Language of "certificate"): We accept the reviewer's assessment here. Answering to the remark "stronger than what the actual measure is"; a "certificate" is kept for the set-level MI/CMI values, which carry the Prop.1 guarantee. SVs become "attributions"; measures w/ no guarantee (PID, kernel, product) are renamed "attribution scores" & our conclusion is updated throughout <-- "The provable bound is claimed for set-level MI/CMI only"

Summary. All 5 points are adopted; W2 + W3 are now backed by numbers. We hope the reviewer will consider raising the score.

AuthorsOpenReview ↗

Rebuttal reminder; PDF uploaded (all 5 points addressed)

Dear Reviewer 1ewa,

With the discussion closing on Nov 18 (AoE), we would kindly ask you to check whether our responses address your concerns.

All 5 points are in the revised PDF:

  • W1 (vs Aldarmini & Nafea, 2025). Sec1 ("Relation to prior measures") states what is taken from that paper and what is new here
  • W2 (Prop.1 -> certificates). The certificate is the set-level MI/CMI value, issued for every feature set (Sec4); the bound is now reported next to the realized gap on all 7 datasets (new Sec5.3, Tbl3 + Tbl17; table in our most recent reply to 7enP)
  • W3 (LOO Ref + redundancy). The redundancy test is in Sec5.3; the SV Ref is the main one in Sec5.3 + AppJ, now on all 7 datasets (Tbl17; e.g., 0.6/1.5/3.3 on ACS Emp. and 13.7/16.6/16.7 on ACS Pub. Cov., accuracy/SP/EO, %)
  • W4 (Q5). The limit is stated in the abstract and Sec5.6, with how to read certificates without reference labels
  • W5 (Language). "Certificate" is kept for the set-level MI/CMI values; measures with no guarantee are "attribution scores" throughout

Corrections to our rebuttal above: Adult LOO before duplication 0.09-0.11, not 0.09-0.10; random signed 33-37%, not 33-36%

If any part remains unclear, we would be glad to clarify it right away.

Reviewer_7enPOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Fairness audits usually need access to the trained model. This paper asks what an auditor who holds only the data, not the model, can certify about the fairness of models trained on it. It formalizes which auditing role may access what. The proposed "stage-local certificate" uses Shapley values to split a dependence measure between the features and the sensitive attribute, such as mutual information, across individual features. The main result says that the mutual information between a set of features and the sensitive attribute bounds how much any predictor that uses only those features can reveal about the attribute, which in turn caps its statistical-parity and equalized-odds gaps. Experiments on several tabular datasets with a handful of features compare the certificates with leave-one-out changes in the fairness gaps of trained models from several families. A two-stage study injects label bias upstream and asks what a downstream certificate can detect.

Critical strengths
  1. The two-stage study gives a useful negative result: an equalized-odds certificate computed on inherited labels does not track downstream harm. The certificate falls in every state, while the realized gap rises in a few. I like that this is measured against realized gaps and that the failed pre-specified hypothesis is reported. It is a useful warning, if only for one label-bias mechanism.

  2. Within the paper's protocol, the best certificate for each objective rarely depends on the model class. A data-side report is written before anyone picks a model, so this is the property it needs. Lower ranks do swap, though, and no model here is trained to suppress dependence on the sensitive attribute, where the bound should be slack.

Critical weaknesses

1. The guarantee covers sets of features, but the paper certifies and evaluates single features.

  • The main result bounds the leakage of a set of features, and the Shapley values add up to the leakage of the full set. A single feature's value carries only a weak bound: its own leakage is at most the number of features times its value. Two copies of one proxy each get half of the leakage, yet dropping either copy leaves the bound unchanged.
  • Still, the conclusion claims that the certificates provably bound the fairness gap of every downstream model. Yet the best-scoring certificates for both fairness objectives have no guarantee at all, as the paper acknowledges.
  • The bound itself is never set beside a realized gap. From the reported mutual information, the implied cap on the statistical-parity gap is large even in the most favorable case, so it rules out little. Issuing the feature-set value as the certificate, with the per-feature values as a diagnostic, would match the guarantee to what is reported.

2. The access model rules out the strongest data-only auditor without a good reason.

  • The paper's own admissibility rule allows any method whose output is a function of the auditor's data, so a surrogate model fitted on that data qualifies.
  • The paper excludes surrogates for two reasons: the downstream features may not exist yet, and the auditor may be barred from holding the data. Neither applies in the benchmark, which audits the stage where the features exist. The information-theoretic certificates also already use the full joint distribution of the quantized data, which is all one needs to fit a model.
  • A surrogate gives no guarantee, but neither do the per-feature values beyond the weak bound above. So the paper's estimate of what role separation costs rests on a restriction its own access model does not impose.

3. The benchmark may not separate good certificates from bad ones.

  • The error metric rescales both the certificate and the reference by their largest entry, which discards the magnitude that the guarantee controls.
  • In the synthetic study, the paper's own negative control, which is wrong in direction, scores about as well as the main conditional-MI certificate on the graphs where the parity and odds mechanisms differ (Table 3).
  • The reference is the leave-one-out change of one trained network. If the prediction-aware certificates use the same network, part of their advantage is self-agreement, and the paper does not say which network they use.
Questions for authors
  1. How do surrogate attributions compare with the best certificates? On the ACS datasets this needs no new training: the leave-one-out profiles of all model families already exist, so each family can act as the surrogate for the others. If the surrogate is not clearly better, my concern about the access model is resolved.

  2. Could you score the main benchmark against exact model-based Shapley values of each downstream metric, and compute the prediction-aware certificates from a different model than the reference? The prediction-aware certificates already need the restricted predictions for every coalition, so the cost argument in the limitations does not seem to hold.

  3. What does the benchmark add beyond Nafea & Aldarmini (2026)? The paper describes that study as already comparing restrictions for Shapley-based fairness attribution on several real datasets, with synthetic graphs of the same groups.

Minor:

  • A certificate should hold for the population, so I would report a high-probability upper bound on the mutual information instead of a plug-in estimate. Quantization can only lower mutual information, so a value computed on coarse bins covers only models that use the same bins, and an issuer could shrink it by coarsening them.
  • Absolute error differences would read more clearly than the relative gap, which explodes when the post-hoc error is tiny.
  • To show what Shapley aggregation adds, I would compare it with simpler attributions of the same measure: the single-feature value, the drop when one feature is removed, and a uniform attribution. These would also anchor the error scale.
3 comments
AuthorsOpenReview ↗

Official Rebuttal to Reviewer 7enP – Full Response

We thank the reviewer for their time and detailed feedback and respond below. New numbers use the paper's pipeline on Adult + COMPAS (7predictors x 5seeds); our revision will extend them to all 7 datasets:

W1 (Set-level vs Per-feature): The reviewer is correct. The fix is in what we report here not in our result; Recall that Prop.1 holds already for every feature set SS. What we changed:

  1. The Certificate: It is now the set-level MI/CMI value v(XS)v(X_S), issued ∀S\forall S. Shapley values (SVs) ϕi\phi_i sum to the 'Full-Set' certificate, ∑iϕi=v(X[m])\sum_i \phi_i = v(X_{[m]}) (m=m=#features) -> so we report them as how the certificate splits across features, not as per-feature guarantees
  2. Measures w/ no guarantee: vSP,SI:2v_{SP,SI:2} & vD,Prodv_{D,Prod} carry no guarantee (P2 + App. G.2 say so). Our conclusion overstated this; we will fix it -> these 2 measures are renamed "attribution scores" & our conclusion is updated throughout: "the provable bound is claimed for set-level MI/CMI only"
  3. Bound vs Realized-gap: Here we use the full feature set; ΔSP\Delta_{SP} is the SP gap. On Adult, I(A;X)I(A;X) = 0.316 nats, cap on ΔSP\Delta_{SP} 0.66-0.91 and realized 0.17-0.19. On COMPAS, 0.059 nats, cap 0.28-0.36 and realized 0.20-0.24--> Loose on Adult (1 feature carries 86% of I(A;X)I(A;X)), while within 1.1-1.4x on COMPAS. This is what Remark 2 mentions; explicitly measured
  4. Units: Tbl14 reports I(A;X)I(A;X) in bits not nats -> implied caps are ~17% lower

W2 + Q1 (Surrogates): This is outside our scope & Deliberately so; below is why:

  • Sec3 says right after Def1 that training a ref model on the stage's data is inadmissible for the data auditor
  • A surrogate is a model as it carries its own inductive bias, split+seed, so its attribution describes that ONE fit. A certificate is a statement about every downstream predictor
  • Labels: vSP,MIv_{SP,MI} uses no labels; on inherited labels (Sec5.5), a surrogate would be trained on the biased supervision itself

We believe surrogate faithfulness deserves its own study; we say so in Limitations + tighten our Def1's wording. Still, we ran the test --> Each predictor family's profile is the surrogate for the other 6 below (SP/EO error, %):

  • LOO Ref--The reviewer's comparison: Adult 5.7/7.6 (surrogate) vs 5.5/7.5 (vSP,MIv_{SP,MI}/vEO,CMIv_{EO,CMI}). COMPAS 8.3/9.5 vs 7.7/9.2 (vSP,SI:2v_{SP,SI:2}). The surrogate is closer in 44-48% of family pairs on Adult and 52-55% on COMPAS. We conclude it is not clearly better
  • SV Ref--Q2: Adult 2.9/3.8 vs 6.3/5.0. COMPAS 2.2/2.6 vs 6.8/6.3. It is ahead but its error moves->1.3-2.3x w/ the split alone->The model dependence in 2nd bullet above. ACS and vSP,SI:2v_{SP,SI:2} on Adult will be in the revision

W3: Does the benchmark separate certificates?

  1. Normalization. Certificates + Ref are in different units -> the error compares how value splits across features; magnitude is now reported (W1). Random attributions score 33-36% vs 5-19% for the certificates
  2. Negative control. The reviewer is correct for the EO column of Tbl3; the LOO Ref is the reason. On 78 sampled DAGs w/ distinct SP+EO mechanisms, EO error of vEO,CMIv_{EO,CMI} vs the faulty control is 26.3 vs 27.4 on LOO Ref (certificate closer on 50%; Wilcoxon pp=0.59) and 18.0 vs 36.0 on SV Ref (82%; pp=9e-11). Tbl3 will be re-scored on all DAGs
  3. Same network? Yes; v∗v^* uses the Ref's architecture, seed+split; we will state it. From a different predictor family its error rises by 1.5-2.4 points (e.g., Adult SP 3.5->5.0) vs 6.4 for the pre-hoc certificate

Q2 (SV Ref): Done. Certificate error (accuracy/SP/EO, %): Adult 9.3/5.5/7.5 (LOO) vs 9.3/6.3/5.0 (SV). COMPAS 6.2/15.9/18.7 vs 5.5/9.2/11.2 -> Conclusions hold; SV Ref becomes the main one. We agree on cost; Limitations will be restricted to the 20-feature study

Q3; vs Nafea & Aldarmini, 2026. That study (cited in Sec2 + AppC) compares restrictions for a few MI/PID measures against ONE network. We fix the restriction they recommend + read the benchmark by role--> which measures each access set admits (Def1), what the data auditor gives up w.r.t. model access (Q3), across predictor families (Q2) + on inherited labels (Q5)

Minor edits:

  • Population bound--A finite-sample MI guarantee is its own research question; we will report a bias-corrected value w/ a 1-sided upper confidence limit
  • Quantization--Prop.1 will state the bound is for the declared bins, which become a required field (P5). A strategically coarsening issuer is a threat model we do not pose
  • Absolute differences--Adopted
  • Simpler attributions--(SP error vs SV Ref--SV/single-feature/drop-one/uniform): Adult 6.3/6.6/5.4/34.1. COMPAS 9.2/8.2/10.9/30.3

Summary. The reviewer rates soundness as "minor or fixable". W1 is adopted as proposed, Q2 is done, & under the reviewer's own criterion in Q1 the concern on the access model is resolved. We hope the reviewer will reconsider the score.

AuthorsOpenReview ↗

Follow-up to our rebuttal above – Supporting details

Same setup (Adult + COMPAS, 7predictors x 5seeds). Nothing here changes the answers above

W1: Bound vs Realized-gap:

  • 3 caps on ΔSP\Delta_{SP}--Remark 1 closed form/exact inversion of the MI bound/total-variation (TV) distance between the 2 groups' feature distributions. On Adult, 0.91/0.79/0.66. On COMPAS, 0.36/0.35/0.28. The TV cap is new; some predictor attains it -> no data-side cap can be smaller
  • How much of the bound is used? Predictors realize 8% of I(A;X)I(A;X) on Adult and 34-50% on COMPAS (I(A;Y^)/I(A;X)I(A;\hat Y)/I(A;X); Y^\hat Y is the thresholded prediction)
  • Ordering? Across feature sets, a larger certificate goes w/ a larger realized gap (Spearman 0.82-0.84 on Adult, 0.74-0.79 on COMPAS)
  • When the cap is informative? 17 of 63 Adult feature sets and 23 of 31 COMPAS feature sets have a TV cap <= 0.2
  • Sampling? Computed on the evaluation sample, the TV cap is never exceeded (0 of 3,290 feature-set runs). A plug-in cap from the full data is exceeded by test-split gaps in 2% of runs on Adult and 26-37% on COMPAS (1,742 test rows), never for the full feature set -> we will report each cap w/ an upper confidence limit

W2 + Q1: Surrogates:

  • What if the surrogate is trained on a different split? An auditor's surrogate would be, since the auditor does not hold the target's split. On LOO Ref, it is then closer than vSP,SI:2v_{SP,SI:2} in only 22-23% of family pairs on COMPAS (52-55% on the same split). On SV Ref, its SP/EO error rises from 2.9/3.8 to 3.8/4.9 on Adult and from 2.2/2.6 to 4.9/5.9 on COMPAS
  • Accuracy? Here the surrogate is far ahead: error 0.8 vs 9.3 for the certificate on Adult, 1.2 vs 5.5 on COMPAS (SV Ref). We state this clearly in the revision
  • vD,Prodv_{D,Prod} on COMPAS? SP/EO error 18.5/19.0 (LOO Ref) and 11.1/11.0 (SV Ref) -> it scores like vEO,CMIv_{EO,CMI} (18.4/18.7 and 11.2/11.2)

W3: Negative control + Same network:

  • Which DAGs? 317 randomly sampled stored DAGs, ONE network each. Absolute errors are lower than in Tbl3 (10 networks per DAG) -> we compare within this run only
  • All 317 DAGs? EO error of vEO,CMIv_{EO,CMI} vs the faulty control is 21.1 vs 28.7 (LOO Ref) and 17.6 vs 34.5 (SV Ref)
  • The 78 distinct SP-EO DAGs? A random non-negative attribution scores 20.7 (LOO Ref) and 30.5 (SV Ref). So on LOO Ref the certificate (26.3) is not below random, while on SV Ref (18.0) it is. The 2 Refs disagree w/ each other by 31% for EO on these DAGs
  • v∗v^* from a different predictor family? Error vs the NN's SV Ref (SP/EO): Adult 3.5/2.9 -> 5.0/5.3. COMPAS 3.9/4.4 -> 5.7/6.1. Pre-hoc certificates score 6.4/4.4 (Adult) and 8.3/10.0 (COMPAS) -> model access still helps in 3 of 4 cases; for EO on Adult the pre-hoc certificate is ahead

Q2: LOO Ref vs SV Ref:

  • How far apart are the 2 Refs? They differ by 5-6% (Adult) and 10-11% (COMPAS) for SP/EO
  • What happens under redundancy? We duplicated the strongest proxy of AA (NN, HGB, LR; 3 seeds on Adult). LOO Ref gives both copies exactly 0 (from 0.09-0.10 on Adult, 0.04-0.07 on COMPAS) -> it calls the main proxy irrelevant. SV Ref + the certificate split the value between the 2 copies; the set-level certificate is unchanged & dropping either copy leaves it unchanged
  • Certificate error under redundancy? SP error is 22-29% (LOO Ref) vs 14-17% (SV Ref) on Adult; 15-19% vs 6-7% on COMPAS
  • Random level? 33-36% for a signed random attribution; 22-26% for a non-negative one

Minor edits: Simpler attributions w/ a duplicated proxy:

  • Errors? SP error vs SV Ref (SV/single-feature/drop-one/uniform): Adult 14-17/16-19/18-20/20-27. COMPAS 6-7/14-16/11/32-34
  • Reading? Drop-one gives both copies 0. SV is lowest on both datasets & is the only one that sums to the certificate
AuthorsOpenReview ↗

Rebuttal reminder; PDF uploaded + numbers on 7 datasets

Dear Reviewer 7enP,

With the discussion closing on Nov 18 (AoE), we would kindly ask you to check whether our responses address your concerns.

Updates from the newer runs (Sec5.3, Tbl3 + AppJ) are listed below:

W1. TV cap vs realized ΔSP on the full feature set:

DatasetTV capRealized ΔSP
COMPAS0.270.20-0.24
ACS Emp.0.370.28-0.34
ACS Income0.200.10-0.11
Adult0.660.17-0.19
ACS Pub. Cov.0.090.003-0.010
Census-KDD0.180.011-0.013
Heritage0.390.05-0.07
  • Minor corrections to our preliminary numbers: COMPAS TV cap 0.27, not 0.28; I(A;X) 0.058, not 0.059 nats; leakage 34-49%, not 34-50%; Adult LOO before duplication 0.09-0.11, not 0.09-0.10; random signed 33-37%, not 33-36%; COMPAS single-feature with duplicated proxy 14-15, not 14-16
  • With the 95% limit, 0 of 3,815 (default) and 0 of 9,275 (tuned, all 7 datasets) feature-set runs exceed the TV cap; Spearman 0.74-0.84 (Adult + COMPAS), 0.47-0.57 (ACS Income)

W2 + Q1. On ACS Income, SV Ref, the surrogate scores 0.4/0.5/1.1 (accuracy/SP/EO) vs 3.7/15.0/23.9 for the certificates' attributions, also ahead on a different split (0.5/0.9/2.4); Def1 says why it is outside the data auditor's access

W3. On 333 distinct SP-EO DAGs (re-run on 717; Tbl4 stores LOO only), EO error of v_EO,CMI vs the faulty control: 43.3 vs 42.1 on LOO Ref (closer on 45%); 18.5 vs 34.0 on SV Ref (closer on 78%; p=4e-35); random non-neg. 47.8/30.0 -> same reading as before; these replace our 78- and 317-DAG numbers (all 717: 38.7 vs 41.5 LOO, 16.9 vs 34.6 SV)

Q2. On ACS Income: 5.3/14.0/26.7 (LOO) vs 3.7/15.0/23.9 (SV); the EO attribution is at the random non-negative level (22-26%), now stated as a dataset-based limitation (Sec5.3 + Limitations). Census-KDD + Heritage (SV Ref): 9.9/20.8/21.5 and 8.6/21.3/23.0, SP/EO modestly below random non-neg. (26.5-28.2%; AppJ)

If any part remains unclear, we would be glad to clarify it right away.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response to all reviewers

We thank all reviewers for their thoughtful and detailed feedback. Several questions overlapped across reviews; they guided our new experiments and strengthened our paper. Each individual response is self-contained, so some overlap between them is intended. New numbers use the paper's pipeline on Adult + COMPAS (7predictors x 5seeds); our revision will extend them to all 7 datasets. A revised PDF will be uploaded soon with changes marked.

Summary of changes from submission to revision:

  1. Set-level certificate. The certificate is now the set-level MI/CMI value, issued for every feature set; Shapley values are reported as how it splits across features, not as per-feature guarantees (7enP, 1ewa, TZdx)
  2. Language. "Certificate" is kept for the set-level MI/CMI values that carry the Prop.1 guarantee; measures with no guarantee are renamed "attribution scores", and our conclusion is updated throughout (7enP, 1ewa, TZdx)
  3. Tightness. The bound is now reported next to the realized fairness gap (7enP, 1ewa, TZdx), with an added total-variation cap and corrected units in Tbl14 (7enP)
  4. Reference. Shapley values of the realized metrics become the main reference; a redundancy test shows why. Conclusions hold (7enP, 1ewa, TZdx)
  5. Scope. We clarify that a trained surrogate is outside the data auditor's role (Def1 + Limitations), and report the cross-family test (7enP)
  6. Prior work. Sec1 states what is taken from Aldarmini & Nafea (2025) and what is new here (1ewa, TZdx)
  7. Inherited labels. The limit of what a stage can certify is stated in the abstract, with guidance on reading certificates without reference labels (1ewa, TZdx)
  8. Protocol. The main benchmark moves from 3 to 5 seeds; Tbl3 is re-scored; dimension and learned-representation scope are stated in Discussion/Limitations (7enP, TZdx)

We are grateful to the reviewers; these changes sharpened our claims.

AuthorsOpenReview ↗

Rebuttal reminder; PDF uploaded (changes in blue)

Dear Reviewers,

Thank you again for your reviews. The revised PDF is uploaded, along with the full anonymized code as supplementary material.

Since the discussion closes on Nov 18 (AoE), we would kindly ask you to check our responses against the revised PDF and let us know whether your main concerns are addressed.

Two differences from the changes listed above: (i) the SV Ref is the main Ref in Sec5.3 + AppJ, while Tbl1-2 keep the LOO Ref; and (ii) the synthetic table (Tbl4) stores only LOO values, so we re-ran 717 DAGs with both Refs instead of re-scoring it. The benchmark now reports 5 seeds. Section numbers from Sec5.3 and table numbers from Tbl3 on are shifted by one (new Sec5.3 + Tbl3). Updates since our responses are listed below:

  • Datasets. New numbers now cover all 7 datasets: Adult, COMPAS, Census-KDD, Heritage + the 3 ACS tasks (7 predictors x 5 seeds); Sec5.3 (Tbl3) + AppJ
  • Tuned predictors. AppJ repeats Tbl3 with the 6 tree + linear predictors tuned on a validation split -> SV Ref errors move by <= 0.3 points on Adult + COMPAS; caps do not depend on the predictor; Tbl2 now uses the tuned predictors too
  • Minor corrections to our preliminary numbers: On COMPAS, the TV cap is 0.27, not 0.28; I(A;X) is 0.058, not 0.059 nats; realized leakage is 34-49%, not 34-50%. These came from our verification runs (details in the replies below)
  • What held on the new datasets? With its 95% limit, the TV cap is never exceeded: 0 of 3,815 feature-set runs with the default predictors of Tbl3 (on Adult, COMPAS, ACS Income), and 0 of 9,275 with tuned predictors on all 7 datasets
  • What did not hold? We now state three dataset-based limitations, specifically: (i) on ACS Income, the EO error of v_EO,CMI on SV Ref is 23.9%, at the level of a random non-negative attribution (22-26%); (ii) on ACS Pub. Cov., errors are higher on SV Ref than on LOO Ref; and (iii) on Census-KDD + Heritage, realized gaps are small (the TV cap is 5-16x larger), and SP/EO errors on SV Ref (21-23%) are only modestly below random non-negative attributions (26.5-28.2%; Sec5.3 + AppJ)

If any part remains unclear, we would be glad to clarify it right away.

AuthorsOpenReview ↗

Rebuttal Reminder

Dear Reviewers,

The discussion period closes in about 12 hours; we would be grateful if you could check whether our responses and the revised PDF address your concerns. We did our best to address all comments; we reran and verified our experiments, clarified our claims and conclusions, and updated the draft with all promised modifications. We appreciate your time and engagement.

Sincerely, The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.