Probabilistic Stability Guarantees for Feature Attributions

Helen Jin, Anton Xue, Weiqiu You, Surbhi Goel, and Eric Wong · 2025

Read Probabilistic Stability Guarantees for Feature Attributions by Helen Jin, Anton Xue, Weiqiu You, Surbhi Goel, and Eric Wong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13787.txt.

Introduction

Jin and co-authors work on a trust problem for AI explanations: a feature-importance map is of little use if it changes wildly when the input shifts slightly, in a 2025 paper. Earlier methods that certify stability demanded heavily blurred models and gave weak guarantees.

The team defines a softer notion of stability and offers a simple certification method that works with any explanation technique and few samples. Light smoothing, they show, trades accuracy for stability far more gently than prior work assumed, and they explain why using tools from the analysis of Boolean functions. Tests on image and language tasks support the claims.

Catalog record

CREATORHelen Jin, Anton Xue, Weiqiu You, Surbhi Goel, and Eric Wong
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-13787

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Probabilistic Stability Guarantees for Feature Attributions Helen Jin, Anton Xue, Weiqiu You, Surbhi Goel, and Eric Wong Abstract 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. 1 Introduction Powerful machine learning models are increasingly deployed in practice. However, their opacity presents a major challenge when adopted in high-stakes domains, where transparent explanations are needed in decision-making. In healthcare, for instance, doctors require insights into the diagnostic steps to trust a model and effectively integrate it into clinical practice [ 31 ] . In the legal domain, attorneys must likewise ensure that model-assisted decisions meet stringent judicial standards [ 50 ] . There is much interest in explaining the behavior of complex models. One popular class of explanation methods is feature attributions [ 48 , 37 ] , which aim to select the input features most important to a model’s prediction. However, many explanations are unstable , such as in Figure 1 , where additionally including a few features may change the output. Such instability suggests that the explanation may be unreliable [ 60 , 44 , 67 ] . This phenomenon has motivated efforts to quantify how model predictions vary with explanations, including the effects of adding or removing features [ 63 , 52 ] and the influence of the selection’s shape [ 23 , 51 ] . However, most existing works focus on empirical measures [ 3 ] , with limited formal guarantees of robustness. Original Image Loggerhead Sea Turtle Explanation Loggerhead Sea Turtle ✓ +3 Features Coral Reef ✗ Figure 1: An unstable explanation. Given an input image (left), the LIME explanation method [ 48 ] identifies features (middle, in pink) that preserve Vision Transformer’s [ 17 ] prediction. However, this explanation is not stable: adding just three more features (right, in yellow) flips the predictions. To address this gap, prior work in Xue et al. 2023 considers stability as a formal certification framework for robust explanations. In particular, a hard stable explanation is one where adding any small number of features, up to some maximum tolerance, does not alter the prediction. However, finding this tolerance is non-trivial: for an arbitrary model, one must exhaustively enumerate and check all possible perturbations in a computationally intractable manner. To overcome this, Xue et al. 2023 introduce the MuS algorithmic framework for constructing smoothed models, which have mathematical properties for efficiently and non-trivially lower-bounding the maximum tolerance. While this is a first step towards certifiably robust explanations, it yields conservative guarantees and relies on smoothing. In this work, we introduce soft stability , a new form of stability with mathematical and algorithmic benefits over hard stability. As illustrated in Figure 2 , hard stability certifies whether all small perturbations to an explanation yield the same prediction, whereas soft stability quantifies how often the prediction is maintained. Soft stability may thus be interpreted as a probabilistic relaxation of hard stability, which enables a more fine-grained analysis of explanation robustness. Crucially, this shift in perspective allows for model-agnostic applicability and admits efficient certification algorithms that provide stronger guarantees. This work advances our understanding of robust feature-based explanations, and we summarize our contributions below. Soft Stability is Practical and Certifiable To address the limitations of hard stability, we introduce soft stability as a more practical and informative alternative in Section 2 . Its key metric, the stability rate, provides a fine-grained characterization of robustness across perturbation radii. Unlike hard stability, soft stability yields non-vacuous guarantees even at larger perturbations and enables meaningful comparisons across different explanation methods. Sampling-Based Certificates Achieve Better Stability Guarantees We introduce the Stability Certification Algorithm (SCA) in Section 3 , a simple, model-agnostic, sampling-efficient approach for certifying both hard and soft stability with rigorous statistical guarantees. The key idea is to directly estimate the stability rate, which enables certification for both types of stability. We show in Section 5 that SCA gives stronger certificates than smoothing-based methods like MuS. Mild Smoothing Can Theoretically Improve Stability Although SCA is model-agnostic, we find that mild MuS-style smoothing can improve the stability rate while preserving model accuracy. Unlike with MuS, this improvement does not require significantly sacrificing accuracy for smoothness. To study this behavior, we use Boolean analytic techniques to give a novel characterization of stability under smoothing in Section 4 and empirically validate our findings in Section 5 . 2 Background and Overview Feature attributions are widely used in explainability due to their simplicity and generality, but they are not without drawbacks. In this section, we first give an overview of feature attributions. We then discuss the existing work on hard stability and introduce soft stability. Figure 2: Soft stability offers a fine-grained measure of robustness. For Vision Transformer [ 17 ] , LIME’s explanation [ 48 ] is only hard stable up to radius r\leq 2 . In contrast to hard stability’s binary decision at each r , soft stability uses the stability rate \tau_{r} to quantify the fraction of \leq r -sized perturbations that preserve the prediction, yielding a more fine-grained view of explanation stability. 2.1 Feature Attributions as Explanations Let f:\mathbb{R}^{n}\to\mathbb{R}^{m} be a classifier that maps each input x\in\mathbb{R}^{n} to a vector of m class scores. A feature attribution method assigns an attribution score \alpha_{i}\in\mathbb{R} to each input feature x_{i} that indicates its importance to the prediction f(x) . The notion of importance is method-dependent: in gradient-based methods [ 55 , 58 ] , \alpha_{i} typically denotes the gradient at x_{i} , while in Shapley-based methods [ 37 , 57 ] , it represents the Shapley value of x_{i} . For real-valued attribution scores, it is common to convert them into binary vectors by selecting the top- k highest-scoring features [ 48 , 43 ] . 2.2 Hard Stability and Soft Stability Many evaluation metrics exist for binary-valued feature attributions [ 3 ] . To compare two attributions \alpha,\alpha^{\prime}\in\{0,1\}^{n} , it is common to check whether they induce the same prediction with respect to a given classifier f:\mathbb{R}^{n}\to\mathbb{R}^{m} and input x\in\mathbb{R}^{n} . Let (x\odot\alpha)\in\mathbb{R}^{n} be the \alpha -masked variant of x , where \odot is the coordinate-wise product of two vectors. We write f(x\odot\alpha)\cong f(x\odot\alpha^{\prime}) to mean that the masked inputs x\odot\alpha and x\odot\alpha^{\prime} yield the same prediction under f . This way of evaluating explanations is related to notions of faithfulness, fidelity, and consistency in the explainability literature [ 44 ] , and is commonly used in both vision [ 26 ] and language [ 38 , 66 ] . It is often desirable that two similar attributions yield the same prediction [ 67 ] . While similarity

Read the complete text