On the Complexity-Faithfulness Trade-off of Gradient-Based Explanations
Amir Mehrpanah, Matteo Gamba, Kevin Smith, Hossein Azizpour · 2025
Read On the Complexity-Faithfulness Trade-off of Gradient-Based Explanations by Amir Mehrpanah, Matteo Gamba, Kevin Smith, Hossein Azizpour (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-10490.txt.
Introduction
Amir Mehrpanah, Matteo Gamba, Kevin Smith, and Hossein Azizpour measure the trade-off between simple and faithful AI explanations in a 2025 paper. Gradient-based explanations of image networks are noisy, because the networks can hinge on single pixels. Popular fixes smooth the explanation with a stand-in model, but smoothing can distort what the network really did.
The authors build a spectral framework that scores smoothness and faithfulness on common ground. With it, they quantify how much of the distortion comes from the network's own high-frequency behavior. They define an explanation gap and measure it across methods. Experiments over design choices, data sets, and ablations back the theory. The aim is principled control of explanation quality rather than eyeballing heat maps.
Catalog record
| CREATOR | Amir Mehrpanah, Matteo Gamba, Kevin Smith, Hossein Azizpour |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-10490
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Complexity-Faithfulness Trade-off of Gradient-Based Explanations Amir Mehrpanah, Matteo Gamba, Kevin Smith, Hossein Azizpour Abstract 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. 1 1 1 https://github.com/Amir-Mehrpanah/On-the- Complexity-Faithfulness-Trade-off-of-Gradient- Based-Explanations-ICCV25/ 1 Introduction The growing complexity of deep networks necessitates explainability, especially in safety-critical applications. Gradient-based explanation methods are widely used in computer vision for this aim. These methods, however, suffer from two main shortcomings: lack of smoothness or faithfulness , the trade-off of which is the focus of our study. Explanation complexity. A crucial property for explanations to be human-understandable is their simplicity, which translates to smoothness 2 2 2 We may refer to smoothness and complexity interchangeably. in saliency-based explanations. However, both theoretical [ 19 , 28 ] and empirical [ 47 , 54 ] studies suggest that ReLU networks, the most common variant of deep networks used for visual data, have sharp transitions, sometimes relying on individual pixels for predictions [ 57 ] . This sharpness can result in complex gradient-based explanations that hinder interpretability. Thus, as our preliminary step, we establish a formal connection between a network’s architecture and complexity of its explanations. With this formalism, we particularly study ReLU networks. Explanation faithfulness. To reduce the explanation complexity, post-hoc techniques produce smooth surrogates during the explanation phase [ 41 ] , at the cost of lower faithfulness to the original network, leading to an inherent trade-off between explanation complexity and faithfulness. Therefore, it is vital to carefully consider this trade-off when developing, choosing, or using post-hoc methods [ 23 , 1 ] . While several metrics are proposed to measure complexity ( e.g . , entropy-based methods [ 6 ] ) and faithfulness ( e.g . , pixel removal scores [ 6 ] ), these metrics disjointly measure one of the two aspects and are influenced by extraneous factors such as the choice of baseline and removal order [ 60 , 33 ] . These caveats of existing metrics impede a principled analysis of the complexity-faithfulness trade-off [ 46 , 14 ] . Our goal is to formally study this trade-off. Specifically, we introduce consistently-defined measures of complexity and faithfulness with which we empirically analyze the existing post-hoc explanation methods, and our method of mitigation of sharpness in ReLU networks. Our Approach. We adopt a spectral perspective to formally establish a relationship between a network’s architecture and its gradient-based explanation. We first measure explanation complexity via spatial high-frequency content of input gradients ( Section 3.2 ), and formally link it to the high-frequency components, or sharp changes, of a network ( Section 3.3 ). This connection, importantly, allows for characterization and improvement of network architectures for their explanation complexity, which we showcase in Section 3.4 . Finally, in Section 4 , we leverage our formalism in a unified framework to analyze the complexity-faithfulness trade-off, i.e . , by measuring complexity as “expected frequency” and faithfulness as the “gap” in the expected frequency of the original and surrogate functions. We use this framework to analyze (smoothed versions of) ReLU networks and various post-hoc explanations; see Fig. 1 . (a) Input (b) ReLU:VG (c) ReLU:SG (d) \operatorname{SP}(\beta=.9) :VG (e) \operatorname{SP}(\beta=.9) :SG (f) Figure 1 : Exploring the Faithfulness-Complexity Trade-Off. This figure shows the trade-off typically made between faithfulness and complexity in post-hoc explanation methods. (b) presents VanillaGrad (VG) explanations for a ReLU network, which appear grainy due to the network’s reliance on high-frequency information. To mitigate this, post-hoc methods like SmoothGrad (SG), shown in (c) , remove high-frequency components by creating surrogates, thereby introducing a trade-off between complexity and faithfulness, quantified by \operatorname{EF} and \Delta\operatorname{EF} , respectively. This trade-off for a ReLU network is represented by the dashed blue line in (f) . In this work, we propose a framework which can control a ReLU network’s reliance on high-frequency information by modifying the tail of its power spectrum. This is achieved by training a network with a smooth parameterization (SP) of ReLU, obtained by convolving ReLU with a Gaussian function, where the standard ReLU corresponds to \beta\to\infty . (d) and (e) show the VG and SG explanations for such a network, denoted as \operatorname{SP}(\beta=0.9) . As shown, reducing the network’s dependence on high-frequency components leads to VG explanations with lower complexity, enabling alternative trade-offs. One such trade-off is depicted by the dashed orange line in (f) —see Fig. 14 for more examples. Our Contributions. We summarize in the following list: • A Framework for Formal Analysis: We introduce a framework based on a formal connection between a network’s power spectrum tail and the complexity of its explanations, which provides a foundation for analyzing the complexity-faithfulness trade-off. Using this framework, we analyze the role of ReLU in inducing sharp transitions in the network, leading to complex explanations. • The Expected Frequency (EF): We introduce a metric to quantify a network’s reliance on high-frequency information. We reduce EF by convolving ReLU with a Gaussian function, hence controlling the complexity of VanillaGrad explanations ( Section 3 ). • The Explanation Gap: We introduce the “explanation gap” , a measure for quantifying the discrepancy between explanations produced for surrogates and the original model, highlighting potential faithfulness risks associated with post-hoc explanation methods, in Section 4 . • Empirical Validation: We empirically validate our theoretical contributions across various datasets of varying input sizes, such as ImageNet, Imagenette, CIFAR10, and Fashion-MNIST. Moreover, we conduct several ablation studies, in Appendix B , including the effect of other design decisions such as skip connections and batch norm. 2 Related Works Although inherent and post-hoc explainability are distinct concepts [ 48 ] , both can rely on gradients as their explainer, as seen in methods like B-cos [ 11 ] and Integrated Gradients [ 58 ] , respectively. We focus on methods that utilize gradients as their explainer, without making a distinction between post-hoc or inherent explainability. 2.1 Explanation for Smooth Surrogates Our work is related to research on explainability methods that incorporate smooth surrogates, either as part of their design or in post-processing. Whether explicit or implicit, a common part in these methods is the use of smooth surrogates to improve visual quality. One approach to creating smooth surrogates is through a perturbation distribution , which can involve noise in the input space [ 54 ] , noise in the parameter space [ 10 ] , input space traversal [ 31 , 49 ] , spatial Gaussian blur [ 11 ] , or removing negative gradient values [ 32 , 55 ] . Another method for creating surrogates is by using subnetworks , as in