On Counterfactual Explanations under Predictive Multiplicity

Martin Pawelczyk, Klaus Broelemann, Gjergji Kasneci

Abstract

Counterfactual explanations are usually obtained by identifying the smallest change made to an input to change a prediction made by a fixed model (hereafter called sparse methods). Recent work, however, has highlighted that these methods are often fragile under predictive multiplicity—the phenomenon where multiple models achieve similar accuracy but make different individual predictions. This paper explores the hidden risks of sparse recourse and demonstrates that "data support" methods, which suggest changes moving an individual toward the real-world data manifold, are significantly more robust to model updates and swaps.

The Challenge of Predictive Multiplicity

In high-stakes decision-making, such as loan approvals or credit scoring, a counterfactual explanation serves as a recommendation for action (e.g., "If your debt were $500 lower, your loan would be approved"). However, predictive multiplicity poses a significant threat to the reliability of these recommendations. For any given dataset, there are often multiple models ($f, g, h...$) that perform equally well on average but have slightly different decision boundaries.

If a bank switches from model $f$ to model $g$, a recommendation based on $f$ might no longer be sufficient for $g$. This failure is termed "negative surprise." Most existing research focuses on finding the sparse counterfactual—the absolute minimum change required to cross a decision boundary. This paper argues that these minimal recommendations are inherently unreliable because they land on the "edge" of the boundary, where even a minor model shift can invalidate the recourse.

Figure 1: (a) Sparse vs. Support counterfactual recommendations. (b) The cost of negative surprise. Sparse methods often land on the decision boundary, making them vulnerable to model shifts.

Sparse vs. Data-Support Approaches

The authors categorize counterfactual methods into two distinct paradigms:

  1. Sparse Approaches: These minimize a distance metric (like the $\ell_1$ or $\ell_2$ norm) to find the closest point across the decision boundary. Methods like Growing Spheres (GS) and Actionable Recourse (AR) fall into this category.
  2. Data Support Approaches: These ensure the recommendation sits in a region populated by real-world data (the data manifold). The authors propose a VAE-based method (OURS) that searches for counterfactuals in a latent space to ensure they align with the distribution of the target class.

Theoretically, the authors derive a general upper bound for the costs of counterfactuals under multiplicity. They introduce the Oracle cost inequality, proving that while data-supported recommendations are more "expensive" (requiring more effort from the user), they are at most twice as costly as sparse ones under certain conditions, while offering significantly higher reliability.

Empirical Evaluation and Transferability

The study utilizes two popular financial recourse datasets: HELOC (Home Equity Line of Credit) and "Give Me Some Credit". These datasets represent scenarios where the stability of a recommendation is legally and ethically vital. The primary metric for evaluation is transferability: the probability that a counterfactual generated for model $f$ remains valid for a different model $g$.

Figure 3: Transferability results for HELOC and 'Give Me Some Credit' datasets. The data-support method (ours) consistently maintains higher transferability than sparse methods (gs, ar) across different model transitions.

Key Results and Discussion

The empirical results confirm that sparse methods are highly sensitive to model changes. As shown in the transferability plots, the data-support method (OURS) consistently outperforms sparse methods (GS and AR) across various model architectures, including transitions between Linear and Random Forest models.

While data-supported methods require a higher "upfront cost" from the user—measured by the Total Percentile Shift in features—this cost acts as "insurance" against future model updates. Qualitatively, these methods also produce more "semantically sane" recommendations, moving users toward the actual distribution of successful applicants rather than just identifying mathematical loopholes in a specific model's weights.

Conclusion

This research highlights a fundamental trade-off between the cost of an action and its robustness to model changes. While sparse methods are computationally and effort-wise cheaper, they are fragile under predictive multiplicity. Data-support methods offer a path toward more reliable algorithmic recourse by targeting the center of the positive class distribution. Future work remains to bridge the gap between these extremes, potentially by integrating causal graphs to ensure recommendations are not only data-supported but also physically and logically actionable.

Summary updated

Abstract

Counterfactual explanations are usually obtainedby identifying the smallest change made to an input to change a prediction made by a fixed model (hereafter called sparse methods). Recent work, howe...
BibTeX
@inproceedings{pawelczyk2020counterfactual,
  author = {Martin Pawelczyk and Klaus Broelemann and Gjergji Kasneci},
  title = {{On Counterfactual Explanations under Predictive Multiplicity}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=BLZkFcf6Lj},
}
Figure