Research map / Label-efficient and robust learning / Recognition and long-tail
Benchmarking Deletion Metrics with the Principled Explanations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes TRACE, a combinatorial-optimization framework (simulated annealing with greedy baseline) that finds near-optimal deletion trajectories to serve as a principled explanation and to benchmark insertion/deletion metric settings on ImageNet CNNs.
Problem
Insertion/deletion metrics for attribution methods are widely used but their settings (reference values, LeRF/MoRF criterion, feature size, logit vs probability) are poorly understood, and evaluating them with existing explanation methods is circular and suffers from the out-of-distribution issue.
Approach
Reformulate the deletion metric's optimal explanation as a finite combinatorial optimization over permutations (trajectories) of features, solved with simulated annealing and greedy search, and validate near-optimality by squeezing between a complete-search lower bound and the greedy/SA upper bound.
Key results
- TRACE-SA is nearly indistinguishable from the complete-search lower bound on a 4x4 patch setting, while TRACE-Greedy is slightly worse, bounding the global optimum tightly.
- On ILSVRC2012 with ResNet-18 and zero reference, TRACE-y/p reach LeRF-MoRF probability AUC differences of 24.98/31.69 versus 10-16 for the best attribution method (Grad-CAM 16.24).
- Using superpixel patches (e.g., 7x7) and LeRF-MoRF criterion, the paper finds reference-value choice has negligible influence on TRACE scores, while smaller patches increase OOD sensitivity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TRACE-p instead of Grad-CAM | ResNet-18 deletion evaluation · ImageNet-1k, zero reference | LeRF–MoRF probability AUC difference: 16.24 -> 31.69 | Helped |
| Use TRACE-p instead of Grad-CAM | ResNet-18 deletion evaluation · ImageNet-1k, mean reference | LeRF–MoRF probability AUC difference: 16.22 -> 32.51 | Helped |
| Use TRACE-p instead of Grad-CAM | ResNet-18 deletion evaluation · ImageNet-1k, blurring reference | LeRF–MoRF probability AUC difference: 17.38 -> 33.84 | Helped |
| Optimize using probabilities rather than logits (ablation) | TRACE on ResNet-18 · ImageNet-1k, zero reference | LeRF–MoRF probability AUC difference: 24.98 -> 31.69 | Helped |
| Use superpixel patches rather than pixel-wise deletion (ablation) | TRACE deletion evaluation · ImageNet-1k | prediction robustness to random deletion | Helped |
| Use LeRF rather than MoRF (ablation) | TRACE deletion evaluation · ImageNet-1k | resistance to OOD-induced prediction decline | Helped |
| Combine LeRF and MoRF using the LeRF−MoRF objective (ablation) | TRACE deletion evaluation · ImageNet-1k | consistency across LeRF and MoRF tests | Helped |
| Use simulated annealing instead of greedy optimization (ablation) | TRACE · ImageNet-1k, 16 patches | deletion objective | Helped |
| Use TRACE-SA rather than TRACE-Greedy (ablation) | TRACE · ImageNet-1k, 16 patches | closeness to complete-search bound | Helped |
Surprising findings
- Existing attribution methods can be outperformed by a large margin, and model probability can increase when unimportant features are deleted under TRACE.
- MoRF-based criteria are severely affected by OOD; TRACE-Mo performs very poorly under the LeRF test.
Limitations
- TRACE is NP-hard and SA/Greedy only approximate the global optimum
- Experiments limited to image classification on ImageNet with superpixel patches
- Global optimum is inaccessible, so near-optimality is verified only via bounds
Experimental setup
Datasets: ImageNet-1k (ILSVRC2012) validation set
Benchmarks: ILSVRC2012 deletion/insertion tests
Metrics: AUC of predicted probability under LeRF and MoRF AUC of logits under LeRF and MoRF difference between LeRF and MoRF AUCs
Baselines: Gradient Grad-CAM IBA RISE Extremal Perturbation Excitation Backprop Integrated Gradient Input x Gradient TRACE-Greedy Complete Search
Builds on: Insertion/deletion metrics (Petsiuk et al., 2018) ROAR (Hooker et al., 2019) ROAD (Rong et al., 2022) Simulated annealing (Kirkpatrick et al., 1983) SHAP (Lundberg & Lee, 2017)
Closest papers by meaning
- The Out-of-Distribution Problem in Explainability and Search Methods for Feature Importance Explanations (NeurIPS 2021 · similarity 0.86)
- Synthetic Benchmarks for Scientific Research in Explainable Machine Learning (NeurIPS 2021 · similarity 0.85)
- Regional Explanations: Bridging Local and Global Variable Importance (NeurIPS 2025 · similarity 0.83)
- Feature Attribution with Necessity and Sufficiency via Dual-stage Perturbation Test for Causal Explanation (ICML 2024 · similarity 0.82)
- Benchmarking the Attribution Quality of Vision Models (NeurIPS 2024 · similarity 0.82)
- Taming Hyperparameter Sensitivity in Data Attribution: Practical Selection Without Costly Retraining (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.