SHAP values via sparse Fourier representation

We sincerely thank the reviewer for the positive and encouraging feedback. We are especially grateful for the recognition of the novelty in using sparse Fourier representations to compute SHAP values efficiently, as well as for the kind words on the clarity of the paper, theoretical contributions, and experimental validation. We also discuss points mentioned by the reviewer below.

SHAP Values of One-hot Encoded Features: We used the SHAP values of the individual one-hot components separately for each category and compared them across methods. We will clarify this in the paper to avoid confusion and make our evaluation choices more transparent.

Generalization to Continuous Features: As for continuous features, we agree this is an interesting direction for future work. In Appendix F.1, we discuss possible extensions for this purpose such as quantization. The challenge lies in the trade-off between discretization granularity and computational cost. Since the dimensionality increases with finer quantization, this has non-trivial impact on runtime and approximation error.

However, while interesting, we focus the scope of our work to discrete features, for which we can also provide theoretical guarantees and empirical validation. We think even for the discrete setting, our work proposes a SOTA method for computing accurate SHAP values efficiently and therefore makes for a strong algorithmic contribution.

Practical Significance of Speedups over KernelSHAP: Below we report the absolute runtimes of KernelSHAP (in seconds) on the SGEMM dataset across varying sizes of the query and background sets.

The first table corresponds to the same settings used in the main paper, where background sizes were kept relatively small. This decision was made intentionally: during experimentation, we observed that larger background sizes caused LinregSHAP and KernelSHAP to become prohibitively slow, making it impractical to include full-scale results across datasets and seeds. Despite this limitation, our method already achieved orders-of-magnitude speedups.

KernelSHAP Runtime (Main Paper Setup)

To further emphasize the practical gains of FourierSHAP, we conducted additional experiments for this rebuttal with significantly larger query and background sets, closer to what might be used in real-world deployments. Despite the background dataset still being modest in size (100–400), KernelSHAP runtimes quickly increase to minutes, while FourierSHAP continues to run in milliseconds.

KernelSHAP Runtime (Larger Setup)

FourierSHAP Runtime (Same Setup, in milliseconds)

These results reinforce that our reported relative speedups (often 100×–10,000×) translate into meaningful real-world runtime improvements. We will include both tables in the final version for completeness.

Positioning of FourierSHAP vs. Multivariate Function Decomposition: Although we agree that low-order additive decompositions can yield computational benefits, it is unclear which specific work is being referred to. If the reviewer could point us to a particular method in mind, we could clarify how our approach compares.

We hope our response addresses the concerns raised by the reviewer, and we are happy to engage in further discussions.

We sincerely thank the reviewer for their assessment. We are pleased that the key strengths of the paper, namely, the theoretical novelty of the closed-form SHAP expression, the principled use of Fourier sparsity, and the empirical demonstration of substantial computational gains, were clearly recognized. We also appreciate the reviewer’s perspective on our contribution to Explainable AI and its potential impact on game theory, as well as the validation of our assumptions on spectral sparsity in real-world models.

Regarding the clarity of Section 4: we fully agree that the presentation is dense. This section introduces the main result, i.e., the closed-form SHAP expression in the Fourier basis, which is mechanically derived and is notationally heavy. The derivation relies on a sequence of algebraic manipulations and combinatorial identities that are correct but offer little in terms of intuition. For this reason, we chose to move the full derivation to Appendix B and keep the main text concise.

However, we understand that this may have made the exposition harder to follow, and we will revise this section in the final version to improve accessibility. Specifically, we will include a high-level walkthrough of the key steps of the proof and better guide the reader to the relevant appendix material.

We also want to reassure the reviewer that we have validated the correctness of the formula both theoretically and empirically. In Figure 5 located in the Appendix, we include experiments comparing our computed SHAP values against ground-truth values (computed via enumeration), which serve as an internal consistency check on the correctness of the formula.

Finally, we agree with the reviewer that the restriction to discrete inputs should be stated more clearly and prominently. Although we already mention this in Section 2.2 and dedicate Appendix F.1 to this topic, we will revise the introduction and abstract to explicitly highlight that the current theory is scoped to discrete features.

We are grateful for the reviewer’s valuable feedback, which we believe helps us improve the main text even further.

We are grateful for the positive and thoughtful assessment and happy to see that the reviewer finds our work both theoretically exciting and also having a strong experimental validation with significant speedups. We also acknowledge the weaknesses mentioned by the reviewer and discuss them below.

W1 - Discrete Input Assumption: We appreciate the reviewer drawing attention to the limitation of our method to discrete inputs, which is a key point we discuss in Appendix F.1 of the paper. There, we discuss possible extensions for this purpose such as quantization. The challenge lies in the trade-off between discretization granularity and computational cost. Since the dimensionality increases with finer quantization, this has non-trivial impact on runtime and approximation error. A true and general extension to continuous features (potentially involving new surrogate representations), remains an open and important direction for future work. We believe this requires a careful theoretical and empirical treatment.

We focus the scope of our work to discrete features, for which we have provided theoretical guarantees and empirical validation. We think even for the discrete setting, our work proposes a SOTA method for computing accurate SHAP values efficiently and therefore makes for a strong algorithmic contribution.

W2 - Spectral Sparsity Assumption: As the reviewer has thoughtfully pointed out the assumption of spectral sparsity is central to our method, and while it is theoretically and empirically supported for many real-world models (such as those presented in the paper), it is not always guaranteed. We have tried to be clear about this limitation and explained the scope of applicability in Section 3. Namely, we provided guarantees for the case of trees (Section 3.1), low-order functions (Proposition 1), MLPs (Section 3.2), and generic functions (Appendix A.2).

We also attempt to offer a broader intuitive argument in this rebuttal. Functions that only contain low-order interactions have a sparse Fourier spectrum by Proposition 2. We think low-order interactions is a useful inductive bias for models that can generalize well, especially when trained on limited data.

W3 - Limitations of NTK-based Justification for Spectral Bias: We thank the reviewer for raising this point. NTK theory was used primarily as a theoretical motivation in the specific context of MLPs. In Sections 3.1 and 4, we also cited empirical works that highlight spectral bias in fully connected neural networks. Additionally, the results shown in Figure 1 reflect this phenomenon in our own empirical studies.

Although NTK theory provides useful intuition in the lazy regime, we acknowledge its limitations and welcome deeper integration with insights from richer training regimes. We would be happy to consider incorporating additional references if there are particular works that the reviewer believes would help strengthen the motivation.

We appreciate the encouraging feedback from the reviewer and are excited to build on this work in future directions.

We thank the reviewer for their time and for thoughtful participation in our work. We appreciate the recognition of our method’s ability to compute exact SHAP values with orders-of-magnitude speedup through a sparse Fourier representation. Below are our responses to the concerns raised by the reviewer.

Positioning of FourierSHAP vs. FastSHAP: We thank the reviewer for pointing out this distinction. While FastSHAP amortizes the computation of SHAP values by learning a model that maps input features directly to SHAP values, it does so by implicitly learning both the surrogate and the SHAP estimator end-to-end. Therefore, errors in the final SHAP values can arise jointly from the model approximation and also SHAP estimation.

In contrast, FourierSHAP decouples these steps: we first approximate the original predictive model using a global sparse Fourier surrogate, and then compute the exact SHAP values of this surrogate. This separation allows us to provide theoretical guarantees and also fine-grained control of the surrogate approximation quality through the sparsity parameter.

Although different in structure, both methods aim to accelerate SHAP computation by orders of magnitude. Hence, we considered FastSHAP a relevant baseline for the empirical comparison. Moreover, we consider our method amortized, because the expensive training of the surrogate is done once and future evaluation of the SHAP value is, similar to FastSHAP, very fast. To re-iterate, we say the method is amortized because the upfront cost of training an expensive surrogate is done once and this cost is amortized over the large number of subsequent shap value predictions that are computationally extremely cheap.

Expressiveness of Surrogate Model: This is indeed an important point. We discuss this in Section 3.2 for the case of ensemble of tress and in Proposition 1 for the more general case of functions that can be decomposed as a sum of low order functions. For these classes of functions, the Fourier representation is exact, therefore we incur no approximation error in the SHAP values.

In addition to the points above, we also have a discussion in Section 3.1 on why our method can approximate MLP functions as well, and furthermore provided empirical experiments ourselves in Section 5, validating the approximation capabilities. Finally, in Appendix A.2 we have discussed the type of guarantees available for the surrogate function when approximating a generic black box. These are uniform bounds that bound the L2 norm of the error based on the spectrum of the function.

Positioning of FourierSHAP vs. TreeSHAP: We appreciate the reviewer raising this important point. Indeed, TreeSHAP allows exact SHAP computation for decision trees and is highly efficient. However, its applicability is limited to tree-based models.

FourierSHAP, in contrast, is model-agnostic and furthermore captures a broader class of functions. As mentioned above as well as in Section 3.2 and Proposition 1, trees and, more generally, low-order functions admit exact sparse Fourier representations. Therefore, FourierSHAP provides exact SHAP computation capability for the case of these models. Indeed, as shown in Figure 3, for decision trees, our method reproduces TreeSHAP outputs exactly but with order-of-magnitude speedups. Therefore, not only is our method exact for trees, it is also applicable to a broader class of models, and it is more computationally efficient. We believe this makes our method a better alternative for computing SHAP values.

Unnecessary Approximation of Trees: We would like to clarify that we did not approximate decision trees. We computed its Fourier transform exactly. The theory is detailed in Section 3.2. Thus, the surrogate is an exact representation, and the SHAP values derived from it are identical to those produced by TreeSHAP (see our response above to previous two concerns).

Naming of the Method: We appreciate the reviewer’s point and agree that terminology should be used carefully to avoid confusion. While Shapley values are rooted in cooperative game theory, the term SHAP values has become the standard when referring to their adaptation for feature attribution in machine learning models, as popularized by Lundberg and Lee [1]. We believe FourierSHAP is consistent with names in existing literature (e.g., KernelSHAP, TreeSHAP). We have addressed how feature attribution is related to cooperative games in Section 2.1.

In summary, our method enables efficient SHAP value computation by approximating the original model with a global Fourier surrogate. This approximation is exact for common classes such as ensembles of trees and other black-blox low-degree functions. The novelty lies in the closed-form SHAP computation in the Fourier basis, which, under sparsity assumptions, provides exact values and substantial computational gains. While the method can involve approximation of the underlying predictor, our focus is squarely on the accuracy and efficiency in the computation of the SHAP values themselves.

We hope that our detailed responses have addressed your concerns and clarified the contributions and scope of our work. If there are any remaining questions or further points to discuss, we would appreciate additional feedback otherwise we kindly ask you to please consider increasing your score.

[1] Lundberg, Scott M., and Su-In Lee. "A unified approach to interpreting model predictions." Advances in neural information processing systems 30 (2017).