SPEX: Scaling Feature Interaction Explanations for LLMs

This rebuttal contains (anonymized) links to figures. We also built a web app to help explore SPEX: https://anon858023.github.io/spex-webapp/

Thank you for the review. We hope that with the proposed additions based on your comments, your concerns are addressed and we can convince you that this manuscript is not a borderline case.

Discussion of Mechanistic Interpretability We will add a discussion of mechanistic interpretability, which is a very timely topic in the space of LLMs. Specifically, much work in mechanistic interpretability focuses on discovering sparse circuits. Alternatively, this can be seen as finding interactions between attention heads (i.e., features in the context of our paper). Interesting future work can explore the application of SPEX to sparse feature discovery and other topics in mechanistic interpretability.

Importance of feature attribution with LLMs Our approach offers several key advantages over asking an LLM to explain itself.

1. Many transformer-based models are encoder only which are unable to generate such explanations. Our experiments on the sentiment-analysis demonstrate the strong performance on SPEX on these models. Further, generative models such as protein language models are also unable to generate such explanations.
2. Recent work has shown that LLMs often cannot explain themselves (https://arxiv.org/pdf/2405.04382), and self-explanations do not accurately reflect the underlying reasoning process of the model. On the other hand, our approach is grounded in the model output, and can be systematically verified via our faithfulness and top-$r$ removal experiments, while LLM explanations are not.

More models We have considered 4 different models in this work: DistillBERT, Llama-3.2, GPT 4o-mini and LLaVA-NeXT-Mistral-7B. For additional diversity, we repeat the faithfulness experiments with two additional models: Qwen2-7B-Instruct and Mistral-7B on the DROP dataset, and provide the results in the table below. Due to limited time, we only re-ran SPEX and the Faith-Banzhaf methods, and consider $5$ examples for each regime of $n$. We chose Faith-Banzhaf methods since they displayed the most competitive performance with SPEX in our previous experiments.

Table: Faithfulness on DROP dataset across input lengths (n) for Mistral-7B and Qwen2-7B-Instruct.

We continue to achieve significantly higher faithfulness across models. We will include these results, and run them for the other interpretability methods as well as for HotpotQA in the camera-ready version.

Noise Robustness We find that the use of the BCH code makes SPEX impressively robust. We've conducted an experiment where we repeat our Sentiment experiment with additional observation noise. Our results demonstrate the robustness of SPEX to noise, as it mostly retains its $R^2$ performance even under very high noise levels. (https://imgur.com/a/qAf0y2J). These robustness results will be included in the camera-ready version of the paper.

This rebuttal contains (anonymized) links to figures. Web app to explore SPEX: https://anon858023.github.io/spex-webapp/

Thank you for the thorough and helpful review. We hope our proposed additions and clarifications convince you that this paper is not a borderline case, but rather an impactful and important contribution.

Kang et al. This is the main theoretical inspiration behind this work, showing that sparse transforms and signal processing ideas can be used to compute feature interactions. As the reviewer notes, however, there is a large gap between the practical performance of SPEX and the Sparse Möbius Transform (SMT). We will add a paragraph specifically to highlight the significant effort that enabled this.

1. SPEX uses the Fourier transform, which is orthonormal. This improves robustness by avoiding noise amplification of SMT in the transform domain.
2. The sampling procedure uses different code structures (1) random linear codes and (2) BCH codes, both contributing to robustness.
3. The BCH code is used as a source-channel code, leveraging samples to both compressively sense each $\mathbf{k}$ and build robustness.
4. We add a soft decoder that exploits the real-valued nature of logits, unlike SMT, which quantizes output ratios. Switching between soft and hard decoding allows trading compute for superior performance (see KaFj rebuttal).
5. The SPEX message passing procedure enables superior detection of interaction effects, as we can decode multitons (cases where non-zero coefficients collide) if there is enough difference in interaction magnitude. SMT does not decode multitons.

In exchange for superior practical performance, SPEX has a more involved implementation and lacks SMT’s clean theoretical results.

Faithfulness Kang et al. defines $f$ as zero mean, so our evaluation is identical.

Experimental Design

Hyperparameters All hyper-parameters $C$, $t$ and $b$ control the sample complexity (i.e., number of sampled masks). As discussed in Section 5.1, the number of training masks is $2^bCt\log_2(n)$. Faithfulness is monotonic in all 3 parameters. Since $b$ has the largest effect, we measured faithfulness for $b\in \\{4,6,8 \\}$ for all three datasets in Fig 9. We outperform marginal approaches and are competitive with enumerative interaction indices. We perform additional hyper-parameter sweeps over $C$, $b$, and $t$ for the sentiment analysis task over all possible regimes of $n$. Results in https://imgur.com/G4k4Q91 show $C=3$ and $t=5$ achieve a favorable trade-off in faithfulness and sample-complexity. We will include these experiments in the camera-ready version.

"Missed Interactions" This question hits at a deep point! Every Fourier interaction is present in every test mask (see eq. 1), and influences the output proportional to its magnitude. The direction (+/-) of influence changes depending on the mask. This is not true of the Möbius transform, for which interactions may or may not be involved in the output depending on the mask. This property of the Fourier transform (deeply connected to the orthonormal property) is the reason why this approach works so well. Our revised paper will reflect this discussion.

Additional experimental evidence supporting this:

1. Variance of test responses High variance in model outputs is observed across all datasets. For instance, in https://imgur.com/a/pagr97R, we show test response distributions for varying-length examples from Sentiment. Moreover, the test response distribution demonstrates clear bias, further indicating that variance in test responses is not an artifact of random noise.
2. Difference in performance across methods If this hypothesis were true, all feature attribution methods would have the same faithfulness since they would be evaluated on test samples with $0$ variance.
3. Removal Results Our top-$r$ removal results indicate we learn meaningful information.

[MASK] vs [UNK] Thank you, we will update this. [UNK] is used.

SPEX Interaction Statistics We've conducted a series of experiments to evaluate this. See figure caption for details:

1. Significant interactions: Across datasets and input sizes, most of the faithfulness is achieved through a small number of interactions (https://imgur.com/a/8sKgFrO).
2. Interaction signs: We explore the signs of the interactions for different sized inputs from sentiment analysis.(https://imgur.com/a/cyON8I2)

Fourier Intuition Table 1 provides equations converting Fourier coefficients to Möbius transform, Shapley indices, and Banzhaf values. Fourier coefficients themselves are also interpretable as they are central to influence functions which are widely used for feature and data attribution. In particular, for subset $S$, with Fourier coefficient $F(S)$, the term $F(S)^2/|S|$ corresponds to the contribution of the interaction $S$ to the influence function of $i\in S$. We will add a paragraph in the camera-ready version.

This rebuttal contains (anonymized) links to figures. We also built a web app to help explore SPEX: https://anon858023.github.io/spex-webapp/

Thank you for your constructive and positive review! We appreciate your insightful comments and have addressed them with additional experiments and clarifications below. We believe that SPEX's unique scalability for computing feature interactions in long-text inputs represents a significant advancement beyond the state of the art, and we hope this will be reflected in your final evaluation.

Memorization This is an interesting hypothesis. Memorization could lead to the phenomenon you suggest, where only a few tokens suffice to determine the full sequence. Note that all baseline methods are masking based, and thus our SOTA performance claim is not invalidated, even if this hypothesis is valid. In practice, however, we find evidence that this hypothesis does not hold in our datasets:

1. Variance: We find that the variance on the test dataset we use to evaluate faithfulness is not small. That is, depending on the masks, the model output changes significantly. We visualize these model outputs for examples from the Sentiment dataset (https://imgur.com/a/pagr97R). This is further validated by Fig. 4, which show that marginal attributions, which perform a linear fit, are unable to capture the complex nature of the model output.

2. Explicitly avoid memorization bias An evaluation on unseen data is difficult for the models used in our paper since we do not know the pre-training data that was used. However, to address this concern, we repeat our faithfulness experiments on the TriviaQA dataset for OLMo2-7B-Instruct, an open-source/open-data language model. TriviaQA was not included in the pre-training corpus and was also not used at all during model development for OLMo2-7B-Instruct. Due to time constraints, we do not consider every regime of $n$, and only compare to Faith-Banzhaf since it was strongest in our previous experiments.

Table: Faithfulness on TriviaQA dataset (held-out on OLMo2-7B-Instruct) across input lengths ($n$) for OLMo2-7B-Instruct

Theoretical Claims (We tried our best to answer based on what you wrote, but, please feel free to clarify if we did not answer the question here, as there are many ways to interpret your point about feature independence) The boolean Fourier transform is defined under a Hilbert space of functions with inner product $\langle f,g \rangle = \mathbb{E}_{\mathbf{x} \sim B^n} f(\mathbf{x})g(\mathbf{x})$. The induced distance metric essentially measures the average distance ($\ell_2$) in output between the two functions when features are i.i.d Bernoulli(1/2). However, the transform itself remains well-defined and interpretable even with feature dependencies. Our faithfulness metric (only one of our evaluation criteria) is related to the $\ell_2$ distance in the output space, provides a valuable measure of how well our recovered interactions approximate the original model's behavior. While other metrics might be more relevant for correlated features, the optimal metric for interpretability remains an open question. Importantly, SPEX can effectively capture learned correlations within the LLM.

Example: When the LLM has already learned some of the correlations in the data, SPEX can extract this. For example, when two words ($w_1$ and $w_2$) always appear together, the model will not be impacted when either $w_1$ or $w_2$ are masked (since seeing either $w_1$ or $w_2$ is enough to deduce the presence of the other), and will only change when both $w_1$ and $w_2$ are masked simultaneously. SPEX will find a $2^{nd}$ order interaction here that indicates this correlation.

Synonym Swap We appreciate this suggestion. While valuable, introducing synonym swaps adds potential confounding factors and poses scalability challenges for comprehensive evaluation. We believe this direction warrants further investigation in future work.

BCH Complexity The complexity of decoding a $BCH(n_c, k_c, t)$ code is in Appendix A.5. It is $O(n_ct + t^2)$, with $n_c \approx n + t\log(n)$. Soft-decoding offers a way to trade off complexity for superior performance. We implement a 2-chase decoder which has an additional $2^{d_{chase}}$ factor, where $d_{chase} \leq t$ can be designed. We emphasize that this complexity is small compared to current interaction indices which have complexity that scales as $O(n^d)$, where $d$ is the highest degree of interaction considered. We will include a discussion in the final revision.