Technical Summary: RECAST

Problem Statement

The paper addresses the challenge of model reconstruction (creating a surrogate model to mimic a black-box classifier) under severely limited data access and restricted query budgets. This scenario is common in auditing Machine Learning-as-a-Service (MLaaS) platforms, where third parties cannot interactively query the target model during reconstruction and must rely on a fixed, offline dataset.

Specifically, the authors focus on settings where only one-sided counterfactual explanations (CFs) are available. In many real-world applications (e.g., loan rejections), users receive explanations on how to change a negative outcome to a positive one, but not vice versa. Existing CF-based reconstruction methods face three critical limitations in this regime:

1. Decision Boundary Shifts: Treating CFs as hard-labeled samples of the target class causes the surrogate to become overconfident in regions near the boundary, incorrectly shifting the decision surface (as illustrated in Figure 1).
2. Overfitting: Neural network-based approaches struggle with overfitting when training data is scarce and query budgets are tight.
3. Non-Identifiability: Under one-sided CF access and limited queries, the true decision boundary is statistically non-identifiable; multiple distinct classifiers can produce identical input-output behaviors. Therefore, attempting to recover a unique geometric boundary is ill-posed.

Methodology: RECAST

The authors propose RECAST (REconstruction via Counterfactual-Aware waSserstein opTimization), a behavior-centric approach that reconstructs class-level distributions rather than explicit decision boundaries.

1. CF-Consistent Uncertainty Sets

Instead of assuming CFs lie exactly on the decision boundary, RECAST treats them as soft, cross-class constraints. It defines a CF-consistent feasible set $\mathcal{C}_c$ for each class $c \in \{0, 1\}$. This set is the intersection of two Wasserstein balls:

• One centered at the empirical class-conditional distribution $P_c$.
• One centered at the one-sided counterfactual distribution $P_{cf}$.

This creates a "lens-shaped" ambiguity set in Wasserstein space, encoding both sampling uncertainty and the geometric constraints imposed by the counterfactuals.

2. Robust Wasserstein Barycenters

To find a stable representative for each class within this uncertainty set, RECAST computes Wasserstein barycenters. Theorem 3.2 establishes that minimizing the worst-case distributional reconstruction risk over the feasible set is equivalent to finding a prototype $Q_c^*$ that minimizes a weighted sum of squared Wasserstein distances:
$$Q_c^* = \arg\min_{\mu} \left( (1-\lambda_c)W_2^2(\mu, P_c) + \lambda_c W_2^2(\mu, P_{cf}) \right)$$
Here, $Q_c^*$ is the 2-Wasserstein barycenter of the original class data and the counterfactual data. The mixing weight $\lambda_c$ is derived canonically from the relative geometry of the distributions ($P_c$, $P_{cf}$, and the opposite class $P_{1-c}$), ensuring the method does not require explicit tuning of uncertainty radii.

3. Barycentric Prototype Classifier

The final surrogate model $\hat{m}$ classifies an input $x$ by comparing its Wasserstein distance to the learned class prototypes:
$$\hat{m}(x) := \arg\min_{c \in \{0, 1\}} W_2(\delta_x, Q_c^*)$$
where $\delta_x$ is the Dirac measure at $x$. This classifier is CF-identifiable, meaning its decision behavior is invariant to the specific realizations of the underlying distributions within the uncertainty set.

4. Fairness Diagnostics

The framework adapts Threshold-Invariant Demographic Parity (TIDP) and Threshold-Invariant Equalized Odds (TIEO) to the Wasserstein geometry. By comparing the distributions of the Wasserstein-based scores across sensitive groups, the method provides a systematic diagnostic for fairness disparities that persists across all decision thresholds, independent of a specific cutoff.

Key Contributions

• RECAST Framework: A novel solution for behavioral model reconstruction using counterfactual-aware Wasserstein barycentric prototypes, specifically designed for offline, one-sided CF access.
• Theoretical Grounding: Proof that minimizing robust risk bounds under CF-consistent uncertainty leads to Wasserstein barycenters, providing a stable geometric representation of class distributions even when the boundary is non-identifiable.
• Fairness Auditing Tool: A geometry-based diagnostic that quantifies distributional disparities across sensitive groups relative to the reconstructed decision geometry.
• Empirical Validation: Extensive experiments on four real-world datasets (Adult, COMPAS, HELOC, California Housing) demonstrating that RECAST achieves higher fidelity and query efficiency than baselines (SAMPLES, CCA, TRA), particularly in low-query regimes and under noisy conditions.

Experimental Results

• Fidelity: RECAST consistently outperforms baselines in fidelity (agreement with the target model's predictions) across various target models (MLP, Logistic Regression, Decision Trees) and datasets. It shows a distinct advantage in low-query regimes (e.g., 100 samples), where other methods suffer from overfitting or boundary shifts.
• Robustness: The method demonstrates superior stability under additive noise and distribution shifts (e.g., cross-domain evaluation from California to Michigan data). While baselines degrade significantly near the decision threshold, RECAST degrades gracefully.
• CF Generators: RECAST maintains high fidelity regardless of the counterfactual generation method (MCCF, DiCE, ROAR, etc.), whereas baselines are highly sensitive to the specific properties and "overshooting" behavior of the CFs.
• Fairness: The proposed diagnostics show that RECAST preserves the target model's fairness characteristics more faithfully than competing methods, even under perturbation.

Significance and Claims

The paper positions RECAST as a practical tool for auditing opaque decision systems in high-stakes domains (finance, criminal justice, healthcare) where data access is restricted and query budgets are limited.

• Behavioral Focus: The authors emphasize that under one-sided CF access, recovering a unique ground-truth decision boundary is impossible. Instead, RECAST focuses on behavioral equivalence, reconstructing the input-output relationship that is statistically identifiable.
• Regulatory Relevance: The work supports the goals of the EU AI Act and similar regulations by enabling independent investigation of model behavior, transparency, and fairness without requiring access to the model's internal parameters or training data.
• Limitations: The authors modestly note that the current approach is limited to binary classification and relies on the assumption of passive observation (no strategic adversarial interaction with the platform). They also acknowledge that while Wasserstein distance is computationally intensive, it remains tractable in the low-data regimes for which the method is designed.

In summary, RECAST offers a mathematically rigorous and empirically validated approach to reconstructing black-box models when only limited, one-sided counterfactual feedback is available, prioritizing stability and behavioral fidelity over the impossible task of boundary recovery.