- 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 , 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?