Probabilistic Stability Guarantees for Feature Attributions

We thank the reviewer for their thoughtful comments and helpful suggestions. Below, we address the main points raised.

W1. Binarizing Explanations

While 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.

To 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.

W2. Investigating Choice of k

We 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.

ResNet18 with top-0.125 selection

Resnet18 with top-0.250 selection

ResNet18 with top-0.375 selection

W3. Adding Suggested Citations

Thank 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.

Addressing Questions

Q1. This interpretation is correct: Please see W1 above.

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.

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.

We thank the reviewer for their constructive feedback and respond to their comments below.

W1. On Stable Explanations and Adversarial Robustness

We 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.

W2. On Discrete Randomized Smoothing

The 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.

As 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.

Nonetheless, the suggested references do suggest interesting directions for future analysis, particularly how one might selectively apply random masking on selected subsets of the features.

Addressing Questions

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.

On 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).

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).

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.

However, 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.

[3] https://cocodataset.org

[4] https://storage.googleapis.com/openimages/web/index.html

[5] https://huggingface.co/datasets/stanfordnlp/imdb

[6] Levine et al. “Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation”. AAAI 2020.

Thank you for clarifying the adversarial robustness and comparison with other discrete randomized smoothing techniques. I am increasing my score by 1 point.

We thank the reviewer for their thorough comments and constructive feedback. Below, we address the main points raised.

W1. Accompanying Code

Since 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.

W2. On selecting $\lambda$

Thank 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.

W3. Formatting and consistency

Thank you for catching these inconsistencies. We will fix them in the updated manuscript (cf. Q6).

Addressing Questions

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.

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].

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.

Q4. Please see W2 above.

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$).

Q6. Thank you again for your attention to detail on these. We will update them accordingly in the final manuscript.

[1] Krishna et al. “The Disagreement Problem in Explainable Machine Learning: A Practitioner’s Perspective.” 2025.

[2] Szczepankiewicz et al. “Ground truth based comparison of saliency maps algorithms.” 2023.

[3] Pirie et al. “AGREE: A Feature Attribution Aggregation Framework to Address Explainer Disagreements with Alignment Metrics.” 2023.

Thanks for the response from the author(s). I have read the replies, which clarify my confusion and concerns more or less. I will vote to accept the manuscript, i.e., maintain my original score.

Regarding the statement "Release the code afterwards," I’d like to express a concern based on my past experiences — as a reviewer, I have encountered several cases where code was promised but never released or just partly, even 2–3 years after publication. I sincerely hope the author(s) of this manuscript will help restore trust in such promises by making the code available as stated — ideally with a concrete timeline and a real repository link. Thanks.

I also appreciate the author(s)’ acknowledgment of the importance of reproducibility. Good luck!

We thank the reviewer for their thoughtful comments and positive reception. Below, we address the main points raised.

W1. Regarding human validation

Our 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.

W2. On Baseline Coverage of [1-4]

We 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:

• [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.
• [2, 4] measure how the explanation changes when the training data or input graph is perturbed.
• [3] measures how the feature ranking changes when the top feature is removed from consideration. In 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.

W3. On Computational Cost and Runtime

The 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.

W4. Mask-time sensitivity study

Thank 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.

As 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.

Importantly, 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.

ResNet18 with top-0.125 selection

Resnet18 with top-0.250 selection

ResNet18 with top-0.375 selection

Addressing Questions

Moreover, we address the specific questions raised below:

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.

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:

• 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.
• 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.

We also appreciate the reviewer for taking the time to enumerate limitations, and we will update our manuscript to reflect them.