When a machine learning model denies a loan application or flags a medical diagnosis, users do not just want to know why the decision was made—they want to know how to change the outcome. This is the purpose of counterfactual explanations, which suggest the minimal modifications required to flip a model's prediction.
Intuitively, the ideal explanation is sparse: it should alter only one or two features so that it remains digestible and actionable for a human. However, a fundamental tension exists in Explainable AI (XAI): forcing an explanation to be sparse often makes it completely unrealistic or physically impossible. This conflict between sparsity and plausibility (or data realism) represents a core challenge across modern explanation frameworks.
The Core Intuition: Why Simple Explanations Fail
To understand why this trade-off occurs, imagine a model that predicts creditworthiness based on income, savings, and age. If a sparse counterfactual algorithm tells an applicant, "Your loan would be approved if your income were $50,000 higher," it treats income as an independent variable.
In reality, features are highly correlated. A person with a significantly higher income would likely have different savings patterns or employment histories. By changing only a single feature, the sparse explanation generates a "Frankenstein" data point that lies far outside the true data distribution. As Mishra et al. observe, enforcing extreme sparsity to align strictly with model logic can result in suggestions that are practically impossible for an individual to implement. To remain plausible, an explanation must often modify a larger number of features simultaneously to maintain these underlying real-world correlations (Dandl et al.).
The Geometry of the Conflict: Sparsity vs. Distance
Mathematically, this tension can be viewed as a geometric conflict between different norms in the feature space. Minimizing the number of changed features (the $L_0$ norm) forces the optimization to move strictly along coordinate axes.
As Artelt et al. explain, reducing the number of features modified in an explanation forces the remaining feature values to deviate significantly from their original baselines to successfully cross the model's decision boundary. This creates a direct trade-off between sparsity and closeness (or proximity) to the original input.
Implausible Sparse Counterfactual (Large jump in 1 feature)
▲
│
│ ╔═════════════════════════╗
│ ║ Decision Boundary ║
│ ╚═════════════════════════╝
│
│ Plausible Dense Counterfactual
│ / (Small changes in multiple features)
│ ▄▀
│ ▄▀
│▄▀
Factual Point ────────■────────────────────────►
Through a geometric analysis of ReLU-based neural networks, Villani et al. demonstrate that restricting a counterfactual to a small subset of features inherently results in a larger total Euclidean distance from the decision boundary compared to non-sparse alternatives. If you are only allowed to turn a few knobs, you must crank them to extreme, unnatural values. Conversely, You et al. provide a theoretical counterpoint, showing that under joint-distribution-informed refinements, sparse explanations can theoretically maintain proximity without unnecessary "bloat," though navigating this boundary in practice remains difficult.
This trade-off is not unique to classification. Artelt notes a similar tension when explaining complex dimensionality reduction projections, where minimizing the modified features degrades the target accuracy of the explanation in the low-dimensional visualization space. Similarly, Aryal documents this technical challenge in semi-factual ("even if") explanations, where maximizing the distance to demonstrate a decision's robustness directly conflicts with maintaining a human-interpretable number of feature changes. Even in early feature-selection contexts, Marchand et al. identified a parallel tension between model simplicity (sparsity) and the margin of error required to remain robust against noise.
The Data Manifold Dilemma
When optimization algorithms ignore the underlying data distribution, they tend to exploit the model's blind spots, generating adversarial noise rather than actionable insights. Sadiku et al. emphasize that optimizing exclusively for minimal feature changes frequently yields physically impossible suggestions that lack real-world utility.
To prevent this, explanations must be guided along the data manifold—the lower-dimensional surface where realistic data points actually reside. However, traveling along the manifold inherently requires coordinated changes across many features. This leaves practitioners with a stark choice:
- High Sparsity / Low Plausibility: Simple, human-readable explanations that describe impossible scenarios.
- Low Sparsity / High Plausibility: Realistic, achievable scenarios that are too complex for a human to easily interpret.
Algorithmic Strategies for Navigating the Frontier
Because a single "perfect" explanation rarely satisfies both constraints, the research community has developed several distinct paradigms to manage this trade-off.
Multi-Objective Optimization
Rather than collapsing competing goals into a single weighted objective function, Dandl et al. treat counterfactual generation as an explicit multi-objective optimization problem. This approach surfaces a diverse "Pareto front" of explanations, allowing end-users to visualize the trade-off directly and select the path that best fits their real-world constraints.
Latent Space Transitions
To guarantee plausibility by design, several frameworks route the explanation generation through a learned, low-dimensional latent space using Variational Autoencoders (VAEs). By performing linear interpolations in a "cleaned" latent space, the resulting explanations are guaranteed to be highly realistic and valid (Broelemann et al.; Nagesh et al.).
However, this design choice comes with a catch: a single step in the latent space ripples outward, causing small changes across almost all features in the input space, which destroys individual feature sparsity. To mitigate this, Caccia et al. introduce frameworks that navigate disentangled latent spaces to intentionally ignore dominant, trivial features, forcing the model to find non-obvious yet sparse and valid pathways.
Density Estimation and Proximal Gradients
Rather than mapping to a latent space, some methods use density estimators directly in the input space. For example, Dandl et al. leverage Adversarial Random Forests to compute data density, explicitly penalizing counterfactuals that wander into low-density regions. To handle the mathematical friction between discrete sparsity constraints and continuous density functions, Sadiku et al. employ Accelerated Proximal Gradient methods to smoothly balance validity, sparsity, and realism.
Path-Based and Constrained Search
Instead of presenting a single, isolated counterfactual point, Luss proposes tracing a stable path of feature subsets from the original input down to a minimally sufficient set, preventing the sharp drop in fidelity that often accompanies sudden sparsity constraints. However, restricting explanations to very few features severely constrains the mathematical search space—a limitation that Qian et al. address by balancing sparsity against the diversity of alternative paths using Boolean satisfiability solvers.
Beyond Counterfactuals: Faithfulness in Feature Attributions
The tension between sparsity and plausibility extends beyond "what-if" scenarios into feature attribution methods (such as saliency heatmaps and graph explanations). Here, the trade-off manifests as a conflict between human interpretability and mathematical faithfulness.
Humans naturally prefer highly localized, sparse heatmaps that highlight a single object. However, Wolf et al. demonstrate that enforcing extreme visual sparsity in convolutional neural network explanations often omits broader, complex regions that the model actually relies on for its decision-making. This creates a severe conflict: sparse heatmaps are visually appealing but mathematically unfaithful to the model's internal logic.
To bridge this gap, Walker introduces a metric-driven attribution framework for Vision Transformers that allows practitioners to explicitly tune the balance between sparse, minimal feature sets and dense, object-level visualizations. A similar phenomenon occurs in Reinforcement Learning agents, where Zuo et al. show that balancing sparsity with robustness to input noise is essential for generating explanations that are concise enough for human interpretation yet stable enough for deployment.
Strict Sparsity Regularization ──► Omit structural context ──► Low Faithfulness
Broad Information Retention ──► Overwhelm human user ──► Low Interpretability
This same challenge appears when explaining Graph Neural Networks (GNNs). When isolating an explanatory subgraph, Chen et al. show that overly aggressive regularization for sparsity can easily omit critical structural features necessary to accurately represent the model's decision-making process. As Wang et al. observe, smaller subgraphs often fail to capture the full reasoning of the model, making the automatic determination of an optimal explanation size an ongoing challenge.
Furthermore, Zhang et al. note that evaluating explanation quality requires balancing the drop in model performance when features are removed against the conciseness of the highlighted set. When the underlying data itself is highly sparse, traditional masking techniques often fail entirely to reach a balanced level of complexity, leading Mazur et al. to implement dense proxy data branches to restore high-fidelity explanations. On a global scale, standard sparsity constraints also struggle to maintain a balance between individual sample conciseness and global explanation diversity across an entire dataset, requiring specialized regularization frameworks to prevent models from over-relying on a narrow dictionary of concepts (Parekh et al.).
Ultimately, the choice of where to sit on the sparsity-plausibility curve depends on the audience. A developer debugging a model may require a dense, highly faithful attribution map, while an end-user seeking an actionable path forward requires a sparse, highly plausible counterfactual. Recognizing and mathematically managing this trade-off remains central to designing effective explanation systems.
Key Foundational Work
Multi-Objective Counterfactual Explanations (2020) — contributed 2 concept elements to this direction.
Efficient computation of contrastive explanations (2020) — contributed 1 concept elements to this direction.
Locally and globally explainable time series tweaking (2020) — contributed 1 concept elements to this direction.