CS Paper Radar

Realistic Counterfactual Explanations via Denial Constraints

Avia Asael, Nave Frost, Amir Gilad, Daniel Deutch

cs.DB ·submitted 2026-08-26 19:16 UTC · v1
top venue

Abstract

In the realm of Explainable AI, classification results are often explained via counterfactuals (CFs for short), which are (ideally small) perturbations to an instance that lead to a change of classification label. Such CFs may serve as explanations for the prediction, pinpointing the features that were important. Existing explainability solutions typically aim at minimizing the distance of CFs from the original instance so that they are specific to it, and/or maximizing the diversity of CFs to cover multiple facets of the reasons underlying the prediction. In this paper, we note that in pursuing these aims, state-of-the-art explainability solutions may (and often do) yield counterfactual explanations that do not correspond to realistic instances. This limits their applicability and usefulness in practice. To remedy this, we combine ideas from Explainable AI with ideas from data management. Specifically, we capture realism of CFs via logical constraints that hold with respect to a dataset of examples (e.g., training set); the class of such constraints that we focus on is that of denial constraints, extensively studied in the context of relational databases. Algorithmically, we then combine explainable AI solutions to yield CFs, with ideas from data cleaning that we adapt to this unique setting, to transform CFs into realistic ones. Extensive experiments across four datasets validate that our solutions achieve realism with relatively minor compromise in terms of distance and diversity. They further validate that the dedicated optimizations that we have developed to speed up the search for CFs are indeed highly effective.

Journal ref
Proc. 32nd ACM SIGKDD Conf. on Knowledge Discovery and Data Mining (KDD '26), Jeju Island, South Korea, Aug 2026, pp. 33-44
DOI
10.1145/3770855.3817712

Closest papers

Nearest neighbours by meaning across the whole index.

FCx: An algorithm for finding Feasible Counterfactual Explanations

cs.LG ·2026-09-16 ·Kleopatra Markou, Vana Kalogeraki, Dimitrios Gunopulos
similarity 0.73
Abstract · 20 pages, 9 figures

Counterfactual (CF) explanations identify changes that alter an input's classification. While existing methods produce realistic and low-cost CFs, they often fail to ensure feasibility, by suggesting non-constructive modifications or incompatible with future changes (e.g., changing an individual's race to secure a job offer). We introduce a refinement of CF explanations that explicitly enforces feasibility. Our approach is the first to efficiently generate CFs that are realistic, low-cost and feasible. We accommodate both hard feasible constraints, specified by domain knowledge users, and soft feasible constraints, inferred automatically via causal inference from the dataset. Our method, Feasible Counterfactual Explanations (FCx), is based on a modified Variational Autoencoder (VAE) optimized with a multi-factor loss function. We measure the cost of a change based on the absolute change in values (proximity) as well as the number of features changed (sparsity) while realism is measured based on the LOF for density estimation, guaranteeing that CFs reside in densely populated regions. Extensive experiments on four public datasets show that our approach matches state-of-the-art performance across multiple metrics while guaranteeing feasibility.

0.09

On Formal Counterfactual Explanations

cs.AI cs.LGcs.LO ·2026-11-16 ·Alexey Ignatiev, Peter J. Stuckey, Joao Marques-Silva
similarity 0.72
Abstract

Counterfactual explanations are often seen as counterfactual conditionals under closest-world semantics, requiring one to reason over all minimally distant counterexamples. In contrast, formal XAI typically relies on feature-based abductive explanations (AXps) and contrastive explanations (CXps), which admit efficient computation and a minimal hitting-set duality. This paper bridges these perspectives by (i) characterizing closest-world counterfactual explanations explicitly as a disjunctive normal form over all minimally distant counterexample instances, and (ii) introducing conjunctive counterfactual explanations (CFXps), a subclass of counterfactual antecedents restricted to conjunctions of feature literals that guarantee prediction change. The paper establishes structural results connecting CXps, AXps and CFXps: every CXp induces an AXp for its witness instance, and every CXp together with a witness AXp induces a CFXp whose support is precisely determined by that AXp. These theoretical results yield a modular approach for computing CFXps using existing AXp/CXp machinery. Experiments on a representative set of benchmarks using tree ensembles and neural networks show that CFXp extraction is practically efficient. Compared with popular point-based counterfactual explainers, CFXps generally require no more feature changes and can guarantee the counterfactual prediction beyond a single instance.

0.10

Counterfactual Explanations and the Scope of Contestability

cs.CY ·2026-08-25 ·Alice C. W. Huang, Thomas Grote
similarity 0.71
Abstract · forthcoming in Synthese

The automation of consequential decisions through opaque machine learning models in societal domains impedes our agency. This paper is about how agency can be reinstated by the provision of certain kinds of knowledge. More precisely, we discuss whether a specific type of explanation, counterfactual explanations, facilitates our ability to contest algorithmic decisions. Against this backdrop, our paper makes three contributions: First, we develop an account of contestability, where contestability is defined as the provision of information, sufficient for a decision-subject to use as a basis for demanding that a decision be revoked. We also demarcate contestability from adjacent concepts in the discourse surrounding the right to explanation, such as justification and recourse. Second, we examine to what extent counterfactual explanations are conducive to contestability by considering a variety of failure modes causing problematic algorithmic decisions and scrutinize to what extent counterfactual explanations help us detect the underlying errors. Third, we propose ways in which, with certain modifications, counterfactual explanations can be made more fitting to serve the desired function. In this vein, we sketch the contours of a multi-shot approach to counterfactuals, where decision-subjects can query a model to test their own counterfactuals for a (limited) number of times.

0.23

Taking the Whys Seriously: Limitations of Counterfactual Explanations in Justification and Recourse

cs.CY cs.AI ·2026-08-31 ·Mattia Cerrato, Otto Sahlgren, Xenia Heilmann
similarity 0.70
Abstract

Counterfactual explanations (CEs) are widely used in explainable artificial intelligence (AI) to show how a model's outputs would change if the input features were manipulated. This technique is used for a range of tasks such as debugging models, explaining predictions, justifying decisions, and providing algorithmic recourse. In this paper, we explore the normative legitimacy of employing counterfactuals in real-life model deployment settings. We discuss the different stakes involved in these different purposes for which CEs are commonly employed, and find stricter requirements for justification and recourse. In particular, we find that naive application of CEs for justification and recourse can lead to ignoring contestable choices made throughout the machine learning (ML) pipeline, thus obfuscating that decisions and counterfactuals for those decisions are also artifacts of an organization's materialized design and governance choices. We demonstrate this with four empirical experiments involving interventions at stages of the ML pipeline ``upstream" of the explanation itself, and show that these affect the generated counterfactuals. We find that an organization's choices on measurement models for feature and labels, business requirements, model validation, and the metric of model success have as much or more impact on the generated counterfactuals as the specifics of the generating method. Our findings underline the need to account for such choices upon providing justification and recourse, providing a stark reminder of the relational nature of these tasks. As putative justifications or recourse recommendations, CEs do not provide adequate answers to some important "why"-questions because they preclude consideration of whether the decision-maker ought to have acted differently.

0.17

Towards A Unified Information Bottleneck Framework for Time Series Explanations

cs.LG cs.AI ·2026-08-26 ·Xu Zheng, Zichuan Liu, Zhuomin Chen, Mayur Akewar, Janki Bhimani +5 more
similarity 0.70
Abstract

Explaining deep learning models operating on time series data is crucial in various applications that require transparent and interpretable insights into model behavior. {Existing explanation methods generally fall into two categories: attribution-based explanations, which identify the temporal regions most responsible for a prediction, and counterfactual explanations, which reveal how an input should be modified to alter the model's decision.} {Despite valuable insights, these two fields are largely studied independently. This disconnect leaves attribution methods lacking causal validation, while counterfactual methods suffer from severe instability, producing adversarial-like noise instead of meaningful explanations.} In this work, we revisit time-series explainability from an information-theoretic perspective and show that existing explainers are vulnerable to trivial solutions and distributional shifts. To address these limitations, we propose a unified objective function for explainable time series learning that bridges attribution and counterfactual reasoning within a single framework. Building upon the Information Bottleneck principle, our formulation explicitly prevents trivial explanations and out-of-distribution counterfactuals. {Based on this objective function, we introduce {\modelname}, a novel explanation framework that learns a parametric transformation network to construct explanation-embedded instances, where preserved information yields attribution explanations and controlled information removal produces stable counterfactual explanations.} We evaluate {\modelname} on synthetic and real-world benchmarks against state-of-the-art baselines. Extensive quantitative and qualitative results show that {\modelname} consistently outperforms competing methods, yielding faithful attributions and stable counterfactual explanations.

0.06

Evolving Explanations: Complexity-Adaptive Refinement of Faithful Explanations for Symbolic Regression

cs.LG ·2026-11-02 ·Elisabeth Mayrhuber, Ting Hu, Stephan Winkler
similarity 0.69
Abstract

Natural-language explanations generated by large language models (LLMs) for machine learning models often seem fluent but are not necessarily faithful to the underlying model. We formalize this mismatch as a faithfulness gap and propose a complexity-adaptive refinement framework for symbolic regression that iteratively generates and validates explanations until numerical agreement with the target expression is achieved. The approach follows a two-stage pipeline: an explainer LLM produces textual descriptions at increasing levels of detail, while an independent validator LLM extracts a symbolic expression that is compared against the original model. This process is framed as a discrete search over explanation space, where complexity is minimized subject to a faithfulness constraint. We evaluate the method on real-world and synthetic datasets, with a total of 250 runs across varying model complexities. The explanation refinement loop achieves an overall pass rate of 84.0%, with most explanations converging at low complexity levels and only a small fraction requiring detailed descriptions. Our results demonstrate that faithful explanations can be obtained with minimal necessary complexity by explicitly closing the explanation loop through symbolic validation.

0.13

When Are Concept Bottleneck Model Explanations Faithful and Compact?

cs.LG cs.AIstat.ML ·2026-10-05 ·Stefano Teso, Emanuele Marconato, Steve Azzolin, Antonio Vergari
position similarity 0.68
Abstract

Concept bottleneck models (CBMs) are neural classifiers that allow to explain their decisions via high-level concepts, potentially enabling understanding, steering and debugging. However, their explanations are often derived heuristically. Building on formal explainability, we argue they should also be faithful, i.e., not misreport which concepts actually matter. We show that, for widespread CBM architectures, including recent VLM-based variants, faithful explanations must include all concepts in the bottleneck, compromising interpretability when this is large. This result applies to both heuristic and faithful-by-construction formal explanations. To encourage the existence of compact faithful explanations, we suggest i) modeling concepts probabilistically as binary or categorical random variables (rather than logits), and ii) employing per-concept training-time sparsification via group lasso (rather than regular elastic net). We also extend algorithms from formal explainability to CBMs, and show they outperform natural heuristics in terms of guarantees and explanation size. Overall, our work warns against naive interpretability claims and provides formal conditions and practical strategies for ensuring CBMs are as interpretable as advertised.

0.07

On the Limits of Sufficient Explanations

cs.LG ·2026-11-13 ·Klaus Weinbauer, Peter F. Stadler, Thomas Gärtner, Sagar Malhotra
similarity 0.67
Abstract

We formally characterize the conditions under which sufficient explanations exist for classifiers on structured data such as graphs and strings. We focus on post-hoc explainers that select parts of the input as sufficient explanations. An explanation is sufficient if the selected part alone ensures the predicted label. Sufficient explanations have been widely adopted across data modalities, including graphs, strings, and images. However, a unified formal analysis of sufficient explanations remains missing. We bridge this gap with four main contributions: (i) We define a general explanation formalism consisting of an instance space, a classifier, and a select relation. The select relation specifies which potential sub-instances or feature subsets can be selected as explanations from each instance; (ii) We show that the existence of sufficient explainers is fully characterized by the interplay between the classifier and the select relation; (iii) We extend this analysis to practically relevant variants of sufficiency, including probabilistic sufficiency and deletion sufficiency; (iv) Based on the formal analysis, we devise statistics that bound the maximum achievable sufficiency for a given task. We evaluate these statistics on language, protein, and molecular classification datasets and find that full sufficiency is unattainable on most of them. Since these bounds hold for every explainer, they provide a task-level reference against which any explainer's sufficiency can be judged in absolute terms.

0.25