Proxy-Based Approximation of Shapley and Banzhaf Interactions

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Proxy-Based Approximation of Shapley and Banzhaf Interactions

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neuralnetworks

machine learning, deep learning, neural networks

Proxy-Based Approximation of Shapley and Banzhaf Interactions

Santo M. A. R. Thies 1,2,3 Hubert Baniecki 4,5 R. Teal Witter 6 Eyke Hüllermeier 1,2,3 Maximilian Muschalik 1,2,† Fabian Fumagalli 1,2,7,†

arXiv:2605.22738v1 [cs.LG] 21 May 2026

LMU Munich 2 MCML 3 DFKI 4 Centre for Credible AI, Warsaw University of Technology 5 University of Warsaw 6 Claremont McKenna College 7 Bielefeld University

Abstract Shapley and Banzhaf interactions capture the complex dynamics inherent in modern machine learning applications. However, current estimators for these higher-order interactions trade off between speed and accuracy. To overcome this limitation, we introduce ProxySHAP. ProxySHAP reconciles the high sample efficiency of treebased proxy models with a principled path to consistency via residual correction. On a theoretical level, we derive a polynomial-time generalization of interventional TreeSHAP to compute exact interaction indices for tree ensembles, successfully bypassing exponential tree-depth dependencies in prior methods. Furthermore, we formally analyze the residual adjustment strategy, characterizing the specific conditions under which Maximum Sample Reuse (MSR) corrects proxy bias without its variance scaling exponentially with interaction size. Extensive benchmarking demonstrates that ProxySHAP sets a new state-of-the-art standard for approximation quality, including in large-scale applications with thousands of features. By achieving the lowest error in both small- and large-budget regimes, ProxySHAP significantly outperforms the prior best estimators ProxySPEX and KernelSHAP-IQ, while also delivering superior performance on downstream explainability tasks.

Introduction

With the growing integration of artificial intelligence into critical decision-making processes across healthcare and finance, the demand for transparency and trustworthiness has never been higher. To interpret the often opaque dynamics of these models, the field has coalesced around cooperative game theory as the de facto standard [36, 41, 42, 49]. Specifically, Shapley values [53] and Banzhaf values [3], fundamental instances of cardinal-probabilistic values, provide a rigorous axiomatic framework for attribution. These concepts are ubiquitous in modern machine learning, serving as the cornerstone for tasks such as feature attribution [36, 55] and data valuation [25, 49]. Formally, we consider a set N = {1, . . . , n} consisting of n entities, such as input features or training data points. The theoretical foundation of these explanations rests on a value function, ν : 2N → R, which assigns a scalar score to any subset (or coalition) S ⊆ N . The interpretation of ν depends on the application: in feature attribution, ν(S) typically represents the model’s prediction when features in N \ S are masked or marginalized out; in data valuation, ν(S) corresponds to the utility, such as test accuracy or negative loss, of a model trained exclusively on the subset of data points S. To summarize the complicated dynamics of the value function, cardinal-probabilistic values quantify the marginal effect of each entity i on the model’s output. Formally, the attribution to i is a weighted † Equal supervision.

Preprint.

Token interactions at low-budget regimes

(Banzhaf interactions)

FIxLIP+Baseline

Token attribution (Shapley values)

similar

giraffe

unsimilar

Why?

X₃ ₃X X₃ X₇ ν ν ₇X X₇ ν ν ν ν

X₃,₇

Linear Model with Interactions

XGBoost, LightGBM, ...

proxy.ﬁt(X, y)

a giraffe drinking water from a river

giraffe

0.7 9.2 4.2 2.7 5.6

Extract Interactions from Proxy

a giraffe drinking water from a river

Input text

1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0bina0ry-e0ncod 0 edx1 atri 1coal1itio1n m0 1

drinking

FIxLIP+ProxySHAP

Phase 2

SigLIP-2 (ViT-B) Probability: 0.69

Fit Regression Proxy Model on X and y

Sample Game Evaluations

Phase 1

Input image

X₃ ₃X X₃ X₇ ν ν ₇X X₇ ν ν ν ν

apply TreeSHAP extension

proxy.predict(X) situational

Adjust Interactions

X₃,₇

read coefﬁciencs from model

1 0 1 0 1

0 0 1 0 1 1 1 0 0 0 0 0 coalitions 1 1 0

1 0 0 1 1

0.6 9.3 4.0 2.8 5.7

0.7 9.2 apply MSR 4.2 2.7 estimator 5.6

drinking

Figure 1: Left: A ProxySHAP explanation of the SigLIP-2 model using only 2048 model calls. Right: In Phase 1, we fit a regression proxy model using sampled binary coalitions and game values. In Phase 2, we extract proxy interactions and, when appropriate, adjust them using residual estimates. sum of its marginal contributions across all possible subsets: X ϕpi (ν) := pt (n)∆i ν(T ),

(1)

T ⊆N \{i}

where ∆i ν(T ) := ν(T ∪ {i}) − ν(T ) denotes the discrete derivative of ν at coalition T with respect 1 to i, and t := |T | is the cardinality of T . Setting the weights to pt (n) = n n−1 yields the Shapley ( t ) 1 value, while pt (n) = 2n−1 yields the Banzhaf value. More generally, with the constraint that the non-negative weights sum to one, ϕpi (ν) can be interpreted as the expected marginal contribution of entity i under a specific distribution over coalition sizes. While probabilistic values are useful for understanding individual contributions, they are inherently limited to singleton effects and often fail to capture the rich, higher-order dependencies between elements. For instance, in vision-language similarity models such as SigLIP-2 [59], interactions between image and text patches are not captured by probabilistic values [2], as illustrated in Figure 1. To capture these complex dynamics, recent research has shifted toward richer explanations grounded in higher-order terms. These concepts have seen rapid adoption for quantifying feature interactions [15, 43, 58], cross-modal interactions in vision-language models [2, 26], data valuation [4], language modelling [52, 54], and even hyperparameter optimization [62]. Cardinal-probabilistic interaction indices naturally generalize probabilistic values to arbitrary subsets [14]. Rather than isolating the marginal contribution of a singleton, they quantify the contribution of a subset S ⊆ N as it is added to a coalition T : X ϕpS (ν) := pst (n)∆S ν(T ), (2) T ⊆N \S

where ∆S ν(T ) denotes the discrete derivative of ν at T with respect to the subset S. Analogous to the singleton case, specific weight choices allow us to recover the Shapley interaction index [19] and the Banzhaf interaction index [19]. For s = 1, the interaction weights reduce to pt (n). 1.1

Estimating Cardinal-Probabilistic Interactions

Computing probabilistic values and interactions is computationally prohibitive for large n, as it requires evaluating the value function ν(T ) across all 2n subsets. Consequently, researchers rely on algorithms that produce estimates using a fixed evaluation budget. For probabilistic values, there are numerous estimators such as Monte Carlo sampling [56], maximum sample reuse (MSR) [60], permutation sampling [6], and regression-based approaches like KernelSHAP [9, 36, 45]. While historically sparse, recent work on estimating probabilistic interactions is expanding to explain the complex, higher-order dependencies inherent in modern machine learning. Yet, current estimators are generally either fast or accurate, but not both. SHAP-IQ [15] generalizes MSR to interactions, being efficiently computable, but notoriously inaccurate: its variance scales quadratically with the value function’s magnitude, which we find compounds further for higher-order interactions. 2

Conversely, regression approaches like KernelSHAP-IQ [16] are accurate but require impractical sample budgets to adequately fit the large number of higher-order terms. Additionally, KernelSHAPIQ remains computationally expensive, suffering a quadratic time complexity dependence on n. To circumvent these bottlenecks, recent work leverages surrogate models ν̂ to approximate ν [4, 63]. ProxySPEX [4] extracts Fourier coefficients from a tree surrogate, which scales exponentially with depth, necessitating aggressive, accuracy-compromising truncation. Additionally, even with the exact Fourier coefficients, ProxySPEX would return the interaction of ν̂ rather than the underlying function ν. RegressionMSR [63] elegantly resolves this by directly extracting the values from the tree and employing MSR to estimate the residual values of ν − ν̂. Despite its state-of-the-art performance for probabilistic values, RegressionMSR is restricted to singleton effects. Extending this residual-correction framework to higher-order interactions requires efficient interaction extraction from tree proxies. While an algorithm for extracting Shapley interaction indices (a particular cardinalprobabilistic interaction) exists [65], it is ill-suited for general cardinal-probabilistic interactions (e.g., those used for vision tasks as shown in Figure 1). 1.2

Our Contributions

Currently, estimators of higher-order interactions trade off between speed and accuracy. In this work, we propose the state-of-the-art interaction estimator ProxySHAP, extending three recent works to produce fast and accurate estimates: We use the maximum sample reuse (MSR) method generalized to interactions by [15]. While inaccurate on its own, we combine MSR with the surrogate model and residual estimation strategy of [63]. By extending the algorithm of [65], we obtain an efficient algorithm capable of extracting any cardinal-probabilistic interaction indices from trees (see Section 3.1). Furthermore, we analytically and empirically find that the expected error of MSR depends not only on the value function but also on the number of entities and exponentially on the size of the interactions (see Section 3.2). To address this, we characterize the specific conditions–in terms of number of entities, budget, and interaction size–under which MSR is helpful. The payoff is an estimator that is more accurate, and optimized for out-of-the-box use. In an extensive benchmark across 47 datasets, we find that ProxySHAP achieves state-of-the-art performance for estimating probabilistic interactions, including large-scale applications with thousands of features (see Section 4.2). In particular, we achieve the lowest error in the small-budget regime where ProxySPEX previously dominated and the lowest error in the larger-budget regime where KernelSHAP-IQ previously dominated (see, e.g., Figure 4). Notably, ProxySHAP also achieves superior performance on a downstream CLIP explainability task (see Section 4.3). Our main contributions can be summarized as follows: (1) ProxySHAP. We introduce ProxySHAP, a novel estimation framework for cardinal-probabilistic interaction indices (see Figure 1). It reconciles the high sample efficiency of tree-based proxy models with a principled path to consistency via residual correction under explicit coverage conditions. (2) Theoretical Foundations. We derive a polynomial-time generalization of interventional TreeSHAP to compute exact cardinal-probabilistic interaction indices for tree ensembles, avoiding the exponential tree-depth dependence of Fourierbased extraction. We further study residual adjustment for higher-order interactions both theoretically and empirically, characterizing when MSR corrects proxy bias and when its variance makes the correction impractical. (3) State-of-the-Art Performance. We demonstrate that ProxySHAP sets a new standard for approximation quality. Across extensive benchmarks, our method outperforms the prior best estimators ProxySPEX and KernelSHAP-IQ.

Background

Cardinal-Probabilistic Interaction Indices. Fujimoto et al. [14] extended semivalues to interactions between subsets S ⊆ N . A cardinal-probabilistic interaction index is defined as: X X ϕpS (ν) := pst (n)∆S ν(T ), where ∆S ν(T ) := (−1)s−ℓ ν(T ∪ L). (3) L⊆S

T ⊆N \S

Here, ∆S ν(T ) quantifies the interaction of S in the presence of T . These indices satisfy the axioms of linearity (additivity), symmetry, dummy partnership, monotonicity, and k-monotonicity [14]. 3

Möbius Representation. Fujimoto et al. [14] have further shown the equivalent representation in terms of the Möbius transform mS (ν) := ∆S ν(∅), as X ϕpS (ν) = qts (n)mT (ν), (4) T ⊇S

where the corresponding weights qts (n) are computable by pst (n) for s ∈ {1, . . . , n} and all t ∈ {s, . . . , n}. The structure of cardinal-probabilistic interaction indices simplifies in their Möbius representation (see Table 1), which itself is a cardinal-probabilistic interaction index.

Maximum Sample Reuse (MSR). Since evaluating ν on all 2n coalitions is intractable, Wang and Jia [60] introduced maximum sample reuse (MSR), which was later extended to interactions by Fumagalli et al. [15]. Given a sample collection T drawn according to Psampling , MSR estimates: ϕ̂MSR (ν; T ) := S

(−1)s−|S∩T | pst−|S∩T | (n) 1 X ν(T ) . |T | Psampling (T )

(5)

T ∈T

MSR generalizes Unbiased KernelSHAP [9] and has been refined via stratification [31]. However, the variance of MSR scales with ν(T )2 [63]. To address this, Witter et al. [63] proposed RegressionMSR using a proxy model ν̂. We refine this approach for cardinal-probabilistic interaction indices.

Proxy-based Approximation of Shapley and Banzhaf Interactions

We now present ProxySHAP, a general framework for approximating cardinal-probabilistic interaction indices via a decomposition into a proxy term and a residual correction term. Given a budget of m coalitions, we sample a collection T = {T1 , . . . , Tm } ⊆ 2N and query the value function ν(T ) for all T ∈ T . Using these samples, we fit a proxy model ν̂T : 2N → R to approximate the underlying game ν. The key observation underlying ProxySHAP is that, by linearity of cardinal-probabilistic interaction indices [14], the target interaction admits the decomposition ϕpS (ν) = ϕpS (ν̂T ) + ϕpS (ν − ν̂T ) . | {z } | {z } Exact Proxy

(6)

Residual

This separates the overall approximation problem into two components: (i) a modeling problem, namely how well the proxy ν̂T approximates ν, and (ii) a correction problem, namely, how accurately the residual interactions can be estimated from the available coalition evaluations. This perspective makes ProxySHAP a framework rather than a single fixed estimator. At a conceptual level, the only requirement for the proxy class is that its cardinal-probabilistic interactions can be efficiently extracted. Learning the proxy itself is a standard supervised regression problem, where the sampled coalitions are represented as binary inputs and the corresponding game values ν(T ) serve as targets. Hence, in principle, any machine learning model can serve as a proxy, provided its interactions remain tractable. Moreover, this viewpoint naturally enables hyperparameter optimization to improve proxy quality, as shown in Figure 5. In this work, we study two proxy classes. First, we consider a linear proxy with interaction features, which provides a simple and often competitive baseline. Second, we consider tree-based proxies, which form our main instantiation of ProxySHAP. Their appeal is that they are substantially more expressive than linear surrogates, while—as we show in the next subsection—still admitting exact polynomial-time cardinal-probabilistic interaction extraction. This exact extraction is the key to obtaining a substantial runtime improvement over Fourier-based proxy methods. Linear Proxy. We first consider a linear model with interaction features. Let S ⊆ 2N be all interactions of interest, e.g. interactions up to order k = 1, . . . , n. We define the linear proxy as X ν̂linear (T ) := βS · 1[S ⊆ T ] with β ∈ R|S| . (7) S∈S |S|

The coefficients β ∈ R are determined using standard linear regression. A key advantage of the linear proxy in our setting is that its interactions are directly accessible through the Möbius representation. Each coefficient βS corresponds to a Möbius coefficient mS (ν̂linear ), and therefore the proxy interactions can be computed directly via Eq. (4). 4

Proposition 3.1. TheP Möbius transform of the linear proxy is given by mS (ν̂linear ) = βS 1[S ∈ S]. Hence, ϕpS (ν̂linear ) = T ∈S:T ⊇S qts (n)βT . Thus, linear proxies provide a simple and effective instantiation of ProxySHAP whenever the interaction basis remains sufficiently small to be fitted reliably. However, they become restrictive when the value function exhibits a strong nonlinearity, and the number of their parameters grows combinatorially with the interaction order. This makes them increasingly impractical for large n or high-order interactions. Tree-based proxies offer a compelling alternative: they capture complex non-linear relationships while remaining applicable to large feature sets and high-order interactions. Motivated by their strong empirical performance for cardinal-probabilistic values [63], we make treebased proxies applicable to interaction estimation by deriving an exact polynomial-time extraction procedure for cardinal-probabilistic interactions. 3.1

Exact Proxy Interactions for Tree-Based Models

Our main proxy classes are tree-based models such as XGBoost [8] and LightGBM [29]. We define such tree-based proxies as the piecewise constant functions induced by decision tree leaf predictions: X ν̂tree (T ) := cj · 1[Rj ⊆ T ⊆ N \ Lj ]. (8) j∈L

Runtime Improvement over Fourier

Here, L denotes the set of leaves, cj ∈ R is the prediction of leaf j, and Rj and Lj are the sets of features that split to the right and left, respectively, along the path leading to leaf j. An input coalition T reaches leaf j if and only if it contains all features in Rj and none of the features in Lj . The representation in Eq. (8) is particularly convenient, since each leaf contribution is an indicator game [65]. By deriving the Möbius representation of these indicator games and combining it with Eq. (4), we obtain a closed-form expression for any cardinal-probabilistic interaction index of the tree proxy. P Proposition 3.2. For S ⊆ N , we have ϕpS (ν̂tree ) = j∈L:S⊆Lj ∪Rj cj · λ (|Lj |, |Rj |, |S ∩ Lj |, |S|) , s Pℓ−u where λ(ℓ, r, u, s) := i=0 (−1)i+u ℓ−u i qi+u+r (n). 10 5 x faster BII order 1 FBII order 2 4 Proposition 3.2 shows that the interactions of the tree 10 x SII order 3 proxy can be computed exactly by aggregating leaf-wise FSII 3 10 x contributions. In particular, for a fixed interaction S, extraction requires only a single pass over the tree leaves 10 2 x together with evaluation of the closed-form weight λ. This 10x yields Algorithm 2 with a runtime of O(nnodes ) for a single interaction and O(nnodes · |S|) for a target collection S of 1 interactions (see Appendix B for details). Crucially, by slower the linearity of cardinal-probabilistic interaction indices 10x 1 2 3 4 6 8 5 7 Tree Depth [14], the result extends directly to ensembles of trees, with runtime scaling linearly with the number of trees. Figure 2: Runtime improvement of This exact extractor is the key computational advantage of extracting interactions using our Algotree-based ProxySHAP. In contrast to ProxySPEX, which rithm 2 over Fourier-based extraction. obtains interactions via Fourier coefficients and exhibits Per-dataset speedups and the effect of worst-case complexity exponential in the tree depth, O(4d ) tree depth on approximation quality are [4, 18], our method remains efficient even for deep trees. shown in Figures 13 and 14. As shown in Figure 2, interventional tree-based extraction is orders of magnitude faster than Fourierbased extraction (see Appendix D.5 for details), making tree models particularly attractive proxies for ProxySHAP. We refer to Appendix D.6 for a detailed comparison of ProxySPEX and ProxySHAP. 3.2

Residual Adjustment and its Practical Limits

While the tree proxy alone already yields a powerful estimator, it is not consistent in general, since the fitted proxy needs not perfectly match the underlying value function ν (see, e.g., Figure 4). To obtain a consistent estimator, we therefore correct for proxy bias by estimating the interactions of the residual game ν − ν̂T . As previously shown by Witter et al. [63], MSR adjustment consistently improves approximation quality for probabilistic values; our results in Figure 3 confirm this behavior. 5

Adjustment effect on MSE

4x 3x 2x

low

Order 1

medium

high

better

2x 3x 4x worse 17

low

Order 2

medium

Order 3

low

better

medium

no effect

30 90 Number of Players

high

worse

high

better

no effect

worse

212 17 30 90 212 17 Number of Players Budget: 1k 5k 10k 20k 35k

30 90 Number of Players

212

Figure 3: Comparison of ProxySHAP with and without MSR adjustment, measured by the MSE ratio. While MSR improves Shapley value approximation, it can degrade higher-order interaction estimates, as its variance scales as nk−1 /|T | for interactions of order k (Theorem 3.3). This motivates the adjusted ProxySHAP estimator ϕ̂ProxySHAP (ν; T ) = ϕpS (ν̂T ) + ϕ̂MSR (ν − ν̂T ; T ). S S While MSR often improves singleton estimates, this does not directly translate to improved interaction approximation, as evidenced in Figure 3. This is explained by the variance of the MSR estimator. Theorem 3.3 (Variance growth of MSR under leverage sampling for Shapley interactions). Suppose coalitions are sampled i.i.d. according to leverage sampling, Psampling (T ) =

1 . (n + 1) |Tn |

Then, for any interaction S ⊆ N , the MSR estimator of the Shapley interaction index satisfies  ∥ν∥2∞ log n  O , |S| = 1, h i  |T | V ϕ̂MSR (ν; T ) ≤ S  ∥ν∥2∞ n|S|−1  O , |S| ≥ 2. |T | Theorem 3.3 shows that, for Shapley interactions under leverage sampling, the variance upper bound grows rapidly with the interaction order. In particular, 2 when estimating all Shapley interactions up to ∥ν∥∞ nk−1 order k, the dominant variance term scales as O . Thus, the variance of MSR is governed |T | by three quantities: the number of sampled coalitions |T |, the number of players n, and the maximal interaction order k. We provide matching lower bounds and a related order-dependent result for Banzhaf interactions in Appendix A.2. We evaluate the quality of MSR adjustment across all 26 benchmarked TabArena [13] datasets in Figure 3; further details are provided in Appendix D.7. Our findings are threefold. First, for pairwise interaction approximation, MSR substantially reduces the MSE as the evaluation budget increases. Second, this benefit diminishes as the number of players grows, making the adjustment impractical for high-dimensional games. Third, for higher-order interactions, adjustments can already harm performance in medium-sized games, even with large budgets, in contrast to the more robust gains observed for pairwise interactions. Consequently, while MSR adjustment remains effective for first-order interactions, its benefit for higher-order interactions is more nuanced. It substantially improves approximation quality for secondorder interactions in small- to medium-sized games, but beyond pairwise interactions, it is mainly beneficial for smaller games. As a practical rule of thumb, we recommend applying MSR adjustment primarily in low-dimensional settings with n < 30. For larger games, adjustment should only be used when the sampling budget is sufficiently large relative to the dominant variance term, i.e., when |T | ≫ nk−1 for interactions up to order k, which in our experiments occurs for medium-sized games only at budgets above 10,000. 6

3.3

The ProxySHAP Algorithm

We summarize the full ProxySHAP procedure in Algorithm 1, using Algorithm 2 to compute the exact proxy interactions. Similar to [63], we find that using the same sampled coalitions T for both proxy fitting and residual estimation is beneficial, see Appendix D.8 for a comparison. Unless stated otherwise, we obtain coalitions through leverage sampling [45] and sample without replacement, which can only reduce the variance compared to i.i.d. sampling [22]. ProxySHAP also works with other sampling schemes [16, 36], though we found they yield similar results (see Appendix D.4 for further details). Computational Complexity. Fitting the Algorithm 1 ProxySHAP(XGBoost, MSR) XGBoost proxy ν̂ in ProxySHAP with m s distribubinary-encoded coalitions takes roughly Require: value function ν, weight pt (n), sampling N tion P , interactions of interest S ⊆ 2 sampling O(m log m) time [8]. Extracting the p interactions from the proxy using Al- Ensure: ϕ̂S for all S ∈ S T ← sample according to Psampling gorithm 2 takes O(ntrees ℓmax |S|) time, ▷ Phase 1: fit proxy ν̂ and residual game r where ntrees is the number of trees and ν̂T ← train XGBoost on {(T, ν(T )) : T ∈ T } ℓmax is the maximum number of leaves r(T ) ← ν(T ) − ν̂T (T ) for all T ∈ T per tree. The situational MSR adjust▷ Phase 2: extract interactions ments adds another O(|S|m), with the for S ∈ S do total complexity of ProxySHAP being ϕ̂Proxy ← ϕpS (ν̂T ) ▷ Algorithm 2 S MSR O (|S| · (ntrees ℓmax + m)). For a linear ϕ̂S ← ϕ̂MSR (r; T ) ▷ situational adjustment; see S proxy, the number of fitted parameters Section 3.2 equals the number of target interactions, ϕ̂pS ← ϕ̂Proxy + ϕ̂MSR S S end for so the computational demand grows as p return ϕ̂S for all S ∈ S O(mn2k ) using ordinary least squares, where k is the maximal interaction order.

Experiments

We empirically evaluate ProxySHAP across a range of experimental settings and systematically compare it against different standard baselines: KernelSHAP-IQ [16], ProxySPEX [4], SHAPIQ [i.e., MSR for interactions, 15], SVARM-IQ [31], and traditional permutation sampling [57, 58]. The implementation 1 is based on shapiq [42]. Games. We evaluate ProxySHAP on local-explanation games across tabular benchmarks [42, 55], including TabArena [13], and established vision, language, graph, and vision–language settings [2, 42, 44]. The underlying models include TabPFN [23], XGBoost [8], LightGBM [29], vision transformers [11], language models [51], CLIP [48], and GNNs [64]; Table 3 summarizes all 47 datasets. We use exhaustive evaluation only for games with n ≤ 16, since exact Shapley and Banzhaf interactions scale exponentially in n. For larger tabular games, tree models allow efficient ground-truth extraction via Algorithm 2; for graphs, we use GraphSHAP-IQ [44]. For CLIP, ground-truth interactions are unavailable, so we use task-specific faithfulness metrics. Further details are given in Section C. Metrics. We measure approximation quality using relative mean squared error (Relative MSE; lower is better), defined as the sum of squared errors normalized by the sum of squared groundtruth interaction values. This normalization makes errors comparable across games with different interaction magnitudes. Unless stated otherwise, we report the mean and standard error of the mean (SEM) over 30 explained instances per dataset. We additionally report computational efficiency in terms of model evaluations and runtime (see Appendix D.3). To broaden the scope of evaluation, for models such as CLIP, we evaluate explanation quality using R2 faithfulness and the area under the insertion–deletion curve (see Appendix D.1; 2). 4.1

Approximation Quality

We first compare ProxySHAP to state-of-the-art baselines in terms of approximation quality (see Figure 4). We evaluate two proxy classes: a linear model with interaction features, ProxySHAP 1 https://github.com/Advueu963/ProxySHAP

100

10 1

10 2

10 3 10 4

102

103

104

102

100

103

10 1

10 2

10 3

104

LGBM on MarketingCamp (n = 25)

LGBM on Kddcup09 (n = 212)

100

102

103

104

LGBM on Splice (n = 60)

100

103

104

LGBM on Coil2000 (n = 85)

100

10 1

10 2

10 3

order 2 order 3

GNN on Mutagenicity (n = 35)

10 3 DistilBERT on IMDB (n = 14)

10 3

ViT16 on ImageNet (n = 16)

order 2

TabPFN on Estate (n = 15)

10 1

103

104

10 1

10 2

10 4 102

order 3

Relative MSE ± SEM

100

102

ProxySHAP (XGBoost) [our] ProxySHAP (XGBoost, MSR) [our]

103

104

102

Model Evaluations

ProxySHAP (Linear) [our] ProxySHAP (Linear, MSR) [our]

103

104

KernelSHAPIQ ProxySPEX (XGBoost)

102

103

104

SHAPIQ SVARMIQ PermutationSamplingSII

Figure 4: Approximation quality (Relative MSE) for Shapley interactions of ProxySHAP across different configurations and state-of-the-art baselines. Additional results for Shapley and Banzhaf interactions on all 47 datasets can be found in Figure 18 and Figure 19, respectively.

(Linear), and an XGBoost regressor with default hyperparameters, ProxySHAP (XGBoost), each with and without MSR adjustment. Across datasets and interaction orders, ProxySHAP consistently outperforms all baselines, often by several orders of magnitude in relative MSE. MSR adjustment improves estimates for small games (n < 30) and for larger games when the sampling budget is sufficiently large, as in M UTAGENICITY. However, consistent with Section 3.2, its benefit decreases with interaction order and player count and can hurt performance in larger games, as observed on S PLICE. The linear proxy is competitive and sometimes even outperforms the tree-based proxy, e.g., on M ARKETING C AMP. Yet, it becomes impractical for large feature counts and higher-order interactions due to its computational complexity (see Section 3). Tree-based proxies avoid this bottleneck and remain effective even when KernelSHAPIQ is no longer feasible. Overall, XGBoost provides a scalable and accurate proxy, while MSR adjustment is most useful when the sampling budget is sufficiently large relative to the player count and interaction order. Additional results for further datasets and for both Shapley and Banzhaf interactions are provided in Section D.9. 4.2

Practical Considerations of ProxySHAP CG60 (n = 60)

Crime (n = 101)

Relative MSE ± SEM

100 HPO improves performance. The qual100 ity of ProxySHAP’s approximation de10 1 10 1 pends directly on the fitted proxy. We 10 2 10 2 validate this via hyperparameter optimization (HPO), denoting the tuned variant 102 103 104 102 103 104 as ProxySHAP (XGBoost+HPO) (see ApModel Evaluations QsarTid11 ( n = 1024 ) Bioresponse ( n = 1776 ) pendix C.3). As shown in Figure 5 (top), 100 100 HPO substantially improves over the de10 1 fault XGBoost proxy, with further exam10 2 ples in Appendix D.2. Since HPO is 10 1 costly, we derive a cheaper ProxySHAP 10 3 100 102 101 101 (XGBoost+HPO-Informed) variant from Total Runtime (s; without Model call time) recurring strong HPO configurations. It ProxySHAP (XGBoost+Default) [our] ProxySPEX (XGBoost+HPO-Informed) ProxySHAP (XGBoost+HPO-Informed) [our] ProxySPEX (XGBoost+Default) performs on par with full HPO at small to ProxySHAP (XGBoost+HPO) [our] medium budgets, highlighting the importance of proxy configuration. Figure 5: Relative MSE for pairwise Shapley interacScalability of ProxySHAP. We demon- tion approximation of ProxySHAP with HPO (top) and strate the scalability of ProxySHAP beyond for large n (bottom). Further results in Figure 10.

1000 features in Figure 5. Using ProxySHAP, we achieve better approximation quality at lower 8

runtime, with the HPO-informed variant further improving it. Contrary to ProxySHAP, ProxySPEX does not improve approximation quality using the HPO-informed configuration. 4.3

ProxySHAP Improves the Approximation of Faithful Interaction Explanations of CLIP

Setup. Similarly to Baniecki et al. [2], we analyze the CLIP model in two vision transformer variants: ViT-32 and ViT-16. We explain a sample of 200 image–text pairs from the MS COCO dataset [33], which contain around 10– 30 text tokens per input, resulting in about 60–72 players in the final approximation game. Following the original work, we approximate the faithful Banzhaf interaction index of order 2 and quantify the quality of explanations with the area between the insertion/deletion curves (AID). Unlike the original work, we experiment with smaller budgets ranging from 103 to 105 CLIP model calls, where each inference denotes that both the vision and language encoders are called on a single image–text pair.

Area under the Insertion-Deletion Curve

We demonstrate the broader applicability of ProxySHAP to improve the approximation of faithful interaction explanations of CLIP [FIxLIP, 2], a popular vision–language encoder architecture [48]. We follow the original experimental setup [2] and compare ProxySHAP to the original linear regressionbased approximation, as well as ProxySPEX, in the FIxLIP game, where the goal is to explain the interaction between image and text inputs in CLIP (see Figure 1). Further details on the experimental setup and additional results are provided in Appendix D.1. FIxLIP: ViT16

FIxLIP: ViT32

1.0 0.8 0.6 0.4 0.2 0.0

103

104 FIxLIP+Baseline

105103

CLIP Calls

FIxLIP+ProxySHAP (XGBoost) [our]

104 FIxLIP+ProxySPEX

Figure 6: Area between the insertion/deletion curves (AID) for explaining two CLIP ViT variants on the MS COCO dataset with ProxySHAP, ProxySPEX, and the FIxLIP baseline.

Results. Figure 6 effectively demonstrates that ProxySHAP Pareto-dominates the original linear regression-based approximation, as well as ProxySPEX, in the FIxLIP game for both models. Overall, we find that the ProxySHAP adjustment incurs substantial computational overhead despite not improving the estimate. Note that in this setup, ProxySPEX and ProxySHAP with adjustment took about 10× more time to compute than ProxySHAP without the adjustment and the FIxLIP baseline. In Appendix D.1, we provide additional analysis measuring the R2 metric, which yields a similar conclusion, and we ablate on FIxLIP’s cross-modal estimator.

Conclusion

We propose ProxySHAP, an efficient model-agnostic approximation method for the broad class of cardinal-probabilistic interaction indices. At its core, ProxySHAP extracts, in closed form, any cardinal-probabilistic interaction index, including Shapley and Banzhaf variants, from tree-based proxies. Notably, we achieve orders-of-magnitude speedups over Fourier-based extraction. By exploiting the linearity of interaction indices, ProxySHAP admits a clean decomposition into an exact proxy term and an MSR-based residual correction. Based on our extensive empirical evaluation and theoretical variance bound for MSR, we recommend applying the residual correction situationally: for interactions of order k, it is most useful in games with n < 30 players or when the budget satisfies |T | ≫ nk−1 . Empirically, ProxySHAP achieves strong approximation quality across an extensive benchmark, outperforming ProxySPEX and KernelSHAP-IQ in both low- and high-budget regimes, and Pareto-dominating FIxLIP and ProxySPEX when applied to CLIP. Limitations and future work. The quality of ProxySHAP’s approximation depends directly on the trained proxy. We demonstrated that HPO substantially increases the performance of the XGBoost proxy, but incurs a large computational overhead. In future work, we aim to explore other proxy classes, including their efficient interaction extraction. A second open direction concerns the residual correction: while MSR restores consistency in principle, its variance grows rapidly with interaction order, limiting its practical benefit in high-dimensional settings. Developing residual estimators that scale more gracefully remains an important open problem. Another extension is the class of generalized values [39] that capture joint contributions across feature groups [17]. 9

Broader impact. We believe ProxySHAP can empower scientific researchers in quantifying nonlinear dependencies between variables in complex systems, e.g. in physics [35] and material sciences [5]. We provide a highly scalable C++ implementation of our algorithm, enabling the quantification of interactions in foundation models spanning billions of parameters across large datasets.

Acknowledgments and Disclosure of Funding Fabian Fumagalli and Maximilian Muschalik acknowledges funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation): TRR 318/3 2026 – 438445824. Hubert Baniecki was supported by the Foundation for Polish Science (FNP), and the Polish Ministry of Education and Science within the “Pearls of Science” program, project number PN/01/0087/2022.

References [1] Hubert Baniecki, Giuseppe Casalicchio, Bernd Bischl, and Przemyslaw Biecek. Efficient and Accurate Explanation Estimation with Distribution Compression. In Proceedings of the International Conference on Learning Representations (ICLR), 2025. [2] Hubert Baniecki, Maximilian Muschalik, Fabian Fumagalli, Barbara Hammer, Eyke Hüllermeier, and Przemyslaw Biecek. Explaining Similarity in Vision-Language Encoders with Weighted Banzhaf Interactions. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [3] John F Banzhaf III. Weighted voting doesn’t work: A mathematical analysis. Rutgers Law Review, 19:317, 1964. [4] Landon Butler, Abhineet Agarwal, Justin Singh Kang, Yigit Efe Erginbas, Bin Yu, and Kannan Ramchandran. Proxy-SPEX: Sample-efficient interpretability via sparse feature interactions in LLMs. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [5] Yu-Xuan Cai, Hai-Yan Chen, Ya-Jing Qu, Wen-Hao Zhao, Mei-Ying Wang, Ying Chen, and Jin Ma. Improved vertical distribution prediction of soil vocs contamination in site-scale utilizing ensemble machine learning approach integrated with molecular descriptors. Journal of Hazardous Materials, page 139452, 2025. [6] Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the Shapley value based on sampling. Computers & Operations Research, 36(5):1726–1730, 2009. doi: 10.1016/j. cor.2008.04.004. [7] Javier Castro, Daniel Gómez, Elisenda Molina, and Juan Tejada. Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation. Computers & Operations Research, 82:180–188, 2017. doi: 10.1016/j.cor.2017.01.019. [8] Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 785–794. ACM, 2016. doi: 10.1145/2939672.2939785. [9] Ian Covert and Su-In Lee. Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3457–3465, 2021. [10] Ian Connick Covert, Chanwoo Kim, Su-In Lee, James Zou, and Tatsunori Hashimoto. Stochastic amortization: A unified approach to accelerate feature and data attribution. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2024. [11] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In Proceedings of the International Conference on Learning Representations (ICLR), 2021. 10

[12] James Enouen and Yan Liu. InstaSHAP: Interpretable additive models explain shapley values instantly. In Proceedings of the International Conference on Learning Representations (ICLR), 2025. [13] Nick Erickson, Lennart Purucker, Andrej Tschalzev, David Holzmüller, Prateek Mutalik Desai, David Salinas, and Frank Hutter. Tabarena: A living benchmark for machine learning on tabular data. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2026. [14] Katsushige Fujimoto, Ivan Kojadinovic, and Jean-Luc Marichal. Axiomatic characterizations of probabilistic and cardinal-probabilistic interaction indices. Games and Economic Behavior, 55(1):72–99, 2006. doi: 10.1016/j.geb.2005.03.002. [15] Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Hammer. SHAP-IQ: Unified Approximation of any-order Shapley Interactions. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pages 11515–11551, 2023. [16] Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Hammer. KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions. In Proceedings of the International Conference on Machine Learning (ICML), pages 14308–14342, 2024. [17] Fabian Fumagalli, Maximilian Muschalik, Eyke Hüllermeier, Barbara Hammer, and Julia Herbinger. Unifying Feature-Based Explanations with Functional ANOVA and Cooperative Game Theory. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 5140–5148, 2025. [18] Ali Gorji, Andisheh Amrollahi, and Andreas Krause. SHAP values via sparse fourier representation. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2025. [19] Michel Grabisch and Marc Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of Game Theory, 28(4):547–565, 1999. doi: 10.1007/s001820050125. [20] Léo Grinsztajn, Klemens Flöge, Oscar Key, Felix Birkel, Philipp Jund, Brendan Roof, Benjamin Jäger, Dominik Safaric, Simone Alessi, Adrian Hayler, Mihir Manium, Rosen Yu, Felix Jablonski, Shi Bin Hoo, Anurag Garg, Jake Robertson, Magnus Bühler, Vladyslav Moroshan, Lennart Purucker, Clara Cornu, Lilly Charlotte Wehrhahn, Alessandro Bonetto, Bernhard Schölkopf, Sauraj Gambhir, Noah Hollmann, and Frank Hutter. Tabpfn-2.5: Advancing the state of the art in tabular foundation models. CoRR, abs/2511.08667, 2025. doi: 10.48550/ARXIV.2511.08667. [21] Naofumi Hama, Masayoshi Mase, and Art B. Owen. Deletion and insertion tests in regression models. Journal of Machine Learning Research, 24:290:1–290:38, 2023. [22] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13–30, 1963. [23] Noah Hollmann, Samuel Müller, Lennart Purucker, Arjun Krishnakumar, Max Körfer, Shi Bin Hoo, Robin Tibor Schirrmeister, and Frank Hutter. Accurate predictions on small data with a tabular foundation model. Nature, 637(8045):319–326, 2025. doi: 10.1038/s41586-024-08328-6. [24] Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lee, and Rajesh Ranganath. FastSHAP: Real-Time Shapley Value Estimation. In Proceedings of the International Conference on Learning Representations (ICLR), 2022. [25] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J. Spanos. Towards efficient data valuation based on the shapley value. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1167–1176, 2019. [26] Peng Jin, Hao Li, Li Yuan, Shuicheng Yan, and Jie Chen. Hierarchical Banzhaf interaction for general video-language representation learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47(3):2125–2139, 2025. 11

[27] Justin Singh Kang, Landon Butler, Abhineet Agarwal, Yigit Efe Erginbas, Ramtin Pedarsani, Bin Yu, and Kannan Ramchandran. SPEX: Scaling feature interaction explanations for LLMs. In Proceedings of the Conference on Machine Learning (ICML), pages 28878–28903, 2025. [28] Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of Medicinal Chemistry, 48(1):312–320, 2005. doi: 10.1021/jm040835a. [29] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pages 3146–3154, 2017. [30] Patrick Kolpaczki, Viktor Bengs, Maximilian Muschalik, and Eyke Hüllermeier. Approximating the shapley value without marginal contributions. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 13246–13255, 2024. [31] Patrick Kolpaczki, Maximilian Muschalik, Fabian Fumagalli, Barbara Hammer, and Eyke Hüllermeier. SVARM-IQ: efficient approximation of any-order shapley interactions through stratification. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3520–3528, 2024. [32] Quentin Lhoest, Albert Villanova del Moral, Patrick von Platen, Thomas Wolf, Mario Šaško, Yacine Jernite, Abhishek Thakur, Lewis Tunstall, Suraj Patil, Mariama Drame, Julien Chaumond, Julien Plu, Joe Davison, Simon Brandeis, Victor Sanh, Teven Le Scao, Kevin Canwen Xu, Nicolas Patry, Steven Liu, Angelina McMillan-Major, Philipp Schmid, Sylvain Gugger, Nathan Raw, Sylvain Lesage, Anton Lozhkov, Matthew Carrigan, Théo Matussière, Leandro von Werra, Lysandre Debut, Stas Bekman, and Clément Delangue. Datasets: A community library for natural language processing. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, (EMNLP 2021), pages 175–184. Association for Computational Linguistics, 2021. [33] Tsung-Yi Lin, Michael Maire, Serge J. Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. Microsoft COCO: common objects in context. In European Conference on Computer Vision ECCV, volume 8693, pages 740–755, 2014. [34] Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter. Smac3: A versatile bayesian optimization package for hyperparameter optimization. Journal of Machine Learning Research, 23(54):1–9, 2022. URL http://jmlr.org/papers/v23/21-0888.html. [35] Tianran Liu, Nicky Evans, Kangyu Ji, Ronaldo Lee, Aaron Zhu, Vinn Nguyen, James Serdy, Elizabeth M Wall, Yongli Lu, Florian A Formica, et al. Disentangling environmental effects on perovskite solar cell performance via interpretable machine learning. ACS Energy Letters, 11: 1609–1617, 2026. [36] Scott M. Lundberg and Su-In Lee. A Unified Approach to Interpreting Model Predictions. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pages 4765– 4774, 2017. [37] Scott M. Lundberg, Gabriel G. Erion, Hugh Chen, Alex J. DeGrave, Jordan M. Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable AI for trees. Nature Machine Intelligence, 2(1):56–67, 2020. doi: 10.1038/s42256-019-0138-9. [38] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the Association for Computational Linguistics: Human Language Technologies (HLT), pages 142–150, 2011. [39] Jean-Luc Marichal, Ivan Kojadinovic, and Katsushige Fujimoto. Axiomatic characterizations of generalized values. Discrete Applied Mathematics, 155(1):26–43, 2007. doi: 10.1016/J.DAM. 2006.05.002. 12

[40] Majid Mohammadi, Siu Lun Chau, and Krikamol Muandet. Computing exact Shapley values in polynomial time for product-kernel methods. arXiv preprint, arXiv:2505.16516, 2025. [41] Christoph Molnar, Gunnar König, Julia Herbinger, Timo Freiesleben, Susanne Dandl, Christian A Scholbeck, Giuseppe Casalicchio, Moritz Grosse-Wentrup, and Bernd Bischl. General pitfalls of model-agnostic interpretation methods for machine learning models. In xxAI-Beyond Explainable AI: International Workshop, Held in Conjunction with ICML 2020, pages 39–68, 2022. [42] Maximilian Muschalik, Hubert Baniecki, Fabian Fumagalli, Patrick Kolpaczki, Barbara Hammer, and Eyke Hüllermeier. shapiq: Shapley Interactions for Machine Learning. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pages 130324–130357, 2024. [43] Maximilian Muschalik, Fabian Fumagalli, Barbara Hammer, and Eyke Hüllermeier. Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 14388–14396, 2024. doi: 10.1609/aaai.v38i13.29352. [44] Maximilian Muschalik, Fabian Fumagalli, Paolo Frazzetto, Janine Strotherm, Luca Hermes, Alessandro Sperduti, Eyke Hüllermeier, and Barbara Hammer. Exact Computation of AnyOrder Shapley Interactions for Graph Neural Networks. In Proceedings of the Conference on Learning Representations (ICLR), 2025. [45] Christopher Musco and R. Teal Witter. Provably Accurate Shapley Value Estimation via Leverage Score Sampling. In Proceedings of the International Conference on Learning Representations (ICLR), 2025. [46] Alexander Nadel and Ron Wettenstein. From decision trees to boolean logic: A fast and unified SHAP algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 24476–24485, 2026. doi: 10.1609/AAAI.V40I29.39630. [47] Lars H. B. Olsen, Ingrid K. Glad, Martin Jullum, and Kjersti Aas. Using Shapley values and variational autoencoders to explain predictive models with dependent mixed features. Journal of Machine Learning Research, 23(213):1–51, 2022. [48] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Proceedings of the International Conference on Machine Learning ICML, pages 8748–8763, 2021. [49] Benedek Rozemberczki, Lauren Watson, Péter Bayer, Hao-Tsung Yang, Oliver Kiss, Sebastian Nilsson, and Rik Sarkar. The shapley value in machine learning. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), pages 5572–5579, 2022. [50] Benjamin Sanchez-Lengeling, Jennifer Wei, Brian Lee, Emily Reif, Peter Wang, Wesley Qian, Kevin McCloskey, Lucy Colwell, and Alexander Wiltschko. Evaluating attribution for graph neural networks. In The Thirty-third Annual Conference on Neural Information Processing Systems, volume 33, pages 5898–5910, 2020. [51] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. CoRR, abs/1910.01108, 2019. [52] Meghdut Sengupta, Maximilian Muschalik, Fabian Fumagalli, Barbara Hammer, Eyke Hüllermeier, Debanjan Ghosh, and Henning Wachsmuth. Investigating the impact of conceptual metaphors on LLM-based NLI through shapley interactions. In Findings of the Association for Computational Linguistics: EMNLP 2025, pages 17393–17403, 2025. [53] L. S. Shapley. A Value for n-Person Games. In Contributions to the Theory of Games (AM-28), Volume II, pages 307–318. Princeton University Press, 1953. [54] Maximilian Spliethöver, Tim Knebler, Fabian Fumagalli, Maximilian Muschalik, Barbara Hammer, Eyke Hüllermeier, and Henning Wachsmuth. Adaptive prompting: Ad-hoc prompt composition for social bias detection. In Proceedings of the Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics, 2025. 13

[55] Erik Strumbelj and Igor Kononenko. An Efficient Explanation of Individual Classifications using Game Theory. Journal of Machine Learning Research, 11:1–18, 2010. [56] Erik Strumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and Information Systems, 41(3):647–665, 2014. doi: 10.1007/s10115-013-0679-x. [57] Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The Shapley Taylor Interaction Index. In Proceedings of the International Conference on Machine Learning (ICML), pages 9259–9268, 2020. [58] Che-Ping Tsai, Chih-Kuan Yeh, and Pradeep Ravikumar. Faith-Shap: The Faithful Shapley Interaction Index. Journal of Machine Learning Research, 24(94):1–42, 2023. [59] Michael Tschannen, Alexey Gritsenko, Xiao Wang, Muhammad Ferjad Naeem, Ibrahim Alabdulmohsin, Nikhil Parthasarathy, Talfan Evans, Lucas Beyer, Ye Xia, Basil Mustafa, et al. SigLIP 2: Multilingual vision-language encoders with improved semantic understanding, localization, and dense features. arXiv preprint arXiv:2502.14786, 2025. [60] Jiachen T. Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 6388–6421, 2023. [61] Jiachen T. Wang, Prateek Mittal, and Ruoxi Jia. Efficient data Shapley for weighted nearest neighbor algorithms. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2557–2565, 2024. [62] Marcel Wever, Maximilian Muschalik, Fabian Fumagalli, and Marius Lindauer. HyperSHAP: Shapley Values and Interactions for Hyperparameter Importance. In AAAI, 2026. [63] R. Teal Witter, Yurong Liu, and Christopher Musco. Regression-adjusted monte carlo estimators for shapley values and probabilistic values. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2025. URL https://openreview.net/forum? id=Qabko39AS5. [64] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the International Conference on Learning Representations (ICLR), 2019. URL https://openreview.net/forum?id=ryGs6iA5Km. [65] Artjom Zern, Klaus Broelemann, and Gjergji Kasneci. Interventional SHAP values and interaction values for piecewise linear regression trees. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 11164–11173, 2023. [66] Chenyang Zhao, Kun Wang, Janet H. Hsiao, and Antoni B. Chan. Grad-ECLIP: Gradient-based visual and textual explanations for CLIP. In Proceedings of the International Conference on Machine Learning ICML, 2024.

Appendix for “Proxy-based Approximation of Shapley and Banzhaf Interactions” A Proofs

A.1 Proof of Proposition 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.2 Proof of Theorem 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.3 Closed Forms for Proposition 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . .

B Generalization of Interventional TreeSHAP

C Experimental Details

C.1 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

C.2 Computational Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

C.3 Hyperparameter Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . .

C.4 Baselines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D Additional Approximation Results

D.1 Additional Experiments with FIxLIP . . . . . . . . . . . . . . . . . . . . . . . . .

D.2 XGBoost Default for Large Player Counts . . . . . . . . . . . . . . . . . . . . . .

D.3 Runtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.4 Ablation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.5 Fourier Extraction vs. Interventional Extraction . . . . . . . . . . . . . . . . . . .

D.6 Detailed Comparison of ProxySHAP and ProxySPEX . . . . . . . . . . . . . . . .

D.7 When to use Adjustment? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.8 Shared vs. Disjoint Subsets in ProxySHAP . . . . . . . . . . . . . . . . . . . . .

D.9 Approximation Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E Additional Related Work

Table 1: Weights of cardinal-probabilistic interaction indices.

Weight

Banzhaf (w)

pst (n)

w (1 − w)

qts (n)

wt−s

Shapley 1 (n − s + 1) n−s t 1 t−s+1

n−s−t

Möbius

1[t = 0] 1[t = s]

Proofs

A central contribution of our method is an extension of the algorithm of [65] to compute cardinalprobabilistic interactions of arbitrary order (see Algorithm 2). We establish a general extraction result in Section A.1, with specialized proofs for commonly used indices—including the Banzhaf Interaction Index (BII)[19], the Chaining Interaction Index (CHII) [14], the Faithful Banzhaf Interaction Index (FBII)[58] and Faithful Shapley Interaction Index (FSII) [58]—provided in Section A.3. These results rely repeatedly on Lemma A.1 and Lemma A.2. We prove the variance growth of MSR for general interaction indices under general sampling schemes in Appendix A.2. We investigate the variance growth of MSR for the Shapley Interaction Index and Banzhaf Interaction Index under leverage sampling. We further showcase that the derived upper bounds are tight by providing matching lower bounds for both indices and sampling schemes. A.1

Proof of Proposition 3.2

Before proving the main result, we first establish two lemmas that are instrumental for the proof of Proposition 3.2. These will also be used to derive the closed-form expression for the Banzhaf Interaction Index, Chaining Interaction Index, Faithful Banzhaf Interaction Index, and Faithful Shapley Interaction Index in Section A.3. Lemma A.1. For A ⊆ B ⊆ N , we have X 1[A,B] = (−1)t 1[T ∪A,N ] T ⊆N \B

Proof. See proof of Lemma 1 in Zern et al. [65]. Lemma A.2. Let N be the set of players, A ⊆ B ⊆ N , and the game 1[A,B] (T ) = 1 iff A ⊆ T ⊆ B. Then it holds that the Möbius value for a set S ⊆ N equals mS (1[A,B] ) = (−1)|(N \B)∩S| · 1A⊆S,(B\A)∩S=∅ Proof. Let N be the set of players, A, B ⊆ N such that A ⊆ B, and the game 1[A,B] be defined as above, and S ⊆ N . Then X mS (1[A,B] ) = (−1)s−l 1[A,B] (L). L⊆S

Note that we must have A ⊆ S, as otherwise the game value is always zero. We therefore define F = (N \ B) ∩ S and G = (B \ A) ∩ S such that S = A ∪ F ∪ G, which yields: X mS (1[A,B] ) = (−1)f +g+a−l 1[A,B] (L). L⊆G∪F ∪A

Observe that only those L have non-zero game values for which A ⊆ L and L ∩ F = ∅, as otherwise L ⊆ B would not hold. Therefore, we can equivalently express the sum as X mS (1[A,B] ) = (−1)f +g (−1)−l = (−1)f +g

L⊆G g X l=0

g (−1)−l . l

The latter term always equals 0 for g ̸= 0, which yields our second condition G = (B \ A) ∩ S = ∅. Finally, we then have mS (1[A,B] ) = (−1)f = (−1)|(N \B)∩S| if and only if (i) A ⊆ S and (B \ A) ∩ S = ∅, which concludes the proof. We now prove the main result of this section, which provides a closed-form expression for the cardinal-probabilistic interaction indices of tree-based proxies. Proposition 3.2. For S ⊆ N and leaves j ∈ L, we have X ϕpS (ν̂tree ) = cj · λ (|Lj |, |Rj |, |S ∩ Lj |, |S|) , j∈L S⊆Lj ∪Rj

where λ(ℓ, r, u, s) :=

Pℓ−u

i+u ℓ−u s i=0 (−1) i qi+u+r (n).

Proof of Proposition 3.2. Let 1[A,B] : 2N → {0, 1} be an indicator game such that 1[A, B](T ) = 1[A ⊆ T ⊆ B]. We observe that ν̂tree can be written as a sum of indicator games :   X p p  ϕS (ν̂tree ) = ϕS cj · 1[Rj , N \ Lj ] j∈L

cj · ϕpS (1[Rj , N \ Lj ])

j∈L

Using Lemma A.1 we obtain:  ϕpS (ν̂tree ) =

cj ϕpS 

(−1)t ϕpS (1[T ∪Rj ,N ] )

X T ⊆Lj

j∈L

(−1)t 1[T ∪Rj ,N ] 

T ⊆Lj

j∈L

 X

j∈L

T ⊆Lj

(−1)t

qvs (n)mV (1[T ∪Rj ,N ] )

V ⊇S s (−1)t qt+r (n) j

T ⊆Lj T ∪Rj ⊇S

j∈L

In the second-to-last step we use (4); in the last step we use mV (1[Rj ∪T,N ] ) = 1 iff Rj ∪ T = V and 0 otherwise (a direct consequence of B = N in Lemma A.2). Notice that we can only update those interactions S in leaf j for which it holds S ⊆ Lj ∪ Rj , since the condition T ∪ Rj ⊇ S does not hold otherwise, and as such ϕpS (1[Rj , N \ Lj ]) = 0. We define S0 := S ∩ Lj and let B ⊆ Lj \ S0 , so that T = S0 ∪ B, which gives rise to X X s ϕpS (ν̂tree ) = cj (−1)b+s0 qb+s (n) 0 +rj j∈L S⊆Lj ∪Rj

B⊆Lj \S0 ℓj −s0

i+s0

(−1)

i=0

j∈L S⊆Lj ∪Rj

Defining λ(ℓ, r, u, s) :=

Pℓ−u

ℓj − s0 s qi+s0 +rj (n) i

i+u ℓ−u s i=0 (−1) i qi+u+r (n) we obtain:

ϕpS (ν̂tree ) =

cj λ(|Lj |, |Rj |, |S ∩ Lj |, |S|)

j∈L S⊆Lj ∪Rj

which concludes the proof. 17

|S| = 1 (fitted C = 1.05)

|S| = 2 (fitted C = 3.11)

empirical Var (mean over |S|=1) empirical Var (max over |S|=1) empirical Var (min over |S|=1) bound v 2 logn/|T|

100

|S| = 3 (fitted C = 6.05)

empirical Var (mean over |S|=2) empirical Var (max over |S|=2) empirical Var (min over |S|=2) bound v 2 n 1/|T|

102

103

101

10 2

10 1

103

budget |T|

10 2

104 mean / bound max / bound min / bound fitted C

1.2 1.0

100

0.6

budget |T|

0.4

104

10 1

mean / bound max / bound min / bound fitted C

Var / bound

0.8

103

budget |T|

3 2

104 mean / bound max / bound min / bound fitted C

10 5 0

104

budget |T|

0.2

103

Var / bound

10 3

Var / bound

102

Var

10 1 100

empirical Var (mean over |S|=3) empirical Var (max over |S|=3) empirical Var (min over |S|=3) bound v 2 n 2/|T|

104

103

budget |T|

104

103

budget |T|

104

Figure 7: Empirical variance scaling with sampling budget |T | for interaction orders |S| = k. For each order k, the plot shows the mean, minimum, and maximum empirical variance over all subsets S of size k. The black curve denotes the theoretical bound shape, namely proportional to ∥v∥2∞ log(n)/|T | for k = 1 and to ∥v∥2∞ nk−1 /|T | for k > 1. Since big-O bounds are defined only up to a multiplicative constant, the theoretical shape is rescaled by a constant C, fitted in log-space to the empirical maximum variance across budgets. Thus, the black curve is used to compare scaling behavior rather than absolute constants. Agreement in slope between the empirical maximum and the rescaled theoretical curve indicates that the observed worst-case variance is consistent with the proposed asymptotic bound over the tested budget range. A.2

Proof of Theorem 3.3

We first derive a general variance identity for the MSR estimator under arbitrary sampling distributions in Theorem A.3. We then specialize this identity to proportional sampling and, most importantly, to leverage sampling for the Shapley interaction index. The latter specialization yields Theorem 3.3 from the main paper. Corresponding lower bounds are shown in Corollary A.7. The corresponding bound for the Banzhaf interaction index can be found in Corollary A.8. In Figure 7, we provide an empirical sanity check of the derived bound on SII under leverage sampling, as the SII is a widely adopted interaction index. Theorem A.3 (General variance identity for MSR). Let S ⊆ N with s := |S|, and let T1 , . . . , T|T | be sampled i.i.d. from a sampling distribution Psampling on 2N with Psampling (T ) > 0 for all T ⊆ N . Then the MSR estimator ϕ̂p,MSR (ν; T ) = S

|T | (−1)s−|S∩Ti | ps|Ti |−|S∩Ti | (n) 1 X ν(Ti ) |T | i=1 Psampling (Ti )

satisfies   2 s X p (n) 1 |T |−|S∩T |  V[ϕ̂p,MSR (ν; T )] = ν(T )2 − ϕS (ν)2  . S |T | P (T ) sampling N T ∈2

In particular, V[ϕ̂p,MSR (ν; T )] ≤ S

∥ν∥2∞ ΓS (Psampling ), |T |

where ΓS (Psampling ) :=

X T ∈2N

ps|T |−|S∩T | (n) Psampling (T )

2 .

Proof. Define the random variable X := ν(T )

(−1)s−|S∩T | ps|T |−|S∩T | (n) Psampling (T )

T ∼ Psampling .

Since T1 , . . . , T|T | are i.i.d., the corresponding variables Xi := ν(Ti )

(−1)s−|S∩Ti | ps|Ti |−|S∩Ti | (n) Psampling (Ti )

are i.i.d. as well, and ϕ̂p,MSR (ν; T ) = S

|T | 1 X Xi . |T | i=1

Using independence, we obtain 

 |T | X 1 V[ϕ̂p,MSR (ν; T )] = V Xi  S |T | i=1 =

|T | 1 X V[Xi ] |T |2 i=1

1 V[X]. |T |

(9)

We now expand the variance of X: V[X] = E[X 2 ] − E[X]2 . For the second moment, we compute X

E[X ] =

Psampling (T ) ν(T )

T ∈2N

ν(T )2

ps|T |−|S∩T | (n)

ps|T |−|S∩T | (n) Psampling (T ) 2 ,

Psampling (T )

T ∈2N

(10)

where the sign disappears since it is squared. For the first moment, E[X] =

Psampling (T ) ν(T )

(−1)s−|S∩T | ps|T |−|S∩T | (n) Psampling (T )

T ∈2N

ν(T ) (−1)s−|S∩T | ps|T |−|S∩T | (n)

T ∈2N

= ϕS (ν).

(11)

Substituting (10) and (11) into the variance expansion yields V[X] =

X T ∈2N

ν(T )

2 ps|T |−|S∩T | (n) Psampling (T )

− ϕS (ν)2 .

Combining this with (9) proves the exact variance identity. The upper bound follows from ϕS (ν)2 ≥ 0 and ν(T )2 ≤ ∥ν∥2∞ for all T ⊆ N . Corollary A.4 (Variance of MSR under proportional sampling). Under the assumptions of Theorem A.3, suppose the coalitions are sampled proportionally to the interaction weights, i.e. Psampling (T ) ∝ ps|T |−|S∩T | (n), Then V[ϕ̂p,MSR (ν; T )] ≤ S 19

for all T ⊆ N.

4s ∥ν∥2∞ . |T |

Proof. By Theorem A.3, V[ϕ̂p,MSR (ν; T )] ≤ S

∥ν∥2∞ ΓS (Psampling ). |T |

Under proportional sampling, Psampling (T ) =

ps|T |−|S∩T | (n) 2s

and hence ΓS (Psampling ) =

X ps|T |−|S∩T | (n) Psampling (T )

T ⊆N

Psampling (T )

ps|T |−|S∩T | (n)

T ⊆N

Psampling (T )

Psampling (T ) (2s )2

T ⊆N

= 4s

Psampling (T )

T ⊆N

= 4s . Substituting this into the general bound proves the claim. Corollary A.5 (Asymptotics of the leverage-sampling variance factor for SII). Suppose Psampling is given by leverage sampling, 1 , Psampling (T ) = (n + 1) |Tn | and let pst (n) denote the SII weights, pst (n) =

1 . (n − s + 1) n−s t

Then, for fixed interaction order s, ΓS (Psampling ) =

O(log n), s = 1, O(ns−1 ), s ≥ 2.

Proof. We rewrite ΓS (Psampling ) as a double sum over the overlap size r = |S ∩ T | and the outside size q = |T \ S|, then treat the cases s = 1 and s ≥ 2 separately. Step 1: Rewriting ΓS (Psampling ). Using the definition of ΓS (Psampling ) from Theorem A.3, together with the SII weights and leverage sampling, we obtain 2 X ps|T |−|S∩T | (n) ΓS (Psampling ) = Psampling (T ) T ⊆N X 1 n = · (n + 1) . 2 n−s |T | (n − s + 1)2 T ⊆N

|T \S|

We group coalitions T ⊆ N according to r := |S ∩ T |,

q := |T \ S|.

Then |T | = r + q, and for fixed (r, q) there are exactly s n−s r q 20

coalitions with these values. Hence s n−s X n+1 s X ΓS (Psampling ) = (n − s + 1)2 r=0 r q=0

n r+q n−s . q

Next, we rewrite the binomial ratio: n

n! q!(n − s − q)! r+q · n−s = (r + q)!(n − r − q)! (n − s)! q =

q! (n − s − q)! n! · · . (n − s)! (r + q)! (n − r − q)!

Using the rising factorial (a)k := a(a + 1) · · · (a + k − 1), this becomes

n (n − s + 1)s r+q . n−s = (q + 1) (n − s − q + 1)s−r r q

Therefore, ΓS (Psampling ) =

s n−s 1 (n + 1)(n − s + 1)s X s X . r (n − s + 1)2 (q + 1) (n − s − q + 1)s−r r q=0 r=0

Assume first that s = 1. Then r ∈ {0, 1}, so (12) becomes 1 n−1 1 n+1X 1 X ΓS (Psampling ) = . n r=0 r q=0 (q + 1)r (n − q)1−r

Step 2: The case s = 1.

We used (n − s + 1)s = (n)1 = n and (n − s + 1)2 = n2 when s = 1. For r = 0, n−1 X

n X 1 1 = = Hn , n−q j q=0 j=1

and similarly for r = 1, n−1 X

n X 1 1 = = Hn . q + 1 j=1 j q=0

Hence ΓS (Psampling ) = Step 3: The case s ≥ 2.

2(n + 1) Hn = O(log n). n

Now let s ≥ 2 be fixed. In (12), we bound the inner sum via

(q + 1)r ≥ (q + 1)r ,

(n − s − q + 1)s−r ≥ (n − s − q + 1)s−r ,

which yields n−s X

n−s X 1 1 ≤ . r (n − s − q + 1)s−r (q + 1) (n − s − q + 1) (q + 1) r s−r q=0 q=0

We distinguish two cases. Case 1: r = 0 or r = s. If r = 0, then n−s X

n−s+1 X 1 1 = = O(1), s (n − s − q + 1) js q=0 j=1

(12)

since the sum only becomes smaller as the exponent s increases, so we can upper bound it by the case s = 2, which we assume. The same argument applies to r = s, giving n−s X

1 = O(1). (q + 1)s q=0

Case 2: 1 ≤ r ≤ s − 1. In this range, both exponents are at least 1, and therefore 1 1 ≤ . r s−r (q + 1) (n − s − q + 1) (q + 1)(n − s − q + 1) Writing A := n − s, we get A A X 1 X 1 1 1 = + (q + 1)(A − q + 1) A + 2 q=0 q + 1 A − q + 1 q=0 log n 2HA+1 =O . = A+2 n Here we used 1 1 1 1 = + . (q + 1)(A − q + 1) A+2 q+1 A−q+1 Combining the two cases, we find that for every fixed r ∈ {0, . . . , s},   r = 0 or r = s, n−s O(1), X 1 = log n  (q + 1)r (n − s − q + 1)s−r , 1 ≤ r ≤ s − 1. O q=0 n Thus, the dominant contributions come from the boundary cases r = 0 and r = s, while all interior contributions are asymptotically smaller. Therefore s n−s X s X 1 = O(1). r (q + 1) (n − s − q + 1)s−r r r=0 q=0 By (12), ΓS (Psampling ) = O

(n + 1)(n − s + 1)s (n − s + 1)2

Finally, for fixed s, (n + 1)(n − s + 1)s = O(ns−1 ), (n − s + 1)2 and therefore

ΓS (Psampling ) = O(ns−1 ).

Proof of Theorem 3.3. By Theorem A.3, ∥ν∥2∞ ΓS (Psampling ). |T | Under leverage sampling and SII weights, Corollary A.5 yields O(log n), |S| = 1, ΓS (Psampling ) = O(n|S|−1 ), |S| ≥ 2. V[ϕ̂MSR (ν; T )] ≤ S

Substituting this into the general bound gives  ∥ν∥2∞ log n   O ,  |T | V[ϕ̂MSR (ν; T )] ≤ S  ∥ν∥2∞ n|S|−1  O , |T |

|S| = 1, |S| ≥ 2,

where the constants hidden in the O(·) notation depend only on |S|. This proves Theorem 3.3. 22

Lemma A.6 (Lower bound on ΓS for SII under leverage sampling). Suppose Psampling is leverage sampling and pst (n) are the SII weights. Then, for fixed interaction order s, Θ(log n), s = 1, ΓS (Psampling ) = Θ(ns−1 ), s ≥ 2. Proof. Recall from the proof of Corollary A.5 that ΓS (Psampling ) =

s n−s (n + 1)(n − s + 1)s X s X 1 . r (n − s + 1)2 (q + 1) (n − s − q + 1)s−r r r=0 q=0

Since every term of the double sum is non-negative, we may lower-bound it by retaining only the boundary term r = 0: n−s n−s+1 (n + 1)(n − s + 1)s X 1 (n + 1)(n − s + 1)s X 1 ΓS (Psampling ) ≥ = . (n − s + 1)2 (n − s − q + 1)s (n − s + 1)2 (j)s q=0 j=1

Case s = 1. Then (j)1 = j and

n X 1 j=1

= Hn = Θ(log n),

so ΓS (Psampling ) ≥ n+1 n Hn = Θ(log n). Pn−s+1 Case s ≥ 2. The sum j=1 1/(j)s converges to a positive constant as n → ∞ (its j = 1 term alone equals 1/s!), so it is Θ(1). Combined with (n − s + 1)s = Θ(ns ) and (n − s + 1)2 = Θ(n2 ) for fixed s, we obtain n · ns ΓS (Psampling ) = Θ = Θ(ns−1 ). n2 Corollary A.7 (Matching lower bound on MSR variance for SII under leverage sampling). Suppose coalitions are sampled i.i.d. according to leverage sampling, Psampling (T ) =

1 . (n + 1) |Tn |

Then there exists a value function ν such that  2  Θ ∥ν∥∞ log n , h i  |T | V ϕ̂MSR (ν; T ) = S ∥ν∥2∞ n|S|−1   Θ , |T |

|S| = 1, |S| ≥ 2.

Proof. By Theorem A.3,   2 s X p (n) 1 |T |−|S∩T |  ν(T )2 − ϕS (ν)2  . V ϕ̂MSR (ν; T ) = S |T | P (T ) sampling N h

T ∈2

Take ν ≡ 1, so ϕS (ν) = 0 for any |S| ≥ 1 by the dummy axiom. The variance then equals ΓS (Psampling )/|T | = ∥ν∥2∞ ΓS (Psampling )/|T |, and the claim follows from the Lemma A.6 above. Corollary A.8 (Variance of MSR under leverage sampling for BII). Suppose Psampling is given by leverage sampling, 1 , Psampling (T ) = (n + 1) |Tn | and let pst (n) denote the Banzhaf Interaction Index weights, pst (n) = 23

1 2 n−s

Then

n + 1 2n . ΓS (Psampling ) = n−s n 4

In particular,

√ ΓS (Psampling ) = Θ(4s n),

and therefore, by Theorem A.3, V[ϕ̂MSR (ν; T )] ≤ S

√ ∥ν∥2∞ ∥ν∥2∞ 4s n ΓS (Psampling ) = O . |T | |T |

In particular, for fixed interaction order s, V[ϕ̂MSR (ν; T )] = O S

√ ∥ν∥2∞ n . |T |

Proof. By Theorem A.3, V[ϕ̂MSR (ν; T )] ≤ S

∥ν∥2∞ ΓS (Psampling ), |T |

where ΓS (Psampling ) :=

X ps|T |−|S∩T | (n) Psampling (T )

T ⊆N

2 .

For the Banzhaf Interaction Index, the weights are constant in the coalition size, namely 1

pst (n) =

2 n−s

Hence 1 1 4 n−s Psampling (T ) T ⊆N 1 X n = n−s (n + 1) . |T | 4

ΓS (Psampling ) =

T ⊆N

We now group coalitions T ⊆ N by their size t := |T |. For each t ∈ {0, . . . , n}, there are exactly n t coalitions of size t. Therefore n X n X n n = |T | t t t=0 T ⊆N n 2 X n = . t t=0 Using Vandermonde’s identity, n 2 X n t=0

2n . n

Substituting this into the previous display yields the exact formula n + 1 2n ΓS (Psampling ) = n−s . 4 n To obtain the asymptotic form, we use the central binomial coefficient estimate n 2n 4 =Θ √ . n n 24

Hence

√ n + 1 4n n + 1 2n =Θ ·√ = Θ(4s n). ΓS (Psampling ) = n−s n−s n 4 4 n

Finally, substituting this into the general variance bound from Theorem A.3 gives √ ∥ν∥2∞ ∥ν∥2∞ 4s n MSR V[ϕ̂S (ν; T )] ≤ ΓS (Psampling ) = O . |T | |T | For fixed interaction order s, the factor 4s is absorbed into the constant, yielding √ ∥ν∥2∞ n V[ϕ̂MSR (ν; T )] = O . S |T | This proves the claim.

A.3

Closed Forms for Proposition 3.2

A.3.1

Shapley Value and Shapley Interaction Index

Proposition A.9. The Shapley Value and the Shapley Interaction Index yield the closed form λ(|Lj |, |Rj |, |Lj ∩ S|, |S|) = (−1)u

1 , (a + b) a+b a

where u := |Lj ∩ S|,

a := |Rj | − |Rj ∩ S|,

b := |Lj | − |Lj ∩ S|.

Proof. This is exactly Proposition 1 in Zern et al. [65], specialized to our notation. A.3.2

Banzhaf Value and Banzhaf Interaction Index

Proposition A.10. The Banzhaf Value and the Banzhaf Interaction Index yield the closed form 1 λ(ℓ, r, u, s) = (−1)u ℓ+r−s . 2 Proof. Starting from Proposition 3.2 and using the Möbius weights for the Banzhaf interaction index from Table 1, we obtain λ(ℓ, r, u, s) =

ℓ−u X ℓ−u 1 (−1)i+u . i+u+r−s i 2 i=0

Define k0 := u + r − s,

m := ℓ − u.

Then m X

m 1 λ(ℓ, r, u, s) = (−1) i+k0 i 2 i=0 m X u 1 i m 1 = (−1) k0 (−1) i 2i 2 i=0 i m 1 1 X m − = (−1)u k0 2 i=0 i 2 i m X m 1 u 1 − = (−1) k0 1m−i . 2 i=0 i 2 i+u

By the binomial theorem, i m m m X 1 1 m 1 m−i 1 = 1− = . − i 2 2 2 i=0 Hence 1 λ(ℓ, r, u, s) = (−1) k0 2 u

m 1 1 = (−1)u k0 +m . 2 2

Substituting the definitions of k0 and m gives 1 λ(ℓ, r, u, s) = (−1)u ℓ+r−s . 2

A.3.3

Chaining Value and Chaining Interaction Index

Proposition A.11. The Chaining Value and the Chaining Interaction Index yield the closed form λ(ℓ, r, u, s) = s(−1)u B(u + r, ℓ − u + 1), where

Z 1 B(z1 , z2 ) :=

xz1 −1 (1 − x)z2 −1 dx

denotes the Beta function. Proof. For the Chaining Interaction Index, the Möbius weights satisfy qts (n) = st [14]. Therefore, Proposition 3.2 yields ℓ−u X ℓ−u s λ(ℓ, r, u, s) = (−1)i+u . i i + u +r i=0 Factor out the constant terms: u

λ(ℓ, r, u, s) = (−1) s

ℓ−u X

(−1)

i=0

ℓ−u 1 . i+u+r i

Now define m := ℓ − u,

k0 := u + r, and use the identity 1 = i + k0

Z 1

xi+k0 −1 dx.

Then m X

Z 1 m xi+k0 −1 dx i 0 i=0 Z 1X m m i k0 −1 xx dx = (−1)u s (−1)i i 0 i=0 ! Z 1 X m m u i m−i = (−1) s (−x) 1 xk0 −1 dx i 0 i=0 Z 1 = (−1)u s (1 − x)m xk0 −1 dx

λ(ℓ, r, u, s) = (−1)u s

(−1)i

= (−1)u s B(k0 , m + 1). Substituting back k0 = u + r and m = ℓ − u gives λ(ℓ, r, u, s) = (−1)u s B(u + r, ℓ − u + 1).

A.3.4

Faithful Banzhaf Interaction Index (FBII)

Proposition A.12. For the Faithful Banzhaf Interaction Index (FBII), Proposition 3.2 yields the closed form X ϕFBII (ν̂tree ) = cj λ |Lj |, |Rj |, |S ∩ Lj |, |S| , S j∈L S⊆Lj ∪Rj

where λ(ℓ, r, u, s) = (−1)u 1[Rj ⊆ S] +

ℓ−u X

u+i+k−s −(r+i+u−s)

(−1)

i=max(0,k−r−u+1)

and k denotes the maximal interaction order to be computed. 27

ℓ−u i

r+i+u−s−1 . k−s

Proof. We begin with the Möbius representation of FBII [58]: X 1 |T |−s |T | − s − 1 FBII k−s mT (ν). ϕS (ν) = mS (ν) + (−1) 2 k−s T ⊇S |T |>k

Applying Lemma A.1 to the tree representation yields   X X  ϕFBII (−1)|T | 1[T ∪Rj ,N ]  (ν̂tree ) = cj ϕFBII S S T ⊆Lj

j∈L

(−1)|T | ϕFBII (1[T ∪Rj ,N ] ). S

X T ⊆Lj

We now analyze a fixed leaf j. For notational brevity, write r := |Rj |,

ℓ := |Lj |,

u := |S ∩ Lj |,

s := |S|.

Using the Möbius representation above, we split the expression into two parts: X (−1)|T | ϕFBII (1[T ∪Rj ,N ] ) S T ⊆Lj

(−1)|T | mS (1[Rj ∪T,N ] )

T ⊆Lj

+ (−1)

k−s

|T |

(−1)

T ⊆Lj

Step 1: The Möbius term.

X 1 |V |−s |V | − s − 1 mV (1[Rj ∪T,N ] ). k−s 2

V ⊇S |V |>k

Consider X

(−1)|T | mS (1[Rj ∪T,N ] ).

T ⊆Lj

By Lemma A.2 with B = N , we have mS (1[Rj ∪T,N ] ) = 1

⇐⇒

Rj ∪ T = S,

and otherwise it is zero. Moreover, only interactions with S ⊆ Lj ∪ Rj can contribute. Under this condition, we must have Rj ⊆ S, hence X X (−1)|T | mS (1[Rj ∪T,N ] ) = (−1)|T | 1[Rj ∪ T = S] T ⊆Lj

T ⊆Lj

= (−1)u 1[Rj ⊆ S]. Step 2: The faithful tail term.

Now consider X X 1 |V |−s |V | − s − 1 (−1)k−s (−1)|T | mV (1[Rj ∪T,N ] ) 2 k−s T ⊆Lj

= (−1)k−s

V ⊇S |V |>k

X 1 |V |−s |V | − s − 1 X V ⊇S |V |>k

k−s

(−1)|T | mV (1[Rj ∪T,N ] ).

T ⊆Lj

Again by Lemma A.2 with B = N , mV (1[Rj ∪T,N ] ) = 1

⇐⇒

Rj ∪ T = V.

Since the outer sum only contains V with |V | > k, only subsets T satisfying |Rj ∪ T | > k contribute, i.e. |T | > k − r. 28

Furthermore, we must have S ⊆ Rj ∪ T , which is equivalent to S ∩ Lj ⊆ T . Therefore, the tail term becomes r+|T |−s X 1 r + |T | − s − 1 (−1)|T |+k−s . 2 k−s T ⊆S∩Lj |T |>k−r

Write SL := Lj ∩ S, SR ⊆ Lj \ SL , T = SL ∪ S R . Then |T | = |SL | + |SR |, and summing over all possible SR gives r+|SR |+u−s X r + |SR | + u − s − 1 1 . (−1)|SR |+u+k−s 2 k−s SR ⊆Lj \SL |SR |>k−r−u

Grouping terms by i := |SR |, there are ℓ−u X

ℓ−u i

such subsets. Hence, the tail term simplifies to r+i+u−s 1 r+i+u−s−1 ℓ−u u+i+k−s (−1) . 2 k−s i

i=k−r−u+1

Step 3: Combine both parts. When k − r − u + 1 ≤ 0, the constraint |T | > k − r is satisfied by every T ⊆ S ∩ Lj , so the lower summation index collapses to 0; as such, the lower index can be written as max(0, k − r − u + 1) as in the proposition statement. Combining the Möbius term and the faithful tail term, summing over all leaves, and incorporating the condition S ⊆ Lj ∪ Rj , we obtain X ϕFBII (ν̂tree ) = cj · λ |Lj |, |Rj |, |S ∩ Lj |, |S| , S j∈L S⊆Lj ∪Rj

where λ(|Lj |, |Rj |, |S ∩ Lj |, |S|) =(−1)|S∩Lj | 1[Rj ⊆ S] ℓ−u X

u+i+k−s

(−1)

i=max(0, k−r−u+1)

r+i+u−s 1 r+i+u−s−1 ℓ−u 2 k−s i

yields the claimed formula. A.3.5

Faithful Shapley Interaction Index (FSII)

Proposition A.13. For the Faithful Shapley Interaction Index (FSII), Proposition 3.2 yields the closed form X ϕFSII (ν̂tree ) = cj λ |Lj |, |Rj |, |S ∩ Lj |, |S| , S j∈L S⊆Lj ∪Rj

where λ(|Lj |, |Rj |, |S ∩ Lj |, |S|) =(−1)|S∩Lj | 1[Rj ⊆ S] +

ℓ−u X

u+i+k−s

(−1)

i=max(0,k−r−u+1)

Proof. We use the Möbius representation of FSII [58]: X s k FSII k−s ϕS (ν) = mS (ν) + (−1) k+s s

r+i+u−1 k ℓ−u s k r+u+i+k−1 k+s s i k+s

T ⊇S |T |>k

|T |−1 k mT (ν). |T |+k−1 k+s

Applying Lemma A.1 to the tree representation gives X X ϕFSII (ν̂tree ) = cj (−1)|T | ϕFSII (1[T ∪Rj ,N ] ). S S j∈L

T ⊆Lj

Fix a leaf j, and write r := |Rj |,

ℓ := |Lj |,

u := |S ∩ Lj |,

s := |S|.

The first term is identical to the corresponding term in the proof of Proposition A.12, since it only depends on the Möbius term mS . Hence it contributes (−1)u 1[Rj ⊆ S]. For the second term, the same Möbius support argument as in the FBII proof shows that only subsets T ⊆ Lj with |T | > k − r contribute, and the outer sum reduces to the case V = Rj ∪ T . Again, we must have S ⊆ Rj ∪ T , which is equivalent to S ∩ Lj ⊆ T . Therefore, the faithful tail term equals X r+|T |−1 s k k−s |T | k (−1) (−1) . r+|T |+k−1 k+s s T ⊆S∩Lj |T |>k−r

k+s

Now write SL := Lj ∩ S, SR ⊆ Lj \ SL , T = SL ∪ S R . Then |T | = |SL | + |SR |, and grouping subsets by i := |SR | yields r+i+u−1 ℓ−u X k s u+i ℓ − u k−s k (−1) (−1) . r+u+i+k−1 i k+s s k+s i=k−r−u+1

When k − r − u + 1 ≤ 0, the constraint |T | > k − r is satisfied by every T ⊆ S ∩ Lj , so the lower summation index collapses to 0; as such, the lower index can be written as max(0, k − r − u + 1) as in the proposition statement. Combining this faithful tail term with the Möbius term and summing over all leaves gives X (ν̂tree ) = cj · λ |Lj |, |Rj |, |S ∩ Lj |, |S| ϕFSII S j∈L S⊆Lj ∪Rj

where λ(|Lj |, |Rj |, |S ∩ Lj |, |S|) =(−1)|S∩Lj | 1[Rj ⊆ S] +

ℓ−u X

u+i+k−s

(−1)

i=max(0,k−r−u+1)

which proves the claim.

r+i+u−1 s k ℓ−u k r+u+i+k−1 i k+s s k+s

Table 2: Tree-extraction algorithms. Parenthesized check marks indicate pairwise-only.

Algorithm Interventional extraction TreeSHAP (Lundberg et al. [37]) TreeSHAP (Zern et al. [65]) Woodelf [46] Ours (Algorithm 2)

Values

Interactions

Faithful

SII

BII

CII

FSII

FBII

✓ ✓ ✓ ✓

× × ✓ ✓

× × × ✓

× ✓ (✓) ✓

× × (✓) ✓

× × × ✓

Generalization of Interventional TreeSHAP

Central to ProxySHAP is the ability to efficiently extract exact cardinal-probabilistic Algorithm 2 Tree Interaction Extraction interaction indices from tree-based proxies. Building on interventional TreeSHAP [65], Require: Tree-based model ν̂treep, interaction S ⊆ N Extracted interaction ϕS we extract the indices of ν̂ for a target set Ensure: p N 1: ϕ ← 0 ▷ initialize S ⊆ 2 in O(nnodes |S|) time. Table 2 S summarizes the supported indices and com- 2: for each leaf j ∈ L do pares our generalized interventional Tree- 3: (Lj , Rj ) ← PATH(j) 4: cj ← L EAF VALUE(j) SHAP with existing tree-based extraction 5: if S ⊆ Lj ∪ Rj then algorithms. 6: ϕpS ← ϕpS + λ(|Lj |, |Rj |, |S ∩ Lj |, |S|) cj First, consider a single decision tree with 7: end if inputs as binary-encoded subsets T ⊆ N . 8: end for p Each leaf j ∈ L corresponds to a path of 9: return ϕS node splits, where each split on feature i ∈ N determines whether i ∈ T (right branch) or i ∈ / T (left branch). An input T reaches leaf j if and only if along the path to j: (i) T ⊇ Rj , meaning it contains all features that split to the right (Rj ), and (ii) T ⊆ N \ Lj , meaning it contains none of the features that split to the left (Lj ). The tree-based proxy is then given by the piecewise constant leaf predictions cj ∈ R as X ν̂tree (T ) := cj · 1[Rj ⊆ T ⊆ N \ Lj ]. (13) j∈L

Zern et al. [65] exploited linearity in Eq. (8) and computed the Shapley interactions for each 1[Rj ⊆ T ⊆ N \ Lj ], based on the Möbius representation of 1[Rj ⊆ T ⊆ N \ Lj ]. In a similar spirit, we can compute the general cardinal-probabilistic interaction indices for 1[Rj ⊆ T ⊆ N \ Lj ] via the Möbius representation, and then use linearity to obtain the interaction indices for ν̂tree . This yields Proposition 3.2, which gives a closed-form solution for any cardinal-probabilistic interaction index of 1[Rj ⊆ T ⊆ N \ Lj ]. Then, by using the closed forms of the Möbius weights qts for specific cardinal-probabilistic interaction indices, we can obtain closed-form solutions for the corresponding interventional TreeSHAP interactions, as shown in Propositions A.11, A.12, and A.13. The overall procedure is summarized in Algorithm 2. Note that, due to Corollary 1 in Zern et al. [65], Proposition 3.2 also enables exact computation of interactions for piecewise linear regression trees [65]. Given an interaction S, the algorithm iterates over all leaves j and extracts the corresponding path information (Lj , Rj ) and leaf value cj . Then, it updates the interaction value ϕpS by adding the contribution from leaf j, which is computed using the closed-form solution λ(|Lj |, |Rj |, |S ∩Lj |, |S|) from Proposition 3.2 multiplied by the leaf value cj . Finally, the algorithm returns the extracted interaction ϕpS . The lookups PATH and L EAF VALUE can be pre-computed for all leaves and stored in a hash map for efficient access, resulting in an overall time complexity of O(nnodes ) for extracting a single interaction S.

Experimental Details

C.1

Datasets

Table 3: Summary of datasets used in the experiments. “Players” denotes the number of features or components considered in the corresponding game. Dataset

Task

Model(s)

Players Source

License

Vision and language datasets [42] ViT3by3 Image classification Language (IMDB) Classification ResNet18-SP Image classification ViT4by4 Image classification

ViT-B DistilBERT ResNet18 ViT-B

9 14 14 16

shapiq shapiq / HuggingFace shapiq shapiq

Public Domain Public Domain Public Domain Public Domain

Tabular datasets [42, 55] Housing Bike Forest Fires AdultCensus Estate Hepatitis Thyroid Mushroom Cancer Ionosphere Soybean CG60 IL60 NHANES Crime

Regression Regression Regression Classification Regression Classification Classification Classification Classification Classification Classification Regression (synthetic) Regression (synthetic) Survival Regression

TabPFN TabPFN TabPFN TabPFN TabPFN LightGBM LightGBM LightGBM XGBoost LightGBM LightGBM XGBoost XGBoost XGBoost XGBoost

8 12 13 14 15 19 21 22 30 33 35 60 60 79 101

scikit-learn OpenML (42712) UCI OpenML (1590) UCI UCI (46) UCI (102) UCI (73) scikit-learn UCI (52) UCI (90) SHAP SHAP SHAP SHAP

Public Domain Public Domain CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 MIT MIT Public Domain CC-BY 4.0

TabArena datasets [13] Online Shoppers Churn Credit-G Airline Satisfaction JM1 Credit Card Default HELOC Coupon Recommendation Marketing Campaign Hazelnut Students Dropout Anneal QSAR Biodeg Diabetes 130-US Splice Bankruptcy Superconductivity COIL 2000 NATICUSdroid Taiwanese Bankruptcy MIC APS Failure KDD Cup 09 QSAR TID11 HIVA Agnostic Bioresponse

Classification Classification Classification Classification Classification Classification Classification Classification Classification Classification Classification Classification Classification Classification Classification Classification Regression Classification Classification Classification Classification Classification Classification Classification Classification Classification

LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM LightGBM

17 19 20 21 21 23 23 24 25 30 36 38 41 47 60 64 81 85 86 94 111 170 212 1024 1617 1776

OpenML (46947) OpenML (46915) OpenML (46918) OpenML (46920) OpenML (46979) OpenML (46919) OpenML (46932) OpenML (46937) OpenML (46940) OpenML (46930) OpenML (46960) OpenML (46906) OpenML (46952) OpenML (46922) OpenML (46958) OpenML (46950) OpenML (46961) OpenML (46916) OpenML (46969) OpenML (46962) OpenML (46980) OpenML (46908) OpenML (46939) OpenML (46953) OpenML (46933) OpenML (46912)

CC-BY 4.0 MIT CC-BY 4.0 CC0 Public Domain CC-BY 4.0 Public Domain CC-BY 4.0 Public Domain CC-BY-SA CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 CC-BY 4.0 Public Domain Public Domain Public Domain Public Domain

Graph datasets [44] Benzene Mutagenicity

Classification Classification

Graph Neural Network Graph Neural Network

25 35

Sanchez-Lengeling et al. [50] CC0 1.0 Universal Kazius et al. [28] CC0 1.0 Universal

We build an interventional game for each tabular dataset with more than 16 features, based on the underlying trained XGBoost [8] or LightGBM [29]. The interventional game is based on a point to explain xe and background samples B = {b1 , . . . , bnbg }. Given the coalition S we construct new points e x [j] if j ∈ S zi [j] = bi [j] otherwise 32

where we access the feature j via x[j]. The game value of S is then obtained by averaging each value from z1 , . . . , znbg , i.e. ν

(S) =

nbg 1 X f (zi ) nbg i=1

where we denote the underlying tree-based models as f . In total, we use nbg = 50 background samples drawn from the training dataset. The exact values are calculated using Algorithm 2. In the following, we provide concise descriptions of each domain; an overview of all datasets is presented in Table 3. Vision and Language For Vision and Language tasks, we directly use the pre-computed games provided by shapiq [42], which are based on pretrained models and standard datasets in the respective domains. The language games are based on DistilBERT [51] fine-tuned on the IMDB movie reviews dataset [32, 38], while the image classification games use Vision Transformer and ResNet18 pretrained on ImageNet. The language games aim to predict the sentiment of movie reviews, while the image classification games aim to predict the class of input images. Tabular Datasets We consider a variety of tabular datasets [13, 42, 55, 63]. For all tabular datasets with fewer than 16 features, we train TabPFN-2.5 [20, 23], as this feature count still allows for the exact computation of the probabilistic indices. On all other tabular datasets, we either train an XGBoost model [8] or a LightGBM model [29], with default hyperparameters to obtain the interventional game. This makes our evaluation more comprehensive and enables us to investigate the influence of the underlying model on the interactions we obtain. Graph Datasets For graph datasets, we follow the setup of Muschalik et al. [44] and use their proposed GraphSHAP-IQ method to compute exact Shapley interactions for graph neural networks. The M UTAGENICITY dataset [28] consists of 1,768 molecular graphs, categorized into two classes according to their mutagenic properties, specifically their effect on the Gram-negative bacterium S. typhimurium [44]. The B ENZENE dataset [50] consists of 12,000 molecular graphs, each labeled according to whether it contains a benzene ring. We use the pretrained models from Muschalik et al. [44], which have 2 GNN layers and a hidden dimension of 32. C.2

Computational Resources

Approximation-quality experiments and hyperparameter optimization were conducted on a compute cluster with 96 Intel Xeon Platinum 8480+ (Sapphire Rapids) CPUs and 512 GB of RAM, totaling 3 weeks of runtime. TabPFN-based games were precomputed using NVIDIA V100 GPUs in parallel, enabling exhaustive evaluation of the value function for datasets with n ≤ 16 features. CLIP experiments were run on a cluster consisting of NVIDIA A100 GPUs. C.3

Hyperparameter Optimization

To obtain high-quality proxy models, we tune the XGBoost hyperparameters using Bayesian optimization (BO), since the approximation quality of ProxySHAP depends directly on the fitted proxy. Compared with grid or random search, BO explores the predefined search space more adaptively and can therefore identify strong configurations with fewer evaluations. We use the BO implementation of Lindauer et al. [34]. The integer-valued hyperparameters are the number of estimators ([500, 2000]), maximum tree depth ([2, 8]), and minimum child weight ([1, 20]). The continuous hyperparameters are the subsampling rate ([0.6, 1.0]), column subsampling rate ([0.6, 1.0]), learning rate ([0.001, 0.3]), and ℓ2 regularization strength ([0.001, 50]). We run BO for 200 iterations and evaluate each configuration using 5-fold cross-validation. After optimization, the final proxy model is retrained on the full set of sampled coalitions. HPO runtime varies substantially across datasets, depending on the number of sampled coalitions and the number of features. Expanding the search space may further improve approximation quality, but would also increase the computational cost. 33

C.4

Baselines

We briefly describe the baseline methods used for comparison in our experiments. All baselines are based on the implementation of the shapiq library [42]. PermutationSamplingSII. PermutationSamplingSII is a Monte Carlo estimator for the Shapley Interaction Index (SII), extending classical permutation sampling for Shapley values [6] to higherorder interactions [15, 58]. The method estimates interactions by averaging marginal contributions across random feature orderings. It is applicable exclusively to SII. SVARM-IQ. SVARM-IQ (Stratified Variable Approximation for Interaction Quantification) [31] is an efficient estimator for cardinal probabilistic interaction indices based on stratified sampling of marginal contributions. It builds on the MSR framework [7] and reduces variance by stratifying coalitions by cardinality. SHAP-IQ. SHAP-IQ [15] provides a unified framework for approximating Shapley interactions of arbitrary order by extending unbiased KernelSHAP to interaction indices. It supports all cardinal probabilistic interaction indices. KernelSHAP-IQ. KernelSHAP-IQ [16] generalizes KernelSHAP to higher-order interactions by solving a weighted least-squares optimization problem with interaction-specific kernels. The method supports the estimation of both Shapley and Banzhaf interactions but suffers from scalability limitations due to the combinatorial growth in interaction terms. ProxySPEX. ProxySPEX [4] is an inference-efficient method for estimating sparse Shapley and Banzhaf interactions, improving upon SPEX [27]. By learning a sparse proxy model, ProxySPEX significantly reduces the number of required model evaluations and scales to settings with thousands of features.

Additional Approximation Results

D.1

Additional Experiments with FIxLIP

Following Baniecki et al. [2], we estimate model explanations with the faithful Banzhaf interaction index (FBII) of second-order and assess approximation quality using the area between the insertion/deletion curves (AID) and R2 metrics. We rely on the default experimental setup, restricting pairwise interactions to the top 72 clique for ViT-B/16, selected via a greedy increase-in-value P strategy. Given estimated interactions ϕFBII , we sample m = 1000 coalitions and define ν̂(T ) = S⊆T ϕFBII S . The R2 score is computed as ∥ν̂ − ν∥2 R2 = 1 − , ∥ν∥2 where ν denotes the sampled game values obtained from the model outputs. AID score measures the average increase/decrease in the model’s prediction when sequentially inserting/deleting important features based on their ranking as measured with an explanation [21, 66]. Evaluating faithfulness of the game. We measure R2 on explanations for 30 image–text inputs from MS COCO, with budgets ranging from 102 to 104 . Figure 8 shows that ProxySHAP improves the original approximation in low-budget regimes, improves the R2 metric more rapidly, and requires substantially fewer model evaluations than ProxySPEX. It effectively solves the challenge of approximating the n ≪ p regression matrix using a linear-based model, as reported in the original work. Ablation on approximating the cross-modal FIxLIP estimator. We run additional ablations with another cross-modal estimator proposed in [2], which is more sample-efficient. The standard estimator samples image–text coalitions jointly, i.e., each CLIP call yields a single game evaluation. The cross-modal estimator samples image and text coalitions independently and evaluates the model on all pairwise combinations, yielding more game evaluations for the same CLIP-call budget. Table 4 summarizes the rough relationship between CLIP calls and the resulting number of game evaluations, which varies with vision model size and input text length. Figure 9 reports R2 approximation performance for ProxySHAP on the FIxLIP game, which remains useful in the low-budget regimes, especially for the larger ViT-16 game.

Figure 8: Faithfulness R2 for explaining CLIP (ViT-16) on the MS COCO dataset with ProxySHAP, ProxySPEX, and the FIxLIP baseline. D.2

XGBoost Default for Large Player Counts

When games involve many features, hyperparameter optimization (HPO) often selects XGBoost proxies with many shallow trees. In particular, the selected configurations often use approximately 2,000 trees together with a small maximum depth. We use this observation to define an HPOinformed default configuration, denoted by ProxySHAP (XGBoost+HPO-Informed). Table 5 summarizes the differences between the standard XGBoost configuration used in ProxySHAP and the HPO-informed configuration. 35

Table 5: XGBoost proxy configurations. Hyperparameter Default HPO-informed nestimators max_depth learning_rate reg_lambda

100 6 0.3 1

2,000 3 0.05 5

Table 4: Relationship between CLIP calls and the resulting number of game evaluations under normal and cross-modal approximation. CLIP model

CLIP calls

Approximate Game Evaluations

Crossmodal Game Evaluations

ViT-B/16

100 200 500 1 000 2 000 5 000 10 000

2 869 11 279 69 653 278 522 1 069 905 6 507 023 24 062 727

ViT-B/32

100 200 500 1 000 2 000 5 000 10 000

790 1 713 6 834 6 834 103 252 593 381 2 645 307

Figure 9: Ablation on approximating the cross-modal FIxLIP estimator. Faithfulness R2 for explaining two CLIP variants on MS COCO with ProxySHAP and the FIxLIP baseline. Motivated by this observation, we evaluate ProxySHAP (XGBoost+HPO-Informed) as an alternative default proxy for large-scale games. The results show that this configuration improves approximation quality in low-budget regimes and for games with many players. As illustrated in Figure 10, the HPO-informed configuration consistently outperforms the standard XGBoost default at low budgets. For moderate feature counts, however, its advantage decreases as the budget increases, and the standard configuration eventually becomes competitive or superior. For datasets with more than 1,000 features, ProxySHAP (XGBoost+HPO-Informed) significantly outperforms the standard default across all considered budgets. This is the case, for example, on H IVA AGNOSTIC and B IORESPONSE, which contain 1,617 and 1,776 features, respectively. These results further highlight the importance of proxy hyperparameters for ProxySHAP, especially in 36

10 1

10 3

IL60 (d = 60)

100

10 2

Relative MSE ± SEM

CG60 (d = 60) 101

NHANES (d = 79)

100

10 1

10 2

order 2

Cancer (d = 30)

100

10 2

10 4

10 3

10 3 102

100

103

104

102

Crime (d = 101)

103

104

10 3 102

QsarTid11 (n = 1024)

10 1

103

104

102

HivaAgnostic (n = 1617)

103

104

Bioresponse (n = 1776)

order 2

10 1 10 2

10 3 102

103

104

10 1 103

104

Model Evaluations ProxySHAP (XGBoost) [our] ProxySHAP (XGBoost, MSR) [our]

ProxySHAP (XGBoost+HPO-Informed) [our] ProxySHAP (XGBoost+HPO-Informed, MSR) [our]

ProxySHAP (XGBoost+HPO) [our] ProxySHAP (XGBoost+HPO, MSR) [our]

Figure 10: Approximation quality of two different XGBoost defaults. We show that using 2000 trees with a maximum depth of 3 improves estimation quality in low- to medium-budget regimes. low-budget regimes and for games with many players, where the standard XGBoost default may be insufficient to capture the relevant interaction structure. D.3

Runtime

We evaluate runtime by translating model evaluations into wall-clock time using fixed per-evaluation costs of 0 ms, 1 ms, 10 ms, and 100 ms. These regimes capture increasingly expensive inference settings, from highly optimized models to large-scale neural networks. Figure 11 reports the resulting runtimes for second- and third-order interaction estimation. Figure 11 reports approximation quality together with runtime, ranging from zero model-evaluation cost (top row) to 100 ms per model call. We find that the linear proxy incurs higher computational overhead than the tree-based proxy, especially for higher-order interactions, due to its polynomial scaling in the number of interaction terms. It only outperforms the tree-based proxy in low-dimensional pairwise settings, such as TabPFN on Estate. ProxySHAP is faster than ProxySPEX when model-inference costs are ignored. As model evaluations increasingly dominate the runtime, this difference becomes less pronounced. We observe a similar pattern for MSR adjustment: its overhead grows with the interaction order and number of players, but becomes less visible as the cost of model calls increases. Overall, ProxySHAP remains an efficient estimator for Shapley and Banzhaf interactions, requiring less computation than current proxy-based baselines, most notably ProxySPEX.

100

10 1

10 2

10 3 10 4

GNN on Mutagenicity (n = 35)

10 3 10 3 10 2 10 1 100

101

DistilBERT on IMDB (n = 14)

LGBM on MarketingCamp (n = 25)

LGBM on Kddcup09 (n = 212)

100

10 1

10 2

10 3

10 4 10 3 10 2 10 1 100 101 100

100

10 3

10 2

100

10 1

10 2 10 1 100

LGBM on Splice (n = 60)

100

101

102

103

102

103

LGBM on Coil2000 (n = 85)

100

10 1

10 2

10 3

ViT16 on ImageNet (n = 16)

order 2

TabPFN on Estate (n = 15)

10 1

10 3 10 2 10 1 100

101

10 1

10 2

10 4 10 3 10 2 10 1 100

order 3

Relative MSE ± SEM

100

101

102

10 2 10 1

100

102

101

100

10 1

101

Total Runtime (s; without Model call time) 100

10 1

10 2

10 3 10 4

GNN on Mutagenicity (n = 35)

10 3 10 1

100

101

10 1

DistilBERT on IMDB (n = 14)

100

10 1

10 2

10 3

101

LGBM on MarketingCamp (n = 25)

LGBM on Kddcup09 (n = 212)

100

10 1

101

LGBM on Splice (n = 60)

100

101

102

103

100

101

102

103

LGBM on Coil2000 (n = 85)

100

10 1

10 2

10 3

ViT16 on ImageNet (n = 16)

order 2

TabPFN on Estate (n = 15)

10 1

100

101

10 1

10 2

10 4 10 1

order 3

Relative MSE ± SEM

100

10 1

102

101

100

10 1

102

101

10 1

Total Runtime (s; 1ms per Model call) 100

10 1

10 2

10 3 10 4

GNN on Mutagenicity (n = 35)

10 3 100

101

102

DistilBERT on IMDB (n = 14)

100

101

10 1

10 2

10 3

102

LGBM on MarketingCamp (n = 25)

LGBM on Kddcup09 (n = 212)

100

102

101

LGBM on Splice (n = 60)

100

102

103

102

103

LGBM on Coil2000 (n = 85)

100

10 1

10 2

10 3

ViT16 on ImageNet (n = 16)

order 2

TabPFN on Estate (n = 15)

10 1

101

102

10 1

10 2

10 4 100

order 3

Relative MSE ± SEM

100

101

102

100

102

101

103

100

101

Total Runtime (s; 10ms per Model call) 100

10 1

10 2

10 3 10 4

101

102

103

101

100

102

103

10 1

10 2

10 3

LGBM on MarketingCamp (n = 25)

LGBM on Kddcup09 (n = 212)

100

101

102

103

LGBM on Splice (n = 60)

100

102

103

LGBM on Coil2000 (n = 85)

100

10 1

10 2

10 3

order 2 order 3

GNN on Mutagenicity (n = 35)

10 3 DistilBERT on IMDB (n = 14)

10 3

ViT16 on ImageNet (n = 16)

order 2

TabPFN on Estate (n = 15)

10 1

102

103

10 1

10 2

10 4 101

order 3

Relative MSE ± SEM

100

101

102

103

101

102

Total Runtime (s; 100ms per Model call) ProxySHAP (XGBoost) [our] ProxySHAP (Linear) [our] ProxySHAP (XGBoost, MSR) [our] ProxySHAP (Linear, MSR) [our]

103

101

KernelSHAPIQ ProxySPEX (XGBoost)

102

103

SHAPIQ SVARMIQ PermutationSamplingSII

Figure 11: Approximation quality as a function of runtime for second- and third-order interaction estimation across different per-evaluation cost regimes.

D.4

Ablation Details

MSE

We further investigate the effect of the residProxySHAP (XGBoost, MSR) ProxySHAP (XGBoost, MSR) ual approximator and sampling weights used 0.06 0.06 in the adjustment step. Specifically, we 0.05 0.05 compare SHAP-IQ [15] and KernelSHAP-IQ 0.04 0.04 [16] as model-agnostic residual approxima0.03 0.03 tors. We also compare leverage weights, as 0.02 0.02 used in LeverageSHAP [45], with KernelSHAP0.01 0.01 IQ weights [16]. As underlying games, we 0.00 0.00 default leverage kernelshapiq shapiq svarmiq use V I T4 BY 4PATCHES, B IKE S HARING L O Sampling Weight Residual Approximator CAL XAI, C ALIFORNIA H OUSING L OCAL XAI, C ORRGROUPS 60L OCAL XAI, and C OMMUNI - Figure 12: Ablations of sampling weights and TIES A ND C RIME L OCAL XAI; details on these residual approximators for ProxySHAP. datasets are provided in Section C.1. For each game, we approximate second-order Shapley interaction indices so that the comparison directly reflects the effect on interaction estimation. As shown in Figure 12, neither the choice of residual approximator nor the choice of sampling weights has a clear systematic effect on approximation quality for these games. D.5

Fourier Extraction vs. Interventional Extraction

Relative MSE ± SEM

Heloc (n = 23)

CG60 (n = 60)

Coil2000 (n = 85)

100

100 100

10 1

10 2

10 1

10 2

10 3 10 4

order 2 102

10 2 103

ProxySHAP (XGBoost@Depth2) ProxySHAP (XGBoost@Depth4)

104

order 2 102

10 3 103

Model Evaluations

ProxySHAP (XGBoost@Depth6) ProxySHAP (XGBoost@Depth8)

104

order 2 102

ProxySPEX (XGBoost@Depth2) ProxySPEX (XGBoost@Depth4)

103

104

ProxySPEX (XGBoost@Depth6) ProxySPEX (XGBoost@Depth8)

Figure 13: Approximation quality (Relative MSE) of ProxySHAP and ProxySPEX using different maximum tree depth options across small, medium, and large player domains. Our method relies on the ability to efficiently extract exact cardinal-probabilistic interaction indices from the underlying tree-based model. We extend interventional TreeSHAP by Zern et al. [65] to extract the exact cardinal-probabilistic interaction indices of ν̂ for a target set S ⊆ 2N in O(nnodes ·|S|) time, where nnodes denotes the number of tree nodes. An alternative is Fourier extraction, as proposed by Butler et al. [4], Gorji et al. [18], whose cost grows exponentially with the maximum tree depth d. In the worst case, a tree of depth d can induce up to O(4d ) Fourier coefficients [18], which must then be extracted and converted to the desired interaction indices. We compare the two extraction approaches on ten datasets: B IKE, A DULT C ENSUS, H OUSING, C RIME, F OREST F IRES, IL60, CG60, NHANES, C ANCER, and E STATE. For each method, we measure the runtime required to extract all target interactions. We exclude preprocessing time, such as storing the tree structure in a hash map, since this is a one-time cost that can be amortized across multiple extraction runs. For Fourier extraction, we measure the time required to extract the Fourier coefficients and convert them to the target interaction indices. For interventional extraction, we directly measure the runtime of our extraction algorithm. We use the Fourier extraction implementation provided by shapiq [42] and our interventional extraction implementation based on Algorithm 2. We report the speedup as the ratio between the runtime of Fourier extraction and the runtime of interventional extraction in Figure 14. Since a tree can only contain interactions of order k if its depth is at least k, we report order-k speedups only for trees with depth at least k. The results show that interventional extraction consistently outperforms Fourier extraction across datasets, with speedups ranging from 10× to more than 1000×, depending on the dataset and maximum tree depth. The only exception occurs for shallow trees of depth 3 when extracting 39

third-order interactions, where Fourier extraction can be slightly faster on large datasets such as C RIME. We additionally investigate the effect of varying the tree depth of the XGBoost proxy on the approximation quality of ProxySPEX and ProxySHAP in Figure 13. To this end, we set the maximum depth of the individual XGBoost trees [8] to 2, 4, 6, and 8. We observe that shallow trees perform particularly well for small coalition budgets, while medium-depth trees are effective across most of the considered budget range. For large coalition budgets, deeper trees become increasingly beneficial, suggesting that the default depth of 6 may no longer capture all relevant interaction structure once sufficient training data are available. This trend is evident in both ProxySHAP and ProxySPEX, underscoring the importance of adjusting the tree depth to the available coalition budget. D.6

Detailed Comparison of ProxySHAP and ProxySPEX

ProxySPEX [4] is a model-agnostic approximation method for computing any-order cardinalprobabilistic interaction indices, including in settings with large feature counts. It consists of four main steps: 1. Sampling and evaluation. Coalitions T ⊆ 2N are sampled and evaluated, yielding the dataset D = {(T, ν(T ))}T ∈T . 2. Proxy fitting. A gradient-boosted tree model, by default LightGBM, is fitted on D by minimizing the mean squared error. 3. Fourier extraction and truncation. Fourier coefficients are extracted from the fitted tree proxy. ProxySPEX then keeps a minimal subset C ⋆ ⊆ F of coefficients that explains at least 95% of the total squared Fourier mass, P F2 ⋆ C = arg min |C| s.t. PF ∈C 2 ≥ 0.95, C⊆F F ∈F F where F denotes the set of Fourier coefficients extracted from the tree. 4. Adjustment. Given the truncated coefficient set C ⋆ , ProxySPEX applies a refinement step to improve the extracted Fourier coefficients. It constructs a design matrix X ∈ ⋆ {−1, +1}|T |×|C | with entries Xi,j = (−1)|Ti ∩Cj | , and solves the regularized regression problem F ⋆ = arg min⋆ ∥ν − XF ∥22 + λ∥F ∥22 . F ∈R|C |

The truncation step is essential for making the refinement step computationally feasible, since the number of Fourier coefficients of a tree can grow as O(4d ) with the tree depth d. Based on the refined Fourier coefficients F ⋆ , ProxySPEX can compute any cardinal-probabilistic interaction index, since the Fourier coefficients form a basis of the value function. For the exact transformations, we refer to Appendix A of Butler et al. [4]. ProxySHAP follows a closely related proxy-based strategy, but differs in two important aspects. First, instead of extracting Fourier coefficients and converting them into the desired index, ProxySHAP directly extracts the target cardinal-probabilistic interaction index from the tree proxy. Second, ProxySHAP applies an case-by-case MSR adjustment directly to the residual game. This yields a consistent estimator whenever the residual correction is sufficiently well covered by the sampled coalitions, and it leads to improved performance in regimes where sufficient budget is available (see Figures 4 and 18). Figure 15 illustrates how the approximation quality of ProxySPEX changes as the cutoff threshold is increased and, consequently, more Fourier energy is retained in C ∗ . As the cutoff approaches 1, ProxySPEX increasingly recovers the behavior of ProxySHAP, but at substantially higher computational cost, since up to O(4d ) Fourier coefficients may need to be converted to the desired interaction index. In contrast, ProxySHAP consistently exhibits near-diagonal behavior across budgets and datasets, and is only outperformed by KernelSHAP-IQ once the latter receives a sufficiently large evaluation 40

10000x 1000x

BII

order 1

BII

order 2

order 3

BII

100x 10x 1x 10x 10000x 1000x

faster

slower

FBII

100x 10x

Speedup

1x 10x 10000x 1000x

faster

slower

SII

100x 10x 1x 10x 10000x 1000x

faster

slower

FSII

100x 10x 1x

faster

slower

10x 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 3

Max Depth Fourier baseline

Bike (n = 12) Forest (n = 13) Adult (n = 14)

Estate (n = 15) Cancer (n = 30) CG60 (n = 60)

IL60 (n = 60) NHANES (n = 79) Crime (n = 101)

Figure 14: Speedup of interventional extraction compared to Fourier extraction for extracting all interactions of order 1, 2, and 3 across different datasets.

Figure 15: Predicted versus ground-truth normalized interaction values for different approximation methods and sampling budgets. Each point represents one interaction value from one dataset and one benchmark run; points closer to the diagonal indicate better agreement with the exact interaction values. Columns compare ProxySHAP, ProxySPEX, SHAPIQ, PermutationSamplingSII, and KernelSHAPIQ, while rows correspond to increasing evaluation budgets. In ProxySPEX, the central column shows four cutoff thresholds, with larger cutoffs retaining more Fourier energy in the surrogate approximation. As the ProxySPEX cutoff increases, the scatter increasingly aligns with ProxySHAP, indicating that ProxySPEX becomes more equivalent to ProxySHAP as more Fourier energy is retained.

budget. For C OIL 2000, even a cutoff of 0.999 does not lead to substantial improvements, since more than 48% of the Fourier coefficients are still discarded. We refer to Figure 18 for a complementary overview of the best-performing methods on these datasets. D.7

When to use Adjustment?

The adjustment step is designed to make the resulting interaction estimates consistent. To assess its practical relevance, we complement this theoretical motivation with an empirical analysis across all 26 considered TabArena datasets [13], budgets, and interaction orders. Since each experiment is repeated over 30 explained instances per dataset, we measure the instance-wise relative change in approximation quality as MSE with adjustment ri = , MSE without adjustment and report the geometric mean N

1 X r̄ = exp log ri N i=1

! ,

pooled across all instances with the same number of players. The shaded bands show the geometric standard deviation factor, s = exp(std(log ri )) , 42

Cancer (d = 30)

102

ProxySHAP (XGBoost)

103

IL60 (d = 60)

102 101 100 10 1 10 2 10 3 104

Crime (d = 101) 10 1

order 2

Relative MSE ± SEM

102 101 100 10 1 10 2 10 3 10 4

10 2

102

103

Model Evaluations

ProxySHAP (XGBoost, MSR)

104

102

ProxySHAP (XGBoost, MSR, disjoint)

103

104

ProxySHAP (XGBoost, disjoint)

Figure 16: ProxySHAP with disjoint coalition sets for proxy fitting and residual adjustment.

drawn as the multiplicative interval [r̄/s, r̄ · s], corresponding to one standard deviation in log-space. Hence, values below one indicate that adjustment improves approximation quality, whereas values above one indicate that it deteriorates. For interaction indices, however, the effect of adjustment is more nuanced. While adjustment can reduce proxy bias, it can also introduce substantial variance, especially for higher-order interactions. This is consistent with our theoretical analysis in Section 3, where we show that the dominant variance term of the adjustment estimator scales as nk−1 , with n denoting the number of features and k the maximal interaction order. Consequently, adjustment can deteriorate approximation quality when the feature dimension or interaction order is large. Empirically, Figure 3 shows that, for secondorder interactions, adjustment remains beneficial up to datasets with 90 features, provided that the budget is sufficiently large. In contrast, for third-order interactions, adjustment already deteriorates approximation quality for games with more than 30 features, even at large budgets. We therefore recommend applying MSR adjustment primarily when the available coalition budget is substantially larger than the dominant variance term, i.e., when |T | ≫ nk−1 . In practice, this supports using adjustment for second-order interactions at sufficiently large budgets, while omitting it for third-order interactions and beyond unless the budget is exceptionally large. D.8

Shared vs. Disjoint Subsets in ProxySHAP

We compare two strategies for using the sampled coalitions: reusing the same set for both proxy fitting and residual adjustment, or splitting it into disjoint sets. For the disjoint variant, we first sample coalitions T and then split them into T Proxy and T Adjustment , which are used for fitting the proxy and estimating the residual correction, respectively. As shown in Figure 16, enforcing disjoint sets degrades approximation quality for cardinal-probabilistic interactions. This provides empirical evidence that the observation of Witter et al. [63] also holds for interaction indices: reusing the same sampled coalitions for proxy fitting and adjustment is preferable in practice. Based on this finding, all experiments in the main paper use the same sampled coalitions for both steps, as shown in Figure 1. D.9

Approximation Quality

We provide additional approximation-quality results across datasets and budgets for second- and third-order Shapley interaction indices and Banzhaf interaction indices (Figure 17). We also report winner maps for SII (Figure 18) and BII (Figure 19), where the winner is the method with the lowest average relative MSE across the 30 explained instances for each dataset and budget. A complete collection of approximation curves is available at https://github.com/Advueu963/ProxySHAP, alongside additional metrics such as Pearson’s correlation. Banzhaf Interaction Index. As shown in Figure 19, ProxySHAP with an XGBoost proxy almost always outperforms all baselines across datasets and budgets for both second- and third-order interactions. For second-order interactions, the linear proxy can be stronger on some datasets, such as C RIME and S OYBEAN. For third-order interactions, however, the tree-based proxy tends to perform better. As the number of players and target interactions grows, the linear proxy becomes less effective because fitting the interaction basis requires larger budgets. Overall, ProxySHAP with an XGBoost proxy is the strongest method for approximating Banzhaf interaction indices in our experiments. 43

Shapley Interaction Index. Figure 18 shows that ProxySHAP with an XGBoost proxy consistently outperforms all baselines across budget and player regimes. For smaller datasets, ProxySHAP outperforms for mid-sized budget counts, but shifts to the lower-budget regime as the number of players increases. For pairwise interactions on datasets with roughly 30 features and sufficiently large budgets, KernelSHAP-IQ can outperform both XGBoost and linear ProxySHAP variants, e.g., on S OYBEAN, I ONOSPHERE, and D ROPOUT. However, as the number of features increases, KernelSHAP-IQ becomes applicable in fewer regimes, and ProxySHAP with XGBoost becomes the best-performing method. The winner maps also show that the regime in which MSR adjustment is beneficial shrinks with increasing feature count for both second- and third-order interactions. For third-order interactions, ProxySHAP with XGBoost outperforms all baselines across datasets and budgets, whereas the linear proxy is preferable in only a few cases, such as Z OO.

Additional Related Work

Beyond proxy-based methods, research has focused on variance reduction for Monte Carlo estimates of probabilistic values [30, 56, 60] and interactions [31, 58]. Parallel to our work is amortization, where an explanation model is trained to directly predict attributions [10, 24] or interactions [12], rather than explaining the proxy post-hoc. Further related are ways for improving estimation of the value function for explanations via marginal distribution compression [1] and conditional distribution generation [47]. Specialized polynomial-time algorithms exist for computing values and interactions for k-nearest neighbours [61], SVMs [40], and graph neural networks [44]. Within tree-based methods, Muschalik et al. [43] derived exact algorithms for path-dependent interactions; however, unlike our proposed interventional extension, their method is incompatible with proxy modeling.

102

103

104

102 100 10 2 10 4

Relative MSE ± SEM

102

103

104

102 100 10 2 10 4 102

103

100 10 2 10 4

100 10 2 10 4 102

102 100 10 2 10 4 10 6

104

102

103 101 10 1 10 3

103

102

102 100 10 2 10 4

103

104

103

104

102

103

102 100 10 2 10 4 102

104

102

103

104

101 10 1 10 3 103

104

103

104

103 100 10 3

102

103

104

102

103

104

102

103

104

102

103

104

10 2 102

103

104

103

104

103

104

103

104

100 10 1 10 2 10 3 2 10 100 10 1 10 2 10 3 10 4

103

104

102

103

104

102

103

104

102

104

10 2 103

104

103

104

102 103 101 10 1 10 3

103

104

100 10 1 10 2 10 3

10 1 10 2 102

105 103 101 10 1

104 102 100 10 2 10 4

100

103 101 10 1

100 102

103

105

102

102 100 10 2

102

104 102 100 10 2 102

104

103 100 10 3

10 3 103

103

102 100 10 2 10 4 10 6

104

10 1 102

102 101 10 2 10 5

101

101 10 1 10 3

104

103

BII Estate (n = 15)

102

103

104

100 10 1

102

100 10 1 10 2 10 3 2 10 100 10 1 10 2 10 3 10 4

Model Evaluations

103

Thyroid (n = 21)

103

102

Diabetes130 (n = 47) Ionosphere (n = 33)

102

102 100 10 2 10 4 10 6

Order 3

SII

MIC (n = 111) Superconductivity (n = 81) Splice (n = 60)

104 102 100 10 2 10 4

BII

ApsFailure (n = 170)

Order 2

SII

Figure 17: Selection of representative approximation curves for SII and BII at second- and third-order interactions.

Order 2 (SII)

Order 3 (SII)

Dataset

Bioresponse (n = 1776) (INT) HivaAgnostic (n = 1617) (INT) QsarTid11 (n = 1024) (INT) Kddcup09 (n = 212) (INT) ApsFailure (n = 170) (INT) MIC (n = 111) (INT) Crime (n = 101) (INT) TWBankruptcy (n = 94) (INT) NaticusDroid (n = 86) (INT) Coil2000 (n = 85) (INT) Superconductivity (n = 81) (INT) NHANES (n = 79) (INT) Bankruptcy (n = 64) (INT) Splice (n = 60) (INT) IL60 (n = 60) (INT) CG60 (n = 60) (INT) Diabetes130 (n = 47) (INT) QsarBiodeg (n = 41) (INT) Anneal (n = 38) (INT) StudentsDropout (n = 36) (INT) Soybean (n = 35) (INT) Mutagenicity_n35 (GRAPH) (d=35) Ionosphere (n = 33) (INT) Hazelnut (n = 30) (INT) Cancer (n = 30) (INT) MarketingCamp (n = 25) (INT) Benzene_n25 (GRAPH) (d=25) CouponRec (n = 24) (INT) Heloc (n = 23) (INT) CreditCard (n = 23) (INT) Mushroom (n = 22) (INT) Thyroid (n = 21) (INT) Jm1 (n = 21) (INT) Airline (n = 21) (INT) CreditG (n = 20) (INT) Churn (n = 19) (INT) Hepatitis (n = 19) (INT) OnlineShoppers (n = 17) (INT) ViT16 (n = 16) (EXT) Estate (n = 15) (TABPFN) DistilBERT (n = 14) (EXT) ResNet18 (n = 14) (EXT) Adult (n = 14) (TABPFN) Forest (n = 13) (TABPFN) Bike (n = 12) (TABPFN) 13

ProxySHAP (XGBoost) [our] ProxySHAP (XGBoost, MSR) [our]

227

ProxySHAP (Linear) [our] ProxySHAP (Linear, MSR) [our]

951

3,987

Budget

KernelSHAPIQ ProxySPEX (XGBoost)

16,701

70,000 13

227

951

3,987

Budget

ProxySPEX (XGBoost+HPO-Informed) ProxySHAP (XGBoost+HPO-Informed) [our]

16,701

70,000

PermutationSamplingSII SHAPIQ

SVARMIQ

Figure 18: Winnermap comparing the best performing method for each dataset and budget for SII orders 2 and 3. Note that the HPO-Informed variants are considered only for datasets with more than 1000 features in this overview.

Order 2 (BII)

Order 3 (BII)

Dataset

Bioresponse (n = 1776) (INT) HivaAgnostic (n = 1617) (INT) QsarTid11 (n = 1024) (INT) Kddcup09 (n = 212) (INT) ApsFailure (n = 170) (INT) MIC (n = 111) (INT) Crime (n = 101) (INT) TWBankruptcy (n = 94) (INT) NaticusDroid (n = 86) (INT) Coil2000 (n = 85) (INT) Superconductivity (n = 81) (INT) NHANES (n = 79) (INT) Bankruptcy (n = 64) (INT) Splice (n = 60) (INT) IL60 (n = 60) (INT) CG60 (n = 60) (INT) Diabetes130 (n = 47) (INT) QsarBiodeg (n = 41) (INT) Anneal (n = 38) (INT) StudentsDropout (n = 36) (INT) Soybean (n = 35) (INT) Ionosphere (n = 33) (INT) Hazelnut (n = 30) (INT) Cancer (n = 30) (INT) MarketingCamp (n = 25) (INT) CouponRec (n = 24) (INT) Heloc (n = 23) (INT) CreditCard (n = 23) (INT) Mushroom (n = 22) (INT) Thyroid (n = 21) (INT) Jm1 (n = 21) (INT) Airline (n = 21) (INT) CreditG (n = 20) (INT) Churn (n = 19) (INT) Hepatitis (n = 19) (INT) OnlineShoppers (n = 17) (INT) ViT16 (n = 16) (EXT) Estate (n = 15) (TABPFN) DistilBERT (n = 14) (EXT) ResNet18 (n = 14) (EXT) Adult (n = 14) (TABPFN) Forest (n = 13) (TABPFN) Bike (n = 12) (TABPFN) 13

ProxySHAP (XGBoost) [our] ProxySHAP (XGBoost, MSR) [our]

178

ProxySHAP (Linear) [our] ProxySHAP (Linear, MSR) [our]

666

2,479

Budget

9,313

KernelSHAPIQ ProxySPEX (XGBoost)

35,000 13

178

666

2,479

Budget

ProxySPEX (XGBoost+HPO-Informed) ProxySHAP (XGBoost+HPO-Informed) [our]

9,313

35,000

PermutationSamplingSII SHAPIQ

SVARMIQ

Figure 19: Winnermap comparing the best performing method for each dataset and budget for BII orders 2 and 3. Note that the HPO-Informed variants are considered only for datasets with more than 1000 features in this overview.

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: Please see Section 3, Section 4 and for the proofs see Appendix A. Guidelines: • The answer [N/A] 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 in the paper and important assumptions and limitations. A [No] or [N/A] 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 as 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: Please see the end of Section 5. Guidelines: • The answer [N/A] means that the paper has no 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 a 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 (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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 approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it 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 to address problems of privacy and fairness. • 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 important 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 a complete (and correct) proof? Answer: [Yes] 48

Justification: Please see Section 3.2 and Appendix A. Guidelines: • The answer [N/A] means that the paper does not include theoretical results. • All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or 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 complemented 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 conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Please see Section 4 as well as Appendix C. Guidelines: • The answer [N/A] 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 to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to 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 is often one good way to accomplish this, but reproducibility can also be provided via 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 a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If 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 a way to access this model for reproducing the results or a way to reproduce 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 authors 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 to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? 49

Answer: [Yes] Justification: Please see the code: https://github.com/Advueu963/ProxySHAP Guidelines: • The answer [N/A] means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://neurips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an 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: //neurips.cc/public/guides/CodeSubmissionPolicy) 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. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results? Answer: [Yes] Justification: Please see Section 4 as well as Appendix C. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a 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 appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: Please see Section 4 as well as Appendix C. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The authors should answer [Yes] if the results are accompanied by error bars, confidence 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.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. 50

• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates). • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Please see Appendix C. Guidelines: • The answer [N/A] 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 as well as 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 make it into the paper). 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: We have reviewed the NeurIPS Code of Ethics and confirm that our research conforms to it in every respect. Guidelines: • The answer [N/A] 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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: Please consult the Broader Impact statement in Section 5. Guidelines: • The answer [N/A] means that there is no societal impact of the work performed. • If the authors answer [N/A] or [No], they should explain why their work has no societal impact or 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 specific groups), privacy considerations, and security considerations. 51

• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)? Answer: [N/A] Justification: We do not release any data or models with a high risk for misuse, so we have not put in place any safeguards. Guidelines: • The answer [N/A] means that the paper poses no such risks. • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to 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 not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [Yes] Justification: Please see Appendix C. Guidelines: • The answer [N/A] means that the paper does not use 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 a URL. • The name of the license (e.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. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 52

• 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 documentation provided alongside the assets? Answer: [Yes] Justification: Please see https://github.com/Advueu963/ProxySHAP Guidelines: • The answer [N/A] means that the paper does not release new assets. • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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 paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [N/A] Justification: Our paper does not involve crowdsourcing nor research with human subjects. Guidelines: • The answer [N/A] 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, 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 describe 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: [N/A] Justification: Our paper does not involve crowdsourcing nor research with human subjects. Guidelines: • The answer [N/A] 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 equivalent) 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 we expect authors to adhere to the NeurIPS 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 53

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 rigor, or originality of the research, declaration is not required. Answer: [N/A] Justification: The core method development does not involve LLMs as any important, original, or non-standard components. Guidelines: • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.

Record · ID 216825 · SHA-256 d967210482db709c
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.