# Rigorous Probabilistic Guarantees for Robust Counterfactual Explanations

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 10 Jul 2024.

## Builds on (most cited first, 20 of 20)

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Learning Model-Agnostic Counterfactual Explanations for Tabular Data](https://mlsanity.com/paper/1910.09398/) (2019)
- [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)
- [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)
- [Consistent Counterfactuals for Deep Models](https://mlsanity.com/paper/2110.03109/) (2021)
- [Abstraction based Output Range Analysis for Neural Networks](https://mlsanity.com/paper/2007.09527/) (2020)
- [Robust Counterfactual Explanations in Machine Learning: A Survey](https://mlsanity.com/paper/2402.01928/) (2024)
- [Formalising the Robustness of Counterfactual Explanations for Neural Networks](https://mlsanity.com/paper/2208.14878/) (2022)
- [Enumerating Safe Regions in Deep Neural Networks with Provable Probabilistic Guarantees](https://mlsanity.com/paper/2308.09842/) (2023)
- [Robust Bayesian Recourse](https://mlsanity.com/paper/2206.10833/) (2022)
- [Promoting Counterfactual Robustness through Diversity](https://mlsanity.com/paper/2312.06564/) (2023)
- [Recourse under Model Multiplicity via Argumentative Ensembling (Technical Report)](https://mlsanity.com/paper/2312.15097/) (2023)
- [Generating robust counterfactual explanations](https://mlsanity.com/paper/2304.12943/) (2023)

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

- [Counterfactual Explanations with Probabilistic Guarantees on their Robustness to Model Change](https://mlsanity.com/paper/2408.04842/) (2024)
- [RobustX: Robust Counterfactual Explanations Made Easy](https://mlsanity.com/paper/2502.13751/) (2025)
- [On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI](https://mlsanity.com/paper/2601.09455/) (2026)
- [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)

We study the problem of assessing the robustness of counterfactual explanations for deep learning models. We focus on textitplausible model shifts altering model parameters and propose a novel framework to reason about the robustness property in this setting. To motivate our solution, we begin by showing for the first time that computing the robustness of counterfactuals with respect to plausible model shifts is NP-complete. As this (practically) rules out the existence of scalable algorithms for exactly computing robustness, we propose a novel probabilistic approach which is able to provide tight estimates of robustness with strong guarantees while preserving scalability. Remarkably, and differently from existing solutions targeting plausible model shifts, our approach does not impose requirements on the network to be analyzed, thus enabling robustness analysis on a wider range of architectures. Experiments on four binary classification datasets indicate that our method improves the state of the art in generating robust explanations, outperforming existing methods on a range of metrics.