CS Paper Radar

On Formal Counterfactual Explanations

Alexey Ignatiev, Peter J. Stuckey, Joao Marques-Silva

cs.AI cs.LGcs.LO ·submitted 2026-11-16 23:51 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Realistic Counterfactual Explanations via Denial Constraints

cs.DB ·2026-08-26 ·Avia Asael, Nave Frost, Amir Gilad, Daniel Deutch
top venue similarity 0.72
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.

0.43

FCx: An algorithm for finding Feasible Counterfactual Explanations

cs.LG ·2026-09-16 ·Kleopatra Markou, Vana Kalogeraki, Dimitrios Gunopulos
similarity 0.68
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

Modus Tollens and Counterfactuals and Counterfactual Reasoning Based on Three Types of Negation

cs.AI ·2026-09-07 ·Zhenghua Pan
similarity 0.67
Abstract · 19 papers,6 figures

Modus Tollens (MT) is a classical logical inference rule, while counterfactuals are hypothetical statements that are contrary to facts, and counterfactual reasoning is a process of reasoning based on counterfactuals. Negation is an indispensable core concept in them. In this paper, based on the logical systems LCOI&PLCOI with contradictory negation, opposite negation and intermediary negation, we propose three variants of Modus Tollens corresponding to distinct negation types, namely MTC: Modus Tollens based on contradictory negation, MTO: Modus Tollens based on opposite negation, and MTI: Modus Tollens based on intermediary negation. We define the implications within MTC, MTO and MTI, provide the truth value algorithms of MTC, MTO and MTI, and discuss the reducibility of these algorithms. To incorporate these three types of negation into counterfactuals and counterfactual reasoning, we differentiate counterfactuals into two types based on whether they possess logical negation, thereby proposing three counterfactuals and counterfactuals reasoning based on different logical negations. In this paper, we further argue that the three counterfactuals reasoning based on different logical negations have the same inference form as MTC, MTO and MTI, respectively. In other words, they share the same inference structure. As a result, the truth value algorithms for MTC, MTO and MTI can be as the truth value algorithms for the three counterfactuals reasoning based on different logical negations. The algorithms indicates that if the first premise of the reasoning is true, the truth values of the reasoning conclusions are identical to the truth values of the three negative premises in the reasoning premises, respectively. This reflects the consistency and accuracy of the truth value algorithms.

0.18

Formal Explanations for Linear Temporal Logic over Finite Traces

cs.LO cs.AI ·2026-10-26 ·Valeria Fionda, Antonio Ielo, Francesco Ricca
theory similarity 0.63
Abstract

Linear Temporal Logic over Finite Traces (LTLf) is widely used in Artificial Intelligence to specify desired temporal behavior and determine whether finite traces satisfy or violate it. Explaining these outcomes is essential for debugging and trust. However, existing approaches typically capture either sufficient reasons or counterfactual causes, without clarifying their relationship. We introduce a native characterization of abductive (AXps) and contrastive (CXps) explanations directly over finite traces, based on locking and unlocking time-indexed events. We prove its equivalence to the classifier-based formulation, and show that CXps coincide with a recently proposed temporal causality semantics for LTLf. This characterization enables an efficient implementation based on the enumeration of minimal unsatisfiable cores and minimal correction sets of ASP programs. Experiments on real-world event logs demonstrate the effectiveness of the approach.

0.27

xWhyL: Causal Interactive Learning

cs.LG cs.AIstat.ML ·2026-09-22 ·Nicholas Tagliapietra, Florian Peter Busch, Moritz Willig, Matej Zečević, Lavdim Halilaj +2 more
theory similarity 0.63
Abstract

Explanations are central to causal reasoning, and cognitive science has long established that the human drive to explain is itself a mechanism for learning about causality. Despite this, learning from those abductive signals is largely ignored in artificial intelligence. While explainable AI (XAI) increasingly draws on causal models to generate explanations, the converse direction about what explanations can do for causality remains largely unexplored. To fill this gap, we propose xWhyL, a formal framework connecting causality and XAI by learning causal models from explanations. We develop a mathematical theory that translates explanations into a learning signal complementary to observational data, and demonstrate how it enables overcoming the limits of observational causal discovery. As explanations can be derived from incorrect beliefs and clash with data, a tension we call the Causal Tug-of-War, we prove conditions under which our framework rejects misspecified explanations rather than absorbing them. Our practical instantiation, Causal Interactive Learning (CIL), shows how expert explanations can efficiently support causal discovery and distinguish correct from incorrect explanations.

0.13

Counterfactual Explanations and the Scope of Contestability

cs.CY ·2026-08-25 ·Alice C. W. Huang, Thomas Grote
similarity 0.63
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

The Illusion of $\textit{What If}$: Evaluating the Breakdown of Counterfactual Reasoning in LLMs

cs.AI ·2026-08-28 ·Yucheng Wang, Yuetian Du, Zhengyi Liu, Rongyu Zhang, Bing Zhao +6 more
top venuebenchmarkcode/data similarity 0.62
Abstract · Accepted by EMNLP 2026

Counterfactual reasoning requires models to reason beyond the observed world and explain how altered conditions propagate through downstream consequences. Existing benchmarks largely target bounded settings with fixed variables or single gold outcomes, overlooking open-domain scenarios requiring causal-process evaluation. To this end, we present $\textbf{WhatIfBench}$, a diagnostic benchmark for open-domain, open-form, long-horizon counterfactual causal reasoning, containing 220 what-if questions across STEM, HSS, and Hybrid scenarios. To evaluate free-form responses, we further propose $\textbf{PRISM}$, which first converts each natural-language explanation into a Response-Derived Semantic Causal Graph of events, states, and mechanisms. On top of this graph, PRISM then jointly applies a Process Metric assessing graph-level causal validity and a Rubric Metric assessing answer-level explanatory adequacy. Evaluating six frontier LLMs with this framework, we find that WhatIfBench remains far from saturated: even the strongest model reaches only a 64.62% final score. Further analysis reveals persistent causal gaps, premise drift, and topology fragmentation, suggesting that fluent counterfactual narratives often mask fragile causal processes. The benchmark, code, and evaluation scripts are available at $\href{https://github.com/zju-gt/WhatIfBench}{WhatIfBench}$.

0.52

MEA: A Reward-Driven Multi-Agent System for Faithful Model Explanations

cs.AI ·2026-10-01 ·Yuyang Cheng, Raghav Kaushik Ravi, Srivarshinee Sridhar, Sriparna Saha, Akash Ghosh +1 more
similarity 0.61
Abstract

Recent years have seen the employment of a plethora of machine learning (ML) models in high-stakes domains, but they remain largely opaque to the practitioners who act on their predictions. While post-hoc explanation methods offer a lens into this model behavior, wielding them effectively demands expertise most domain experts lack: navigating high-dimensional outputs, selecting the best explanations, and synthesizing evidence across disparate tools. To this end, we present MEA, a multi-agent framework that removes the explanation knowledge barrier entirely: a Proposer agent selects and configures explanation tools based on the question and modality, while an Actor agent is optimized end-to-end against faithfulness, transforming the outputs into natural language explanations grounded in model behavior across tabular, text, and vision modalities. Further, we introduce diverse question types spanning feature attribution, counterfactual reasoning, and spurious feature detection, each paired with a perturbation-based faithfulness metric. We find that frontier LLMs systematically produce unfaithful explanations. By optimizing against faithfulness rewards augmented with a modality-adaptive penalty, MEA consistently outperforms post hoc explainers, agentic, and closed-source baselines across six datasets, with reward-driven optimization yielding faithfulness gains of +28% (tabular), +21% (text), and +34% (vision) over the untrained backbone. More broadly, our findings suggest that AI agents themselves can serve as a scalable, adaptable interface to ML explainability, opening a path toward natural-language explainability that generalizes beyond the fixed, single-purpose tools that have long defined the field.

0.17