# Probabilistic Stability Guarantees for Feature Attributions

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 61 of its 77 references that are in the map.
- First posted on arXiv 18 Apr 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (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)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [Evaluating the visualization of what a Deep Neural Network has learned](https://mlsanity.com/paper/1509.06321/) (2015)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [The (Un)reliability of saliency methods](https://mlsanity.com/paper/1711.00867/) (2017)
- [On the (In)fidelity and Sensitivity for Explanations](https://mlsanity.com/paper/1901.09392/) (2019)
- [From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AI](https://mlsanity.com/paper/2201.08164/) (2022)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Faithful Chain-of-Thought Reasoning](https://mlsanity.com/paper/2301.13379/) (2023)
- [Influence Functions in Deep Learning Are Fragile](https://mlsanity.com/paper/2006.14651/) (2020)
- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [A Diagnostic Study of Explainability Techniques for Text Classification](https://mlsanity.com/paper/2009.13295/) (2020)
- [Towards Faithful Model Explanation in NLP: A Survey](https://mlsanity.com/paper/2209.11326/) (2022)
- [OpenXAI: Towards a Transparent Evaluation of Model Explanations](https://mlsanity.com/paper/2206.11104/) (2022)
- [Benchmarking LLMs via Uncertainty Quantification](https://mlsanity.com/paper/2401.12794/) (2024)
- [Safe Planning in Dynamic Environments using Conformal Prediction](https://mlsanity.com/paper/2210.10254/) (2022)
- [A Consistent and Efficient Evaluation Strategy for Attribution Methods](https://mlsanity.com/paper/2202.00449/) (2022)
- [Do Feature Attribution Methods Correctly Attribute Features?](https://mlsanity.com/paper/2104.14403/) (2021)

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

- [Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations](https://mlsanity.com/paper/2506.08505/) (2025)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Interpretability Can Be Actionable](https://mlsanity.com/paper/2605.11161/) (2026)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [Invisible Attributes, Visible Biases: Exploring Demographic Shortcuts in MRI-based Alzheimer's Disease Classification](https://mlsanity.com/paper/2509.09558/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Missingness Bias Calibration in Feature Attribution Explanations](https://mlsanity.com/paper/2603.04831/) (2026)
- [When LRP Diverges from Leave-One-Out in Transformers](https://mlsanity.com/paper/2510.18810/) (2025)

## Abstract (arXiv)

Stability guarantees have emerged as a principled way to evaluate feature attributions, but existing certification methods rely on heavily smoothed classifiers and often produce conservative guarantees. To address these limitations, we introduce soft stability and propose a simple, model-agnostic, sample-efficient stability certification algorithm (SCA) that yields non-trivial and interpretable guarantees for any attribution method. Moreover, we show that mild smoothing achieves a more favorable trade-off between accuracy and stability, avoiding the aggressive compromises made in prior certification methods. To explain this behavior, we use Boolean function analysis to derive a novel characterization of stability under smoothing. We evaluate SCA on vision and language tasks and demonstrate the effectiveness of soft stability in measuring the robustness of explanation methods.