SPEX: Scaling Feature Interaction Explanations for LLMs
Authors: Justin Singh Kang
Landon Butler
Abhineet Agarwal
Yigit Efe Erginbas
Ramtin Pedarsani
Bin Yu
Kannan Ramchandran
Venue: ICML 2025 poster (2025)
Keywords: Interpretability
Signal Processing
Compressed Sensing
SHAP
Interactions
Primary area: social_aspects->accountability_transparency_and_interpretability
TL;DR: Enabling post-hoc interaction explanations with orders of magnitude larger input spaces over the previous state of the art via a signal processing inspired algorithm.

Abstract: Large language models (LLMs) have revolutionized machine learning due to their ability to capture complex interactions between input features. Popular post-hoc explanation methods like SHAP provide *marginal* feature attributions, while their extensions to interaction importances only scale to small input lengths ($\approx 20$). We propose *Spectral Explainer* (SPEX), a model-agnostic interaction attribution algorithm that efficiently scales to large input lengths ($\approx 1000)$. SPEX exploits underlying natural sparsity among interactions—common in real-world data—and applies a sparse Fourier transform using a channel decoding algorithm to efficiently identify important interactions. We perform experiments across three difficult long-context datasets that require LLMs to utilize interactions between inputs to complete the task. For large inputs, SPEX outperforms marginal attribution methods by up to 20\% in terms of faithfully reconstructing LLM outputs. Further, SPEX successfully identifies key features and interactions that strongly influence model output. For one of our datasets, *HotpotQA*, SPEX provides interactions that align with human annotations. Finally, we use our model-agnostic approach to generate explanations to demonstrate abstract reasoning in closed-source  LLMs (*GPT-4o mini*) and  compositional reasoning in vision-language models.

SPEX: Scaling Feature Interaction Explanations for LLMs
Justin Singh Kang" 1
Landon Butler" 1 Abhineet Agarwal *2 Yigit Efe Erginbas' Ramtin Pedarsani Bin Yu 12 Kannan Ramchandran
Abstract
among features'. Interactions are critical for complex tasks like protein design, drug discovery, or medical diagnosis, which require examining combinations of hundreds of fea- tures. As LLMs are increasingly used in such high-stakes applications, they require trustworthy explanations to aid in responsible decision-makin tions enable debugging and can drive development through improved understanding (Zhang et al., 2023a).
Large language models (LLMs) have revolution- ized machine learning due to their ability to cap- ture complex interactions between input features. Popular post-hoc explanation methods like SHAP provide marginal feature attributions, while their extensions to interaction importances only scale to small input lengths (+e 20). We propose Spectral Ex- plainer (SPEX), model-agnostic interaction attri- bution algorithm that efficiently scales to large input lengths ( 1000). SPEX exploits underlying nat- ural sparsity among interactions-comee world data- and applics a sparse Fourier transform using a channel decoding algorithm to efficiently identify important interactions. We perform exper- iments across three difficult long-context datasets that require LLMs to utilize interactions between inputs to complete the task. For large inputs, SPEX outperforms marginal attribution methods by up to 20% in terms of faithfully reconstructing I.IM out- puts. Further, SPEX successfully identifies key fea- tures and interactions that strongly influence model output. For one of datasets, HotporQA, SPEX provides interactions that align with human annota- tions. Finally, we use our model-agnostic approach to generate explanations to demonstrate abstract rea- soning in closed-source LLMs (GPT-40 mini) and compositional reasoning vision-language models.
Moreover, LLM explana-
Current post-hoc explainability approaches for LLMs fall into two categories: (i) methods like Shapley values (Lund- berg & Lee, 2017) and LIME (Ribeiro et al., 2016) compute marginal feature attribution but do not consider interactions. As a running example, consider sentiment analysis task (see Fig. I(a)) where the LLM classifies a review containing the sentence "Her acting never fails to impress". Marginal at- tribution methods miss this interaction, and instead attribute positive sentiment to "never" and "fails" (see Fig. (a)). (ii) Interaction indices such as Faith-Shap (Tsai et al., 2023) attribute interactions up to given order d. That is, for input features, they compute attributions by considering all ((n)) interactions. This becomes infeasible for small n and This motivates the central question of this paper:
in real-
Can we perform interaction attribution at scale for a large input space n with reasonable computational complexity?
We answer this question affirmatively with Spectral Ex- plainer (SPEX) by leveraging information -thooretic tools to efficiently identify important interactions at LLM scale. The scale of SPEX is enabled by the observation that LLM outputs are often driven by a small number of sparse in- teractions between inputs (Tsui & Aghazadeh, 2024: Ren et al., 2024a). See Fig. 1 for examples of sparsity in vari- ous tasks. SPEX discovers important interactions by using sparse Fourier transform to construct a surrogate expla- nation function. This sparse Fourier transform searches for interactions via a channel decoding algorithm, thereby avoiding the exhaustive search used in existing approaches.
1. Introduction
Large language models (LLMs) perform remarkably well across many domains by modeling complex interactions
"Equal contribution 'Department of Electrical Engineering and Computer Science. UC Berkeley "Department of Statistics, UC Berkeley 'Department of Electrical and Computer Engineer- ing, UC Santa Barbara. Correspondence to: Justin Singh Kang <justin_ @ berkeley.edu>.
Our experiments show we can identify a small set of in- teractions that effectively and concisely reconstruct LLM outputs with
1000. This scale is far beyond what
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'LLM features refer to inputs at any granularity, e.g, tokens, sentences a prompt or image patches in lisoon-language models.

---

SPEX: Scaling Feature Interaction Explanations for LLMS
(d) SENTIMENT ANALYSIS
(b) RETRIEVAL AUGMENTED GENERATION
(4)
VISUAL QUESTION ANSWERING
CONTEXT
CONTEXT
CONTEXT
Her acting never fall to impress. She
brings depth and authenticity to every role. Her performances consistently drow the
Rio
Summer Brazil
Winter Brazil
Mixi
Camiival
Roord
PROMPT
PROMPT
PROMPT
this positive negative review?
What the weather like during Rio Cornival?
What shown in this image?
GENERATED RESPONSE
GENERATED RESPONSE
GENERATED RESPONSE
Rio Cariial generally lakes place during the at
Positive
A dog playing with baskethall
typically
never fails
Intersctions:
Interaction:
Rio Cannivl & Summer Brasil
Rio Camival
Iuteraction:
Water in Brazi
fails
Summmr Brazi
Rio Camiral
Winter Brazil
Marginal attributions:
never
Fails
Figure I: (a) Sentiment analysis: SPEX identifies the double negative "never fails". Marginal approaches assign positive attributions to "never" and "fails". (b) Retrieval augmented generation: SPEX explains the output of a RAG pipeline, finding a combination documents the LLM used to answer the question and ignoring unimportant information. (c) Visual question answering: SPEX identifies interaction between image patches required to correctly summarize the image.
current interaction attribution benchmarks consider, e.g., SHAP-IQ (Muschalik et al., 2024) only considers datasets with no more than 20 features. This summarized in Fig 2; marginal attribution methods scale to large n but ignore crucial interactions. On the other hand, existing interaction indices do not scale with SPEX both captures interac- tions and scales to large For an sparse Fourier transform containing interactions of at most degree d, SPEX has com- putational complexity at most (sdn). In contrast, popular interaction attribution approaches scale as ()
Interaction Order
4+
SPEX
3
SHAP-IQ / Faith-Shap
SHAP LIME
Evaluation Overview. We compare SPEX to popular fea- ture and interaction indices across three standard datasets. Algorithms and experiments are made publicly available
10
100
1000
Input Length
Figure 2: Marginal attribution approaches scale to large n, but do not capture interactions. Interaction indices only work for small n. SPEX computes interactions and scales.
Faithfulness. SPEX more faithfully reconstructs (+z 20% improvement) outputs of LLMs as compared to other meth- ods across datasets. Moreover, learns more faithful re- constructions with fewer model inferences.
2. Related Work
LLMs capable of generating rationalizations for their outputs, but such rationalizations are another form of model output, susceptible to the same limitations (Sarkar, 2024). In contrast, this work focuses on explanations in the form of feature attributions that are grounded in the model's in- puts and outputs, and can be applied any ML model. i.e., model--ggnstic methods. Moreover, model-agnostic methods can be applied to LLMs incapable of explaining their own output such protein language models well as encoder-only models (see experiments in Sec. 6)
Identifying Interactions. SPEX identifies a small num- ber of influential interactions that significantly change model output. For one of our datasets, HotporQA, SPEX provides interactions that align with human annotations.
Case Studies. demonstrate how one might use SPEX identify and debug reasoning errors made by closed- source LLMs (GPT-40 mini) and for compositional rea-
soning in large multi-modal model.
h tttp:s//////tubuut/eeee com wtt..ao...b.a.c.c.ce...........s labb/ spectraal meeetral--eppass -explain
Model-Agnostic Feature Attributions LIME (Ribeiro et al., 2016), SHAP (Lundberg Lee, 2017), and Banzhaf
2

---

SPEX: Scaling Feature Interaction Explanations for LLMs
SPEX
0.45 - (fa
(t00 0.37 (impress)
Decoding
0. 70 (never, fails)
0.53 (never, impress)
LLM
+0.97 (never, fails, impress)
Input
Masking Design
Model Outputs
Fourier Surrogate Function
Explanation
Figure 3: SPEX utilizes channel codes determine masking patterns. We observe the changes in model output depending on the used mask. SPEX uses message passing to learn surrogate function to generate interaction-based explanations.
values (Wang& & Jia, 2023) popular model-agnostic fea- ture attribution approaches. SHAP and Banzhaf use game- theoretic tools for feature attribution, while LIME fits a sparse linear model. Chen et al. (2018) utilize tools from information theory for feature attributions. Other methods (Sundararajan et al., 2017; Binder et al., 2016) instead utilize internal model structure to derive feature attributions.
the coordinates in x we retain, replacing all others with the [MASK] token. For example, if S {1, 4, 5, 6). then the masked input x5 is "Her acting [MASK] fails to impress". Masks can be more generally applied to any input. In Fig. 1(b) and (c), masks are applied over documents and image patches respectively.
Value Function For input x, let s(xs) E IK be the output of the LLM under masking pattern S. In sentiment analysis, (see Fig. ((a)) f(xs) is the logit of the positive class. If Xs is "Her acting [MASK] fails to impress", this masking pattern changes the score from positive to negative. For text generation tasks, we use the well-established practice of scalarizing generated text using the negative log-perplexity' of generating the original output for the unmasked input (Paes et al., 2024; Cohen- Cohen-Wang al., 2024). Since only consider sample-specific explanations for given we suppress dependence on x and write (xxs as fSS).
Interaction Indices Tsai et al. (2023) and Sundararajan al. (2020) extend Shapley values to consider interactions. Fumagalli et al. (2023) provide general framework towards interaction attribution but can only scale to most 20 input features. Ren et al. (2023; 2024b) theoretically study sparse interactions, a widely observed phenomenon in practice. Kang et al. (2024) show that sparsity under the Möbius transform (Harsanyi, 1958) can be theoretically exploited for efficient interaction attribution. In practice, the proposed algorithm fails due noise being amplified by the non-orthogonality of the Möbius basis. Our work utilizes the orthonormal Fourier transform, which improves robustness by preventing noise amplification. Hsu et al. (2024) apply tools from mechanistic interpretability such as circuit discovery for interaction attribution.
Fourier Transform of Value Function Let F3 = {0. 1)", and addition between two elements in F2 as XOR. Since there are 2" possible masks S, we equivalently write f F3 R. where f(S) fm) with S {i m, 1}. That is, m F7 is binary vector representing a masking pattern. If m, = O we evaluate the model after masking the 8th input. The Fourier transform F F F7 + R of f is:
Feature Attribution in LLMs Enouen et al. (2023); Paes et al. (2024) propose hierarchical feature attribution for lan- guage models that first groups features (paragraphs) and then increase the feature space via more fine-gras mne-grained anal- ysis (sentences words/tokens). Johen-Wang et al. (2024) provide marginal feature importances via LASSO. These works do not explicitly compute interaction attributions.
f(m) = Σ (m)) F(k). KEF
The Fourier transform is an orthonormal transform onto parity (XOR) function basis (O'Donnell, 2014).
3. Overview: Fourier Transform Formulation
Sparsity f is sparse if F(k) 2 0 for most of the k Fm. Moreover, we call f low degree, if large F(k) have small kk/ Ren et al. (2024b); Kang et al. (2024); Valle-Perez et al. (2018); Yang & Salman (2019) and experiments in Ap- pendix establish that deep-learning based value functions f are sparse and low degree. See Fig, for examples.
We review background on the Fourier transform for SPEX. Model Input Let x be the input to the LLM where x consists of n input features, e.g., words. For x = "Her acting never fails to impress"", n = 6. In Fig. 1(b) and (c), n refers to the number of documents or image patches. For C [n], we define x5 as masked input where denotes
Other approaches scalarization exist: text embedding simi- larity, BERT score, etc. See (Paes et al., 2024) for an overview.
3

---

SPEX: Scaling Feature Interaction Explanations for LLMs
4. Problem Statement
S. Then u has Fourier transform U:
Our goal is to compute an approximate surrogate f. SPEX finds small set of with [k| < n denoted K. and F(k) for each k I such that
u(t) = e( = U(i) Σ F(k). Mk=j
(4)
f(m) = - (-1) F(k).
(2)
Shift Property: For any function f FF2 - R. if we shift the input by some vector p E F2. the Fourier transform changes as follows:
KE
This goal is motivated by the Fourier sparsity that commonly occurs in real-world data and models. Some current interac- tion indices (Tsai et al., 2023) determine K. by formulating it as a LASSO problem, and solving it via & Ei-penalized regression (Tibshirani, 1996).
fo (m) = fmm+p) = (-1)) (p.k) F(k). (5)
Designing Aliasing The aliasing property (4) dictates that when sampling according to M E 12 all F(k) with image j = Mk are added together. If only one dominant F(k) satisfies Mk = j. which can happen due to sparsity, we call it a singleton. We want M to maximize the number of singletons, since we ultimately use singletons to recover the dominant coefficients and estimate F'. SPEX uses M with elements chosen uniformly from F2. Such M has favorable properties regarding generating singletons.
2 + ||1
F = argmin F
Σ f(m) - (mm) m
(3)
For given order d, this approach requires enumeration of all Onn)) interactions. This leads to explosion in computa- tional complexity as n grows, as confirmed by our experi- ments (see Fig 4(a)). To resolve this problem, we need to find an efficient way to search the space of interactions.
Designing Shifts Once we create singletons, we need to identify them, extract the dominant index k, and estimate Fk)). The shift property (5) is critical for this task since the sign of the dominant F(k) changes depending on (p. k). Thus, each time apply a shift vector, we gather (poten- tially noisy) information about the dominant k. Finding k and estimating (k) can be modeled as communicating information over noisy channel (Shannon, 1948), where the communication protocol is controlled by the shift vec- tors. We use the aforementioned BCH channel code, which requires only R log(n) shifts to recover k. The parameter controls the robustness of the decoding procedure. Gen- erally, if the maximum degree is |k| d, choose t 2 d. If ( - |k > O, we use the additional shifts to improve the estimation of F F(k). Since most of the time |k| is less than 5, we fix = 5 for experiments in this paper.
Ideas behind SPEX The key to efficient search is realiz- ing that we are not solving an arbilrary regression problem: (i) the Fourier transform (1) imparts algebraic structure and (ii) we can design the masking patterns m with sparsity and that structure in mind. SPEX exploits this by embedding BCH Code (Lin& & Costello, 1999), a widely used algebraic channel code, into the masking patterns. In doing so, we map the problem of searching the space of interactions onto the problem of decoding message (the important k) from a noisy channel. We decode via the Berlekamp- Massey algorithm (Massey, 1969), a well-established algebraic al- gorithm for decoding BCH codes.
5. SPEX: Algorithm Overview
We now provide a brief overview of SPEX (see Fig. 3). A complete overview is provided in Appendix A. The high- level description consists of three parts:
Combined Masking Combining ideas from above, we construct C = 3 independently sampled M, and p shifting vectors P., which come from rows of BCH parity ma- trix. Then, for the function uz, = fM, T t pp)) The total number of samples is R (o)()n). We note that all model inference informed by our masking pattern can be conducted in par- allel. The Fourier transform of cach Me denoted Ue is connected to the transform of the original function via
[C] and i E [p]. we entirely sample
Step 1: Determine a minimal set of masking patterns m to use for model inference, and query (mm for each m.
Step 2: Efficiently learn the surrogate function ff from the set of collected samples (m))
Step 3: Use f and its transform F to identify important interactions for attribution.
Ui.(i) = Σ (-1)
(6)
5.1. Masking Pattern Design: Exploiting Structure
k : M,K=j
We first highlight two important properties of Fourier trans- form related to masking design structure.
5.2. Computing the Surrogate Function
Once we have the samples, we use an iterative message passing algorithm to estimate ((k) for small (a-priori unknown) set of k K.
Aliasing (Coefficient Collapse) Property: For b S n and M E Fbxn let u 1 >> TR. denote subsampled version of
4

---

SPEX: Scaling Feature Interaction Explanations for LLMS
Bipartite Graph We construct a bipartite graph depicted in Fig. 5. The observations U.(i) (Uao(i)..... Uep (i)) are factor nodes, while the values f(k) correspond to vari- able nodes. F(k) is connected to (i) if M.k
C' 3, informed by Li al. (2014) under simplified sparse Fourier setting. We fix f = 5, which is the error cor- rection capability of SPEX and serves as approximate bound on the maximum degree. We also set b = 8; the total collected samples are R Cog))) An empirical validation of these selections on the sentiment dataset is presented in Appendix B.5.1. For & regression-baset inter- action indices, we choose the regularization parameter via 5-fold cross- voss-validation.
Message Passing The messages from factor to variable are computed by attempting to decode a singleton via the Bersskamp-Massey algorithm. If a k is successfully de- coded, k is added to and F(k) is estimated and sent to factor node F(k). The variable nodes send back the average of their received messages to all connected factor nodes. The factor nodes then update their estimates of F, and at- tempt decoding again. The process repeats until conver- gence. Once complete the surrogate function constructed from IC and F(k) according to (2). Complete step-by-step details are in Appendix A, Algorithm
6.1. Metries
We compare SPEX other methods across a variety of well-established metries to assess performance.
Faithfulness: To characterize how well the surrogate func- tion f approximates the true function, we define faithfulness (Zhang et al., 2023b):
6. Experiments
R -=11- 11 fl
Datasets We use three popular datasets that require the LLM understand interactions between features.
|| 1f-fi 51
1. Sentiment is primarily composed of the Large Movie Review Dataset (Maas et al., 2011), which contains both positive and negative IMDb movie reviews. The dataset is augmented with examples from the SST dataset (Socher et al., 2013) to ensure coverage for small n. We treat the words of the reviews as the input features.
where ||.[| Emery f(m)² and f f= 2 Emery f(m).
Faithfulness measures the ability of different explanation methods to predict model output when masking random inputs. We measure faithfulness over 10,000 random test masks per-sample, and report average 12 across samples.
2. HotporQA (Yang et al., 2018) is a question-answeringg dataset requiring multi-hop reasoning over multiple Wikipedia articles to answer complex questions. We use the sentences of the articles as the input features.
Top-r Removal: We measure the ability of methods to identify the top r influential features to model output:
Rem(r) (S(1) - s(m))
[f(1]
(8)
3. Discrete Reasoning Over Paragraphs (DROP) (Dua et al., 2019) is comprehension benchmark requiring discrete reasoning operations like addition, counting, and sorting over paragraph-level content to answer questions. We use the words of the paragraphs as the input features.
m² argmax 1f(1) ((1)-fol f(m)).
Recovery Rate@r: Each question in HotporQA contains human-labeled annotations for the sentences required to correctly answer the question. We measure the ability of interaction indices to recover these numan-labeled anno- tations. Let S,.- C [nx] denote human-annotated sentence indices. Let St denote feature indices of the 7th most im- portant interaction for given interaction index. Define the recovery ability a r for each method as follows
Models For DROP and HotpotQA, (generative question- answering tasks) we use Llama- 3..aaa3.2333 2-38--33-0 I2-3B-Inattnn (Grattafiori et al., 2024) with 8-bit quantization. For Sen- timent (classification). we use the encoder-only fine-tuned DistilBERT model (Sanh et al., 2019; Odabasi, 2025).
Baselines We compare against popular marginal metrics LIME, SHAP, and the Banzhaf value. For interaction in- dices, we consider Faith-Shapley, Faith-Banzhaf, and the Shapley-Taylor Index. We compute all benchmarks where computationally feasible. That is, we always compute marginal attributions and interaction indices when n is suffi- ciently small. In figures, we only show the best performing baselines. Results and implementation details for all base- lines can be found in Appendix B.
St n SSS.
Recovery @r
S
Intuitively, (9) measures how well interaction indices cap- ture features that align with human-labels.
6.2. Faithfulness and Runtime
Fig. 4 shows the faithfulness of SPEX compared to other methods. We also plot the runtime of all approaches for the Sentiment dataset for different values of n. All attribution methods are learned over a fixed number of training masks.
Hy perparaaaeessss SPEX has several parameters to deter- mine the number of model inferences (masks). We choose
5

---

SPEX: Scaling Feature Interaction Explanations for LLMs
SPEX LIME
(urs))
Faith-Shap
2nd
3rd
4th
Banzhaf
2nd
3rd
4th
30
1.0
Limit of Other Interaction Methods
Compute Time [sec.)
Faithfulrest (RP)
0.9
25
20
Paln Bucano 411 Ovter
Faith Sundher Test Chtler
Pamm STO Ath Onder
Talns Shep Onter
0.7
10
0.6
0.5
8-15
16-31
32-63
64 127
128 255
256 511
512 512-1023
1024 2047
16
32
64
128
256 512 1024
Number of Words (n)
Number Words (n)
(a) Sentiment
Faithfolness (JP)
0.7
Faithfulness (RR)
0.8
0.6
10:00
0.5
0.7
Fainls Faihh-Banaain Sanahal 4th Oroir
Eandral Order
0.4
0.6
0.3
0.5
Shapley
Faihh Sonette
0.2
0.4
FS 3rd
0.1
32-63
64-127
128-255
256-511
512-1023
8-15
16-31
32-63
64-127
Number of Words (n)
Number of Sentences (n)
(b) DROP
(c) HotporQA
Figure 4: (a) SPEX uniformly outperforms all baselines in terms of faithfulness. High order Faith- Baith-Banzhaf indices have competitive faithfulness, but rapidly increase in computational cost. (b) The DROP dataset contains only larger examples, so we primarily compare against first order methods. (c) Our approach remains competitive this task as well, and still outperforms marginal approaches for large n.
Samping Group
Samping Group
Comparison to Marginal Attributions For input lengths too large to interaction indices, SPEX is significantly more faithful than marginal attribution approaches across all three datasets.
Ui(1)
U
U
U
U2(22
U2(
Varying number of training masks Results in Appendix B show that SPEX continues to out-perform other ap- proaches as we vary the number of training masks.
F(ks)
F(ke)
F(ks)
((ke)
Decade: Fail
Decoded Success
Factar Message
Variable Message
Sparsity of SPEX Surrogate Function Results in Ap- pendix B, Table show surrogate functions learned by SPEX have Fourier representations where only ~ 10 100 percent of coefficients are non-zero.
Figure 5: Depiction of the message passing algorithm for computing the surrogate function in SPEX.
6.3. Removal
Comparison to Interaction Indices SPEX maintains com- petitive performance with the best perfoommn interaction indices across datasets. Recall these indices enumerate all possible interactions, whereas SPEX does not. This differ- ence reflected in the runtimes Fig. 4(a). The runtime of other interaction indices explodes as n increases while SPEX does not suffer any increase in runtime.
Fig. plots the change in model output as we mask the top features for different regimes of n.
Small n SPEX is competitive with other interaction in- dices for Sentiment, and out- out-performs them for HotpotQA and DROP. Performance of SPEX in this task particularly notable since Shapley-based methods designed iden-
6

---

SPEX: Scaling Feature Interaction Explanations for LLMs
Shapley-Taylor 2nd
Paith-Shap 2nd
2nd
SPEX (Ours)
SHAP LIME
Banzhaf
1.4
0.012
0.007
1.3
0.010
0.006
Rem
1.2
Rem(r)
Rem(r)
0.008
0.005
0.006
0.9
0.003
0.8
Removal Distance (7)
Removal Distance (r)
Removal Distance (r)
(a) Sentiment n. [32 63
(h) DROP n [32, 63)
(c) HosporQA n [32,
0.014
0.0050
2.2
0.013
Rem(r)
Rem(r)
0.012
Rem(r)
0.0045
0.011
1.6
0.010
0.0040
1.4
1.2
0.008
0.0035
3
3
3
Removal Distance (r)
Removal Distance (r)
Removal Distance (r)
(d) Sentiment n [64, 127]
(c) DROP [64, 127]
(f) HotpotQA E [64, 127]
Figure 6: On the removal task, SPEX performs competitively with 2nd order methods on the Sentiment dataset, and out-perform all approaches on DROP and HorporQA dataset for n E [32, 63). interaction indices, we outperform marginal methods.
When n is too large to compute other
tify small set of influential features. On the other hand, SPEX does optimize for this metric, but instead learns the function f()) over all possible 2" masks.
7. Case Studies
In this section, we apply SPEX to two case studies: de- bugging incorrect responses and visual question answering. Refer to Appendix for further details implementation.
Large SPEX out-performs all marginal approaches, in- dicating the utility of considering interactions.
6.4. Recovery Rate of Human-Labeled Interactions
7.1. Debugging Incorrect LLM Responses
We compare the recovery rate (9) for r = 10 of SPEX against third order Faith-Banzhaf and Faith-Shap interaction indices. We choose third order interaction indices because all examples are answerable with information from at most three sentences, i.e., maximum degree d = 3. Recovery rate is measured as we vary the number of training masks.
LLMs often struggle to correctly answer modified versions of popular puzzle questions, even when these alterations trivialize the problem (Williams & Huckle, 2024). In this spirit, we consider variant of the classic trolley problem:
A runaway trolley is heading away from five people who are tied to the track and cannot move. You are near lever that can switch the direction the trolley is heading. Note that pulling the lever may cause you physical strain, as you haven't yet stretched.
Results are shown in Fig. 7a, where SPEX has the highest recovery rate
interaction indices across all sample sizes. Further, SPEX achieves close to maximum per- formance with few samples, other approaches require many more samples approach the recovery rate of SPEX.
True False: You should not pull the lever.
Example of Learned Interaction by SPEX Fig. 7b dis- plays long-context example (128 sentences) from Hot- porQA whose answer is contained in the three highlighted sentences. SPEX identifies the three human labeled sen- tences as the most important third order interaction while ignoring unimportant contextual information. Other third order methods not computable this length.
GPT-4o mini (OpenAI, 2024) incorrectly selects the swer false 92.19 % of the time. To understand the response, we run SHAP and SPEX over a value function that mea- sures the logit associated to the output true.
Fig. 8 presents the results of these methods: words and interactions highlighted in green contribute positively to

---

SPEX: Scaling Feature Interaction Explanations for LLMs
Faith-Shap 3rd
Faith-Banzhaf 3rd SPEX (Ours)
Question:
The magazine that nominated George Rainsford for their Best Ac- tor award in 2017 comes out every week on what day of the week?
30%
Recovery Rate
+9.2%
4-6.2%
Title: George Rainsford (actor)
+8.8%
George Rainsford is English actor and has been nominated for Best Actor award in the 2017 TV Choice Awards.
20%
Title: NFL regular season
The National Football League (NFL) regular season begins the...
10%
Title: TV Choice
0%
Choice British weekly listings magazine published by H. Bauer Publishing. It features weekly TV broadcast programming listings and goes on sale every Tuesday.
1,344
5,376 Samples
21,504
(a) Recovery 1a for HorporQA
(b) Human-labeled interaction identified by SPEX.
Figure 7: (a) SPEX recovers more human-labeled features with significantly fewer training masks as compared to other methods. (b) For a long-context example (n 128 sentences), SPEX identifies the three human-labeled sentences as the important third order interaction while ignoring unimportant contextual information.
producing the correct output, while those in red lead the model toward an incorrect response. SHAP indicates that both instances of the word molley have the most significant negative impact, while the last sentence appears to aid the model in answering correctly. A more comprehensive un- derstanding is provided by the top interactions learned via SPEX. These interactions indicate a negative fourth order interaction involving the two instances of trolley, as well as the words pulling and lever. This negative interaction is em- blematic of the original problem's 's formulation, indicating that the model may be over-fit.
response. Negative interactions between different parts of the dog indicate redundancy, implying that the total effect of these regions is less than the sum of their marginal con- tributions.
8. Conclusion
Identifying feature interactions is critical problem in ma- chine learning. We have proposed SPEX, the first interac- tion based model-agnostic post-hoc explanation algorithm that is able to scale to over 1000 features. SPEX achieves this by making a powerful connection to the field of channel coding. This enables SPEX to avoid the (nz)) complexity that existing feature interaction attribution algorithms suffer from. Our experiments show SPEX is able to significantly outperform other methods across the Sentiment, Drop and HotporQA datasets terms of faithfulness, feature removal, and interaction recovery rate.
7.2. Visual Question Answering
VQA involves answering questions based image. Pet- siuk et al. (2018); Frank et al. (2021); Parcalabeseu & Frank (2023) consider model-agnostic methods for attributing the marginal contributions of image regions to the generated re- sponse. In many compositional reasoning tasks, interactions are key and marginal attributions are insufficient. We illus- trate this using an image of a dog playing with basketball and prompting the LLaVA- NexT -Mistral-78 model (Liu et al., 2023) with "What is shown in this image?". This yields the response "A dog playing with basketball.".
Limitations Sparsity is central to algorithm, and with- out underlying sparse structure, SPEX can fail. Fur- thermore, even though we make strides in terms of sample efficiency, the number of samples still might remain too high for many applications, particularly when inference cost or time is high. Another consideration the degree of human understanding we can extract from computed in- teractions. Manually parsing interactions can be slow, and useful visualizations of interactions vary by modality. Fur- ther improvements in visualization and post-processe of interactions are needed.
In Fig. 8, SHAP indicates that image patches containing the ball and the dog are important, but does not capture their interactions. Positive interactions obtained via SPEX reveal that the presence of both the dog and the basketball together contributes significantly more the response than the sum of their individual contributions. This suggests that the model not only recognizes the dog and the basketball as separate objects but also understands their interaction-do playing with the ball-as crucial for forming the correct
Future Work SPEX works in a non-adaptive fashion, pre- determining the masking patterns m. For greater sample efficiency, adaptive algorithms might be considered, where
8

---

SPEX: Scaling Feature Interaction Explanations for LLMs
A runaway trolley is heading away from five people who are tied cannot move. You are near lever that can switch the direction the trolley heading. Note that pulling the lever may cause you physical strain, as you haven't t yet stretched.
runaway trolley heading away from five people who are tied to the track and cannot move. You are near a lever that can switch the directibn the trolley is heading. Note that pulling the lever may cause you physical strain, you haven't yet stretched.
track and
SHAP
Interactions via SPEX True False: You should not pull the lever.
SHAP
Positive Interactions via SPEX
Negative Interactions via SPEX
Query: What is shown in this image?
Response: A dog playing with basketball.
Figure 8: SHAP provides marginal feature attributions. Feature interaction attributions computed by SPEX provide more comprehensive understanding of (above) words interactions that cause the model to answer incorrectly and (below) interactions between image patches that informed the model's output.
initial model inferences help determine future masking pat- terns. addition, we have focused on model-agnostic expla- nations, but future work could consider combining this with internal model structure. Finally, interactions are central aspect of the attention structures in transformers. Studying the connection between SPEX and sparse attention (Chen et al., 2021) is another direction for future research.
dation for the Collaboration on the Theoretical Founda- tions of Deep Learning through awards 814639, NSF grant MC2378 to the Institute for Artificial CyberThreat Intelligence and OperatioN (ACTION), and NIH grant RO1GM152718. L.B. acknowledges that this terial is based upon work supported by the National Science Foundation Graduate Research Fellowship Program (NSF GRFP) under Grant No. DGE-2146752.
2031883 and
Impact Statement
Any opinions, findings, conclusions, or recommendations expressed this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Getting insights into the decisions deep learning models offers significant advantages, including increased trust in model outputs. By reasoning about the rationale behind model's decisions with the help of SPEX, we can develop greater confidence in its output, and use it to aid in our own reasoning. When using analysis tools like SPEX, it's crucial to avoid over-interpretation of results.
References
Amrollahi, A., Zandieh, A., Kapralov, M., and Krause, A. Efficiently learning fourier sparse set functions. Advances in Neural Information Processing Systems, 32, 2019.
Acknowledgments
Banzhaf III, J. F. Weighted voting doesn't work: A mathe- matical analysis. Rutgers L. Rev., 19:317, 1964.
R.P. acknowledges the support of NSF award 2342253 and 2419982. K.R. acknowledges the support of NSF award 2232146. B.Y. acknowledges partial support from NSF grant DMS-2413222 NSF grant DMS 2209975, NSF grant 2023505 on Collaborative Research: Foundations of Data Science Institute (FODSI), the NSF and the Simons Foun-
Binder, A., Montavon, G., Bach, S., Müller, K.-R,, and Samek, W. Layer-wise relevance propagation for neural networks with local renormalization layers, 2016. URL https://arae http://xxxivvoorrbb//l//ees h 00825.

---

SPEX: Scaling Feature Interaction Explanations for LLMS
Bird, S., Klein, E.,, and Loper, E. Natural language process- ing with Python: analyzing text with the natural language toolkit. O' O'Reilly Media, Inc.", 2009.
Grabisch, M. Bases and Transforms of Set Functions. In Saminger-Platz, S. and Mesiar, R. (eds.), On Logical, Algebraic, and Probabilistic Aspects of Fuzzy Set The- ory, volume 336, pp. 215-231. Springer International Publishing, Cham, 2016. ISBN 978-3-319-28807-99 978- 3-319-28808-6. doi: 10.1007/978-33119-88885
Chen, B., Dao, T., Winsor, E., Song, Z., Rudra, A., and Ré, C. Scatterbrain: Unifying sparse and low-rank attention. Advances in Neural Information Processing Systems, 34: 17413-17426, 2021.
URL http: //1:nk./nkk..... springer. ctrriinngr..oom///.. com/ 1007
3- - 6 6_13. Series Title: Studies in Fuzziness and Soft Computing.
Chen, J., Song, L., Wainwright, M., and Jordan, M. Learn- ing to explain: An information thoommttin--hhoorttic theoretic perspective on model interpretation. In International conference on ma- chine learning, pp. 883 892. PMLR, 2018.
Grabisch, M., Marichal, J.-L., and Roubens, M. Equiv- alent representations of set functions. Mathematics of Operations Research, 25(2):157-178, 2000.
Cohen-Wang, B., Shah, H., Georgiev, K., and Madry, A. Contextcite: Autributing model generation to con- text, 2024. URL 00729.
Grattafiori, A. al. The llama 3 herd of models, 2024. URL https: http://awxvvv.....a.../.. 24t...///44...... 21783.
Harsanyi, J. C. A bargaining model for the cooperative n-person game. PhD thesis, Department of Economics, Stanford University, Stanford, CA, USA, 1958.
Dua, D., Wang, Y., Dasigi, S., Singh, S., Gardner, M., and Kwiatkowski, T. Drop: A reading comprehension bench- mark requiring discrete reasoning over paragraphs. In Proceedings of the 2019 Conference of the North Amer- ican Chapter of the Association for Computational Lin- guistics: Human Language Technologies, Volume (Long and Short Papers). pp. 2368 -2788, 2019.
Hassamieh, H., Indyk, P., Katabi, D., and Price, E. Simple and practical algorithm for sparse Fourier transform. In SIAM Symposium on Discrete Algorithms (SODA), pp. 1183-1194, 2012. doi: 10. 0957//1.7716119999
URL ht https: / http/pppbssseeeeeeee s siam. org/ /doi//oo///// /abs/ 40. 93.
Enouen, J., Nakhost, H., Ebrahimi, S., Arik, S. O., Liu, Y., and Pfister, T. TextGenSHAP: Scalable post-hoc explana- tions in text generation with long documents, 2023. URL 01279.
1 1137/1.978161199
Hostetter, M. Galois: A performant NumPy extension for Galois fields, November 2020. URL https://
https:/ / /ttp://aaavv../ee wwtpp//pppp....../ httppp///axvoooog/p////32323
github. comc com//thostette//gal...
Erginbas, Y. E.,, Kang, J., Aghazade,, A., and Ramchandran, K. Efficiently computing sparse fourier transforms of q-ary functions. In IEEE International Symposium on Information Theory (ISIT), pp. 513-518, 2023. doi: 10. L109/SSTS54713.2223. 10206686.
Hsu, A. R., Zhou, G., Cherapanamjeri, Y., Huang, Y., Odisho, A. Y., Carroll, P. R., and Yu, B. Efficient auto- mated circuit discovery in transformers using contextual decomposition, 2024. URL abs/2407. 008224877708.....
Frank, S., Bugliarello, E., and Elliott, D. Vision-and- language rision-forllanguage" on cross-modal influ- ence in multimodal transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Lan- guage Processing, pp. 9847-9857, 2021.
Kang. J. S., Erginbas, E.,, Butler, L., Pedarsani, R., and Ramchandran, K. Learning to understand: Identifying interactions via the mobius transform. arXiv preprint arXiv:2402.02631, 2024.
Fumagalli, F., Muschalik, M., Kolpaczki, P., Hüllermeier, E.,, and Hammer, B. E. SHAP-IQ: Unified approximation of any-rrder shapley interactions. In Conference on Neural Information Processing Systems, 2023. URL https: //openreview.. wwt.eeewwwwwweeeeeeeeeee.eeeeeee forumm idd= http://wwww.eeeoooeiieeeeeee 4gMM
Kolpaezki, P., Muschalik, M., Fumagalli, F., Hammer, B., and Hüllermeier, E. Svarm-iq: Efficient approximation of any-order shapley interactions through stratification. arXiv preprint arXiv:2401. 13371, 2024.
Li, X., Bradley, J. K., Pawar, S., and Ramchandran, K. The SPRIGHT algorithm for robust sparse Hadamard Transforms. In IEEE International Symposium on In- formation Theory (ISIT), pp. 1857-1861, 2014. doi: N0.11099SSTT2204465851111
Grabisch, M. k-order additive discrete fuzzy mea- sures and their representation. Fuzzy Sets and Systems, 92(2):167-189, 1997.
ISSN 0165-0114,
doi: http://bb.rr///00000000051111010
URL httpst//ww..cceenneedeeeed com/ science/are wttee////rcceeee/s///ooloo111110
Lin, S. and Costello, J. Error control coding. Pearson, Upper Saddle River, NJ, 2 edition, December 1999.
Fuzzy Measures and Integrals.
10

---

SPEX: Scaling Feature Interaction Explanations for LLMs
Liu, H., Li, C., Li, Y., and Lee, Y. J. Improved baselines with visual instruction tuning, 2023.
Pawar, S. and Ramchandran, K. Computing k-sparse length Discrete Fourier Transform using most 4k sam- ples and O(klogk) complexity. In IEEE International Symposium on Information Theory (ISIT), pp. 464 468, 2013. doi: 10. 09/1STTT201136622220
Lundberg, S. M. and Lee, S.-I. A unified approach to inter- preting model predictions. In Proceedings of the s1 In- ternational Conference on Neural Information Processing Systems, NIPS' 17, pp. 4768-4777, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 97815 7781510860964.
Pedregosa, F, Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P.. Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
Maas, A. L., Daly, R. E.,, Pham, P. T., Huang, D., Ng. A. Y., and Potts, C. Learning word vectors for sentiment anal- ysis. In Annual Meeting of the Association for Com- putational Linguistics: Human Language Technologies, pp. 142-150, Portland, Oregon, USA, June 2011. As- sociation for Computational Linguistics. URL http:
Petsiuk, V., Das, A., and Saenko, K. RISE: Randomized in- put sampling for explanation of black-box models. In The Twenty-ninth British Machine Vision Conference, 2018. URL https: / arxiv.vee.. org pdf / /1806.800000 07421.
//www. acl web. orgg
Maleki, A. Approximate message passing algorithms for compressed sensing. PhD thesis, Stanford University, 2010.
Ren, J., Zhou, Z., Chen, Q. and Zhang, Q. Can we faith- fully represent absence states to compute shapley values on a DNN? In International Conference on Learning Representations, 2023. URL net / forummorummmmm -it:itdd=vVV--- 7bW6K..
Massey, J. Shift-register synthesis and bch decoding. IEEE Transactions on Information Theory, 15(1):122- 127, 1969. doi: 10.1
Ren, Q. Gao, J., Shen, W., and Zhang, Q. Where we have arrived in proving the emergence of sparse inter- action primitives in DNNs. In International Confer- ence Learning Representations, 2024a. URL https: / //ooppeevieeee eww net/ forum? d=
Muschalik, M., Baniecki, H., Fumagalli, F., Kolpaczki, P., Hammer, B., and Hüllermeier, E. shapiq: Shapley interactions for machine learning. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024. URL https: //openreview.net forum? fworrmmmdddnnGmmmmm www.dd=wwwnnnieemm 6SJ1.
Ren, Q., Xu, Y., Zhang, J., Xin, Y., Liu, D., and Zhang, Q. Towards the dynamics of a DNN learning symbolic inter- actions, 2024b. URL /ttp:vss//axxvoor////// pdf/ 2407.19199
Odabasi, ment. Accessed January, 2025.
DistilBERT Finetuned Senti- URL
https: https://hugginggfce.e cow..riihlii.... distilbert-basee fine-trte---be----ett-e--------
Ribeiro, M. T., Singh, S., and Guestrin, C. " why should trust you?" explaining the predictions of any classifier. the
In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135-1144, 2016.
O'Donnell, R. Analysis of boolean finctions. Cambridge University Press, 2014.
OpenAl. Gpt-4o system card, 2024. URL https:// arxiv. org/ abs /212/211111 21276.
Roubens, M. Interaction between criteria and definition of weights in meda problems. In 44th Meeting of the Euro- pean Working Group "Multicriteria Aid for Decisions", Brussels, Belgium, 1996.
Paes, L. M., Wei, D., Do, H. J., Strobelt, H., Luss, R., Dhurandhar, A., Nagireddy, M., Ramamurthy, K. N., Sattigeri, P., Geyer, W., et al. Multi-level explanations for generative language models, 2024. URL https: //arxiv. httpg/ddf/224000 14459.
Sanh, V., Debut, I.,, Chaumond, J., and Wolf, T. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. ArXiv, abs/1910.011088, 2019.
Parcalabescu, L. and Frank, A. MM-SHAP: A performance- agnostic metric for measuring multimodal contributions in vision and language models & tasks. In Proceed- ings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 4032 4059, 2023.
Sarkar, A.
Large language models cannot explain them- selves. arXiv preprint arXiv:2405.04332 2024.
Shannon, E. A mathematical theory of communication.
The Bell System Technical Journal, 27(3):379 -23, 1948. doi: 10. 10. 1538- 7305.11 1948. A44..b01338.x.

---

SPEX: Scaling Feature Interaction Explanations for LLMS
Socher, R., Perelygin, A., Wu, Chuang, J., Manning. C. D., Ng, A., and Potts, C. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing, pp. 1631-1642, 2013.
dataset for diverse, explainable multi-hop question swering. arXiv preprint arXiv: 1809:00:0000000000 180900900, 2018.
Zhang. Q. Singh, C., Liu, L., Liu, X., Yu, B., Gao, J., and Zhao, Tell your model where attend: Post-hoc atten- tion steering for Ilms. arXiv preprint arXiv:2311.0226.. 2023a.
Stobbe, P. and Krause, A. Learning Fourier sparse set fune- tions. In International Conference Artificial Intelli- gence and Statistics (AISTA7S), Proceedings of Machine Learning Research, pp. 1125-1 133, La Palma, Canary Islands, Apr 2012. URL https: httpp//ceedngss... milr.press / v22 stobbe12 html.
Zhang. Y., He, H., Tan, Z., and Yuan, Trade-off be- tween efficiency and consisteney for removal-based ex- planations. Advances in Neural Information Processing Systems, 36:25627-25661 2023b.
Sundararajan, M., Taly, A., and Yan, Q. Axiomatic attribu- tion for deep networks. In International conference on machine learning, pp. 3319-3328. PMIR, 2017.
Sundararajan, M., Dhamdhere, K., and Agarwal, A. The Shapley Taylor interaction index. In International Conference on Machine Learning, pp. 9259-9268, Jul 2020. URL URL.tttps://proceeeii v119/sunen ht11s/unndxaaaaaaa222... html.
mlr.press/
Tibshirani, R.
Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-288, 1996.
Tsai, C.-P. Yeh, C.-K., and Ravikumar, P. Faith-shap: The faithful Shapley interaction index. Journal of Machine Learning Research, 24(94):1-42) 2023.
Tsui, D. and Aghazadeh, A. On recovering higher-order interactions from protein language models. In ICLR 2024 Workshop Generative and Experimental Per- spectives for Biomolecular Design, 2024. URL https: / //openreviey net /et//eruunee forum? www.mmidddmmaooooooi Wd-WEA50HpYT.
Valle-Perez, G., Camargo, C. Q., and Louis, A. A. Deep learning generalizes because the carameter-function map is biased towards simple functions. arXiv preprinl arXiv:1805.08522 2018.
Wang, J. T. and Jia, R. Data Banzhaf: robust data valuation framework for machine learning. In In- ternational Conference
Artificial Intelligence and Statistics, volume 206, pp. 6388-6421, 25-27 Apr 2023. httpst hwt.https://ppooeee /ppp/oceeddiie igg.ingnn... .ml www.m.rr..... r.pess/////// v206 2000/wang23.... .tmm1....
Williams, S. and Huckle, J. Easy problems that Ilms get wrong, arXiv preprint arXiv:2405. 19616, 2024.
Yang, G. and Salman, H. fine- lne-grained spectral perspective neural networks. arXiv preprint 2019.
Yang, Z. Qi, P.. Zhang, S., Bengio, Y. Cohen, W. W., Salakhutdinov, R., and Manning, C. D. Hotpotqa: A
12

---

SPEX: Scaling Feature Interaction Explanations for LLMS
A. Algorithm Details
A.1. Introduction
This section provides the algorithmic details behind SPEX. The algorithm is derived from the sparse Fourier (Hadamard) transformation described in Li al. (2014). Many modifications have been made to improve the algorithm and make suitable for use in this application. Application of the original algorithm proposed in Li et al. (2014) fails for all problems consider in this paper. In this work, we foeus on applications of SPEX and defer theoretical analysis future work.
Relevant Literature on Sparse Transforms This work develops the literature sparse Fourier transforms. The first of such works are (Hassanieh et al., 2012; Stobbe & Krause, 2012; Pawar & Ramchandran, 2013). The most relevant literature is that of the sparse Boolean Fourier (Hadamard) transform (Li et al., 2014; Amrollahi et al., 2019). Despite the promise of many of these algorithms, their application has remained relatively limited, being used in only a handful of prior applications. Our code base is forked from that of (Erginbas et al., 2023). In this work we introduce a series of major optimizations which specifically target properties of explanation functions. By doing so, our algorithm is made significantly more practical and robust than any prior work.
Importance of the Fourier Transform The Fourier transform does more than just impart critical algebraic structure. The orthonormality of the Fourier transform means that small noisy variations in f remain small in the Fourier domain. In contrast, AND interactions, which operate under the non-orthogonal Möbius transform (Kang et al., 2024), can amplify small noisy variations, which limits practicality. Fortunately, this is not problematic, as it is straightforward to generate AND interactions from the surrogate function f. Many popular interaction indices have simple definitions in terms of F. Table 1 highlights some key relationships, and Appendix provides a comprchensive list.
Shapley Value
Banzhaf Interaction Index
Möhius Coefficient
SV = Σ
F(S)/IS)
[S) = (-2)15)
- (-2)) Σ F(T)
S3i, [8] odd
T2S
Table 1: Popular attribution scores in terms of Fourier coefficients
A.2. Directly Solving the LASSO
Before we proceed, we remark that in cases where n is not too large, and we expect the degree of nonzero |k| S d to be reasonably small, enumeration is actually not infeasible. In such cases, we can set up the LASSO problem directly:
F argmin Σ fmm
F(k) kk
F(k)
+ + F
(10)
Note that this is distinct from the Faith Srith-Banzhaff and Faith-Shapley solution methods because those perform regression over the AND, Möbius basis. We observe that the formulation above typically outperforms these other approaches in terms of faithfulness, likely due to the properties of the Fourier transform.
Most popular solvers use coordinate descent to solve (10), but there is long line of research towards efficiently solving this problem. In our code, we also include implementation of Approximate Message Passing (AMP) (Maleki, 2010), which can be much faster in many cases. Much like the final phase of SPEX, AMP is low complexity message passing algorithm where messages are iteratively passed between factor nodes (observations) and variable nodes.
A more refined version of SPEX, would likely examine the parameters n and the maximum degree d and determine whether or not to directly solve the LASSO, or to apply the full SPEX, as we describe in the following sections.
A.3. Masking Pattern Design and Model Inference
The first part of the algorithm to determine which samples we collect. All steps of this part of the algorithm are outlined in Algorithm 1. This is governed by two structures: the random linear codes M. and the BCH parity matrix P. Random linear codes have been well studied as central objects in error correction and cryptography. They have previously been considered
13

---

SPEX: Scaling Feature Interaction Explanations for LLMS
for sparse transforms in (Amrollahi al., 2019). They suitable for this application because they roughly uniformly hash k with low hamming weight.
The use of the P E F2x", the parity matrix of binary BCH code is novel. These codes are well studied for the applications in error correction (Lin & Costello, 1999). and they were once the preeminent form of error correction in digital communications. A primitive, narrow-sense BCH code characterized by its length, denoted fee dimension, denoted ke (which we want to be equal to our input dimension vi) and its error correcting capability te = 2d + 1, where minimum distance of the code. For some integer m and te 2mm the parameters satisfy the following equations:
Te = 2m -1
(11)
= The - ke S mt.
(12)
Note that the above says we can bounds p S t (ng) and it is easy to solve for p given n ke and t, however, explicitly bounding p in terms of and is difficult, so for the purpose of discussion, we simply write p z & log(n), since
n. = p + n, and we expect n >> p in nearly all cases of interest.
We use the software package galois (Hostetter, 2020) to construct a generator matrix, G E F2 F.. in systematic form:
I xhc
G
(13)
P
Note that according to (13) P E 1 In cases where ki >> n, consider only the first n rows P. This is process
Algorithm 1 Collect Samples
Input: Parameters (n, b, C 3,7 0.9), Query function f(-)
2: for to n, to b, to do
Generate random linear code
3:
X1j (0.5)
4:
[Moli, +- Xi
5: end for
6: Code +- BCH(n, = nh hic 2 n, la =
b Systematic BCH code with dimension n and correcting capacity /
7: p f - -1
8: P Pode.P
9: P + rows(P) = 00, pi...., Ppl
10: for all LE R32 E (0..... .......,,.... (1,...,C) C)do do
11: (e) + (M. 2 PPii)
Query the model at masking patterns >> Compute the Boolean Fourier transform of the collected samples
12: end for
.p.....,p..c. (I,...,C) do 13: for all FFT(Ue))
14:
15: end for
U. + [Ue....., Ucpp]
17: Output: Processed Samples Uc, Un,0 c= I,...,C
known as shortening. Our application of this BCH code in our application is rather unique. Instead of the typical use of a BCH code as channel correction code, we use as a joint source channel code.
Let Po 0, and let Pa. i= ....... correspond the rows of We collect samples written as:
(e) - (M P.) ve E F4, c= 1,...,, C, i
O.....p.
(14)
Note that the total number of unique samples can be upper bounded by C(p + 1)2", For large this upper bound is nearly always very close the true number of unique samples collected. After collecting each sample, compute the boolean Fourier transform. The forward and inverse transforms as we consider in this work are defined below.
Forward: F(k)
1
Σ mEF
(-1) (k.m) f(m)
Inverse:
f(m)
Σ (-1) (m.k) F(k),
(15)
2n
KEFS
14

---

SPEX: Scaling Feature Interaction Explanations for LLMS
When samples are collected according to (14), after applying the transform in (15), the transform of Ue, can be written as:
Ue,((i)
Σ (-1) F(k).
(16)
M.
To ease notation, we write U.- [Ve,1..... Uepl" 1" Then we can write
Uc(i)= E (-1)PkF(k))
(17)
k:M,k=j
where we have used the notation (-1) ((-1)(Pok) (-1)(p..k)) We call the (-1) the signature of k. This signature helps to identify the index of the largest interactions and is central to the next part of the algorithm. Note that also keep track of U,) which is equal to the unmodulated sum U,,(() Ek: M,K F(k).
A.4. Message Passing for Fourier Transform Recovery
Using the samples (17), we aim to recover the largest Fourier coefficients F(k). To recover these samples we apply message passing algorithm, described in detail in Algorithm 4. The factor nodes are comprised of the C2 vectors U.( Vj E F2. Each of these factor nodes are connected all values k that are comprise their sum, i... {k M,k j}. Since the number of variable nodes is too great, we initialize the value of each variable node, which we call F(k) to zero implicitly. The values (k) for each variable node indexed by represent our estimate of the Fourier coefficients.
A.4.1. THE MESSAGE FROM FACTOR TO VARIABLE
Consider an arbitrary factor node (j) initialized according to (17). We want to understand there are any large terms F(k) involved in the sum in (17). To do this, we can utilize the signature sequences (-1) If (c( is strongly correlated with the signature sequence of given k, i.e., if ((-1)Pk Uz(i)) is large, and M,k- from the perspective of Ua(j), it is likely that F(k is large. Searching through all M,k- = J. which, for full rank M. contains 2n- different k is intractable, and likely to identify many spurious correlations. Instead, we rely the structure of the BCH code from which P is derived to solve this problem.
BCH Hard Decoding The BCH decoding procedure is based on an idea known generally in signal processing as "treating interference as noise". For the purpose of explanation, assume that there is some k" with large F(k*), and all other k such that M,k = correspond small F(k). For brevity let Ac(i) (k M,K = j}. We can write:
(.( = F(k))
Σ (-1)PkF(k)
(18)
Aei)k
After normalize with respect to (fi this yields:
Uc(i)
(-1)Pk' + (EA.UR- (-1)PkF(k) (F(K)+ E F(k)
(19)
U2u(i) 1+ E F(K)/F(K*) = A() +w))
(20)
As we can see, the ratio (20) is noise-corrupted version of the signature sequence of k". To estimate Pk we apply nearest-neighbor estimation rule outlined in Algorithm 2. In words, if the ith coordinate of the vector (20) is closer to -1 we estimate that the corresponding element of Pk to be 1, conversely, if the ith coordinate is closer to we estimate the corresponding entry to be 0. This process effectively converts the multiplicative noise A and additive noise w to a noise vector 2. We can write this as Pk* + n. According to the Lemma A.1 if the hamming weight n is not too large, we can recover k*.
Lemma A.1. If If|n|+ [k*| tt, where is the additive noise in Fg induced by the noisy process in (20) and the estimation procedure in Algorithm 2, then can recover k*
Proof. Observe that the generator matrix of the BCH code is given by (13). Thus, there exists codeword of the form
k*
c = Gk*
(21)
Pk*
15

---

SPEX: Scaling Feature Interaction Explanations for LLMS
Now construct the "received codeword" as in Algorithm 2:
0
(22)
Pk +
Thus |c (c-ri n| + | Since the BCH code was designed to be t enror correcting, Decoding the code will recover which contains k".
For decoding we use the implementation in the python package galois (Hostetter, 2020). It implements the standard procedure of the Berlekamp-Massee Algorithm followed by the Chien Search algorithm for BCH decoding.
Algorithm 2 BCH Hard Decode
Input: Observation (j), Decoding function Doc(-)
2: ri < 0 ,...,7
3: for all i E n + 1, , n
do
4: Ti 7=1-1 Uc
(i.
< 0
5: end for
6: dec, k+ Deo(r)
7: Output: dec, k
BCH Soft Decoding In practice the conversion of the real-valued noisy observations (20) to noisy elements in F2 is a process that destroys valuable information. In coding theory, this known as hard imput decoding, which is typically suboptimal. For example, certain coordinates will have values (2.(3) xs O. For such coordinates, we have low confidence U.a(i)
about the corresponding value of (-1) (-1)(p.kk)) (p..k), since it is equally close to +1 and 11. This uncertainty information is lost in the process of producing a hard input. With this so-called seft information it is possible to recover k* even in cases where there are more than errors in the hard decoding case. We use a simple soft decoding algorithm for BCH decoding known as chase decoder. The main idea behind a chase decoder is perform hard decoding on the dehase most likely hard inputs, and return the decoder output of the most likely hard input that successfully decoded. In practical setting like the ones consider in this work, we don't 't have an understanding of the noise in (20). A practical heuristic is to simply look at the is large, we assume it has high confidence, while if it is small, we assume the confidence is low. Interestingly, if we assume A(j) 1 and w(j) ~ N(0, o²) in (20), then the ratio corresponds exactly Pr((p,,k)--)) For the purposes of soft decoding we interpret these
margin of estimation. In other words, if
(ea(j))
(.,(())
to the logarithm of the likelihood ratio (LLR) log (r((p..k)==))
ratios LLRs. Pseudocode can be found in Algorithm
Remark: BCH soft decoding is well-studied topic with vast literature. Though put significant effort into building strong implementation of SPEX, we have used the simple Chase Decoder (described in Algoritium 3 below) as soft decoder: The computational complexity of Chase Decoding scales as 20os but other methods exist with much lower computational complexity and comparable performance.
If we successfully decode some k from the BCH decoding process via the bin U.(i), we construct a message to the corresponding variable node. Before do this, verify that the k term satisfies M,K j. This acts final check to increase our confidence in the output of k. The message construct is of the following form:
(e.j)= ((-1)Pk U.(i))/p
(23)
To understand the structure of this message. This message can be seen as an estimate of the Fourier coefficient. Let's assume we are computing this message for some k*:
Mecj)-k +(k")+
Σ
1 ((-1)) (-1)Pk') F(k)
(24)
AGj
typically small
The inner product serves to reduce the noise from the other coefficients in the sum.
16

---

SPEX: Scaling Feature Interaction Explanations for LLMS
Algorithm 3 BCH Soft Decode (Chase Decoding)
1: Input: Observation (j), Decoding function Dec(-), Chase depth dehase.
2: r < 0i 1....
3: R detuse most likely hard inputs
Can be computed efficiently via dynamic programming
4: dec + False
5: j +-
6: while dec is False and V dehase do
7:
F(n+1)((n+)) + R(j]
8:
j+i+1
9: dec, k Dec(r)
end while
11: Output: dec, k
Algorithm 4 Message Passing
1: Input: Processed Samples U L....,, C
2: S {c.j) :J 12, {I,...,C)) C}]
Nodes to process
3: F[k] < 0 vk
4: K. E+ 0
5: while |S|>0] > do
Outer Message Passing Loop
6: Ssub t 0
7: Kouh <- 0
8:
for (c, E S do
9:
dec, k < (.,
D. Process Factor Node
10:
dec then
corr ((-1)Pk.u.())
[,,1))|
12:
else
13:
corr <- 0
14:
end
if corr y then
Interaction identified
16:
Sub t Sub U ((k,c,)) Kwub + Ksub U [k}
17:
18:
else
19:
S S Sisss(ess {(r,))}
Cannot extract interaction
20:
end
end for
for
Kruh do Sk - [ik' c' j) (k','' c')) Sub, k' k}
23:
24:
M(cJ)-kk + ((-1)Pk Ui(i)/pp
25:
Mk-sall E(KeeJess Med)+
26:
F(k) + F(k) + 4KK+all
Update variable node
27:
for C (l,..., CJ. C} do
28:
(M,)) + U.(Mkk) - fk-+all Pk ((c, M,k)]
> Update factor node
end for 31: end for
32: K KU Kaub
33:
end while
34: Output: (K,, k E EK. interactions, and scalar values corresponding to interactions.
17

---

SPEX: Scaling Feature Interaction Explanations for LLMs
A.4.2. THE MESSAGE FROM VARIABLE TO FACTOR
The message from factor variable is comparatively simple. The variable node takes the average of all the messages receives, adding the result its state, and then sends that average back to all connected factor nodes. These factor nodes then subtract this value from their state and then the process repeats.
A.5. Computational Complexity
Generating masking patterns Constructing each masking pattern requires n2 for each M.- The algorithm for computing it efficiently involves gray iteratively adding to bit vector and keeping track of the output in Gray code. Doing this for all C, and then adding all p additional shifting vectors makes the cost OCpp22))
Taking FFT For each ue, we take the Fast Fourier transform in b2 time, with total of OCCpb2"). This dominated by the previous complexity since, b S n
Message passing One round of BCH hard decoding is O(,, + t²). For soft decoding, this cost is multiplied by 2d which we is a constant, Computing the correlation vector is (mp)), dominated by the computation of Pk. In the worst case, we must do this for all C2 vectors (i). We also check that Mk = j before sending the message, which costs (1b).. Thus. processing all the factor nodes costs O(C2"(net + f² + n(p + b))). The number of active (with messages send) variable nodes is at most C2 and computing their factors is at most C. Thus, computing factor messages
most C22b messages. Finally, factor nodes updated with most C2 variable messages sending messages at most C' factor nodes each, each with cost of (mp)). Thus, the total cost of processing all variable nodes is OCC22) + C²22 The total cost of message is dominated by processing the factors.
The total complexity is then O(2 + + + n(p + b)). Note that p = n. n = t log(n.). Due to the structure of the code and the relationship between n: p and ne, one could stop here, and would be best to we want to consider very large t. For the purposes of exposition, we will assume that < n, which implies n > p. and thus p t llog(n). In this case, we can write:
Complexity (nt + nb))
(25)
To arrive the stated equation in Section I, we take 2 = Os).. Under the low degree assumption, we have log())) Then assuming take t (dl) we arrive at complexity of Osdnn log(n)).
B. Experiment Details
B.1. Implementation Details
Experiments are run on a server using Nvidia L40S GPUs and A100 GPUs. When splitting text into words or sentences, we make use of the default word and sentence tokenizer from nitk (Bird et al., 2009). To fit regressions, we use the scikit-lest rn (Pedregosa et al., 201 1) implementations of LinearRegressi on and RidgeCV.
B.2. Datasets and Models
B.2.1. SENTIMENT ANALYSIS
152 movie reviews were used from the Large Movie Review Dataset (Maas et al., 2011), supplemented with movie reviews from the Stanford Sentiment Treebank dataset (Socher et al., 2013). These 160 reviews were categorized using their word counts into groups ([8-15, 16-32, .... 1024-2047J), with 20 reviews in each group
To measure the sentiment of each movie review, utilize Disti 1ERT model (Sanh et al., 2019) fine-tuned for sentiment analysis (Odabasi, 2025). When masking, we replace the word with the [UNK] token. We construct an value function over the output logit associated with the positive class.
B.2.2. HOTPOTQA
We consider 100 examples from the HotporQAAYang et al., 2018) dataset. These examples were categorized using the number of sentences into four groups (18-15, 16-32, 32-64, 64-127]). We use a a.lama-3, 3. 2-33B- Instruct model with
18

---

SPEX: Scaling Feature Interaction Explanations for LLMs
8-bit quantization. When masking, replace with the [UNK] token, and measure the log-perplexity of generating the original output. Since HotpotQA is multi-document dataset, use the following prompt format.
Title: {title_1}
Content: (document
Title: (title_m) }
Content: [document_m]
Query: {question).
Keep your answers as short as possible.
B.2.3. DROP
consider 100 examples from the DROP (Yang et al., 2018) dataset. These examples were categorized using the number of words into six groups ([8-15, 16-32. 32-64, 64-127, 128-256, 512-1024]). We use the same model as HotporQA and mask similar fashion. We use the following prompt format.
Context: {context)
Query: {question]. Keep your answers as short as possible.
B.2.4. TROLLEY PROBLEM
The simplified trolley problem was inspired by the one provided in (Williams Huckle, 2024). When masking, the [UNK] token was used to replace words. The following prompt given to gpt-44o-mi1--2224-777
System: Answer with the one word True False only. Any other answer will be marked incorrect.
User: (Masked Input} True or False: You should not pull the lever.
A value function was created by finding the difference between the model's logprob associated with the "True" token minus the logprob of the "False" token.
B.2.5. VISUAL QUESTION ANSWERING
The base image was partitioned into 6 x grid. To mask, Gaussian blur was applied to the masked cells. The masked image was input into LLaVA NeXT Mistral- 7B, a large multimodal model, with following prompt:
Context: (masked image}
Query: What is shown this image?
The original output to the unmasked image "A dog playing with basketball." Using the masked images, we build a value function that measures the probability generating the original output sequence (log probability).
B.3. Baselines
The following marginal feature attribution baselines were run:
LIME: LIME (Local Interpretable Model-agnostic Explanations) (Ribeiro et al., 2016) uses LASSO to build a sparse linear approximation of the value function. The approximation is weighted to be local. using an exponential kernel fit the function better closer the original input (less maskings).
2. SHAP:
Implemented using KernelSHAP (Lundberg & Lee, 2017). SHAP interprets the value function as a cooperative game and attributes credit to each of the features according to the Shapley value. KernelSHAP approximates the Shapley
19

---

SPEX: Scaling Feature Interaction Explanations for LLMs
values of this game through solving weighted least squares problem, where the weighting function is informed by the Shapley kernel, promoting samples where very either very few most inputs masked.
3. Banzhaf: Similar Shapley values, Banzhaf values (Banzhaf III, 1964) represent another credit attribution concept from cooperative game theory. We compute the Banzhaf values by fitting ridge regression to uniformly drawn samples, selecting the regularization parameter through cross-validation.
Furthermore, we compared against the following interaction attribution methods:
4. Faith- :hirh-Bancchf: The Faith- Banzhaf Interaction Index (Tsai et al., 2023), up to degree t, provides the most faithful tt order polynomial approximation of the value function under a uniform kernel. We obtain this approximation using cross-validated ridge regression on uniformly drawn samples.
5. Faith-Shap: Similarly, the Faith-Shapley Interaction Index (Tsai et al., 2023), up to degree t, provides the most faithful order polynomial approximation of the value function under a Shapley kernel. As described (Tsai et al., 2023), the indices can be estimated through solving a weighted least squares problem. We use the implementation provided in SHAP-IQ (Muschalik et al., 2024).
6. Chapley-Taylors The Shapley- Taylor Interaction Index (Sundararajan et al., 2020). up to degree t. provides another interaction definition based on the Taylor Series of the Möbius transform of the value function. To estimate the interaction indices, we leverage the sample-efficient estimator SVARM-IQ (Kolpaczki al., 2024), implemented in SHAP-IQ (Muschalik et al., 2024).
B.4. Sample Complexity
The total number of samples needed for SPEX is x C2'tlog(n) We fix C' = 3 and t = 5. The table below presents the number of samples used in our experiments for various choices of sparsity parameter b and different input sizes n:
Number of Inputs (n) 93-215
Sparsity Parameter (b)
8-11
12-36
37-92
216-466
467-973
974-1992
1,008
1,344
1,728
1,968
2,208
2,448
2,688
4,032
5,376
6,912
7,872
8,832
9,792
10,752
8
16,128
21,504
27,648
31,488
35,328
39,168
43,008
Table 2: Number of samples needed for each b and n.
B.5. Additional Results
B.5.1. FAITHFULNESS
Faithfulness for fixed sparsity parameter 8: We first measure the faithfulness by scaling the number of samples logarithmically with n. The exact number of samples used can be found in Table 2.
In Table 3, showcase the average faithfulness of every runnable method across every group of examples for the Sentiment, DROP, and HotporQA datasets. Among marginal attribution methods, LIME and Banzhaf achieve the best faithfulness. SHAP's faithfulness worsens as n grows, though this is unsurprising, as Shapley values are only efficient (intended to sum to the unmasked output), not faithful.
Comparing to interaction methods, SPEX is comparable to the highest order Faith-Banzhal that can feasible be run at every size of n. However, due poor computation complexity scaling of this, and other interaction methods, these methods are only able be used for small In particular, we found Shapley-Tayle Taylor difficult run for the DROP and HotporQA tasks, unable to finish within thirty minutes.
We also report the average sparsity and the average sparsity ratio (sparsity over total interactions) discovered by SPEX for each of the groups For Sentiment, once reaching the n E [128- - 255] group, the average sparsity is found to be less than the number of inputs! Yet, SPEX is still able to achieve high faithfulness and significantly outperform linear methods like LIME and Banzhaf.
20

---

SPEX: Scaling Feature Interaction Explanations for LLMS
Faith-Bunzhar
Faith-Shup
Shupley-Taylor
Avg. Sparsity
Avg. Spursity Ratio
3rd
3rd
8-15
369.9
3.70
10
1.00
0.83
0.84
0.96
0.99
1.00
0.62
0.93
0.98
1.00
0.72
0.81
0.92
16:31
208.7
2.31
0.97
0.75
0.75
0.93
0.98
0.20
0.89
0.95
0.46
-710.85
32-63
149.7
3.14
10-9
0.93
0.67
0.68
0.90
-0.25
0.82
-0.30
Sentiment
64-127
118.4
2.19
10
10
0.87
0.66
0.66
0.63
-3.94
-1.17
256-511
100.4
5.48
10
0.76
0.62
0.62
-6.7
2,02
10-103
-.78
1024-2047
81.7
3.78
10
0.71
0.59
0.59
-17.31
32-63
77.1
1.97
0.58
0.29
0.29
0.53
-0.07
0.17
NIA
64-127
56.3
2.59
10
0.51
0.30
0.30
0.02
DROP
128-255
58.7
2:31 x 10-3s
0.67
0.43
0.43
0.14
256-511
$6.7
10-76
0.44
-5.29
512-1023
36.3
9.63 10
0.55
0.46
0.48
-0.23
1.10
HolporQ4
16-31
96.4
3.30 x 10
0.67
0.39
0.49
0.66
0.72
0.23
-2.28
0.40
N/A
NAA
32-63
79.4
5.80
0.57
0.44
0.45
0.59
0.13
0.32
NIA
64-127
73.0
1,02
10-15
0.63
0.53
0.53
-0.31
Table 3: Faithfulness across all baseline methods for fixed b = 8. The average recovered sparsity and the average ratio between sparsity and total possible interactions is also reported.
SpectrolExxplann
Danahof Stopley
Punt Donzhaf 2nd Order
Faith Shop 2nd Order
Shapley Taylor 2nd Order
LIME
Paris Danzhat 2nd Order
Falth Shop ded Order
Shapley Taylor 3ed Ordes
Faithfiness (RA)
0.8
0.6
0.2
1,344
5,376
21, 104
Samples
(a) Sentiment
[16, 31]
Sprctra Fxplain
Ranahal Shapley
Faith-Banshal 2nd Onler Shap
Sluplay- Taylor 3nd Order
0.6
Faithfulzess
0.2
0
1,728
6,912 Samples
27 648
(b) DROP n [32, 63)
SpectrollEppiate
Bonchaf Shapley
Purta Dunahaf 2nd Order
Falth Shop 2nd Order
Shaple: Tayler 2nd Order
Pairi-Bonchaf 3rd Order
Faith Suth-SSapp
Shopley- Taype Order
Futhhfuleess (RP)
0.6
0.4
0.2
1,344
5,376
Samples
(c) HotpotQA n E [16,31]
Figure 9: Faithfulness across the three datasets for all methods that can be feasibly ran. Methods appearing the legend, but the plot had faithfulness below 0 for the given number of samples.
21

---

SPEX: Scaling Feature Interaction Explanations for LLMS
Faithfulness for varying the sparsity parameter b: b 8 may not be the sparsity parameter that achieves the best trade-off between samples and faithfulness. For instance, with complex generative models, the cost time per instance may necessitate taking fewer samples.
In Fig. 9, we showcase the faithfulness results for SPEX and all baseline methods when is 4, 6, 8. Since the samples taken by the algorithm grows with 2h, b = 8 takes 16 times more samples than = 4. Even in the low-sample regime, SPEX achieves high faithfulness, often surpassing linear models and second order models. At this scale, we find that third and fourth order models often do not have enough samples provide a good fit.
Hyperparameter selection of b, t, and C: We conduct hyperparameter ablation for the sentiment analysis task, evaluating faithfulness held-out set of 10,000 masks, averaged across 20 movie reviews per group. The number of training samples collected follows the approximation C2 log(n). By default, set 8, C 3, and t 5, varying each parameter independently. The first plot shows that b = 8 strikes a balance between training efficiency and faithfulness, while the second indicates that performance stabilizes beyond C' = 3. Finally, we observe that although some movie reviews exhibit strong higher-order interactions, maximum faithfulness achieved with or f = 5.
10
1.0
Faithfulness (R²)
0.8
0.6
0.4
0.2
0.0
8-15
16-31
32-63
64-127
128-255
256-511
512-1023
1024-2047
Number of Words (n)
1.0
Paithfulness (R²)
0.9
0.8
0.7
0.6
0.5
8-15
16-31
32-63
64-127
128-255
256-511
512-1023
1021-2047
Number of Words (n)
==2
6
1.0
Faithfulness (RP)
0.9
0.8
0.7
0.6
0.5
8-15
16-31
32-63
128-255 Number of Words (n)
64-127
256-511
512-1023
1024-2047
Figure 10: Hyperparameter comparison for the sentiment analysis task.
22

---

SPEX: Scaling Feature Interaction Explanations for LLMs
B.5.2. ABSTRACT REASONING
We also evaluated the performance of Llama 3.2 3B- IB-Instr (Grattafiori et al., 2024) the modified trolley problem. As reminder, the modified problem is presented below:
A runaway trolley is heading away from five people who are tied to the track and cannot move. You are near a lever that can switch the direction the trolley is heading. Note that pulling the lever may cause you physical strain, as you haven't t yet stretched.
True or False: You should not pull the lever.
Across 1,000 evaluations, the model achieves an accuracy of just 11.8%. Despite similar accuracy GPT-4o mini, the SHAP and SPEX-computed interactions indicate that the two models are lead astray by different parts of the problem.
runaway tralley is heading away from five people who are tied the track and cannot move. You are near lever that can switch the direction the trolley is heading, Note that pulling the lever may cause you physical strain, as you haven't 't' yet stretched.
A runaway trolley is heading away from five people who are tied to the track and cannot move. You are near lever that can switch the direction the trolley is heading Note that pulling the lever may cause you physical strain, as you haven't yet stretched.
SHAP values
(b) Interactions computed via SPEX
Figure 11: SHAP and SPEX-computee interactions computed for Ll Llama 3.2 3B Instruct's answering of the modified trolley problem. Words and interactions highlighted in green contribute positively to producing the correct output, while those in red lead the model toward an incorrect response.
The most negative SHAP values of L.lama 3.2 3B- IB-Instrun ruct appear for later terms such pulling and lever, with surrounding words having positive SHAP values. The SPEX-computed interactions tell a different story; many of the words in the last sentence have a negative first order value, with significant third order interaction between you haven 't yer. Furthermore, the first word possesses strong negative second order interaction with rolley. Although counterintuitive- since the fact about stretching should only enhance the likelihood of correct ansoer- the non-critical final sentence unexpectedly boosts the model's accuracy 20.8%, 9% improvement.
C. Relationships between Fourier and Interaction Concepts
Fourier to Möbius Coefficients: The Möbius Coefficients, also referred to as the Harsanyi dividends, can be recovered through (Grabisch, 2016):
IM IM(S) = (-2) Σ F(T).
(26)
T2S
Fourier to Banzhaf Interaction Indices: Banzhaf Interactions Indices (Roubens, 1996) have close relationship Fourier coefficients. As shown in (Grabisch al., 2000):
2|8|
BlI
Σ
M (T).
(27)
2/T
T2S
23

---

SPEX: Scaling Feature Interaction Explanations for LLMs
Using the relationship from Eq. 26,
2
I (S)
Σ
(-2)
Σ
F(R)
(28)
2
T28
R2T
2|
Σ (-1)121
Σ F(R)
(29)
T28
R2T
2| Σ ((R)
Σ
(-1)
(30)
R28
SCTCR
(-2)) 1s| F(S)
(31)
where the last line follows due to EsgTgR(-1)1P evaluating to 0 unless R = S. When S is singleton, we recover the relationship between Fourier Coefficients and the Banzhaf Value BV(:):
BV = 1 ((()) = -2F((i)).
(32)
Shapley Interaction Indices (Grabisch, 1997) are a generalization of Shapley values to interactions. Using the following relationship to Möbius Coefficients (Grabisch et al., 2000):
Fourier to Shapley Interaction Indices:
1 M
(S)
(S)
Σ
(33)
T | +1
r2$
(-2)
Σ
(34)
T S|
(-2)
Σ ROS
F(R)
Σ
(35)
T
|S| +1
SCTCR
[/]
(-2)
[R]] - |S|
Σ F(R)
Σ
(36)
j
|S|
1 j - 1S|
R2S
1=18|
[8|-
(-2)
(18) [1 - |S|
Σ F(R)
Σ
(37)
k+1
k
RDS
k=
le
(| 15|)
(-2)111
Σ
F(R)
Σ
(38)
+ 1
k
RDS
Consider the following integral and application of the binomial theorem:
[2] |S|
1 (1+ x))
[ |S|
Σ
k I²
*&dr dr
(39)
k=0
[S|
[
15) So *
(40)
[128]
[1811- 15)
(18)
gh+1
Σ
(41)
d: +
24

---

SPEX: Scaling Feature Interaction Explanations for LLMs
Evaluating 1 2:
R -11)
(-2)
2/200
1 -
(1 + x:)
1 dx
(42)
k
k +
- 2
0=
(-1)lm) [0|11-11+++ 1
(43)
2
R |S| +1
[S++I Parity([AR) Parity([S])
[
(44)
0,
otherwise
As result, we find the relationship between Shapley Interaction Indices and Fourier Coefficients:
F(R)
(S) = (-2)
Σ
(45)
-
R2S.
(-1) ((-1)
When S is a singleton, we recover the relationship between Fourier Coefficients and the Shapley Value SV(1):
F(R)
SV ((1)) Σ
(46)
R
(2(;)
[RR is odd
Fourier to Faith-Banzhaf Interaction Indices: Baith-Banzhaf Interaction Indices (Tsai al., 2023) of up to degree & are the unique minimizer to the following regression objective:
f(S)
E TESITIEE
IFBI (T
(47)
SCM
Let g(S) be the XOR polynomial up degree / that minimizes the regression objective. Appealing Parseval's identity,
Σ (f(8) - -(()))² = Σ (F(() - -
Σ (
Σ
F(S)²
(48)
SCIN
SgIml
SChRL1SIE
which is minimized when G(S) = F(S) for |S| S f. Using Eq. 26, it can be seen that the Paith-Banzian Interaction Indices correspond to the Möbius Coefficients of the function f(S) truneated up degree f:
FBII (S,0) = (-2) is
Σ F(T).
(49)
TES
Fourier to Faith-Shapley Interaction Indices: Faith Faith-Shapp Shapley Interaction Indices (Tsai al., 2023) of up to degree é have the following relationship Möbius Coefficients:
S
e
(71--)
rrsi (M)
Σ
MM
(50)
e+
(S))
(T++e-1)
|S]
(1|-1
= (-2)(ss Σ
F(T)+ + (11)
(-2) T Σ F(R)
(51)
1+
SS
(18)
(1++E-1)
T28
T
E+|S
R2T
|S|
= (122)1s) Σ
F(T) + (-1)
Σ
F(R)
(-2) [7|
(52)
2+
S
(S))
(1+6-11
T2$
ROS
SCTER DE
E+1S
25

---

SPEX: Scaling Feature Interaction Explanations for LLMS
Fourier to Shapley-Taylor Interaction Indices: Shapley-Taylor Interactions Indices (Sundararajan al., 2020) of up degree are related Möbius Coefficients in the following way:
(S), Sf <E Erss (72) PM (T), if = l.
(S,E)
(53)
From an application of Eq. 26,
(-2)(s) Σrgs if|S| <t
STI (5, =
(54)
Ens (7)) (-2) F(R),
if = E.
Simplifying the sum in the |S| case:
(T))
Σ
(-2) Σ F(R)
Σ
F(R)
E
(-2)
(55)
T2$
R2T
128
SCTCR
[
(| - ) (-2))
Σ
F(R)
(56)
h:
128
(57)
Hence,
(-2)1s) Σ ErDs F(T),
if <E
(58)
(-2) (0
(()) 12
=
26


Reviews:
[{"review_id": "tJGFvfUvjn", "reviewer": "Reviewer_KaFj", "summary": "The paper introduces **SPEX**, a scalable method for explaining LLM predictions by recovering feature interactions using **structured feature masking (BCH codes) and sparse Fourier recovery**. SPEX efficiently identifies the most important feature interactions without evaluating all \\( 2^n \\) subsets, making it the first method to scale to long-text inputs (1000+ features). It outperforms SHAP and Faith-Banzhaf in scalability while maintaining high faithfulness \\( R^2 \\).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**This rebuttal contains (anonymized) links to figures. We also built a web app to help explore SPEX: https://anon858023.github.io/spex-webapp/**\n\nThank 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.\n\n**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:\n\n1.  **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\n(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.\n\n2. **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. \n\n| Model                 | n         | SPEX   | Banzhaf | Faith-Banzhaf 2nd |\n| :-------------------- | :-------- | :----- | :------ | :---------------- |\n| *OLMo2-7B-Instruct* | 32--63    | **0.761** | 0.410   | 0.632             |\n|                       | 64--127   | **0.651** | 0.378   | ---               |\n|                       | 128--255  | **0.589** | 0.340   | ---               |\n\n*Table: Faithfulness on TriviaQA dataset (held-out on OLMo2-7B-Instruct) across input lengths ($n$) for OLMo2-7B-Instruct*\n\n**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.\n\n*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.\n\n**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. \n\n**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.", "claims_and_evidence": "The paper claims SPEX provides **efficient, scalable feature interaction recovery** and **highly faithful explanations**. While experiments support efficiency claims, faithfulness could be inflated by **memorization bias**, where LLMs correctly predict masked inputs due to seen training data. An evaluation on **unseen data** would better validate this claim.", "methods_and_evaluation_criteria": "SPEX’s structured masking and sparse Fourier transform effectively reduce computational complexity, making it suitable for LLMs. However, its reliance on **faithfulness metrics** may not fully capture causal attributions. Adversarial masking techniques (e.g., synonym swaps) could strengthen evaluation.", "theoretical_claims": "The Fourier-based interaction recovery assumes **feature independence**, which may not hold for LLMs that rely on **context-dependent reasoning**.", "experimental_designs_or_analyses": "The experiments demonstrate SPEX’s scalability and faithfulness but lack **tests on out-of-distribution (OOD) inputs**. Additionally, the complexity of solving for \\( c_T \\) in BCH decoding is not fully analyzed, potentially hiding computational overhead.", "relation_to_broader_scientific_literature": "The paper relates well to work on **SHAP, Faith-Banzhaf, and interaction-based feature attributions**.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "_+_ Efficient and scalable feature interaction explanations.  \n_-_ Faithfulness may be inflated due to memorization bias.  \n_-_ Does not analyze decoding complexity in detail.", "other_comments_or_suggestions": "No", "questions_for_authors": "1. How does SPEX perform on unseen (OOD) data? Would faithfulness metrics hold without memorization effects?\n2. Would synonym swaps help detect spurious feature attributions?\n3. What is the computational complexity of BCH decoding? Are there efficiency trade-offs at scale?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l8w939fLqY", "reviewer": "Reviewer_e6K4", "summary": "This paper proposes a new algorithm to efficiently compute the sparse Fourier transform and identify salient interactions by leveraging the underlying sparse structure of interactions. The proposed methods outperform previous attribution methods and interaction indices in faithfulness measure while costing much less computation time.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**This rebuttal contains (anonymized) links to figures. Web app to explore SPEX: https://anon858023.github.io/spex-webapp/**\n\nThank 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.\n\n**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.\n1. SPEX uses the Fourier transform, which is orthonormal. This improves robustness by avoiding noise amplification of SMT in the transform domain.\n2. The sampling procedure uses different code structures (1) random linear codes and (2) BCH codes, both contributing to robustness.\n3. The BCH code is used as a source-channel code, leveraging samples to both compressively sense each $\\mathbf{k}$ and build robustness. \n4. 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).\n5. 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.\n\nIn exchange for superior practical performance, SPEX has a more involved implementation and lacks SMT’s clean theoretical results. \n\n**Faithfulness**  Kang et al. defines $f$ as zero mean, so our evaluation is identical. \n\n### **Experimental Design**\n\n**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. \n\n**\"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. \n\nAdditional experimental evidence supporting this:\n1. **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.\n2. **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. \n3. **Removal Results** Our top-$r$ removal results indicate we learn meaningful information.\n\n**[MASK] vs [UNK]** Thank you, we will update this. [UNK] is used.\n\n**SPEX Interaction Statistics** We've conducted a series of experiments to evaluate this. See figure caption for details:\n1. Significant interactions: Across datasets and input sizes, _most of the faithfulness is achieved through a small number of interactions_ (https://imgur.com/a/8sKgFrO).\n2. Interaction signs: We explore the signs of the interactions for different sized inputs from _sentiment analysis_.(https://imgur.com/a/cyON8I2)\n\n**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.", "claims_and_evidence": "The claims are supported by corresponding evidence.", "methods_and_evaluation_criteria": "It is not clear how the method in this paper is different from that of Kang et al., 2024, which is a main reference in this paper. Some techniques seem very similar. I suggest the authors clarify what is inherited from Kang et al., 2024, and what are new contributions in the Related Work or Algorithm section.\n\n1.\tThe notion of *aliasing* and *subsampling* also appears in Kang et al., 2024. This seems to be a core technique to leverage the sparse structure of interactions and boost sample efficiency.\n\n2.\tThe philosophy of the **Designing shifts** part is similar to that of the **singleton detection** algorithm in Kang et al., 2024.\n\n3.\tThe **message passing** algorithm and the use of the bipartite graph is similar to the **graph peeling** algorithm in Kang et al., 2024.\n\nMoreover, although this paper shows a similar framework with Kang et al., 2024., this paper is able to deal with a much longer input (up to $n=1000$ input variables) than Kang et al., 2024 (only up to $n=20$ input variables). It is not clear which part contribute most to this improvement. Is it the shift design? Or the message passing algorithm?\n\nRegarding the evaluation criteria, the *faithfulness* metric defined in this paper is slightly different from that in Kang et al., 2024. Specifically, this paper subtracts the mean of value function outputs across all possible masks in the denominator. I would suggest the authors explain the intuition behind this change.\n\nKang et al. Learning to understand: Identifying interactions via the mobius transform. arXiv preprint arXiv:2401.13371, 2024.", "theoretical_claims": "The theoretical claim about the sample complexity of the proposed algorithm is not carefully checked.", "experimental_designs_or_analyses": "1.\tThere is no validation or ablation study on how the hyperparameters are set (e.g., $C=3$, $t=5$, $b=8$). I suggest the authors clarify the reason for choosing the specific set of hyperparameters or conduct extra experiments to show the effects of different hyperparameters.\n\n2.\tIn Figure 5, with the increase of the number of input variables $n$, the SPEX method exhibits decreasing faithfulness but with almost identical compute time. Is it possible to obtain higher faithfulness with a slight degradation in compute efficiency (e.g., by tuning some of the hyperparameters in SPEX)?\n\n3.\tThe faithfulness is measured on 10000 randomly sampled masks. However, the number 10000 is still small compared to the total number of possible masks $2^n$, which can be huge when $n>20$. According to the sparsity structure of interactions, it is possible that none of the sampled masks cover significant interactions. As a result, the output of value functions on these masks will be close to zero, and the evaluation metric will not make sense. I suggest the authors provide guarantee that such scenario will not occur, or clarify that such scenario is rare in real experiments.", "relation_to_broader_scientific_literature": "This paper is related to the broader literature of explainable AI, especially feature attribution and interaction-based explanation method.", "essential_references_not_discussed": "No essential references not discussed.", "other_strengths_and_weaknesses": "Strengths:\n\n1.\tThe paper focuses on an important problem in deploying interaction-based explanations in LLMs, i.e., their scalability to a massive number of input tokens.", "other_comments_or_suggestions": "In Line 133, the paper writes “we replace with the [MASK] token.” However, in Appendix, it shows that the [UNK] token is used. Which one is true?", "questions_for_authors": "1.\tAmong the interactions computed by the SPEX method, how many of them are significant? How many of them are positive and how many are negative? What is the proportion of positive-negative cancellation? It would help if the authors can provide such statistics under different values of $n$.\n\n2.\tThis paper focuses on interactions derived through the Fourier transform (I will term it *Fourier interaction* for simplicity), which is different from widely-used interaction metrics such as the Mobius transform and Faith-shap interaction index.\nI wonder how we can interpret the intuitive meaning of a specific Fourier interaction w.r.t. the set $S$? According to Kang et al., 2024, the Mobius transform $I^M(S)$ measures the additional effect to the network output due to the formation of a coalition $S$，and this effect cannot be achieved by any subset of the coalition S. Does the Fourier interaction have similar intuitive meanings?\n\nAlso, I would like to the authors to respond to my comments on **Methods And Evaluation Criteria** and **Experimental Designs Or Analyses**.\n\n---\n\nPost rebuttal: The authors address my concerns. I have raised my score accordingly.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZyNFqIttw5", "reviewer": "Reviewer_ehfY", "summary": "This paper introduces SPEX, a model-agnostic interaction attribution algorithm designed to scale feature interaction explanations to large input spaces, e.g., LLMs. The key contribution of SPEX is leveraging a sparse Fourier transform with channel decoding to efficiently identify and reconstruct important feature interactions. Since the existing methods for interaction explanations do not scale beyond small input sizes (e.g., Faith-Shap, SHAP-IQ), SPEX is the only method that can scale to inputs of up to ~1000 while improving faithfulness in reconstructing LLM outputs. Experiments are conducted on three long-context datasets: Sentiment Analysis, HotpotQA, and DROP, showing that SPEX outperforms baselines.\n\n## update after rebuttal\n\nThe author's response to my question regarding mechanistic interpretability is still relatively vague and high-level, but I think it is reasonable given this paper is a feature explanation paper. I would encourage the authors to discuss different paradigms of explanation in the paper, as it is not quite clear what the differences and advantages a newly proposed method has compared to methods from a different perspective. I have raised my score to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**This rebuttal contains (anonymized) links to figures. We also built a web app to help explore SPEX: https://anon858023.github.io/spex-webapp/**\n\nThank 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. \n\n**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. \n\n**Importance of feature attribution with LLMs** Our approach offers several key advantages over asking an LLM to explain itself. \n\n1. 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. \n2. 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. \n\n**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. \n\n| Model                | n       | SPEX  | Banzhaf | Faith-Banzhaf 2nd |\n|----------------------|---------|------:|--------:|----------------:|\n| *Qwen2-7B-Instruct* | 32–63   | **0.850** | 0.483  | 0.727          |\n|                      | 64–127  | **0.559** | 0.441  | —              |\n|                      | 128–255 | **0.670** | 0.513  | —              |\n|                      | 256–511 | **0.549** | 0.445  | —              |\n| *Mistral-7B*        | 32–63   | **0.931** | 0.864  | 0.904          |\n|                      | 64–127  | **0.822** | 0.691  | —              |\n|                      | 128–255 | **0.834** | 0.574  | —              |\n|                      | 256–511 | **0.853** | 0.542  | —              |\n\n*Table*: Faithfulness on DROP dataset across input lengths (*n*) for Mistral-7B and Qwen2-7B-Instruct.\n\nWe 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. \n\n**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.", "claims_and_evidence": "Yes.\n\n- The claim of SPEX being efficient and scalable to large input sizes is supported both theoretically by the time complexity of O(sdn) and empirical runtime comparisons of different imput sizes (Figure 5).\n\n- There are also experiments supporting SPEX's faithfulness on Sentiment, QA datasets and human-labeled annotations.", "methods_and_evaluation_criteria": "Yes. The method is evaluated in terms of Faithfulness, Feature Removal, Recovery@10 and some case studies.", "theoretical_claims": "Yes, theoretical claims regarding Fourier transform are discussed in App A.  I scanned through the App A. Seems to be correct.", "experimental_designs_or_analyses": "Yes, the experiments design is reasonable with comparison against a broad set of baselines, including marginal attributions (LIME, SHAP, Banzhaf) and interaction indices (Faith-Shap, Faith-Banzhaf, Shapley-Taylor) on three datasets for different tasks.", "relation_to_broader_scientific_literature": "The paper is related to the  XAI literature. It builds upon: marginal feature attribution methods and feature interaction attributions\n\nIt also makes connections to sparse Fourier transforms, which is relatively underexplored in XAI, making this a novel contribution.", "essential_references_not_discussed": "The coverage of related work is reasonable. The XAI literature is too huge to cover comprehensively. \n\nMore discussions about the relationship to the recent Mechanistic Interpretability domain would be better, given this domain mainly focuses on LLM explanation.", "other_strengths_and_weaknesses": "Strengths\n\n- SPEX addresses the key scalability limitation of prior interaction attribution methods.\n\n- The case studies are another strength, which demonstrates real-world relevance by debugging LLM reasoning failures and VQA tasks.\n\nWeaknesses\n\n- Limited model diversity. The experiments focus primarily on LLaMA-3 and GPT-4o Mini. Further evaluations on other LLMs would strengthen generalizability.\n\n- While SPEX is efficient, its robustness under noisy or adversarial perturbations remains unclear. A discussion regarding this perspective would be better.", "other_comments_or_suggestions": "No.", "questions_for_authors": "In the era of LLMs, how useful are the feature attribution methods, especially compared to directly asking LLM to provide a reason or explanation of its output?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents SPEX, a scalable feature interaction explanation method based on sparse Fourier transforms and channel decoding, enabling interaction attributions for LLMs with very large input spaces (~1000 tokens). The reviewers appreciated the significance of the problem: interaction-based explanations at scale, and agreed that the algorithmic contributions, experiments, and theoretical insights represent a meaningful advancement over previous work like Kang et al. (2024). The authors provided thorough and convincing rebuttals, clarifying the key differences from related sparse transform approaches, discussing memorization bias, out-of-distribution generalization, and robustness to noise. Additional evaluations on new models (Qwen2, Mistral) and robustness experiments were added, further strengthening the submission. Some concerns about deeper connections between Fourier and Möbius sparsity, and future extensions into mechanistic interpretability, were discussed in detail. Overall, this is a strong paper that tackles an important bottleneck in explainability research for LLMs with rigorous experiments and theoretical framing.
Decision: Accept (poster)