ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs
Authors: Landon Butler
Abhineet Agarwal
Justin Singh Kang
Yigit Efe Erginbas
Bin Yu
Kannan Ramchandran
Venue: NeurIPS 2025 spotlight ()
Keywords: Interpretability
Signal Processing
Hierarchy
SHAP
Interactions
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Large Language Models (LLMs) have achieved remarkable performance by capturing complex interactions between input features. To identify these interactions, most existing approaches require enumerating all possible combinations of features up to a given order, causing them to scale poorly with the number of inputs $n$. Recently, Kang et al. (2025) proposed SPEX, an information-theoretic approach that uses interaction sparsity to scale to $n \approx 10^3$ features. SPEX greatly improves upon prior methods but requires tens of thousands of model inferences, which can be prohibitive for large models. In this paper, we observe that LLM feature interactions are often *hierarchical*—higher-order interactions are accompanied by their lower-order subsets—which enables more efficient discovery. To exploit this hierarchy, we propose ProxySPEX, an interaction attribution algorithm that first fits gradient boosted trees to masked LLM outputs and then extracts the important interactions.   Experiments across four challenging high-dimensional datasets show that ProxySPEX more faithfully reconstructs LLM outputs by 20\% over marginal attribution approaches while using *$10\times$ fewer inferences* than SPEX. By accounting for interactions, ProxySPEX efficiently identifies the most influential features, providing a scalable approximation of their Shapley values. Further, we apply ProxySPEX to two interpretability tasks. *Data attribution*, where we identify interactions among CIFAR-10 training samples that influence test predictions, and *mechanistic interpretability*, where we uncover interactions between attention heads, both within and across layers, on a question-answering task. The ProxySPEX algorithm is available at <https://github.com/mmschlk/shapiq>.

ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs
Landon Butler" Department of EECS
Abhineet Agarwal* Department of Statistics UC Berkeley aa3797@berkeley edu
Justin Singh Kang" Department of EECS UC Berkeley justin_ kangSberkeley. edu
UC Berkeley landonb@berkeley..o edu
Yigit Efe Erginbas
Bin Yu Departments of Statistics and EECS
Kannan Ramchandran
Department of EECS
Department of EECS
UC Berkeley erginbas@berkelly.cco edu
UC Berkeley binyu@berkeley.ccm edu
UC Berkeley kamnanr@berkeley edu
Abstract
Large Language Models (LLMs) have achieved remarkable performance by capturing com- plex interactions between input features. To identify these interactions, most existing ap- proaches require enumerating all possible combinations of features up to a given order, caus- ing them scale poorly with the number of inputs Recently, Kang al. (2025) proposed approach that uses interaction sparsity to scale to n = 10 features. SPEX greatly improves upon prior methods but requires tens of thousands of model inferences, which can be prohibitive for large models. In this paper, we observe that LLM fea- interactions often searaarchicl-highheee lower-order aabsets-which enables more efficient discovery. To exploit this hierarchy, we propose PROXYSPEX, an interaction attribution algorithm that first fits gradient boosted trees to masked LLM outputs and then extracts the important interactions. Experiments across four challenging high-dimensional datasets show that PROXYSPES more faithfulll reconstructs LLM outputs by 20% over marginal attribution approaches while using 10x fewer inferences than SPEX. By accounting for interactions, PROX efficiently identi- fies the most influential features, providing scalable approximation of their Shapley values. Further, we apply PROXYSPEX to two interpretability tasks. Data attribution, where we identify interactions among CIFAR-10 training samples that influence test predictions, and mechanistic interpretabilliyy where we uncover interactions between attention heads, both within and across layers, on a question-answeriigg task. The PROXYSPEX algorithm is avail- able at https::/ http:://ggtttu...oommmmmmmmeee com//mschhhk/shappi
SPEX, an
interactions are accompanied by their
Introduction
Large language models (LLMs) have achieved great success in natural language processing by cap- turing complex interactions among input features. Modeling interactions is only crucial for language, but also in domains such computational biology, drug discovery and healthcare, which require reasoning over high-dimensiooal data. In high-stakes contexts, responsible decision-making based on model outputs requires interpretability. For example, in healthcare, physician relying on LLM diagnostic assistance must intelligibly be able to explain their decision to patient.
Post-hoc feature explanation methods such as SHAP (II] and LIME [2] focus on marginal attribu- tions and do not explicitly capture the effect of interactions. To address this limitation, recent work
Equal contribution. Order determined coin flip.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Sentiment A Analysis (BERT)
Image Captioning (CLIP)
0.9
Faithfilhees (R²²
Faithfuinnss (AP))
0.8
10.6x
0,0x
0.7
12.8x
0.7
0.6
0.6
0.5
0.5
0.4
0.4
10a
# Model Inferences
# Model Inferences
LASSO
ProxySPEX (Ours)
SPEX
Figure 1: PROXYSPEX requires ~00 fewer inferences to achieve equally faithful explanations as SPEX for sentiment classification and image-captioning task using a BERT and CLIP model respectively. LASSO faithfulness plateaus indicating limits of marginal approaches.
has proposed interaction indices, such as Faith-Shap [R] that attribute all interactions up to given order d by exhaustively enumerating them. With n features, enumerating O(n*) interactions quickly becomes infeasible for even small n and d. Kang al. [ recently introduced SPEX, the first in- teraction attribution method capable of scaling up to n = 1000 features. SPEX scales with n by observing that LLM outputs are driven by small number of interactions. It exploits this sparsity by utilizing a sparse Fourier transform to efficiently search for influential interactions without enumer- ation. For example, with 100 features, SPEX requires approximately x 10* model inferences to learn order 5 interactions- small fraction of all possible 100 interactions. Nonetheless, 2 x 104 inferences prohibitively expensive for large models. Hence, the question naturally arises: Can identify additional structural properties among interactions to improve inference-effiienng,
We show empirically that local (i.e., input specific) LLM feature interactions are often hierarchical: for an order d interaction, an LLM includes lower-order interactions involving subsets those features (see Figure Z). We this develop PROXYSPEX. that reduces the number of inferences compared to SPEX by 10x while achieving equally faithful explanations. PROXYSPEX exploits this local hierarchical structure by first fitting gradient boosted trees (GBTs) as a proxy model to predict the output of LLMs on masked input sequences. Then, PROXYSPEX extracts important interactions from the fitted GBT' [5]].
interaction attribution algorithm
Evaluation overview. We compare PROXYSPEX to marginal feature attributions and SPEX across four high-dimensional datasets with hundreds of features. Results summarized below:
1. Faithfulness. PROXYSPEX learns more faithful representations LLM outputs than marginal approaches (= 1515% to 25%) average across datasets we vary the number of inferences. Fig- ure MI compares explanation faithfulness of PROXYSPEX to marginal attributions and SPEX.
Feature identification. By accounting for interactions, PROXYSPER identifies influential fea- tures that impact model outputs more significantly than marginal approaches, and can approximate Shapley values better than KernalSHAP in the low-inference regime.
3. Case study 1: Data attribution. Data Attribution is the problem of identifying training points responsible for given test prediction. On CIFAR- 10 [[]] PROXYSPEX identifies the interactions between training samples that most significantly impact classification performance.
4. Case study 2: Model component attribution. We use PROXY SPEX to study interactions be- tween attention heads, both within and across layers, on MMLU [ for 1e-aa....---IInnttt
[.. We observe that intra-layer interactions become more significant for deeper layers. PROX- YSPEX identifies interactions that allow to prune more heads than the LASSO.
Related work and applications
Feature and interaction attribution. SHAP [M] and LIME [2] are widely used for model-agnostic feature attribution. SHAP uses the game-theoretic concept of Shapley values [9] for feature attri-
bution, while LIME fits a sparse linear model [[O]. Cohen-Wang et al. [[ also consider fitting sparse linear model for feature attribution. Chen al. [122] uses an information-theore
approach
for feature attributions. Other methods [ |e] study model structure to derive feature attributions.

---

Sundararajan et al. [[5]] and Bordt and von Luxburg [ define extensions to Shapley values that consider interactions. Fumagalli et al. [[Z[] provides a framework for computing several interaction attribution scores, but their approach does not scale past s 20 features, which prevents them from being applied to modern MI. problems that often consist of hundreds of features. Note that some feature attribution approaches such as LIME and Faith SHAP|R [3] are formulated explicitly as a func- tion approximation, while others are defined axiomatically such as SHAP, though one can typically construct equivalent function approximation objectives with suitable distance metric.
Fourier transforms and deep learning explainability. Several works theoretically study the spec- tral properties of transformers. Ren et al. [[S]] show transformers have sparse spectra and Hahn and Rofin [ Abbe et al. [20] establish that they are low degree. Abbe et al. [21]. 22] study the bias of networks learning interactions via "staircase" property, i.c.. using lower-order terms to learn high-order interactions. Sparsity and low degree structure is also empirically studied in [23) [2]]. Kang et al. [25] shows that under sparsity in the Möbius basis [26]], a representation closely related to Shapley values and the Fourier transform, interaction attributions can be computed efficiently. Mohammadi et al. [2Z]] also learn sparse Möbius representation for computing Shapley values. Kang et al. [3]] use these insights to propose SPEX, the first robust interaction attribution algorithm to scale to the order of n as 1000 features. Gorji et al. [D] apply sparse Fourier transforms [28-31]] for computing Shapley values. They also provide an algorithm to extract the Fourier transform of tree-based models using single forward pass.
SPEX. We refer to the algorithm proposed in this manuscript as PROXYSPEX, in reference to SPEX, since both works exploit sparse interaction prior to reduce computational and sample bud- get. SPEX uses an algebraic structured sampling scheme, coupled with error correction decoding procedures to efficiently compute the interactions in the form of a Fourier transform. In contrast, PROXYSPEX uses random samples to learn a proxy model that implicitly exploits the sparse inter- action priors and our newly proposed hierarchical prior.
Mechanistic Interpretability (MI). MI seeks to uncover the underlying mechanisms of neural net- works and transformers [62]] in order to move past treating these models as black boxes. PROx- YSPEX answers the question "what combinations of inputs matter?" which is a vital precursor and complement to MI investigations that subsequently address "how does the model compute based on those specific imputs?" ?" Some closely related MI work attempts to recover circuits to explain under- lying model behavior [33] G4].. Hsu et al. [35]] use MI for interaction attribution. See Sharkey et al. [36) for a review of open problems and recent progress in MI.
3 PROXYSPEX
In this section, we first empirically justify our premise that significant interactions affecting LLM output are hierarchical we introduce PROXYSPEX, which aims to identify feature interactions for given input x while minimizing the number of expensive calls to an LLM.
high-order interactions imply important lower-order ones. Next,
3.1 Preliminaries
Value function. Let x be the input to the LLM consisting of n features For S C [n]. where [n] ,,, n. denote xs the masked input where retain features indexed in S and replace all others with the [MASK] token. For example, in the sentence x TThe sequel truly elevated the original", if {1, 2, 5, 6). Xs "Thh sequel [MASK] [MASK] the original". Masks can be more generally applied to any type of input such as image patches in a vision-language model. For a masked input xs and LLM f. let f(xs) R denote the output of the LLM under masking pattern S. The value function f is problem dependent. For classification tasks, a common choice is the logit of the predicted class for unmasked input, (xx). In generative tasks, f(xs) can represent the perplexity of generating the original output for the unmasked input. Since we focus on providing input-specific explanations, we suppress notation on x and denote ff (xs) as f(S).
Fourier transform of value function. Let 2 be the powerset of the index set. The value function I can be equivalently thought of as set function from f : 2|m] + R. Every such function admits
Features refer inputs given granularity, e.g., tokens in LLM image patches in vision model.
3

---

21.22 3
3223
3224
J72
J73
Figure 2: We observe that LLM feature interactions are often hierarchicalhighhr--oderr interactions accompanied by their lower-order subsets.
Fourier transform F; 2 + IR of f, related as follows:
1
Transform: F(T)
Σ (-1) sha S(S), 1
Inverse: S(S)
Σ MC
( (I)
2
The parameters (T) are known as Fourier coefficients and capture the importance of an interaction of features in subset T. Equation (Il) represents orthonormal transform onto parity (XOR)
basis [3Z]]. For the rest of the paper, we use the terms Fourier coefficient and interaction interchange-
ably. Further, refer to the set of Fourier coefficients (T, T S [n]} the spectrum.
Interpretable approximation of value function. We aim to learn an interpretable approximate function f that satisfies the following:
Faithful representation. characterize how well the surrogate function f approximates the true function, we define faithfulness [38]:
n² 11 f112
where 11/1
Σ S(S) SE(m]
J-
1 2
Σ S(S).
SC
Faithfulnees measures how well f predicts model output. High faithfulness implies accurate approximation of F(T) (this follows from orthonormality of (II).
2. Sparse representation. f should be succinct. Previous works [ 25
have shown that a sparse and low-degree ff can achieve high R². That is, F(T) R 0 for most T (sparsity), and [T)) is only large when [T] < n (low degree).
Efficient computation. Without any additional assumptions on the spectrum, learning f is ex- ponentially hard since there are 2" possible subsets T. PROXYSPEX relies the sparse, low degree Fourier transform along with the hicrarchy property to reduce LLM inferences.
faithful and sparse j allows straightforward computation of popular feature or interaction attribution scores defined in the literature, e.g., Shapley, Banzhaf, Influence Scores, Faith-Shapley. Closed-form formulas for converting F to various attribution indices are provided in Appendix
3.2 Empirical evidence of spectral hierarchies
To quantify the degree of hierarchical structure in LLMs, we introduce the following definition called Direct Subset Rate (DSR), defined for any value function and integer k.
DSR(F = Σ SEFi
1 (S)
where Fg denotes the k largest Fourier coefficients of f.
For the top i coefficients (i.e., interactions), DSR measures the average fraction of Fourier efficients that exclude only one of the features F(S \ (i)). For example, an f with F4 = {0, {1). (2), 11,3}} would have DSR of (1+1+1+1) = g. High DSR implics that sig- nificant high-order interactions have corresponding significant lower-order Fourier coefficients, as visualized Figure M Next, we show that two L.M based value functions have high DSR.
?
We take 20 samples from sentiment analysis task and an image captioning task [42]; see Section g for a detailed description and our choice of value function. We generate masks S and apply SPEX until our learned value function has faithfulness (f22) more than 0.9. Figure G visualizes the DSR
For S = 0. we set g

---

Sentiment Analysis (BERT)
Image Captioning (CLIP)
Direct Subset, Rate
100%
Direct Subset Rate
100%
80%
60%
60%
40%
40%
20%
0%
0%
16
32
128
256
16
32
64
128
256
Top Coefficients
Top Coefficients
Figure 3: The top-k interactions both sentiment analysis and image captioning task have high
DSR indicating strong hierarchical structure.
for various values of k, i.e., number top interactions. DSR is consistently larger than 80%, indi- cating strong hierarchical structure. In Appendix B.2,, we consider two additional metrics measuring hierarchical structure, and demonstrate that the top-k interactions are faithful.
Using GBTs to capture hierarchical Interactions. Tan et al. [B]]] proved that decision trees learn "staircase" functions, e.g., / I1 + 22 TI effectively due their greedy construction procedure. We empirically confirm this by comparing the performance of various proxy models on a synthetic hierarchical function (i.e., sum of staircase functions resembling Figure Q well as the Sentiment dataset in Appendix Figure II Appendix B4.44 details the simulation set-up. GBTss vastly outperform other proxy models, indicating their natural ability to identify hierarchical interactions with limited training data. Interestingly, GBT's outperform random forests well. This is because random forests are ineffective at learning hierarchical functions GBT-llkee algorithms disentangle sums effectively [0
[+ i.e., sums of staircases, while
Input
Masked Inference
The film embraces bold visuals and the plot rarely drags. However, glaring plot holes and forced jokes undercut impact.
The
embrioe
LLM
Proxy Fitting
Top Interactions
Positive
embraces
bold visuals
rarely
drags
Fourier Extraction
embraces bold visuals film However + 7 and the plot
undercut impact
g
glaring
plot
holes
41 rarely drags 38 undercut impact
Negative
glaring
plot holes
forced jokes
Figure 4: (1) PROXYSPEX masks subsets words and queries the LLM using this masked in- put. (2) It then fits GBTs a proxy model to learn the LLM's hierarchical interactions. (3) An interpretable sparse representation is extracted from the fitted GBT which captures the influential interactions.
3.3 PROXYSPEX via Gradient Boosted Trees to fit hierarchies
The PROXYSPEX algorithm (see Figure ;
Step Sampling and querying. Given LLM and input instance explain, generate a dataset D = (S;, (S.)), for training the proxy. The inputs S; represent the masks of x. Each mask S; is sampled uniformly from the set (n). The labels f(S.) are obtained by querying the LLM.

---

Sentiment Analysis
DROP
Fattfidnsss (RP)
+385%
+333%
-31%
Faithfulness (TP)
0.6
+3:4%
0.4
0.4
0.2
0.2
0.0
Inference Multiplier (a)
Inference Multiplier (a)
HotpotQA
MS-COCO
Fulthfulness (Rt)
0.3
+386
+230
-000
Fathifulness (It
0.8
++450
+3445
11.99
0.6
0.2
0.4
0.2
Inference Multiplier (a)
Inference Multiplier (a)
LASSO
ProxySPEX (Ours)
SPEX
Figure 6:
Comparison of faithfulness of different attribution methods with a n (ng)(n) training masks for different inference multipliers
{2, 6, 8). While SPEX only competitive with
LASSO for large the gap between PROXYSPEX and LASSO increases with a.
Step - Proxy Training. Fit GBTs to D with 5-fold cross-validation (CV).
Rel. Faithfulness
Step 3 Fourier extraction. We use Gorji et al.
[S] to extract the Fourier representation of the
0.6
fitted GBTs in single forward pass; see Ap- pendix A. With T trees of depth d there are at most O(T4") non-zero Fourier coefficients [5]. To improve interpretability, we sparsify the ex- tracted representation by keeping only the top & Fourier coefficients. Fig. shows that only As 200 Fourier coefficients are needed to achieve equiv- alent faithfulness for sentiment classification and image captioning (MS-COCO) dataset. Ad- ditional results regarding the sparsity of Fourier spectra learned by GBTs are in Appendix BER
0.4
Captioning
0.2
Sentiment
0.0
10a
10a
10a
10a
104
Sparsity (k)
Figure 5: Relative faithfulness as a function of Fourier sparsity. Only ~ 200 coefficients are re- quired achieve equivalent faithfulness. Spar- sity for sentiment is higher since inputs have larger n.
Step (Optional): Coefficient refinement via regression. As final step, we optionally regress the extracted, top k Fourier coefficients on the collected data D to improve the estimation. Empirically we observe this step can sometimes marginally improve performance, but seldom negatively impacts performance. This step is included it leads lower CV error.
4 Results
Datasets and models
Sentiment is a classification task composed of the Large Movie Review Dataset [ which con- sists of positive and negative IMDb movie reviews. We words input features and restrict to samples with n [256, 512]. We use the encoder-only fine-tuned DistilBERT model [47 [8], and the logit of the positive class the value function.
2. HotpoiQA | is a generative
cessiion-answriin task over Wikipedia articles. Sentences are input features, and we restrict to samples with [64, 128). We use Llama-3. --Bt-nnst and perplexity of the unmasked output as the value function.

---

Sentiment Analysis
DROP
LLLM Output
ALLM Outpur
6.3
0.9
4 0.8
0.01
3
3
# Features Removed (r)
# Features Removed (r)
HotpotQA
MS-COCO
0.35
I.LM Ontpue
0.20
A LLM Output.
0.20
0.30
0.15
0.20
0.30
0.08
Features Removed
Features Removed (r)
LASSO
ProxySPEX (Ours)
SPEX
By accounting for interactions, PROXYSPEX identifies more influential features across datasets than the LASSO. Apart from the sentiment analysis task (top left), SPEX does not collect enough training masks to out-perform LASSO.
Figure 7:
Discrete Reasoning Over Paragraphs (DROP) [50]] is a paragraph level question-answering task. We use words as input features and restrict to samples with n E [256, 512]. 512]. We use -lama-3-8B-Instrucct and the perplexity the unmasked output as the value function.
4. MS-COCO [+Z] contains images and corresponding text captions. Image patches and words the input features with E [60, 85). We use CLIP-ViT-B/32 a joint vision-language encoder, with the value function defined as the contrastive loss over all datapoints.
Baselines and hyperparameters. For marginal feature attributions, we use the LASSO. We use the same datasets [8] and add MS-COCO for an additional modality. It was shown in [[]] that popular marginal metrics such as SHAP are significantly less faithful than the LASSO, e.g., have
Rd < O. We use the LASSO implementation from scikit-learn, and choose the regulariza- tion parameter via 5-fold CV. For interaction indices, we compare PROXYSPEX to SPEX. Due to the scale of in our experiments, we cannot compare methods for computing interaction indices such as Faith-Shaplee, Faith-Banzhaf, and Shaplcy-Taylor using SHAP-IQ [I7]], and SVARM-IQ [БI], because they enumerate all possible interactions, making them computationally infeasible, For PROXYSPEX, a list of GBT hyper-paramett parameters we tune over are in Appendix B.
4.1 Faithfulness
We compare attribution method faithfulness by varying the number of training masks. For each sample with features, we generate n (n) masks, varying difficulty across inputs of varying lengths (some by over 100 tokens). This log(n) type scaling is heuristically guided by compressed sensing bounds [52]]. These suggest the number of samples required grows with sparsity (assumed x n) and logarithmically with problem dimensionality (if dimensionality for degree-d interactions is se ndd, this yiclds a log(n=) lllgg() factor). Together, these factors support an n log(n) scaling. While not directly applicable, these bounds offer a useful heuristic for how sampling complexity scales with
{2, 6,6, 8], to normalize
Figure shows average faithfulness over 1,000 test masks per sample. PROXYSPEX outperforms LASSO with limited inferences and continues to improve where LASSO plateaus, indicating that it learning influential interactions. While SPEX often faster for the same number of masks, SPEX needs additional inference time match R², making PROXYSPEX faster overall. For the smaller DistilBERT model under the sentiment analysis task, the wall clock speedup is ~3x, while with the bigger CLIP-ViT-B// model with MS-COCO we see ~5x speedup (See Appendix B.

---

Sentiment Analysis
DROP
Shapley Recallo
Shapley Recall@10
0.40
0.7
0.33
0.6
0.5
0.30
04
0.25
0.25
0.5
0.75
0.25
0.5
0.75
1.0
Inference Muleiplier (a)
Inference Multiplier (a)
HotpotQA
MS-COCO
Shapley Recall881
0.50
Shapley Recal1a10
0.45
0.6
0.35
0.25
0.5
0.76
1.0
0.20
0..5
0.75
1.0
Inference Multiplier (a)
Inference Multiplier (a)
KernelSHAP
ProxySPEX (Ours)
Figure 8: Recall of the top ten Shapley values after a n log2(n)) inferences for multipliers (0.25, 0.5, 0.75, 1.0]. For small a, PROXYSPEX is superior at recovering the most significant features, while KernalSHAP outperforms increases. Error bands indicate the standard deviation across ten different runs of the algorithms.
4.2 Feature Identification
We measure the ability of methods to identify the top features influencing LLM outputs:
A LLM Output (r) [f(m)) - f(S))
S argmax (f((m)))))))))))(())) - f(S)).
(4)
[f((m))
|
Solving Eq. for an arbitrary f presents a challenging combinatorial optimization problem. How- ever, PROXYSPEX and SPEX represent f as a sparse Fourier transform. This representation facil- itates solving the optimization Fourier representation ensures that the time required to solve this program is negligible compared to sampling the LLM and fitting the GBT's Full details of the construction of this program given in Appendix A. Under LASSO, Eq. is easily solved through selecting features by the size of their coefficients. We measure the removal ability of different attribution methods when we collect 8n (n) training masks and plot the result in Figure M. By accounting for interactions, PROX- YSPEX identifies significantly more influential features than the LASSO. Apart from the sentiment analysis task, SPEX does not collect enough training masks to outperform the LASSO.
tractable linear integer program. The sparsity of the extracted
4.3 Shapley Value Approximation
PROXYSPEX can be directly used to approximate Shapley values. Across all tasks, we first run KernelSHAP with 10,000 test masks and treat these approximated Shapley values as ground truth. We measure the recall of the top ten highest-magnitude Shapley values for KerneISHAP and PROX- YSPEX under a-n logg(? inferences with multipliers a E (0.25, 0.5, O. 75, 1.0]. For this inference budget, competing algorithms such LeverageSHAP [5>3]] and SVARM [544]] struggle provide ac- curate approximations. We find PROXYSPEX initially provides a better coarse approximation than KernelSHAP (Figure IT). However, since PROXYSPEX is optimized for faithfulness and does not rely on the Shapley kernel, it is eventually surpassed by KerneSSHAP with enough inferences. Ad- ditional results under mean squared error are included in Appendix B.S.
5
Case studies
We now present two case studies of PROXYSPEX for two different interpretability problems: data attribution [5S] and model component altribution [56], a key problem in mechanistic interpretability. We first show how both of these tasks can be reformulated as feature attribution tasks; recent work has highlighted the connections between feature, data, and model component attribution [57]]
8

---

Heldout Image
Synergistic Interactions
Heldout Image
Redundant Interactions
BBird
Bird
Truck
Airplane
Airplane
Bird
Bird
Bird
Dog
Horse
Cat
Cat
Horse
Dog
Dog
Dog
Automobile
Automobile
Truck
Truck
Frog
Bird
Bird
Bird
Figure 9: Synergistic interactions: data that together are more valuable together than the sum of their parts and aid in classification. Redundant interactions: Data that may contain similar information, their combined influence is less than the sum of the parts.
5.1 Data Attribution via Non-Linear Datamodels
Data attribution for classification the problem of understanding how fitting model go subset of training samples affects the prediction of a test point of class c. This problem can be converted into framework by defining an appropriate value function
f(S) - (logit for on z) (highest incorrect logit on z), when go is trained on S.
(5)
The value function quantifies the impact of subset S on the classification of Sampling very expensive since it involves training a new model ge for every subset S. As a result, most data attribution approaches do not consider the impact of interactions. Notably, Ilyas et al. [55] use LASSO to learn f when training a ResNet model on the CIFAR-10 1-10 dataset [6]] As a case study, we apply PROXYSPEX to understand the impact of interactions between CIFAR-10 training samples.
Defining data interactions. Interactions between samples can be either redundant interactions or synergistic interactions. Redundant interactions are when the influence of a subset S is not additive. Redundancy typically occurs between highly correlated samples, e.g., semantic duplicates [58]. Synergistic interactions occur when a subset S influences prediction by shaping a decision boundary that no individual sample could so by itself. That is, the model needs the combined effect of training samples in S to correctly classify
Results. We visualize interactions learned by PROXYSPEX in Figure for randomly selected CIFAR-10 test points. Experimental details are in Appendix C.I. PROXYSPEX identifies highly similar training samples (redundancies) as well as synergistic interactions between samples of dif- ferent classes. See Appendix CT for examples of other randomly selected test samples.
5.2 Model Component Attribution
We study the role of attention heads for a question-answeeteeee task using Llama-3. 1-0-:..-------nntut and MMLUU hhigh-scholl-us-histrryy head feature and aim identify interactions among heads using PROXYSPEX. Let L represent the number of layers in an LLM and let L C [4] represent subset of the layers. Let Hc denote the of attention heads within these layers. For subset of heads S Hc. we set the output of heads in He \ S to and denote the ablated LLM as LLMs Define f as:
which multiple-choice dataset. We treat each attention
fe(S)= Accuracy of LLMs training of MMLU.
(6)
Pruning results. use the LASSO and PROXYSPEX to identify most important heads for various sparsity levels ( i.e., the number of retained heads) across different sets of layers. We also compare a Best-of-N baseline, where we take the best of = 5000 different randomly chosen S.
further details are in Appendix en
We use the procedure detailed in Section y to identify heads

---

Unpruned Acc.
Best-of-N
LASSO
ProxySPEX (Ours)
Layers 1-3
Layers 14-16
Layers 30-32
Tost Accurccy
1:0%%
0.8
0.8
0.7
0.7
0.7
50%
66%
83%
50%
66%
83%
50%
66%
83%
% of Attention Heads Kept
80%
8% 12%
67%
23%
10%
51%
39%
10%
% of ProxySPEX's Spectral Energy
Linear
Within-Layer Inter.
Across-Layer Inter.
Figure 10: Attention head pruning for Llama-3. 1--B--In-trrutt for MMLU (high- (high-school-us- history). Top: We report the test accuracy vs. percentage of heads retained, comparing PROx- YSPEX, LASSO, and Best-of-N across layer groups (1-3, 14-16, 30-32). Unpruned accuracy shown by dashed line. Bottom: PROXYSPEX's learned spectral energy distribution into linear effects, within-layer, and across-layer interactions per layer group.
to remove for both PROXYSPEX and LASSO. Test accuracies for each method presented in Figure M+ at three different sparsity levels, and with three different layer ranges: initial (1-3), middle (14-16) and final (30-32). We observe that PROXYSPEL consistently outperforms both baselines, with higher test accuracy on the pruned models identified using PROXYSPEX.
Characterizing interactions between attention heads. Analyzing the Fourier spectrum learned by PROXYSPEX offers insights into the nature of the internal mechanisms of the LLM. As shown in Figure I (bottom), the spectral energy attributed to interactions, particularly within-layer interac- tions, markedly increases deeper layers Ll a.lama-3... Instructt. There are many works that look at the differing functional roles of attention heads across layers [59]. PROXYSPEX provides an exciting new quantitative approach to further investigate these phenomena.
Discussion
Conclusion. We introduce PROXYSPEX, inference-efficient interaction attribution algorithm that efficiently scales with n by leveraging an observed hierarchical structure among significant inter- actions in the Fourier spectrum of the model. Experiments across 4 high-dimensional datasets show that PROXY SPEX exploits hierarchical interactions via a GBT proxy model to reduce inferences by 100 SPEX [ while achieving equally faithful explanations. Through applications data and model component attribution, we demonstrate the importance of efficient interaction discovery.
Limitations. GBTs effectively capture hierarchical interactions but may not perform well when interactions have a different structure. For example, simulations in Appendix |ل empirically con- firm that GBTs suffer in the case of sparse but non non-hierarchical functions. More generally, in cases where the proxy GBT model is not faithful, the interactions identified by PROXYSPEX might not be representative of the model's reasoning. Another limitation is the degree of human interpretabil- ity that can be understood from computed interactions. While interactions can offer richer insights, they more difficult to parse than marginal alternatives. Further improvements in visualization and post-processing of interactions are needed to fully harness the advances of PROXYSPEX.
Future work. Inference-efficiennc could be further improved by exploring alternative proxy mod- els, additional Fourier spectral structures, or adaptive masking pattern designs. Integrating PROx- YSPEX with internal model details, such via hybrid approaches with MI or by studying its con- nection to sparsity in transformer attention [[0]] offers another promising avenue. Finally, further deepening and improving applications of PROXYSPEX in data attribution and mechanistic inter- pretability as well as potentially exploring more complex value functions or larger-scale component interactions remains interesting future work.
10

---

Acknowledgments and Disclosure of Funding
This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-2146752. Any opinions, findings, and conclusions or recommendations expressed in this material are those the author(s) and do not necessarily reflect the views of the National Science Foundation.
This work used NCSA DeltaAl at UTUC through allocation CIS250245 from the Advanced Cy- berinfrastructure Coordination Ecosystem: ported by U.S. National Science Foundation grants #2138259, #2138286, #2138307, #2137603, and #2138296.
Services & Support (ACCESS) program, which is sup-
B.Y. gratefully acknowledge partial support from NSF grant DMS-2413265, NSF grant DMS 2209975, NSF grant 2023505 on Collaborative Research: Foundations of Data Science Institute (FODSI), the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-2031880 and 814639, NSF grant MC2378 to the Institute for Artificial CyberThreat Intelligence and OperatioN (ACTION), and NIH grant R01GM1
References
[1] M. Lundberg and S.-I. Lee, "A unified approach to interpreting model predictions," in Ad- vances in Neural Information Processing Systems, 2017, pp. 4768
[2] M. T. Ribeiro, S. Singh, and C. Guestrin, ""ees should I trust you?" Explaining the predictions of any classifier," in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016, pp. 1135-1144.
[3] C.-P. Tsai, C.-K. Ych, and P. Ravikumar, "Faith-Shayy Shap: The faithful Shapley interaction index," Journal of Machine Learning Research, vol. 24, no. 94, pp. 1-42, 2023.
[4] J. S. Kang, L. Butler, A. Agarwal, Y. E. Erginbas, R. Pedansani, K. Ramchandran, and B. Yu, "SPEX: Scaling Feature Interaction Explanations for LLMs," International Conference on Ma- chine Learming (ICML), 2025.
[5] A. Gorji, A. Amrollahi, and A. Krause, "SHAP values via sparse Fourier representation," in Advances in Neural Information Processing Systems, 2025.
[6] A. Krizhevsky and G. Hinton, "Learning multiple layers of features from tiny images," " 2009, Technical Report.
[7] D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt, "Mea- suring massive multitask language understanding." in International Conference on Learning Representations (ICLR), 2021.
[8] A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, A. Yang. A. Fan, A. Goyal, A. Hartshor, A. Yang, A. Mitra, A. Sravankumar, A. Korenev, A. Hinsvark, A. Rao, A. Zhang, A. Rodriguez, A. Gregerson, A. Spataru, B. Roziere, B. Biron, B. Tang, B. Chern, C. Caucheteux, C. Nayak al., "The llama 3 herd of models," 2024. [Online]. Available: https://aniw.or//ab//2277.111
[9] L. S. Shapley, A Value for N-Person Games. Santa Monica, CA: RAND Corporation, 1952.
[10] R. Tibshirani, "Regression shrinkage and selection via the LASSO." Journal of the Royal Sta- ristical Society Series B: Statistical Methodology, vol. 58, no. pp. 267-288, 1996.
[11] B. Cohen- Cohen-Wang, Shah, K. Georgiev, and A. Mądry, "ContextCite: Autributing model gen- eration to context," in Advances in Neural Information Processing Systems, 2024, pp. 95 764- 95 807.
[12] J. Chen, L. Song, M. Wainwright, and M. Jordan, "Learning to explain: An information- theoretic perspective on model interpretation," in International Conference on Machine Learn- ing (ICML), 2018, pp. 883-892.

---

[13] M. Sundararajan, A. Taly, and Q. Yan, "Axiomatic attribution for deep networks," in Interna- tional Conference on Machine Learning (ICML), 2017, pp. 3319-3328.
[14] A. Binder, G. Montavon, S. Lapuschkin, K.R. Müller, and W. Samek, "Layer-wise relevance propagation for neural networks with local renormalization layers," in International Confer- ence on Artificial Neural Networks, 2016, pp. 63-71.
[15] M. Sundararajan, K. Dhamdhere, and A. Agarwal, "The Shapley Taylor interaction index," in International Conference on Machine Learning (ICML), Jul 2020, pp. 9259-9268.
[16] S. Bordt and U. von Luxburg, "From Shapley values to generalized additive models and back," in International Conference on Artificial Intelligence and Statistics (AISTA7S), 2023, pp. 709- 745.
[17] F. Fumagalli, M. Muschalik, P. Kolpaczki, E. Hüllermeier, and B. E. Hammer, "SHAP-IQ: Unified approximation of any-order Shapley interactions," in Advances in Neural Information Processing Systems, 2023.
[18] Q Ren, J. Gao, W. Shen, and Q. Zhang, "Where we have arrived in proving the emergence of sparse interaction primitives in DNNs," in International Conference Learning Representa- tions (ICLR), 2024.
[19] M. Hahn and M. Rofin, "Why are sensitive functions hard for transformers?" in Annual Meet- ing of the Association for Computational Linguistics (ACL), December 2024.
[20] E. Abbe, S. Bengio, A. Lotfi, and K. Rizk, "Generalization the unseen, logic reasoning and degree curriculum," " Journal of Machine Learning Research, vol. 25, no. 331, pp. 1-58, 2024.
[21] E. Abbe, E. Boix-Ad M. S. Brennan, G. Bresler, and D. Nagaraj, "The staircase prop- erty: How hierarchical structure can guide deep learning," in Advances in Neural Information Processing Systems, 2021, pp. 26 989-27 002.
[22] E. Abbe, E. Biox-Adsera, and T. Misiakiewicz. "The perged-staircant property: A necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural net- works," in Conference on Learning Theory, 2022, pp. 4782-4887
[23] D. Tsui and A. Aghazadeh, "On recovering higher-order interactions from protein language models," " in ICLR Workshop on Generative and Experimental Perspectives for Biomolecular Design, 2024.
[24] Ren, Z. Zhou, Q. Chen, and Q. Zhang, "Can we faithfully represent absence states compute Shapley values on a DNN?" in International Conference on Learning Representations (ICLR), 2023.
[25] S. Kang, Y. Erginbas, L. Butler, R. Pedarsani, and K. Ramchandran, "Learning to un- derstand: Identifying interactions via the Möbius transform," Advances in Neural Information Processing Systems, 2024.
[26] J. C. Harsanyi, "A bargaining model for the cooperative n-person game," Ph.D. dissertation, Department of Economics, Stanford University, Stanford, CA, USA, 1958.
[27] M. Mohammadi, Tiddi, and A. Ten Teije, "Unlocking the game: Estimating games in Möbius representation for explanation and high-order interaction detection," AAAA Conference Arti- ficial Intelligence, pp. 19 19512-19519, Apr. 2025.
[28] X. Li, K. Bradley, S. Pawar, and K. Ramchandran, "The SPRIGHT algorithm for robust sparse Hadamard transforms," in IEEE International Symposium on Information Theory (ISIT), 2014, pp. 1857-1861.
[29] A. Amrollahi, A. Zandich, M. Kapralov, and A. Krause, "Efficiently learning Fourier sparse set functions," in Advances in Neural Information Processing Systems, 2019.
[30] Y. E. Erginbas, J. Kang, A. Aghazadeh, and K. Ramchandran, "Efficiently computing sparse Fourier transforms of q-ary functions," IEEE International Symposium on Information The- ory (ISIT), 2023, pp. 513-518.
12

---

[31] R. Scheibler, S. Haghighatshoar, and M. Vetterli, "A fast Hadamard transform for signals with sublinear sparsity in the transform domain," IEEE Transactions on Information Theory, vol. 61, no. 4, pp. 21 2115-2132, 2015.
[32] C. Olah, N. Cammarata, L. Schubert, G. Goh, M. Petrov, and S. Carter, "Zoom in: An introduction to circuits," Distill, 2020. [Online]. Available: https://issilllppb/222ZZeeennnn zoom-in
[33] A. Conmy, Mavor-Parker A. Lynch, S. Heimersheim, and A. Garriga-Alonso, "Towards automated circuit discovery for mechanistic interpretability." Advances in Neural Information Processing Systems, pp. 16318-16 352, 2023.
[34] A. Syed, C. Rager, and A. Conmy, "Autribution patching outperforms automated circuit dis- covery," in EMNLP BlackboxNLPP Workshop: Analyzing and Interpreting Neural Networks for NLP, Nov. 2024, pp. 407-416.
[35] A. R. Hsu, G. Zhou, Y. Cherapanamjeri, Y. Huang, A. Odisho, P. R. Carroll, and B. Yu, "Effi- cient automated circuit discovery in transformers using contextual decomposition." in Interna- lional Conference on Learning Representations (ICLR), 2025.
[36] L. Sharkey, B. Chughtai, J. Batson, J. Lindsey, J. Wu, L. Bushnaq. N. Goldowsky-DDe S. Heimersheim, A. Ortega, J. I. Bloom, S. Biderman, A. Garriga-Alonso, A. Conmy, Michaud, S. Casper, M. Tegmark, D. Bau, E. Todd, A. Geiger, M. Geva, J. Hoogland, D. Murfet, and
N. Nanda, J. M. Rumbelow, M. Wattenberg, N. Schoots, J. Miller, W. Saunders,
T. McGrath, "Open problems in mechanistic interpretability. Transactions on Machine Learn- ing Research, 2025.
[37] R. O'Donnell, Analysis of Boolean functions. Cambridge University Press, 2014.
[38] Y. Zhang, H. He, Tan, and Y. Yuan, "Trade-off between efficiency and consistency for removal- based explanations," in Advances in Neural Information Processing Systems, 2023, pp. 25 627-252-666 661.
[39] G. Valle-Perez, C. Q. Camargo, and A. A. Louis, "Deep learning generalizes because the garameter-function map is biased towards simple functions," in International Conference Learning Representations (ICLR), 2019.
[40] G. Yang and H. Salman, "A fine-grained spectral perspective on neural networks," 2020. [Online]. Available: https://axdw.or//aa//997....
[41] Q. Ren, J. Zhang, Y. Xu, Y. Xin, D. Liu, and Q. Zhang, "Towards the dynamics of a dnn learning symbolic interactions," in Advances in Neural Information Processing Systems, 2024, pp. 50 653-50 688.
[42] T.-Y. Lin, M. Maire, J. Belongiie L. D. Bourdev, R. B. Girshick, J. Hays, P. Perona, D. Ra- manan, Dollár, and C. L.. Zitnick, "Microsoft COCO: Common objects in context," Euro- pean Conference Computer Vision (ECCV), 2014, pp. 740-755.
[43] Y. S. Tan, J. M. Klusowski, and K. Balasubramanian, "Statisiical-computttionn trade-offs for recursive adaptive partitioning estimators." 2025. [Online]. Available: https://arxi.oog/abs//1111111..1
[44] Y. Shuo Tan, A. Agarwal, and B. Yu, "A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds," in AAAI Conference on Artificial Intelligence, Mar 2022, pp. 8663-9685.
[45] Y. S. Tan, C. Singh, K. Nasseri, A. Agarwal, J. Duncan, O. Ronen, M. Epland, A. Kornblith, and B. Yu, "Fast interpretable greedy-tree sums," Proceedings of the National Academy of Sciences, vol. 122, no. 7, 2025.
[46] A. L. Maas, R. E. Daly, T. Pham, D. Huang, A. Y. Ng, and C. Pout,, "Learning word vectors for sentiment analysis," Annual Meeting of the Association for Computational Linguistics (ACL), June 2011, pp. 142-150.
13

---

[47] V. Sanh, L. Debut, J. Chaumond, and T. Wolf, "Distilbert, distilled version of bert: smaller, faster, cheaper and lighter," 2020. [Online]. Available: https:/aaxv..rraa////1000111
[48] K. Odabasi, "DistilBERT Finetuned Sentiment," " accessed January 2025. [Online]. Available:
[49] Z. Yang, P. Qi, S. Zhang, Y. Bengio. W. Cohen, R. Salakhutdinov, and C. D. Manning, "Hot- potQA: A dataset for diverse, explainable multi-hop question answering," in Conference on Empirical Methods in Natural Language Processing (EMNLP), 2018, pp. 2369-2380.
[50] D. Dua, Y. Wang, S. Dasigi. S. Singh, M. Gardner, and T. Kwiatkowski, "DROP: A reading comprehension benchmark requiring discrete reasoning over paragraphs," in Annual Meeting of the Association for Computational Linguistics (ACL), 2019, pp. 2368-2378.
[51] Kolpaezki, M. Muschalik, F. Fumagalli, B. Hammer, and E. Hüllermeier, "SVARM-IQ: Efficient approximation of any-order Shapley interactions through stratification," in AAAI Con- ference on Artificial Intelligence, 2024, pp. 3520-3528.
[52] E. Candes and T. Tao, "Decoding by linear programming." " IEEE Transactions on Information Theory, vol. 51, 12, pp. 2203-4215, 2005.
[53] C. Musco and R. T. Witter, "Provably accurate Shapley value estimation via leverage score sampling," in International Conference on Learning Representations (ICLR), 2025.
[54] P. Kolpaczki, V. Bengs, M. Muschalik, and E. Hüllermeier, "Approximating the Shapley value without marginal contributions," in AAAI Conference on Artificial Intelligence, 2024, pp. 13
[55] A. Ilyas, S. M. Park, L. Engstrom, G. Leclerc, and A. Madry. "Datamodels: Understanding pre- dictions with data and data with predictions," in International Conference on Machine Learn- ing (ICML), 2022, pp. 9525-9587.
[56] H. Shah, A. lyas, and A. Mądry, "Decomposing and editing predictions by modeling model computation," in International Conference on Machine Learning (ICML), 2024, pp. 44 244- 292.
[57] S. Zhang, T. Han, U. Bhalla, and H. Lakkaraju, "Building bridges, not walls: Advancing interpretability by unifying feature, data, and model component attribution," in ICLR Workshop on Navigating and Addressing Data Problems for Foundation Models, 2025.
[58] A. K. M. Abbas, K. Tirumala, D. Simig, S. Ganguli, and A. S. Morcos, "SSeDDDup:: Data- efficient learning at web-scale through semantic deduplication," in ICLR Workshop on Mathe- matical and Empirical Understanding of Foundation Models, 2023.
[59] W. Shi, S. Li, T. Liang, M. Wan, G. Ma, X. Wang, and X. He, "Route sparse autoencoder to interpret large language models," in Conference Empirical Methods in Natural Language Processing (EMNLP), 2025, pp. 6812-6826.
[60] B. Chen, T. Dao, E. Winsor, Z. Song, A. Rudra, and C. Ré, "Scatterbrain: Unifying sparse and low-rank attention," Advances in Neural Information Processing Systems, pp. 17 473-1-1740 426, 2021.
[61] M. Li and Q. Zhang, "Technical note: Defining and quantifying AND-OR interactions for faithful and concise explanation of DNNs." " 2024. [Online]. Available:
https:
Varxiv.org/ab//2344.333
[62] E. Kushilevitz and Y. Mansour, "Learning decision trees using the Fourier spectrum," in Annual ACM Symposium on Theory of Computing (STOC), 1991, pp. 455-464.
[63] Y. Mansour, "Learning Boolean functions via the Fourier transform." in Theoretical Ad- vances in Neural Computation and Learning, V. Roychowdhury, K. Siu, and A. Orlitsky, Eds. Springer, 1994, pp. 391-424.
14

---

Appendices
Method Detais
16
Fourier Conversions
16
Fourier Extraction
16
Sparse Fourier Optumization
17
Experimental Details
19
B.1
Implementation Detail
19
B.I.1
19
B.1.2
Sentiment Analysis
19
B.1.3 HotpotQA
19
DROB
19
B.I.S MS-COCO
20
B B.2
Measuring Spectral Hierarchies
20
Sparsification
20
Proxy Model Selection
Shapley Value Approxımation
22
8.6 Practical Implications
22
Case Study Details
23
Data Attribution via Non- Jinar Datamode
23
Model Component Attriuution
28
15

---

A Method Details
A.1 Fourier Conversions
INTERACTION INDEX
FOURIER CONVERSION
Banzhaf V%
-2F((())
Shapley di
(-2) Σ 8210 [8] is odd
F(S) TST
Influence &
Σ F(S)²
Möbius (T)
(-2) Σ F(S)
$2T
Σ Esgin) F(S)
if =
Or (T)
(-2) Σ (-1)15) F(S)
if +
92T
Banzhaf Interaction (T)
-TF(T)
Shapley Interaction (S(
(-2) Σ Es2t s.t. (-1)181---1)1 151-14
F(S)
MM)),
[T| <
[18]
Shapley Taylor 18T (T)
Σ
(S), [7| = E.
i
52T
Faith-Banzhaf (2)
(-2) '1 Σ SDT F(S) 18
(7]
((ST)E
e [T| (T)
SST STDE
Paith-Shapley (F((T)
(RI
where (S,T,() E
(1i++-11) (-2)
TCRES
e+|Ti
[R|SE
The relationship between Fourier coefficients and influence scores are provided in [[2]] We derive the conversion between Fourier and the OR interaction index [6]]] in this work. All remaining conversions are derived in Appendix of [[]]
A.2 Fourier Extraction
The exact Fourier transform of a decision tree can be computed recursively (5L, 62, [3
Due to the linearity of the Fourier transform, the Fourier transform of each boosted tree can be computed separately and added together. Algorithm M. provided by [55], proceeds by traversing the nodes of each tree and summing the resultant Fourier transforms.
16

---

Algorithm Fourier Extraction from Gradient Boosted Trees [[]]
Require: Gradient boosted model M
Ensure: Fourier mapping J.
1: Initialize F <-
2: for Tree T" in .M do
3:
F J-F.mmerp FFueree(EXTRCCCTTRCCCCCCC
>> Add mappings of the individual trees
4: end for
5: return F
6: procedure EXTRACTTREE(node n)
7: if is leaf then
8:
return {0 + n.value)
9:
else
10:
N₁ ExTRACTTRRm(1Jeefchhhlll
11:
NR +- EXTRACCTTREs((nniittcchiii W+0
12:
13:
for S in Kiys LeeysUNia UNR. do
14:
UL N2[5]
b Mapping returns 0 if not contained
15:
VR + NR[S]
16:
M[S + (Uz t2n)2
17:
N U (n.featureSplit]] +- (0z. - UR)/
18:
end for
19: end
20: return V
21:
end procedure
A.3
Sparse Fourier Optimization
We assume f(8) is sparse, low-degree function with support K:
f(S)
(-1)115T F(T)
TEK
Equivalently, the function can be represented (and efficiently converted) under the Möbius transform.
Converting Fourier Möbius (via Appendix I.I.). letting IC+ { R applying the inverse Möbius transform:
S T
T T K). and
f(S)=
Σ
iM
REK+,
The optimization problem can then be expressed as polynomial over (0,1). Let x be a binary vector of length and S (i [m] I. 1}. We will focus the maximization problem (minimization follows analogously).
max f(S) SCIn)
Σ iM(R)
II
max
REK+
IE
To reduce the problem to linear integer program, each monomial IRRR 24 can be replaced with decision variable yR and the following constraints:
max yE(0.)jict)
Σ ÍM (R)yR
(7)
REK+
S.L.
yR
JQ
AQ R. REKC
(8)
Σ VE
M1 R + DR YREKT
The first constraint guarantees that whenever monomial is activated (i.e. = Vi E R), all of its subsets are also activated. The second constraint ensures that if monomial is deactivated (i.e. li E R s.I. 0), at least one of its constituent terms (2(3)) is likewise deactivated. After
17

---

the optimization is solved, the solution can be read-off from the univariate monomials (()) These monomial terms can also be used to impose cardinality constraints on the solution, as was used in Section g.2 and Section 5.2.
18

---

B Experimental Details
B.1
Implementation Details
B.1.1
Hyper-parameters
We performed 5-fold cross-validation over the following hyper-parameters for each of the models:
Model
LASSO SPEX
L1 Reg. Param. À (100 with Amsn/ Aman 0.001)
LI Reg. Param. À (100 with Amin/ Amax 0.001)
PROXYSPEX
Max. Tree Depth [3, 5, None]
Number Trees [500, 1000, 5000]
Learning Rate [0.01, 0.1]
LI Reg. Param. À (100 with Amin/ Amaz = 0.001)
Random Forest
Max. Tree Depth [3, 5, None]
Number Trees [100, 500, 1000, 5000]
Neural Network
Hidden Layer Sizes [( + 3) G- 3- 3] Learning Rate [Constant, Adaptive]
Learning Rate Init. [0.001, 0.01, 0.1]
Number of Trees [100, 500, 1000, 5000]
B.1.2 Sentiment Analysis
20 movie reviews were used from the Large Movie Review Dataset [6 with [256, 512) words. To measure the sentiment of each movie review, utilize DistilBERT model [+7]] fine-tuned for sentiment analysis [A8]. 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.1.3 HotpotQA
We consider 50 examples from the HotpotQA[[3] dataset between [64, 128) sentences. We use a Llama-3. [UNK] token, and measure the log- per--peepextty of generating the original output. Since HotporQA is multi-document dataset, we use the following prompt format.
model with 8-bit quantization. When masking, we replace with the
Title: [titl__1}
Content: [document_1]
Title: (title m)
Content: (document m)
Query: (question). Keep your short possible.
B.1.4 DROP
We consider 50 examples from the DROP [89] dataset with E [256, 512) number of words. We use same model as HolpoiQA and mask in a similar fashion. We use the following prompt format.
Context:
(context)
Query: (question). Keep your answers short possible.
19

---

B.1.5 MS-COCO
We utilize the Microsoft Common Objects in Context (MS-COCO) dataset [22], which comprises images paired with descriptive text captions. For our experiments, we treat image patches (there are 48 patches per image) and individual words from the captions as the input features. We used the first 50 examples from the test set, which had n (image patches + words) between the range of [60, 85).
To model the relationship between images and text, we employed the CLIP-ViT-B/32 model, laiiualanguuae encoder designed to learn joint representations of visual and textual data. In our PROXYSPEX framework, when masking input features (either image patches or words), replace them with a generic placcholder token suitable for the CLIP architecture (c.g., a zeroed-out patch vector or the text [MASK] words. The value function f(S) for given subset of features S was defined as the contrastive loss among the other image/caption pairs. By measuring the change in this contrastive loss upon masking different feature subsets, can attribute importance individual features and their interactions in the context of joint image-text understanding.
B.2 Measuring Spectral Hierarchies
To quantify the hierarchical structure observed in the Fourier spectra of the LLMs under study, we introduce and analyze two key metries: the Staircase Rate (SCR) and the Strong Hierarchy Rate RSH These metrics are computed based on the set of the k largest (in magnitude) Fourier coefficients, denoted as Fk.
The Staircase Rate (SCR( k)) is defined as:
Uta) E Fx } 1=1
SCR(f,K) 1 Σ 1 3(1 Jei...... e|st) E PS)m(S) s.t. bj
SET,
where Fx denotes the & largest Fourier coefficients of f. and Perm(S) is the set of all ordered sequences of the elements in S.
(10)
The SCR measures the proportion of top-k: Fourier coefficients F(S) for which there exists an or- dering of its constituent elements (e1,... =|5)) such that all initial subsets (i.e., e1, (e),,........ itself) are also among the top-k coefficients. A high SCR indicates that significant high-order inter- actions are built up from significant lower-order interactions in step-wise or "staircase" manner.
The Strong Hierarchy Rate (SHR(f, k)) is defined as:
SHR(f,k) = To
Σ L S,S FF), SET,
where Fi denotes the k largest Fourier coefficients of f.
(11)
The SHR is a stricter measure, quantifying the proportion of top-k coefficients F(S) for which all subsets of S (not just initial subsets, in DSR) also present in Fu. A high SHR suggests very robust hierarchical structure where the significance of an interaction implies the significance of all its underlying components.
Figure M visualizes these rates alongside faithfulness (RP) for the Sentiment Analysis and MS- COCO datasets. These empirical results aim to demonstrate that LLM feature interactions exhibit significant hierarchical structure. The high SCR and SHR R scores support the core motivation for that important interactions are often built upon their lower-order subsets, structure that Gradient Boosted Trees (GBTs) are well-suited to capture and exploit.
B.3 Sparsification
The process of sparsification is crucial for enhancing the interpretability of the explanations gen- erated by PROXYSPEX By retaining only the top Fourier coefficients, we can achieve a more concise and understandable representation of the model's 's behavior without significantly compromis- ing the faithfulness of the explanation. As demonstrated Figure & a relatively small number of Fourier coefficients (approximately 200) are often sufficient to achieve faithfulness comparable to using a much larger set of coefficients for tasks like sentiment classification and image captioning (MS-COCO).
20

---

1.0
Faithfulness (Ite
Paithfulness (It*)
0.6
0.6
0.1
0.4
0.2
0.2
0.0
16
32
64
128
256
8
16
32
64
128
256
Top & Coefficients
Top I Coefficients
100%
100%
Staircaso Rate
80%
Staircase Rate
80%
60%
60%
40%
40%
20%
20%
0%
0%
16
256
Top Coefficients
Top Coefficients
100%
100%
Strong Hier. Rate
Strong Hier. Rate
80%
60%
60%
40%
40%
20%
20%
8
16
32
64
128
256
8
16
32
64
128
256
Top &e Coefficients
Top k Coefficients
(a) Sentiment
(b) MS-COCO
Figure 11: (top row) We run SPEX until R² 0.9. We report the faithfulness when we truncate the spectrum to keep just the & coefficients for range of k. We include results from Sentiment n E [256, 512], and MS-COCO n E [60, 85). In both cases faithfulness steadily increases as we increase k. (middle row) We report the SCR (ICI) for the same top k Fourier truncated functions above. In all cases, the SCR is nearly 100%. (bottom row) We also report the SHR (L.), which is the strongest of the metric consider. Here find that though SH R decreases somewhat as lo grows, it still strongly in favor the hierarchy hypothesis.
Further results in Figure D2 illustrate the relationship between relative faithfulness and Fourier spar- sity for both Sentiment and MS-COCO datasets across different inference multipliers (a). These plots show that faithfulness generally increases with k, plateauing after a certain number of coeffi- cients, reinforcing the idea that sparse representation effectively capture the essential dynamics of the LLM''s decision-making process.
B.4 Proxy Model Selection
The choice of GBTs as the proxy model within PROXYSPEX is motivated by their inherent ability to identify and learn hierarchical interactions from limited training data. This is a critical characteristic, LLM feature interactions often exhibit hierarchical structure where higher-order interactions built upon their lower-order subsets. As indicated in the main text, GBTs have been shown to vastly outperform other proxy models, including random forests, particularly because random forests less effective at learning hierarchical functions. GBT-like algorithms, on the other hand, are adept disentangling sums of these hierarchical components.
Figure provides a comparative view of proxy model performance. Figure IK and Figure L3A illustrate the faithfulness (R²) of different proxy models (LASSO, Random Forest, Neural Network.
21

---

1.0
1.0
Rel. Faithfulness
Rel Fatthfulnes
0.8
0.6
0.5
0.2
0.2
10'
10'
10P
10'
10'
10a
10
10P
10a
10
Sparsity (k)
Sparsity (4)
(a) Sentiment
(b) MS-COCO
Figure 12: We plot faithfulness (R²) as function of Fourier sparsity. Only = 200 coefficients are required achieve equivalent faithfulness.
and GBTs) on both synthetic dataset with a complete hicrarchy (defined below) and the Sentiment Analysis dataset, respectively, across various inference parameters (a). These results empirically support the superiority GBTs in capturing these complex interaction structures. However, it's also important to acknowledge limitations; for instance, GBTs may not perform well when interactions possess a different, non-hierarchical sparse structure, as empirically confirmed by simulations like the Synthetic-Peak example (which lacks hierarchical structure) shown in Figure 153
Synthetic Peak
Synthetic Complete Hierarchy
(S) (-1 shai ( F(T) where P is set of 10 uniformly sampled sets cardinality 5 and F(T) Sniform(-1,1) for T
(s = ( F(R) where H (R C T P} and F(R) Uniform (-0mmm((1111) 1) for R
B.5 Shapley Value Approximation
We repeat the experiments of Section PT under the metric of mean squared error relative those computed by KemaaSSHAP under an inference budget of 10,000. In Figure I4, we find that PROX- YSPEX uniformly outperforms KernelSHAP within this tested range. Just as with recall, with large enough KernelSHAP eventually surpasses PROXYSPEX.
B.6 Practical Implications
The practical implications of PROXYSPEX are significant, primarily revolving around its inference efficiency and the resulting speedups in generating faithful explanations for LLMs. A major chal- lenge with existing interaction attribution methods, like SPEX, is the substantial number of model inferences required, which can be computationally expensive and time-consuming for large models. PROXYSPEX addresses this by leveraging a GBT proxy model, which dramatically reduces the number of inferences needed while maintaining or even improving explanation faithfulness.
Figure presents the practical benefits in terms of wall clock time for achieving different levels of faithfulness (It²) on the Sentiment Analysis (Figure IISal) and MS-COCO (Figure (SF) datasets. These plots clearly demonstrate the speedups achieved by PROXYSPEX For example, in the senti- ment analysis task using the smaller DistilBERT model, PROXYSPEX offers speedup of approx- imately 3x, while for the larger ELIP-ViT-B/32 model with MS- MS-COCO, the speedup around 5x when compared to methods that require more extensive sampling. This increased efficiency makes PROXYSPEX a more viable tool for interpreting complex L.LMs in real-world scenarios where com- putational resources and time are often constrained.
22

---

LASSO
Random Forest
Neural Network
GBTs
0.8
Fatthfulness (I2))
Falthfulness (R()
0.6
0.4
0.4
0.2
0.2
0.0
0.0
Inference Parameter (a)
Inference Parameter (a)
(a) Synthetic Complete Hierarchy
(b) Sentiment
Paithfulness (RP)
0.5
Sample Parameter (a)
(c) Synthetic Peak
Figure 13: Comparison of proxy model faithfulness in capturing function structures. (a) Faithfulness of LASSO, Random Forest, Neural Network, and GBTs on a synthetic dataset with complete hierarchical structure, across varying inference parameters (ai). (b) Faithfulness of the same proxy models on the Sentiment Analysis dataset across varying a. (c) Faithfulness on synthetic dataset with sparse, non-hierarchical peak function, across varying illustrating a limitation of GBTs Is for non-hierarchical structures.
C Case Study Details
C.1 Data Attribution via Non-Linear Datamodels
The training masks and margin outputs were provided by [55]], corresponding to their subsampling rate of 50% (i.e., half the training images were used fit each model). See [[S]] for the hyper- parameters selected. With n 50,000 training samples, 300,000 training masks (model retrainings) were provided. This corresponds a 0.38, which underscores the inference-efficiency of PROX- YSPEX to identify strong interactions.
Utilizing these masks and margins, randomly selected 60 test images (6 from each class) for analysis with PROXYSPEX. Below, in Figure [[G and Figure II we present the strongest second- order interactions of the first thirty of these selected test images. Figure El visualizes the six test images exhibiting the most significant third-order interactions identified through this analysis.
After fitting PROXYSPEX, Since target and non-target images affect the test margin in opposite directions, we partition the interaction space into the following categories:
convert the Fourier interactions to Möbius using Appendix A.
share the same label as the held-out test image. Target-class interactions T: Interactions composed exclusively of training images that
Non-target-class interactions To; Interactions where least one training image in the set has label different from that of the held-out test image.
23

---

Sentiment Analysis
DROP
2 10
Shapley MSE
2x 10
Shapley MSE
10-3
10
6x
0.5
077
0.25
0.75
Inference Multiplier (a)
Inference Multiplier (a)
HotpotQA
MS-COCO
Shapley MSE
Shapley MSE
10
10-3
x 10-5
0.25
0.5
0.75
0.75 1.0
Inference Multiplier (a)
Inference Multiplier (a)
KernelSHAP
ProxySPEX (Ours)
Figure 14: Shapley value mean square error after a n log2 (n) inferences for multipliers a E {0.25, 0.5, 0.75, 1.0]. Across all four tasks and multipliers, within the tested range, PROX- YSPEX provides a better approximation of the values computed under 10,000 inferences. Error bands indicate the standard deviation across different runs of the algorithms.
ProxySPEX (Ours)
SPEX
Faithfulness (It))
0.80
Paithfilness (T(e
0.80
2 spoed-up
5.3x speed-up
2.7x speed-up
6.9% speed-up
0 Inference
Inference Ator. Comp.
0,770
3.7x speendup
Astr. Comp.
0.70
speed-up
25
100
125
130
100
200
300
400
Wall Clock Time (sec.)
Wall Clock Time (sOc.)
(a) Sentiment
(b) MS-COCO
Figure 15: Wall clock time demonstrating PROXYSPEX's efficiency. Comparison of wall clock time (seconds) required to achieve different levels of faithfulness (R²) for PROXYSPEX, show- ing breakdown of inference time and attribution computation time. (a) Results on the Sentiment Analysis dataset with the DistilBERT model. (b) Results on the MS-COCO dataset with the CLIP-VAT-B/32 model, highlighting speedups achieved by PROXYSPEX.
Synergistic Interactions: The top synergistic interaction R of order-r is defined as:
S argmax I (S)
SET,|S|=r
T argmin M (T)
(12)
TET%,
S* if (T*)
R"
T otherwise
Visually, as presented in Figure IG r 2, the interactions identified by this rule often involve training images that appear to work together to reinforce clarify the classification of the held-out image, frequently by contributing complementary features or attributes. important to acknowledge that this definition serves heuristic and does not perfectly isolate synergy; For

---

example, the first frog image contains redundant bird images due to strong Bigher-order interactions involving these bird images.
Redundant Interactions: The top redundant interaction R of order-r is defined as:
S" argmin (S)
SET.|S|=r
T argmax TET-,ITER
AM (T)
(13)
1 Rº
2
T
otherwise
Figure T demonstrates that this definition identifies redundant training images that are similar to the held-out image.
25

---

Airplane
Bird
Rird
Airplane
Airplane
Airplane
Airplane
Bird
Cat
Automobile
Automobile
Automobile
Automobile
Truck
Truck
Automobile
Ship
Ship
Bird
Cat
Dog
Bird
Airplane
Truck
Bird
Bird
Bird
Cat
Cat
Cat
Cat
Cat
Cat
CCtt
Bird
Dog
Dog
Dog
Dog
Dog
Dog
Dog
Bird
Bird
Dog
Frog
Bird
Bird
Frog
Frog
Frog
Frog
Frog
Frog
Horse
Horse
Horse
Horse
Dog
Dog
Horse
Dog
Dog
Ship
Automabile
Airplane
Ship
Automobile
Automobile
Ship
Ship
Ship
Figure 16: For 30 random held-out images, their corresponding top second-order synergistic inter- action (green box).
26

---

Airplane
Bird
Rird
Airplane
Airplane
Airplane
Airplane
Airplane
Airplane
Automobile
Truck
Truck
Automobile
Automobile
Automobile
Automobile
Automobile
Automobile
Bird
Cat
Cat
Bird
Cat
Truck
Bird
Bird
Bird
Cat
Cat
Cat
Cat
Cat
Cat
CCat
Horse
Dog
Dog
Dog
Dog
Cat
Dog
Horse
Dog
Frog
Frog
Frog
Frog
Bird
Bind
Frog
Frog
Frog
Horse
Horse
Horse
Horse
Dog
Dog
Horse
Dog
Dog
Ship
Ship
Ship
Ship
Automobile
Automobile
Ship
Ship
Ship
Figure 17: For 30 random held-out images, their corresponding top second-order redundant interac- tion (red box).
27

---

C.2 Model Component Attribution
We study the influence of specific model components on task performance, using a controlled abla- tion methodology. Our experiments are conducted on Llama-3, 1-8B---Bnss -B--rntt evaluated on the high-school -uwoolllussssstooyr -istorr subset of the MMLU dataset, benchmark comprising multiple-choice questions.
MMLU includes 231 questions in the high-schhoo--us-histrr subset. To perform pruning and then evaluate the ablated models, we split this data into two sets-training split Drain consisting of the first 120 questions and test split Dest with the remaining questions. We use accuracy as the evaluation metric, which is computed as the proportion of correctly answered multiple-choice questions on a given data split.
For an layer LLM, we let [L] denote the set of layers and let He denote the set of attention heads in layer & E [L]. For each experiment, focus particular group of layers L S [4] within the model and denote the corresponding set of attention heads as He = Utee He. The Llama-3. 1ew.1-8-IIntttre
model consists of I. 32 layers, each with 32 attention heads.
At each layer & of the LLM, the output the attention heads is combined into a latent representation by concatenating the outputs of the attention heads. Then, this latent vector is passed to the feed- forward network of layer To study the contribution of specific heads, we define an ablated model LLMs for any subset 5 C c.. In LLMs, the outputs of the heads in H.. \ S are set to zero before the concatenation step. After concatenation, we apply a rescaling factor to the resulting latent vector |M6
at each layer é E L. equal to the inverse of the proportion of retained heads in that layer, i.c., [SmPte] This modified latent representation is then passed to the ferwafo network as usual.
We define fc
fc(S) Accuracy of LLMg D
(14)
and interpret fc(S) a proxy for the functional contribution of head subset S to model performance, enabling quantitative analyses of attribution and interaction effects among attention heads.
Pruning, We perform pruning experiments across three different layer groups L: initial layers (C (1, (1,3,, middle layers (C = {14, 15, 16)), and final layers (C = {30,31 32)). Since each layer has 32 attention heads, we effectively perform ablation over n |Hccl = 96 features (attention heads) in total. For given group L, we begin by estimating the function fc using both LASSO and PROXYSPEX, based on evaluations of [c(S) for 5000 subsets S sampled uniformly at random. These estimates serve as surrogates for the true head importance function. We then maximize the estimated functions to identify the most important attention heads under varying sparsity constraints (target numbers of retained heads). We use the procedure detailed in Section +> to identify heads to remove for both PROXY SPEX and LASSO. We also compare against Best-of-N baseline, in which the model is pruned by selecting the subset S that achieves the highest value of fc(S) among 5000 randomly sampled subsets at the target sparsity level.
Evaluation. In order to evaluate the performance of an ablated model LLMs, we measure its accu- racy on the test set using
(C( _ Accuracy of LLMs on Drest-
(15)
In Figure IIC we report the value of gc( for the pruned models obtained by each method. We find that PROXYSPEX consistently outperforms both baselines, yielding higher test accuracy across all evaluated sparsity levels.
Inference setup. All experiments are run on a single NVIDIA H100 GPU, with batch size 50. Av- erage runtime per ablation (i.e., evaluating fz(8) once for given S) is approximately 1.7 seconds. Therefore, collecting training dataset {(S;, (S:))) with 5000 training samples takes approxi- mately 2.5 hours.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the paper are clearly stated. The results, which primarily empirical, are backed by experimental data. Relevant theoretical research is also cited.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: There is a limitations section, which specifically highlights work that remains to be done.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: We make no major theoretical claims, and any theoretical statements are accompanied by proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All code and experimental setup are provided.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
All data and code will be included in the publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpp::/nnis..o cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:)
/ hnaps.cc/publiccguiddee (oodeddee///ddubmiiiia ittpssummmssiioooooooo ssionpolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:
[Yes]
Justification: All relevant details are included.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are provided where relevant.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
31

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details on the compute used is included.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't it make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///aaaasccccoooo/occccccaaa
Answer: [Yes]
Justification: Yes.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification: Yes, this presented work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: all assets open-source.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: All code and new tools will be published and reasonably documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
34

---

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs are not non-standard component of the methods in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: htcpss///eaarrrssecc//ooooeeeees for what should or should not be described.
35


Reviews:
[{"review_id": "hr8Ej6pFCM", "reviewer": "Reviewer_kopj", "summary": "In this paper, the authors develop a method that enhances the interpretability of LLMs. In particular, they want to identify interactions responsible for the prediction in a downstream task for a given model $f$ and instance $x$. To that end, building on the SPEX framework, the authors study the value function, which is the output of the LLMs $f$ with some tokens randomly replaced by the [MASK] token and approximates this function using the Fourier Transform.\n\nAs opposed to SPEX, which frames the problem of finding the optimal Fourier coefficient as a decoding problem, ProxySpex proposes to train auxiliary gradient boosting trees on a dataset of inference values and associated masks. The intuition (backed by experimental results) is that the LLMs learns hierarchical features, i.e. features part of an interaction group are more likely to be selected as singletons as well (or being part of a sub-group). Leveraging recent results on boosting trees shows that they also capture such interaction and allow for the fast computation of the Fourier Coefficient with them. The resulting coefficients are further filtered to allow for even more sparsity.\n\nThis approximation is constructed for 4 different datasets with different downstream tasks and is compared to other approximations obtained with LASSO and the original SPEX. It is shown that the interactions recovered by Proxy Spex are more influential on the performance than its two counterparts and the approximation is more faithful.  Proxy Spex is further applied to different use cases beyond feature attribution (\"datamodelling\" as [1] and head pruning [1]) and shows promising results on these test cases.", "questions": "- Have the authors explored other mask sampling methods to allow a better evaluation of the model ? For instance, using the attention maps in the mask design directly could lead to the combination or subgroups of features? \n- I am a bit unsure of the novelty of some parts of the paper. For instance, are the definitions of redundant and synergistic interaction new?\n- The hierarchy discovered in the model seems similar to this prior training, which suggests that one needs to go through unigram, then bigram ... to discover the results [1]. It could be interesting to discuss these results in the paper.\n\n[1] Edelman, E., Tsilivis, N., Edelman, B., Malach, E., & Goel, S. (2024). The evolution of statistical induction heads: In-context learning markov chains. Advances in neural information processing systems, 37, 64273-64311.", "limitations": "The limitations of the models are correctly addressed. However, I don't think I see the error bars mentioned for the statistical significance of the results.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- **Quality and Originality** : \n\t- (+) Clear motivation : All the intuitions (hierarchical nature of the interaction of the LLM or the GBT, sparsity of the resulting approximation) used to motivate the model is experimentally investigated. \n\t- (+) Extensive experiments conducted on four diverse datasets (NLP and vision tasks) show ProxySPEX's superior faithfulness, efficiency, and interpretability compared to SPEX and LASSO.\n\t- (-)Due to the closeness with existing methods (mostly SPEX), I think a proper discussion to properly distinguish this method from the other is required. \n\t- (-) The regression-based refinement step is only briefly discussed, but might be crucial in practice for stability and accuracy. \n\t    \n- **Clarity**:  (+) The paper is very clear and the experiments are carefully described.\n    \n- **Significance**:  The method develop in this paper is very close to existing methods (SPEX) and ideas from other papers in the field (approximating the value function with Fourier transforms, leveraging GBT for Fourier Coefficients...), but the experimental results are impressive and constitute a nice advancement in the field. The extension to the two case studies on data attribution and attention head pruning demonstrates ProxySPEX's applicability beyond standard feature attribution and large potential to other applications. Different metrics and concepts (DSR, Synergetic interactions) were introduced and should help ML practitioners better understand both datasets and models.", "was_revised": true, "final_justification": "The answer from the authors addressed my concerns regarding the novelty, and I have raised my score accordingly.", "rebuttal": "Thank you for your careful review. We will discuss and clarify some of the main points below, and hope to convince you that this is not a borderline case. \n\n**Relationship between SPEX and ProxySPEX:** This was a common comment across many reviews. We will add a section carefully describing the relationship of the two approaches. \n\nNote that SPEX and ProxySPEX differ significantly. The only common factors in these two methods are that they:\n\n1. Both exploit an empirically observed structure (sparsity and low-degree) for SPEX and (sparsity, low-degree and hierarchy) for ProxySPEX.\n\n2. Both ultimately generate a Fourier transform to approximate the model.\n\nSPEX uses an algebraic structured sampling scheme, coupled with error correction decoding procedures to efficiently compute the interactions in the form of a Fourier transform. SPEX is a rather complex algorithm that involves many carefully designed components that work in concert to enable efficient estimation.  \n\nProxySPEX, in contrast, is much simpler. ProxySPEX uses random samples to learn a GBT proxy model. We then apply an efficient method for computing the Fourier transform of the GBT model to extract the most important interactions from the proxy model. \n\n**Regression:** We will extend our discussion of the use of a final regression step. Empirically, we observe that in most cases, there is a small positive effect on the final faithfulness, but is not a critical aspect of ProxySPEX.\n\n**Other sampling methods:** We would like to emphasize that ProxySPEX is meant to be a *model agnostic* approach to identifying sparse features interactions. That being said, it is certainly an interesting research direction to try to extract an even more powerful prior beyond sparsity and hierarchy by looking at internal components (that are computed anyways) during the process of inference. During the process of developing ProxySPEX, we did study correlations between our extracted interactions and the one suggested by attention heads, but more work would be required to have a complete and operationally useful understanding of this relationship. \n\n**Definitions of Synergy and Redundancy:** Creating definitions of redundancy and synergy in interactions for classification was a problem we faced when developing this work. As far as we are aware, there do not exist standard definitions for these, as it is typically considered computationally intractable to compute even pairwise interactions between training data. Our definitions come from the notion of *Harsanyi dividends* in game theory, and how they relate to subadditive and superadditive game structures [1]. Importantly, Harsanyi dividends are equivalent to the Mobius coefficients, which we can compute due to efficient transformations between the Fourier and the Mobius transform. In the camera ready version, we will more prominently discuss these definitions. \n\n**Edelman et al.** This paper has some fascinating observations. It seems likely that the models trained in Edelman et al. would exhibit a hierarchical interaction structure, just like the larger, production-size models we considered in this paper. We would certainly discuss this connection in the final revision of our manuscript. \n\n[1] Dehez, P. (2017). On Harsanyi dividends and asymmetric values. International Game Theory Review, 19(03), 1750012."}, {"review_id": "GQYsYmbFgy", "reviewer": "Reviewer_EPSB", "summary": "The paper focuses on the problem of \"local approximation based explanations\" which attempt to identify the features that were important for a particular prediction by approximating the model with a simpler/explainable function across some neighborhood.  Importantly, the paper considers interaction effects between these features.  Additionally, the paper shows that the same approach can be used for data attribution and model component attribution.\n\n\nThe paper proposes a method, ProxySPEX, which builds on an existing method, SPEX, based on two observations:\n-  In addition to being sparse, the Fourier spectra of the interactions between features in LLMs is hierarchical \n-  GBTs are very effective for learning this type of hierarchical structure\n\nProxySPEX then works by:\n1.  Evaluating the model on a random sample of masked inputs\n2.  Fitting the GBT to that data\n3.  Efficiently computing the Fourier representation of the GBT using an existing method\n4.  Refining those Fourier coefficients\n\nThe paper shows that this process produces more faithful explanations than SPEX and LASSO regression across a variety of datasets and number of masked samples used in Step 1.\n\nThen the paper shows that different definitions of the value function can be used to enable ProxySPEX to be used for data attribution (identifying which training points where important to have for the model's prediction at this point and which were redundant) and model component attribution (identifying which attention heads can be pruned).", "questions": "Could the authors elaborate on Step 4?  I'm still not clear on exactly how this works.\n\nWhile reading the paper, I was confused about what the \"local neighborhood\" ProxySPEX was approximating the model over.  I eventually realized that this was \"the set of all randomly masked inputs\".  But it would be nice if this was made clearer earlier.\n\nIt'd be great if the authors commented on why SHAP isn't expected to perform well in this setting.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n-  Quality:  The paper supports its claims with well designed and extensive experiments\n-  Clarity:  Most of the paper is clearly written.  The next section has some questions/suggestions regarding this.\n-  Significance:  The problem studied is an important one and the proposed method is a clear improvement along multiple axes (computational efficiency and efficacy).\n-  Originality:  I'm not deeply familiar with the related work, but the two observations that justify ProxySPEX were interesting to read and think about.\n\nWeaknesses:  Clarity on SHAP vs LIME (and other related methods)\n-  It is very common for papers to treat SHAP (and related methods) and LIME (and related methods) as interchangeable because they are both \"local explanations that assign 'importance' to features\".\n-  However, they are better thought of as separate types of explanations.  SHAP is an example of a \"local feature attribution\" explanation, which identifies \"important\" features (usually by measuring how the model's predictions change when a feature is \"removed\").  LIME (and ProxySPEX) are \"local approximation based\" explanations which explicitly try to approximate the model across some \"neighborhood\".\n-  The fact that the \"neighborhood\" in this paper is the \"the set of all randomly masked inputs\" blurs the line between these types of explanations, but the evaluation metric (faithfulness) is clearly measuring approximation accuracy accuracy across it.  Given that, it is entirely expected for SHAP (or anything other local feature attribution explanation) to perform poorly on it (they are optimized for something else).  Especially when compared to methods that explicitly optimize for it.\n-  This detail hardly matters for this paper.  But it would be nice if papers treated these method categories with more care because it would go a long way towards reducing the confusion about when and why one method works better than another (and also towards reducing the amount of non-sensical comparisons run or requested by reviewers).", "was_revised": true, "final_justification": "The authors' responses addressed my concerns.  \n\nLooking at the other reviews, I think the main concern is with the novelty of ProxySPEX.  While many of the \"pieces\" required to build ProxySPEX already existed, I think there is value in putting them together.  Especially when the results are good.  As a result, I don't think that the concerns over novelty are sufficient to reject the paper.\n\nOverall, I still recommend that the paper is accepted.", "rebuttal": "Dear reviewer, thank you for your comments and review. We appreciate your effort and insightful follow-up questions. \n\n**Weakness Section:** This is a good point, and is certainly worthy of a more nuanced follow-up discussion in the camera ready version. We should expect Shapley Values, which are not optimized for faithfulness, to perform poorly in this task, which is observed in Appendix B.5.1 of [1]. \n\nThe structure of the Shapley Kernel is more suited to the feature identification experiments in Section 4.2 of this paper (where we try to identify the top $r$ features). Here too, however, we find that Shapely values perform comparably to LASSO/LIME which we significantly outperform. Similar results are observed in Section 6.3 of [1]. Interestingly we also find that using the learned Fourier transform of ProxySPEX to estimate the Shapley Values often generates a better estimate (in terms of MSE, correlation, etc.) of the Shapley Values than standard approaches such as KernelSHAP.\n\n**Regression:**  We will extend our discussion of the use of a final regression step. Empirically, we observe that in most cases, there is a small positive effect on the final faithfulness, typically most impactful in very high-noise settings. \n\n**Follow-up discussion:**\n\n*Some discussion of \"approximation\" vs. \"importance\"*:\nLIME is typically viewed as an \"approximation\" while Shapley Values are not. It should be noted though, the distinction between \"approximation\" and \"importance\" is somewhat arbitrary. Ultimately, most attribution scores can be defined as the solution to an approximation problem with a suitably defined distance metric (loss) and optionally some regularization. For SPEX and ProxySPEX, (and often LIME) that is the $\\ell_2$ distance metric, while for the Shapley Value that distance metric is the Shapley Kernel (this is the essence of Theorem 2 in Lundberg et al. 2017).\n\nThe real distinction seems to be that local \"approximation\" based approaches are typically evaluated in terms of their approximation loss, while Shapley Values, are typically not. In the camera ready version, we will add some discussion of this, and highlight our definition of \"distance\", which is, as you described, the set of all randomly masked inputs. \n\nInterestingly, and complementary to the above discussion, one can  use the ProxySPEX approximation to compute Shapley values using the closed-form conversion in Appendix A.1. Evidence suggests that this is efficient strategy. Using the *Sentiment* dataset and model, we first approximated the Shapley values by running KernelSHAP (Lundberg et al. 2017) under 100,000 model inferences, treating these as the ground truth value. We then compared the approximation quality of the Shapley values computed via KernelSHAP and ProxySPEX under just 100 and 1,000 model inferences, measuring the mean-squared error, spearman rank correlation, and the recall of the top 10 Shapley values. Results are averaged over the 20 movie reviews in the dataset.\n\n|            |  MSE (100) ↓ | MSE (1000) ↓ | Spear. Corr. (100) ↑ | Spear. Corr. (1000) ↑ | Recall@10 (100) ↑ | Recall@10 (1000) ↑ |\n|:----------:|:----------:|:----------:|:------------------:|:-------------------:|:---------------:|:----------------:|\n|  ProxySPEX | **0.0015** | **0.0004** |     **0.2197**     |      **0.6168**     |    **0.300**    |     **0.725**    |\n| KernelSHAP |   0.0728   |   0.0071   |       0.0947       |        0.3167       |      0.085      |       0.400      |\n\nThe approximation quality is better under all three metrics in this regime. A more thorough comparison with other approximation algorithms is  needed, but it seems that leveraging Fourier structural properties (sparsity, hierarchy and low-degree structures) is valuable, not just in an \"approximation\" sense, but also in determining Shapley Value-like notions of \"importance\" when model evaluation is very costly. \n\n[1] Kang, J. S., Butler, L., Agarwal, A., Erginbas, Y. E., Pedarsani, R., Yu, B., Ramchandran, K. SPEX: Scaling Feature Interaction Explanations for LLMs. In Forty-second International Conference on Machine Learning."}, {"review_id": "CNHbwe761B", "reviewer": "Reviewer_6aRb", "summary": "This paper introduces a method for identifying important feature interactions. Given a function $f$ and input instance $x$, the method works by sampling a number of masks; evaluating $f$ on the masked instances of $x$; fitting a gradient boosted tree (GBT) to the dataset of mask/function output pairs; and extracting the Fourier representation of the GBTs. The empirical evaluation shows that the method outperforms a marginal feature attribution method, and outperforms another interaction attribution method using fewer function evaluations.", "questions": "- For # features removed (in figure 7): for ProxySPEX, is a feature a single word, or an interaction (a set of words)? \n- Would it be possible to compare to one of the other interaction baselines on a dataset with fewer features?\n- In sec. 5.1, would it be possible to give a more formal definition of redundant interactions and synergistic interactions? How are these identified?\n- What is the relative faithfulness metric in figure 5? Is this relative to the GBT or to the underlying model?\n- I did not find Figure 2 to be very helpful. Would it be possible to add more concrete example---for example, illustrating hierarchical features in an actual task?\n- In line 164: \"With $T$ trees of depth $d$ there are at most $O(T4^d)$ non-zero Fourier coefficients\" Where does $O(T4^d)$ come from? For the decision trees in this paper, is $d = n$ (the number of features)?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths*\n\n- It is valuable to identify feature interactions, but computationally difficult. This method seems to offer an effective way to identify important interactions at lower cost (especially compared to the main prior work (SPEX).\n- The method is evaluated on a variety of different settings. These include different feature granularities (words vs. sentenences), different modalities (text vs. images), and also two very different case studies (data attribution and model attribution). These evaluations indicate that the method has potential broad applicability.\n\n\n\n*Weaknesses*\n\n- Clarity: I found it difficult to understand the main methodological contributions from reading the paper. In particular, it was difficult to understand the difference in methodology between ProxySPEX and the main prior work (SPEX). The paper offers an extended discussion of the hierarchical nature of features in LLMs, but it was not so clear to me why GBTs leverage this hiearchy, and how this reduces the number of necessary function evaluations compared to prior work. I think the paper would be stronger if it gave a clearer description of the method, especially the differences between ProxySPEX and SPEX.\n- The evaluations do not include comparison with other methods for identifying important interactions, with the exception of SPEX. The paper states that existing methods are too inefficient to be applied to the problem considered in the experiments, but I think it would be helpful to see comparisons on smaller size problem.\n- Similarly, I had some difficulty understanding the empirical comparison between SPEX and ProxySPEX. Is the difference in performance due to the fact that SPEX requires more masks to perform well? How would the methods differ if you could enumerate all masks (e.g. on a toy problem)? Would ProxySPEX perform worse (given the GBT approximation)? Without a clearer description of the method, it is difficult to understand how exactly ProxySPEX improves over SPEX, and where it might be more limited.\n\n*Overall:* This paper seems to offer a useful method that is substantially more efficient than methods from prior work, but clarity issues make it difficult to fully understand the method and the contribution relative to existing methods. I am open to increasing my score if the authors can address my comments above.", "was_revised": true, "final_justification": "This paper makes a clear methodological contribution by proposing a new method for finding feature interactions that empirically out-performs existing work, and scales more efficiently. In my original review, I listed a few main weaknesses. The authors have addressed these in the rebuttal.\n\n1. Clarity about the method / relationship between SPEX and ProxySPEX. The authors have explained the differences in the rebuttal and plan to incorporate this clarification into the next version of the paper.\n\n2. Empirical comparison to other methods. The authors have conducted additional evaluations comparing ProxySPEX to other methods for finding feature interactions.\n\nSince the authors have addressed my main concerns, I am increasing my score to recommend that the paper is accepted.", "rebuttal": "Thank you for your review. We clarify some of the main points below, and hope to convince you that this work meets the criteria for acceptance.\n\n**Relationship between SPEX and ProxySPEX:** This was a common comment across many reviews. We will add a section carefully describing the relationship of the two approaches. \n\nNote that SPEX and ProxySPEX differ significantly. The only common factors in these two methods are that they:\n\n1. Both exploit an empirically observed structure (sparsity and low-degree) for SPEX and (sparsity, low-degree and hierarchy) for ProxySPEX.\n\n2. Both ultimately generate a Fourier transform to approximate the model.\n\nSPEX uses an algebraic structured sampling scheme, coupled with error correction decoding procedures to efficiently compute the interactions in the form of a Fourier transform. SPEX is a rather complex algorithm that involves many carefully designed components that work in concert to enable efficient estimation.  \n\nProxySPEX, in contrast, is much simpler. ProxySPEX uses random samples to learn a GBT proxy model. We then apply an efficient method for computing the fourier transform of the GBT model to extract the most important interactions from the proxy model. \n\n**Comparison to other interaction methods:** We stress that we believe the main advantage of ProxySPEX to be the scale at which it is able to operate. Due to this, we have primarily focus on comparing against other approaches that achieve scale, i.e., SPEX. As you suggested, we have conducted experiments that show that ProxySPEX also outperforms other approaches, even at smaller scales.\n\nBelow, we repeat the faithfulness experiments for *Sentiment*, with 20 new movie reviews with $n\\in [16,32]$ words and $n\\in [64,128]$ words. As in Section 4.1, we vary the number of inferences by $\\alpha \\cdot n \\log_2(n)$ and compute the faithfulness. In addition to SPEX and LASSO, we consider Faith-Banzhaf Interaction Indices [1] of up to $k$th order, which were shown in SPEX to achieve the best faithfulness among interaction attribution algorithms. Because this method enumerates all possible interactions of up to order $k$ (totaling $\\approx n^k$ interactions), it becomes computationally intractable to consider >3rd order methods for the first experiment, and >2nd order methods for the second.\n\n> *Sentiment* for $n\\in [16,32]$\n|           | $\\alpha=2$ | $\\alpha=4$ | $\\alpha=6$ | $\\alpha=8$ |\n|:---------:|:----------:|:----------:|:----------:|:----------:|\n| ProxySPEX |  **0.873** |  **0.919** |  **0.936** |  **0.946** |\n|    SPEX   |    0.510   |    0.621   |    0.750   |    0.801   |\n|   LASSO   |    0.727   |    0.744   |    0.746   |    0.749   |\n|  FBII 2nd |    0.846   |    0.891   |    0.905   |    0.911   |\n|  FBII 3rd |    0.836   |    0.898   |    0.920   |    0.932   |\n\n\n> *Sentiment* for $n\\in [64,128]$\n|           | $\\alpha=2$ | $\\alpha=4$ | $\\alpha=6$ | $\\alpha=8$ |\n|:---------:|:----------:|:----------:|:----------:|:----------:|\n| ProxySPEX |  **0.805** |  **0.847** |  **0.868** |  **0.882** |\n|    SPEX   |    0.385   |    0.580   |    0.691   |    0.695   |\n|   LASSO   |    0.632   |    0.643   |    0.646   |    0.649   |\n|  FBII 2nd |    0.774   |    0.804   |    0.815   |    0.821   |\n\n\n**Hierarchical Nature of GBTs:**\nGBTs capture hierarchy in the feature space inherently through their structure. Each tree in the ensemble is, by its nature, a hierarchical model.\n\nIndividual Trees: The first split in a tree, at the root, is on the feature that provides the most information gain  across the entire dataset. This is the most dominant feature in the hierarchy. As you move down the tree, further splits are made on other features within the subsets of data created by the previous split. For example, a split on feature B might only occur for data points where feature A was greater than a certain value.\n\nBoosting: The boosting process in GBTs refines this hierarchical modeling.\nEach new tree is trained to correct the errors of the existing ensemble. This means that later trees focus on capturing patterns and relationships that the earlier trees missed. If a complex hierarchical interaction between features was not fully modeled by the first few trees, subsequent trees will specifically target and model that remaining part of the relationship, further refining the hierarchy.\nFor instance, an initial tree might capture the main effect of age. A later tree might then model a more subtle interaction, like how income has a different effect specifically for younger age groups, a hierarchical relationship that was a source of error for the earlier, simpler model.\n\n**Empirical Difference Between SPEX and ProxySPEX - number of masks** \nThe primary empirical difference between SPEX and ProxySPEX is an order of magnitude decrease in the number of inference required to achieve the same faithfulness (see Figure 1). For large models (and LLMs in particular), due to the latency of inference, this results in a significant speed-up in wall clock time for computing interactions at scale.\nWe would like to refer the reviewer to Figure 13 in appendix B.5 (The purple lines are for SPEX, and teal for ProxySPEX, the legend was ommitted in error, which will be corrected in the camera ready version). Here, SPEX requires much more time collecting data by performing inference as compared to ProxySPEX to achieve the same faithfulness. This is a result of ProxySPEX's ability to exploit hierarchical information to more efficiently identify interactions. SPEX, on the other hand does not directly exploit any relationship between interactions, only that the interactions themselves are sparse and low-degree. \n\n**Toy Problem - Mask Enumeration** The toy problem of mask enumeration is not an interesting one for comparing SPEX and ProxySPEX, since the most interesting mechanism is their ability to exploit structure to reduce the number of required masks. SPEX directly learns a Fourier transform, which is a universal approximator (since the transform is 1-to-1). In the case where it has full information about $f$ (access to all the masks), it has zero error. Similarly, in the ensemble limit and given sufficient depth, GBTs are universal approximators, and thus also achieve perfect reconstruction. Practically though, for some fixed ensemble size, there will be some non-zero approximation error, and SPEX would slightly outperform ProxySPEX in this setting. \n\n## Questions:\n\n**Figure 7:** Here we are removing individual \"features\", which can be words or sentences, depending on the dataset. See the \"datasets and models\" part of section 4 for details on a per-dataset basis.\n\n**Section 5.1:** In the camera-ready version, we will discuss this in more detail. For your reference, precise definitions given in Appendix C.1. See rebuttal of review kopj for more details. \n\n**Figure 2:** With the additional page, we will improve this figure with a simple example from sentiment analysis in the camera-ready version.\n\n**Relative Faithfulness:** The relative faithfulness is relative to the ``full'' GBT model. That is, we are plotting how faithful the sparsified model is compared to the full GBT model. Our results show that sparsification does not hurt faithfulness while improving interpretability. The plots look similar when plotting absolute faithfulness (relative to the underlying function), but simply saturate at some fixed level (~90\\%).  We will clarify this in the camera-ready version. \n\n**Line 164:** This result is provided in Gorji et al. [5] (top of page 6), for which we will provide a citation for this statement in the camera-ready version. This result comes from the fact that each leaf of a decision tree has at most $2^d$ non-zero Fourier coefficients. With each tree having at most $2^d$ leaves, and by linearity of tree ensembles and the Fourier transform over $T$ trees, there are at most $T\\cdot 2^d \\cdot 2^d = T4^d$ non-zero Fourier coefficients.\nFor the decision trees in this paper, the depth is typically set to d=3 or d=5, selected through cross-validation. This is much fewer than $n$ number of features. \n\n[1] Tsai, C. P., Yeh, C. K., \\& Ravikumar, P. (2023). Faith-shap: The faithful shapley interaction index. Journal of Machine Learning Research, 24(94), 1-42."}, {"review_id": "XcVIj3xySY", "reviewer": "Reviewer_ikfA", "summary": "This work proposes ProxySPEX, a method for quantifying arbitrary-order interactions for many features. Specifically, the authors develop a method to represent and estimate *value functions* accurately, efficiently and sparsely. The approach stems from the empirical finding that interactions are often hierarchical (in the models considered), and thus may be well captured by gradient boosted trees. For a given input of interest, gradient boosted trees are trained to predict the value function (i.e. on different masked subsets of the input), after which a sparse set of Fourier coefficients are extracted. This approach to estimating and using the value functions is significantly more tractable than SPEX (a prior work also making use of the Fourier transform of the value function) achieving higher faithfulness with fewer inferences, and is shown to be superior to LASSO. The approach is shown to be effective for a number of model families and datasets, as well as in two case-studies.", "questions": "* It is reasonable to me that the Fourier coefficient $F(T)$ could be interpreted as the strength of the interaction in set $T$. However, as someone who does not have experience with Fourier Transforms on functions of the hypercube, it is not immediately clear to me why this is the case. It would be helpful to provide more detail as to why. As is, the paper states that $F(T)$ is the importance, and that “Eq. 1 represents an orthonormal transform onto a parity (XOR) basis”. Is this latter reason the explanation? If so, it could be expanded a bit.\n* Complementary to the question above, is there a straightforward interpretation of the literal equation you provide for $F(T)$ as importance, i.e., aside from its interpretation as a Fourier coefficient? Maybe some sort of decomposition of the sum? It looks like $T$ benefits from having even intersections with $S$ that have large $f(S)$ and, when the intersection of $T$ and $S$ is odd, for $f(S)$ to be small, but this alone is not very intuitive to me as a measure of importance.\n\nIncluding responses to one or both of the above questions in Section 3.1 would be valuable for improving the interpretability of the paper.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths** \n* The problem of identifying higher order feature interactions is both important and notoriously hard in high dimensions. Attempts to make this tractable for massive models, as in this work, are valuable.\n* Section 3.2 and Figure 3 provide strong evidence that the models you consider indeed contain hierarchical interactions. Aside from providing motivation for your method, I believe that this is a potentially valuable finding for the community in general.\n* The optimization described in Eq 4. Is a natural and efficient use of your $\\hat{f}$ for finding influential groups of features. \n* Your experiments clearly show ProxySPEX’s ability to achieve higher faithfulness with fewer inferences compared to SPEX and LASSO. Further, the experiments are thorough and wide-ranging covering multiple model families and datasets in the faithfulness and feature identification experiments, in addition to two case studies. \n\n**Weaknesses**\n* The method ProxySPEX is built upon, SPEX, is not made clear in this work. For example, I don’t think that the acronym SPEX is ever articulated. Aside from both using the Fourier transform it would be helpful to make the exact relationship between SPEX and ProxySPEX clear. From the naming and presentation of the work, my impression is that the major difference is the use of Gradient Boosted Trees, but more details would be helpful. I believe this can be achieved with some light modifications to the “Preliminary” section.\n\n*Minor*\n* There are 2 related works that I think the paper would benefit from including. In [1] the authors develop a pair-wise interaction quantification method which tractably extends to higher-order interactions, partially guided by the intuition that such interactions beget interactions of lower-order subsets, in their models. In [2] the authors create a method for extending a wide range of interpretability methods to directly quantify feature interactions – with an experimental focus on Shapley values and second-order interactions.\n* (line 121) I believe $f$ should be $\\hat{f}$. \n* Eq 3. RHS: I believe this condition should be slightly rephrased as you are not summing over the coefficients but the sets which have the largest coefficients. Maybe something like “where $\\mathcal{F}_k$ denotes the set of sets with the $k$ largest Fourier coefficients in $f$.” ?\n\n[1] Tsang et al. How does this interaction affect me? interpretable attribution for feature interactions. Advances in Neural Information Processing Systems, 2020.\n\n[2] Masoomi et al. Explanations of black-box models based on directional feature interactions. In International Conference on Learning Representations, 2021.", "was_revised": true, "final_justification": "I maintain my positive rating of accept. This work addresses an important and challenging problem: tractably estimating interactions in high dimensions. The authors provide solid evidence that the hierarchical interactions motivating their approach can be found in the models they consider, a straightforward optimization (Eq 4) for using ProxySPEX to find influential feature groups, and a broad range of experimental results validating the efficacy of their method. The authors plan to fix the minor typos I have found as well as add citations and discussions for the relevant related works that I noted. The authors also provide a reasonable explanation of how the Fourier transform captures interaction importance. Finally, they address my issue regarding the difference between SPEX and ProxySPEX in their response to another reviewer, and I find that ProxySPEX still contains sufficient novelty.", "rebuttal": "1. Thank you for your careful review as well as pointing out the relevant references [1] and [2]. Both should have been considered and we will add a discussion of both methods to the camera ready version. \n\n2. Thanks, we will change $f$ to $\\hat{f}$.\n\n3.  We will replace this with the  more precise and correct statement. \"where $\\mathcal{F}_k$ denotes the set corresponding to the $k$ largest Fourier coefficients of $f$\".\n\nOther Questions: Fourier transforms as interaction importance scores: One way to think about why a Fourier coefficient corresponds to an importance is to think of the Fourier transform $F$ as a decomposition of the function. For any given set $T$, $F(T) = 0$ implies that the function does not depend jointly on the effect of the features in $T$. On the other hand, the existence of a non-linear effect between features in $T$ (for example, a synergistic effect), implies a non-zero Fourier coefficient. The Fourier coefficients (scaled by a factor of $-2$) also precisely correspond to the Banzhaf Interaction Index from game theory [a], and thus inherits all interpretations.\n\n[a] Marichal, Jean-Luc, and Pierre Mathonet. \"Weighted Banzhaf power and interaction indexes through weighted approximations of games.\" European journal of operational research 211.2 (2011): 352-358."}]

Author rebuttal:

Meta-review: This paper proposes ProxySPEX, an inference-efficient approach for recovering influential higher-order feature interactions around a test input by fitting a gradient-boosted tree proxy on masked inputs and then extracting a sparse Fourier representation from the proxy. The key empirical premise is that local interaction spectra in the studied models are not only sparse and low-degree but also hierarchical, in the sense that strong higher-order interactions tend to co-occur with their subsets. Across sentiment classification with DistilBERT, question answering with Llama-3/3.1, and CLIP image-text matching, the method achieves higher faithfulness than LASSO and approaches or exceeds SPEX with roughly an order of magnitude fewer model queries. The paper also presents case studies on data attribution and attention-head interactions that show the surrogate can support downstream interventions such as feature removal and head pruning.

The strongest aspects are the clear computational win relative to prior interaction attribution at comparable faithfulness, the breadth of evaluation across modalities and value functions, and a concrete pipeline that produces compact, interpretable spectra that can be reused for analysis beyond attribution. The empirical characterization of hierarchical interactions is useful in its own right and helps justify the proxy choice. Reviewers found the experiments well designed overall, and the added results during rebuttal strengthened the case for practicality.

The main weaknesses raised during review were about novelty relative to SPEX, clarity of the relationship between the two methods, and the scope of comparisons. Several reviewers also asked for clearer exposition of the masking neighborhood and the regression refinement step, and for stronger context on why SHAP-style methods are not competitive under the paper’s faithfulness metric. My own reading also flags an external-validity question as the approach leans on the hierarchy prior, and performance as this prior weakens is not fully mapped. Finally, the paper emphasizes reduced inference counts however lacks a fully budgeted comparison that includes proxy fitting time.

The rebuttal and discussion were productive. Reviewer kopj initially questioned novelty and asked about the regression step and the authors provided a precise delineation of ProxySPEX versus SPEX and committed to adding a comparative section to the paper. They also clarified that regression yields small but consistent gains without being critical. Reviewer EPSB asked for a clearer statement of the neighborhood and why SHAP should not be expected to perform well under the chosen metric and the authors addressed both points and also showed that ProxySPEX’s Fourier surrogate can efficiently approximate Shapley values. Reviewer 6aRb’s initial concerns centered on method clarity and comparisons to which the authors supplied additional small-scale experiments against interaction baselines and a more explicit account of how GBTs leverage hierarchy and why this reduces query counts relative to SPEX. Finally, reviewer ikfA requested clearer connections to related work on interactions and minor notation fixes and the authors agreed to incorporate the citations. They also clarified the interpretation of Fourier coefficients as interaction strengths. After rebuttal, there is consensus amongst the reviwers (and myself) for clear acceptance of the paper as the earlier concerns about clarity and novelty have been addressed to satisfaction.
Decision: Accept (spotlight)