# Attribution-based Explanations that Provide Recourse Cannot be Robust

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 58 references that are in the map.
- First posted on arXiv 31 May 2022.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI](https://mlsanity.com/paper/1910.10045/) (2019)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [SmoothGrad: removing noise by adding noise](https://mlsanity.com/paper/1706.03825/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Towards Faithfully Interpretable NLP Systems: How should we define and evaluate faithfulness?](https://mlsanity.com/paper/2004.03685/) (2020)
- [A Benchmark for Interpretability Methods in Deep Neural Networks](https://mlsanity.com/paper/1806.10758/) (2018)
- [Interpretation of Neural Networks is Fragile](https://mlsanity.com/paper/1710.10547/) (2017)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [The (Un)reliability of saliency methods](https://mlsanity.com/paper/1711.00867/) (2017)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [On the Robustness of Interpretability Methods](https://mlsanity.com/paper/1806.08049/) (2018)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [Opportunities and Challenges in Explainable Artificial Intelligence (XAI): A Survey](https://mlsanity.com/paper/2006.11371/) (2020)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Explanations can be manipulated and geometry is to blame](https://mlsanity.com/paper/1906.07983/) (2019)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Multi-Objective Counterfactual Explanations](https://mlsanity.com/paper/2004.11165/) (2020)
- [Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems](https://mlsanity.com/paper/1907.09615/) (2019)
- [A survey of algorithmic recourse: definitions, formulations, solutions, and prospects](https://mlsanity.com/paper/2010.04050/) (2020)
- [Towards Robust and Reliable Algorithmic Recourse](https://mlsanity.com/paper/2102.13620/) (2021)
- [The Dangers of Post-hoc Interpretability: Unjustified Counterfactual Explanations](https://mlsanity.com/paper/1907.09294/) (2019)
- [If Only We Had Better Counterfactual Explanations: Five Key Deficits to Rectify in the Evaluation of Counterfactual XAI Techniques](https://mlsanity.com/paper/2103.01035/) (2021)
- [Towards falsifiable interpretability research](https://mlsanity.com/paper/2010.12016/) (2020)

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

- [Toward Transparent AI: A Survey on Interpreting the Inner Structures of Deep Neural Networks](https://mlsanity.com/paper/2207.13243/) (2022)
- [OpenXAI: Towards a Transparent Evaluation of Model Explanations](https://mlsanity.com/paper/2206.11104/) (2022)
- [Impossibility Theorems for Feature Attribution](https://mlsanity.com/paper/2212.11870/) (2022)
- [Don't trust your eyes: on the (un)reliability of feature visualizations](https://mlsanity.com/paper/2306.04719/) (2023)
- [SoK: Explainable Machine Learning for Computer Security Applications](https://mlsanity.com/paper/2208.10605/) (2022)
- [RoCourseNet: Distributionally Robust Training of a Prediction Aware Recourse Model](https://mlsanity.com/paper/2206.00700/) (2022)
- [Explainable Contextual Anomaly Detection using Quantile Regression Forests](https://mlsanity.com/paper/2302.11239/) (2023)
- [Feature Responsiveness Scores: Model-Agnostic Explanations for Recourse](https://mlsanity.com/paper/2410.22598/) (2024)
- [Provably Better Explanations with Optimized Aggregation of Feature Attributions](https://mlsanity.com/paper/2406.05090/) (2024)
- [Robust ML Auditing using Prior Knowledge](https://mlsanity.com/paper/2505.04796/) (2025)
- [Do graph neural networks learn traditional jet substructure?](https://mlsanity.com/paper/2211.09912/) (2022)
- [Robust Knowledge Extraction from Large Language Models using Social Choice Theory](https://mlsanity.com/paper/2312.14877/) (2023)
- [Factor Graph-based Interpretable Neural Networks](https://mlsanity.com/paper/2502.14572/) (2025)
- [Informative Post-Hoc Explanations Only Exist for Simple Functions](https://mlsanity.com/paper/2508.11441/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [A Quantitatively Interpretable Model for Alzheimer's Disease Prediction Using Deep Counterfactuals](https://mlsanity.com/paper/2310.03457/) (2023)
- [Fast Fourier Correlation is a Highly Efficient and Accurate Feature Attribution Algorithm from the Perspective of Control Theory and Game Theory](https://mlsanity.com/paper/2504.02016/) (2025)
- [Feature Attribution from First Principles](https://mlsanity.com/paper/2505.24729/) (2025)
- [Comprehensive and Reliable Feature Attribution for Diverse Modalities and Models via Frequency-Domain Insights](https://mlsanity.com/paper/2411.18343/) (2024)
- [We Need Explanation Cards to Connect Explanation Algorithms to the Real World](https://mlsanity.com/paper/2606.16786/) (2026)

## Abstract (arXiv)

Different users of machine learning methods require different explanations, depending on their goals. To make machine learning accountable to society, one important goal is to get actionable options for recourse, which allow an affected user to change the decision f(x) of a machine learning system by making limited changes to its input x. We formalize this by providing a general definition of recourse sensitivity, which needs to be instantiated with a utility function that describes which changes to the decisions are relevant to the user. This definition applies to local attribution methods, which attribute an importance weight to each input feature. It is often argued that such local attributions should be robust, in the sense that a small change in the input x that is being explained, should not cause a large change in the feature weights. However, we prove formally that it is in general impossible for any single attribution method to be both recourse sensitive and robust at the same time. It follows that there must always exist counterexamples to at least one of these properties. We provide such counterexamples for several popular attribution methods, including LIME, SHAP, Integrated Gradients and SmoothGrad. Our results also cover counterfactual explanations, which may be viewed as attributions that describe a perturbation of x. We further discuss possible ways to work around our impossibility result, for instance by allowing the output to consist of sets with multiple attributions, and we provide sufficient conditions for specific classes of continuous functions to be recourse sensitive. Finally, we strengthen our impossibility result for the restricted case where users are only able to change a single attribute of x, by providing an exact characterization of the functions f to which impossibility applies.