When a machine learning model denies a loan application, flags a transaction as fraudulent, or categorizes a patient as high-risk, the natural follow-up question from the affected individual is: What can I do to change this outcome?
To answer this, explainable AI frameworks often generate counterfactual explanations—synthetic scenarios that describe the minimal changes required to flip a model's prediction from negative to positive. However, standard optimization algorithms operate in an abstract mathematical space completely detached from physical and social reality. This disconnect introduces a critical failure mode: recommending changes to features that are fundamentally impossible to alter.
The Distance Paradox
Mathematically, generating a counterfactual explanation is typically framed as a closest-vector problem. Given an individual's original feature vector $x$, an algorithm searches for a new vector $x'$ across the model's decision boundary that minimizes a distance metric, such as Euclidean distance ($L_2$ norm) or Manhattan distance ($L_1$ norm).
As Fabrizio Silvestri et al. observe in Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking, an unconstrained optimizer treats every dimension of a feature space as equally fluid. To the math, decreasing a person's age by five years or changing their place of birth is just as valid as increasing their savings account balance.
This creates a "distance paradox": the mathematically closest point across a decision boundary often requires actions that violate the laws of physics or biology. As Mark T. Keane et al. highlight in If Only We Had Better Counterfactual Explanations: Five Key Deficits to Rectify in the Evaluation of Counterfactual XAI Techniques, failing to ground these algorithms in real-world constraints renders automated guidance practically useless for human decision-making.
Categorizing the Feature Space
To resolve this paradox, the optimization objective must be constrained by a taxonomy of feature mutability. As Michael T. Lash et al. outline in A budget-constrained inverse classification framework for smooth classifiers, features within consequential decision-making models generally fall into three categories:
- Immutable Features: Inherent or historical characteristics that cannot be altered under any circumstances, such as age, ethnicity, genetic profiles, or fixed historical metadata (see also Generalized Inverse Classification).
- Directly Actionable Features: Variables that an individual can consciously alter through effort or financial expenditure, such as a bank balance, education level, or the specific wording of a product description (e.g., RecRec: Algorithmic Recourse for Recommender Systems).
- Indirectly Affected Features: Downstream variables that change as a consequence of direct actions, such as a credit score or overall health risk metrics.
By formalizing these distinctions, recourse algorithms can freeze immutable dimensions during the optimization process, restricting the search space entirely to actionable pathways.
Hard Constraints and Causal Interventions
There are two primary methodologies for enforcing these mutability boundaries during counterfactual generation: hard optimization constraints and causal interventions.
Hard Optimization Constraints
The most direct approach is to embed mutability constraints into the search algorithm itself. In frameworks like MACE, developed by Amir-Hossein Karimi et al. in Model-Agnostic Counterfactual Explanations for Consequential Decisions, formal verification tools like Satisfiability Modulo Theories (SMT) solvers are used to find explanations. If a feature is flagged as immutable, the solver treats its value as a hard constant, forcing the perturbation vector $\delta$ to be exactly zero for that dimension.
Causal Interventions
Simply freezing features is often insufficient because real-world variables are causally linked. In Algorithmic Recourse: from Counterfactual Explanations to Interventions, Amir-Hossein Karimi et al. argue that recourse must be reframed as a structural causal intervention rather than a coordinate shift. For example, if a model requires a higher income to approve a loan, a causal framework recognizes that income cannot be tweaked directly; it must be altered by intervening on its causes, such as education or hours worked.
Crucially, immutable features often act as exogenous confounders in these causal graphs. As Jingquan Yan et al. demonstrate in Self-Interpretable Time Series Prediction with Counterfactual Explanations, failing to condition on immutable exogenous variables (like a patient's biological sex) leads to causal simulations that generate physically impossible counterfactual paths.
Data-Driven Feasibility Paths
Rather than manually mapping out complex causal graphs or hard-coding constraints, some modern frameworks infer mutability directly from empirical data distributions.
The FACE framework, introduced by Rafael Poyiadzi et al. in FACE: Feasible and Actionable Counterfactual Explanations, achieves this by constructing a density-weighted graph over the training data. Instead of allowing an individual to "teleport" to an arbitrary point across the decision boundary, FACE uncovers a continuous path of small, feasible transitions between actual observed data points. Because the training data inherently reflects real-world limitations, the resulting path naturally respects mutability constraints.
Unconstrained Search: [Current State] -----------------------------> [Teleported Counterfactual]
(Suggests: Decrease Age)
Graph-Based Path: [Current State] -> [Data Point A] -> [Data Point B] -> [Valid Recourse]
(Respects: Real Transitions)
Similarly, Alexander Asemota et al. in Using Longitudinal Data for Plausible Counterfactual Explanations leverage longitudinal datasets to observe how individuals actually evolve over time. This data-driven approach bypasses the need for manual domain engineering, as the historical records implicitly encode the physical impossibility of reversing time or altering fixed demographic attributes.
When generative architectures are used to scale recourse generation, these constraints must be explicitly integrated into the model's steering mechanism. For instance, Emmanouil Panagiotou utilizes a transformer-based variational autoencoder in TABCF: Counterfactual Explanations for Tabular Data Using a Transformer-Based VAE to capture realistic tabular structures, while Nishtha Madaan et al. introduce iterative steering mechanisms in Navigating the Structured What-If Spaces: Counterfactual Generation via Structured Diffusion to ensure sensitive demographic attributes are strictly preserved during the generation process.
Recourse-Aware Model Training
While most algorithmic recourse research focuses on post-hoc explanations for an existing model, a parallel direction argues that the predictive models themselves must be trained to accommodate recourse constraints.
If a classifier relies too heavily on immutable features to make its predictions, it creates confined regions within the feature space. As Connor Lawless et al. demonstrate in Understanding Fixed Predictions via Confined Regions, these are zones where an individual's negative prediction is completely locked in. No matter what actionable steps the user takes, the model's mathematical reliance on their immutable traits prevents them from ever crossing the decision boundary. This dynamic can trap specific sub-populations in persistent feedback loops of rejection, a phenomenon formalized in Algorithmic Censoring in Dynamic Learning Systems.
To prevent this, authors have proposed integrating actionability constraints directly into the model's loss function. In On the Adversarial Robustness of Causal Algorithmic Recourse, Ricardo Dominguez-Olmedo et al. introduce a training regularizer that explicitly penalizes a model's reliance on immutable or protected features. By forcing the decision boundary to align exclusively with dimensions that users can realistically control, the model guarantees that recourse remains a practical possibility rather than a mathematical illusion.
Key Foundational Work
A budget-constrained inverse classification framework for smooth classifiers (2016) — contributed 2 concept elements to this direction.
Generalized Inverse Classification (2016) — contributed 1 concept elements to this direction.
Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking (2017) — contributed 1 concept elements to this direction.