# Interval Abstractions for Robust Counterfactual Explanations

arXiv: https://arxiv.org/abs/2404.13736 · HTML: https://mlsanity.com/paper/2404.13736/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 72 references that are in the map.
- First posted on arXiv 21 Apr 2024.

## Builds on (most cited first, 30 of 47)

- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [Algorithmic Recourse: from Counterfactual Explanations to Interventions](https://mlsanity.com/paper/2002.06278/) (2020)
- [Interpretable Counterfactual Explanations Guided by Prototypes](https://mlsanity.com/paper/1907.02584/) (2019)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach](https://mlsanity.com/paper/1801.10578/) (2018)
- [Multi-Objective Counterfactual Explanations](https://mlsanity.com/paper/2004.11165/) (2020)
- [Learning Model-Agnostic Counterfactual Explanations for Tabular Data](https://mlsanity.com/paper/1910.09398/) (2019)
- [Algorithmic recourse under imperfect causal knowledge: a probabilistic approach](https://mlsanity.com/paper/2006.06831/) (2020)
- [An approach to reachability analysis for feed-forward ReLU neural networks](https://mlsanity.com/paper/1706.07351/) (2017)
- [Counterfactual Explanations Can Be Manipulated](https://mlsanity.com/paper/2106.02666/) (2021)
- [Towards Robust and Reliable Algorithmic Recourse](https://mlsanity.com/paper/2102.13620/) (2021)
- [Diffusion Visual Counterfactual Explanations](https://mlsanity.com/paper/2210.11841/) (2022)
- [CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms](https://mlsanity.com/paper/2108.00783/) (2021)
- [Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking](https://mlsanity.com/paper/1706.06691/) (2017)
- [On Counterfactual Explanations under Predictive Multiplicity](https://mlsanity.com/paper/2006.13132/) (2020)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [Instance-based Counterfactual Explanations for Time Series Classification](https://mlsanity.com/paper/2009.13211/) (2020)
- [NICE: An Algorithm for Nearest Instance Counterfactual Explanations](https://mlsanity.com/paper/2104.07411/) (2021)
- [On the Adversarial Robustness of Causal Algorithmic Recourse](https://mlsanity.com/paper/2112.11313/) (2021)
- [Robust Counterfactual Explanations for Tree-Based Ensembles](https://mlsanity.com/paper/2207.02739/) (2022)
- [Robust Counterfactual Explanations for Neural Networks With Probabilistic Guarantees](https://mlsanity.com/paper/2305.11997/) (2023)
- [Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse](https://mlsanity.com/paper/2203.06768/) (2022)
- [A Survey on the Robustness of Feature Importance and Counterfactual Explanations](https://mlsanity.com/paper/2111.00358/) (2021)
- [Consistent Counterfactuals for Deep Models](https://mlsanity.com/paper/2110.03109/) (2021)

## Built on by (most cited first, 7 of 7)

- [RobustX: Robust Counterfactual Explanations Made Easy](https://mlsanity.com/paper/2502.13751/) (2025)
- [ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets](https://mlsanity.com/paper/2602.07674/) (2026)
- [Argumentative Ensembling for Robust Recourse under Model Multiplicity](https://mlsanity.com/paper/2506.20260/) (2025)
- [Synthesising Counterfactual Explanations via Label-Conditional Gaussian Mixture Variational Autoencoders](https://mlsanity.com/paper/2510.04855/) (2025)
- [Evaluating Counterfactual Explanation Methods on Incomplete Inputs](https://mlsanity.com/paper/2604.08004/) (2026)
- [A Probabilistic Consensus-Driven Approach for Robust Counterfactual Explanations](https://mlsanity.com/paper/2604.17494/) (2026)
- [Robust to Which Model Change? A Unified Evaluation of Robust Counterfactual Explanations](https://mlsanity.com/paper/2609.30918/) (2026)

## Abstract (arXiv)

Counterfactual Explanations (CEs) have emerged as a major paradigm in explainable AI research, providing recourse recommendations for users affected by the decisions of machine learning models. However, CEs found by existing methods often become invalid when slight changes occur in the parameters of the model they were generated for. The literature lacks a way to provide exhaustive robustness guarantees for CEs under model changes, in that existing methods to improve CEs' robustness are mostly heuristic, and the robustness performances are evaluated empirically using only a limited number of retrained models. To bridge this gap, we propose a novel interval abstraction technique for parametric machine learning models, which allows us to obtain provable robustness guarantees for CEs under a possibly infinite set of plausible model changes Delta. Based on this idea, we formalise a robustness notion for CEs, which we call Delta-robustness, in both binary and multi-class classification settings. We present procedures to verify Delta-robustness based on Mixed Integer Linear Programming, using which we further propose algorithms to generate CEs that are Delta-robust. In an extensive empirical study involving neural networks and logistic regression models, we demonstrate the practical applicability of our approach. We discuss two strategies for determining the appropriate hyperparameters in our method, and we quantitatively benchmark CEs generated by eleven methods, highlighting the effectiveness of our algorithms in finding robust CEs.