Imagine you apply for a loan and get rejected by an automated machine learning model. Seeking recourse, you ask for an explanation: "What is the smallest change I could make to get approved?" The model responds: "Decrease your age by five years, change your country of origin, and set your salary to \$200,000 while maintaining your current one year of work experience."
Mathematically, this recommendation is flawless. It identifies the absolute closest point in the feature space that crosses the model's decision boundary. Practically, it is completely useless. This disconnect is known as the actionability gap Explainable Machine Learning in Deployment. As Umang Bhatt et al. observe, while counterfactual explanations are theoretically ideal for providing algorithmic recourse, they frequently fail in deployment because they treat human actions as unconstrained geometric coordinates.
To bridge this gap, a major research direction has emerged: feasibility-constrained counterfactual generation. Instead of treating counterfactual search as a simple distance minimization problem, this paradigm embeds physical, logical, and statistical constraints directly into the optimization process.
The Distance Paradox and Adversarial Recourse
Why do standard counterfactual algorithms produce such unrealistic recommendations? The culprit lies in the traditional objective function. Standard methods solve for a counterfactual instance $x'$ by minimizing a distance metric $d(x, x')$ (such as the $L_1$ or $L_2$ norm) subject to the constraint that the model's prediction $f(x')$ matches a target outcome $y^*$.
By optimizing only for geometric proximity, the algorithm inadvertently exploits the model's blind spots. It acts exactly like an adversarial attack, pushing the counterfactual into low-density regions of the feature space where the model has never seen real data Convex Density Constraints for Computing Plausible Counterfactual Explanations. In these unpopulated regions, the model's decision boundaries are highly volatile and arbitrary, leading to nonsensical suggestions.
To prevent this, researchers divide feasibility constraints into two main categories: hard domain constraints (what is logically or physically possible) and soft density constraints (what is statistically plausible).
Hard Constraints: Enforcing Domain Laws and Immutability
The most direct way to ensure actionability is to explicitly restrict which features can change and how they can evolve. Fabrizio Silvestri et al. formalized this by partitioning features into static (immutable) and actionable variables Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking. Features like birth year, race, or historical data are locked during optimization, preventing the algorithm from suggesting impossible retroactions.
However, actionability is rarely binary. Features often possess directional or relational dependencies. For instance, a person's education level or age can only increase, never decrease. Miguel Á. Carreira-Perpiñán demonstrated that these directional requirements (monotonicity constraints) can be integrated directly into the local optimization steps of tree models, ensuring that the generated paths respect the arrow of time Counterfactual Explanations for Oblique Decision Trees: Exact, Efficient Algorithms.
In specialized domains, these hard constraints represent strict physical laws:
- Engineering and Radar Planning: Parameters are bound by hardware limitations and physical coverage laws; a counterfactual cannot suggest a hardware configuration that violates energy conservation Counterfactual Explanations for the Set Cover Problem, a Radar use case.
- Molecular Chemistry: When explaining Graph Neural Networks predicting molecular properties, structural modifications must obey valency and connectivity rules to avoid generating chemically impossible or unstable molecules Explaining Graph Neural Networks with Large Language Models: A Counterfactual Perspective on Molecule Graphs.
Soft Constraints: Anchoring Explanations to the Data Manifold
Hard constraints prevent obvious absurdities, but they cannot prevent statistically improbable combinations. A counterfactual might suggest a salary of \$200,000 for someone with one year of work experience—individually valid feature values, but collectively highly unrealistic.
To solve this, researchers introduce density constraints that force counterfactuals to reside within high-probability regions of the true data distribution. This ensures that the suggested changes align with real-world correlations.
Unconstrained Counterfactual (Adversarial / Out-of-Distribution)
x' (Nonsensical combination)
/
/ <- Minimizes pure geometric distance
/
x (Original Point) ───> x'' (Feasible Counterfactual)
▲
└─ Forced onto the Data Manifold (High Density)
Several distinct mechanisms are used to mathematically enforce density during optimization:
1. Generative and Mixture Models
André Artelt and Barbara Hammer integrated Gaussian Mixture Models (GMMs) directly into the optimization objective, penalizing counterfactuals that land in low-density zones Efficient computation of contrastive explanations. To scale this to complex tabular data, Tri Dung Duong and Qian Li leveraged Normalizing Flows to provide exact probability density estimation, ensuring synthetic points are highly representative of real-world observations CeFlow: A Robust and Efficient Counterfactual Explanation Framework for Tabular Data using Normalizing Flows.
2. Tree-Based Density Proxies
For tree ensembles, Axel Parmentier embedded Isolation Forests directly into the optimization constraints Optimal Counterfactual Explanations in Tree Ensembles. Because Isolation Forests isolate anomalies, forcing the counterfactual to pass the forest's threshold guarantees it behaves like a normal data point. Similarly, Kentaro Kanamori et al. utilized Local Outlier Factors (LOF) to penalize outlier states DACE: Distribution-Aware Counterfactual Explanation by Mixed-Integer Linear Optimization.
3. Predictive Uncertainty
Instead of modeling density explicitly, Aman Bilkhoo et al. used Conformal Prediction to avoid regions of high predictive uncertainty CONFEX: Uncertainty-Aware Counterfactual Explanations with Conformal Guarantees. If the underlying model has high uncertainty in a specific region, the counterfactual is barred from entering it, ensuring the recourse path is reliable and backed by training data support.
Continuous Paths vs. Static Points
Even if a counterfactual point is plausible, the transition from the original state to the target state might be impossible. Real life happens sequentially, not in instantaneous jumps.
To address this, frameworks like FACE, introduced by Rafael Poyiadzi et al., construct density-weighted feasibility graphs over the training data FACE: Feasible and Actionable Counterfactual Explanations. Instead of jumping across the decision boundary, the algorithm finds the shortest path connecting the user to the target outcome through existing data points. The user is given a step-by-step roadmap where every intermediate state is known to be feasible.
This graph-based approach has also been extended to group-level auditing by Christos Fragkathoulas et al. to quantify the varying "burden" different demographic groups face when attempting recourse FGCE: Feasible Group Counterfactual Explanations for Auditing Fairness.
Taking this a step further, Alexander Asemota and Giles Hooker proposed using longitudinal data—tracking how individuals actually evolve over time—to ground recourse recommendations in historical trajectories rather than static spatial proximity Using Longitudinal Data for Plausible Counterfactual Explanations.
The Computational Landscape of Realism
Adding these constraints comes at a steep price. Unconstrained counterfactual search is already difficult, but adding non-linear density constraints or combinatorial domain rules makes the problem significantly harder.
André Artelt and Martin Olsen proved that computing and even approximating exact counterfactuals under real-world feasibility constraints is NP-hard for most common machine learning models, including ReLU networks and additive trees On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI.
To bypass this intractability, the field relies on specialized optimization frameworks. Researchers frequently reframe the problem using Mixed-Integer Linear Programming (MILP) DACE: Distribution-Aware Counterfactual Explanation by Mixed-Integer Linear Optimization or convex relaxations of density estimators Convex Density Constraints for Computing Plausible Counterfactual Explanations to find valid, sparse, and highly plausible recourses in practical timeframes. By trading off pure geometric minimality for statistical and logical constraints, these methods ensure that algorithmic recourse is a practical reality rather than a mathematical abstraction.
Key Foundational Work
Explainable Time Series Tweaking via Irreversible and Reversible Temporal Transformations (2018) — contributed 2 concept elements to this direction.
Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking (2017) — contributed 1 concept elements to this direction.