Note: We include a general response covering global updates and experiments in our comment to Reviewer itGy. Please refer to that comment and the supplementary PDF link there.

Q: The method is an extension of Fischer et. al. 2021. Therefore, the theoretical novelty is limited.

While our work indeed builds on Fischer et al. (2021)'s certification for segmentation, adapting it to the certified attribution setting, on the pixel-level, is completely novel and non-trivial. The previous work focuses on segmentation models, but it does not contain (1) The mathematical formulation for the pixel-level certified attribution setting, (2) Certified robustness and localization metrics, (3) Rigorous comparison of the robustness-localization tradeoff of certified attributions.

1. Mathematical formulation: We are the first to formulate pixel-level certified attributions by sparsifying the attribution map (Eq. 4) and casting the result as a segmentation-like function with binary pixel labels (important/unimportant) that are semantically meaningful in the attribution settings.

2. Certified robustness and localization metrics: we introduce two certified metrics to evaluate both the pixel-level certified robustness (%certified) and localization (Certified GridPG) of 12 attribution methods spanning 3 families. Our work is the first to discuss such metrics in a certified attribution setting.

3. Rigorous comparison of different attribution methods: by leveraging our contribution in (1) and (2), we benchmark all methods across five architectures (including CNNs and ViTs), certification radii, and multiple sparsification levels.

In short, our work does not trivially rely on prior work by Fischer et al. (2021) as it includes different novel components that are essential for the certified attribution and evaluation settings that are not obvious apriori. It presents an important data point, and research direction, in the field of certified explainability.

Q: Is the method generalizable to deeper CNNs (e.g., ResNet101) or transformer-based model (e.g., ViTs)?

We fully agree with the reviewer that broader evaluation across architectures strengthens our conclusions. In response, we have extended our experimental results beyond ResNet-18 and VGG11 to include three additional architectures: Wide ResNet-50-2, ResNet-152, and a Transformer-based ViT-B/16 (Rebuttal Section 1). This nicely rounds up our analysis of the performance of all attribution methods on many architectures of different design and depths.

Q: What are the practical benefits of certified pixel-level attributions against non-certified attributions?

Certified attributions provide users with pixel-level guarantees of robustness under input perturbations, allowing them to assess which regions in an explanation are trustworthy. In contrast, standard attribution methods offer no such reliability; highlighted features may be highly sensitive to small input changes. In safety-critical domains such as medical imaging, this distinction is essential. For example, in tumor detection from X-rays, a region attributed as important but uncertified may be unstable and thus misleading. Our framework enables practitioners to identify and rely only on attributions that are provably robust, or abstain when stability cannot be guaranteed.

Thus, certified pixel-level attributions provide actionable interpretability: they enhance standard attribution maps with robustness guarantees, enabling more informed decisions about when to trust a model’s explanation, and by extension, its prediction. This capability is essential for integrating AI safely into high-stakes domains.

Q: Besides certified segmentation, can you discuss more recent certification methods (e.g., using transformer or deeper-CNN)?

The certification setting based on Fischer et al. (2021) is architecture-agnostic and applies to any black-box model.

Q: Can you discuss recent datasets and benchmarks for XAI and how they relate to your work?

Our current work focuses on certifying pixel-level robustness of attribution methods, and we evaluate on ImageNet for two reasons: (1) it is the standard benchmark used across prior certified attribution works [2, 3], and (2) it includes complex images where attribution stability is challenging. We leverage the Grid Pointing Game benchmark [4, 1], one of the frameworks for evaluating localization and explanation quality, by introducing Certified GridPG, a certified variant of this benchmark tailored to our setup.

[1] Rao et al. Better understanding differences in attribution methods via systematic evaluations. CVPR, 2022.

[2] Levine et al. Certifiably robust interpretation in deep learning. arXiv, 2019.

[3] Liu et al. Certifiably robust interpretation via renyi differential privacy. AI, 2022.

[4] Böhle et al. Convolutional dynamic alignment networks for interpretable classifications. CVPR, 2021.

Response to all reviewers

We thank all reviewers for their thoughtful and constructive feedback. We very much appreciate the diligent and constructive reviews by all reviewers, and believe the additional insights gained in preparing this rebuttal significantly strengthen our work. While we respond to all reviews individually, we would like to draw your attention to the following general points:

Supplementary PDF

A supplementary PDF with all figures and analyses is available: https://anonymous.4open.science/r/certified-attributions-E80D/ICML25_Rebuttal___Pixel_level_certified_explanations_via_randomized_smoothing.pdf

Key Updates

Three new architectures: Added Wide ResNet-50-2, ResNet-152, and ViT-B/16 (WAuF, iTN6)

Faithfulness metric: Deletion-based faithfulness analysis of certified attributions (S6h4)

Two new attribution methods: Added CAM and LRP (itGy)

Qualitative visuals: More certified maps for shape and Certified GridPG analysis (WAuF, itGy)

Conclusions

• Our certification setup is general enough to scale across five different architectures and twelve attribution methods.

• Certified robustness, certified localization and empirical faithfulness are not mutually exclusive, and some methods strike a balance between the three (e.g., LRP), hence, providing faithful and trustworthy attributions, essential for safety-critical domains.

Sincerely,

The authors

Response to Reviewer itGy

Q: Why do you use radii $R= 0.10\, 0.17\, 0.22$?

We follow the common practice from [1] and [2] for Randomizerd Smoothing for segmentation for such values of the radius. The certified radius $R\coloneqq \frac{\sigma}{2} \Phi^{-1}(\tau)$ depends on the noise level $\sigma$ and the top class probability $\tau$ (Section 4.2). We fix $\tau=0.75$ and vary $\sigma \in \{0.15, 0.25, 0.33\}$ to obtain different certified radii. These values ensure the added noise remains visually imperceptible, while enabling a controlled evaluation of robustness across a range of certification strengths.

Q: Why does Figure 1 use K=40, while the rest use K=50?

We ran all the analysis with the same $K=40$ and again double-checked this in our codebase. It turned out to be just a typo, Figure 1 indeed uses $K=50$ like the remaining ones. Thank you for pointing this out!

Q: Can you provide qualitative discussions on shapes of certified pixel-level explanations across methods?

Certainly! We extend the qualitative comparison of certified attribution shapes in Section 7.1 and further detailed in App. A & E.

We observe that input-layer methods (e.g., Backpropagation and perturbation) produce fine-grained certified regions, often concentrated on small parts of the object (e.g., GB highlighting eyes in Figure 1). In our rebuttal experiments, LRP nicely highlights the object boundaries and its parts with varying importance levels in Rebuttal Figures 10 & 11. In contrast, activation-based methods evaluated at the final layer produce larger and coarser certified regions. More specifically:

• Backpropagation-based methods are highly sensitive to perturbations and often abstain, but when certified top $K$% pixels are present, they highlight sharp localized features. LRP seems to provide the sharpest certified attributions.

• Perturbation-based methods’ coarseness of highlighted regions is influenced by the mask size and generally yield broader certified top $K$% regions than backpropagation-based methods. They also exhibit higher robustness.

• Activation-based methods produce lower-dimensional attributions that, when rescaled to the input size, yield coarser certified top $K$% regions. Our framework nicely controls the granularity of such regions via the sparsification parameter $K$, lower values concentrate the certified top $K$% pixels on smaller more important areas (Figure 2).

Q: Can you mention or compare the CAM method in your evaluation pipeline?

Thank you for this suggestion. We now include results on not only ten attribution methods, but also two additional ones: Class Activation Mapping (CAM) [3] and Layer-wise Relevance Propagation (LRP) [4] in Rebuttal Section 3. We notice that Cam highlights coarse certified top $K$ regions similar to other activation methods, while LRP produces high-quality certified attributions that focus on fine-grained details in the objects in Rebuttal Figures 10 & 11.

Q: Should L056 and L638 be changed?

Yes, thanks for pointing the typos out!

[1] Fischer et. al. Scalable certified segmentation via randomized smoothing. ICML, 2021.

[2] Anani et. al. Adaptive hierarchical certification for segmentation using randomized smoothing. ICML, 2024.

[3] Zhou et al. Learning deep features for discriminative localization. CVPR, 2016.

[4] Bach et al. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 2015.

Note: We include a general response covering global updates and experiments in our comment to Reviewer itGy. Please refer to that comment and the supplementary PDF link there.

We thank the reviewer for recognizing the significance of our certification framework, particularly the value of providing pixel-level robustness guarantees and its relevance in safety-critical applications.

Q: Should the method be evaluated on different architectures?

We agree that broader evaluation across architectures strengthens our conclusions. We extend our experimental results to 3 additional architectures: Wide ResNet-50-2, ResNet-152, and a Transformer-based ViT-B/16. These include deeper CNNs and a transformer, confirming the generality of our method (Rebuttal Section 1).

Q: Can you increase the readability and cleanliness of the code?

We appreciate this suggestion. We are restructuring the codebase to include a clear execution guide, ensuring full reproducibility. This will be available in the camera-ready version.

Q: Should the method be evaluated under different data distributions?

We used ImageNet to align with prior certified attribution work. We agree that it would be advantageous to extend our evaluation to a different data distribution. Due to limited computational resources during the rebuttal, we prioritized architectural diversity. That said, our method applies directly to other data domains, and we will include such evaluations in the final version.

Q: Should you cover all important aspects of the performance of attribution methods (e.g., other than %certified and localization)?

We appreciate the concern and would like to clarify a key point: the goal of our work is not to introduce new, but certify the robustness of existing attribution methods, which means their original performance on standard metrics stays unchanged. Our certification provides context for the end user that allows them to asses which explanations (pixel-wise attributions) to trust. To this end, our proposed two certified metrics answer the questions:

1. Does the explanation remain stable under perturbations? (%certified)

2. Do the certifiably robust pixels point to the correct region? (Certified GridPG)

In summary, our work does not aim to redefine attribution performance metrics, but to provide a certified framework that augments existing methods with trust guarantees, allowing practitioners to assess the trustworthiness of attributions. Our evaluation framework is designed to complement, not replace, standard evaluation.

Q: Can you comment on the computational cost of the method, and its real-time performance?

Certainly! We agree with the reviewer that the certification process incurs a computational cost due to the Monte Carlo sampling. We use $n=100$ samples per image in our experiments, which suffices to obtain statistically sound guarantees at a reasonable cost. In fact, there is actually seminal work on sampling with noise just to sharpen gradient-based attribution maps, such as SmoothGrad [2], which is shown to be most faithful by a benchmark for interpretability [3]. While, like our work, not designed for real-time deployment, our method is suitable for high-stakes offline settings such as medical diagnostics, legal forensics, and model auditing, where certifiable robustness is essential.

Q: Does the method need to be adjusted or improved when dealing with different dataset types?

Thank you for raising this question, which highlights the practical applicability of our method. Our certification pipeline is model and dataset-agnostic. It treats the attribution function $h(x)$ as a black-box and operates without assumptions on the model or input distribution. Thus, it applies to any domain where attribution is defined.

Q: Does Certified GridPG cover the localization of small targets?

Yes, Certified GridPG is explicitly designed to be invariant to object size. It computes the fraction of certified top $K$% pixels located in the correct subimage within a constructed grid (e.g., $2\times 2$), regardless of the object’s size (Eq. 8). This formulation extends [1]. Rebuttal Figure 11 and App. E (Figures 12-14), show various qualitative results across layers, certification radii, and sparsification levels.

Q: Is the certification equally applicable to transformer-based architectures?

Certainly! Our approach does not rely on any architectural properties. We have validated this by including ViT-B/16 in our extended experiments, alongside deeper CNNs (Rebuttal Section 1).

[1] Böhle et al. Convolutional dynamic alignment networks for interpretable classifications. CVPR, 2021

[2] Smilkov et al. Smoothgrad: removing noise by adding noise. arXiv, 2017

[3] Hooker et al. A benchmark for interpretability methods in deep neural networks. NeurIPS, 2018

Note: We include a general response covering global updates and experiments in our comment to Reviewer itGy. Please refer to that comment and the supplementary PDF link there.

We thank the reviewer for raising very fundamental questions regarding the motivation of our work. We clarify that our goal is not to make attributions robust, but to certify their robustness at the pixel level under input perturbations. This distinction appears to have been misunderstood. Other reviewers recognized our contribution: WAuF noted that our method opens “a new direction” in interpretability and iTN6 highlighted our “robust insights into method performance”.

Q: What is the problem this paper is trying to address?

We address the lack of pixel-level robustness guarantees in post hoc attribution methods. As discussed in (Section 2, Robustness issues), small input perturbations can significantly alter attribution maps even when the predictions remain unchanged, undermining trust in explanations, especially in high-stakes domains. Prior work provides only image-level bounds (Section 2, Certified explanations), which lack interpretability (Section 1, L023-L037 Right). We bridge this gap by introducing a certification setting that provides pixel-level guarantees, along with certified metrics for robustness and localization.

Q: Step-by-step reasoning for “pixel-level robustness should be proven”.

1. For a model to be trustworthy, its explanations must also be trustworthy.
2. Attribution methods are non-robust under small perturbations.
3. Existing certified attribution work focuses only non-interpretable image-level numeric bounds.
4. Pixel-level guarantees are essential to identify trustworthy regions in explanations. In a biomedical setting such as tumor detection from X-rays, a doctor can directly see which pixels the model used to predict cancer. For example, if a model highlights a shaded region as important, but our certification flags it as non-robust, a clinician can be alerted to treat the attribution with caution, potentially influencing their reliance on the model’s prediction.
5. Thus, the claim is justified to ensure trust in explanations.

Q: Does the method consider model robustness?

We agree that model robustness influences attribution robustness [3–5]. However, our goal is to certify attribution robustness for a fixed model, without enforcing or assuming model robustness. This distinction is crucial: our certification setting is attribution-centric.

To ensure attributions reflect correct class evidence, we select inputs with prediction confidence $\geq 0.99$ (Section 6, L224-L227, Right) as in [6], ensuring certified top $K$% pixels reflect correct class evidence.

Q: What do you mean by certifiably robust explanations?

Attribution maps where each pixel's certified label (important/unimportant) is guaranteed to remain unchanged under input perturbations within an $\ell_2$-ball around the input (Eq. 5 & Section 3.2). Unstable pixels are abstained from.

Claim: ”The goal of this paper is trying to make the attribution robust.”

Clarification: our goal is to certify, not improve, attribution robustness. If a method is not robust, it yields high abstentions and a low %certified scores.

Q: Does explanation robustness align with faithfulness?

We agree that attribution robustness doesn’t always reflect faithfulness. High robustness may be (i) Informative, highlighting class-relevant features (i.e., faithful) or (ii) Trivial, by producing constant maps. To disentangle these cases, we introduced Certified GridPG (Eq. 8) to jointly assess robustness and localization, which is actually a very effective sanity check. In Rebuttal Fig. 5, RISE and LRP are both robust and localize well, while methods like Grad and GB are robust at the final layer but fail to localize, due to the constant grid-like patterns they produce on that layer.

Q: Can you evaluate faithfulness using existing metrics?

Certainly! We thank the reviewer for this valuable suggestion which we believe makes our submission stronger. We include a deletion-based faithfulness analysis in Rebuttal Sec 2, where we progressively remove the certified top K% pixels (lowest to highest) in the input and measure the ground truth class confidence:

1. At the input layer, LRP and RISE cause the steepest confidence drop in the first removal step, indicating high faithfulness.
2. At the final layer, most methods cause a prediction flip after the first deletion step, showing higher faithfulness to the input layer.

Our analysis shows that high certified robustness and faithfulness co-exist (e.g., LRP) . Our framework allows the joint evaluation to identify attribution methods that are robust, faithful, and well-localized.

Further analysis in Rebuttal Sec 2.

[6] Rao et al. Better understanding differences in attribution methods via systematic evaluations. CVPR, 2022