Probabilistic Stability Guarantees for Feature Attributions
Authors: Helen Jin
Anton Xue
Weiqiu You
Surbhi Goel
Eric Wong
Venue: NeurIPS 2025 poster ()
Keywords: Explainability
Interpretability
Feature Attributions
Safety
Robustness
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We scale certified explanations to provide practical guarantees in high-dimensional settings.

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.

Probabilistic Stability Guarantees for Feature Attributions
Helen Jin" University of Pennsylvania helenjin@seas upenn. edu
Anton Xue University of Texas at Austin anton xuedaustin. uteras. edu
Weiqiu You
Surbhi Goel
Eric Wong
University of Pennsylvania weiqiuyOseas. upenn. edu
University of Pennsylvania supeeeesssuunnn..nen. surbhig@seas upenn edu
University of Pennsylvania exwongSseas. upenn edu
Abstract
Stability guarantees have emerged as a principled way to evaluate feature attri- butions, but existing certification methods rely on heavily smoothed classifiers and often produce conservative guarantees. To address these limitations, we intro- duce soft stability and propose 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 vision and language tasks and demonstrate the effectiveness of soft stability in measuring the robustness of explanation methods.
Introduction
Powerful machine learning models are increasingly deployed in practice. However, their opacity presents major challenge when adopted in high-stakes domains, where transparent explanations needed in decision-making. In healthcare, for instance, doctors require insights into the diagnostic steps trust model and effectively integrate it into clinical practice (32. In the legal domain, attorneys must likewise ensure that model-assisted decisions meet stringent judicial standards (53]
There is much interest in explaining the behavior of complex models. One popular class of explanation methods feature attributions [39 51) which aim to select the input features most important to model's prediction. However, many explanations are unstable, such in Figure []] where additionally including a few features may change the output. Such instability suggests that the explanation may be unreliable [47] 655 [72). This phenomenon has motivated efforts to quantify how model predictions vary with explanations, including the effects of adding or removing features (55] 68 and the influence of the selection's is shape (23 [5]. However, most existing works focus empirical measures [3]. with limited formal guarantees of robustness.
To address this gap. prior work in Xue et al. [70 considers stability as formal certification framework for robust explanations. In particular, hard stable explanation one where adding any small number of features, up to some maximum tolerance, does not alter the prediction. However, finding this tolerance non-trivial: for an arbitrary model, one must exhaustively enumerate and check all possible perturbations in computationally intractable manner. To overcome this, Xue et al. (70) introduce the MuS algorithmic framework for constructing smoothed models, which have mathematical properties
Equal contribution. Code is available at: httpp:://gtchub..c////llele/////
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Original Image
Explanation
+3 Features
Loggerhead Sea Turtle /
Loggerhead Sea Turtle /
Coral Reef x
Figure 1: An unstable explanation. Given an input image (left), the LIME explanation method [51 identifies features (middle, in pink) that preserve Vision Transformer's [77 prediction. However, this explanation not stable: adding just three more features (right, in yellow) flips the predictions.
for efficiently and non-trivially lower-bounding the maximum tolerance. While this is first step towards certifiably robust explanations, yields conservative guarantees and relies on smoothing.
In this work, we introduce soft stabiliry, 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 maintained. Soft stability may thus be interpreted stability, which enables more fine-graines analysis of explanation robustness. Crucially, this shift perspective allows for model-agnostic applicability and admits efficient certification algorithms that provide stronger guarantees. This work advances our understanding of robust feature-bard based explanations, and we summarize our contributions below.
probabilistic relaxation of hard
Soft stability is practical and certifiahle To address the limitations of hard stability, introduce soft stability as a more practical and informative alternative property in Section 2 Its key metric, the stability rate, provides 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 methods achieve better stability guarantees We introduce the Stability Certi- fication Algorithm (SCA) 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 stability. We show Section that SCA gives stronger certificates than smoothing- -ased methods like MuS.
Mild smoothing can theoretically improve stability Although SCA is model-agnostic, we find that mild MuS-style smoothing 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, use Boolean analytic techniques give novel characterization of stability under smoothing in Section and empirically validate our findings in Section
2 Background and Overview
Feature attributions are widely used in explainability due to their simplicity and generality, but they without drawbacks. In this section, first give overview of feature attributions. We then discuss the existing work on hard stability and introduce soft stability.
2.1 Feature Attributions as Explanations
fe R be a classifier that maps each input x Rd vector m class scores. feature attribution method assigns an attribution score E R to each input feature r; that indicates its importance to the prediction (xx) The notion of importance is method-ddependent: gradient- based
methods [59 63 a typically denotes the gradient at while in Shapley-based methods (39 62). it
represents the Shapley value of z;. For real-valued attribution scores, common convert them into binary vectors by selecting the top-k highest-scoring features [46] 51]

---

Radius
2
S-
S
Original
LIME
Explain
Perturb
features
Ciroster Swiss
Prediction match??
Mountain Dog
Average
Hard Stable?
Yos
Yes
No
No
Stability Rates
1.00 1.00
Figure 2: Soft stability offers a fine-grained measure of robustness. For Vision Transformer [7]. LIME's explanation [ST] is only hard stable up radius 2. In contrast to hard stability's binary decision at each r, soft stability uses the stability rate т, to quantify the fraction of I r- sized perturbations that preserve the prediction, yielding more fine-graine' grained view of explanation stability. Note that hard stability (when T, = 1) is form of adversarial robustness tailored for feature attributions.
2.2 Hard Stability and Soft Stability
Many evaluation metries exist for binary-valued feature attributions 3 To compare two attributions a,a' E {0, 1]", it is common to check whether they induce the same prediction with respect to given classifier f : Rn + R and input E R". Let (æ @ a) E RR" be the a-masked variant of x, where @ is the coordinate-win wise product of two vectors. We write f(x O a) _ f( O a') to mean that the masked inputs x @ a and x @ a' yield the same prediction under f. This way of evaluating explanations is related to notions of faithfulness, fidelity, and consistency in the explainability literature 47 and is commonly used in both vision [26] and language 40 7T].
While similarity can be defined various ways, such as overlapping feature sets [47]. we focus on additive perturbations. Given an explanation a, we define additive perturbation a' as one that includes more features than a. This is based on the intuition that adding information (features) to high-quality explanation should not significantly affect the classifier's s prediction.
It is often desirable that two similar attributions yield the same prediction 72
Definition 2.1 (Additive Perturbations). For an attribution a and integer- radius 2 define r-additive perturbation set of a as:
: a' 2 a, la' - sr). (r = {a' E [0,
(1)
where a' 2 iff each of 2 a; and |-| counts the non-zeros binary vector (i.e., the 1 norm).
The binary vectors in (a(a) represent attributions (explanations) that superset by at most features. This lets us study explanation robustness by studying how more inclusive selection of features affects the classifier's prediction. A natural way to formalize this is through stability: an attribution a is stable with respect to and if adding small number of features does not alter (or rarely alters) the prediction. One such formulation of this idea is hard stability.
Definition 2.2 (Hard Stability (70). For classifier f and input x, the explanation a is hard-stable with radius if: f(x d') [(x a.) for all a' E A,.
In essence, hard stability is a form of adversarial robustness tailored for feature attributions. The certification process verifies that explanation is robust against worst-case adversary who adds up to r features to make it fail. Specifically, a has a certified hard stability radius if one can formally prove that all perturbations a' E (,)a) induce the same prediction. While this guarantee is powerful, its certification is not straightforward, as existing algorithms suffer from costly trade-offs that we later discuss in Section 3.1 This practical barrier motivated our development of seft stability: a probabilistic relaxation of hard stability that offers a more tractable yet meaningful way to quantify robustness.
2 Xue
70 equivalently call this "incrementally stable" define "stable" a stricter property.
"Although probabilistic notions of robust explainability have been studied in the literature [22 soft stability stands one-sided notion of robustness.
52
66
67
3

---

Original
LIME
SHAP
T2 = 0.37
T2 = 0.76
Figure 3: Similar explanations may have different stability rates. Despite visual similarities, the explanations generated by LIME [51) (middle) and SHAP (39] (right), both in blue, have different stability rates radius r = 2. In this example, SHAP's explanation is more stable than LIME'S.
Definition 2.3 (Soft Stability). For classifier f and input x, define the stability rate Tr a:) as the probability that the prediction remains unchanged when a is perturbed by up to r features:
Ty (f, x, x) Pr a'rd,
((x
o)); where o' A, is uniformly sampled.
When a, are clear from the context, we will simply write for brevity. An important aspect of soft stability is that it can distinguish between the robustness of two similar explanations. In Figure 3 for example, LIME and SHAP find significantly overlapping explanations that have very different stability rates. We further study the stability rate of different explanation methods in Section
Relation Between Hard and Soft Stability Soft stability is probabilistic relaxation of hard stability, with T,- = recovering the hard stability condition. Conversely, hard stability is valid but coarse lower bound on the stability rate: if T, 1, then the explanation not hard stable at radius r. This relation implies that any certification for one kind of stability can be adapted for the other.
3 Certifying Stability: Challenges and Algorithms
We begin by discussing the limitations of existing hard stability certification methods, particularly those based on smoothing, such as MuS [70]. We then introduce the Stability Certification Algorithm (SCA) in Equation (3). providing simple, model-agnostic, and sample-efficient way certify both hard (Theorem 3.2 and soft (Theorem 3.I stability at all perturbation radii.
3.1 Limitations in (MuS) Smoothing- based Hard Stability Certification
Existing hard stability certifications rely on classifier's Lipschitz constant, which is measure of sensitivity to input perturbations. While the Lipschitz constant is useful for robustness analysis [14] often intractable to compute and difficult to approximate 20
669. To address this, Xue et al. (70) construct smoothed classifiers with analytically known Lipschitz constants. Given
43
64
classifier f. its smoothed variant f defined as the average prediction over perturbed inputs: f(x)
NV - (()(()),, where 21(1) ....,,((N) ((r) perturbations of If D appropriately chosen, then the smoothed classifier f has a known Lipschitz constant x that allows for efficient certification. We review MuS smoothing Definition 4.1 and its hard stability certificates in Theorem C.I
Smoothing has severe performance trade-offs A key limitation of smoothing-based certificates is that the stability guarantees apply to rather than f. Typically, the smoother the classifier, the stronger its guarantees (larger certified radii), but this comes at the cost of accuracy. This because smoothing reduces classifier's sensitivity, making it harder to distinguish between classes 6 25
Smoothing- hard stability is conservative Even when smoothing- certified radius is obtained, it often conservative. The main reason is that this approach depends on global property. the Lipschitz constant K, to make guarantees about local perturbations a' ~ (, In particular, the certified hard stability radius of scales as ((1kk), which claborate in Theorem C.I

---

Walker hound v
Stability Rate Estimate: 0.953
Beagle
Walker bound o
Figure 4: The stability certification algorithm (SCA). Given an explanation a (0, 13" for classifier f and input E IR", we estimate the stability rate as follows. First, sample perturbed masks a' (a( uniformly with replacement. Then, compute the empirical stability rate f,. defined as the fraction of samples that preserve the prediction: f, N Ln O= = f(z@a)]. With properly chosen sample size N, both hard and soft stability can be certified with statistical guarantees.
3.2 Sampling-based Algorithms for Certifying Stability
Our key insight is that both soft and hard stability can be certified by directly estimating the stability rate through sampling. This leads to simple algorithm, illustrated in Figure and formalized below:
1 7, N Σ ()(c0a = f(x where a
(a) are sampled i.idd (3)
The estimator ir provides a statistical approximation of soft stability. With an appropriate sample size N, this estimate yields formal guarantees for both hard and soft stability.
Theorem 3.1 (Certifying Soft Stability with SCA). Let łt be the stability rate estimator defined
in D computed with 2
log(2/5) for any confidence parameter ô > 0 and error tolerance
2x
Then, with probability at least 5, the estimator satisfies f Trl S
Proof. The result follows by applying Hoeffding's inequality to the empirical mean of independent Bernoulli random variables x (()),,..,,,,N)) where each (0) 1[f(x O (i)) = f(x @ a)]. O
SCA also certify hard stability by noting that f, implies high-confidence guarantee. Theorem 3.2 (Certifying Hard Stability with SCA). Let fr be the stability rate estimator defined log(5) in Equation 3). computed with sample size N 2 [- for any confidence parameter ô > and ervor tolerance & > 0. i, 1, then with probability at least a' (a) violates hard stability with probability most
a uniformly sampled
Proof. We bound the probability of the worst-case event, where the explanation is not hard stable at radius r, meaning T, < 1- E, yet the estimator satisfies fr 1. Because each a Ap is uniformly sampled, this event occurs with probability
Pr
5 (1- 88
which holds whenever > log(5)/ log(1 8).
In both hard and soft stability certification, the required sample size N depends only and 5, as T, is a one-dimensional statistic. Notably, certifying hard stability requires fewer samples, since the event being verified is simpler. In both settings, SCA provides simple alternative to MuS that does not require smoothing.
Implementing SCA The main computational challenge is in sampling a' (a) uniformly. When r S n jal, this may be done by: (1) sampling a perturbation size ~ 10. .r with probability ("= (a)),, where [a) = E ("-lel); and then (2) uniformly selecting k zero positions in flip to one. To avoid numerical instability from large binomial coefficients, we Gumbel softmax reparametrization 227 to sample in the log probability space.
5

---

4 Theoretical Link Between Stability and Smoothing
While SCA does require smoothing to certify stability, find that applying mild MuS-style smoothing can improve the stability rate while incurring only a minor accuracy trade-off. While this improvement unsurprising, it is notable that the underlying smoothing mechanism is discrete. In contrast, most prior work relies on continuous noise distributions [14]. Below, we introduce this discrete smoothing method, MuS, wherein the main idea is promote robustness feature inclusion and exclusion by averaging predictions over randomly masked (dropped) inputs.
Definition 4.1 (Musf (Random Masking)). For any classifier f and smoothing parameter À [0, define the random masking operator Mx as:
Mxf(x)= z~
E f(r O 2). where 21, 21........ Bern (A) are i.ddd samples.
(4)
Here, Mf is the smoothed classifier, where each feature is kept with probability A. A smaller implies stronger smoothing: at À = we have f = f: at À = 1/2. half the features of x C 2 are dropped on average; at = 0. f reduces to constant classifier. We summarize our main results in Section 4.1 with details in Section 4.2 and extended discussions in Appendix Appendix
4.1 Summary of Theoretical Results
Our main theoretical tooling is Boolean function analysis 448. which studies real-valued functions of Boolean-valus inputs. To connect this with evaluating explanations: for any classifier f IR" - R and input x E R", define the masked evaluation (=(a) = f(x O a). Such fa : {0. 1 + R m is then Boolean function, for which the random masking (MuS) operator Mx is well-defined because fx o a) (a)) To simplify our analysis, we consider a simpler form of prediction agreement for classifiers of the form fx {0, 13" - R. where for a' ~ (a)a) let:
fa(a') fa if (fa(d') - (a)) S
(5)
where y is the distance to the decision boundary. F This setup can be derived from general m-class classifier once the x and a are given. In summary, we establish the following.
Theorem 4.2 (Smoothed Stability, Informal of Theorem B.4). Smoothing improves the lower bound on the stability rate by shrinking its gap to 1 by a factor of X. Consider any classifier fw and attribution a that satisfy Equation (5). and let Q depend the monotone weights of fa, then:
1 - 7 < (T(,aa)) = 1- XQ I (M.
Q
7
Theoretically, smoothing improves the worst-case stability rate by factor of X. Empirically, we observe that smoothed classifiers tend to be more stable. Interestingly, we found it challenging to bound the stability rate of MM -soothedd classifiers using standard Boolean analytic techniques, such those in widely used references like [48]. This motivated us to develop novel analytic tooling to study stability under smoothing, which we discuss next.
4.2 Challenges with Standard Boolean Analytic Tooling and New Techniques
It is standard to study Boolean functions via their Fourier expansion. For any h: (0. 1)" + R, its Fourier expansion exists uniquely as a linear combination over the subsets of [n] = [1.....n]:
h(a)=
Σ h(S)xs(a).
SCiM]
where each (a) is Fourier basis function with weight Tr(S), respectively defined as:
1
(s II (-)%% xo(a)= 1, T((S)
Σ h(a)xs(a).
(8)
2n
SES
a
'We use the terms MuS, random masking, smoothing, and MA interchangeably. depending on the context.
'In the special case where the model outputs a sorted probability vector with P1 2 P2 2 ... 2 Pm. we let = (pi P2)/2. This is half the gap between the top two classes, which ensures that even if pa decreases by it remains the highest class.

---

The Fourier expansion makes all the k = 0, ........ degree (order) interactions between input bits explicit. For example, the AND function h(a,, a2) ai A 02 is uniquely expressible as:
1 Man, 02) xe(e))) -
1 x())(a) + 1 (x(12)(0).
To study how linear operators on Boolean functions, it is common isolate their effect on each term. With respect to the standard Fourier basis, the operator M, acts as follows.
Theorem 4.3. For any standard basis function Xs and smoothing parameter [0, 1].
MAxs(a)= = Σ (1 (1((1-1)15-2
(10)
ICS
For any any function h: [0, 11th - I, its smoothed variant Myh has the Fourier expansion
Mah(a)= = Σ Mah(T)xr(a), where Mah(T) = X T
Σ 92F
(1-A))
(11)
TChn
This result shows that smoothing redistributes weights from each term S down all of its subsets T S S, scaled by a binomial decay Bin([S), A). However, this behavior introduces significant complexity in the algebraic manipulations and is distinct from that of other operators commonly studied in literature, making it difficult to analyze stability with existing techniques.
Although one could, in principle, study stability using the standard basis, we found that the monotone basis was better suited to describing the inclusion and exclusion of features. While this basis is also known in game theory as unanimity functions, its use in analyzing stability and smoothing is novel.
Definition 4.4 (Monotone Basis), For each subset T S [nx]. define its monotone basis function as:
{ 0 otherwise (any feature of T is absent).
if a; = 1 for all i E (all features of T are present),
(a)
(12)
The monotone basis provides a direct encoding of set inclusion, where the example of conjunction is now concisely represented as 1112) (01, (x2) = on Q2. Similar to the standard basis, the monotone basis also admits unique monotone expansion for any function h : {0, 13" -+ and takes the form:
h(a) Σ ((T)L(()), where k(T) h(T) Σ T(S), SCT
T((0) h(..,, (13)
TCMa
where T(T)) are the recursively defined monotone weights at each T S [n]. with l(T) being the evaluation of h on the natural {0, vvaluud representation T. A key property the monotone basis is that the action of MA is now point- contraction at each T. Theorem 4.5. For any function : {0, 1) + I, subset C [n]] and À E [0, 11. the smoothed classifier experiences spectral contruction of
M = XTT
(14)
where MT) and h(T) are the monotone basis coefficients of Myh and h at subset T, respectively.
smoothing in the monotone basis exponentially decays each weight by a factor of A!TI, which better aligns with the motifs of existing techniques. b As previewed in Theorem 4.2 the stability rate of smoothed classifiers can be bounded via the monotone weights of degree S r, which we further discuss in Appendix B
In contrast to smoothing in the standard basis (Theorem 4.3)
5 Experiments
We evaluate the advantages of SCA over MuS, which is currently the only other stability certification algorithm. We also study how stability guarantees vary across vision and language tasks, as well across explanation methods. Moreover, for Definition[4. 4. often improves stability while preserving accuracy. We summarize our key findings here and defer full technical details and additional experiments Appendix C
show that mild smoothing, defined as À > 0.5
'The standard smoothing operator is random flipping: let Tph(()) Eg- [La[a z) mod for any p E [0, 1] and q (1 p)/2. Then, the standard Fourier basis contracts T2xs(a) || xs(().
7

---

1.00
1.00
1.00
Stailityy Rate
Stabiltty Rata
9.75
6.75
Sability Rate
0.50
0250
1-0.125
0.250
Stbilitu
0.50
0250
0.125
0.20
0.375
1 0.375
0.375
A 0.375
0.25
0.500
0.25
0.500
0.500
9.25
A D.500
0.00
3
3.00
2
0.00
0.00
(VIT LeME) Pert Badkus
(Resteet5 LIME Pert Radius
(Resker18 LIME Port Radius
[RodeRTs LIME) Pert Radius
SCA certifies more than MuS. Soft stability certificates obtained through SCA are stronger than those obtained from MuS, which quickly become vacuous as the perturbation size grows. When using MuS with smoothing parameter X, guarantees only exist for perturbation radii I 1/22. Moreover, the smaller the X, the worse the smoothed classifier accuracy, see Figure
Figure 5:
UIEE
1.00
UIME
3.00
LIME
LIME
Sbabiity mate
SHAP Intrred
0.75
SHAP
Smblihty Ratt
SHAP
Stakin gaabiity Bate
Inttrad
SHAP
6.6
babllty
NFABA
0.4
0.25
0.25
6.2
25
5.0
75
1.00
50
23
10 15
20
(VTT) Pert Radius
(RoBEHTTa) Pert Radius
Figure 6: Soft stability varies across explanation methods. For vision models, LIME and SHAP yield higher stability rates than gradient-basee methods, with all methods outperforming the random baseline. On RoBERTa, however, the methods are less distinguishable. Note that perturbation of size 100 affects over half the features in a patched image input with n = 196 features.
Experimental Setup We used Vision Transformer (VIT) 17 and ResNet50/18 [24] as our vision models and RoBERTa (38 as our language model. For datasets, we used 2000-image subset of ImageNet (2 images per class) and six subsets of TweetEval (emoji, emotion, hate, irony, offensive, sentiment), totaling 10653 samples. Images of size 3 x 224 x 224 were segmented into 16 x 16 patches, for n = 196 features per image. For text, each token was treated as one feature. We used five feature attribution methods: LIME [5T], SHAP (39), Integrated Gradients 663 MFABA (75]. and a random baseline. We selected the top-25% of features as the explanation.
Question I: How do SCA's guarantees compare to those from MuS? We begin by comparing the SCA-based stability guarantees to those from MuS. To facilitate comparison, we derive stability rates for MuS-based hard stability certificates (Theorem C.T using the following formulation:
Stability rate at radius r [xx, a) CertifiedRadius/ (Ma,,, 2 r
(15)
Total number of xz'
In Figure 5] present results for LIME across different MuS smoothing parameters X, along with the SCA-based soft (Theorem 3. and hard (Theorem 3.2) stability certificates. SCA yields non- trivial guarantees beyond a radius of 1/2X. smaller À improves MuS guarantees but significantly degrades accuracy (see Figure 8 resulting in certificates for less accurate classifiers. Section Appendix presents an extended comparison of SCA and MuS over various explanations, where we observe similar trends.
larger perturbation radii, whereas MuS-based certificates become vacuous
Question 2: How does stability vary across explanation methods? We next show in Figure how the SCA-certified stability rate varies across different explanation methods. Soft stability can effectively distinguish between explanation methods in vision, with LIME and SHAP yielding the highest stability rates. However, this distinction is less clear for RoBERTa and for MuS- hard stability certificates, further studied in Appendix C33 Furthermore, we show ablations on the top-k feature selection in Appendix C.4
Question 3: How well does mild smoothing (A > 0.5) improve stability? We next empirically study the relation between stability and mild smoothing, for which À 2 0.5 is too large to obtain hard stability certificates. We show in Figure the stability rate at different X, where we used 32 Bernoulli samples to compute smoothing (Definition|44)
We used 200 samples from our subset of ImageNet and 200 samples from vvl that had at least 40 tokens, and random attribution to select 25%

---

1.0
Aw2.
Stabiing RaRe
1-28
Stabilty Raae
0.8
1.0
0.5
2:10
Stabliy Rae
3.0
66.6
0.
0.6-
0.8
0.7
0.4
32
20
16 (ResNet50) Port Rodius
5
12
20
12 20
12
16
20
(VT)) Port Rodius
|Restiet 51 Port Radius
(RoBERT)) Port Radius
Figure 7: Mild smoothing (A 2 0.5) improve stability. For vision, this is most prominent for
ResNet50 and ResNet18. While transformers also benefit, RoBERTa improves more than ViT.
6.8
0.6
Accurasy
0.6
Accurecy
0.5
0.334
Accuracy
0.225
0.593
Accuracy
0.7
0.4
0.088
0.069
0.6
0.790
0.753
0.612
0.2
0.657
0.347
0,482
6.0
(ResNet50)
[ResNet18)
(RoBERTa)
Figure 8: Mild smoothing (A 0.5) preserves accuracy. We report accuracy three key smoothing levels: (A = 1.0, in green) the original, unsmoothed classifier; (A = 0.5, in orange) a mildly smoothed classifier, the largest for which hard stability certificates can be obtained; (A 0.25, in red) heavily smoothed classifier, where MuS can only certify at most perturbation radius of size 2.
of the features. We see that smoothing generally improves stability, and we study setups with larger perturbation radii Appendix C.5
Question 4: How well do mildly smoothed classifiers trade off' accuracy? We analyze the impact of MuS smoothing on classifier accuracy in Figure g and highlight three key values: the original, unmodified classifier accuracy (A 1.0), the largest smoothing parameter usable in the certification of hard stability (A 0.5), and the smoothing parameter used in many hard stability experiments of [70] (A 0.25). We used 64 Bernoulli samples to compute smoothing (Definition 4.1 These results demonstrate the utility of mild smoothing. In particular, transformers (ViT, RoBERTa) exhibit more gradual decline in accuracy, likely because their training involves random masking.
Related Work
Feature-based Explanations Feature attributions are popular class of explanation methods. Early
examples include gradient saliency [59], LIME (5T), SHAP [39], Integrated Gradients [63], and
SmoothGrad [61]. More recent works include DIME 42 LAFA (73), CAFE [15]. DoRaR [50], various Shapley value-based methods 62). and methods based on influence func-
MEABA 775
tions 10
33
While feature attributions
commonly associated with vision models, they
also used in language [41] and time series modeling 566 However, they have known limita-
tions [1
18
44
60). We refer to 47 58
for general surveys, to 33 49 for surveys
explainability in medicine, and to for surveys on explainability in law.
Evaluating and Certifying Explanations There is much work on empirically evaluating feature
attributions [I-
28 31
47
54 74), with various notions of robustness [2 22).. Probabilistic
notions of robust explainability are explored in [12 52 66 67), though stability is notable in that is a form of one-sided robustness. There is also growing interest in certified explanations. For instance, certifying that an explanation is robust to adding (70] and removing [36] features, that
minimal 99 [2], or that the attribution scores are robustly ranked 22 A related notion of
probabilistic guarantees exists for analyzing the explanation method itself 30 which quantifies how
much the feature attribution changes the input perturbed. However, the literature on certified explanations is still emergent.

---

7 Discussion
Many perturbations relevant to explainability are inherently discrete, such as feature removal or token substitution. This contrasts with continuous perturbations, e.g., Gaussian noise, which more commonly studied in adversarial robustness literature. This motivates the development of new techniques for discrete robustness, such those inspired by Boolean analysis. In our case, this approach enabled us to shift away from traditional Lipschitz-based techniques to provide an alternative analysis of robustness. Our work highlights the potential of discrete methods in explainability.
Our stability framework generalizes adversarial robustness. Hard stability, the case where T, = 1, is certified robustness against an adversary adding up to features. However, this discrete, structural attack model differs from the continuous fy-norm perturbations common in adversarial robustness. Soft stability offers more nuanced evaluation, where the stability rate т, quantifies explanation's success under random additive attacks, providing a richer characterization of its robustness. Thus, in this view, stability itself can be interpreted as form of adversarial robustness. If an explanation achieves a stability rate of 1 at some radius, it is adversarially robust up to that perturbation radius. Consequently, high stability rates, ideally 1, are desirable indicators of robust explanations.
Conclusion
Soft stability is form of stability that enables fine- one-grained measures of explanation robustness to additive perturbations. We introduce SCA to certify stability and show that it yields stronger guarantees than existing smoothing- require smoothing, mild smoothing improve stability at little cost to accuracy, and we use Boolean analytic tooling to explain this phenomenon. We validate our findings with experiments on vision and language models across range of explanation methods.
certifications, such as MuS. Although SCA does not
Potential directions include adaptive smoothing based on feature importance and ranking 22 as well as selectively smoothing only parts of the features [57]. One could also study training in relation to adversarial training. Other directions include robust explanations through other families of probabilistic guarantees, such as those based on conformal prediction [5] g 13] 35
Additionally, it would be interesting to investigate how well explanation stability aligns with human evaluations of quality.
Acknowledgements This research was partially supported by the ARPA-H program on Safe and Explainable Al under the grant D24AC00253-00, by NSF award CCF 2313010, by the AI2050 pro- gram at Schmidt Sciences, by an Amazon Research Award Fall 2023, by an OpenAï SuperAlignment grant, and Defense Advanced Research Projects Agency's (DARPA) SciFy program (Agreement No. HR0011 12520300). The views expressed are those of the author and do not reflect the official policy or position the Department of Defense or the U.S. Government.
References
[1] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances in Neural Information Processing Systems, 31, 2018.
[2] Julius Adebayo, Michael Muelly, Harold Abelson, and Been Kim. Post hoc explanations may be ineffective for detecting unknown spurious correlation. In International Conference on Learning Representationss, 2022.
[3] Chirag Agarwal, Satyapriya Krishna, Eshika Saxena, Martin Pawelczyk, Nari Johnson, Isha Puri, Marinka Zitnik, and Himabindu Lakkaraju. Openxai: Towards transparent evaluation of model explanations. Advances in Neural Information Processing Systems, 35, 2022.
[4] Kasun Amarasinghe, Kit T Rodolfa, Hemank Lamba, and Rayid Ghani. Explainable machine learning for public policy: Use cases, gaps, and research directions. Data & Policy, 2023.
[5] Anastasios N Angelopoulos, Stephen Bates, al. Conformal prediction: A gentle introduction. Foundations and Trends@ in Machine Learning, 16, 2023.
10

---

[6] Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In International Conference on Machine Learning. PMLR, 2019.
[7] Staffan Arvidsson McShane, Ulf Norinder, Jonathan Alvarsson, Ernst Ahlberg, Lars Carlsson, and Ola Spjuth. Cpsign: conformal prediction for cheminformatics modeling. Journal of Cheminformatics, 16, 2024.
[8] Pepa Atanasova. diagnostic study of explainability techniques for text classification. In Accountable and Explainable Methods for Complex Reasoning over Text. Springer, 2024.
[9] Shahaf Bassan and Guy Katz. Towards formal xai: formally approximate minimal explanations of neural networks. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 2023.
[10] Samyadeep Basu, Philip Pope. and Soheil Feizi. Influence functions in deep learning are fragile. arXiv preprint urXiv:2006. 14651, 2020.
[11] Blair Bilodeau, Natasha Jaques, Pang Wei Koh, and Been Kim. Impossibility theorems for feature attribution. Proceedings of the National Academy of Sciences, 121, 2024.
[12] Guy Blanc, Jane Lange, and Li- Yang Tan. Provably efficient, succinet, and precise explanations. Advances Neural Information Processing Systems, 34, 2021.
[13] Diogo V Carvalho, Eduardo M Pereira, and Jaime S Cardoso. Machine learning interpretabilliy:: A survey on methods and metrics. Electronics, 8, 2019.
[14] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning. PMLR, 2019.
[15] Adam Dejl, Hamed Ayoobi. Matthew Williams, and Francesca Toni. Cafe: Conflict-aware feature-wise explanations. arXiv preprint arXiv:2310.20366 2023.
[16] Jonathan Dinu, Jeffrey Bigham, and Zico Kolter. Challenging common interpretability assumptions in feature attribution explanations. arXiv preprint arXiv:2012..2778. 2020.
[17] Alexey Dosovitskiy. An image worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11
2020.
[18] Jiarui Duan, Haoling Li, Haofei Zhang, Hao Jiang, Mengqi Xue, Li Sun, Mingli Song, and Jie Song. On the evaluation consistency attribution- explanations. In European Conference on Computer Vision. Springer, 2024.
[19] Jamil Fayyad, Shadi Alijani, and Homayoun Najjaran. Empirical validation of conformal prediction for trustworthy skin lesions classification. Computer Methods and Programs in Biomedicine, 2024.
[20] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[21] Yuyou Gan, Yuhao Mao, Xuhong Zhang, Shouling Ji, Yuwen Pu, Meng Han, Jianwei Yin, and Ting Wang. "is your explanation stable?" robustness evaluation framework for feature attribu- tion. In Proceedings of the 2022 ACM SIGSAC Conference Computer and Communications Security, 2022.
[22] Jeremy Goldwasser and Giles Hooker. Provably stable feature rankings with shap and lime. arXiv preprint arXiv:2401.158800 2024.
[23] Peter Hase, Harry Xie, and Mohit Bansal. The out-of-distributis problem in explainability and search methods for feature importance explanations. Advances in Neural Information Processing Systems, 34, 2021.
[24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
11

---

[25] Todd Huster, Cho- Yu Jason Chiang, and Ritu Chadha. Limitations of the lipschitz constant as a defense against adversarial examples. In ECML PKDD 2018 Workshops: Nemesis 2018, UrbReas 2018, SoGood 2018, !WAISe 2018, and Green Data Mining 2018. Springer, 2019.
[26] Saachi Jain, Hadi Salman, Eric Wong, Pengchuan Zhang, Vibhav Vineet, Sai Vemprala, and Aleksander Madry. Missingness bias in model debugging. In International Conference on Learning Representations, 2022.
[27] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with cumbel-softmax arXiv preprint arXiv: 1.01 144, 2016.
[28] Helen Jin, Shreya Havaldar, Chachyeon Kim, Anton Xue. Weiqiu You, Helen Qu, Marco Gatti, Daniel Hashimoto, Bhuvnesh Jain, Amin Madani, Masao Sako, Lyle Ungar, and Erie Wong. The fix benchmark: Extracting features interpretable to experts. arXiv preprint arXiv:2409. 1364, 2024.
[29] Sandesh Kamath, Sankalp Mittal, Amit Deshpande, and Vineeth N Balasubramanian, Rethink- ing robustness of model attributions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, 2024.
[30] Zulqarmain Q Khan, Davin Hill, Aria Masoomi, Joshua Bone, and Jennifer Dy. Analyzing explainer robustness via probabilistic lipschitzness of prediction functions. In International Conference on Artificial Intelligence and Statistics. PMLR, 2024.
[31] Pieter-Jan Kindermans, Sara Hooker, Julius Adebayo, Maximilian Alber, Kristof T Schütt, Sven Dähne, Dumitru Erhan, and Been Kim. The (un) reliability of saliency methods. In Explainable AI: Interpreting, Explaining and Visualizing Deep Learning. Springer, 2019.
[32] Frederick Klauschen, Jonas Dippel, Philipp Keyl, Philipp Jurmeister, Michael Bockmayr, Andreas Mock, Oliver Buchstab, Maximilian Alber, Lukas Ruff, Grégoire Montavon, et al. Toward explainable artificial intelligence for precision pathology. Annual Review of Pathology: Mechanisms of Disease, 19, 2024.
[33] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning. PMLR, 2017.
[34] Alexander J Levine and Soheil Feizi. Improved, deterministic smoothing for 11 certified robustness. In International Conference on Machine Learning. PMLR, 2021.
[35] Shuo Li, Xiayan Ji, Edgar Dobriban, Oleg Sokolsky, and Insup Lee. Pac-wrap: Semi-supervised pac anomaly detection. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
[36] Chris Lin, Ian Covert, and Su-In Lee. On the robustness of removal- based feature attributions. Advances in Neural Information Processing Systems, 36, 2024.
[37] Lars Lindemann, Matthew Cleaveland, Gihyun Shim, and George Pappas. Safe planning in dynamic environments using conformal prediction. IEEE Roboties and Automation Letters, 2023.
[38] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 1907. 1692, 2019.
[39] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017.
[40] Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang, Delip Rao, Eric Wong, Mariannaa Apidianaki, and Chris Hallison-Burch Faithful chain-of-thouge reasoning. Proceedings of the 13th International Joint Conference on Natural Language Processing and the 3rd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics ( (Volume I: Long Papers), 2023.
12

---

[41] Qing Lyu, Mariannaa Apidianaki, and Chris Callison-Burch. Towards faithful model explanation nlp: A survey. Computational Linguistics, 50, 2024.
[42] Yiwei Lyu, Paul Pu Liang, Zihao Deng, Ruslan Salakhutdinov, and Louis-Philippe Morency. Dime: Fine-grained interpretations of multimodal models via disentangled local explanations. In Proceedings of the 2022 AAAI/ACM Conference on AI, Ethics, and Society, 2022.
[43] Ravi Mangal, Kartik Sarangmath, Aditya V Nori, and Alessandro Orso. Probabilistic lipschitz analysis of neural networks. In International Static Analysis Symposium. Springer, 2020.
[44] Reda Marzouk, Shahaf Bassan, Guy Katz, and Colin de la Higuera. On the computational tractability of the (many) shapley values. arXiv preprini arXiv:2502. 12295, 2025.
[45] Stephanie Milani, Nicholay Topin, Manuela Veloso, and Fei Fang. Explainable reinforcement learning: A survey and comparative review. ACM Computing Surveys, 56, 2024.
[46] Tim Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial intelligence, 267, 2019.
[47] Meike Nauta, Jan Trienes, Shreyasi Pathak, Elisa Nguyen, Michelle Peters, Yasmin Schmitt, Jörg Schlötterer, Maurice Van Keulen, and Christin Seifert. From anecdotal evidence to quantitative evaluation methods: A systematic review on evaluating explainable ai. ACM Computing Surveys, 55, 2023.
[48] Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
[49] Cristiano Patrício, João C Neves, and Lufs F Teixeira. Explainable deep learning methods in medical image classification: A survey. ACM Computing Surveys, 56, 2023.
[50] Dong Qin, George Amariucai, Daji Qiao, Yong Guan, and Shen Fu. A comprehensive and reliable feature attribution method: Double-sided remove and reconstruct (dorar). Neural Networks, 173, 2024.
[51] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. why should trust you?" explaining the predictions of any classifier. Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, 2016.
[52] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model- agnostic explanations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[53] Karen McGregor Richmond, Satya M Muddamsetty, Thomas Gammeltoft- Hansen, Hen- rik Palmer Olsen, and Thomas Moeslund. Explainable ai and law: an evidential survey. Digital Society, 3, 2024.
[54] Yao Rong, Tobias Leemann, Vadim Borisov, Gjergji Kasneci, and Enkelejda Kasneci. A consistent and efficient evaluation strategy for attribution methods. In International Conference on Machine Learning. PMLR, 2022.
[55] Wojeiech Samek, Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, and Klaus- Robert Müller. Evaluating the visualization of what a deep neural network has learned. IEEE Transactions on Neural Networks and Learning Systems, 28, 2016.
[56] Udo Schlegel, Hiba Arnout, Mennatallah El-Assady, Daniela Oelke, and Daniel A Keim. Towards rigorous evaluation of xai methods on time series. 2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW). IEEE, 2019.
[57] Yan Scholten, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Hierarchical randomized smoothing. Advances in Neural Information Processing Systems, 36, 2023.
[58] Gesina Schwalbe and Bettina Finzel. A comprehensive taxonomy for explainable artificial intelligence: a systematic survey of surveys on methods and concepts. Data Mining and Knowledge Discovery, 38, 2024.
13

---

[59] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034, 2013.
[60] Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, 2020.
[61]
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smooth- grad: removing noise by adding noise. arXiv preprint
2017.
[62] Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In International Conference on Machine Learning. PMLR, 2020.
[63] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks, In International Conference on Machine Learning. PMLR, 2017.
[64] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
[65] Jorg Wagner, Jan Mathias Kohler, Tobias Gindele, Leon Hetzel, Jakob Thaddaus Wiedemer, and Sven Behnke. Interpretable and fine fine-grained visual explanations for convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2019.
[66] Stephan Wäldchen, Jan Macdonald, Sascha Hauch, and Gitta Kutyniok. The computational complexity of understanding binary classifier decisions. Journal of Artificial Intelligence Research, 70, 2021.
[67] Eric Wang, Pasha Khosravi, and Guy Van den Broeck. Probabilistic sufficient explanations. arXiv preprint 2rXiv:2105.10111 2021.
[68] Weibin Wu, Yuxin Su, Xixian Chen, Shenglin Zhao, Irwin King, Michael R Lyu, and Yu-Wing Wing Tai. Towards global explanations of convolutional neural networks with concept attribution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020.
[69] Anton Xue, Lars Lindemann, Alexander Robey, Hamed Hassani, George J Pappas, and Rajeev Alur. Chordal sparsity for lipschitz constant estimation of deep neural networks. In 2022 IEEE 6lst Conference on Decision and Control (CDC). IEEE, 2022.
[70] Anton Xue, Rajeev Alur, and Eric Wong. Stability guarantees for feature attributions with multiplicative smoothing. Advances in Neural Information Processing Systems, 36, 2023.
[71] Fanghua Ye, Mingming Yang, Jianhui Pang, Longyue Wang, Derek F Wong, Emine Yilmaz, Shuming Shi, and Zhaopeng Tu. Benchmarking Ilms via uncertainty quantification. arXiv preprint arXiv:2401. 12794, 2024.
[72] Chih-Kuan Yeh, Cheng- Yu Hsieh, Arun Suggala, David I Inouye, and Pradeep K Ravikumar. On the (in) fidelity and sensitivity of explanations. Advances in Neural Information Processing Systems, 32, 2019.
[73] Sheng Zhang, Jin Wang, Haitao Jiang, and Rui Song. Locally aggregated feature attribution on natural language model understanding. arXiv preprint arXiv:2204. 02022204..08000 10893, 2022.
[74] Yilun Zhou, Serena Booth, Marco Tulio Ribeiro, and Julie Shah. Do feature attribution methods correctly attribute features? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, 2022.
[75] Zhiyu Zhu, Huaming Chen, Jiayu Zhang, Xinyi Wang, Zhibo Jin, Minhui Xue, Dongxiao Zhu, and KwnnK Raymond Choo. Mfaba: A more faithful and accelcrated boundary- based attribution method for deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, 2024.
14

---

A Analysis of Smoothing with Standard Techniques
In this appendix, we analyze the smoothing operator M, using classical tools from Boolean function analysis. Specifically, we study how smoothing redistributes the spectral mass of function by examining its action on standard Fourier basis functions. This sets up the foundation for our later motivation to introduce more natural basis in Appendix B First, recall the definition of the random masking-based smoothing operator.
Definition A.1 (MuS 70 (Random Masking)). For any classifier f R" R and smoothing
parameter À E [0, IJ. define the random masking operator Mx as:
Maf (x) = E
f(x O z). where 21..... Zn ~ (ern(A) are i.dd. samples.
(16)
a~Berr(A)
To study MA via Boolean function analysis, fix the input R" and view the masked classifier f2(0) = f(x @ o.) as a Boolean function fa {0, 1) + R In particular, we have the following:
Maf(r = Mafa(a) = Mafxoa
(17)
This relation is useful from explainability perspective because it means that features not selected by a (the x, where a; = 0) will not be seen by the classifier. other words, this prevents a form of information leakage when evaluating the informativeness of a feature selection.
A.1 Background on Boolean Function Analysis
key approach in Boolean function analysis is to study functions of the form h :0. R by their unique Fourier expansion. This is linear combination indexed by the subsets S C [n] of form:
M(x)) = Σ (S))xs())
(18)
SCiM
where each Xs(a) is a Fourier basis function, also called the standard basis function, with weight T(S)). These quantities are respectively defined as:
xs(a)= = (-1)%, Xa(a) = =1, T((S) 2n aE(0,1)
Σ Ma))s((a).
(19)
iES
The functions xs (0,1)* [11] form an orthonormal basis on (0, 13"h n in the sense that:
1
Σ xs(a)xı(a) = { if aE(0,1)
if (20)
(Xs.XT) = an~Ber(11/2"
[xs(a)xr(a)] = 2n
Consequently, all of the 2n weights T((S) (one for each S C [n]) uniquely determined by the 2n values of (((()) (one for each a E {0, 13a) under the linear relation T((S) = Xs) as
in Equation (9).. For example, one check that the function h(a1,az) a1 ag is uniquely expressible in this basis as:
h(a1, 4 xe(a) x(i)(a) (a)(a) (()a)(a).
(21)
We defer to O'Donnell
[48 for more comprehensive introduction to Boolean function analysis.
A.2 Basic Results in the Standard Basis
We now study how smoothing affects stability by analyzing how M,, transforms Boolean functions in the standard Fourier basis. A common approach is to examine how MM acts on each basis function Xs. and we show that smoothing causes a spectral mass shift from higher-order lower-order terms.
Lemma A.2. For any standard basis function xss and X [0, 1].
Mxxs(a) Σ X
1) xT(a).
(22)
TCS
15

---

Proof. We first expand the definition of xs(a) to derive:
Maxs(a)= = E
II (-1)a
(23)
iES
E (-1)
(by independence of 21,...y kn)
iES
(1 X) + X(-1)''
(24)
IE
We then use the distributive property (i.e., expanding products over sums) to rewrite the product I. as a summation over T' C to get
(II
Maxs(a)
Σ
II (1 x)
(25)
TES
(jES-T
VET
Σ
(1 A) A-II-TI xT(a),
(26)
rCs
where T acts like enumeration over (0, 1)" and recall that xr(o) IIE)((a)
In other words, M2 redistributes the Fourier weight at each basis over to the 2| subsets T C S according to binomial distribution Bin A). Since this redistribution is linear in the input, we can visualize M,, 2="x"" upper ppperutringglar matrix whose entries are indexed by T, S C [n]] where
{ A x) if C S,
(Ma)T,s
(27)
otherwise.
Using the example of h(a1,
(2) = a1 A a2, the Fourier coefficients of M,h may be written as:
Mx)(0)
(1 (1-A) (1 A)
(1 X)2
T:(0)
(2 2)2
MAh((1))
X(1 A)
h((11)
- A(2 A)
Mx)((2)
X(1 A)
(((())
=
A(2 A)
(28)
MAR((1,2H)
X2
((((
X2
where recall that h(SS) 1/4 for all S C (1, For visualization, it is useful to sort the rows and columns of M2 by inclusion and partition them by degree. Below is an illustrative expansion of MA E 88x8 for = 3, sorted by inclusion and partitioned by degree:
0
{1}
(2]
{3)
{1,2}
f1.3}
{2.3}
{1,2,3) 37
0
1
(1
A)
(1 A)
(1 A)
1)2
(1-
(1- A)2
2)3
11
X
A(1 - A)
A(1 A(--1) 1)
A(1 - 2)
(2
A(1 - A)
A(1 - X)
A(1 - 2)2
(3)
A(1 - A)
X(1 A)
X(1 2)2
(1,2)
x
X A
(1.3)
X
A A)
2,3)
X
A2 A) X
1, 1,2,3
(29)
Because the columns of MA sum to 1, we have the identity:
Mah(T)= Σ To(S). for any function h 10, IR
(30)
MC
SC
Moreover, MA may be interpreted as downshift operator in the sense that: for each T C [m]]. the Fourier coefficient MTl(T)) depends only on those of h(()) for S 2 T. The following result gives more precise characterization of each Myh(T') in the standard basis.
16

---

Lemma A.3. For any function h {0, 13" + and X E [0, 1].
Mah(a)= = Σ Ma where Mah(T) = rI
Σ
(1 - A)
(31)
TChm
$27
Proof. This follows by analyzing the 7-th row of MA as in Equation
29 Specifically, we have:
Mah(a) = Σ
R(S)Maxs(a)
(32)
1gmm
Σ
(SS
Σ
(Lemma A.2
M
TSB
= Σ Xr(a)
Σ
|T| - 1)1s-TTT((S))
(33)
TCNM
52T
MyA(T)
where the final step follows by noting that each Myh(TT) depends only on h(S) for S T.
The expression derived in Lemma A.3 shows how spectral mass gets redistributed from higher-order to lower-order terms. To understand how smoothing affects classifier robustness, it is helpful to quantify how much of the original function's complexity (i.e., higher-order interactions) survives after smoothing. The following result shows how smoothing suppresses higher-order interactions by bounding how much mass survives in terms of degree k.
Theorem A.4 (Higher-order Spectral Mass After Smoothing). For any function [0, + R, smoothing parameter X e [0, and 0 $ k S
Σ [Ma((T) Pr X~Bin(n_A)
X 2 kj
Σ (((S))
(34)
T-TTIK
S:112
Proof. We first apply Lemma A.3 to expand each MT)(T) and derive
Σ MAR(T) Σ
Σ X ATI
2)1s-TI
(35)
24
T:T 22
[S|
{S]
= Σ ((S)
(36)
S:SSk
J=
Pr Vo-iin (8) (A)
[Y
where we re-indexed the summations to track the contribution of each [T) for |S] 2 k. To yield the desired result, we next apply the following inequality of binomial tail CDFs given [S] S n
Pr
Y k|
Pr X~Bin((.A)
X X ks).
(37)
Our analyses with respect to the standard basis provide first step towards understanding the random masking operator MA. However, the weight-mixing mixing from initial calculations suggests that the standard basis may be algebraically challenging to work with.
A.3 Analysis in the Biased Fourier Basis
While analysis on the standard Fourier basis reveals interesting properties about M2. it suggests that this may not be the natural choice basis in which to analyze random masking. Principally, this is because each Mxxs is expressed as linear combination of xr where T C S. By "natural", we instead aim to express the image of M, as a single term. One partial attempt is an extension of the standard basis, known as the p-biased basis, which is defined as follows.
17

---

Definition A.5 (p-Biased Basis), For each subset S - [nd], define its p- p-biased function basis as:
x²(a)
II 1EB
p 03 V - pd
(38)
Observe that when p 1/2, this is the standard basis discussed earlier. The p-biased basis is orthonormal with respect to the p-biased distribution on {0, 10 in that:
[ if (e((a)x((a)) = { S oo a>-Bern(p""
(39)
On the p-biased basis, smoothing with well-chosen À induces a change-of- effect. Lemma A.6 (Change-of-Bassy For any p-biased basis function X's and À E (p. 1}.
Maxa(a)= = (1 (A-2)
181/2
Xs (a).
(40)
Proof. Expanding the definition of Mx, we first derive:
Maxa(a)= z~Berm(A))
II
P
(41)
VP p
LIES
p 0i
(by independence of #1...., kn)
p2
SES
p Aa;
(42)
p p
iES
We then rewrite the above in terms of (p/ (o/A)-biased basis function follows:
(p/ A) ai
Maxa(a) = II
(43)
V - 12
KES
(p/2) (p/A)² (p/2) - as
p))
VP-P² D2
V(p/A) (p/A)²
IES
(p/A) as
P
(44)
P (p//A) (w/A)²
X p>
/2
(p/A) as
(45)
1 -
V(p/A) (p/2)2
IES
(a)
When measured with respect this changed basis, MA provably contracts the variance.
Theorem A.7 (Variance Reduction). For any function h {0, 10" and X E (p. 1).
(A-D) Var
Var [M>h(a)] < (1-P)
[h(aa]]
(46)
o--Bern(p/ a
BerBer(
If the function centered at B Bew [k(aa)] then we also have:
E
[Mah(a) <
E Bern)))p)
[b[a)
(47)
anBern(p/2)"
18

---

Proof. We use the previous results to compute:
Var a>BBrr(p/A)
[Mh((a)]= =
Var an-Bera(p/A)
MA
Σ
(()))(((a)
Sg(m
(by unique p-biased representation of h)
181/2
Var anBerr(p/A))
Σ [
P 1
X(S)xss (a)
(by linearity and Lemma (emma|A.6)
Σ
A
R(S)²
(Parseval's by orthonormality of x
1
540
A - p
Σ R(())² 5
(0 S A-p S because p S 1) 1-p
1
p
Var
[h(a)]
(Parseval's by orthonormality of x">
p
aorBer (p))
leading to the first desired inequality. For the second incquality, we continue from the above to get:
E a--Ber(p))
[h(a)²] h(0)22 + Σ A(S))
(48)
S
Var [M(a))
E a--Bempp/A/) A/m
[Mah(a)) MMa((0)²
Σ Mah(S)²
(49)
S
Var [MaA(a)]
where recall that h(0) = E, [h(aa] = 0 by assumption.
The smoothing operator MM acts like a downshift on the standard basis and change-of- on a well-chosen p-biased basis. In both cases, the algebraic manipulations can be cumbersome and inconvenient, suggesting that neither is the natural choice of basis for studying Mx. To address this limitation, we use the monotone basis in Appendix B to provide a novel and tractable characterization of how smoothing affects the spectrum and stability of Boolean functions.
B Analysis of Stability and Smoothing in the Monotone Basis
While the standard Fourier basis is a common starting point for studying Boolean functions, its interaction with M2, is algebraically complex. The main reason is that the Fourier basis treats 0 - 1 and 1 + 0 perturbations symmetrically. features (i.c.. a' ~ (a)) and smoothing operations that remove features. This mismatch results terms that is algebraically inconvenient to manipulate. We were thus motivated to adopt the monotone basis (also known unanimity functions in game theory), under which smoothing by MA is well-behaved.
contrast, we wish to analyze perturbations that add
in complex redistribution
B.1 Monotone Basis for Boolean Functions
For any subset T S [n]], define its corresponding monotone basis function 1r (0,1)" + {0, 1} as: if a; = for all E T' (all features present), otherwise (any feature in T is absent),
(a) {
(50)
where let (a) = 1. First, we flexibly identify subsets of [n] with binary vectors in (0, 1)",, which lets us write T' if 7 implies a; This gives us useful ways equivalently write (a)):
T C c,
(r(a)=
II iET'
(51)
0 otherwise.
19

---

The monotone basis lets us more compactly express properties that depend on the inclusion or exclusion of features. For instance, the earlier example of conjunction h(a) an A ag may be equivalently written as:
a1 02 = (1)
(monotone basis)
1 7 Xo(a)) (x1)(a) (xee((a) (x).2((a)
1
(standard basis)
Unlike the standard bases (both standard Fourier and p-biased Fourier), the monotone basis is not orthonormal with respect to {0, 1) because
E (0.1)
[s(a)]r(aa]]
Pr [ 1-uu a-10,1)"
(52)
where note that SUT S a iff both S S a and T a. However, the monotone basis does satisfy some interesting properties, which we describe next.
Theorem B.1. Any function h: {0, 11" R is uniquely expressible in the monotone basis
h(a) = Σ h(T))r(a),
(53)
TCMN
where h(T) R are the monotone basis coefficients of h that can be recursively computed via:
T(T)) = h(T) ( i(S)),
7(0) h(,)),
(54)
SET
where h(T) denotes the evaluation of the binary vectorized representation of
Proof. We first prove existence and uniqueness. By definition of 1r, we have the simplification:
h(aa Σ h(T))T(()) = -Ehen
(55)
TCM
TCa
This yields system of 2 linear equations (one for each h(aa)) in 2" unknowns (one for each (())). We may treat this as matrix of size 2" x 2" with rows indexed by h(aa and columns indexed by h(T), sorted by inclusion and degree. This matrix is swwer-rringularr with ones the diagonal (T) = 1 and (a) = 0 for [T| >> a; like a transposed Equation (29). ). and so the 2" values of h(a)) uniquely determine h(T).
For the recursive formula, we simultaneously substitute a T and T S in Equation 55 write:
M(T) = Ī(T) + Σ (S)),
(56)
SÇT
and re-ordering terms yields the desired result.
B.2 Smoothing and Stability the Monotone Basis
key advantage the monotone basis is that yields convenient analytical expression for how smoothing affects the spectrum.
Theorem B.2 (Smoothing in the Monotone Basis), Let M2 be the smoothing operator in Defini- Then, for any function h {0, 1 + IR and T S [ni), we have the spectral contraction:
tion A.
Mah(T) (IT)T(T)
where M2h(T) and h(T)) the monotone basis coefficients of Myh and h at T. respectively.
20

---

Proof. By linearity of expectation, it suffices to study how Ms acts on each basis function:
MAlr(a)= z~Bern(A)
[r @ 2)]
(by definition of M2)
II (aszs)
(by definition of 1r(a))
z=BBer(AA)
LiET
III iET
as
E Ber(B))(A))
[25]
(by independence of 21....: 2n.
X = (a())
(I [z,] A)
The monotone basis also gives a computationally tractable way of bounding the stability rate. Crucially, the difference between two Boolean functions is easier characterize. As simplified setup, we consider classifiers of form h: {0. 1)"h + RR where for 3 ~ (r(a) let:
= if [M(8) h(a)) S-
(57)
R Such h and its decision boundary may be derived from general classifier f: R" - IR once and a are known. This relation the decision boundary then motivates the difference computation:
h(3) h(a) Σ (3T) - =
E TEMOTT70
k(T))
(58)
TC(A)
where recall that (g) - (a( = iff T * 0 and 7 S \ a. This algebraic property plays key role tractably bounding the stability rate. Specifically, we upper-bound the instability rate TyA
1 1-
Pr [1((B) h(a)l 71. B~dr(a)
(59)
An upper bound of form 1 T, < Q. where Q depends on the monotone coefficients of h, then implies lower bound on the stability rate - Q S Tr- We show this next.
Lemma B.3 (Stability Rate Bound). For any function h 10,1)" [0, and atribution (0, 1)" that satisfy Equation (57). the stability rate T, is bounded by:
T
[i(T))
Pr B~A.
al 2 k). |13
(60)
a [T
where
Pr 8~A,
n la
|
|A|= Σ
n n-
(61)
A
j j-k
21

---

Proof. We can directly bound the stability rate as follows:
1 T Pr
[lh(3) h(a)) > m
(62)
AmA,
<
E
[lh(3) h(a)]l
(Markov's inequality)
7 A
E
Σ (?(T)
(by Equation 58 triangle inequality)
y Ar
TC T=0
Σ
Σ
Σ
ITT))
(enumerate / E Ar(a) by its size, k)
k= 1=/ a
Σ [(()))
(the k = 0 term zero, and let S = 33 o)
(a TES
TCS
(A(T) .
a : 527, S
(re-index by T)
A
Am TC Ba
-
Total times that h(T) appears
Σ H(T))
Pr a A-A,
(63)
1=
aa
Tk
An immediate consequence from Theorem B.2 stability rate bound on smoothed functions.
Theorem B.4 (Stability of Smoothed Functions).
Consider any function : {0, 13" [0, 1] and
attribution a E {0, that satisfy Equation 557
Then, for any X E [0, 1].
Q S Tr(
= 1 XQ 7
1
I Tr TMaM,,, a)),
(64)
7
where
Σ
((TIII Pr [B\] a0 kk..
(65)
B-A.
MC T+
Proof. This follows from applying Theorem B.2 to Lemma B.3 by noting that:
T.. (Mah,
S
((T) Pr
[I8 al 2 A).
(66)
ANA.
T a 1
Moreover, we also present the following result on hard stability in the monotone basis.
Theorem B.5 (Hard Stability Bound). For any function h {0. 1}" - [0, 1] and attribution (0, 1)" that satisfy Equation 57). lei
F = arg max max
k(T)) S9
(67)
20
TCAA..440
Then, h is hard stable with radius r*
22

---

Proof. This follows from Equation
58
because it is equivalent to stating that:
arg max r S
max
[1(33 h(a)) $
(68)
((3)ah(a)
L
In summary, the monotone basis provides a more natural setting in which study the smoothing operator MA. While Ms yields an algebraically complex weight redistribution under the standard basis, its effect is more compactly described in the monotone basis as a point-wise contraction each T S [n]. In particular, we are able to derive lower-bound improvement on the stability of smoothed functions Theorem B.4
C Additional Experiments
In this section, we include experiment details and additional experiments.
Models For vision models, we used Vision Transformer (ViT) 17 ResNet50, and ResNet18 24
For language models, we used RoBERTa (38]
Datasets For the vision dataset, used subset of ImageNet that contains images per class, for a total of 2000 images. The images are of size x 224 x 224, which we segmented into grids 196 features. For the language dataset,
with patches of size 16 16, for total of n (224/16) we used six subsets of TweetEval (emoji, emotion, hate, irony, offensive, sentiment) for total of 10653 items; we omitted the stance subset because their corresponding fine-tuned models were not readily available.
Explanation Methods For feature attribution methods, used LIME (51, SHAP (39], Integrated Gradients [63] and MFABA [75] using the implementation from exlib. Each attribution method outputs ranking of features by their importance score, which we binarized by selecting the top-25% %
of features.
Certifying Stability with SCA We used SCA (Equation (3) for certifying soft stability (Theo- rem 3.1 with parameters of s = ā = 0.1, for a sample size of N = 150. We use the same N when certifying hard stability via SCA-hard (Theorem 3.2 Stability rates for shorter text sequences padded by repeating their final value. Where appropriate, we used 1000 iterations of bootstrap compute the 95% confidence intervals.
Compute We used a cluster with NVIDIA GeForce RTX 3090 and NVIDIA RTX A6000 GPUs.
C.1 Certifying Hard Stability with MuS
We next discuss how Xue et al. [70] compute hard stability certificates with MuS-smoothed classifiers. Theorem C.1 (Certifying Hard Stability via MuS (70). For any classifter f RR." - [0, 1]mh and
E [0, 11, let f= f be the MuS- smoothed classifier. Then, for any input x E I2" and explanation (0, i)", the certifiable hard stability radius is given by:
Peert
(69)
2A
where fa(x o a:) and f2(2 @ a) are the top-1 and top-2 class probabilities of f(x @.).
Each output coordinate fi...., fm is also X-Lipschitz to the masking of features:
(s @ a) f( e a')l < A/a a'), for all a, E [0, and i I,..., m. (70)
That is, the keep- erep-probability of each feature also the Lipschitz constant (per earlier discussion:
A). Note that deterninistically evaluating Mxfz would require 2n samples in total, there
23

---

1.00
100
Staility Pate
Stabiitty Rata
6.75
Sability Rate
1-0.125
0.50
0250
0.2250
Stbilit
A 0250
0.25
0.375
1 0.375
0.375
A 0.375
0.500
0.25
0,500
0.500
9.25
A D.500
0.00
3.00
2
0.00
0.00
(VIT LIME) Pert Badkus
(Resteet5 LIME Pert Radius
(Resker18 LIME Pert Radius
[RodeRTs LIME Pert Radius
Stabiltt Rate
A.322
Stability Rato
2m0.125
SCA-hard
Staility
SCA-hard
0-..225
Sabiiity 2218
0.75
A 0.2.22
0.50
0.255
0.375
0.50
1- 0.250
0.375
6.50
0.250
0.375
0.50
Am 02200
A 0.375
0.25
0.500
0.25
1m00000
0.25
0.500
0.25
0.500
0.00
3.00
0.00
0.00
(VIT SHAP) Pert Radius
[ResNet50 SHAPI Port Radius
(ResNet18 SHAP) Port Radius
(RuBERTa SHAP) Racius
SCA
SEA
Stabiity Rate
0.75
SCA-hard
A 0.125
Stability Rata
0.75
SCA-hard
6.125
Stability Rate
6.75
SCA-hard
0.125
Stabiiitt Rate
0.75
A 0.125
SCK-hard
0.50
A- 0.250
0.50
A- 0.250
8.50
0.250
0.50
A- 0.250
0.375
1- 0.375
= 0.375
A D.315
0.25
0.25
0.25-
0.25
0.00
2.00
0.00
0.00
ImSirad) Pert Radius
(Reshiet50 inttirad) Pert Radhus
(ResNett6 intGradi Radius
(RoBERD) intöiaad Radius
1.00
SCA
1.00
SCA
1.00
SCA
1.00
SCA
Spaility Rate
0.75
Sck-hard
A 0.125
Stallit Raze
2.75
SCA-ardd
0.122
Stabiity Rate
0.75
SCA-hard
- 0.125
Sabillit Ratz
0.75
A- 0.125
SCk-hard
0.50
A-0250
0.50
1-0.250
6.50
-225
0.50
A- 0-25
0.25
3.25
0.25
0.25
0.00
0.00
(VIT
(ResNet50 MFABA)
MPABA) Radius
(RoBERTs MPABA Radius
1.00
SCA
1.00
SCA
1.00
SCA
1.00
SCA
Sabilty Pate
0.75
SCA-hard
0.325
Stabiltt Rate
0.75
SCIvaad
Stablity
6.75
SCached
0.122
0.75
SCA-hard
0.125
0.50
0.50
0.50
0.375
0.375
0.500
0.25
A- 0.500
0.500
0.25
0.500
0.00
0.00
0.00
3
2
3
2
IVI Randomi Radius
[ResNat50 Random)) Radius
[hesNetia Randam) Part
(heBEITs Random) Part
Figure 9: SCA certifies more than MuS. An extended version of Figure
5 SCA-based stability
guarantees are typically much stronger than those from MuS.
are 2" possibilities for (ern Interestingly, distributions other than Bern(A)" also suffice to attain the desired Lipschitz constant, and thus a hard stability certificate. In fact, Xue et al. [70] constructs such a distribution based on de-randomized sampling (34], for which a smoothed classifier deterministically computed in 2n samples. However, our Boolean analytic results do not readily extend to non-Bede on-Bernoulli distributions.
C.2 SCA vs. MuS on Different Explanation Methods
We show in Figure an extension of Figure where include all explanation methods. Similar to the main paper, we observe that SCA typically obtains stronger stability certificates than MuS, especially vision models. On RoBERTa, MuS certificates be competitive for small radii, but this requires very smooth classifier (A 0.125).
C.3 MuS-based Hard Stability Certificates
We show in Figure 10 that MuS-based certificates struggle to distinguish between explanation methods. This is in contrast to SCA-based certificates, which show that LIME and SHAP tend to be more stable. The plots shown here contain the same information as previously presented in Figure 9 except that we group the data by model and certification method.

---

1.0
Stabiliy Rate
SHAP
Stability Rate
Stabiiity Rate
LIME
0.9
Int3rod
intrrad MFABA
LIME
0.8-
Stabiitty
MFASA
6.8-
0.8
Random
Ransim
MRABA
MFASA
Random
Random
(MT,, SCA) Radius
|ResNet50, SCA) Radius
(RosNet1 SCA) Radius
[RoBERTO, SCA)
1.00
2.00
1.00-
1.00-
LIME
Sobiiit Rate
0.75
Stabiiity Rate
8.75
Stabiity Rate
0.50
MFADA
Bendomm
0.50
MEABA
Rendem
Stablity
0.50
MTAMA
Rendom
0.50
Rendom
0.25
0.25
0.25
0.25
3
2
5
2
(VIT. har-h Radius
|Restee550, SCA-hard) Radius
(ResNet10, SCA SCA-hard) Radius
[RoDERTb, SCN hah- Radius
Stabiity Rate
0.75
SHAP
Stablity Rate
0.75
SHAP
Stabiity Bate
0.75
0.50
NPARA
IntGred
0.50
MFABA
IntGred
Stabiitty
0.50
UME
0.50
Random
Random
0.25
0.25
0.25
MEABA
9.25
MEABA
Random
Ramdom
0.00
2.00
0.00
0.00
(MTT 2 0.125) Radius
(RecNet50, A 0.125) Radius
[Resher18, A 0.12 Radius
(RaBERTa, 00.125) Radius
1.00
LIME
1.00
LIME
1.00
UIE
1.00
LIME
Sabiliy Rate
0.75
0.50
NEABA
Intrrad
SHAP
Stabiltt Rate
0.75
2.50
Intorad
S1APP
MHABA
Staility
0.75
0.50
MFABA
SHAP
InsSrad
Sabilit Rate
0.75
0.50
Intrrad
MFABA
SHAP
Random
Random
0.25
0.25
6.25
0.25
0.00
2.00
0.00
0.00
(VIT. 0.250) Railuss
(ResNet50, =0250) Radius
(Resheet8. 0.2500 Radius
IRoBERTs, 0250) Radius
1.00
UME
1.00
LIME
1.00
UME
1.00
LIME
Staility Rate
0.75
SHAP
Stabllty Rate
0.75
SHAP
6.75
SHAP
Stability Rate
0.75
SHAP
Inttrad
Int5rad
Intörad
IntGrad
0.50
0.50
Stabiley
0.50
0.50
0.25
0.25
0.00
(WT, 0.375) Radius
(ResNet50. 0.375)
(Reshet18, 0.375) Radius
(RoBERTa, 375) Radius
1.00
UME
1.00
LIME
LINE
1.00
UME
Stability Rate
0.75
Stbiiity Rate
0.75
0.75
Stabilitt Rate
0.75
SHAP
Stability
0.50
Random
Random
Random
Random
3
2
(MT. 2 0.500) Radius
(tesNee50, 0.500) Radius
[Reshee 18,
A 0.500) Redius
(RoBERTa, 500) Radius
Figure 10: MuS-based hard stability struggles to distinguish explanation methods. SCA-based
stability certificates (top two rows) show that LIME and SHAP tend to be the most stable.
C.4 Ablation Top-k Feature Selection
To see the stability of explanation methods across different selections top-k, we show an ablation study in Figure I1 Notably, observe that SHAP is generally the most stable, whereas Integrated Gradients and the random baseline tend to be the least stable.
C.5 Stability Smoothing
show in Figure an extension Figure 7 where we plot perturbations at larger radii. While stability trends extend to larger radii, the effect is most pronounced at smaller radii. Nevertheless, even mild smoothing yields benefits at radii beyond what MuS can reasonably certify without significantly degrading accuracy.
25

---

1,00
LIEE
1.00
UINE
1.00
LIKE
0.75
Intorad
SHAP
Stalliy Razz
0.75
In6rrad
SHAP
0.75
mt5rad
Stabiit Rahe
Instiad
SHAP
Stabiin
0.50
MFABA
0.50
MFABA
0.50
MPABA
NFABA
Random
Random
0.25
0.25
0.25
0.00
0.00
0.00
100
10
15
(VIT. 12.55 Pwrt Radlus
(Reskeet0, Top 12.5%) Redlus
(Recket50 12.5% Pert Radhus
[NoBBIX Tpp 12.5%) Pert
UNN
LIME
Bave
0.00
Intörad
Staaley Rare
0.75
SHAAP
Inerrad
Staatity
0.75-
Intrrdd
Stabiity Rate
Inttirad
SHAP
1.66
MFABA
0.50
Random
MFABA
WPABA
NFABA Random
0.4
0.25
0.2
50
100
15
(VIT. Radius
(Hesdieb5. Top 25.0%) Pert Itedus
NSenNe150, 25.0%) Part Rarths
[NuBEKT, Top 25.05) Radios
1.0
1.0
LIME
Qrakiity faee
SHAP
Stubiily tlate
Rate
0.8
SHAP
Staakiity Ratt
SHAP
8.8
IntGrad
IntGrad
Int5rad
0.8
Inttrad
MFABA
MFABA
MFABA
NFABA
0.6-
Rancom
Random
Random
Random
0.4
50
100
75
50
15
Top
[RoBERTb.
Top 37.5%) Radius
1.0
LIME
1.0
LIME
1.0
UME
Smowinng Rate
0.9
SHAP
Slubaliy tlate
Stabiliy Satt
IntGrad
0.8
IntGrad
Smawiiy
0.6
IntSrad
IntGrad NFABA
6.8
MEABA
MPABA
MTABA
0.8
0.7
Biendom
0.6
Rendom
0.6
Random
Random
0.6
0.4
0.4
50
75
15
Top
[RaBERTD. Tbp 50.0%) Radius
Figure 11: Soft stability rates on different top-k selection. SHAP tends to be the most stable method, particularly for vision models. On the other hand, Integrated Gradients and the random baseline are usually the least stable. Note that the top-25% row of plots is the same one as shown carlier in Figure
0.8
Stabiity Rate
Stabiitt Noal
Siability Bane
0.9
0.6
0.6
0.8
Aw7.
0.4
3.5
0.4
2005
1-25
12
20
16
12
20
0.6
4
12
16
(VTT) Port Radius
(RisNe150) Part Radius
(ResNuti Port Radius
(RoBEHTT) Pert Radius
Stabiity Bate
0.6
0.8-
Sebblity 1955
0.6
Stabiity Bakg
0.5
0.4
Aw0.5
Stabaltty
0.6-
1w0.0
0.4
0.8
A.555
3.5
0.2
0.2
0.0
60
800
1.00
20
40
60
100
80 (RcoNet18) Port Raclus
60
100
12
24
(VIT) Port Radius
[Reshet50) Pert Radius
(RoBEITT)) Pert Radios
Figure 12: Mild smoothing (A 2 0.5) can improve stability. An extended version of Figure improvement is more pronounced at smaller radii (top row) than at larger radii (bottom row).
7 The
C.6 Computational Efficiency of Certification
Certifying soft stability requires log(2/8) forward passes of the model. However, the exact wall-clock time depends on system and implementation-spenn -pppctcatiioossssiiiiiiiiiiiiic details. In particular, batched evaluation of the samples can speed up the individual per-sample forward pass, as we show Table Tusing different batch sizes. We report statistics for each model averaged over 100 samples from its respective dataset.
2
26

---

Baseline
Effective Time per Pass (ms) with Batching
Model
Time (ms)
Batch Size 5
Batch Size 10
Batch Size 15
VIT
3.94 + 0.17
1.60 + 0.06 (2.46x)
1.44 0.05 (2.74x)
1.46 + 0.06 (2.71 x)
ResNet50
3.82 - 0.10
0.84 0.07 (4.52x)
0.48 = 0.08 (7.99x)
0.40 0.01 (9.57x)
ResNet18
1.62 + 0.12
0.39 = 0.04 (4.10x)
0.24 0.01 (6.72x)
0.19 + 0.01 (8.50x)
RoBERTa
4.81 0.14
3.84 = 0.10 (1.25x)
3.66 = 0.09 (1.31x)
3.77 + 0.13 (1.28x)
Table I: Batching significantly reduces the effective time per forward pass. We compare the baseline single-pass time against the effective per-pass time achieved during stability certification (which requires N = 150 passes for = = 0.1). The speedup factor relative to the baseline is shown in parentheses.
1.0
Rand Mask
Rand Flip
1.0
1,0
1
0.9
Mass
0.5
A = 0,9
0.5
0,8
0.8
0.0
0
2
8
10
2
8
Fourier Degree
Fourier Degree
Random masking and flipping are fundamentally different. On the standard Fourier spectrum, random masking (left) causes a down-shift in spectral mass, where note that the orange and green curves are higher than the blue curve at lower degrees. In contrast, the more commonly studied random flipping (right) causes a point-wise contraction: the curve with smaller À is always lower.
Figure 13:
C.7 Random Masking vs. Random Flipping
We next study how the Fourier spectrum is affected by random masking and random flipping (i.e., the noise operator), which are respectively defined for Boolean functions as follows:
Myh(a)= E
[h(a O 2)]
(random masking)
z~Berr(A)"
[n((a= 2) mod q= 1 A
Tah(a)=
E z>~Ber(g))
(random flipping)
In both cases, corresponds mild smoothing, whereas À O corresponds heavy smoothing. To study the difference between random masking and random flipping, we randomly generated
spectrum via T(( N(0, 1) for each S C [n) We then average the mass of the randomly masked and randomly flipped spectrum at each degree, which are respectively:
Average mass degree from random masking
Σ
MAh(S))
(71)
S:|S|=k
Average mass at degree h from random flipping = Σ
(TM(S)
(72)
S:
We plot the results in Figure 13 which qualitatively demonstrates the effects of random masking and random flipping the standard Fourier basis.
D Additional Discussion
Alternative Formulations of Stability There are other ways to reasonably define stability. For example, might define 7=k the probability that the prediction remains unchanged under an exactly k-sized additive perturbation. A conservative variant could then take the minimum over T=i....,Tes The choice of formulation affects the implementation of the certification algorithm.
SCA vs. MuS While MuS offers deterministic (hard) guarantees, it conservative and limited to small certified radii, making it less practical for distinguishing between feature attribution methods.
27

---

In contrast, SCA uses statistical methods to yield high-confidence probabilistic (soft) guarantees on the stability rate. More broadly, probabilistic guarantees are relevant for modern, large-scale systems as they are often more flexible and efficient than their deterministic counterparts. They have seen use medical imaging [19), drug discovery 77, autonomous driving (37, and anomaly detection [35
often through conformal prediction 5
13
Limitations While soft stability provides a more fine-grained and model-agnostic robustness measure than hard stability, it remains sensitive to the choice of attribution thresholding and masking strategy. While standard, we only focus on square patches and top-25% selection. Additionally, certificates are statistical rather than robustly adversarial, which may be insufficient in some high-stakes settings.
Broader Impact Our work is useful for developing robust explanations for machine learning models. This would benefit practitioners who wish to gain a deeper understanding of model predictions. While work may have negative impacts, it is not immediately apparent to us what they might be.
28

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant
information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist one of the factors their evaluation. While "[Yes]" is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] provided a proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer often more nuanced, so please just use your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We support our claims with both theoretical proof' and experimental evaluations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It fine to include aspirational goals as motivation as long as it clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
We discuss the limitations Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
29

---

The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (e.g,, independence assumptions, noiseless settings, model well-speciffcation, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or a speech-to-ter system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Ys]]
Justification: We give some proofs of our claims in the main paper, as well as more in- treatment in Appendix andd Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proofs provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Ys]]
Justification: We describe our experimental setup in Section and Appendix C Moreover, we will make our code available open source when it is okay to do so.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide
30

---

access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily reproduce that algorithm.
algorithm, the paper should make it clear how
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
new model (e.g., large language model), then there should either
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-sourg models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
We will make our code available as open source when permitted to do
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines httttp::/nips.cc/// ss guides/CodeSubee ssisssoioooooos ioliiiic for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: : /nips httppullccggiide//cdeeiit ottp://ooooestmmssiooooooooooooo wwwsssooioinoiiioo//o..oaaoiiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We give detailed descriptions of experiment setup in Section 5 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details be provided either with the code, in appendix, or supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
31

---

Answer:
[Yes]
Justification:
We report error bars where appropriate.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It OK report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
We describe compute resources Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn' 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics http:pss///oorppp.ccooo/o///a//s
ines?
Answer: [Yes]
Justification: To the best of our ability and knowledge, we have conformed to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
* If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consideration
due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss broader impacts in Appendix Guidelines:
32

---

The answer NA means that there is no societal impact of the work performed. If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to partieular applications. let alone deployments. However, if there is a direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We not release new models and data.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All assets are properly credited in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswi whooode......e.....e www.cooo/aaoooo com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce assets in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification:
We do not conduct research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants. whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We do not have human participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, standard component of the core methods in this research? Note that the LLM used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required. Answer: [Yes]
34

---

Justification:
We used an LLM, RoBERTa, only for evaluating the stability of explanation
methods.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy http:://aaarrsssccccooooeerrrres what should or should not be described.
for
35


Reviews:
[{"review_id": "cseGeu0m6B", "reviewer": "Reviewer_sbAw", "summary": "The paper tackles certifying the robustness of feature-attribution explanations when additional features are added. It introduces soft stability, a probabilistic metric quantifying the share of perturbations that leave the prediction unchanged, and presents the Stability Certification Algorithm (SCA), a simple, model-agnostic sampling method that statistically guarantees both soft and hard stability. Leveraging new Boolean analysis, the authors prove that mild random-mask smoothing improves stability without accuracy loss, and confirm these insights on vision and language models with multiple attribution methods.", "questions": "- Why restrict to additive, uniformly sampled supersets $\\Delta \\_r$? Could SCA be extended to certify robustness to feature removals or structured perturbations (e.g., contiguous text spans or image patches)?\n\n- Practitioners must pick $\\varepsilon, \\delta$ (to decide how many explanations to draw), $r$, and possibly $\\lambda$. Do you have heuristics or default settings that balance certificate strength, runtime, and accuracy loss?", "limitations": "Although the limitations are not crucial, it is important that authors mention them:\n\n- SCA needs $O\\left(1 / \\varepsilon^2\\right)$ forward passes per input; for small $\\varepsilon$ the wall-time and memory could be prohibitive\n\n- Stability is certified only for additive feature inclusions drawn uniformly. Real edits often involve removals or structured, correlated changes, leaving those scenarios uncertified.\n\n- Certificates are framed by ( $\\varepsilon, \\delta$ ) while any non-zero failure probability may be unacceptable in safety-critical settings demanding zero risk.\n\n- The theory assumes a computable distance to the decision boundary $\\gamma$ (eq. 5) while estimating even loose lower bounds is non-trivial for deep networks, so the tightness of the bounds is uncertain.\n\n- The method certifies stability only for a single input-explanation pair. It offers no distribution-level or global guarantee akin to Lipschitz bounds.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths \n\n- The paper is very well-written and easy to follow.\n- SCA is simple and model-agnostic.\n- The authors show that SCA can provably certify soft and hard stability.\n- The authors show that *mild* smoothing can boost stability without the severe accuracy loss of prior certifiers, a well-known usability bottleneck.\n- The authors provide a Boolean-analysis result that supplies a principled explanation for why mild smoothing helps, moving beyond purely empirical claims.\n- Experiments reportedly span both vision and NLP tasks, suggesting breadth.\n\n## Weaknesses\n\nThe main weakness is that the paper's evaluation leaves several gaps that weaken its practical impact. \n\n### No human validation\n\nThe paper does not test whether the proposed stability score aligns with human judgements of explanation quality, leaving practical relevance unverified. I do not expect authors to address the human validation during the rebuttal, but justification for omitting it would strengthen the paper.\n\n### Incomplete baseline coverage\nThe study omits empirical comparisons with other evaluations for feature attribution methods, e.g., [1 - 4]. Again, I do not expect authors to do this comparison during the rebuttal, but it would be nice to explicitly tell why these baselines are beyond the scope of the paper.\n\n### Missing runtime evidence\n\nSCA requires $O\\left(1 / \\varepsilon^2\\right)$ samples (Theorem 3.1). For tight tolerances, this could be prohibitively slow, but the authors report no wall-clock time, FLOP count, or memory usage for SCA and other baselines.\n\n### No mask-time sensitivity study\n\nAll experiments fix the explanation to the top 25 \\% of features, yet attribution methods differ widely in sparsity. Without varying this threshold, we cannot know whether SCA still beats MuS at 10 \\% or 40 \\%, nor can practitioners learn how to pick $k$ for their own tasks.\n\n[1] Hooker, Sara, et al. \"A benchmark for interpretability methods in deep neural networks.\" Advances in neural information processing systems 32 (2019).\n\n[2] Fel, Thomas, et al. \"How good is your explanation? algorithmic stability measures to assess the quality of explanations for deep neural networks.\" Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision. 2022.\n\n[3] Salih, Ahmed, et al. \"Investigating explainable artificial intelligence for mri-based classification of dementia: a new stability criterion for explainable methods.\" 2022 IEEE International Conference on Image Processing (ICIP). IEEE, 2022.\n\n[4] Faber, Lukas, Amin K. Moghaddam, and Roger Wattenhofer. \"When comparing to ground truth is wrong: On evaluating gnn explanation methods.\" Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining. 2021.", "was_revised": true, "final_justification": "I recommend acceptance. The authors' responses adequately addressed my concerns about baseline comparisons and mask-size sensitivity analysis.", "rebuttal": "We thank the reviewer for their thoughtful comments and positive reception. Below, we address the main points raised.\n\n## W1. Regarding human validation\n\nOur primary focus is on certifying the stability of existing explanation methods. Exploring the alignment of stable explanations with human intuition would expand the practical relevance of this line of work and is an interesting future direction, but this is beyond the immediate, mathematically-focused scope of this paper.\n\n## W2. On Baseline Coverage of [1-4]\nWe agree that a thorough comparison to related work is crucial; however, **the suggested baselines are not directly comparable** as they measure fundamentally different properties. To clarify the difference, our work certifies the stability of a *model's prediction* when the *explanation itself* (the feature set) is perturbed. In contrast, the cited works evaluate *how the explanation changes* when the *model or its inputs* are perturbed:\n* [1] Hooker et al. use ROAR to measure feature importance by retraining models, a process that perturbs the model itself and is unrelated to prediction stability.\n* [2, 4] measure how the explanation changes when the training data or input graph is perturbed.\n* [3] measures how the feature ranking changes when the top feature is removed from consideration.\nIn summary, the above methods measure the robustness of the explanation-generating process, whereas we assess the robustness (stability) of a given explanation on a particular model. The only other directly comparable prior work is the hard-stability measure from Xue et al. (2023), which we thoroughly evaluate against. \n\n## W3. On Computational Cost and Runtime\nThe reviewer raised a concern about the potential runtime of SCA, given its $O(1/\\varepsilon^2)$ sample complexity. **This complexity is theoretically optimal for Monte Carlo methods without additional model assumptions.** We report sample complexity—which corresponds to the number of forward passes—as it is the **only model- and hardware-agnostic metric** for computational cost. In contrast, wall-clock time, FLOP count, or memory usage are implementation-dependent and would not provide a generalizable comparison.\n\n\n## W4. Mask-time sensitivity study\n\nThank you for suggesting running an ablation on the top-k features. The current choice of top-25% follows from the convention of prior work in Xue et al. 2023.\n\nAs a preliminary experiment, we ran ResNet18 on 2000 samples from ImageNet with explanations taken from the top-0.125, top-0.250, and top-0.375 of the features. As the proportion of features making up the explanation mask increases, we see that the stability increases, which is expected.\n\nImportantly, MuS can still only certify up to a radius of at most $1/2\\lambda$ and even this requires a heavily smoothed model (e.g., $\\lambda = 0.125$ means that on average, only $1/8$th of the original features are visible to the underlying model). Thus, even if MuS “beats” SCA (certain plots in Figure 9), this can only happen under very heavily smoothed conditions, and even then, only at low radii.\n\n\n**ResNet18 with top-0.125 selection**\n\n| Radius | SHAP | LIME | IntGrad | MFABA | Rand |\n| ------ | ---- | ---- | ------- | ----- | ---- |\n| 0 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 |\n| 1 | 0.817 | 0.796 | 0.819 | 0.807 | 0.834 |\n| 2 | 0.734 | 0.705 | 0.742 | 0.726 | 0.756 |\n| 3 | 0.674 | 0.642 | 0.685 | 0.668 | 0.702 |\n| 4 | 0.625 | 0.595 | 0.640 | 0.623 | 0.656 |\n| 5 | 0.584 | 0.554 | 0.601 | 0.587 | 0.617 |\n| 6 | 0.552 | 0.521 | 0.567 | 0.554 | 0.583 |\n| 7 | 0.524 | 0.494 | 0.536 | 0.526 | 0.550 |\n| 8 | 0.501 | 0.469 | 0.507 | 0.503 | 0.523 |\n| 9 | 0.480 | 0.450 | 0.483 | 0.480 | 0.495 |\n| 10 | 0.461 | 0.433 | 0.458 | 0.458 | 0.473 |\n\n\n**Resnet18 with top-0.250 selection**\n\n| Radius | SHAP | LIME | IntGrad | MFABA | Rand |\n| ------ | ---- | ---- | ------- | ----- | ---- |\n| 0 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 |\n| 1 | 0.885 | 0.871 | 0.848 | 0.866 | 0.845 |\n| 2 | 0.830 | 0.813 | 0.783 | 0.806 | 0.778 |\n| 3 | 0.790 | 0.774 | 0.740 | 0.761 | 0.728 |\n| 4 | 0.757 | 0.740 | 0.701 | 0.727 | 0.691 |\n| 5 | 0.731 | 0.713 | 0.673 | 0.697 | 0.655 |\n| 6 | 0.707 | 0.691 | 0.647 | 0.672 | 0.627 |\n| 7 | 0.687 | 0.670 | 0.623 | 0.649 | 0.600 |\n| 8 | 0.670 | 0.653 | 0.601 | 0.629 | 0.578 |\n| 9 | 0.655 | 0.638 | 0.580 | 0.611 | 0.556 |\n| 10 | 0.642 | 0.624 | 0.563 | 0.595 | 0.536 |\n\n\n**ResNet18 with top-0.375 selection**\n\n| Radius | SHAP | LIME | IntGrad | MFABA | Rand |\n| ------ | ---- | ---- | ------- | ----- | ---- |\n| 0 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 |\n| 1 | 0.919 | 0.912 | 0.870 | 0.886 | 0.863 |\n| 2 | 0.882 | 0.875 | 0.811 | 0.835 | 0.802 |\n| 3 | 0.854 | 0.846 | 0.767 | 0.800 | 0.756 |\n| 4 | 0.831 | 0.824 | 0.733 | 0.771 | 0.721 |\n| 5 | 0.811 | 0.805 | 0.704 | 0.747 | 0.690 |\n| 6 | 0.794 | 0.789 | 0.678 | 0.727 | 0.661 |\n| 7 | 0.780 | 0.776 | 0.655 | 0.707 | 0.637 |\n| 8 | 0.768 | 0.763 | 0.635 | 0.690 | 0.616 |\n| 9 | 0.757 | 0.751 | 0.616 | 0.675 | 0.596 |\n| 10 | 0.747 | 0.740 | 0.598 | 0.661 | 0.579 |\n\n\n## Addressing Questions\nMoreover, we address the specific questions raised below:\n\n**Q1.** We focused on additive subsets to provide a direct comparison with the perturbation style described in Xue et al. (2023). However, our framework can easily be extended. Certifying robustness to feature removals is achievable with a simple modification to our sampling algorithm in Section 3.2 (i.e., sampling from the '1's in the feature mask instead of the '0's). Structured perturbations would require a more complex sampling strategy that respects the desired structure (e.g., sampling contiguous blocks), which we believe is a promising direction for future work. We will clarify this in the paper.\n\n**Q2.** Yes, the reviewer is correct that one must select parameters. While the optimal choice of parameters **depends on the application**, we offer the following guidance:\n * Practitioner-defined Parameters ($\\varepsilon, \\delta, r$): These parameters are standard sample complexity notions that are typically set by the user based on what is meaningful for their specific use case and/or are governed by the runtime the user is willing to pay for. Specifically, $\\varepsilon$ (tolerance) and $\\delta$ (confidence) are to be set at the desired statistical guarantees, while $r$ (perturbation size) is a user and task-specific criterion. \n* Tunable Parameter ($\\lambda$): This can be tuned like a standard hyperparameter. We recommend performing a simple sweep on a validation set to find a value that maximizes stability without a significant drop in accuracy for the whole dataset.\n\nWe also appreciate the reviewer for taking the time to enumerate limitations, and we will update our manuscript to reflect them."}, {"review_id": "wJpTyHNhsF", "reviewer": "Reviewer_wGqH", "summary": "Recognizing the limitations of existing stability guarantees, in this manuscript, the author(s) proposed a stability certification algorithm based on soft stability, extending prior work to the probabilistic setting. And through empirical experiments, the author(s) demonstrated the effectiveness of the proposed method. The manuscript was mainly motivated by the central idea of additive features.\n\n---", "questions": "The manuscript looks interesting, theoretical results are mathematically derived and empirical experiments are performed to verify these results. After reviewing this manuscript, I have the following questions/comments, I am looking forward to the responses from the author(s). Thanks. \n\n1. In Figure 2, the stability analysis is presented only for correctly classified instances. It would be valuable to understand how the hard and soft stability metrics behave on misclassified samples. Are there any interesting results when the algorithm is applied to incorrectly classified images? If such experiments were conducted, it would be great if the author(s) could include or discuss them, as they could provide further insight into the algorithm’s robustness and limitations.\n\n2. In Line 76, the author(s) mentioned that two similar attributions yield the same prediction. And in the manuscript, the author(s) gave two ways including overlapping and subset/superset (i.e., additive perturbations in the manuscript) feature sets. For comparison, could you please illustrate any other ways (If there are) and cite the related work?\n\n3. In Figure 3, the notion of similarity is central to the discussion. Could the author(s) clarify how similarity is defined? Just from the observation, or other actual metrics? Also, even if there is much overlapping, it will not be significant (maybe the cat nose patch is more important than others) if the overlapping are not key features, then it will make the stability very different also be reasonable and obvious.\n\n4. In Line 221, about the value of $\\lambda$, could we use the theoretical results obtained in the manuscript explain/guide it?\n\n5. In Figure 5, could you please explain the cross point and the changing among yellow and green in the 3rd subfigure, yellow and red in the 4th subfigure? And why is there a sudden drop in the last subfigure? Understanding these patterns might help clarify the behavior and limitations of the proposed method under varying conditions.\n\n6. Some other tiny issues:\n\n(1) Please avoid repeatedly spelling out terms after their abbreviations have been introduced, such as \"Stability Certification Algorithm (SCA) \" is fully written multiple times in Lines 48, 108, 131, … after the abbreviation is introduced.\n\n(2) Ensure consistency in reference formatting. There are inconsistencies such as, refs. [59] vs. [60], refs. [62] vs. [64], etc.\n\n---", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "In my opinion, the strengths and weaknesses of this manuscript are as follows:\n\n## Strengths:\n\n1) The proposed algorithm introduces a soft stability-based certification framework, extending prior deterministic stability guarantees to a probabilistic setting. \n2) The algorithm offers stronger and more flexible stability guarantees compared to existing algorithms.\n3) The author(s) implemented empirical experiments to support the effectiveness of proposed algorithm.\n\n---\n\n## Weaknesses:\n\n1) While the author(s) claimed that using experiments validated the finds, the absence of accompanying code will diminish the credibility of the results and makes reproducibility more difficult.\n\n2) Some experimental details/explanations are not clear; for example, how to determine the value of $\\lambda$. For more details, please see Section ***Questions***\n\n3) The manuscript contains some formatting inconsistencies and issues.\n\n\n---", "was_revised": true, "final_justification": "I will vote to accept the manuscript, i.e., maintain my original score.", "rebuttal": "We thank the reviewer for their thorough comments and constructive feedback. Below, we address the main points raised.\n\n## W1. Accompanying Code\nSince we are not permitted to post any links to external pages at rebuttal and discussion time, we will release the code afterwards. We agree that reproducibility is important and will make sure that the code is easy to follow and run.\n\n## W2. On selecting $\\lambda$\nThank you for suggesting adding a discussion on how to select $\\lambda$. Since empirical results suggest that stability is mostly monotonically decreasing with $\\lambda$, we may use a binary search method to quickly search over a range of candidate $\\lambda$ and pick the one that achieves the best accuracy-stability trade-off.\n\n## W3. Formatting and consistency\nThank you for catching these inconsistencies. We will fix them in the updated manuscript (cf. Q6).\n\n\n## Addressing Questions\n\n**Q1.** Thank you for the insightful suggestion. We have performed a preliminary ablation study using ResNet18 and 100 samples from ImageNet. For each image, we randomly sampled two masks that each selected 25% of the features: (1) a “good mask” that recovers the same prediction as the full input does and (2) a “bad mask” that gives a different prediction (i.e., misclassifies). We expect that including more features in a mask should increase the likelihood that a masked prediction recovers the same output as the full input, meaning that the “bad masks” should, on average, be less stable than the “good masks.” Indeed, we observe this in our evaluation, especially as the perturbation size (the number of added features) increases.\n\n| Radius | Good Mask | Bad Mask |\n| ------ | ------ | ------ |\n| 0 | 1.000 | 1.000|\n| 1 | 0.815 | 0.856|\n| 2 | 0.758 | 0.791|\n| 3 | 0.708 | 0.727|\n| 4 | 0.681 | 0.678|\n| 5 | 0.666 | 0.636|\n| 6 | 0.646 | 0.597|\n| 7 | 0.627 | 0.570|\n| 8 | 0.615 | 0.535|\n| 9 | 0.605 | 0.510|\n| 10 | 0.594 | 0.485|\n| 11 | 0.595 | 0.464|\n| 12 | 0.594 | 0.439|\n| 13 | 0.589 | 0.427|\n| 14 | 0.588 | 0.401|\n| 15 | 0.580 | 0.382|\n| 16 | 0.585 | 0.373|\n| 17 | 0.578 | 0.355|\n| 18 | 0.577 | 0.348|\n| 19 | 0.581 | 0.329|\n| 20 | 0.584 | 0.316|\n\n\n**Q2.** We will expand our discussion of feature attribution alignment in the updated manuscript. Similarity of attributions can also be judged by how closely their rankings agree [1], whether they preserve the sign of each contribution [1], perceptual or structural resemblance of image saliency maps [2], and higher‑level alignment in a latent or neighbourhood space [3].\n\n\n**Q3.** Our notion of similarity is based on overlapping feature sets, where 4/6 of the features are common for the two explanations. However, the reviewer brings up a valid concern about the limitation of overlap-based metrics. We will clarify and expand the discussion on this in our revised manuscript, particularly using the related works mentioned in Q3.\n\n**Q4.** Please see W2 above.\n\n**Q5.** The cross-points happen when SCA is compared to a very heavily smoothed MuS ($\\lambda = 0.125, 0.250$). In such cases and at low radii ($\\leq 4$), it is not unexpected that MuS might beat SCA. However, MuS' certifiable stability radius tops out at $1/2\\lambda$, where note the steep drop, meaning that trend lines for MUS do not extend past radius 4 (where $\\lambda = 0.125$).\n\n**Q6.** Thank you again for your attention to detail on these. We will update them accordingly in the final manuscript.\n\n\n[1] Krishna et al. “The Disagreement Problem in Explainable Machine Learning: A Practitioner’s Perspective.” 2025.\n\n[2] Szczepankiewicz et al. “Ground truth based comparison of saliency maps algorithms.” 2023.\n\n[3] Pirie et al. “AGREE: A Feature Attribution Aggregation Framework to Address Explainer Disagreements with Alignment Metrics.” 2023."}, {"review_id": "rxTcsXplsv", "reviewer": "Reviewer_LG7W", "summary": "The paper presents a discrete probabilistic‐verification framework that offers robustness guarantees for feature attributions. By considering soft stability guarantees, the method yields tighter bounds than the hard guarantees produced by multiplicative smoothing. The results show higher stability rates across several attribution techniques.", "questions": "- Within the results of Figure 9, MuS with $\\lambda = 0.125$ yields better results than SCA for the RoBERTa model, why is this the case? How would it perform with $\\lambda = 0.1$? \n- Would it be possible to expand the results to a couple of other datasets both in vision and in language?\n- Would it be possible to expand the results to include an evaluation against adversarial attacks?", "limitations": "It is not clear if for lower $\\lambda$ values MuS is equal to SCA.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The paper is well written, the claims, theorems and propositions are sufficiently proved.\n- The unified framework for certifying both hard and soft stability guarantees is interesting and improve on previous work.\n- Enhancing probabilistic verification techniques for explainability is important to strengthen safety assurances in safety-critical systems.\n\n### Weaknesses\n- The paper offers little to no discussion on how stabilizing feature attributions might improve adversarial robustness.\n- Related works in discrete randomized smoothing, e.g. [1], [2], has not been considered for comparison and/or evaluation.\n\n[1] Hierarchical randomized smoothing\n[2] Localized randomized smoothing for collective robustness certification", "was_revised": true, "final_justification": "The work is technically solid and represents an improvement over prior approaches. The authors' commitment to conducting broader evaluations across additional datasets should effectively demonstrate the method's ability to generalize.", "rebuttal": "We thank the reviewer for their constructive feedback and respond to their comments below. \n\n## W1. On Stable Explanations and Adversarial Robustness\nWe would like to clarify that **stability is, in fact, a form of adversarial robustness**. If one can certify that an explanation has a stability rate of 1 at some radius, then it is adversarially robust up to that perturbation radius. In this view, it is desirable for explanations to have high stability rates, preferably at 1. We will revise our exposition to make this connection more explicit.\n\n## W2. On Discrete Randomized Smoothing\nThe particular form of discrete randomness relevant to us in [1] is based on randomized maskings from [6], which is in fact the same modality that we consider. On the other hand, the discreteness in [2] is in selecting where in the input to apply continuous-valued perturbations.\n\nAs such, **the listed references are either already covered or are not applicable to binary-valued feature attributions**. Moreover, random masking is the only form of discrete smoothing for which it is known how to prove guarantees on the stability rate: hard stability (adversarial robustness) from MuS in Xue et al. 2023, and the stability rate lower-bound in Theorem 4.2.\n\nNonetheless, the suggested references do suggest interesting directions for future analysis, particularly how one might selectively apply random masking on selected subsets of the features.\n\n\n## Addressing Questions\n\n**Q1.** The performance difference happens because we are comparing the stability of a very heavily smoothed model (MuS with $\\lambda = 0.125$) with an unmodified model (SCA). In particular, MuS with $\\lambda = 0.125$ means that only $1/8$th of the original features are visible to the underlying model, which heavily degrades accuracy (see Figure 8). Under such extreme trade-offs, it is not surprising that MuS’ certificates might outperform SCA, especially at small perturbation radii.\n\nOn radii, we would also like to note that, in all the curves for Figure 9, MuS’ stability certificate drops off at radius $1/2\\lambda$, as that is the maximum radius to which MuS can certify. In contrast, SCA can certify far beyond these radii (Figure 6).\n\n**Q2.** Yes, we can expand our results to more image and text datasets in the final manuscript. For image datasets, we are considering adding MS COCO [3] and/or Open Images V7 [4] datasets. And for text datasets, we are considering the Large Movie Review dataset [5]. If there are particular datasets the reviewer wants us to add, we are open to suggestions. Moreover, we would like to note that our dataset coverage is a superset of that used in Xue et al. (2023).\n\n**Q3.** Using adversarial attacks is an interesting suggestion. This would be useful for identifying empirical upper bounds on the hard stability radius. In fact, such experiments were conducted in Xue et al. 2023 (Figure 4), where it was observed that the MuS-certified hard stability radius is much smaller than the empirical hard stability radius.\n\nHowever, it is not immediately obvious how adversarial attacks on an explanation would meaningfully relate to soft stability. One preliminary idea is to see if adversarial attacks may be used to identify “sensitive” regions of an explanation, and then use this to accordingly adapt smoothing, e.g., by changing the probability that a feature is randomly masked.\n\n[3] https://cocodataset.org\n\n[4] https://storage.googleapis.com/openimages/web/index.html\n\n[5] https://huggingface.co/datasets/stanfordnlp/imdb\n\n[6] Levine et al. “Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation”. AAAI 2020."}, {"review_id": "28in6TbFkh", "reviewer": "Reviewer_SAAu", "summary": "The authors present a notion of soft-stability for explanations: Given an explanation and a classifier prediction from masking features not included in the explanation, this captures the *probability* that the classifiers predictions are unchanged when masking using the set of explanations which include up to radius-$r$ more features than the original (where $r$ is a hyperparameter). This is an improvement over previously used hard-stability, which strictly labels an explanation as stable or unstable at a given radius. The authors demonstrate both qualitatively and quantitatively how their relaxed version of stability yields improvements over hard-stability. They propose an estimator for both hard and soft stability, for which they prove formal guarantees. Finally, the authors link stability and smoothing: smoother classifiers enjoying better worst-case stability.", "questions": "The first two questions are related to the weaknesses above\n\n* Am I correct in my interpretation above that you are selecting some $k$ to go from real valued to binary explanations? If not, what are you doing to get the binary explanations? If you are: How do you select $k$? Is it a function of $r$, or chosen independently? \n* While I mention many similarities with [1] I believe that your work still has novelty. Can you explain the similarities and differences with [1]? What does your method bring to the table that [1] does not? One difference is that the astuteness measure in [1] uses the $r$-ball around a point as opposed to your discrete masking. However major similarities, such as both providing a soft stability measure, remain. Would the method in [1] and this method provide similar results at similar radii? I.e., would their stability rankings for different methods agree? To this end, a variant of Figure 6 including the explainer astuteness measure from [1] could be valuable. \n* In line 177 you define $\\gamma$ as the “distance to the decision boundary”. Is this the distance of $x$ to the boundary? Or is it related to the distance of $x$ masked with $\\alpha$ or $\\alpha’$ to the boundary?\n\nBased on the answers to these questions, I will consider raising my score by 1 point. \n\n[1] Khan, Zulqarnain Q., et al. \"Analyzing explainer robustness via probabilistic lipschitzness of prediction functions.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n* The paper is well written and visually appealing, with clear (and well-formatted) theorems and figures. \n* The problem of providing a relaxed version of hard stability is important for obtaining a more nuanced understanding of trusting explanations.\n* The estimator yields guarantees now for the classifier $f$ instead of smoothed $\\hat{f}$, as in MuS. \n* The experimental results are convincing\n  * The SCA bound is indeed non-trivial at larger radii, whereas the MuS bound is. \n  * Smoothing does seem to generally increase stability\n\n**Weaknesses**\n\n* You introduce explanations of feature $i$ as $\\alpha_i \\in \\mathbb{R}$ and hence total explanations as $\\alpha \\in \\mathbb{R}^N$ in section 2.1. However, you later move analysis to $\\alpha \\in \\{0, 1\\}^n$. You explain in line 66-67 that explanations can be converted into binary vectors via selecting the top-k. Two comments on this\n  * (Minor) You never explicitly state that this is indeed what you are doing for the rest of the paper. Although that may be obvious to some, it would be beneficial to do so.\n  * Such a step requires selecting some $k$ to use, but it is not made clear what $k$ is chosen or how. I can see such a choice being consequential.  For example, I imagine larger $k$ correlates with increased stability at all radii.\n* There are two missing citations that would be beneficial for the paper\n  * [1] This is a highly cited work on smoothing in interpretability, proposing the use of gaussian noise to smooth explanations. You mention such a practice in contrast to your discrete smoothing, and adding the citation there or in your related works section seems natural to me.\n  * [2] This work has many similarities to yours. They propose *explainer astuteness* which takes in a radius $r$ and threshold $\\lambda$ and returns the probability that explanations of points $x’$ in the $r$-ball around the point of interest $x$ are within $\\lambda d(x,x’)$ of explanation for $x$. As a probability, explainer astuteness takes values from $0$ to $1$ and is thus a *soft measure of stability*. The authors also provide a link between model smoothness and their measure of stability: lower bounding explainer astuteness with the probabilistic lipschitzness [3] of the model: a relaxed version of local lipschitz. \n\n\n[1] Smilkov, Daniel, et al. \"Smoothgrad: removing noise by adding noise.\" arXiv preprint arXiv:1706.03825 (2017).\n\n[2] Khan, Zulqarnain Q., et al. \"Analyzing explainer robustness via probabilistic lipschitzness of prediction functions.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.\n\n[3] Mangal, Ravi, et al. \"Probabilistic lipschitz analysis of neural networks.\" International Static Analysis Symposium. Cham: Springer International Publishing, 2020.", "was_revised": true, "final_justification": "I recommend acceptance for this paper. I maintain that this paper is clearly written and has a good mix of strong experiments and theory. The idea of relaxing hard stability to soft stability is intuitively important and the experimental results show the approach has clear value. I have raised my score from borderline accept to accept because my questions and weaknesses were well addressed. Namely the authors plan to make their binarization approach more explicit, show the method is useful at different $k$ via an ablation study, and effectively explain the differences with Khan et al. (2024).", "rebuttal": "We thank the reviewer for their thoughtful comments and helpful suggestions. Below, we address the main points raised.\n\n## W1. Binarizing Explanations \nWhile we did describe the conversion from real to binary attributions at the end of Section 2.1, we acknowledge that this could be done more clearly and explicitly. We will accordingly improve the writing to improve exposition.\n\nTo further clarify (re: Q1), we create a binary explanation mask $\\alpha \\in \\\\{0, 1\\\\}^n$ by selecting the top-k features of a real-valued vector in $\\mathbb{R}^n$, a standard technique when evaluating feature attributions (Hooker et al., 2019). The hyperparameter k is chosen independently of the certification radius r. Our choice of k=25% in our experiments follows prior work in Xue et al. 2023.\n\n\n\n## W2. Investigating Choice of k\n\nWe follow the convention from previous work in Xue et al. (2023), which selects top k = 25% features as the explanation. However, the reviewer brings up a fair point that the choice of k may be consequential to our study. Therefore, to investigate further the influence of k, we performed a preliminary ablation study on varying k. The results do not fundamentally alter our original conclusions, though they show that stability tends to increase with k, which is expected. We will add this study to the appendix in the revised manuscript for further details.\n\n**ResNet18 with top-0.125 selection**\n\n| Radius | SHAP | LIME | IntGrad | MFABA | Rand |\n| ------ | ---- | ---- | ------- | ----- | ---- |\n| 0 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 |\n| 1 | 0.817 | 0.796 | 0.819 | 0.807 | 0.834 |\n| 2 | 0.734 | 0.705 | 0.742 | 0.726 | 0.756 |\n| 3 | 0.674 | 0.642 | 0.685 | 0.668 | 0.702 |\n| 4 | 0.625 | 0.595 | 0.640 | 0.623 | 0.656 |\n| 5 | 0.584 | 0.554 | 0.601 | 0.587 | 0.617 |\n| 6 | 0.552 | 0.521 | 0.567 | 0.554 | 0.583 |\n| 7 | 0.524 | 0.494 | 0.536 | 0.526 | 0.550 |\n| 8 | 0.501 | 0.469 | 0.507 | 0.503 | 0.523 |\n| 9 | 0.480 | 0.450 | 0.483 | 0.480 | 0.495 |\n| 10 | 0.461 | 0.433 | 0.458 | 0.458 | 0.473 |\n\n\n**Resnet18 with top-0.250 selection**\n\n| Radius | SHAP | LIME | IntGrad | MFABA | Rand |\n| ------ | ---- | ---- | ------- | ----- | ---- |\n| 0 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 |\n| 1 | 0.885 | 0.871 | 0.848 | 0.866 | 0.845 |\n| 2 | 0.830 | 0.813 | 0.783 | 0.806 | 0.778 |\n| 3 | 0.790 | 0.774 | 0.740 | 0.761 | 0.728 |\n| 4 | 0.757 | 0.740 | 0.701 | 0.727 | 0.691 |\n| 5 | 0.731 | 0.713 | 0.673 | 0.697 | 0.655 |\n| 6 | 0.707 | 0.691 | 0.647 | 0.672 | 0.627 |\n| 7 | 0.687 | 0.670 | 0.623 | 0.649 | 0.600 |\n| 8 | 0.670 | 0.653 | 0.601 | 0.629 | 0.578 |\n| 9 | 0.655 | 0.638 | 0.580 | 0.611 | 0.556 |\n| 10 | 0.642 | 0.624 | 0.563 | 0.595 | 0.536 |\n\n\n**ResNet18 with top-0.375 selection**\n\n| Radius | SHAP | LIME | IntGrad | MFABA | Rand |\n| ------ | ---- | ---- | ------- | ----- | ---- |\n| 0 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 |\n| 1 | 0.919 | 0.912 | 0.870 | 0.886 | 0.863 |\n| 2 | 0.882 | 0.875 | 0.811 | 0.835 | 0.802 |\n| 3 | 0.854 | 0.846 | 0.767 | 0.800 | 0.756 |\n| 4 | 0.831 | 0.824 | 0.733 | 0.771 | 0.721 |\n| 5 | 0.811 | 0.805 | 0.704 | 0.747 | 0.690 |\n| 6 | 0.794 | 0.789 | 0.678 | 0.727 | 0.661 |\n| 7 | 0.780 | 0.776 | 0.655 | 0.707 | 0.637 |\n| 8 | 0.768 | 0.763 | 0.635 | 0.690 | 0.616 |\n| 9 | 0.757 | 0.751 | 0.616 | 0.675 | 0.596 |\n| 10 | 0.747 | 0.740 | 0.598 | 0.661 | 0.579 |\n\n## W3. Adding Suggested Citations\n\nThank you for bringing these additional works to our attention and for providing insightful analysis. We will update our manuscript with the suggested citations and further the discussion on how they relate to our work.\n\n\n## Addressing Questions\n**Q1.** This interpretation is correct: Please see W1 above.\n\n**Q2.** We appreciate you highlighting this work for us. While both our work and Khan et al. (2024) propose probabilistic stability metrics, they address different but complementary notions of robustness. In particular, Khan et al. measure how the explanation changes when the input is perturbed (how $\\alpha, \\alpha’$ vary with $x, x’$, where let $\\alpha = \\phi(x)$ and $\\alpha’ = \\phi(x’)$ for an explanation method $\\phi$). In contrast, we measure how changing the explanation on some input affects the model output (i.e., $f(x\\odot \\alpha)$ vs. $f(x \\odot \\alpha’)$ for different $\\alpha, \\alpha’$ on the same $x$). This is a subtle but important distinction, and we will incorporate a discussion of this in our updated manuscript.\n\n**Q3.** We take $\\gamma$ to be half the difference between the top-1 and top-2 class probabilities (i.e., $(p_1 - p_2)/2$, where $p_1$ and $p_2$ are the probabilities of the top-1 and top-2 classes, respectively). This ensures that even if the top-1 class probability were to drop by a value of $\\gamma$, it would remain the top-1 class. Related to this, the setup in Equation 5 is intended to convey that the class probability of the perturbed prediction $f_x (\\alpha’)$ should stay within a $\\gamma$ radius of the original $f_x (\\alpha)$. Importantly, this notion of distance to the decision boundary applies to both predictions on masked inputs and unmasked inputs. We will improve the manuscript to better describe these."}]

Author rebuttal:

Meta-review: This paper introduces the Stability Certification Algorithm (SCA), which provides probabilistic guarantees for explanation robustness through the notion of soft stability. 

Reviewers agreed that the work is technically solid and makes a meaningful contribution to interpretability by offering a more flexible and practical certification framework than prior methods. Theoretical results are clearly presented and supported with Boolean function analysis, and experiments on both vision and language tasks demonstrate the algorithm’s versatility.

Limitations include the lack of human studies to test whether stability aligns with human judgments, limited runtime and efficiency analysis, and incomplete baseline comparisons. The authors justified these choices and added clarifications and ablations during the rebuttal.

Overall, reviewers agreed that the paper is worthy of acceptance. The framework is simple, well-grounded, and improves upon existing certification techniques. Additional experiments and clarifications during the rebuttal also addressed some key concerns.

The authors should make sure to update their paper based on the discussions including releasing code, encouraging future work for evaluating stability compared to human judgments, empirical runtime costs, and discussion w.r.t. adversarial robustness.
Decision: Accept (poster)