PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression
Authors: Fabian Fumagalli
R. Teal Witter
Christopher Musco
Venue: ICLR 2026 Poster (2026)
Keywords: Explainable AI
Kernel SHAP
Shapley Value
Primary area: interpretability and explainable AI
TL;DR: We introduce PolySHAP, an interaction-aware extension of KernelSHAP

Abstract: Shapley values have emerged as a central game-theoretic tool in explainable AI (XAI). However, computing Shapley values exactly requires $2^d$ game evaluations for a model with $d$ features. Lundberg and Lee's KernelSHAP algorithm has emerged as a leading method for avoiding this exponential cost. KernelSHAP approximates Shapley values by approximating the game as a linear function, which is fit using a small number of game evaluations for random feature subsets.

In this work, we extend KernelSHAP by approximating the game via higher degree polynomials, which capture non-linear interactions between features. Our resulting PolySHAP method yields empirically better Shapley value estimates for various benchmark datasets, and we prove that these estimates are consistent.

Moreover, we connect our approach to paired sampling (antithetic sampling), a ubiquitous modification to KernelSHAP that improves empirical accuracy. We prove that paired sampling outputs exactly the same Shapley value approximations as second-order PolySHAP, without ever fitting a degree 2 polynomial. To the best of our knowledge, this finding provides the first strong theoretical justification for the excellent practical performance of the paired sampling heuristic.

Published as a conference paper at ICLR 2026
POLYSHAP: EXTENDING KERNELSHAP WITH INTERACTION-INFORME]] POLYNOMIAL REGRESSION
Fabian Fumagalli
R. Teal Witter
Christopher Musco New York University emusco@nyu. edu
Bielefeld University
Claremont McKenna College rtea twerteeeeee.....m edu
ffumagal 14 11@ttc1faak..d..
ABSTRACT
Shapley values have emerged as a central game-theoretic tool in explainable Al (XAI). However, computing Shapley values exactly requires 24 game evaluations for a model with d features. Lundberg and Lee's KernelSHAP algorithm has emerged as a leading method for avoiding this exponential cost. KerneISHAP ap- proximates Shapley values by approximating the game as a linear function, which is fit using a small number of game evaluations for random feature subsets.
In this work, extend KernelSHAP by approximating the game via higher de- gree polynomials, which capture non-linear interactions between features. Our resulting PolySHAP method yields empirically better Shapley value estimates for various benchmark datasets, and we prove that these estimates are consistent.
Moreover, we connect our approach to paired sampling (antithetic sampling), a ubiquitous modification to KernelSHAP that improves empirical accuracy. We prove that paired sampling outputs exactly the same Shapley value approximations as second-order PolySHAP, without ever fitting a degree 2 polynomial. To the best of our knowledge, this finding provides the first strong theoretical justification for the excellent practical performance the paired sampling heuristic.
INTRODUCTION
Understanding the contribution of individual features to a model's prediction is central goal in ex- plainable artificial intelligence (XAI) (Covert & Lee, 2021). Among the most influential approaches are those grounded in cooperative game theory, where the Shapley value (Shapley, 1953) provides a principled way to distribute model's output to its d inputs.
The intuition behind the use of Shapley values to attribute larger values to the players coop- erative game with the most effect on the game's is value. In XAI applications, players are typically features or training data points and the game value is typically a prediction or model loss.
Formally, represent cooperative game involving players D {1..... d} via value function v: 2D - IR that maps subsets of players to values (2 denotes the powerset of D). Shapley values then defined! via the best linear approximation to the game v. Concretely, for subset S D, P(S) is approximated by linear function in the binary features L[i E S] for E D. The Shapley values are the coefficients of the linear approximation minimizing specific weighted lg loss:
[p] arg min (E
Σ P(S) v(S)
Σ
where the non-negative Shapley weights μ(S) are given in Equation (2). The constraint that the Shapley values sum to v(D) enforces what is known as the "efficiency property", one of four ax- iomatic properties that motivate the original definition of Shapley values (see e.g. (Molnar, 2024)).
Since the sum above involves 2d terms, exact minimization of the linear approximation to obtain & [μ] is infeasible for most practical games. Over the past several years, substantial research has
Without loss of generality, assume v(0) 0. Otherwise, could consider the centered game v(S) (6) which has the same Shapley values.

---

Published as a conference paper at ICLR 2026
Sampling
KernelSHAP
Extract SV
$
SV
v(S,)
v(22)
Linear approximation
PolySHAP
v(5m
TEDUTHEZ
Polynomiol approximation
Game
Interactions
Figure 1: Both KernelSHAP and PolySHAP fit function to approximate sample of game eval- uations. While KerneISHAP uses linear approximation, PolySHAP uses a more expressive poly- nomial approximation. Finally, both algorithms return the Shapley values (SV) of their respective approximations (trivial for KemelSHAA, see Theorem 4.3 for PolySHAP).
focused making the computation of Shapley values feasible in practice (Covert al., 2020; Covert & Lee, 2021; Mitchell et al., 2022; Musco & Witter, 2025; Witter et al., 2025), with KernelSHIA (Lundberg & Lee, 2017) emerging as of the most widely used model-agnostic methods.
From the least squares definition of Shapley values, KernelSHAP can be viewed as a two step pro- cess: First, approximate the game y with linear function fit from sample of game evaluations v(S) on randomly selected subsets S. Second, return the Shapley values of the approximation, which, for linear functions, are simply the coefficients of each input.
A natural idea is to adapt this framework to fit with a richer function class that still admits fast Shapley value computation. One such class tree-based models like XGBoost, which Witter al. (2025) recently leveraged to approximate the game. When the tree-based approximation is accurate, their RegressionMSRR estimator produces more accurate Shapley value estimates than KernelSHAP. Butler et al. (2025) also use tree-based models to learn an approximation to the game, but extract Fourier coefficients which can be used to estimate more general attribution values. In the small sample regime with budgets less than 5n, their ProxySPEX estimator outperforms KernelSHAP but achieves comparable performance to KernelSHAP for higher budgets.
In this work, introduce alterative approach called PolySHAP, where approximate via higher degree polynomial in the features 1 e S for E D, illustrated in Figure 1. For a degree polynomial, let d' (dd) be the number of terms. We show that, after fitting an approximation with m samples, we can recover the Shapley values of the approximation in just O (dd') time. Across various experiments, we find that higher degree PolySHAP approximations result in more accurate Shapley value estimates (see e.g., Figure 2). Moreover, we prove that the PolySHAP estimates are consistent, concretely that we obtain the Shapley values exactly m goes 2d, This is in contrast to RegressionMSR, which needs an additional "regression adjustment" step to obtain a consistent estimator for free-based approximations (Witter et al., 2025).
As a second main contribution of our work, we provide theoretical grounding for a seemingly un- related sampling strategy called paired sampling, which known to significantly improve the ac- curacy of KernelSHAP estimates (Covert & Lee, 2021; Mitchell et al., 2022; Olsen et al., 2024). In paired sampling, subsets are sampled in paired complements and D \ S. While used in all state-of-the-art Shapley value estimators, the reason for paired sampling's 's superior performance is not well understood. Surprisingly, we prove that KernelSHAP with paired sampling outputs exactly the same Shapley value approximations second-orde PolySHAP without ever fitting degree polynomial. This theoretical finding generalizes very recent result of Mayer & Wüthrich (2025), who showed that KernelSHAF with paired sampling exactly recovers Shapley values when the game
2

---

Published as a conference paper at ICLR 2026
has interactions of most degree 2. Because the second-order PolySHAP will exactly fit degree 2 game, their result follows immediately from special case of ours. However, our finding is more general because it explains why paired sampling is effective for all games, not just those with at most degree interactions.
Contributions. The main contributions of our work be summarized follows:
We propose PolySHAP, extension of KernelSHAP that models higher-order interaction terms to approximate v, and prove returns the Shapley values as the number of samples goes to 24 (Theorem 4.3). Moreover, we empirically show that PolySHAP results in more accurate Shapley value estimates than KemnlSHHA and Permutation sampling.
We establish a theoretical equivalence between paired KerneISHAP and second-order PolySHAP (Theorem 5.1), thereby explaining the practical benefits of paired sampling.
RELATED WORK
KernelSHAP Sampling Strategies. Prior work on improving KerneISHAP has focused on refin- ing the subset sampling procedure, aiming to reduce variance and improve computational efficiency (Kelodjou et al., 2024; Olsen & Jullum, 2024; Musco & Witter, 2025). Among these enhance- ments, paired sampling produces the largest improvement in accuracy (Covert & Lee, 2021), yet, until the present work, it was not understood why beyond limited special cases. Another notable enhancement is in the sampling distribution. While it is intuitive to sample subsets proportional to their Shapley weights (Equation 2), it turns out that sampling proportional to the leverage scores can be more effective (Musco & Witter, 2025). Paired sampling has also been observed to improve LeverageSHAP (KemelSHAP with leverage score sampling).
Other Shapley Value Estimators. Beyond the regression-based approach of KerneISHAP, prior Shapley value estimators are generally based on direct Monte Carlo approximation (Kwon & Zou, 2022a; Castro et al., 2009; Kwon & Zou, 2022b; Kolpaczki et al., 2024; Li & Yu, 2024). These methods estimate the i-th Shapley value based on the following equivalent definition:
VISU ( -VS)
Sv
Mij d
Σ SCDVA)
(1)
(15)
Permutation sampling, where subsets are sampled from a permutation, particularly effective approach (Castro et al., 2009; Mitchell et al., 2022). However, in direct Monte Carlo methods, each game evaluation is used to estimate at most two Shapley values. MSR methods reuse game evaluations in the estimate of every Shapley value, but at the cost of higher variance (Li & Yu, 2024; Witter et al.. 2025). A recent benchmark finds that RegressionMSR with rree-based approximations, LeverageSHAP, KemeISHAP, and Permutation sampling the most accurate (Witter et al., 2025).
Higher-Order Explanations. Another line of work seeks to improve approximations by explicitly modeling higher-order interactions. SSDA- (Pelegrina al., 2023) solves least-squares prob- lem over all interactions up to order k. and converges to the Shapley value for = and A: = (Pelegrina al., 2025). With our results, where the practical differences are discussed in Appendix A.4. Relatedly, Mohammadi et al. (2025) propose a regularized least squares method based the Möbius transform (Rota, 1964), which verges only when all higher-order interactions are included. By contrast, PolySHAP converges for any chosen set of interaction terms. Beyond approximation of the Shapley value, Kang et al. (2024) leverage the Fourier representation of games to detect and quantify higher-order interactions.
simplify SADD-SHAP and prove general convergence,
PRELIMINARIES ON EXPLAINABLE AI AND COOPERATIVE GAMES
Notation.
We boldface letters denote vectors, e.g., æ, with entries 2;, and the corresponding random variable ă. The all-one vector denoted by 1, and (:s is the standard inner product.
Given the prediction of machine learning model f Rd - R. post-hoc feature- explanations aim to quantify the contribution of features D to the model output. Such explanations are defined by (i) the choice of explanation game v: 2D R and (ii) game-the attribution measure,

---

Published as a conference paper at ICLR 2026
such the Shapley value (Covert et al., 2021). For given instance R the local explanation game V/2 describes the model's prediction when restricted to subsets of features, with the remaining features replaced through perturbation. The perturbation is carried out using different imputation strategies, as summarized Table
Similarly, global explanation games are constructed from Vee by evaluat- ing measures such as variance risk (Fumagalli et al., 2025). Beyond an- alyzing features, other variants have been proposed, for instance to char- acterize properties of individual data points (Ghorbani & Zou, 2019).
Table Local explanation games Ve for instance a.
Method
Game
V=(
Va (0)
Baseline
Ve
(b)
[ bDys)
f(b)
Marginal
V (m)
[ff Emss)
E[f(@)
Conditional
(e)
(f) is = xs]
[[f()]]
Like most Shapley value estimators, PolySHAP is agnostic to how the game v is defined.
KernelSHAP. Given budget of m game evaluations, KemelSHAP solves the approximate least squares problem:
2
m
((e)) p(S))
d
3SV [
arg min $ER (
Σ
v(S) Σ
dilli Sol
with Sj.....
:......,,,. Sm ~
where the Shapley weight, for subset S C D is given by
m(S)
if < |S| < d and 0 otherwise.
While effective, KernelSHAP is inherently limited linear (additive) approximation of v based on the sampled coalitions.
INTERACTIOO- APPROXIMATION OF SHAPLEY VALUES
We now present PolySHAP, our core contribution that extends KernelSHAP by approximating the game via polynomial regression. Rather than fitting linear function, PolySHAP captures higher- order feature interactions, leading to more accurate Shapley value estimates. We first introduce the PolySHAP representation, then discuss sampling strategies and interaction frontier construction.
4.1 POLYSHAP INTERACTION REPRESENTATION
We introduce PolySHAP, method for producing Shapley value estimates from polynomial ap- proximation of v. Let the interaction frontier I subset of interaction terms
C (T C 2 2}.
We then extend the linear approximation of by defining interaction-based polynomial repre- sentation restricted to interactions in I. Definition 4.1. The SoAy representation oJ E odd with d' + [I] is given by
Φ [1]
arg min
EU()) v(S)
Σ Su 11jES E
&ERR (6.1))))))))))))))))) () SED
TEDUI
jET
Here, and in the following we abuse notation with 6; = Φ() and 1 E := 1 for
The PolySHAP representation generalizes the least squares formulation of the Shapley value to arbitrary interaction frontiers I. For each interaction set T E I, the approximation contributes coefficient or only if all features in T are present in S.

---

Published as a conference paper at ICLR 2026
Remark 4.2. The PolySHAP representation directly extends the Faithful Shapley interaction index (Tsai et al., 2023) to arbitrary interaction frontters
In the theorem below, we show how to recover Shapley values from the PolySHAP representation. Theorem 4.3. The Shapley values of v are recovered the PolySHAP representation as
1 [ of
S
for E D.
S
SET:ES
other words, consistent estimation of the PolySHAP representation directly implies consistent estimation of the Shapley value.
4.2 POLYSHAP ALGORITIM
A natural approximation strategy is to first estimate the PolySHAP representation and then map the result back to Shapley values using Theorem 4.3. Concretely, we approximate the PolySHAP representation by solving
((()) @ER4+1E):(0.1)) (D) 8=1 p(St)
arg min
Σ
v(S))
E Φr 1[ E
(4)
TEDUZ
JET
with m samples S1...., S. drawn from some distribution where < m < 2d, (When v is clear from context, we write of for (F()))
We then convert o² into Shapley value estimates via Theorem 4.3. The rationale behind this is approach is that the more expressive PolySHAP representation more accurately represents v, which in turn yields more accurate Shapley value estimates. We refer to this interaction-awee aware extension of KemeelSHA as PolySHAP.
In order to produce the PolySHAP solution in practice, we use the matrix representation of the regression problem. Define the sampled design matrix X E Rmxxd and the sampled target vector y E Im The rows are indexed by L E [m], and the columns of X are indexed by interactions E DUI. The entries the sampled design matrix and sampled target vector are given by
((()) p(Se)
((Se) p(ee)
X
V
1[ C St]
and [ý]e V
(v(e)).
(5)
In this notation, may write
T
arg min &ER (VD))
|XΦ - 511..
(6)
We would like to apply standard regression tools when solving the problem, convert from the constrained problem to an unconstrained reformulation. Let P be the matrix that projects off the all ones vector in d' dimensions i.c., Par = =I- $ 11' T. We have
M(D)
2
((D)
arg min Φend', (())
|| - -112
arg min deRd' ((.1))=
Xo + x1
y
+
d'
d'
2
v(D)
((D)
Pa arg min $ER
XP x1
y
d'
d'
PolySHAPis described in pseudocode in Algorithm 1.
5

---

Published as a conference paper at ICLR 2026
Sampling Standard
Method
1-PolySHAP (KernelSHAP)
S-PP (50%)
PolySSHAP (50%)
PoloySHAP
2-POlySHAP
3-PolSSHAP
Bikee (d 12)
Forest (di 13)
Resive188 (d'- 14)
VIT id 16)
1091
20-1
$0.0
30%
10-1
10-1
30
1600
6550
6050
E00O 2956
155%)
(59%))
(78P) 299%
(199))
237
(5574)
199 1924)
130R1 (371)) (55N)) 17 (NEM)
(091 13.7h1 138%) 124%) (9390)
Cancer (d 30)
CG60 (d 60)
NHANES (d) 1 79)
Crime (d 101)
100
10-1
MCC 5E.M
2 10-
BCEO 72000 10303 20000
9333 10000
30300
1030
23100
4331 12000 2070
(+23)) 1-155)
10:200 (6236
(<130) [-15] 14.200 1-18) (42%))
1-1%1 (-250) 1-13) 16.36
(+2361 1-132) (-155] (4200) (12%)
Figure 2: Approximation quality measured by MSE (+ SEM) for various sampling budgets on different games, Adding any number of interactions in PolySHAP improves approximation quality.
Algorithm PolySHAP
Require: game x/x, interaction frontier I, sampling distribution p. sampling budget m > d'
1: Define v(5) == (S) - (0)
Center for notational simplicity
2: {St)mm f- SAMPLB m.
3: Construct X and y
Equation (5)
4: d² + SOLVELLAASTSQUARESSRRR (XP y x1 +
( d
5: BSV + POLYSHAPTOSV(
Equation (3)
6: return U/ (0), +5)
Computational Complexity. The computational complexity of PolySHAP can be divided into two components: evaluating the game for the sampled coalitions, and solving the regression problem followed by extraction of the Shapley values. Evaluating the game requires least one model call for local explanation games, and highly depends on the application setting. Solving the regression problem scales with Omm (d')² + (d')s), whereas transforming the PolySHAP representation to Shapley values is of order O(d d.). Importantly, this complexity scales linearly with the budget m, and quadratically with the number of regression variables d'. In practice, the dominant factor in computational cost is usually the game evaluations, i.e., the model predictions. However, for smaller model architectures, the runtime can be influenced by the number of regression variables.
4.3 SAMPLING STRATEGIES FOR POLYSHAP
PolySHAP uses distribution p to sample m game evaluations for approximating the least squares objective. Previous work (Lundberg & Lee, 2017; Covert & Lee, 2021) chose p proportional to (S)). which cancels the multiplicative correction term Equation (4).
However, sampling proportionally to leverage scores offers improves estimation quality, and is sup- ported by theoretical guarantees (Musco & Witter, 2025). Let X 2 xd' be the full deterministic matrix (each subset is sampled exactly once with probability 1). The leverage score for the row corresponding to subset S is given by
f = XP DIS (PDX [P
(8)
where (.)t denotes the pseudoinverse, and XPpls is the S-th row of XP
Theorem 4.4 (Leverage Score Sampling Guarantee (Musco & Witter, 2025)). Let e, 6 > O. When (dd log of +d' ( subsets sampled proportionally to their leverage scores (with without

---

Published as a conference paper at ICLR 2026
replacement and with without paired sampling), ot satisfies, with probability -
Σ m(S) v(S) SCD
Σ TEDUI
कF I
1D E S]
Σ m(S) SCD
((()
Σ ØT TEDUI
4 JET
JET
Musco & Witter (2025) show that Ls 1/())) for KerelSHHAP, i.e., leverage score sampling equivalent sampling subsets uniformly by their size. For the k-additive interaction frontier (introduced below), we can directly compute the leverage scores using symmetry and Equation (8), although a closed-fore form solution remains unknown. In practice, we observed little variation between leverage scores of order and those of higher orders, which is why we recommend using order-1 leverage scores.
4.4 CONSTRUCTION OF INTERACTION FRONTIERS
The interaction frontier determines the number of additional variables (columns) in the linear regression problem. Its size must be balanced against the budget (rows). Since lower-order interaction terms occur more frequently and are thus less sensitive to noise, it is natural to expand these terms first. To this end, define the k-additive interaction frontier for k = 2,..., d
A
Isa = (SC k3 with IZa
The k-additive interaction frontier includes all interactions up to order by sequentially extending the (A: 1) -additiiee interaction frontier with (%) sets. It is widely used in Shapley-based interaction indices (Sundararajan et al., 2020; Tsai et al.. 2023; Bordt & von Luxburg, 2023). In the following, refer to PolySHAP using Iga k-PolySHAP.
Corollary 4.5. The k-PolySHAP representation is equal order-k Faith-SHAP (Tsai et al., 2023).
A notable special case of S-AP is the interaction frontier without interactions: I-PolySHAP, ie., without interactions (I = 0), is equivalent to KemelSHAP.
We further show convergence for SHAP, extending Theorem 4.2 in (Pelegrina et al., 2025).
Proposition 4.6. kADD-SHIAP converges the Shupley value for k ,,...dd.
KADD-SHAP is linked to d-PolySHAP, but we recommend PolySHAP in practice, see Appendix A.4.
Partial Interaction Frontiers. high dimensions, the k-additive interaction frontier grows com- binatorially with (*) With limited evaluation budget m, including all interaction terms of given order may yield an underdetermined eqastesquares system. To address this, we introduce the partial interaction frontier I, with exactly l elements:
I = Igka UR, with [Zp
where k; is the largest order such that [I= < l, and R C Iggkesa \IEre denotes set of f [Zez interaction terms of order hū + In words, I, sequentially covers the k-additive interaction frontier up to k2. and supplements them with selected subset of the subsequent higher-order interactions. In our experiments, we demonstrate that partially including higher-ordes interactions improves ap- proximation quality, whereas using the full k-additive interaction frontier provides the largest gains.
PAIRED KERNELSHAP IS PAIRED 2-POLYSHAP
common heuristic when estimating Shapley values is to sample subsets in pairs and D S.S. A kind of antithetic sampling (Glasserman, 2004), paired sampling substantially improves the approx- imation of estimators (Covert & Lee, 2021; Mitchell et al., 2022; Olsen & Jullum, 2024). Adding higher-order interactions to PolySHAP improves Shapley value estimates, provided we have enough samples (see Figure 2): 3-PolySHAP outperforms 2-PolySHAP, which outperforms KerneISHAP (1-PolySHAP) Surprisingly, paired sampling partially collapses this hierarchy (see Figure 3).

---

Published as a conference paper at ICLR 2026
Sampling Standard Paired
Method
1-PolySHAP (KerneISHAP)
3-POlySHAP PoloySSHAP
2-PolySHAP
Blice (d - 12)
Forest id= 13)
Resiva18 (d) 14)
VIT Id- 16)
11-1
1.7-
10-1
20-4
10--
10-1
1950
2010 1091 acre
1520 sééo asce who 3528
5010 vièo who Laize (3743 DNEN
soin 10030 isien
127% (924)
(388) 124%) 1825)
Sudget (m)
Busdge
Sudget
Suddee
Cancer (dim 30)
CG60 60)
NHANES (of 79)
Crime (df 101)
35 10-01
10--
SBN
WID SEN
327
325
10--
0321 REEO 7700 19133 70000 Sudget (m)
20013 5100
3308 16000 20120
1066 20313 12333
1460) 73320 Budger (n)
0331 IE00 170903 63200 76030
Budger On)
Budger (m)
Figure 3: Approximation quality measured by MSE (+: SEM) for standard (dotted) and paired (solid) sampling, With paired sampling, KernelSHAP achieves the same performance 2-PolySHAP.
Theorem 5.1 (Paired KernelSHAP Paired 2-PolySHAP). Suppose that subsets are sampled in pairs Le., S sampled then so is its complement D \ S, and, the matrix X has full column rank for interaction frontier D and Izz. Then
S.v POLYSHAPTOSV(05-4
In words, Shapley values approximated by 2-PolySHAP are precisely the KernelSHAP estimates.
We prove Theorem 5.1 by explicitly building the approximate solutions of KerneISHAP and 2- PolySHAP. Of particular help is new technical projection lemma that also use in the proof of Theorem 4.3. See Appendix A for the details.
Generalizing Prior Work. Mayer & Wüthrich (2025) recently showed that paired KernelSHAP exactly recovers the Shapley values of games with interactions of at most size 2. This follows im- mediately from Theorem 5.1, because 2-PolySHAP will precisely a game with order-2 interactions and paired KernelSHAP will return the same solution. However, Theorem 5.1 is far more generally because explains why paired sampling performs so well for all games, not just restricted class.
Higher Dimensional Extensions. A natural question is whether similar results hold for higher-order interactions. Suppose & is odd number, find empirically that paired (k- + 1)-PolySHAP returns the same approximate Shapley values as paired k- k-PolySHAP. We conjecture that this pattern holds for all odd & such that 1 S < n. However, is not obvious how to adapt our proof of Theorem 5.1, since we would need the explicit mapping of k + 1-PolySHAP representations to k-PolySHAP representations (this is clear when is 1, but not for higher dimensions).
EXPERIMENTS
We empirically validate PolySHAP and approximate Shapley values on 15 local explanation games across 30 randomly selected instances, see Table 2. We evaluate all methods with m samples rang- ing from ++ to min(2 20000), and compare PolySHAP against Permutation Sampling (Castro et al., 2009), SVARM (Kolpaczki et al., 2024), MSR (Fumagalli et al., 2023; Wang & Jia, 2023), Unbiased KernelSHA (Covert & Lee, 2021), RegressionMSR with XGBoost (Witter et al., 2025), and KernelSHAP (1- (L-PolySHAP) with leverage score sampling (Lundberg & Lee, 2017; Musco & Witter, 2025).
For tabular datasets, we trained random forests, while for image classification we used ResNet18 18 (He et al., 2016) with 14 superpixels and vision transformers with 3x3 (ViT9) and 4x4 (ViT16) super-patches ImageNet (Deng et al., 2009), and CIFAR-10 (Krizhevsky et al., 2009). For lan- guage modeling, we used a fine-tuned Dist BBert (Sanh et al., 2019) to predict sentiment on the IMDB dataset (Maas al., 2011) with review excerpts of length 14. For tabular datasets, the games
8

---

Published as a conference paper at ICLR 2026
were defined via path-dependent feature perturbation, allowing ground-truth Shapley values to be obtained from TreeSHAP (Lundberg et al., 2020). For all other datasets, we used baseline impu- tation and exhaustive Shapley value computation. As evaluation metrics, report mean-squared error (MSE), top-5 precision (Precision @5)) 5), and Spearman correlation with standard error of the mean (SEM). Code is available https: : / / t.hub. cwm/ com/FFmgl1 PSHA, and additional details and results, including a runtime analysis, are provided in Appendix B.
PolySHAP Variants. For comparability across methods, we sample subsets using order-1 leverage scores, i.e., uniformly over subset sizes. We further adopt sampling without replace- ment and distinguish between standard and paired subset sam- pling. We apply the border trick (Fumagalli et al., 2023), re- placing random sampling with exhaustive enumeration of sizes when the expected samples exceed the number of subsets. We use K-PolySHAP with k E {1, 2, 3, 4J. and additionally the partial interaction frontiers that cover 50% of all k-order inter- actions, denoted by k-PolySHAP (50%). For high- nigh-dimensional settings, introduce PolySHAP (log) that adds d llog(()) order-3 interactions.
Table 2: Explanation games.
ID
d
Domain
Housing
8
tabular
ViT9
image
Bike
12
tabular
Forest
13
tabular
Adult
14
tabular
ResNet18
14
image
DistilBERT
14
language
Estate
15
tabular
Higher-order Interactions Improve Approximation. Fig- ure 2 reports the MSE with SEM for selected expla- nation games and standard sampling. Across different games, we observe that incorporating higher-order interactions
VIT16
16
image
CIFAR1O
16
image
Cancer
30
tabular
CG60
60
synthetic
IL60
60
synthetic
in PolySHAP consistently improves approximation quality. However, higher-order PolySHAP requires a larger sampling budget, and hence performance is only plotted for m 2 d'. Nevertheless, 2-Po and even partial interaction inclu- sion (e.g.. 2-PolySHAP at 50%), still yield notable improve- ments in approximation accuracy.
NHANES
79
tabular
Crime
101
tabular
Paired KernelSHAP is 2-PolySHAP. As shown Theorem 5.1, under paired sampling, Ker- nelSHAP and 2-PolySHAP are equivalent indicated by the overlapping lines. We confirm this empirically in Figure 3. However, there is an important distinction: 2-PolySHAP requires more budget, whereas KerneISHAP can be computed already with d + 1 samples. Lastly, observe a similar pattern for 3-PolySHAP: Under paired sampling 3-PolySHAP substantially improves its approximation quality and is equivalent 4-PolySHAP.
Practical Benefits of PolySHAP. In practice, we adopt paired sampling and benchmark PolySHAP against all baselines in Figure 4 and Figure 7 in Appendix B.2. Because of our paired sampling result, the practical benefits of PolySHAP become apparent only when order-3 interactions are Hous-
included. In low-dimensional settings, the 3-PolySHAP yields the best performance ing, Adult, Estate, Forest, and Cancer datasets (see c.g., Figure 4 and Figure 7). In budget- restricted cases, partially incorporating order-3 interactions already provides substantial gains, ef. 3-PolySHAP (50%) and 3-PolySHAP (log). In high-dimensional settings (d 2 60), however, only small number of order-3 interactions can be added, resulting in more modest improvements. Among all baselines, only RegressionMSR achieves comparable performance, although its performance de- pends strongly on XGBoost, as indicated by its poor results on CG60. Moreover, RegressionMSR has an inherent advantage since all tabular games rely on tree-based models.
7 CONCLUSION & FUTURE WORK
By reformulating the computation of the Shapley value as a polynomial regression problem with selected interaction terms, PolySHAP extends beyond the linear regression framework of Ker- nelSHAP. We demonstrate that PolySHAP provides consistent estimates of the Shapley value (The- orem 4.3), and produces more accurate Shapley value estimates (see Figure and Figure 3). More- over, show that paired subset sampling in KemnlSSHA (Covert & Lee, 2021) implicitly captures all second-order interactions at no extra cost (Theorem 5.1), explaining why paired sampling im- proves estimator accuracy on games with arbitrary interaction structures.

---

Published as a conference paper at ICLR 2026
Sampling Paired
Methed
Pormutation Sampling
MSR SVARM
RegressionM5R
3-FolySHAP (log)
3-PolySHAP
Urbbssedeenellsttl
1-PolySIAP (KerneSHAPP)
3-PalySHAP (50%)
(dl
Forest
ResNet18 14)
VIT16ld-16)
20
10--
MIE
20
460
1660
3000
1203 8040
1523 1e60 #550 6000 7548
5031 seEn who 1355e S4AM Sudget (P)
4:00 5030 12530 Frde 20020
Dudget (m)
Budgee (nI
Budget (n)
(d 301
CC66
NHANES
101)
VILE SIN
20
5353 8000 32000 18033 20000 Budgee (m)
4000 5005 20000 18000 25300
4000 8053 32203 5800 23320 Budge (n)
4207 0000 32000 15500 2003
Budger (m)
Buddee (m)
Figure 4: Approximation quality of PolySHAP variants and baseline methods measured by MSE (# SEM) using paired sampling. With paired sampling, PolySHAP consistently improves upon KerneSSHAP when order-3 interactions are included. In higher dimensions (d 2 60), only a few of these can be modeled, yielding smaller improvements.
Future work could explore more structured variants of interaction frontier, for example by detecting important interactions (Tsang al., 2020) or leveraging inherent interaction structures in graph- structured inputs (Muschalik et al., 2025). In addition, we empirically find that paired k-PolySHAP produce the same estimates (A: + 1)-PolySPPA for odd l 1, but leave the proof for future work.
ETHICS STATEMENT
This work introduces a framework for efficient approximation of Shapley values, which are primarily used for explainable AI. We do not see any ethical concerns associated with this work.
REPRODUCIBILITY STATEMENT
Our implementation is built upon the shapiq (Muschalik et al., 2024) library. We extend this framework with the PolySHAP and Regressi innsssionsss approximator classes, which include op- timized sampling strategies within the CoalitionSampler class. All technical details can be found in Section 6 and Appendix B. The code for reproducing the experiments is available at https://g com/ wtt./////g////oys/aa/ We will soon add our methods to shapiq.
ACKNOWLEDGMENTS
Fabian Fumagalli gratefully acknowledges funding by the Deutsche Forschungsgemeinschaat (DFG, German Research Foundation): TRR 318/1 2021 438445824. Christopher Musco supported by NSF Award #2045590.
REFERENCES
Sebastian Bordt and Ulrike von Luxburg. From Shapley Values to Generalized Additive Models and back. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 709-745, 2023.
Landon Butler, Abhineet Agarwal, Justin Singh Kang, Yigit Efe Erginbas, Bin Yu, and Kannan Ramchandran. Proxyspex: Inference-efficient interpretability via sparse feature interactions in 1lms. CoRR, abs/2505.17499 2025.
Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the Shapley value based on sampling. Computers & Operations Research, 1736:1122133300 2009. doi: 10. 1016016/j.com 2008.04.004.
10

---

Published as a conference paper at ICLR 2026
Javier Castro, Daniel Gómez, Elisenda Molina, and Juan Tejada. Improving polynomial estima- tion of the Shapley value by stratified random sampling with optimum allocation. Computers & Operations Research, 82: $2:180-188, 2017. doi: 10.1016fj.co:2211.01.000
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 785-794. ACM, 2016. doi: 10.1 10.11455299997722333777
Paulo Cortez and Aníbal de Jesus Raimundo Morais. A data mining approach to predict forest fires using meteorological data. New Trends in Artificial Intelligence, Proceedings of the 13th EPIA, pp. 512-523, 2007.
lan Covert and Su-In Lee. Improving KemelSHAP: Practical Shapley Value Estimation Using Lin- ear Regression. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3457-3465, 2021.
Ian Covert, Scott M. Lundberg, and Su-In Lee. Understanding Global Feature Contributions With Additive Importance Measures. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2020.
lan Covert, Scott M. Lundberg, and Su-In Lee. Explaining by Removing: A Unified Framework for Model Explanation. Journal of Machine Learning Research, 22(209):1-90, 2021. doi: 10.5555/ 3546255.3354645
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pp. 248-255, 2009.
An Dinh, Stacey Miertschin, Amber Young, and Somya D. Mohanty. A data-driven approach to predicting diabetes and cardiovascular disease with machine learning. BMC Medical Informatics Decisision Making, 19(1):211:
2019. doi: 11116//12911-01-90115
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
H. Fanace-T and J. Gama. Event Labeling Combining Ensemble Detectors and Background Knowl- edge. Progress in Artificial Intelligence, 2(2): 2014. doi: 1111007//13748-01--00000
Matthias Feurer, Jan N. van Rijn, Arlind Kadra, Pieter Gijsbers, Neeratyoy Mallik, Sahithya Ravi, Andreas Mueller, Joaquin Vanschoren, and Frank Hutter. OpenML-Pythhon an extensible Python API for OpenML. CoRR, abs/1911 0ts/1911.02490, .02490, 2020.
Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Ham- mer. SHAP-IQ: Unified Approximation of any-order Shapley Interactions. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2023.
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), pp. 5140-5148 2025.
Amirata Ghorbani and James Y. Zou. Data shapley: Equitable valuation of data for machine learn- ing. In Proceedings of the International Conference on Machine Learning (ICML), pp. 2242- 2251,2019
Paul Glasserman. Monte Carlo Methods Financial Engineering. plied Probability. Springer, 2004. doi:
Stochastic Modelling and Ap-
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-56) 1999. doi: 10. 10.1007/s001 820050125.
11

---

Published as a conference paper at ICLR 2026
Michel Grabisch, Jean-Luc Marichal, and Mare Roubens. Equivalent representations of set func- tions. Mathematics of Operations Research, 25(2):157-178, 2000. doi: 10.12287/m0o2252..157. 12225.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Justin Singh Kang, Yigit Efe Erginbas, Landon Butler, Ramtin Pedarsani, and Kannan Ramchan- dran. Learning to understand: Identifying interactions via the möbius transform. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2024.
R. Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33(3):291-22 297, 1997. doi: 10. 10.0016601667777529900044444
Gwladys Kelodjou, Laurence Rozé, Véronique Masson, Luis Galárraga, Romaric Gaudel, Maurice Tchuenté, and Alexandre Termier. Shaping up SHAP: enhancing stability through layer-wise neighbor selection. Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan (eds.), Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 13094-13103, 2024.
doi: 10.
R. Kohavi. Scaling up the accuracy of naive- bayee classifiers: A decision-tres hybrid. In Proceed- ings of International Conference on Knowledge Discovery and Data Mining (KDD), pp. 202-207, 1996.
Patrick Kolpaczki, Viktor Bengs, Maximilian Muschalik, and Eyke Hüllermeier. Approximating the shapley value without marginal contributions. In Proceeedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 13246-13255, 2024.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical Report, 2009.
Yongchan Kwon and James Zou. Beta shapley: unified and noise-reduced data valuation frame- work for machine learning. In Proceedings of the International Conference on Artificial Intelli- gence and Statistics (AISTATS), pp. 8780-8802, 2022a.
Yongehan Kwon and James Zou. Weightedshap: analyzing and improving shapley based feature attributions. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2022b.
Weida Li and Yaoliang Yu. Faster approximation of probabilistic and distributional values via least squares. In Proceedings of the International Conference on Learning Representations (ICLR), 2024.
Scott M. Lundberg and Su-In Lee. A Unified Approach to Interpreting Model Predictions. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 4765-4774, 2017.
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 Al for trees. Nature Machine Intelligence, 2(1):56-67, 2020. doi:
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 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (HLT), pp- 142-150, 2011.
Michael Mayer and Mario V Wüthrich. Shapley values: Paired-sampling approximations. CoRR, abs/2508.1 0...508..19477 12947, 2025.
Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling Permutations for Shap- ley Value Estimation. Journal of Machine Learning Research, 23(43): 2022.
12

---

Published as a conference paper at ICLR 2026
Majid Mohammadi, Ilaria Tiddi, and Annette ten Teije. Unlocking the game: Estimating games in möbius representation for explanation and high-order interaction detection. In Proceeedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 19512-19519, 2025. doi: 10. 10.1609/ (AA1139118.3411
Christoph Molnar. Interpretable machine learning: guide for making black box models explain- able. Leanpub, 2024.
Maximilian Muschalik, Hubert Baniecki, Fabian Fumagalli, Patrick Kolpaczki, Barbara Hammer, and Eyke Hüllermeier. shapiq: Shapley Interactions for Machine Learning. Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 130324-130357, 2024.
Maximilian Muschalik, Fabian Fumagalli, Paolo Frazzetto, Janine Strotherm, Luca Hermes, Alessandro Sperduti, Fyke Hüllermeier, and Barbara Hammer. Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks. In Proceedings of the Conference on Learning Representations (ICLR), 2025.
Christopher Musco and R. Teal Witter. Provably Accurate Shapley Value Estimation via Leverage Score Sampling. In Proccedings of the International Conference on Learning Representations (ICLR), 2025.
Lars Henry Berge Olsen and Martin Jullum. Improving the sampling strategy in kernelsha,, 2024.
Lars Henry Berge Olsen, Ingrid Kristine Glad. Martin Jullum, and Kjersti Aas. A comparative study of methods for estimating model-agnostic Shapley value explanations. Data Mining and Knowledge Discovery, pp. 48, 2024.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake VanderPlas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duch- esnay. Scikit-learn: Machine learning in python. Journal of Machine Learning Research, 12: 2825 2825-2830, 2011. doi: 11.5555/1953048.20
Guilherme Dean Pelegrina, Leonardo Tomazeli Duarte, and Michel Grabisch. A k-additive choquet integral-based approach to approximate the SHAP values for local interpretability in machine learning. Artificial Intelligence, 325:104014, 2023. doi: 10..016.J.ATTIIT.20033 1040444
Guilherme Dean Pelegrina, Patrick Kolpaczki, and Eyke Hüllermeier. Shapley value approximation based on k-additive games. CoRR, abs/2502.04763, 2025.
Michael Redmond. Communities and crime unnormalized, 2011.
Gian-Carlo Rota. On the foundations combinatorial theory: I. theory of möbius functions. In Classic Papers in Combinatorics, pp. 332-360. Springer, 1964.
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.
L. Shapley. A Value for n-Person Games. In Contributions the Theory of Games (AM-28), Volume I1, pp. 307-318. Princeton University Press, 1953.
W Nick Street, William H Wolberg, and Olvi L Mangasarian. Nuclear feature extraction for breast tumor diagnosis. In Biomedical image processing and biomedical visualization, volume 1905, pp. 861-870, 1993.
Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The Shapley Taylor Interaction Index. In Proceedings of the International Conference on Machine Learning (ICML), pp. 9259- 9268, 2020.
Che-Ping Tsai, Chih-Kuan Yeh, and Pradeep Ravikumar. Faith-Shap: The Faithful Shapley Interac- tion Index. Journal of Machine Learning Research, 1 12: 2023.
Michael Tsang, Sirisha Rambhatla, and Yan Liu. How does This Interaction Affect Me? Inter- pretable Attribution for Feature Interactions. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 6147-6159, 2020.
13

---

Published as a conference paper at ICLR 2026
Jiachen T. Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learn- ing. In Francisco J. R. Ruiz, Jennifer G. Dy, and Jan Willem van de Meent (eds.), Proceedings of the International Conference Artificial Intelligence and Statistics (AISTATS), pp. 6388-6421, 2023.
R. Teal Witter, Yurong Liu, and Christopher Musco. Regression-adjusted monte carlo estimators for shapley values and probabilisticc values. CoRR, abs/2506. 11849, 2025.
I-Cheng Yeh and Tzu- "'uu-uang Hsu. Building real estate valuation models with comparative approach through base reasoning. Appied Soft Computing, 65:260-271, 2018, doi: 10.1016/..SOC. 2018.01.029.
14

---

Published as a conference paper at ICLR 2026
CONTENTS OF THE APPENDIX
A Proofs
16
A.I Projection Lemma
16
A.2 PolySHAP is Consistent
17
A.3 Paired KemelSHAP Paired 2-PolySHAP
18
A.4 k-ADD-SHAP Converges to the Shapley Value
21
Experimental Details and Additional Results
24
B.1 Experimental Details
24
B.2 Additional Results on Approximation
MSE ................................
25
B.3 Approximation Quality using Precision@5...
27
B.4 Approximation Quality using Spearman Correlation
28
B.5 Runtime Analysis
31
B.6 Additional Tables
34
C Usage of Large Language Models (LLMs)
35
15

---

Published as a conference paper at ICLR 2026
A PROOFS
A. PROJECTION LEMMA
We introduce the following technical lemma that will be useful in the proofs of Theorem 4.3 and Theorem 5.1.
Lemma A.1 (Projection Lemma), Letn 2 d4 > d. Consider a matrix X E Raxd full column rank, vector R and real number RR Let X E Buxxd be matrix where the first d columns are equal to X. Define
34=
arg min 3ER 1 (33,1a_]]
| y112.
Then
arg min (611:(
|XB y112
arg min
X3 X,
(9)
Proof of Lemma A.I. We will first reformulate the constrained least squares problem as an uncon- strained problem. Let Pa be the matrix that projects off the all ones vector in d dimensions i.e., PL, 1ala" T. Similarly, let Pd. = =I à lala In general, we will drop the subscript
when the dimension is clear from context. We have
2
argmin 3e (
XB - -
arg min (8.1)
X8 + X1
3/1
+1
d
d
2
P Paargun min
XP X1
y
+
2 d
BERd
Pa(XP.) (y- x1x -
(10)
where the (.)t denotes the pseudoinverse, and the last equality follows by the standard solution to an unconstrained least squares problem. Similarly,
x arg min
| -yl1 Pa (x-x,1
x,,1
e +1 c
+
(11)
d+
d+
BER - (3,114)-
Let projxP, = (XP (XP))(XP))) a) be the projection onto XP We have
X arg min If)
|83 - x 3 XXP((Pa)) -x1 x1 d
= projxpp
X4 Pa (XPa+)
(y-
+ +1 xxxx11))
x1 + xx1 c
d+
projxp,,rooxxpoo
proix, x d+
+ projxp, x,
projxp, XI + XI + (12)
d+
d'
Since the column space of XPa is contained in the column space of X.Pa, observe that proix,,, projxp.- Then
(12) = projxp,, prujxp,,Xi X1- + X1 c d
XPa (y-x1 - X1 d
d)
X arg min |XG y (p,10
(13)
Since X has full column rank, we have X I, so multiplying on the left by Xt yields the statement.
16

---

Published as a conference paper at ICLR 2026
A.2 POLYSHAP IS CONSISTENT
In this section, we will prove Theorem 4.3.
Theorem 4.3. The Shapley values of v are recovered from the PolySHAP representation as
$ T of +
for E D.
(3)
S|
SEZNES
Proof of Theorem 4.3, Recall d' = d + [Z]. Define the target vector y E R² so that [yss
V Vu(S) (u(S)-v(55) v(e).. Define the design matrix X E R xd so that
8 v (S)) 1 S).
(14)
and the extended design matrix X E 1R=2 xd'
so that
[x+1sT= = 1[ _ S].
(15)
for T E DUI.
In this notation, we may write
B [1]
arg min (E)=((,))=V(()
X y11..
(16)
and
arg min &ERd' (cR)"'((,))=u((D))
| - -
(17)
Consider the game à :2 RR where
D(S)=
Σ (T...
(18)
TEDUZ-TCS
For this game, the target vector is given by ÿ = X $ [v]. Then its Shapley values are given by
T [
arg min
|X r11
(E34:(1.0)=
arg min
|X X x 1=1
(1, =L,))=((D)
argmin
[X y11
(c
SB [v].
(19)
where the penultimate equality follows by Lemma A.1. All that remains to compute the Shapley values D. Since we have an explicit representation of in terms of its Möbius transform in Equa- tion (18), we know its Shapley values are
Σ
P T
(20)
TEDUZHET
by e.g., Table 3 in Grabisch et al. (2000). The statement follows.
17

---

Published as a conference paper at ICLR 2026
A.3 PAIRED KERNELSHAP PAIRED 2- E-POLYSHAP
We introduce some helpful notation, and then use it to restate Theorem 5.1 more formally below.
Define dy -ビ (0) Let X R (2) be the matrix where the E, T entry is given by
Vu(S)
[[ S S.]]
(21)
vp((s)
where St S D is the 7th sampled subset, and T S D such that [T] = k. Then the matrix Xgg Rmxds is given by
x= X1
X
(22)
Let M Radxda be the matrix that projects a 2-PolySHAP 1-PolySHAP. The entry corre- sponding to i E D, and S C D such that [S| S 2 is given by
M = 1 S
(23)
[S]
Theorem A.2 (Paired KernelSHAP is Paired 2-PolySHAP). Suppose X has full column rank. Further, suppose that both I-PolySHAP and 2-PolySHAP are computed with the same paired sam- ples i.e., if S sampled then is complement S. Then
arg min (Lad:(La,))=010
||X
- - = M2-11 arg min
|| - 8112-
(24)
dERd2:(1a, ()) =))(()
In words, the Shapley values of the approximate I-PolySHAP exactly the same those of the approximate 2-POLySHAP.
Proof of Theorem A.2. Define
vDD)
+ 1dg
arg min
[ 812
(25)
d2
where ž is orthogonal to the all ones vector. By Lemma A.1 and the structure Ag2 we have
[A
A2).
v(D)
arg min $ (1. ()x())
| 812
arg min () =)((
x X
1 1dz
(26)
d2
Using Equation 10, we can write Equation 26 explicitly as
v(D) d2
X11a -x,1
v(D)
v(D)
(26) = P.
P
X
à + laz
+ ld
(27)
d
d
where P. 1 111 T is the matrix that projects off the all ones direction in d dimensions.
Our goal to show that
r(D)
(27) M 1 1dz
(28)
d2
We'll begin with the all ones component. Observe that
v(D)
v(D)
1 E T]
1+ d-1
v(D)
M, M
Σ 1 1i=11 1 Σ
=v(D)
d
d2
2
d (d)
d
TED: -
so M2
1ds
v(D) de
1 DDD
Now remains show the equality for the component orthogonal the all ones direction. Since
X X
X1 X2] has full column rank by assumption, X, must have full column rank well.
18

---

Published as a conference paper at ICLR 2026
follows that X (PaX (xXXXX,Pa) Pa), it suffices to show that
Pa. Then, after multiplying Equations 27 and 28 by
v(D)
P(D)
X P P
X 52 2
2+1ds
1, v(D)
d2
d
P X
Pa
8
52
x
(29)
d2
We will first show that the second term on the right hand side is 0. First, notice that
Lklld =
E
VAS
1T ITCS) S]
vPs
S
(30)
VPs
VPs
TED:TISK
where |SIx = E/= (2)). Then
SSk
X X 1a.k
Σ
(31)
dx
Ps ds
S:ES
We have
18l2
(
51)
1S 1+18
|1|
11 d+1
Together,
d2
d+(+)
d 1+(d-1)/2
x E Jz
x 1117
Σ
Us
[ + d+1 d+1
Ps
d+1)
SHES
us |S]([S d)
d(d + 1)
SHES Ps
1
k9 S|([S))
(32)
2d(d+1)
Ps
where the last equality follows because the subsets are sampled paired complements. particular, for given pair S and D \ S, the item i is in exactly one of them, and the coefficient | [S]([S) d) the same for both. We have shown that every entry is the same, i.e., scaling of so Pa projects off the entire vector.
ps
Finally, it remains to show that
P x22
(33)
is easy to verify that (1d, Mτ) = =1,
= 0, so P = M2-11 Therefore, suffices to
prove that P.X M2 = P X52.
Notice that X X1lis = EsHEs,es
ay ps
where i,j E D. Then
[ E R
X, X,
Σ
R
Ps
SaES,jes
d
SS
ps
R
SHES
j=L:ESSER
Ps RNS
(34)
Ps
R
SaES
Meanwhile,
Σ
PS Ps
(35)
SHES,
Clearly, Equations (34) and (35) are equal when [ have
= 1. Now consider the case when R = 2; we
(34)
Σ
Ms 1
+
Σ
Ms
1
Ps
(36)
Ps R
2
Ps
4
Ps
Ps
S
Bas
19

---

Published as a conference paper at ICLR 2026
where the last equality follows by sampling in paired complements. In particular, exactly one of the paired samples S and D S will contain item i, and the coefficient (Ag/Ps the same for both. Finally, because its the same for all the projection Pa eliminates the first term. The statement follows.
20

---

Published as a conference paper at ICLR 2026
A.4 WAAD--SAL CONVERGES THE SHAPLEY VALUE
In this section, we prove Proposition 4.6 and discuss the differences between PolySHAP and KADD" SHAP, and its practical implications. We generally recommend prefer PolySHAP over kADD" SHAP.
Proposition 4.6. KADD-SHAP converges to the Shapley value for k = l,...,d. d.
Proof. The KADD approximation algorithm (Pelegrina et al., 2023) is based on the interaction repre- sentation (Grabisch al., 2000) of v given by
(SS)
Σ TCD
|r| Snry (T)( with 7f
Σ
B B
where B, are the Bernoulli numbers and [sh the Shapley interaction index (Grabisch & Roubens, 1999) with
Thn (s)
E TEDSS (d- |S| 1)(2-19) LCS
Σ
The Shapley interaction index generalizes the Shapley value to arbitrary subsets, and it holds S [w] (i) for all D. The SADD approximation algorithm then restricts this rep- resentation to interactions up to order k.
Definition A.3 (KADD SHAP (Pelegrina et al., 2025)). The KADD SHAP algorithms solves the con- strained weighted least- squs-ss problem
kano = arg min
Σ (()) u(S)
E
TI SSTY
IT
Et (+) SCD
TED:TTSK
s.t. D (DD) - v(0) = Σ
70
Ir.
TCD
In practice, the least-squares objective is approximated and solved similar to KernelSHAP (Lund- berg Lee, 2017), and the Shapley value estimates that are output are Thane for E D from the approximated least-squares system.
Our first observation is that the output 4; is the Shapley value of the approximated game, i.c.
1VS Σ
IT| 4. WieeT
TED:VISK
will show that the Shapley values of this approximation are the Shapley values the PolySHAP representation &= which then are equal to the Shapley values of by Theorem 4.3.
contrast to PolySHAP, SAPD-SHAP fits a coefficient for the empty set de. However, we may rewrite
2
((S)
Σ
IT Snzzy
IT
((() -00
Σ
IT
TED.TISR
TCD:0<ITISk
and thus In is an additive shift of v, which does affect the Shapley values of the approximation, i.c.
Σ
IT SnT [T]
Σ
S [T].
TSR
TEDE
SI
Moreover, compute 76 B, and
21

---

Published as a conference paper at ICLR 2026
(0)
s-1
7/3
Σ
B
Σ
Σ
Be B, 1[s 1] + Bs,
==
t=)
by the recursion of Bernoulli numbers, and thus
Σ
(11s) - 70
181
1s
Σ SED
SCD.SSisk
which is already mentioned by Pelegrina et al. (Prof) of Theorem 4.2]. Now, without loss of generality, we can assume that v0) 0, since does not affect the Shapley values of v, and thus the class of approximations is given by
F.ADD S SH
| JT o E gd+lZesl and Σ4= TED
Σ
IED
Lemma A.4. There is an equivalence between the function class Fhano and the class of functions of PolySHAP representation with interaction frontier Isk, i.e.
F ( { SH Σ Φ II
1i e o Idl and (0, 1) =b)))))())))))))))))))) U(D) }
TEDuIck
JET
Proof. For the game v there exist the two equivalent representations (Grabisch et al., 2000)[ and 4]
v(S)
Σ IT
Ish with 7/ Σ Bi-c.
TED
where Ish is the Shapley interaction index (Grabisch & Roubens, 1999). and the Möbius represen- tation
M(S)
Σ m(S)
II
L e S] with m(S) = Σ (-11)51144
TCD
JES
LCS
Moreover, there exist the two conversion formulas (Grabisch et al., 2000) Table and 4]
(S)
Σ T - S| - (T) and m(S) = Σ
B (T))
TED:22
TED:T3S
From the conversion formulas it is obvious that
(S) 0, AA C D |S
m(S), DS
Hence, restricting the interaction representation to order k yields the same function class as restrict- ing the Möbius representation order k. Moreover, the constraints similarly converted, which proves the equivalence.
Utilizing Lemma A.4, we obtain that for
2
1000 = arg min
Σ M(S)
v(S)
Σ
S IT
2
Ee (1) SCD
TED:ITISK Sk
s.t. v(D)
Σ SED
we have equivalence between the approximations
Σ
IT' Sser
1
ADD
Σ
I's OT
II jET
L S].
TCD
DEDUIER
22

---

Published as a conference paper at ICLR 2026
where ØT the PolySHAP representation, due the equivalent function classes parametrized by the vectors Ao and ø=st By Theorem 4.3, we know that the Shapley values of this approximation are equal to the Shapley values v, and hence, have
ADD I
Σ
1 Msse 1
SV Oi
Σ
Minry -
Ti
ADD = [1],
TED:TTSK
TCD:TTSK
which concludes the proof and show convergence of KADD-SHAP the Shapley value.
Practical difference between S and PolySHAP. In contrast to PolySHAP, kADD- SHAP was proposed for k-additive interaction frontiers. Moreover, the design matrix of -SDD- less intuitive, making the PolySHAP formulation a simpler and more transparent alternative. More importantly, ta key practical difference arises from our use of the modified representation L as an intermediate step in the proof. While to and R yield the same Shapley values when all sub- sets are evaluated, they diverge under approximation. In particular, unlike PolySHAP, -HAP affected by the value of v(0), and its least-squares fit includes an additional variable. For these reasons, recommend PolySHAP in practice over SAAP-SHAP.
23

---

Published as a conference paper at ICLR 2026
Table 3: Datasets used for tabular explanation games
Name (ID in bold)
Reference
License
Source
California Housing
(Kelley Pace & Barry, 1997)
Public Domain
sklearn
Bike Regression
(Fanaee-T Gama, 2014)
CC-BY 4.0
OpenML
Forest Fires
(Cortez & Morais, 2007)
CC-BY 4.0
UCI Repo
Adult Census
(Kohavi, 1996)
CC-BY 4.0
OpenML
Real Estate
(Yeh & Hsu, 2018)
CC-BY 4.0
UCI Repo
Breast Cancer
(Street al., 1993)
CC-BY 4.0
shap
Correlated Groups (CG60)
synthetic
MIT
shap
Independent Linear (IL60)
synthetic
MIT
shap
NHANES I
(Dinh et al., 2019) (Redmond, 2011)
Public Domain
shap
Communities and Crime
CC-BY 4.0
shap
B EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
In this section, we provide additional details regarding our experiments and the local explana- tion game setup (Appendix B.I) with additional results the remaining games using MSE (Ap- pendix B.2), Precision@5 @5 (Appendix B.3), and Spearman correlation (Appendix B.4). Lastly, we report results of the runtime analysis (Appendix B.5).
B. EXPERIMENTAL DETAILS
All experiments were conducted on a consumer- grade laptop with an 11th Gen Intel Core 17-11850H CPU and 30GB of RAM, where we used cuda? on NVIDIA RTX A2000 GPU for inference of the CIFAR10 game.
Non-tabular Datasets. We used the 30 pre-computed games provided by the shapig benchmark for the ResNET18 (He et al., 2016), and the vision transformers pre-trained on ImageNet (Deng et al., 2009). We used the pre-computed language game using DistilBERT (Sanh al., 2019) model and sentiment analysis on the IMDB dataset (Maas et al., 201 1) from the s shapic bench- mark. Lastly for the CIFAR1O game, we used vision transformer (vit-base-patchh paase-patchl6-224-1 6--22--in21k) (Dosovitskiy et al., 2021) fine-tuned on CIFARIO (Krizhevsky et al., 2009), which is publicly avail- able?.
Datasets. The datasets and their source used for the tabular explanation games are described in Table 3. The Forest Fires and Real Estate were sourced from UCI Machine Learning Repository (UCI Repo), whereas Bike Regression was taken from OpenML (Feurer et al., 2020). The Cali- fornia Housing dataset sourced from scikit-lear (Pedregosa et al., kklaarn) and the remaining datasets were sourced from the shap library.
configuration. We use the standard implementation for RandomForestRe Rttooreetteerrsorrrrr and RandomF orestClassi fier from scikit-leame (Pedregosa et al., 2011) with 10 tree instances of maximum depth 10 and fit the training data using accuracy (classification) and Fl-score (regression). For all datasets, 80 80/20 percent train-test-split was executed.
Random forest
RegressionMSR. For the RegressionMSR approach, XGBoost (Chen & Guestrin, 2016) with its default configuration as a tree-based backbone combined with the MonteCarlo approxi- mator (equivalent to MSR (Witter et al., 2025)) from the shapig package.
24

---

Published as a conference paper at ICLR 2026
Sampling
Method
Standard
I-PolYSHAP (KemelSHHP))
2-PolySHAP (50%)
3-PalySHAP (50%)
4-PolySHAP
PolySHAP
3-PalSSHAP
Housing (d'=
VITA (dim
Adull (d - 14)
DistIBERT (dim
16-1
15:
(389%) (371)) 29290 (3398) (999)
(345) (774) 100M (7890 1929)
Budges
Budges
Budget
Budget (9)
Estate (d 15)
CIFAR: 10 VIT26 (d 16)
1L50 (d 60)
30-1
20-1
(3.0%)
2245) 13/91 14336 1637)
29:43 (1216) 130
(206) 131%)
1-130 1-330) 1-1%) 16 (41
Figure 5: Approximation quality measured by MSE (# SEM) for varying budget (m) remaining explanation games. Adding interactions in PolySHAP can substantially improve approximation quality
MSR and Unbiased KernelSHAP. Fumagalli et al. (2023, Theorem 4.5) established that MSR (Wang & Jia, 2023) is equivalent to Unbiased KerneSSHAP (Covert & Lee, 2021). We use the implementation of Unbiased KernelSHAP provided in the shapiq q package.
SVARM Shapley Value Approximation without Requesting Marginals (SVARM) was proposed by (Kolpaczki et al., 2024) and uses stratification of MSR (Castro et al., 2017). We use the imple- mentation SVARM provided in the shapiq q package.
B.2 ADDITIONAL RESULTS ON APPROXIMATION QUALITY USING MSE
In this section, report approximation quality measured by MSE for the remaining explanation games.
Figure 5 reports the MSE for the Housing, VIT9, Adult, DistilBERT, Estate and IL60 explanation games. Similar to Figure 2, we observe that PolySHAP's approximation quality substantially im- proves with higher-order interactions. Again, this comes at the cost of larger budget requirements, indicated by the delay of the line plots. The Permutation Sampling and KernelSHAP (I-PolySHAP) baseline are consistently outperformed by higher-order PolySHAP, while RegressionMSR yields comparable results.
Figure 6 shows the approximation quality of PolySHAP with and without (standard) paired sub- set sampling. Similar to Figure 3, we observe a strong improvement of 1-PolySHAP due to the equivalence 2-PolySHAP. The same observation holds for 3-PolySHAP.
25

---

25000 Published as a conference paper at ICLR 2026
Sampling
Method
Standard
1-PolySHAP (KernelSHAP)
PolySHAP 4-PolySHAP
Paired
2-PolySHAP
Heusing (d'=
VIT9 (dim 9)
Adullt (d 144)
DistiBBRT (di 14)
10"
55-+
30
10-m
118% (37%)) 1979)
17355 (929)
(38 (244) ISON) (1800) 1925)
Estate (d 15)
AR-10 VIT16 (d'= 16)
IL60 (d = 60)
100
30--
130-
20-4
10-1
4003
8000
13000
10353
30000
4000 8300 33000 30030 2E0CO
4000 0003 12003 .0000 23350
Buages (1)
Figure 6: Approximation quality measured by MSE (# SEM) for standard (dotted) and paired (solid) sampling for remaining local explanation games. Under paired sampling, 2-PolySHAP marginally improves, whereas KemelSHAA substantially improves due to its equivalence to 2-PolySHAP.
Sampling
Method
Faired
Fermutation Sampling
NSR SVARM
RegressioMMSR L-PolSSHAP (KamalSHAP)
PHAYSHAP
3-PolSSHAP
UntiasedkemeSillP
PoPoyS (50%)
Heusing (d'=
VIT9 (d- 0)
Adult (d - 14)
DistiBBERT (di- 14)
10-
15
85
10--
30
10--
4015
3180 soto 5000
118%C (37h)) (95A) 1738) (929)
(3. (374) (7850) 1628)
Estate (d 151
AR-10 VIT16 (d 16)
IL60 in 60t
3.7
107
10-1
U00 STM
20-
10
20-4
4383 8500 12000 20033 20000 Sudget (m)
4000 E300
.3500 10030 Budpes (ml
4500 0033 12300 -6000 Budges (m)
Figure 7: Approximation quality of PolySHAP variants and baselines measured by MSE (+ SEM) for paired sampling for remaining local explanation games.
26

---

Published as a conference paper at ICLR 2026
Sampling
Method
Standard
I-PolySHAP (KemelSHHP)
2-PolySHAP (50%)
3-PalySHAP (50%)
4-PolySHAP
P-PolSSHAP
P-lySSHAP
Housing (d=0)
VITA (di 9)
Bike (di 12)
Forest (d' 13)
1.30
1.04
1.10
0.90
2:40
3.40
3.40
0.00
2.02
2.00
0.00
6.78
(2636) (D91)) (246)) (799) (965)
(19181 (174) (77M) (7940 1929)
Budges 6nl
Budges
Busgett
Budget (9)
Adult to 14)
18 (d= 24]
DisBIBERT (d 14)
Estate id 15)
3.00
2.07
1.00
0.00
5.90
3.90
0.50
0:85
0.00
0.36-
3,03
0.00
0.75
(3.54)
(33 F75% 192%)
(309) (171115550 179% 1928)
130R) (371))33311 15550 1736) 1924))
(3.%%) 1200/
1975)
169 (835))
VITI6 ld 16)
CIFAR-10 VIT16 (6 16)
Cancer (3 - 30)
CG60 (dl -
3.00
3,02
1.07
1.00
6.45
3.444
0.46
6.96-
3.00
3.00
6.03
2.00
3.00
0.00
6.75
5.75
3.75
0.75
Are0
12500 16:03 zelen
C00 8200 1250n 160.39 zcicn
6500 0953
12003
Heen 23100
6205
12000
(8%6
1233)1 (30%) (24%) 1315)
1950 (12%) 130% (295) 1318)
(c18) (c2 (45)) (6230 (<15)
[-155] 1-175)
(42N6 (42%)
Budgee
1160 (d 60)
NHANES fd' 79)
Crime 101)
2.06
1.03
8.35
2.05
3.05
6.78
4307 8500 33000 10227 20000
4000 0207 -2300 3800
25300
4506 9000 12307 28000 22320
Sudget (m)
Budgee: Oml
Budget On)
Figure 8: Approximation quality measured by Precision (= SEM) for varying budget (m) on different games. Adding interactions in PolySHAP can substantially improve approximation quality
B.3 APPROXIMATION QUALITY USING PRECISION@5
In this section, report approximation quality with respect to top-5 precision (Precision@) for all explanation games from Table 2.
In Figure 8 that higher-order interactions also improve the approximation quality regarding the Pre- cision@5 metric. However, the distinction is not as clear as for MSE, since ranking is not con- sidered in the optimization objective. In general, the approximation quality varies across different games, where the low-dimensional tabular explanation games show very good results, in contrast to the more challenging con-tabular games (ViT9, DistilBERT, ResNet18 and VIT16), and high- dimensional games (CG60, IL600 NHANES, and Crime), which require more budget for similar results.
In Figure 8 Precision@5 5 is compared for standard sampling and paired sampling. Again, we observe improvements for 1-Poly and 3-PoySSHAP when using paired sampling due its equivalence to 2-PolySHAP and PoPlSSHAP, respectively.
In Figure 10, we report the Precision@5 metric for the PolySHAP variants and the baselines for paired sampling. Again, we observe state-of-the-art performance for PolySHAP and Regression- MSR. PolySHAP's performance substantially improves, if the budget allows to capture order-3 in- teractions.
27

---

Published as a conference paper at ICLR 2026
Sampling Standard Paired
Method
1-PolySHAP (KernelSHAP)
3-POlySHAP P-llySHHAP
2-PolYSHAP
Housing (dim B)
VIT9 (d- 9)
Bike (d 12)
Forest (d) 13)
5 6.45
1.00
2.02
100
Ra.6
110
2.07
0.00
0.03
0.81
0.00
6.75
2.73
3.75
0.75
160
240
são
3.73
1420
2009
0.70
1550 aite asion
15h5
(25%)
(2710) (78%)
Sudget
Adult fef 14)
Resivet (dim 141
DistiBBERT (d'm 14)
Estate td
3.06
1.00
1.00
0.03
0.00
0.00
1.03
0.00
0.00
0.70
1300: 1032) 1E00 7700 TUSTR
0323 1000
WIED 1350 TOA3T
0331 EEED 903E 13320 10031
0300 20030 19533
FEED 2007
Budger (m)
Budger
Busget Dm)
Budger (m)
CIFAR-10
CG60 60)
0.35
0.05
0.5
3.43
0.46
0.00
2.00
0.00
0.70
5353
5000
32000 38353 20000
6.70
530 5300 .3500 36030 20000
3.70
6000 8053
12053 58000 23000
0.70
4205
0000
32000 15500 20030
Sudge: (m)
Budge: (ml
Sudget Un)
Budget (n))
NHAEES id
= 1011
6.00
3.90
0.85
6.40-
3.80
0.70
0303
0300
1-380
14230
(-130) 11N0 1+2%) (+15)
1-281 (x150) 1-3%) 16286 (+15)
Sudget (1)
Budge: Oni
Budges
Figure 9: Approximation quality measured by Precision @5 (+ SEM) for standard (dotted) and paired (solid) sampling. Under paired sampling, 2-PolySHAP marginally improves, whereas Ker- neISHAP substantially improves due to its equivalence to 2-PolySHAP
B.4 APPROXIMATION QUALITY USING SPEARMAN CORRELATION
In this section, we report approximation quality with respect to Spearman correlation (Spearman- Correlation) for all explanation games from Table 2.
Figure 11 reports Spearman correlation of PolySHAP and the baseline methods. Again, we observe consistent improvements of higher-order interactions in this metric. For high- nigh-dimensional settings (2 60). we further observe that the baselines clearly outperform PolySHAP in this metric. Since we have seen that PolySHAP performs very well in the Precision @5 5 metric, we conjecture that this difference mainly due features with lower absolute Shapley values.
In Figure 12, we observe similar pattern as with MSE and Precision@5. Using paired sam- pling drastically improves the approximation quality of I-PolySHAP, due to its equivalence to 2- PolySHAP. Since 3-PolySHAP often performs very well in this metric, we do not observe strong differences between 3-PolySHAP and 4-PolySHAP in both sampling settings.
In Figure 13, report SpearmanCorrelation for the PolySHAP variants and the baseline methods under paired sampling. Again, we observe state-of-the- performance for PolySHAP and the Re- gressionMSR baseline. PolySHAP substantially improves, if the budget allows to capture order-3 interactions.
28

---

Published as a conference paper at ICLR 2026
Sampling
Method
Paired
Fermutation Sampling
NSR SVARM
RegressionMSR
PotySHAP tog! 3-PotySHAP (50%)
3-PolySHAP
UndiaseskemeSiie
1-PolySHAP (KameeSHAP))
())=0)
Forest (d'
0.03
3.99
6.90
3.90
3.60
5.00
0.50
3.00
0.00
0.70
2.70
150 240
REO
0.70
.030
2000
2008 6207
0.70
1550 3300
4500 1000 2015
Budger On!
Budget
Budget
Sudge: (m)
Adult
Resivee 18 (di:
DistiBERR (d 14)
Estate 15)
2.20
1.00
1.00
0.95
3.99
3.50
0..05
0.50
230
0.00
0.70
2030
12000-5000 (37.)) (55%)
(1.94111
(05%) 1925)
13786 (57%) 1738 (924)
(7.88 (824))
(1.%61 12084
1975)
1999 1975)
Budger
Budger
Susget
Budget
VITI6 (d' 16)
CIFAR-10 VITLE (d 16)
Cancer (2 30)
CG60 (d 60)
1.00
3,01
1.00
1.00
6.00
2.02
3.00
3.50
5.45
0.00
1256 (22%) (30%) (24%) 131%)
(550
(125)
(30%) (294) 121%)
(-130) (-28) (417)) 1+2%) (415)
(-15)) (410)
1-15)
SHONE (e2%)
11600 (d 600
NHANES (d 79)
Crime (d' 101)
2.00
2.00
1.00
3.89
0.75
3.75
14330
1+28)
Budge
Figure 10: Approximation quality of PolySHAP variants and baselines measured by Precision @ (# SEM) for paired sampling
29

---

Published as a conference paper at ICLR 2026
Sampling
Standard
I-PolySHAP (KemeelSHAP)
2-PolySHAA (50%)
3-PalySHAP (50%)
PPPlySHAAP
2-PolySHAP
3-PolySHAP
Housing id
SEW
VIT9 (di=))
Bike (d
Forest (d 13]
1.00
1.00
2,00
2.00
0.90
0.92
3,00
0.60
Spearree womeeneetoon
0.00
0.80
0.73
0.79
0.10
120%) (3050)
(28%) (785) (96%)
(10%)
(3778)
(259))
(739) 1929)
Adult Ed 144
Reskett8 (d 14]
DistiisERT (df 14)
Estate (d 15)
1.00
3.00
2.00
1.00
0.99
0.50
3.01
0.65
0.75
0:35
0.75
(378A17700 17%4 (929)
(1940)
(31-0 RMN (979)
(10%)
(171))
(509)) Vou (27))
117
1974)
1996) (479)
VIT26 id
CIFAR:10 VIT16 (di 261
Cancer (d 30)
CG60 td 60)
3.00
1.00
3.90
0.80
0.50
0.30
0.65
0.85
3.05
0.80
0.73
0.75
0.75
1320
8000
12000
10320 30000
4030 1600 32000
16030 30400
4060
2010
12300
-6000
4300
12000
10400
122%1
(38%)
13130
131%
14.290
(+37%)
1-38)
Budge: (m)
UNI
Budges
60)
NHANES (d/
(d'-
0.95
0.95
3.85
0..5
3.85
3.00
0303 8210 12500 19103 zodeo
#550
12200 18020 20320
3.70
4200 9000
12503 raden 25520
Sudget (m)
Dudge: (m)
Dudget (m)
Figure 11: Approximation quality measured by SpearmanCorrelation (+: SEM) for varying budget (m) different games. Adding interactions in PolySHAP can substantially improve approximation quality
30

---

Published as a conference paper at ICLR 2026
Sampling
Method
Standard
1-PolySHAP (KerneISHAP)
3-POlySHAP 4-loySSHAP
Paired
2-PolYSHAP
Housing (dmm) B)
VIT9 (d- 9)
Bike (di 12)
Forest (d- 13)
11.00
1.00
-00
1.00
3.91
0.45
2.07
0.00
0.00
0.81
0.85
0.75
0.75
0.75
0.75
160 260
240
sdo
2015
3206
0.70
1550 3600 45ht
vedo 15h5
120%L
(2710)
(39%)
(181)
Sudget
Speameenroom -29
Adult fef 1.4)
Resivetl8 (d
DistilSERT (ef 14)
Estate (d) m 15)
2.00
1.00
0.59
0.00
0.03
2.00
0.00
1660: 10326 1600 7700 1STE
9326 (0001 VEEP 13500 T0a3
2915 1000
B0SE 13320 1003
(160) 1026 1/33 FEED 2307
Budger (m)
Budger OH)
Budger (m)
Buddee (m))
Ste Cte- wewerrrr 552
-EM
CIFAR-10 (d'=
Cancer
retebeen SEM
0G60 60)
0.55
10.5
3.55
0.59
3.07
2.00
0.00
0.72
4320
5000
33000 39300 20000
4030 2000 33500 36030 20000
3.70
4000
5000
12300
5800 23300
0.70
4200
0030 12030 18600 20030
Pudge: (m))
Dudge: (n)
Budget Oni
Budget (n))
60)
NHANES
Crime = 101)
0.50
3.00
0.89
0.82
3.00
0003
(435) 1-38)
1-2% (-2))) (6236
(-130) 1-3 280
1+2%) (41
1-18) 1-3%)
(6276 (+15)
Sudget (2)
Budge: (n)
Budges
Figure 12: Approximation quality measured by SpearmanCorrelation (+: SEM) for standard (dotted) and paired (solid) sampling. Under paired sampling, 2-PolySHAP marginally improves, whereas KernelSHAP substantially improves due its equivalence to 2-PolySHAP
B.5 RUNTIME ANALYSIS
In this section, we analyze the runtime of PolySHAP and the RegressionMSR baseline, since both methods approximate the game values, and subsequently extract Shapley value estimates.
Figure 14 reports the runtime in seconds (log-scale) PolySHAP and RegressionMSR for the spent budget on different explanation games. As expected, we observe linear relationship between the budget m and the computation time PolySHAP, indicated by the overlapping linear fits (dashed lines). Overall, the computational overhead of the computations executed in RegressionMSR and PolySHAP variants after game evaluations will be negligible most application settings.
Complexity of Evaluations. In realistic application settings. the runtime for game evaluations should be considered a main driver of computational complexity of PolySHAP and RegressionMSR. This is verified by the CIFARIO VIT16 game in Figure 14, a), which requires model call of the VITI6 for each game evaluation. The computational difference between RegressionMSR and all PolySHAP variants are thereby negligible.
For the runtime of the path-dependent tree games, reported in Figure 14, b) the game evaluations require only single pass through the random forests, which becomes negligible with increasing dimensionality.
Complexity of Computation. The computational overhead of RegressionMSR and PolySHAP variants besides the game evaluations is negligible in many application settings. However, there is an impact runtime for the higher-order k-PolySHAP variants, due to the increasing number
31

---

Published as a conference paper at ICLR 2026
2000
propoce 200
SEM
Forest
2,00
0.50
0.00
0.00
2.00
0.00
0.10
0.00
120%)
120%) (789)
(20%) (374) (2290) (754)
Buddpes OnI
Sudget
Budget (m7)
Sudget (1))
Aduult (di 140
Restiet88
Melttere 3EM
DiABiBERT (d 14)
SEN
Esttae 15)
2.00
2.00
9.50
3.43
0.40
0.00
0.75
18000-50000 (176)
0.70
(1990)1171)) 107 (T9N) (929)
(199) 13764
(3050 VTN (974)
(189)
(5TVL 17 (9P4))
117 (2-5) (175)
1999) (479)
Budger
Budget
Creemneerron 5TH
VIT25 id 16)
CIFAR-10 (dd 16)
Cancer (d 30)
C560 Id 60)
2.00
1.40
3,00
1.00
0.50
0.50
2.00
0.50
3.05
0.80
0.00
1061
(32%)
(38%) (296) 133%6
1850
(228))
138%
(894) 1319)
14:700 1-2
C4-266
16 (42h)
(+30))
8.60 (d] - 60)
NHANES Id 79)
Crime (d 101)
1.00
1.00
2.07
3.91
0.65
0.55
2.85
0.75
0.75
12500 19003 zeleo
#20n Lacen 16020
09003 Budget
12003 selen
Budge:
Figure 13: Approximation quality of PolySHAP variants and baselines measured by SpearmanCor- relation (+ SEM) for paired sampling
32

---

Published as a conference paper at ICLR 2026
PolySHAP
Method
Linear RegressionMSR
Runtime
1-PolySHAP (KernelSHAP) Z-PolySHAP
3-PolySHAP
S-PolySHAP
CIFARLO-VITI6 (d - 16)
(xcconds)
30-
19h
1981
0012
(12%)
(24%)
Budget
a) Real-World VIT Inference Game
b) Path-dependent Tree Games
Figure 14: Runtime seconds (log-scale) of PolySHAP and RegressionMSR for varying budgets (m) of a) real-world VIT inference game on CIFAR1O, and b) selected path-dependent tree games of varying dimensionality. The runtime increases linearly with the budget m, indicated by the lin- ear fit (dashed line). As expected in practice, the runtime of the real-world ViT inference game on CIFARIO is dominated by the model calls required for each budget. The computational difference negligible. For path-dependent tree games that require only single tree traversal per game evaluation, the runtime increases for higher-order PolySHAP due to the increas- ing number of regression variables with stronger effects in high-dimensional games.
of the approximators
of regression variables that yield a polynomial increase of computation time. For the tree-path dependent games in Figure 14, b) this effect is visible due to the very efficient computation of game values.
The RegressionMSR method utilizes the XGBoost library (Chen & Guestrin, 2016). which scales well to high-diment nigh-dimensional problems, indicated by the low runtime observed in Figure 14. The runtime of these computations is generally higher than 1- and 2- 2-PolySHAP, but less than 3- and 4-PolySHAP for high-dimensional problems.
33

---

Published as a conference paper at ICLR 2026
B.6 ADDITIONAL TABLES
Table 4: Summary statistics of the MSE error for ALL Shapley value estimators we consider with paired sampling. Increasing the degree of PolySHAP improves its performance, but k-PolySHAP requires budget m 2 d2 (k)) RegressionMSR with XGBoost performs very well, except on games like CG60 or Crime where the decision tree struggles to approximate
$2522
11:199
$2:2-11
Tu4 Cu
13:114
12414
021
315.0
25 277h
31
18
11x15
31.13
Table 5: Summary statistics of the MSE enror for ALL Shapley value estimators we consider with standard (not paired) sampling. Increasing the degree of PolySHAP improves its performance, but k- k-PolySHAP requires budget 2 d2 (k). RegressionMSR with XGBoost performs very well, except on games like CG60 or Crime where the decision tree struggles to approximate 1/.
ROGIETT
$2-5
12:124
65-125
10-5
201--
65-147
3015
34

---

Published as a conference paper at ICLR 2026
C USAGE OF LARGE LANGUAGE MODELS (LLMS)
In this work, we used large language models (LLMs) for suggestions regarding refinement of writ- ing, e.g. grammar, clarity and conciseness.
35


Reviews:
[{"review_id": "CkVgYgK9qi", "reviewer": "Reviewer_cf9r", "summary": "The paper outlines theoretical and practical analysis of a method of obtaining more accurate shapley value estimates. The method essentially recognizes that shapley values are linear least square coefficients, so it computes higher-order pynomial leaest-sqaure estimates, then distributes higher-order coefficients down to individual variables using the shapley value-value property for projecting pure interaction functions. Comparison/euqivalencies to existing shapley work, including paired kernelShap, are given, as well as emperical convergence analysis.", "questions": "- Please comment on the results of the experimetns sectin, as it appears that regression MSR outperforms polySHAP.\n- Have you considered applying the approximate-up-then-project-down approach to other shapley-like methods that are computationally expensive and require random sampling, such as the Shapley-Taylor Interaction Index?\n\nsmall issues:\n- table 1 needs more visual separation from paragraph text\n- 228 - \"this is approach is\"", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- relevant theoretical results\n- sound theoretical basis\n- useful experimental results\n- reasonably clear", "weaknesses": "- I expect more experinental comparisons to other existing shap-acceleration methods in terms of speed and accuacy, as such, it is difficult to assess the effectiveness of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mgL0veZTK4", "reviewer": "Reviewer_L6kD", "summary": "This paper focuses on the Shapley value estimation problem in explainable artificial intelligence (XAI) and proposes a new method, **PolySHAP**, as an improvement over the widely used **KernelSHAP**. Traditional KernelSHAP employs a linear regression to approximate the relationship between model outputs and feature subsets, which limits its ability to capture feature interactions. This paper generalizes the approximation from a linear to a polynomial form, allowing the method to capture higher-order nonlinear interactions and improve the accuracy of feature attribution. In addition, the paper provides a theoretical explanation for the paired sampling mechanism in KernelSHAP, showing that it is equivalent to 2-PolySHAP.", "questions": "1. The paper states that KernelSHAP’s paired sampling is equivalent to 2-PolySHAP. Have the authors analyzed or compared the **computational efficiency** of the two methods? For example, do they exhibit similar runtime, sampling complexity, or scalability?\n2. **Table 3** contains missing results. Could the authors clarify the reason for these omissions? From the current presentation, it appears that **3-PolySHAP becomes infeasible for large feature dimensions (d)**, suggesting scalability limitations. If so, what practical advantages does PolySHAP retain compared to KernelSHAP?\n3. What was the **rationale behind the choice of sampling budgets and interaction orders** in the experiments? Were these hyperparameters tuned empirically, fixed a priori, or derived from theoretical considerations? Clarifying this would help assess the fairness and generality of the results.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* Presents a sound and theoretically grounded generalization of KernelSHAP by introducing polynomial regression to model nonlinear feature interactions, addressing a well-known limitation of additive interpretability methods.\n* The connection between paired sampling and 2-PolySHAP is a notable theoretical insight, offering a formal explanation for an empirical heuristic widely used in practice.\n* PolySHAP is shown to strictly subsume existing variants and guarantees convergence and consistency under reasonable assumptions.\n* Supplementary experiments (Figures 4–5, Table 4) and ablation studies further support the robustness and generality of the proposed approach.", "weaknesses": "* **Limited scalability in high-dimensional or strongly non-additive settings.** Due to the combinatorial explosion, experiments with (k \\geq 3) are restricted to small datasets, leaving open questions about PolySHAP’s feasibility in real-world large-scale scenarios.\n* **Rapid growth in sampling and computational complexity.** The paper does not sufficiently discuss the trade-off between accuracy and computational efficiency when (k > 2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZiC24L9V4I", "reviewer": "Reviewer_ixVM", "summary": "The paper introduces PolySHAP, a generalization of KernelSHAP that fits higher-order interaction terms through a polynomial (technically multilinear) regression model to better approximate the underlying Shapley game. This allows the method to capture non-additive feature interactions beyond what KernelSHAP can represent. The authors prove that PolySHAP yields consistent Shapley value estimates as the number of samples grows and establish a theoretical equivalence between KernelSHAP with paired sampling and second-order PolySHAP, providing an elegant explanation for the strong empirical performance of paired sampling. Experiments on various tabular, image, and text datasets demonstrate that higher-order PolySHAP variants improve accuracy over existing estimators, with paired KernelSHAP performing comparably to 2-PolySHAP but at a lower computational cost. Overall, the paper is clearly written, the experiments are extensive, and the connection between paired sampling and interaction modeling is both interesting and useful.", "questions": "The model in Definition 4.1 effectively uses monomials (or multilinear extension) rather than full polynomials, which is the correct approach since for binary variables, higher-order powers are redundant. However, this point deserves explicit clarification, as using true polynomials would add unnecessary complexity without additional representational benefit.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is well written, conceptually clear, and provides a theoretical and empirical investigation of Shapley value estimation. The most notable strength is the discovery of a relationship between paired sampling and polynomial (interaction-based) fitting in KernelSHAP, which offers a new and elegant theoretical explanation for a long-standing empirical observation in the literature. This connection is both novel and insightful, bridging a practical heuristic with a principled mathematical foundation.", "weaknesses": "While I found the relation between paired sampling and polynomial (or mulilinear) fitting intriguing, I believe the PolySHAP formulation is not entirely novel. \n\nThe regression in Definition (4) corresponds exactly to the multilinear extension of cooperative games. Consequently, several theoretical results, including Theorem 4.2 follow directly from earlier works, particularly Owen’s papers on multilinear extensions [1] - See Section 2 for instance, and the Mobius representation of multilinear games that gives the same results as Theorem 4.2. This close relationship is not (explicitly) discussed in the paper. \n\nThat being said, the idea of using multilinear extensions in explainability is not entirely new. Methods such as Faith-SHAP already build on this formulation, and the equivalence stated in Corollary 4.5 seems straightforward in light of that prior work. There are also other recent studies exploring similar multilinear formulations for feature attribution [2] - they have an exact formulation of PolySHAP via the multilinear extension of games. \n\n\n[1] https://www.jstor.org/stable/2661445\n[2] https://ojs.aaai.org/index.php/AAAI/article/view/34149", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dgfmqVd6jT", "reviewer": "Reviewer_9go5", "summary": "The paper proposes an extension of KernelSHAP by fitting higher-order polynomials to approximate the Shapley value. The results show improvement with higher order polynomials. Interestingly, the authors find that fitting a 2nd order polynomial to approximate the Shapley value is equivalent to fitting KernelSHAP with paired (antithetic) sampling.", "questions": "-Why widely used image datasets, e.g., CIFAR-10, CIFAR-100, and Imagenette, were not included in the experiments?", "limitations": "", "rating": 2, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "-The paper is proposing a novel idea to capture non-linear interactions between features.\n\n-The authors provide theoretical support to the proposed idea.", "weaknesses": "-KernelSHAP with paired sampling has better convergence, and simply using the unbiased KernelSHAP [1], or vanilla KernelSHAP, with more data samples will improve the accuracy as well. \n\n-In addition to the number of samples needed for PolySHAP, there is an additional cost to retrieve the Shapley values ($O(d·d')$), and this additional cost does not exist with KernelSHAP. \n\n-KernelSHAP with paired sampling is equivalent to 2-PolySHAP, and k-PolySHAP representation is equivalent to order-k Faith-SHAP. Moreover, for tabular data, RegressionMSR generally outperforms PolySHAP. So why does the user need PolySHAP?\n\n-In the experiments, the number of examples (10 randomly selected instances) is very small. I am not convinced that we can generalize the findings given this sample size.\n\n-The unbiased KernelSHAP [1] is missing from the comparison.\n\n\n[1]-Covert, I. and Lee, S.-I. Improving kernelshap: Practical Shapley value estimation using linear regression. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pp. 3457–3465, April 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)