Abstract
Transparency is a fundamental requirement for decision-making systems deployed in high-stakes real-world scenarios. Counterfactual explanations (CFEs) provide transparency by suggesting actionable changes to an input that would alter the system's output. However, these methods often exhibit significant instability: minor perturbations in input can lead to disproportionately large changes in the resulting explanation. This instability poses a threat to individual fairness, as nearly identical individuals may receive vastly different advice. This paper formally studies the robustness of CFEs, demonstrates the inherent "curse of dimensionality" that plagues standard methods, and proposes "plausible counterfactuals" as a robust alternative that aligns with the underlying data distribution.
Introduction
As AI systems increasingly handle critical decisions like loan approvals or medical diagnoses, the demand for interpretable feedback grows. Counterfactual Explanations (CFEs) are popular because they offer intuitive "what if" scenarios (e.g., "If your income were $5,000 higher, your loan would be approved").
Despite their utility, CFEs suffer from instability. If a negligible change to input data—such as a rounding error or sensor noise—results in a completely different explanation, the system lacks robustness. This is not merely a technical flaw; it is an issue of individual fairness. If two similar individuals receive divergent advice, the system fails to treat them equitably. This work seeks to quantify this instability and provide a framework for mitigation.
The Curse of Dimensionality
A core technical finding of this research is the relationship between data dimensionality and explanation stability. The authors mathematically prove that for linear classifiers, instability grows linearly with the number of features. In high-dimensional spaces, there are simply more "directions" for an explanation to shift, making standard "closest" counterfactuals inherently fragile.
As shown in the figure above, this linear growth in instability is not limited to linear models but extends to non-linear architectures like Decision Trees and Generalized Learning Vector Quantization (GLVQ). As the feature space expands from 8 to 128 dimensions, the distance between explanations for original and perturbed samples climbs steadily.
Methods: Closest vs. Plausible Counterfactuals
The authors define "local instability" as the expected distance between the explanation for an original data point and the explanation for a slightly perturbed version of that point. They compare two primary approaches:
- Closest Counterfactuals: The standard approach, which identifies the absolute nearest point across the decision boundary. This method often selects "outlier" points that do not resemble real-world data, making them highly sensitive to noise.
- Plausible Counterfactuals: A constrained approach requiring the explanation to lie within a high-density region of the data manifold. By ensuring the counterfactual looks like a realistic example (using density estimators like Gaussian Mixture Models), the optimization is regularized against picking unstable outliers.
Empirical Results
The researchers evaluated these approaches across multiple datasets, including medical diagnostics (Breast Cancer Wisconsin), chemical analysis (Wine), and image-based tasks (MNIST). Across all models—Softmax Regression, GLVQ, and Decision Trees—plausible counterfactuals proved significantly more robust.
As illustrated in the feature masking experiments, even when up to 50% of features are masked, plausible counterfactuals maintain a much lower and more stable distance between explanations compared to the "closest" baseline. For instance, in the Wine dataset using Softmax regression, median instability dropped from 10.16 for closest CFEs to just 1.87 for plausible CFEs.
Conclusion
Robustness and individual fairness are inextricably linked in the context of algorithmic explanations. By forcing counterfactuals to be "plausible," we can mitigate the instability caused by the curse of dimensionality. This ensures that similar individuals receive similar, actionable advice, thereby improving the reliability and fairness of automated decision-making systems. Future work will explore these dynamics in high-capacity models like Deep Neural Networks and investigate how human users psychologically perceive the fairness of these robust explanations.
Summary updated