When we ask an AI model to explain its behavior, we are typically looking for one of two things. We might want to know the sufficient reason for its decision: "What is the minimum set of features that guaranteed my loan approval?" Alternatively, we might want a contrastive reason: "What is the smallest change I could make to my profile to turn this rejection into an approval?"
In the field of formal Explainable AI (XAI), these two questions are known as abductive explanations (why the decision happened) and contrastive explanations (how the decision could change). Historically, these were treated as distinct computational problems. However, a powerful mathematical insight has unified them: abductive and contrastive explanations are dual to one another through the concept of a minimal hitting set.
This duality means that computing why a model made a decision is fundamentally the same task as finding out how to break that decision.
Two Sides of the Same Decision
To understand why this duality exists, let us look at a simple loan-approval model. Suppose an applicant is approved based on three features: High Income ($I$), Good Credit ($C$), and No Debt ($D$).
An abductive explanation is a minimal subset of the current features that is sufficient to retain the prediction. If the combination of High Income and Good Credit $\{I, C\}$ is an abductive explanation, it means that as long as these two conditions are met, the model will always approve the loan, regardless of the applicant's debt status.
A contrastive explanation is a minimal subset of features that, if changed, will flip the prediction. For instance, if changing Good Credit to Bad Credit $\{C\}$ flips the decision to a rejection, then $\{C\}$ is a contrastive explanation.
Now, consider the relationship between the two. If the feature set $\{I, C\}$ guarantees approval, then any action that successfully flips the model's decision to a rejection must break this guarantee. To break the guarantee, an adversarial change must alter at least one feature within $\{I, C\}$.
This is the core of hitting set duality. In combinatorial mathematics, a hitting set of a collection of sets is a set that contains at least one element from each set in that collection. Because every contrastive change must disrupt every sufficient guarantee, an abductive explanation must "hit" every possible contrastive explanation, and vice versa.
The Mathematical Foundation
This relationship is not merely an empirical observation; it is a provable logical property. As shown by Alexey Ignatiev et al., an abductive explanation is a minimal hitting set of all possible contrastive explanations for a given instance.
This formulation maps directly onto classical logic. As Chunxi Ji demonstrates, sufficient and necessary explanations are dual properties of a single underlying Boolean formula representing the decision logic. In logical terms, abductive explanations correspond to prime implicants (the minimal conditions that trigger a formula), while contrastive explanations correspond to prime implicates (the minimal clauses needed to falsify it). This representational strategy mirrors foundational work in modal logic by Meghyn Bienvenu, where negation duality allows algorithms that find consequences to be directly inverted for abductive reasoning.
The same duality applies to conflict resolution in constraint satisfaction. As explored by Éric Grégoire et al. and later extended to human-understandable constraint explanations by Emilio Gamba et al., the complements of maximal satisfiable subsets (MSSes) act as hitting sets for minimal unsatisfiable subformulas (MUSes). Whether explaining a neural network or a scheduling algorithm, the underlying math remains identical.
Flipping the Search Space
Recognizing this duality completely changes how we compute explanations. Proving that a set of features is an abductive explanation is computationally brutal: you must verify that for every possible value of the remaining features, the model's prediction never changes.
However, finding a contrastive explanation is much easier. It only requires finding a single counterexample—an adversarial perturbation that flips the output.
By leveraging hitting set duality, algorithms can use automated reasoners (like SAT or ILP solvers) as oracles to find these counterexamples, and then compute hitting sets over them to systematically construct formal explanations.
┌────────────────────────────────────────────────────────┐
│ Automated Reasoner │
└───────────────────────────┬────────────────────────────┘
│ Generates counterexamples
▼
┌────────────────────────────────────────────────────────┐
│ Contrastive Explanations (CXps) │
│ (Minimal feature tweaks that flip the prediction) │
└───────────────────────────┬────────────────────────────┘
│ Compute Minimal Hitting Set
▼
┌────────────────────────────────────────────────────────┐
│ Abductive Explanation (AXp) │
│ (Minimal feature set that guarantees the prediction) │
└────────────────────────────────────────────────────────┘
As Shahaf Bassan et al. demonstrate in reactive systems, this duality transforms the hard problem of searching for minimal sufficient feature sets into the more tractable task of finding counterexamples via a formal verifier. Similarly, Xuanxiang Huang et al. utilize a SAT solver to generate "seeds" that are iteratively refined into minimal abductive or contrastive explanations, providing a complete map of the decision boundary around an input.
Generalizing Across Models and Constraints
Because hitting set duality is a property of the decision logic itself rather than a specific architecture, it serves as a universal framework for formal XAI. Researchers have successfully adapted it to various domains:
- Model-Agnostic Frameworks: The authors of Efficient and Rigorous Model-Agnostic Explanations show that sample-based abductive and contrastive explanations maintain this exact hitting set relationship, allowing algorithms built for one explanation type to seamlessly generate the other.
- Specialized Classifiers: For structures like decision graphs, Xuanxiang Huang et al. leverage duality to achieve polynomial-time explanation enumeration. For monotonic classifiers, João Marques-Silva 0001 et al. exploit monotonicity alongside duality to bypass exponential complexity entirely.
- Continuous and Range-Based Spaces: Real-world data rarely relies on exact points. Yacine Izza et al. proved that hitting set duality persists even when features are represented as broad ranges or sets of values ("inflated explanations"). This allowed Yacine Izza et al. to compute the "most general" explanations for complex tree ensembles by maximizing valid feature intervals.
- Local and Approximate Search: When searching the entire input space is too costly, the duality remains valid within distance-restricted neighborhoods, as shown by Xuanxiang Huang et al.. For massive models where exact computation is #P-hard, Jinqiang Yu et al. demonstrate that targeting contrastive sets early in an anytime search yields highly accurate approximations of formal feature importance long before the search terminates.
Explanations as Adversarial Roadmaps
The duality between explanations and contrastive examples exposes a profound security tension in machine learning. A contrastive explanation is a minimal set of feature changes that alters a model's prediction. If you apply those exact changes to an input, you have successfully executed an adversarial attack.
This connection is made explicit by Alexey Ignatiev et al., who formalized the link between identifying influential features and identifying model vulnerabilities. When viewed through an optimization lens, counterfactual explanations and adversarial examples often converge to the exact same mathematical solutions. As Timo Freiesleben and Chirag Agarwal et al. argue, both tasks seek the minimal perturbation required to cross a decision boundary.
This convergence creates a fundamental paradox for trustworthy AI: the exact same mechanism used to provide a user with a transparent path to recourse (e.g., "how to get your loan approved tomorrow") simultaneously provides a malicious actor with a precise, minimal roadmap to exploit and manipulate the model.
Key Foundational Work
On Relating Explanations and Adversarial Examples (2019) — contributed 3 concept elements to this direction.
Prime Implicates and Prime Implicants in Modal Logic (2007) — contributed 1 concept elements to this direction.
Model-Based Diagnosis with Multiple Observations (2019) — contributed 1 concept elements to this direction.