{"id":"54c8b2dd-9c45-40c3-9f57-2e419f3b6150","arxiv_id":"2506.15499","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A randomized smoothing wrapper certifies, per pixel, whether an attribution method's top-K importance ranking stays fixed under bounded input perturbations, with LRP and RISE coming out best in evaluation.","lead":"This paper wraps any image explanation method in randomized smoothing so that each pixel receives a certified label of important or not important that provably does not change under small input noise. It then compares 12 explanation methods on ImageNet and finds that LRP and RISE give the most robust and faithful certified maps.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1's certified radius is invalid for the abstaining smoothed function: a pixel with p_A just above τ can abstain at a perturbation inside the claimed ball, so the central certificate as stated is false.","rationale":"I read the paper in good faith: sparsifying attributions to binary top-K maps and applying segmentation randomized smoothing is a sensible and potentially useful idea. The load-bearing problem is not the philosophical question of whether top-K ranks are the right explanation target, but a concrete mathematical error in the stated certificate. Theorem 3.1 as quoted asserts that for every non-abstaining pixel at x, the smoothed abstaining function gτ returns exactly the same value at x+δ for all ||δ||_2<σΦ^{-1}(τ). This cannot be true for the gτ defined in Eq. 3. The Neyman-Pearson lemma only guarantees the argmax class is preserved, not that its probability stays above the abstention threshold τ. A pixel with class probability 0.76 at x satisfies the certification condition for τ=0.75, but an adversary can push that probability to about 0.52 at radius 0.09, where Eq. 3 outputs ⊘. Hence the claimed 'certified pixels remain 1/0 within the ball' guarantee fails exactly under the paper's definition. The same error invalidates the Section 5 assertion that %certified and Certified GridPG are invariant within the certified ball: the certified set is monotone increasing (I_x⊆I_{x+δ}), so the metrics can change. This is independent of the evaluation subset, code execution, or interpretability framing. If the authors intended the usual class-stability certificate without requiring the τ-threshold at the perturbed point, they must remove abstention from the output definition and state the radius as σΦ^{-1}(p_A); the current manuscript as written is not correct. For these reasons, I disagree with the reader's weakest_assumption identification: the top-K proxy concern is a scope caveat, while this is a direct falsification of the central theorem.","tokens_in":25942,"tokens_out":32079,"duration_ms":329185,"concrete_test":"Use the released code to compute, for every pixel certified as 1 or 0 at the default settings (σ=0.15, τ=0.75, R=0.10), the one-sided lower confidence bound p_A^- on the binary class probability. For each such pixel, compare the threshold-stability radius r_i = σ(Φ^{-1}(p_A^-) - Φ^{-1}(τ)) with 0.10 and report the fraction of certified pixels with r_i < 0.10. If any exists, its label can become ⊘ at a perturbation inside the certified ball, falsifying the certificate as stated. Independently, an analytical counterexample suffices: take a one-pixel binary function whose class-1 set is a half-space of measure 0.76; then hbar(x)=1 but hbar(x+δ)=⊘ for ||δ||_2=0.09<R, contradicting Theorem 3.1.","verdict_should_be":"REJECT","load_bearing_attack":"The central guarantee rests on Theorem 3.1, which claims that for every non-abstaining pixel at x, the abstaining smoothed function gτ from Eq. 3 satisfies gτ_i(x+δ)=gτ_i(x) for all ||δ||_2 < σΦ^{-1}(τ). This is not true for the gτ defined in the paper. For a binary pixel with top-class probability p_A(x)=0.76 and τ=0.75, the eligibility condition p_A(x)>τ holds, so the pixel is certified as, say, class 1. The Neyman-Pearson worst case for a perturbation of l2 norm 0.09 (which is below R=σΦ^{-1}(τ)=0.10 at σ=0.15) gives p_A(x+δ)=Φ(Φ^{-1}(0.76)-0.09/0.15)=Φ(0.706-0.600)=Φ(0.106)=0.542. Since 0.542<0.75 and the complementary class probability is 0.458<0.75, Eq. 3 returns ⊘ at x+δ, not 1. Thus the equality asserted in Theorem 3.1 fails even inside the claimed radius. The correct class-stability radius for this pixel is σΦ^{-1}(p_A), not σΦ^{-1}(τ); alternatively, to preserve the τ-threshold the radius must be σ(Φ^{-1}(p_A)-Φ^{-1}(τ)), which can be much smaller. Because all certified maps and the Section 5 claim that %certified and Certified GridPG are invariant within the ball rely on Theorem 3.1, the central claim that a pixel certified '1' or '0' at x remains '1' or '0' at x+δ is not established as stated.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a certification method for pixel-level robustness of post-hoc attribution maps. The authors binarize attribution maps by labeling the top K% of pixels as 'important' and the rest as 'not important', smooth the resulting binary map with Gaussian noise, and then apply randomized smoothing for segmentation to label each pixel as certified '1', certified '0', or abstaining. They introduce three evaluation metrics—%certified, Certified GridPG, and a deletion-based faithfulness score—and report an extensive comparison of 12 attribution methods on 5 ImageNet classifiers. The central claim is that any black-box attribution method can be wrapped so that the binarized importance label of every certified pixel is provably invariant under l2-bounded input perturbations.","tokens_in":26321,"tokens_out":18494,"duration_ms":170532,"significance":"The conceptual reduction of attribution certification to binary segmentation certification is elegant, and the experimental breadth (12 methods, 5 models, multiple layers and sparsification levels) is commendable. The proposed metrics are natural and would be useful if the underlying certificates were valid. The paper is clearly written and provides a code link, and the reformulation of sparsified attributions as a segmentation problem is a simple but productive idea. However, the central theoretical guarantee, Theorem 3.1, is incorrect as stated, and this undermines the quantitative evaluation built on it. If the radius issue is corrected and the experiments are recomputed, the framework could be a valuable contribution to certified explainability.","major_comments":[{"comment":"Theorem 3.1 is false as stated for the abstaining smoothed function g_tau defined in Eq. (3). The radius R = sigma * Phi^{-1}(tau) does not guarantee that the top-class probability remains above tau; it only bounds the classification margin under the assumption p_A > tau. For a binary pixel with p_1(x) = 0.76, tau = 0.75, and sigma = 0.15, the paper's radius is R = 0.101, but at ||delta||_2 = 0.09 the Neyman-Pearson lower bound is p_1(x+delta) >= Phi(Phi^{-1}(0.76) - 0.09/0.15) = Phi(0.706 - 0.600) = Phi(0.106) = 0.542, which is below tau. Hence Eq. (3) returns the abstain symbol at x+delta even though the pixel was certified as '1' at x, so the asserted equality g_tau_i(x+delta) = g_tau_i(x) fails. The correct radius preserving non-abstention is per-pixel and equals sigma * (Phi^{-1}(p_A(x)) - Phi^{-1}(tau)) in the binary case, which tends to zero as p_A approaches tau. The fixed radius R = sigma * Phi^{-1}(tau) used throughout the paper is therefore not a valid certificate for the declared guarantee.","section":"3.2, Theorem 3.1, Eq. (3)"},{"comment":"Because Theorem 3.1 is invalid, the quantitative evaluation built on it does not certify the claimed property. Section 6 states that 'all certified results are robust with confidence 1-alpha w.r.t the radius R=0.10', but with a correct per-pixel radius each pixel is certified only up to its own radius, and pixels with p_A just above tau have certified radius near zero. Consequently, the %certified and Certified GridPG scores in Figures 5-7 and the appendix do not report certified robustness at the stated radii, and the comparative conclusions (e.g., that LRP and RISE strike the best balance) may change when valid per-pixel certificates are used. The experiments need to be recomputed with the corrected radius definition.","section":"5, 6, 7"},{"comment":"The Monte Carlo confidence statement is incomplete. The paper sets n=100 and alpha=0.001 but does not describe how a lower confidence bound on the top-class probability is obtained before applying the radius formula. With n=100, a nominal confidence level of 0.999 requires a substantial margin between the observed frequency and the threshold tau; using point estimates or an unspecified estimator would void the 'with confidence 1-alpha' claim. The certification procedure must specify the confidence-bound computation, especially because the corrected per-pixel radius depends directly on the estimated p_A.","section":"6"}],"minor_comments":[{"comment":"The sparsification parameter K is defined for K in [50,100], but the experiments use K=30, 10, and 5; the admissible range should be clarified or extended to (0,100].","section":"4.1"},{"comment":"Several appendix figure captions (e.g., Figures 15-18) refer to 'certified radiusK' where the correct term is 'certified radius R'.","section":"Appendix E"},{"comment":"The contributions list contains a typo: 'trustworhty' should be 'trustworthy'.","section":"1"},{"comment":"The abbreviation 'SS' is used without a formal definition in the main text; it should be defined when first introduced.","section":"7.1"}],"recommendation":"major_revision","confidential_remarks":"The central theorem error is significant but correctable in principle: replacing the fixed radius with a per-pixel radius derived from the estimated top-class probability would restore the validity of the framework, though it requires recomputing all empirical results and likely changes the quantitative conclusions. I therefore recommend major revision rather than rejection. The paper cites the original Fischer et al. theorem; the authors should carefully verify the exact statement and conditions of that theorem in their revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is the hard part: Theorem 3.1 claims a radius R = σΦ⁻¹(τ) for the abstaining smoothed function in Eq. 3, but that radius does not control the abstention threshold. Take a pixel with top-class probability p_A = 0.76, τ = 0.75, σ = 0.15. The claimed radius is 0.10, but a perturbation of norm 0.09 can push the worst-case p_A down to about 0.54, so Eq. 3 returns ⊘, not the original label. The output changes inside the claimed ball. The correct radius for the abstaining function is σ(Φ⁻¹(p_A) − Φ⁻¹(τ)), which is far smaller; if you drop the abstention threshold, the class-stability radius is σΦ⁻¹(p_A). The paper's central guarantee is therefore false as stated.\n\nWhat is genuinely new: recasting attribution maps as binary segmentations and applying per-pixel randomized smoothing is a natural and useful idea, and this is the first per-pixel certification for black-box attribution methods. The empirical work is extensive: 12 methods across 5 models, multiple layers, several radii and sparsification levels, plus code. The proposed metrics—%certified, Certified GridPG, and the faithfulness score—are reasonable and provide a way to compare methods.\n\nThe soft spots beyond the broken theorem: the default τ = 0.75 is partly chosen because it boosts Certified GridPG (App. C), which is tuning on the evaluation criterion; the evaluation uses only 100 high-confidence images with no error bars; and the abstract and conclusion overclaim by saying “certified attributions” when only the binarized top-K labels are certified, not the attribution scores. These are secondary to the theorem issue.\n\nThe reader's conditional verdict is more generous than mine: the theorem flaw is load-bearing, not cosmetic. The paper needs a corrected radius—or a revised smoothed function—and the experiments redone. That said, the idea is worth pursuing and the error is fixable. I'd send it to peer review with a strong request to fix the central theorem before acceptance; as is, the main claim is unsubstantiated.","headline":"The central certified radius is invalid for the abstaining smoothed function, so the paper's main guarantee does not hold as stated.","tokens_in":26840,"tokens_out":6451,"would_cite":false,"duration_ms":61261,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that any black-box attribution method can be smoothed and binarized so that every pixel receives a provably stable important/unimportant label inside an ℓ2 ball around the input, making explanation robustness a per-pixel…","keywords":["certified robustness","randomized smoothing","pixel-level attribution","explainable AI","saliency maps","segmentation certification","ImageNet","layer-wise relevance propagation"],"falsifier":"Sample many perturbations δ with ‖δ‖₂ ≤ R around certified images and record how often a certified pixel changes label or the model's predicted class changes: a flip rate above the advertised α=0.001 would break the statistical guarantee, and any prediction flip inside the ball while the certified map stays identical would expose that the certificate attests to the explanation but not to the decision it explains. At the assumption level, take a pair of images whose top-K% binary maps coincide but whose attribution magnitudes or sign patterns point to different evidence, and check whether the certified maps are treated as equally faithful by a deletion test.","tokens_in":25742,"feed_emoji":"🛡️","tokens_out":9890,"duration_ms":90605,"temperature":0.7,"pith_summary":"This paper takes on a known failure mode of neural-network explanations: tiny, imperceptible input perturbations can completely reshuffle an attribution map while the prediction is unchanged. It claims that pixel-level robustness can be guaranteed for any black-box attribution method by sparsifying the map into the top-K% important pixels and smoothing it with Gaussian noise, which turns explanation into segmentation and lets an existing certified-segmentation theorem issue per-pixel guarantees. Within the certified ℓ2 ball, each pixel is labeled important, unimportant, or abstain, and the label is provably stable. Across 12 attribution methods and 5 ImageNet classifiers, the certificates are far from vacuous: most methods certify a useful fraction of pixels, and LRP and RISE achieve the best balance on the paper's three metrics of robustness, localization, and faithfulness. If the claims are right, any explanation pipeline can be upgraded to output maps that carry per-pixel stability guarantees usable in downstream tasks.","feed_headline":"Pixel-level certificates prove explanations stay put under noise","feed_subtitle":"Randomized smoothing turns any attribution map into a per-pixel robustness guarantee.","key_machinery":"The load-bearing construction is the composition of two maps. Sparsification h_K thresholds an attribution map by relative rank — pixels in the top K% become 1, the rest 0 — which is what makes the output a two-class segmentation map rather than a vector of real values. The smoothed sparsified attribution h̄_{τ,K} then applies the randomized-smoothing-for-segmentation recipe: for each pixel, Monte Carlo sampling estimates the probability that it is 1 under Gaussian input noise, and the pixel is certified when that probability beats threshold τ, with radius R = σΦ⁻¹(τ) coming from the standard Gaussian CDF. This identity — smoothed sparsified attribution equals smoothed segmentation — is what lets a theorem proven for segmentation models carry over to explanations unchanged. The empirical evaluation is carried by three metrics the paper defines: %certified (coverage), Certified GridPG (localization within 2×2 image grids), and deletion-based faithfulness (class-confidence drop when certified pixels are removed).","core_discovery":"The central claim is that pixel-level attribution robustness reduces to a segmentation-certification problem. Given any attribution map h(x), the paper binarizes it by rank: the top K% of values become 1, the rest 0, producing a sparsified map h_K. Its Gaussian-smoothed version h̄_{τ,K} estimates, per pixel, the probability that the pixel keeps its class under input noise, and certifies the pixel as '1' or '0' when that probability exceeds τ, otherwise abstaining. Because h̄_{τ,K} is exactly a smoothed segmentation model, the randomized-smoothing theorem applies verbatim: every non-abstaining pixel keeps its certified label for all perturbations within radius R = σΦ⁻¹(τ), with confidence 1−α from Monte Carlo estimation. The paper then compares 12 attribution methods on 5 ImageNet models with three new metrics — %certified, Certified GridPG, and deletion faithfulness — and reports that LRP and RISE dominate the robustness-localization-faithfulness trade-off, with final-layer attributions generally certifying better than input-layer ones.","pith_inferences":["The certificate can outlive the decision: nothing in the framework prevents the model's predicted class from changing inside the certified ball, so a certified map may stay intact for a prediction the model no longer makes. A natural extension is to certify the joint object (prediction, explanation), or to condition the certificate on the predicted class.","The construction only needs black-box access plus a smoothing distribution, so the same scheme should transfer to ℓ1 or ℓ∞ balls by swapping Gaussian noise for Laplacian or uniform noise — the segmentation theorem carries over with the corresponding level-set radius and inverse CDF.","Binarizing by rank discards the sign and magnitude structure of attributions, which matters for methods like LRP where positive and negative relevance carry distinct semantics; a testable extension is to certify the signed evidence structure, separating certified positive from certified negative pixels."],"forward_implications":["Any black-box attribution method can be wrapped to emit per-pixel certificates — important, unimportant, or abstain — with the label provably fixed for every ℓ2 perturbation inside radius R = σΦ⁻¹(τ).","Certified maps are immediately usable in downstream tasks: the paper produces the first such maps and shows that deleting LRP/RISE certified pixels collapses class confidence, so the certified pixels are the ones the model truly leans on.","Attribution families differ sharply in certifiability: IxG and IntGrad certify almost no input-layer pixels, while LRP and RISE certify across radii, models, and layers, giving practitioners a principled way to pick an explainer.","The certification is tunable: raising the threshold τ or lowering K trades coverage for precision, so users can dial in how conservative their stability guarantee is.","Final-layer explanations certify better than input-layer ones across nearly all methods, pointing to coarse, high-level attribution maps as the more certifiable target."],"supporting_citations":[{"why":"Supplies Theorem 3.1, the segmentation randomized-smoothing certificate that the paper applies verbatim to sparsified attributions.","marker":"(Fischer et al., 2021)"},{"why":"Establishes the base classification randomized-smoothing guarantee and the Gaussian CDF radius formula R = σΦ⁻¹(p_A).","marker":"(Cohen et al., 2019)"},{"why":"Cited as the framework for certifying high-dimensional segmentation outputs against ℓ2 perturbations, building the bridge between attributions and segmentation.","marker":"(Anani et al., 2024)"},{"why":"First to certify a top-k similarity between sparsified smoothed attributions; supplies the sparsify-before-smooth idea this work extends to per-pixel certificates.","marker":"(Levine et al., 2019)"},{"why":"Provides tighter Rényi-DP bounds and ℓp-norm generalization, plus the observation that sparsification improves certifiable robustness.","marker":"(Liu et al., 2022)"},{"why":"Defines the Grid Pointing Game localization metric that Certified GridPG extends to certified pixels.","marker":"(Bohle et al., 2021)"},{"why":"Defines RISE, one of the two best-performing certified methods, and the deletion-based evaluation the faithfulness score builds on.","marker":"(Petsiuk et al., 2018b)"},{"why":"Defines LRP, the other best-performing method, evaluated with the specified propagation rules in Appendix A.1.","marker":"(Bach et al., 2015)"}],"fun_headline_variants":["Pixel-level robustness certificates for any attribution method","Randomized smoothing certifies pixel importance under noise","Certified pixel attributions: robust to invisible perturbations","Guarantee which pixels matter in explanations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the relative rank of attribution values — which pixels land in the top K% — is what an explanation means, so that certifying a binarized, noise-smoothed version of a map certifies the explanation itself: if the absolute values or the positive/negative evidence structure carry the information, the certificate protects a thresholded proxy, and it also says nothing about whether the model's prediction itself stays fixed inside the certified ball.","fun_headline_variants_meta":{"raw":{"variants":["Pixel-level robustness certificates for any attribution method","Randomized smoothing certifies pixel importance under noise","Certified pixel attributions: robust to invisible perturbations","Guarantee which pixels matter in explanations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000417,"raw_usage":{"total_tokens":2139,"prompt_tokens":920,"completion_tokens":1219,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":536,"completion_tokens_details":{"reasoning_tokens":1173}},"tokens_in":536,"tokens_out":1219,"duration_ms":8896,"temperature":1.0,"reasoning_tokens":1173,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:34:33.562306+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Sample many perturbations δ with ‖δ‖₂ ≤ R around certified images and record how often a certified pixel changes label or the model's predicted class changes: a flip rate above the advertised α=0.001 would break the statistical guarantee, and any prediction flip inside the ball while the certified map stays identical would expose that the certificate attests to the explanation but not to the decision it explains. At the assumption level, take a pair of images whose top-K% binary maps coincide but whose attribution magnitudes or sign patterns point to different evidence, and check whether the certified maps are treated as equally faithful by a deletion test.","supporting_citations":[{"cited_title":"Scalable certified segmentation via randomized smoothing","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 3.1, the segmentation randomized-smoothing certificate that the paper applies verbatim to sparsified attributions."},{"cited_title":"Adaptive hierarchical certification for segmentation using randomized smoothing","cited_arxiv_id":null,"evidence_quote":"Cited as the framework for certifying high-dimensional segmentation outputs against ℓ2 perturbations, building the bridge between attributions and segmentation."},{"cited_title":"Certifiably robust interpretation via r \\'e nyi differential privacy","cited_arxiv_id":null,"evidence_quote":"Provides tighter Rényi-DP bounds and ℓp-norm generalization, plus the observation that sparsification improves certifiable robustness."},{"cited_title":"Convolutional dynamic alignment networks for interpretable classifications","cited_arxiv_id":null,"evidence_quote":"Defines the Grid Pointing Game localization metric that Certified GridPG extends to certified pixels."},{"cited_title":"On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation","cited_arxiv_id":null,"evidence_quote":"Defines LRP, the other best-performing method, evaluated with the specified propagation rules in Appendix A.1."}],"review_version":2}