Abstract
Predictive models are being increasingly used to support consequential decision making at the individual level in contexts such as pretrial bail and loan approval. As a result, there is increasing social and legal pressure to provide explanations that help the affected individuals not only to understand why a prediction was output, but also how to act to obtain a desired outcome. To this end, several works have proposed optimization-based methods to generate nearest counterfactual explanations. However, these methods are often restricted to a particular subset of models (e.g., decision trees or linear models) and differentiable distance functions. In contrast, we build on standard theory and tools from formal verification and propose a novel algorithm that solves a sequence of satisfiability problems, where both the distance function (objective) and predictive model (constraints) are represented as logic formulae. As shown by our experiments on real-world data, our algorithm is: i) model-agnostic ({non-}linear, {non-}differentiable, {non-}convex); ii) data-type-agnostic (heterogeneous features); iii) distance-agnostic (l0, l1, l8, and combinations thereof); iv) able to generate plausible and diverse counterfactuals for any sample (i.e., 100% coverage); and v) at provably optimal distances.
Introduction
When an AI model makes a "consequential decision"—such as denying a loan, flagging a defendant for pretrial detention, or rejecting a job applicant—the affected person deserves to know why. More importantly, they need to know how to change the outcome. This is the domain of "counterfactual explanations." A counterfactual might suggest: "If your income were $5,000 higher and you had one fewer credit card, your loan would have been approved."
However, existing methods for finding these explanations suffer from several major flaws. Many are model-dependent, working only for specific architectures like linear regressions. Others are suboptimal, failing to find the closest possible change, or implausible, suggesting impossible changes like "be five years younger." Finally, most struggle with heterogeneous real-world data that mixes categorical, ordinal, and numerical features.
The MACE Framework
The authors introduce MACE (Model-Agnostic Counterfactual Explanations), which treats the machine learning model not as a black box, but as a program that can be translated into logic. MACE converts the predictive model (e.g., a Random Forest or a Neural Network) into a first-order logic formula. It does the same for the distance metric (how much change is required) and "plausibility" constraints (what is allowed to change).
Instead of using standard optimization techniques like gradient descent, MACE leverages Satisfiability Modulo Theories (SMT) solvers, powerful tools from the world of formal verification. The solver is tasked with finding an input $x$ that results in a desired decision while remaining within a distance $\delta$ of the original user. By performing a binary search on the distance threshold $\delta$, MACE converges on the provably nearest counterfactual explanation.
Key Insights and Results
By encoding constraints directly into the logic formula (e.g., $age_{new} \ge age_{old}$), MACE guarantees it will never return an impossible suggestion. Because almost any model can be represented as a series of logical operations, MACE handles non-differentiable models (like Decision Trees) and differentiable ones (Neural Networks) with the same machinery.
The researchers evaluated MACE on three popular datasets representing high-stakes decisions: Adult (Census Income), Credit (Default), and COMPAS (Recidivism). Key findings include:
- 100% Coverage: MACE's design ensures it always finds a counterfactual if one exists, unlike baselines that often fail for certain individuals.
- Significantly Closer Explanations: MACE found counterfactuals that were much "cheaper" for the user. On the Adult dataset, MACE's suggestions were 70.2% closer on average than the nearest competitor.
- Optimality Guarantees: MACE is the only approach that supports a wide range of models and distances while providing provably optimal results and plausibility.
Conclusion and Future Work
MACE brings mathematical rigor to Explainable AI (XAI) by treating explanation as a verification problem. While SMT solvers can be computationally intensive for very deep neural networks, MACE provides a robust foundation for generating actionable, realistic, and optimal recourse for individuals affected by automated decisions. Future work may involve leveraging specialized solvers for deep learning to improve scalability and incorporating causal relationships to better handle feature correlations.
Summary updated