Proxy-SPEX: Sample-Efficient Interpretability via Sparse Feature Interactions in LLMs

1. Thank you for your careful review as well as pointing out the relevant references [1] and [2]. Both should have been considered and we will add a discussion of both methods to the camera ready version.

2. Thanks, we will change $f$ to $\hat{f}$.

3. We will replace this with the more precise and correct statement. "where $\mathcal{F}_k$ denotes the set corresponding to the $k$ largest Fourier coefficients of $f$".

Other Questions: Fourier transforms as interaction importance scores: One way to think about why a Fourier coefficient corresponds to an importance is to think of the Fourier transform $F$ as a decomposition of the function. For any given set $T$, $F(T) = 0$ implies that the function does not depend jointly on the effect of the features in $T$. On the other hand, the existence of a non-linear effect between features in $T$ (for example, a synergistic effect), implies a non-zero Fourier coefficient. The Fourier coefficients (scaled by a factor of $-2$) also precisely correspond to the Banzhaf Interaction Index from game theory [a], and thus inherits all interpretations.

[a] Marichal, Jean-Luc, and Pierre Mathonet. "Weighted Banzhaf power and interaction indexes through weighted approximations of games." European journal of operational research 211.2 (2011): 352-358.

Thank you for your review. We clarify some of the main points below, and hope to convince you that this work meets the criteria for acceptance.

Relationship between SPEX and ProxySPEX: This was a common comment across many reviews. We will add a section carefully describing the relationship of the two approaches.

Note that SPEX and ProxySPEX differ significantly. The only common factors in these two methods are that they:

1. Both exploit an empirically observed structure (sparsity and low-degree) for SPEX and (sparsity, low-degree and hierarchy) for ProxySPEX.

2. Both ultimately generate a Fourier transform to approximate the model.

SPEX uses an algebraic structured sampling scheme, coupled with error correction decoding procedures to efficiently compute the interactions in the form of a Fourier transform. SPEX is a rather complex algorithm that involves many carefully designed components that work in concert to enable efficient estimation.

ProxySPEX, in contrast, is much simpler. ProxySPEX uses random samples to learn a GBT proxy model. We then apply an efficient method for computing the fourier transform of the GBT model to extract the most important interactions from the proxy model.

Comparison to other interaction methods: We stress that we believe the main advantage of ProxySPEX to be the scale at which it is able to operate. Due to this, we have primarily focus on comparing against other approaches that achieve scale, i.e., SPEX. As you suggested, we have conducted experiments that show that ProxySPEX also outperforms other approaches, even at smaller scales.

Below, we repeat the faithfulness experiments for Sentiment, with 20 new movie reviews with $n\in [16,32]$ words and $n\in [64,128]$ words. As in Section 4.1, we vary the number of inferences by $\alpha \cdot n \log_2(n)$ and compute the faithfulness. In addition to SPEX and LASSO, we consider Faith-Banzhaf Interaction Indices [1] of up to $k$th order, which were shown in SPEX to achieve the best faithfulness among interaction attribution algorithms. Because this method enumerates all possible interactions of up to order $k$ (totaling $\approx n^k$ interactions), it becomes computationally intractable to consider >3rd order methods for the first experiment, and >2nd order methods for the second.

Sentiment for $n\in [16,32]$ | | $\alpha=2$ | $\alpha=4$ | $\alpha=6$ | $\alpha=8$ | |:---------:|:----------:|:----------:|:----------:|:----------:| | ProxySPEX | 0.873 | 0.919 | 0.936 | 0.946 | | SPEX | 0.510 | 0.621 | 0.750 | 0.801 | | LASSO | 0.727 | 0.744 | 0.746 | 0.749 | | FBII 2nd | 0.846 | 0.891 | 0.905 | 0.911 | | FBII 3rd | 0.836 | 0.898 | 0.920 | 0.932 |

Sentiment for $n\in [64,128]$ | | $\alpha=2$ | $\alpha=4$ | $\alpha=6$ | $\alpha=8$ | |:---------:|:----------:|:----------:|:----------:|:----------:| | ProxySPEX | 0.805 | 0.847 | 0.868 | 0.882 | | SPEX | 0.385 | 0.580 | 0.691 | 0.695 | | LASSO | 0.632 | 0.643 | 0.646 | 0.649 | | FBII 2nd | 0.774 | 0.804 | 0.815 | 0.821 |

Hierarchical Nature of GBTs: GBTs capture hierarchy in the feature space inherently through their structure. Each tree in the ensemble is, by its nature, a hierarchical model.

Individual Trees: The first split in a tree, at the root, is on the feature that provides the most information gain across the entire dataset. This is the most dominant feature in the hierarchy. As you move down the tree, further splits are made on other features within the subsets of data created by the previous split. For example, a split on feature B might only occur for data points where feature A was greater than a certain value.

Boosting: The boosting process in GBTs refines this hierarchical modeling. Each new tree is trained to correct the errors of the existing ensemble. This means that later trees focus on capturing patterns and relationships that the earlier trees missed. If a complex hierarchical interaction between features was not fully modeled by the first few trees, subsequent trees will specifically target and model that remaining part of the relationship, further refining the hierarchy. For instance, an initial tree might capture the main effect of age. A later tree might then model a more subtle interaction, like how income has a different effect specifically for younger age groups, a hierarchical relationship that was a source of error for the earlier, simpler model.

Empirical Difference Between SPEX and ProxySPEX - number of masks The primary empirical difference between SPEX and ProxySPEX is an order of magnitude decrease in the number of inference required to achieve the same faithfulness (see Figure 1). For large models (and LLMs in particular), due to the latency of inference, this results in a significant speed-up in wall clock time for computing interactions at scale. We would like to refer the reviewer to Figure 13 in appendix B.5 (The purple lines are for SPEX, and teal for ProxySPEX, the legend was ommitted in error, which will be corrected in the camera ready version). Here, SPEX requires much more time collecting data by performing inference as compared to ProxySPEX to achieve the same faithfulness. This is a result of ProxySPEX's ability to exploit hierarchical information to more efficiently identify interactions. SPEX, on the other hand does not directly exploit any relationship between interactions, only that the interactions themselves are sparse and low-degree.

Toy Problem - Mask Enumeration The toy problem of mask enumeration is not an interesting one for comparing SPEX and ProxySPEX, since the most interesting mechanism is their ability to exploit structure to reduce the number of required masks. SPEX directly learns a Fourier transform, which is a universal approximator (since the transform is 1-to-1). In the case where it has full information about $f$ (access to all the masks), it has zero error. Similarly, in the ensemble limit and given sufficient depth, GBTs are universal approximators, and thus also achieve perfect reconstruction. Practically though, for some fixed ensemble size, there will be some non-zero approximation error, and SPEX would slightly outperform ProxySPEX in this setting.

Questions:

Figure 7: Here we are removing individual "features", which can be words or sentences, depending on the dataset. See the "datasets and models" part of section 4 for details on a per-dataset basis.

Section 5.1: In the camera-ready version, we will discuss this in more detail. For your reference, precise definitions given in Appendix C.1. See rebuttal of review kopj for more details.

Figure 2: With the additional page, we will improve this figure with a simple example from sentiment analysis in the camera-ready version.

Relative Faithfulness: The relative faithfulness is relative to the ``full'' GBT model. That is, we are plotting how faithful the sparsified model is compared to the full GBT model. Our results show that sparsification does not hurt faithfulness while improving interpretability. The plots look similar when plotting absolute faithfulness (relative to the underlying function), but simply saturate at some fixed level (~90%). We will clarify this in the camera-ready version.

Line 164: This result is provided in Gorji et al. [5] (top of page 6), for which we will provide a citation for this statement in the camera-ready version. This result comes from the fact that each leaf of a decision tree has at most $2^d$ non-zero Fourier coefficients. With each tree having at most $2^d$ leaves, and by linearity of tree ensembles and the Fourier transform over $T$ trees, there are at most $T\cdot 2^d \cdot 2^d = T4^d$ non-zero Fourier coefficients. For the decision trees in this paper, the depth is typically set to d=3 or d=5, selected through cross-validation. This is much fewer than $n$ number of features.

[1] Tsai, C. P., Yeh, C. K., & Ravikumar, P. (2023). Faith-shap: The faithful shapley interaction index. Journal of Machine Learning Research, 24(94), 1-42.

Dear reviewer, thank you for your comments and review. We appreciate your effort and insightful follow-up questions.

Weakness Section: This is a good point, and is certainly worthy of a more nuanced follow-up discussion in the camera ready version. We should expect Shapley Values, which are not optimized for faithfulness, to perform poorly in this task, which is observed in Appendix B.5.1 of [1].

The structure of the Shapley Kernel is more suited to the feature identification experiments in Section 4.2 of this paper (where we try to identify the top $r$ features). Here too, however, we find that Shapely values perform comparably to LASSO/LIME which we significantly outperform. Similar results are observed in Section 6.3 of [1]. Interestingly we also find that using the learned Fourier transform of ProxySPEX to estimate the Shapley Values often generates a better estimate (in terms of MSE, correlation, etc.) of the Shapley Values than standard approaches such as KernelSHAP.

Regression: We will extend our discussion of the use of a final regression step. Empirically, we observe that in most cases, there is a small positive effect on the final faithfulness, typically most impactful in very high-noise settings.

Follow-up discussion:

Some discussion of "approximation" vs. "importance": LIME is typically viewed as an "approximation" while Shapley Values are not. It should be noted though, the distinction between "approximation" and "importance" is somewhat arbitrary. Ultimately, most attribution scores can be defined as the solution to an approximation problem with a suitably defined distance metric (loss) and optionally some regularization. For SPEX and ProxySPEX, (and often LIME) that is the $\ell_2$ distance metric, while for the Shapley Value that distance metric is the Shapley Kernel (this is the essence of Theorem 2 in Lundberg et al. 2017).

The real distinction seems to be that local "approximation" based approaches are typically evaluated in terms of their approximation loss, while Shapley Values, are typically not. In the camera ready version, we will add some discussion of this, and highlight our definition of "distance", which is, as you described, the set of all randomly masked inputs.

Interestingly, and complementary to the above discussion, one can use the ProxySPEX approximation to compute Shapley values using the closed-form conversion in Appendix A.1. Evidence suggests that this is efficient strategy. Using the Sentiment dataset and model, we first approximated the Shapley values by running KernelSHAP (Lundberg et al. 2017) under 100,000 model inferences, treating these as the ground truth value. We then compared the approximation quality of the Shapley values computed via KernelSHAP and ProxySPEX under just 100 and 1,000 model inferences, measuring the mean-squared error, spearman rank correlation, and the recall of the top 10 Shapley values. Results are averaged over the 20 movie reviews in the dataset.

The approximation quality is better under all three metrics in this regime. A more thorough comparison with other approximation algorithms is needed, but it seems that leveraging Fourier structural properties (sparsity, hierarchy and low-degree structures) is valuable, not just in an "approximation" sense, but also in determining Shapley Value-like notions of "importance" when model evaluation is very costly.

[1] Kang, J. S., Butler, L., Agarwal, A., Erginbas, Y. E., Pedarsani, R., Yu, B., Ramchandran, K. SPEX: Scaling Feature Interaction Explanations for LLMs. In Forty-second International Conference on Machine Learning.

Thank you for your careful review. We will discuss and clarify some of the main points below, and hope to convince you that this is not a borderline case.

Relationship between SPEX and ProxySPEX: This was a common comment across many reviews. We will add a section carefully describing the relationship of the two approaches.

Note that SPEX and ProxySPEX differ significantly. The only common factors in these two methods are that they:

1. Both exploit an empirically observed structure (sparsity and low-degree) for SPEX and (sparsity, low-degree and hierarchy) for ProxySPEX.

2. Both ultimately generate a Fourier transform to approximate the model.

SPEX uses an algebraic structured sampling scheme, coupled with error correction decoding procedures to efficiently compute the interactions in the form of a Fourier transform. SPEX is a rather complex algorithm that involves many carefully designed components that work in concert to enable efficient estimation.

ProxySPEX, in contrast, is much simpler. ProxySPEX uses random samples to learn a GBT proxy model. We then apply an efficient method for computing the Fourier transform of the GBT model to extract the most important interactions from the proxy model.

Regression: We will extend our discussion of the use of a final regression step. Empirically, we observe that in most cases, there is a small positive effect on the final faithfulness, but is not a critical aspect of ProxySPEX.

Other sampling methods: We would like to emphasize that ProxySPEX is meant to be a model agnostic approach to identifying sparse features interactions. That being said, it is certainly an interesting research direction to try to extract an even more powerful prior beyond sparsity and hierarchy by looking at internal components (that are computed anyways) during the process of inference. During the process of developing ProxySPEX, we did study correlations between our extracted interactions and the one suggested by attention heads, but more work would be required to have a complete and operationally useful understanding of this relationship.

Definitions of Synergy and Redundancy: Creating definitions of redundancy and synergy in interactions for classification was a problem we faced when developing this work. As far as we are aware, there do not exist standard definitions for these, as it is typically considered computationally intractable to compute even pairwise interactions between training data. Our definitions come from the notion of Harsanyi dividends in game theory, and how they relate to subadditive and superadditive game structures [1]. Importantly, Harsanyi dividends are equivalent to the Mobius coefficients, which we can compute due to efficient transformations between the Fourier and the Mobius transform. In the camera ready version, we will more prominently discuss these definitions.

Edelman et al. This paper has some fascinating observations. It seems likely that the models trained in Edelman et al. would exhibit a hierarchical interaction structure, just like the larger, production-size models we considered in this paper. We would certainly discuss this connection in the final revision of our manuscript.

[1] Dehez, P. (2017). On Harsanyi dividends and asymmetric values. International Game Theory Review, 19(03), 1750012.