acceptodds
Under review as a conference paper at ICLR 2027

From Formal Contrastive to Formal Counterfactual Explanations

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.

Primary area:
interpretability and explainable AI
Keywords:
Counterfactual explanations, formal reasoning, formal explainable AI

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_8yPMOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper investigates formal counterfactual explanations for machine learning classifiers. It introduces conjunctive counterfactual explanations (CFXps), which extend contrastive explanations (CXps) by identifying additional features that must remain fixed to guarantee a prediction change. The authors establish theoretical relationships between CFXps, CXps, and abductive explanations (AXps), and propose an algorithm that constructs CFXps by combining existing CXp and AXp computation procedures. Experiments on 21 datasets using XGBoost and ReLU neural networks evaluate computational efficiency and compare the proposed approach against existing counterfactual explanation methods.

Critical strengths

S1) Technically sound theoretical framework. The paper provides a coherent formal analysis connecting CXps, AXps, and CFXps. The propositions appear mathematically correct, and the authors explicitly acknowledge some limitations of the proposed formulation. Although I have concerns about the novelty of the results, the theoretical development itself appears sound.

S2) Practical computational feasibility. The authors demonstrate that CFXps can be computed efficiently using existing formal explanation techniques. The evaluation covers 21 datasets and two different model families, using independent reasoning backends. This provides useful evidence that the proposed construction is computationally practical on the considered benchmarks.

Critical weaknesses

W1) Limited conceptual and algorithmic novelty. Proposition 1 establishes that CFXps and CXps share the same subset-minimal feature sets, while Proposition 4 constructs CFXps by combining an existing CXp, its counterfactual witness, and an AXp of that witness. Although this construction provides an additional certificate guaranteeing the prediction over a region, it remains unclear what fundamentally new explanatory capability it introduces beyond combining these established concepts. Since the introduction of CFXps is the paper's main contribution, I find the limited conceptual and algorithmic novelty a significant concern for ICLR.

W2) Insufficient evaluation of the practical benefits of regional guarantees. A central claim of the paper is that CFXps provide guarantees beyond a single counterfactual instance. However, the experiments do not adequately evaluate the extent of these guarantees. For instance, the authors report that CFXp certificates for ReLU models fix 22.6 features on average. However, the experiments do not directly analyze the number of unconstrained features per explanation or report how frequently the certified region degenerates to a single counterfactual instance. More importantly, similar regional guarantees could be obtained by computing an AXp for a counterfactual returned by an existing method, such as DiCE or Growing Spheres. Although this would not necessarily produce a subset-minimal CFXp, it would provide the same type of guarantee. Without such a baseline, the comparison in Table 2 mainly demonstrates that CFXps require relatively few feature changes, rather than establishing the practical advantage of their regional guarantees. I believe this substantially weakens the experimental validation of the paper's main contribution.

W3) Missing mandatory AI use statement. The manuscript does not appear to include the mandatory AI Use Statement required by the ICLR 2027 submission guidelines. This should be addressed to ensure compliance with the conference requirements.

Questions for authors

Q1) Given that Proposition 1 establishes the equivalence between CXp and CFXp feature sets, is there anything a CFXp tells a user that a CXp plus an AXp of its witness does not?

Q2) For each dataset, what’s the distribution of free features m−∣γ∣−∣δ∣m − |\gamma| − |\delta|, ideally normalized by m? How often is it zero, i.e. the certificate only covers the witness?

Q3) How do CFXp certificates compare with AXps computed on counterfactual points returned by DiCE and Growing Spheres, in terms of certificate size, number of free features, and computation time?

Reviewer_2JHpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces Conjunctive Counterfactual Explanations (CFXps), bridging formal contrastive and abductive explanations with counterfactual explanations. The authors establish theoretical relationships between CXps, AXps, and CFXps, proposing a modular approach for their computation. Experiments on tree ensembles and neural networks demonstrate the feasibility of the proposed approach.

Critical strengths

The paper addresses an interesting and timely problem, providing a theoretically sound framework connecting different types of formal explanations. The proposed approach is well motivated, and the theoretical results represent a valuable contribution to the field of explainable AI.

Critical weaknesses

The practical extraction of CXps and AXps and their combination into CFXps are not sufficiently clear. A pseudocode illustrating the overall procedure would significantly improve the presentation. The related work is also incomplete, missing relevant surveys such as Artelt, A., & Hammer, B. (2019). On the computation of counterfactual explanations--A survey. arXiv preprint arXiv:1911.07749., Guidotti, R. (2024). Counterfactual explanations and how to find them: literature review and benchmarking: R. guidotti. Data mining and knowledge discovery, 38(5), 2770-2824. Verma, S., Boonsanong, V., Hoang, M., Hines, K., Dickerson, J., & Shah, C. (2024). Counterfactual explanations and algorithmic recourses for machine learning: A review. ACM Computing Surveys, 56(12), 1-42. More importantly, the experimental evaluation is rather limited. As discussed extensively in the counterfactual explanation literature, counterfactual quality is typically assessed through multiple dimensions, including proximity, diversity, plausibility, and causal validity. The current evaluation does not sufficiently investigate these aspects, making it difficult to assess the overall quality of the proposed explanations compared to existing approaches.

Questions for authors

Could the authors provide a pseudocode illustrating how CXps and AXps are extracted and combined to generate CFXps? Could the authors extend the experimental evaluation to include additional counterfactual quality metrics, such as diversity, plausibility, and causal validity, following established evaluation practices in the literature?

Reviewer_RvLWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces Conjunctive Counterfactual Explanations (CFXps), which identify feature changes that guarantee a different prediction from a classifier under certain conditions. The work builds on two existing types of explanations: abductive explanations (AXps), which identify features sufficient to guarantee a prediction, and contrastive explanations (CXps), which identify minimal feature sets whose modification can change a prediction. The authors establish theoretical connections between these concepts and show how CFXps can be computed using existing AXp and CXp algorithms. They evaluate their method on 21 tabular datasets using XGBoost classifiers and ReLU neural networks, comparing it against several established counterfactual explanation methods.

Critical strengths
  • The paper provides a detailed formalization of counterfactual explanations and proves several relationships between AXps, CXps, and CFXps. The proposed method comes with formal guarantees about the classifier's predictions, and the theoretical results show how it can be implemented using existing algorithms. The guarantees and the use of existing methods are particularly strong points of this paper.

  • The authors evaluate their method on 21 datasets using two different types of classifiers and compare it against several established methods. The results show that CFXps can be computed efficiently and generally require fewer or the same number of feature changes compared to the baselines, while also providing formal guarantees. However, some aspects of the experimental evaluation need further investigation, as discussed below (see Critical Weaknesses).

Critical weaknesses
  • Although the authors evaluate their method on 21 datasets, they only report aggregated results, making it difficult to understand whether the improvements hold across all datasets or are mainly driven by a few of them. I think a per-dataset breakdown should be included in the appendix, along with some discussion of how dataset characteristics, such as the number of features or classes, affect the results. Another concern is the selection of instances used for the evaluation. The authors randomly select up to 200 instances per dataset, apparently using only one random seed, without examining how this choice affects the results. For datasets with tens of thousands of instances, a different sample could potentially lead to different conclusions. Overall, while the results look promising, I think more analysis is needed to understand how consistent they are across datasets and different selections of instances.

  • The proposed method only considers the number of features that need to change, without accounting for how much they change or whether these changes are realistic. For example, a very large change in a numerical feature is treated the same as a small adjustment. The method also does not consider whether certain features can be changed at all, or whether changing one feature would affect others. I understand that this is not necessarily the focus of the paper, but it limits the practical usefulness of the explanations. The novelty of the work is also not crystal clear to me. The main contribution seems to be connecting existing AXp and CXp methods to construct CFXps, while counterfactual explanations with similar characteristics have already been studied in the literature. That said, I am not very familiar with the Formal XAI area, so I may be missing some important aspects of the contribution. I would be happy to hear the authors' perspective on this and better understand what distinguishes their approach from previous work, and whether they can address the lack of applicability mentioned above (e.g., if they plan to include weighting depending on the magnitude of a change, or consider plausibility or actionability of edits, etc.). See also my questions below.

While the above weaknesses are somewhat important, I believe that they can be clarified during rebuttal with certain revisions, so I propose a weak accept for the paper, while my judgement is between weak reject and weak accept. If my concerns are addressed, I will retain my positive score.

Questions for authors
  1. Could the authors include a per-dataset breakdown of the results in Table 2, perhaps in the appendix? I would be interested to see whether the improvements are consistent across datasets and whether the number of features, classes, or other dataset characteristics affect the performance.

  2. Why did the authors choose to evaluate only up to 200 randomly selected instances per dataset? Have they checked whether the results remain similar when using different random seeds or larger samples, especially for datasets with many thousands of instances?

  3. Have the authors considered taking into account the magnitude of feature changes, or whether certain changes are actually possible or realistic? Would it be possible to incorporate such constraints without affecting the theoretical guarantees of the proposed method?

  4. Could the authors clarify what they see as the main novelty of the proposed CFXp framework compared to existing counterfactual explanation methods? In particular, since the method builds on existing AXp and CXp algorithms, what is gained by combining them in this way, and how does this differ from previous approaches that also provide guarantees over regions of the feature space?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.