💻 computer science

Realistic Counterfactual Explanations via Denial Constraints

This paper proposes a novel approach to generating realistic counterfactual explanations in Explainable AI by integrating denial constraints from relational databases to ensure generated instances adhere to data validity rules, thereby improving practical applicability with minimal compromise to distance and diversity metrics.

Original authors: Avia Asael, Nave Frost, Amir Gilad, Daniel Deutch

Published 2026-08-28✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Avia Asael, Nave Frost, Amir Gilad, Daniel Deutch

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, machines often make decisions that affect our lives, from approving loans to diagnosing illnesses. When these systems say "no," it is helpful to know why. One popular way to explain a decision is to imagine a slightly different version of the situation that would have led to a "yes." If a loan application is rejected, a helpful explanation might suggest that earning a little more money or having a slightly higher credit score would have changed the outcome. These imagined alternatives are called counterfactuals. They act as a spotlight, showing exactly which features of a person or object mattered most to the machine's judgment. However, for these explanations to be truly useful, they must make sense in the real world. An explanation that suggests a tiny apartment in a crowded city could suddenly have ten bedrooms is mathematically possible but physically impossible. If the suggested changes are unrealistic, the explanation fails to help the person understand their situation or fix it.

Researchers at Tel Aviv University, eBay, and the Hebrew University of Jerusalem have tackled this problem of unrealistic suggestions. They found that the most advanced tools currently used to generate these explanations often produce results that violate basic rules of reality. For instance, a tool might suggest that a house in a specific neighborhood has a certain number of bathrooms that simply do not exist in that area, or that a person's age and education level contradict known facts about how people live. To fix this, the team combined the methods used to explain AI with techniques from database management, the field that ensures data in computers remains consistent and accurate. They introduced a system that checks every suggested change against a set of logical rules derived from real data. These rules, known as denial constraints, act like a filter, ensuring that any new scenario proposed as an explanation fits within the boundaries of what is actually possible.

The researchers tested their new approach on four different datasets, including information about New York real estate, tax records, and demographic data. They compared their method against the leading existing tool, which is known for finding diverse and close explanations but ignores whether those explanations are realistic. The results were stark. In the real estate dataset, nearly all the explanations generated by the standard tool violated at least one rule of reality. In some cases, every single suggestion it made was impossible. By contrast, the new system produced explanations that violated zero rules. Every scenario it offered was consistent with the data it had seen. This did not come at a heavy price. The new explanations were only slightly further away from the original situation than the unrealistic ones, and they remained just as diverse, offering a wide range of different reasons for the decision. In fact, on some datasets, the new method actually provided better explanations because the standard tool had been forced to wander into impossible territory to find a solution.

A major challenge in this work was speed. Checking every possible change against thousands of rules can be incredibly slow, to the point where a single check might take hours. The team developed a series of clever shortcuts to make the process fast enough for practical use. Instead of checking every rule against every piece of data every time, their system learned to identify which rules were actually relevant to the specific situation at hand. They also built a way to remember previous checks so they did not have to repeat the work. These optimizations made the system up to sixty-three times faster than a direct, unoptimized approach. This speed is crucial because it means the system can be used in real-time applications without waiting for a computer to crunch numbers for an hour.

The study also looked at other methods that try to make explanations realistic, such as those that use complex models to guess what data looks like or those that only pick examples from a pre-existing list. The researchers found that even these sophisticated methods often failed to respect the hard rules of the data. A model might suggest a combination of features that looks statistically likely but still breaks a specific logical rule, like a tax exemption that does not apply to a certain state. The new approach is unique because it guarantees that the explanation will not break any of the rules. It does this by treating the rules as absolute laws rather than soft suggestions. If a suggestion violates a rule, the system adjusts it until it fits, ensuring the final explanation is not just a guess, but a factually valid scenario.

This work highlights a critical gap in how we currently trust and understand artificial intelligence. It shows that being close to the original data is not enough; an explanation must also be grounded in the reality of the world it describes. By ensuring that counterfactuals are realistic, the researchers have made these explanations more trustworthy and useful for the people who need them. Whether it is a homeowner wondering why their property value is low or a job seeker understanding why they were rejected, knowing that the suggested path to a different outcome is actually possible makes the difference between a confusing mathematical trick and a clear, actionable insight. The team's success in balancing realism with diversity and speed suggests that the future of explainable AI lies not just in finding the closest answer, but in finding the true one.

Technical Summary: Realistic Counterfactual Explanations via Denial Constraints

Problem Statement

In Explainable AI (XAI), counterfactual explanations (CFs) are perturbations to an input instance that result in a change of the model's prediction label. While existing state-of-the-art methods (e.g., DiCE) effectively optimize for proximity (minimizing the distance between the original instance and the CF) and diversity (providing varied reasons for the prediction), they often fail to ensure realism. A CF may be mathematically close to the original instance but correspond to an impossible or highly unlikely scenario (e.g., a Manhattan condo with 10 bedrooms).

Current approaches to realism are limited: some restrict CFs to existing data points (limiting diversity and coverage), while others learn complex generative models (which may not guarantee adherence to specific data integrity rules). This paper addresses the gap by formalizing the problem of generating CFs that are simultaneously close, diverse, and realistic according to logical constraints derived from the data distribution.

The authors define realism through Denial Constraints (DCs), a class of logical constraints extensively studied in relational databases. DCs are universally quantified first-order formulas (e.g., "No individual under 17 holds a Doctorate" or "No Manhattan apartment has more than 4 bedrooms") that must hold for any valid instance in the dataset. The core challenge is to find a set of $k$ CFs that flip the classification label, minimize distance, maximize diversity, and strictly adhere to a given set of DCs.

Methodology

The paper proposes a Perturb-and-Project framework to solve this constrained optimization problem. The approach consists of three main phases:

1. Perturbation Phase

The system first generates candidate CFs using a standard, constraint-agnostic method (specifically DiCE). This phase focuses on finding instances that flip the label and are diverse, ignoring DCs. These initial candidates often violate realism constraints.

2. Projection Phase

This is the core contribution. The system projects the "unrealistic" candidates onto the space of DC-consistent tuples. Formally, given a candidate tuple $p$ , the goal is to find a tuple $p'$ such that:

$p'$ satisfies all Denial Constraints when added to the dataset.
$p'$ preserves immutable attributes (e.g., location, age) of the original instance.
$p'$ minimizes the distance to $p$ .

The authors prove that finding the nearest DC-consistent tuple is NP-hard, even for unary DCs. Consequently, they employ an SMT (Satisfiability Modulo Theories) solver (specifically Z3) to solve the projection problem. The projection is formulated as an optimization problem where the objective is distance minimization subject to constraints derived from the DCs and the dataset.

3. Greedy Selection

The iterative process may yield more than $k$ valid CFs. A final greedy selection step chooses the subset of size $k$ that maximizes a scoring function balancing diversity (via Determinantal Point Processes) and proximity.

Key Optimizations

To address the scalability issues of using SMT solvers repeatedly (which can take hours for a single projection), the authors introduce three dedicated optimizations:

Optimizer Caching (Pre-processing): Since DC satisfaction constraints depend only on the dataset and the set of immutable attributes (not the specific tuple being projected), the solver's constraint set is pre-computed and cached. This avoids re-instantiating constraints for every projection.
Suspect Set Filtering: Inspired by data cleaning literature, this technique filters the dataset to include only "suspect" tuples relevant to the specific immutable attributes of the input. This drastically reduces the number of constraints passed to the solver, particularly for binary DCs.
Diversity Constraints: To prevent the projection of multiple candidates into the same realistic region, explicit constraints are added to the solver to ensure new projections differ significantly from previously found ones.

Key Contributions

Formalization: The paper is the first to formally define the problem of generating diverse counterfactuals that adhere to Denial Constraints, integrating proximity, diversity, and DC-based realism.
Algorithmic Framework: It introduces a perturb-and-project framework that combines state-of-the-art CF generation with database-inspired projection techniques.
Complexity Analysis: The authors prove that the projection subproblem (finding the nearest DC-consistent tuple) is NP-hard.
Optimizations: They develop specific solver optimizations (caching, suspect-set filtering, and diversity-aware constraints) that make the NP-hard problem tractable in practice.
Empirical Validation: Extensive experiments on four benchmarks (Adult, NY Housing, Tax, Census) demonstrate the efficacy of the approach.

Experimental Results

The authors evaluated their method against DiCE and other baselines (including generative models and closest-instance retrieval):

Realism: The proposed solution achieves zero constraint violations. In contrast, DiCE produces unrealistic CFs in 55.9% to 100% of cases across the datasets, with some CFs violating constraints against thousands of database tuples. Even plausibility-aware generative methods (e.g., CCHVAE, CRUDS) failed to satisfy DCs in 100% of cases.
Proximity: The cost of enforcing realism is modest. The aggregated distance ( $dist_{agg}$ ) increased by less than 10% on most datasets (Adult, Tax) compared to DiCE. On the Census dataset, the increase was higher (~31%) but dropped to 9% when diversity constraints were removed, suggesting a trade-off between diversity and strict realism.
Diversity: The method maintains diversity scores comparable to DiCE (within 1-2% on most datasets). The diversity optimization significantly improved scores on the NY Housing dataset, where constraints naturally limit the spread of valid CFs.
Execution Time: A vanilla SMT approach was prohibitively slow (e.g., ~18,000 seconds for a single projection on Census). The proposed optimizations reduced runtime by up to 63× (down to ~300 seconds), making the approach scalable. The overhead compared to unconstrained DiCE is a factor of 1.1 to 10.5, depending on the dataset.

Significance and Claims

The paper claims that existing XAI solutions often produce explanations that are technically correct regarding the model's decision boundary but practically useless because they describe impossible scenarios. By leveraging Denial Constraints, the authors provide a mechanism to guarantee that counterfactuals are logically consistent with the data's integrity rules.

The significance lies in bridging the gap between Explainable AI and Data Management. The authors argue that while statistical methods (like VAEs) approximate data distributions, they cannot guarantee adherence to hard integrity rules. In contrast, DCs offer an explicit, checkable guarantee of realism. The work demonstrates that it is possible to achieve this guarantee with only a minor compromise in proximity and diversity, provided that dedicated algorithmic optimizations are used to handle the computational complexity.

The authors remain modest about their scope, noting that their approach is specific to tabular data and that extending these constraint-based notions to unstructured domains (like images) is left for future work. They also acknowledge that while their method guarantees DC adherence, the quality of the explanation ultimately depends on the quality of the mined or manually defined constraints.