# On the Complexity-Faithfulness Trade-off of Gradient-Based Explanations

arXiv: https://arxiv.org/abs/2508.10490 · HTML: https://mlsanity.com/paper/2508.10490/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 64 references that are in the map.
- First posted on arXiv 14 Aug 2025.

## Builds on (most cited first, 30 of 46)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization](https://mlsanity.com/paper/1610.02391/) (2016)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [On the Spectral Bias of Neural Networks](https://mlsanity.com/paper/1806.08734/) (2018)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [SmoothGrad: removing noise by adding noise](https://mlsanity.com/paper/1706.03825/) (2017)
- [Striving for Simplicity: The All Convolutional Net](https://mlsanity.com/paper/1412.6806/) (2014)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Captum: A unified and generic model interpretability library for PyTorch](https://mlsanity.com/paper/2009.07896/) (2020)
- [A Benchmark for Interpretability Methods in Deep Neural Networks](https://mlsanity.com/paper/1806.10758/) (2018)
- [Visual Transformers: Token-based Image Representation and Processing for Computer Vision](https://mlsanity.com/paper/2006.03677/) (2020)
- [The (Un)reliability of saliency methods](https://mlsanity.com/paper/1711.00867/) (2017)
- [Not Just a Black Box: Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1605.01713/) (2016)
- [Explaining by Removing: A Unified Framework for Model Explanation](https://mlsanity.com/paper/2011.14878/) (2020)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Sensitivity and Generalization in Neural Networks: an Empirical Study](https://mlsanity.com/paper/1802.08760/) (2018)
- [Evaluating and Aggregating Feature-based Model Explanations](https://mlsanity.com/paper/2005.00631/) (2020)
- [Generalization in diffusion models arises from geometry-adaptive harmonic representations](https://mlsanity.com/paper/2310.02557/) (2023)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [The Shattered Gradients Problem: If resnets are the answer, then what is the question?](https://mlsanity.com/paper/1702.08591/) (2017)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [Guided Integrated Gradients: An Adaptive Path Method for Removing Noise](https://mlsanity.com/paper/2106.09788/) (2021)
- [Benchmarking Attribution Methods with Relative Feature Importance](https://mlsanity.com/paper/1907.09701/) (2019)
- [B-cos Networks: Alignment is All We Need for Interpretability](https://mlsanity.com/paper/2205.10268/) (2022)
- [Which Explanation Should I Choose? A Function Approximation Perspective to Characterizing Post Hoc Explanations](https://mlsanity.com/paper/2206.01254/) (2022)
- [On the Similarity between the Laplace and Neural Tangent Kernels](https://mlsanity.com/paper/2007.01580/) (2020)

## Built on by (most cited first, 2 of 2)

- [Improving Adversarial Robustness of Attribution via Implicit Regularization](https://mlsanity.com/paper/2605.29983/) (2026)
- [Grad-CAM for Vision Transformers: A Systematic Taxonomy and Audit of Methodological Ambiguity in Explainable AI](https://mlsanity.com/paper/2608.05258/) (2026)

## Abstract (arXiv)

ReLU networks, while prevalent for visual data, have sharp transitions, sometimes relying on individual pixels for predictions, making vanilla gradient-based explanations noisy and difficult to interpret. Existing methods, such as GradCAM, smooth these explanations by producing surrogate models at the cost of faithfulness. We introduce a unifying spectral framework to systematically analyze and quantify smoothness, faithfulness, and their trade-off in explanations. Using this framework, we quantify and regularize the contribution of ReLU networks to high-frequency information, providing a principled approach to identifying this trade-off. Our analysis characterizes how surrogate-based smoothing distorts explanations, leading to an ``explanation gap'' that we formally define and measure for different post-hoc methods. Finally, we validate our theoretical findings across different design choices, datasets, and ablations.