TreeGrad-Ranker: Feature Ranking via $O(L)$-Time Gradients for Decision Trees
Authors: Weida Li
Yaoliang Yu
Bryan Kian Hsiang Low
Venue: ICLR 2026 Poster (2026)
Keywords: Beta Shapley values
weighted Banzhaf values
feature ranking
decision trees
Linear TreeShap
Primary area: interpretability and explainable AI

Abstract: We revisit the use of probabilistic values, which include the well-known Shapley and Banzhaf values, to rank features for explaining the local predicted values of decision trees. The quality of feature rankings is typically assessed with the  insertion and deletion metrics. Empirically, we observe that co-optimizing these two metrics is closely related to a joint optimization that selects a subset of features to maximize the local predicted value while minimizing it for the complement. However, we theoretically show that probabilistic values are generally unreliable for solving this joint optimization. Therefore, we explore deriving feature rankings by directly optimizing the joint objective. As the backbone, we propose TreeGrad, which computes the gradients of the multilinear extension of the joint objective in $O(L)$ time for decision trees with $L$ leaves; these gradients include weighted Banzhaf values. Building upon TreeGrad, we introduce TreeGrad-Ranker, which aggregates the gradients while optimizing the joint objective to produce feature rankings, and TreeGrad-Shap, a numerically stable algorithm for computing Beta Shapley values with integral parameters. In particular, the feature scores computed by TreeGrad-Ranker satisfy all the axioms uniquely characterizing probabilistic values, except for linearity, which itself leads to the established unreliability. Empirically, we demonstrate that the numerical error of Linear TreeShap can be up to $10^{15}$ times larger than that of TreeGrad-Shap when computing the Shapley value. As a by-product, we also develop TreeProb, which generalizes Linear TreeShap to support all probabilistic values. In our experiments, TreeGrad-Ranker performs significantly better on both insertion and deletion metrics. Our code is available at https://github.com/watml/TreeGrad.

Published as a conference paper at ICLR 2026
TREEGRAD- FEATURE RANKING VIA O(L)-TIME GRADIENTS FOR DECISION TREES
Weida Li', Yaoliang Yu?.3, Bryan Kian Hsiang Low'
Department of Computer Science, National University of Singapore, Republic of Singapore
2 School of Computer Science, University of Waterloo, Canada
3 Vector Institute, Canada vi sitasseeegmaill com, yaoliang yu@uwaterloo.ca. yoolaangyyduutttrroooo.o.. lowkh@comp nus edu.
ABSTRACT
We revisit the use of probabilistic values, which include the well-known Shapley and Banzhaf values, rank features for explaining the local predicted values of decision trees. The quality of feature rankings is typically assessed with the inser- tion and deletion metrics. Empirically, we observe that co-optimizing these two metrics is closely related to joint optimization that selects subset of features to maximize the local predicted value while minimizing for the complement. How- ever, we theoretically show that probabilistic values are generally unreliable for solving this joint optimization. Therefore, we explore deriving feature rankings by directly optimizing the joint objective. As the backbone, we propose TreeGrad, which computes the gradients the multilinear extension of the joint objective in OL) time for decision trees with L leaves; these gradients include weighted Banzhaf values. Building upon TreeGrad, we introduce TreeGrad -annker, which aggregates the gradients while optimizing the joint objective to produce feature rankings, and TreeGrad-Shap. a numerically stable algorithm for computing Beta Shapley values with integral parameters. particular, the feature scores computed by BeeGGrad-Ranke, satisfy all the axioms uniquely characterizing probabilistic values, except for linearity, which itself leads to the established unreliability. Em- pirically, we demonstrate that the numerical error of Linear TreeShap can be up to 1 times larger than that of TreeGrad- -aaap when computing the Shapley value. As by-product, we also develop TreeProb, which generalizes Linear TreeShap to support all probabilistic values. our experiments, InceGrad-Rankee performs significantly better on both insertion and deletion metrics. Our code is available at httpp: /tte:://ttttiie hub. com/ /ttp///ttmmm/eaaaeaee
INTRODUCTION
So far, decision trees remain competitive as recent empirical studies show that cradient-boosted de- cision trees (Friedman, 2001) tend perform better on larger or irregular tabular datasets compared to neural networks (Grinsztajn et al., 2022; McElfresh et al., 2024). Often, decision trees are deemed easier to interpret due their rule-based structures.
In explaining model predictions, the Shapley value (Shapley, 1953) has gained attention due to its uniqueness in satisfying the axioms linearity, null, symmetry, and efficiency (Lundberg Lee, 2017). Generally, it is intractable compute the Shapley value exactly. Thus, many efforts have focused on developing efficient Monte-Card Carlo methods (e.g., Jia et al., 2019; Covert & Lee, 2021; Zhang et al., 2023; Kolpaczki et al., 2024: Li & Yu, 2024a;b) or frameworks that train models to predict the Shapley value (Jethani et al., 2021; Covert et al., 2022).
Despite that, the Shapley value for explaining decision trees be accurately computed in polyno- mial time (Lundberg et al., 2020; Yang. 2021). To our knowledge, the most efficient algorithm is Linear TreeShap (Yu al., 2022). which runs in (T.D) time while consuming O + L.) space.

---

Published as a conference paper at ICLR 2026
Here, D denotes the depth of the tree, whereas L refers to the number of leaves. Alternatively, Kar- czmarz et al. (2022) advocated the use of the Banzhaf value (Banzhaf III, 1965) because it is more numerically stable to compute.
On the other hand, Kwon & Zou (2022b) argue that the Shapley value could be mathematically sub- optimal in ranking features and other members of Beta Shapley values (Kwon & Zou, 2022a) tend to perform better. Note that all the concepts mentioned belong to the family of probabilistic values uniquely characterized by the axioms of linearity, dummy, monotonicity, and symmetry (Weber, 1988). Empirically, Kwon & Zou (2022a;b); Li & Yu (2023) note that there is no universally the best choice of probabilistic values in ranking features or data. Then, a question arises: how reliable are probabilistic values in ranking features?
The quality of feature rankings are typically measured by the insertion and deletion metrics (Petsiuk et al., 2018; Jethani et al., 2021; Covert et al., 2022). In this work, we start by demonstrating how co- optimizing these two metries is closely related a joint optimization that finds a subset of features to maximize the predicted value while its complement minimizes it instead. Using this perspective, we theoretically establish that
if an attribution method is linear, which include all probabilistic values, then it is no better than random at optimizing the joint objective, as shown Proposition 1;
feature rankings induced by probabilistic values can be obtained by substituting a linear surrogate for the joint objective and solving the resulting linearized optimization; opera- tionally, this linearization does not always faithfully represent the original objective.
To circumvent such pitfalls, we explore deriving feature rankings by directly optimizing the joint objective. The focus of our work on decision trees, and our algorithmic contributions can be summarized as follows:
As the backbone, we develop TreeGrad (Algorithm 8), which computes the gradients of the multilinear extension of the joint objective in O(L) time and space for decision trees. These gradients include weighted Banzhaf values (Li & Yu, 2023).
introduce TreeGrad-Ranker (Algorithms 2 and 11), which ag- gregates gradients while optimizing the joint objective to produce vector of feature scores. This design is motivated by the fact that any symmetrie semi-value can be expressed as an expectation over this gradient field (see Appendix A). In particular, as proved in Theorem 1, the resulting feature scores satisfy all the axioms uniquely characterizing probabilistic val- ues, except for linearity, which itself leads to the unreliability established in Proposition 1.
Building on TreeGrad,
Although Linear TreeShap is theoretically guaranteed to compute the Shapley value in polynomial time, as shown in Figure 2, it suffers from severe error accumulation. Based on TreeGrad, we therefore develop TreeGrad-Shap (Algorithms 6 and 7), an equally efficient and numerically stable algorithm for computing Beta Shapley values (Kwon & Zou, 2022a) with integral parameters. Empirically. the numerical error of Linear TreeShap can be up to 1 times larger than that of TreeGrad- Shap when computing the Shapley value.
As by-product, to all probabilistic values. Specifically, the numerical instability in Linear TreeShap stems from the use of ill-conditioned Vandermonde matrix. We alleviate this issue by replacing it with a well-conditioned matrix. A Although this introduces numerical underflow for deep decision trees, the resulting errors are less severe, as shown in Figure 2.
propose TreeProb (Algorithm 3), which generalizes Linear TreeShap
2 BACKGROUND
Notation. Let N be the number of features and write [N] = 21, .J. Then, E RN denotes a specific sample. For convenience, the cardinality of a set C [N] is denoted by its lower-case letter Meanwhile, we write 5 Ui and S \ instead of S U (i) and S (i).
A trained decision tree f is associated with a directed tree T = EV where V and E refer to all the nodes and edges. T is rooted because there exists unique root r E V such that for every v E V we can find a path P. S E starting from r to v. Moreover, each non-root node v has one parent my and each leaf node contains two children a, and by. For each non-leaf node e, it
2

---

Published as a conference paper at ICLR 2026
Cu2
3
Ce. = 20
Cus 10
lez Wie
1/2
Ovz
0.1
Les Weo
Pes = 0.7
Legs Wea
24
Cr 25
ler Wer
Lest Wes
Tud
Cas 10
U1
V/
1,
Des = 0.8
C+1 22
Leg; Wea
Cvs 2
l11 =
Dvs = 0.3
Figure I: An example of a binary decision tree to illustrate notation. Each node is covered by Co instances. Non-leaf nodes ① split a feature l, using threshold To while leaf nodes Ø make prediction Pe. Each edge e v) equipped with weight we = Ca/Ca and feature le lu-
associated with a threshold Ty E R concerning a specific feature 4. E [N]; x is directed into dg if Iı, < To and by otherwise. For each E V. let be the number of training data covered by the subtree rooted at v. Each edge e = (u + v) E E is weighted by 0 < Ss < 1, and we write he == 0; plus, e is labeled with l. Therefore, we and Le refer to the weight and the label of Then, define Pi,e- = {e E P. L = i] and F. == fle: by its nearest ancestor along P. that shares the same label with el may not exist. For each node v, let L, be the set that contains all the leaves of T that can be reached from v. Then, we define L fu' Lu (m,, v) is the nearest edge ancestor of of labeled by 4... }- For each leaf node v E T.,, let Ou E denote its predicted value. We denote by D the depth of and by I. the number of leaves of T. Note that [V| 2T. 1 and D L.. We assume that all the features in [N] are used by T. and thus N < [V]. A simple example with D = 3 and L = 4 can be found in Figure 1.
P.). For every edge E P., denote el
For polynomial p(y) of degree deg(p). write p(y) Edeg(v) Ph+1y i.e., denote its coef- ficients by the corresponding bold letter p E IRdez())+1 Then, the inner product of two polynomials is (p(y), (()) = (p. q)
2.1 PROBABILISTIC VALUES AND VALUES
One popular way of ranking features is the use of probabilistic values, as it uniquely satisfies the ax- ioms of linearity, dummy, monotonicity, and symmetry (Weber, 1988). Precisely, each probabilistic value can be expressed as
8 (1x) = Σ Ws41 -x
(1)
SEINIV
where w E N is non non-negative with Σ (/=1) = and fx(S) Exge [xss X where Xs is the restriction of on S and S : [N]] S. Following Lundberg et al. (2020), there are two choices for sampling Xst. One choice is to use the marginal distribution; however, this has been argued to be unreliable, it uses off-manifold data and thus may produce manipulable explanations (Slack et al., 2020; Frye et al., 2021). We follow the other choice (Algorithm 9), which may be convenient approximation of the conditional distribution. This approach has recently been adopted for computing Shapley interactions (Muschalik et al., 2024). If we further add the consis- tency axiom, the family of probabilistic values shrinks, and the remaining members are referred to as semi-values (Dubey et al., 1981; Li & Yu, 2023). Specifically, d² is semi-value if and only if there exists Borel probability measure a over the closed interval [0, such that for every lt E [N],
Wi:- = f/+' 10 N== dd)(tt.
(2)
In particular, weighted Banzhaf values and Beta Shapley values are semi-values, with the latter including the Shapley value (Shapley. 1953) as special case. We refer the reader to Appendix A for more details. d² (fx) will be used denote semi-values.
3

---

Published as a conference paper at ICLR 2026
2.2 LINEAR TREESHAP
Previously, Yu et al. (2022) introduced Linear TreeShap capable of computing the Shapley value (Jx) in OLLD) time and O + L) space. We notice that counterpart with the same time and space complexities also appeared in Karczmarz et al. (2022, Appendix E), conveniently referred as TreeShap-K. K. Since Yu et al. (2022) offer a more compact set of definitions for describing how the relevant terms traverse the tree, we follow the concepts used by Linear TreeShap. In Appendix D, we demonstrate how to evolve Linear TreeShap into TreeShap-K.
Linearization of the approximation of fs. For each [N] and v Lr, we define x I satisfies all the splitting criteria along the path P. that involves feature i. The convention is E D2 if pi, 0. Then, for each i E [N] and E Ly, a function Vi, R + IR is defined by
(x) = xxell,, IeEEP.. J. Then, (S) = EVEL. (S) where each path-dependent rule function Rx: 2[N] - IR is defined by setting R = L. er Ilees, (x).
The Shapley value of Rx. From now on, we will omit x occasionally for simplicity. Since Shap (fx) Ev
of Shap (Rx) it suffices to demonstrate how to compute the Shapley value of each Ry According Yu al. (2022, Lemma 2.2).
( - 1)
F. 1) 8
-1
Gn(())
Shap ( 0,
Σ
II jES
15 (N. 1)eb 1 Yiu
G/FFol
SCF.M
where Gv(v) aucu ILEEF, (1 + 7/.0 y) is a polynomial of y. and (p((V)) = (p(v), Baeg (p) (v))
i & F,,, the focus is the cases where Gv( divisible by 1 + Yi y. The key idea is that the coefficient of y in I + y) is exactly As 1 Yi.v which shows that the Shapley value of interest can be computed using polynomial operations. Before proceeding, for each edge e E E, define a function %e: RR - R by letting (e(x) IxEE II'' war where x II. if satisfies all the criteria along the path Ph., that involves feature Le, Conveniently, if e the last edge in Pr.e. then Y, = %e While traversing down a path P.. Gv) is what Linear TreeShap computes. For traversing up the tree, we adopt the computation proposed by Karezmarz al. (2022, Lemma 5) as it is more elegant; G.())) [17299
where Ba(y) = 1 El (t) 'y² Since 7h.
precisely, Shaap (Jx) = EeEE EvEr, (7 1)
1-=1
Why does Linear TreeShap run in O(LD) time. The computational efficiency comes from the so-called scaling invariability equality (Yu et al., 2022, Proposition 2.1),
((p(v)) = (p(y) (1 (1+ ))**
where 2 0.
(3)
Accordingly,
Shap ($x))((x) Σ cEEJ.=i
(Te (76- (7 Evert. Go(y).
(1 +1+1 deg((G)) where de They
maxvela, (v)(G,(()) Clearly, the significance of Eq. (3) that now possible to sum over (1411)) } lvent and then compute EvEr, t.
Shap (R*)) using v only once. Without Eq. (3), would $1.
be evaluated [b]_ times instead. Please see Appendix B on how vé is implemented.
3 HOW UNRELIABLE ARE PROBABILISTIC VALUES IN RANKING FEATURES?
Suppose f outputs the probability of a class, and let &a E RV- denotes feature scores for the prediction fx). Then, a higher o; indicates that the i-th feature contributes more positively to increasing fx. Typically, the quality of Φ is measured by the insertion and deletion metrics (Petsiuk et al., 2018). Notice that these two metrics only employ the ranking [N] [N] induced by Φ. i...
(a(1) 2 (x) 2 (N) The two metrics are as follows:
N
Ins(T,; fx)
1
Σ (T)) and fx) = N
Σ fa(S((T)
(4)
N
k=1
Since Wi Wn+1-e for the Shapley value, + Tk.v y interchangeable with 7k + y.
4

---

Published as a conference paper at ICLR 2026
{T(N), T - 1)....,,tt <(N k + 1))- higher Ins(T;;fa fx) indicates that the top-ranked features contribute more positively to increasing ff fxx,, whereas a lowers Del(T;; fx) indicates that the bottom-ranked features contribute more neg- atively. Let S (T) == arg ma (x) fx (T)) and S (T)
where S = (1), ( [[k]] and (
arg arg ming, (x) fx(S (T)). Then, (T) can be viewed as the positive features identified by æ, whereas 5,(Tz) (x) contains negative ones. Empirically, we observe that higher Ins(TT; fx) is often associated with a higher fx( (æ)). which essentially corresponds to finding a subset S that maximizes fx fx(S)). Similarly, the deletion met- ric is closely related finding subset S that minimizes fx(S") Meanwhile, is expected that S = [N] S Therefore, equally co-optimizing Ins(:; fx) and Del(:; fx) is closely related to
maximize SCIN] 2 (fx(S) - [x([N] S)).
(5)
Next, we will theoretically demonstrate why probabilistic values are generally unreliable in solving the problem (5).
Consider arbitrary set function U 2| + I and define Dy by letting Dv(()- - (U(() U[[N] \ 5)). We will show that for each probabilistic value (U),, there exist two distinct sets S1 and S2 such that d² (U) can not reliably differentiate between the two hypotheses (s,( S (v)(S) and (S,) > (S2). Following Bilodeau et al. (2024); Wang et al. (2024), a hypothesis test is a function h N + [0, 1] that takes input contribution vector, such o (U),,, and outputs the possibility to reject the null hypothesis Du (S1) < Du Then, the reliability of a test h can be bounded.
Proposition Suppose o(fx) E TRN is linear in fx with N 3, which includes all probabilistic values. Then, there exist distinct sets S1 and S2 such that S1 + [N] \ S2 and
Rel(h; S2. = inf
[1 ((((U)) + U-Do(S))SDo(SA))
inf U:Du(S.)>Du(SS)
h(o(U)) S 1.
In particular, for random guess h 0.5, we have Rel(h; S1, indicates that for each probabilistic value, there are hypotheses such that it can not reliably reject. The intuition behind this proposition is that a linear operator maps vectors of dimension 2 into significantly compressed ones of dimension N, leaving vast room for not detecting non-neg negliggie differences. This may limit how well probabilistic values are in solving the problem (5), or equiva- lently, ranking features.
Therefore, this proposition
Proposition 2. Let π be a ranking induced by a probabilistic value d² (fx) such that & ()))(()))))))))))))) Z
(fx) 2- ... 2 o (fx) For every S k S N, St = {T(1), (2), ..., [k)] an optimal solution to the problem
1 (g 9" ([N] S)) 2
maximize SCINI.IS]=k
where g" is the best linear surrogate for fxi i.e.. g" = arg min geC Esgin) (fx((((()) g(S))²
gen with L = [g g(S) to Eiesti.. ti). The weights satisfy (i) m, NN 2 0 and (ii) m)s = + W,-1
for 2 < 8 s N.
Let S arg max SCIN (fx(S) [x([V) S)). Then, St can be treated an approximate solution to S Taking it step further,
maximize dfx(S) SC(N]
maximize dfx(W)) wE(S; ISRSN)
maximize dfx(W).
WE(st ISKEN)
where (S) = (()
suggess that the use of probabilistic values equivalent to substituting linear surrogates for fx while optimizing the problem (5).
Why not optimize the problem (5) directly? The problem maximizes US) is known to be NP- hard (Feige et al., 2011). Alternatively, one may resort to a linear surrogate as it is more tractable. However, such a linearization comes at the expense not accurately representing the behavior of fx- In what follows, to solve the problem (5) using gradient ascent. Meanwhile, we are able to obtain feature scores that satisfy all the axioms uniquely characterizing probabilistic values, except linearity.
will demonstrate that decision trees are well-structured such that it is practical
5

---

Published as a conference paper at ICLR 2026
Algorithm TreeGrad (Simplified Procedure)
Input: Decision tree T = (V, E) with root r, instance X E IR point z E [0,
Output: Gradient g
Function traverse (2, 8 = 1)
e (m, -1)
e exists then
(1 21, + 21. 7e)
T- Not
else
8 + 8. (1 21, + (1)
e leaf then
t gucy
else
10
8 + traverse (an, 8) + traverse (b,, 8)
11
if'e exists then
H + H(hht] -8
12
Hu] [[] +
13
14
91. + g1e + (7/ -1. 1).
15
return
16 Initialize [b]] = 0 for every v E V
17 Initialize g = 0N
craverse (a,))
19 traverse (b,)
return g
Algorithm 2 TreeGrad-Ranker with Gradient Ascent (GA)
Input: Decision tree ' = (V, E) with root instance E RN,, learning rate > 0, total number of iterations T
Output: A vector of feature scores 21
Initialize 0.5 1n and Ç ON
for ( 1.2...., T do
23
+ (TreeGrad(T,, x, z) TreeGrad(T, x, 1N - z))
24
z + z t
25
z Proj(z)
11 2; t- min(maxx(,,)))m 2;),
=-1 c+ 1
26
return Ç
TREEGRAD-RANKER
To make fx: 2[ + R differentiable, the first step is to make its domain continuous. Following Owen (1972), the multilinear extension fx, denoted by fx: [0, 11 - IR, defined by letting
Fz(z) Esgin (I])s>)) (IIyes(1- -12)) fx()). Then, the problem (5) relaxed as
1 1 [T((2) - Jx -2)) 2)).
maximize zE|0.1|5
(6)
This relaxation is justified by the following proposition. Proposition Suppose the optimal set S* for the problem (5) is unique, then 1s- whose i-th entry is 1 if E S and O otherwise is the unique optimal solution to the relaxed problem (6).
Then, according to Owen (1972, Eq. (8)), we have
Vz)(2)= = Σ
II 2j JES
II (1 (A((S)))) - (2(S)) JESUI
SCIN

---

Published as a conference paper at ICLR 2026
An (LL)-time TreeGrad for computing gradients. Since Vzx(z)= = EVEEL, (Zg(z), it suffices to simplify the formula each (z).
Lemma 1. We have V, R. (7i,0 1). - +2.%, where H,
H.
LuCy Gr
IIjEF, (1 11=2++22 2g
Starting from r, write P. = (c1, (61,,2,-.. e2,..., ePP)) .lp.) in the order encountered when traversing down the path P. to the leaf node v. Then, running
5
(1 - 2jz + 2j Yer,, of exists,
80 < 1 and 88 c- Zke 2k Yeg
(1 Rje + Rje Yoe) 8g-1,
otherwise,
where je = leg and kg == bg until reaches the leaf node v, we have Rufu 8)P.1 H,, While
traversing up the tree from leaf nodes, each vz)x is computed using the following lemma.
Ewert, H. Lemma 2. (z)x Epee(1e 1). T T-2 1,=1
As shown in Algorithm 1, lines 2-10 perform the traversing-down procedure, whereas the traversing-up procedure is efficiently carried out in lines 11-15.² In line 14, it may occur that - 24, 21,7; Ye = O when = 0 and 2,, = 1, which makes the division invalid. This issue can be easily addressed by noting that most one feature receives a non-zero update in g. The full procedure of TreeGrad that accounts for this corner case is presented in Algorithm 8. Overall, the total running time (T.) while using ((I) space. Equipped with TreeGrad, we can solve the relaxed problem (6) using gradient ascent, which is shown in Algorithm 2. Specifically, is learning rate and Proj projects each -₁- onto [0, 1] i.c., 24 f min(max((,, 24), 1). We comment that < = (0.5 1x) when T = 1, which is exactly the Banzhaf value. Since any symmetric semi-value, which includes the Shapley value and the Banzhaf value, can be expressed as expec- tation of this gradient field (see Appendix A), we take the averaged gradient as the vector of feature scores. Moreover, the gradient ascent used in Algorithm 2 can be replaced by the ADAM optimizer (Kingma & Ba, 2015), resulting in Algorithm 11. In particular, both algorithms verify all the axioms that uniquely characterize probabilistic values except for the linearity axiom.
Theorem 1. The vector of feature scores Ç returned by TreeGrad-Ranker either using Algorithm 2 or 11, can be expressed as Çi = EsciNly Wi(S; (fx(S U - fx(S)) where wx(S: > 0 and E (S; = 1. Moreover, it verifies the axioms of durmmy, equal treatment and monotonic-
ity.
5 AN O(LD)-TIME TREEPROB FOR COMPUTING PROBABILISTIC VALUES
Generalize the scaling invariability equality. To compute probabilistic values, the only differ- ence lies in how v defined. Therefore, to generalize Linear TreeShap for any probabilistic value ndd (fx), it suffices generalize the scaling invariability equality in Eq. (3). This is straightforward by noticing that multiplying by (1 + y) simply introduces a null player.
Lemma 3 (Generalization Eq. (3)). Suppose p(y) is a polynomial of degree N - 2, we have (p(v) (1 (1+ v), END Wk+1 )²) (p(v), EN-2 (Wi+1 + wx42)) v²)
Then, v (p(y)- (1 + w)** + (p(1)) in Eq. (3) is simply the result of recursively applying the equality in Lemma 3 while substituting We (E-1) For semi-values, using Eq. (2), their N!
scaling invariability equality can be simplified as
(p(v) (1 (1+8) 3) ( (v)) (p(y), diggi (z)),
(8)
where (²)) Ei ( (1- -)- =)(-=d((tt) gt
"The original implementation of the traversing-up up procedure, as in (Karezmarz et al., 2022, Algorithms 2-4), is unnecessarily complicated; they compute (0.5 Iw), equivalently the Banzhaf value.
7

---

Published as a conference paper at ICLR 2026
10
10
Linear TreeShap TreeShap-K
Condition number
100
10
105
10"4
Liner TreeShap
10 -6
Uneer TreeShap (vell-condttoned)
TeeGrad-Shap
10a
10
10a
10 10-14
10
10
12
14
16
18
20
36
40
44
48
52
56
60
64
depth D
depth
Figure 2: The condition numbers of matrices involved in Linear TreeShap and TreeShap-K, and the inaccuracy computing the Shapley value.
Inherent numerical instability in Linear TreeShap and TreeShap-K. As detailed in Appendix B, Linear TreeShap involves inverting Vandermonde matrix based the Chebyshev nodes of the second kind. However, as proved by Tyrtyshnikov (1994, Theorem 4.1), the condition number of Vandermonde matrices based on real-valued nodes grows exponentially w.r.t. D, Therefore, Linear TreeShap potentially suffers from numerical instability when D is large. Though TreeShap-K is free of Vandermonde matrices, also faces such numerical issue as it contains step that essentially solves ill-conditioned linear equation; see Appendix D for details. Figure shows that the con- dition numbers the involved matrices are already over 100, 000 when D = 20. Furthermore, also concretely demonstrates how inaccurate Linear TreeShap would be. Refer Appendix G for further experimental details and results.
Well-conditioned Vandermonde matrices. According to Pan (2016), Vandermonde matrix of large size ill-conditioned unless its nodes are more or less spaced equally on the unit circle. Pre- cisely, let {x) be list of complex valued nodes where X number of the Vandermonde matrix independent of D. Another nice properties are V-1 I V and VT V. Therefore, we will this V for encoding and decoding polynomials in our TreeProb algorithm. We refer the reader to Appendix C for how TreeProb implemented. Concurrently, Jiang et al. (2025) also observe this numerical issue and propose identical solution when computing the Shapley value of R² for individual features. However, this solution not fully numerically stable; it instead introduces numerical underflow when the number of nodes is large. As demonstrated in Appendix G, the nu- merical error of TreeProb still blows up as the number of nodes increases.
#2ck 11m Then, the condition D defined by letting Vi, = =x-1 is perfectly 1,
Numerically accurate algorithms for computing weighted Banzhaf values and Beta Shapley values with integral parameters. For the Shapley value, is the uniform distribution (Dubey et al.,
1981, Theorem ((a') )), i.e., Shap (fx) = Jo- VT 1n )tt. Then, we have &f Shop
(fx)= Σ
21
1t=1 Ke
Vfx(te 1x) using the Gauss quadrature rule. Since Kg > O and Σ Shapley value is just weighted sum of finitely many gradients. Likewise, this argument extends to Beta Shapley values with integral parameters, i.e., Beta(a, 3) with 3 N' {0). This observation immediately leads to our TreeGrad-Shap shown Algorithms and Both algorithms run in O(LD) time; the former consumes O(L) space, while the latter vectorizes its for loop and therefore uses O + L) space. Note that TreeGrad-Shap inherits its numerical stability from TreeGrad, which computes weighted Banzhaf values.
1, the
Corollary 1. TreeGrad-Shune (Algorithm 7) computes Beta Shapley value with integral parameters using (LD) time and O(D2 L) space. Without vectorization (Algorithm 6), its space complexity is O(L).
6 EMPIRICAL RESULTS
Metrics. The goal of our experiments is to compare TreeGrad-Ranker -anker with the Beta Shapley values using the insertion and deletion metrics (Petsiuk et al., 2018). We report the averaged insertion and
8

---

Published as a conference paper at ICLR 2026
TreeGrad Rankeer with GA
TreaGrad Ranker with ADAM
Banahaf
Seta-isertion
Buta Deletion
Beta-joint
probabilcy
predicted probabilit
predicted probability
0.0
0.7
0.6
3-8
0.5
0.7
0.5
0.0
0.5
0.4
10
20
30
40
50
30
30
40
50
0.7
1.0
predicted prebabiltt lity
0.8-
predicted probability
predicted probab lity
0.5
0.6
0.4
0.
0.4
5..2
10
20
20 50
10
20 30
30 40
FOTP (D = 20)
GPSP (D = 10)
jannis (D 40)
Figure 3: The trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve lower deletion curve indicates better performance. For our TreeGrad-Ranken we set the candidate Beta Shapley value that maximizes the Ins metric for each fx. whereas Beta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric Ins Del. The output of each fx) is set to be the probability of its predicted class.
100 and c = Beta-Insertion selects
deletion curves and note that the values of Ins and Del defined Eq. (4) correspond the areas under the respective curves. Thus, in terms of increasing f(x), higher insertion curve indicates better ranking performance at the top, while lower deletion curve reflects better ranking qual- ity at the bottom. To avoid noticeable numerical errors, they computed using TreeGrad-SSe Shap (Algorithm 6) and TreeGrad (Algorithm 1).²
Datasets.
Our experiments conducted using nine datasets from OpenML. Datasets of classi- fication include: (1) wwwrrooreeeteeeeem--rroereee (FOTP), (2) PeesuurPPaasSSegnntttioPPPPee
(GPSP), (3) jannis, (4) spambase, (5) philippine and (6) MinibooNE. Datasets of regression include: (7) Buzzinsocialmedia. Twitter (BT), (8) superconduct and (9) wave_energy We randomly sepa- rate each dataset into training dataset (80%) and test dataset (20%). The training is used to train decision trees, and each x is selected from the test set. For BT and wave wave_energy, we scale its predicted values for better presentation. summary of the used datasets can be found in Table 1.
Baselines. Following Kwon & Zou (2022a;b), the selected baselines include Beta Shapley values Beta(q, ()) with (a, 3) {(16, 1), (8, 1), (4, 1). (2, 1), (1, (1, 2), (1, 4), (1, 8), (1, 16)]. and the Banzhaf value. Recall that (eta 1) corresponds to the Shapley value.
All decision trees are trained using the scikit-learn library (Pedregosa et al., 2011). To account for the variability of fx. we randomly select 200 instances of x to report the averaged results for each trained decision tree f. fix the random seed to 2025 to ensure reproducibility. More details and results are deferred to the Appendix G.
For classification tasks, the output of each f(x) chosen to be the probability of either (i) its predicted class (ii) randomly sampled non- non-prrdieted class. All the results of decision trees presented in Figures and 4, with additional results provided in Appendix G. Our observations are follows: (1) For Beta Shapley values, the one that achieves the best insertion metric often does not achieve the best deletion metric, and vice versa; (2) Our TreeGrad -aaedrr---nner significantly outperforms the selected baselines the insertion metric while remaining competitive on the deletion metric.
'These algorithms combined into TreeStab in our GitHub repository.

---

Published as a conference paper at ICLR 2026
TreeGrad Rankeer with GA
TreeGrad Ranker with ADAM
Banahaf
Setainsertion
Buta Deletion
Beta-joint
0.40
predicted probabilty
grabability
predicted probabillty
0.5
9.4
0.30
0.4
0.3
6:25
00.3
0.29
0.0
0.0
20.12
grddeted wrobabilty... 2000
20.17
aredicted grobabilky
0.10
0.125
8.09
0.325
0,100
0.06
0.100
6.075
0.075
0.050
2.00
0.025
0.000
FOTP (T) 20)
GPSP (7) 10)
jannis (T) 40)
Figure& 4: The trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or lower deletion curve indicates better performance. For our TreeGrad-Ranker we set T 100 and 5. Beta-Insertion selects the candidate Beta Shapley value that maximizes the Ins metric for each fx. whereas Beta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric Ins DDl. The output of each f(x) ) is set to be the probability of a randomly sampled non-predicted class.
7 CONCLUSION
In this work, we revisit the evaluation of feature rankings through insertion and deletion metrics and demonstrate their connection the problem (5). From this perspective, we establish theoretical limitations of probabilistic values, showing that they are no better than random in distinguishing patterns and that their reliance on linearization may render them ineffective. To address these short- comings, we propose directly solving the problem (5) using gradient ascent. We developed Tree- Grad to compute these gradients for decision trees in (T.) time. We show that solving problem (5) yields feature scores that satisfy all axioms uniquely characterizing probabilistic values, except lin- carity. Furthermore, our TreeGrad-Shap is the only numerically stable algorithm for computing Beta Shapley values with integral parameters. Our experiments show that TreeGrad-Rane outperforms probabilistic values on both insertion and deletion metrics.
ACKNOWLEDGMENT
This research is supported by the National Research Foundation (NRF), Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) pro- gramme. The Mens, Manus, and Machina (M3S) is an interdisciplinary research group (IRG) of the Singapore MIT Alliance for Research and Technology (SMART) centre. YY gratefully acknowl- edges NSERC and CIFAR for funding support.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
John F Banzhaf III. Weighted voting doesn't 't work: A mathematical analysis. Rutgers Law Review, 19(2):17-333, 1965.
Blair Bilodeau, Natasha Jaques, Pang Wei Koh, and Been Kim. Impossibility theorems for feature attribution. Proceedings of the National Academy of Sciences, 121(2):2304400120, 2024.
James P Bridge, Sean B Holden, and Lawrence C Paulson. Machine learning for first-order theorem proving: learning to select a good heuristic. Journal of automated reasoning, 53:141-172, 2014.
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
lan Covert and Su-In Lee. Improving kernelshap: Practical shapley value estimation using linear regression. In International Conference on Artificial Intelligence and Statisties, pp. 3457-3465, 2021.
Ian Connick Covert, Chanwoo Kim, and Su-In Lee. Learning to estimate shapley values with vision transformers. In The Eleventh International Conference on Learning Representations, 2022.
Pradeep Dubey, Abraham Neyman, and Robert James Weber. Value theory without efficiency. Math- ematics of Operations Research, 6(1):122-128, 1981.
Alfredo Eisinberg and Giuseppe Fedele. On the inversion of the vandermonde matrix. Applied mathematics and computation. 17442):1384-1397, 2006.
Uriel Feige, Vahab S Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. 2011.
SIAM Journal on Computing,
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Christopher Frye, Damien de Mijolla, Tom Begley, Laurence Cowton, Megan Stanley, and Ilya Feige. Shapley explainability on the data manifold. In International Conference on Learning Representations, 2021.
Léo Grinsztajn, Edouard Oyallon, and Gaël Varoquaux. Why do tree-based models still outperform deep learning typical tabular data? Advances in neural information processing systems, 35: 507-520, 2022.
Nicholas Hale and Alex Townsend. Fast and accurate computation of gauss-legendre and gauss- jacobi quadrature nodes and weights. SIAM Journal on Scientific Computing. 35(2):A652AA674 2013.
Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lee, and Rajesh Ranganath. Fastshap: Real-time shapley value estimation. In International conference on learning representations, 2021.
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. The 22nd International Conference on Artificial Intelligence and Statistics, pp- 1167-1176, 2019.
Zhongli Jiang, Min Zhang, and Dabao Zhang. Fast calculation of feature contributions in boosting trees. In The 41st Conference on Uncertainty in Artificial Intelligence, 2025.
Adam Karezmarz, Tomasz Michalak, Anish Mukherjee, Piotr Sankowski, and Piotr Wygocki. Im- proved feature importance computation for tree models based on the banzhaf value. In Uncer- lainty in Artificial Intelligence, pp. 969-979, PMLR, 2022.
François Kawala, Ahlame Choual-Chouakria, Eric Gaussier, and Eustache Dimert. Prédictions l'activité dans les réseaux sociaux en ligne. In 4ième conférence sur les modèles et l'analyse des réseaux: Approches mathématiques informatiques, pp. 16, 2013.

---

Published as a conference paper at ICLR 2026
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2015.
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, pp. 19246-13255 2024.
Yongchan Kwon and James Y Zou. Beta shapley: work for machine learning. In International Conference on Artificial Intelligence and Statistics, pp. 8780-8800 2022a.
unified and noise-reduced data valuation frame-
Yongchan Kwon and James Y Zou. Weightedshap: Analyzing and improving shapley based feature attributions. Advances in Neural Information Processing Systems, 35:34363-34376, 2022b.
Weida Li and Yaoliang Yu. Robust data valuation with weighted banzhaf values. Advances in Neural Information Processing Systems, 36, 2023.
Weida Li and Yaoliang Yu. Faster approximation of probabilistic and distributional values via least squares. In The Twelfth International Conference on Learning Representations, 2024a.
Weida Li and Yaoliang Yu. One sample fits all: Approximating all probabilistic values simultane- ously and efficiently. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024b.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in Neural Information Processing Systems, 30, 2017.
Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex 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.
Renata CB Madeo, Clodoaldo AM Lima, and Sarajane M Peres. Gesture unit segmentation using support vector machines: segmenting gestures from rest positions. In Proceedings of the 28th Annual ACM Symposium on Applied Computing, pp. 46-52, 2013.
Jean-Lue Marichal and Pierre Mathonet. Weighted banzhaf power and interaction indexes through weighted approximations of games. European Journal of Operational Research, 211(2):552-358,
2011.
Dunean McFlfresh, Sujay Khandagale, Jonathan Valverde, Vishak Prasad C, Ganesh Ramakrishnan, Micah Goldblum, and Colin White. When do neural nets outperform boosted trees on tabular data? Advances in Neural Information Processing Systems, 36, 2024.
Maximilian Muschalik, Fabian Fumagalli, Barbara Hammer, and Eyke Hüllermeier. Beyond tree- shap: Efficient computation of any-order shapley interactions for tree ensembles. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 14388-14396, 2024.
Guillermo Owen. Multilinear extensions of games. Management Science, 1865- 1972.
Victor Pan. How bad are vandermonde matrices? SIAM Journal on Matrix Analysis and Appli-
cations, 37(2))676666 2016.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learning in python. Journal of machine learning research, 12(0ca);2855-2830) 2011.
Vitali Petsiuk, Abir Das, and Kate Saenko. Rise: Randomized input sampling for explanation of black-box models. arXiv preprint arXiv: 000011000077755 2018.
Byron P Roe, Hai-Jun Yang, Zhu, Yong Liu, Ion Stancu, and Gordon McGregor. Boosted decision trees as alternative artificial neural networks for particle identification. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associ- ated Equipment, 543(2-3):577-584, 2005.
12

---

Published as a conference paper at ICLR 2026
Lloyd S Shapley. A value for n-person games. Annals of Mathematics Studies, 28:307-317, 1953.
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Conference on Al, Ethics, and Society, pp. 180-186, 2020.
Evgenij Tyrtyshnikov. How bad are hankel matrices? Numerische Mathematik, 67(2)261-266, 1994.
Jiachen Т. Wang, Tianji Yang, James Zou, Yongchan Kwon, and Ruoxi Jia. Rethinking data shapley for data selection tasks: Misleads and merits. In Forty-first International Conference on Machine Learning. 2024.
Robert James Weber. Probabilistic values for games, pp. 101-120. Cambridge University Press, 1988.
Jilei Yang. Fast treeSHAP: Accelerating SHAP value computation for trees. In eXplainable Al approaches for debugging and diagnosis., 2021.
Peng Yu, Chao Xu, Albert Bifet, and Jesse Read. Linear treeshap. Advances in Neural Information Processing Systems, 35:25818-2558 2022.
Jiayao Zhang, Qiheng Sun, Jinfei Liu, Li Xiong, Jian Pei, and Kui Ren. Efficient sampling ap- proaches to shapley value approximation. Proceedings of the ACM on Management of Data, (1):1-24, 2023.
13

---

Published as a conference paper at ICLR 2026
Table of Contents
Semi-Values
B Polynomial Manipulations in Linear TreeShap
15
C Implementation of TreeProb
15
How to Evolve Linear TreeShap into TreeShap-K
E One More (LLD)-Time and O)D Algorithm for Computing the Shapley Value
17
F Missing Proofs
19
Experiments
25
A SEMI- VALUES
One popular way to rank features is by using the Shapley value, as it uniquely satisfies the ax- ioms of linearity, null, symmetry, and efficiency (Shapley, 1953). Based on the Shapley value, the contribution of the i-th feature can be expressed as
s!(N - 1 s)) (((SU [x()
Shap (fx) = Σ
N!
SEINIV
where (x(S) = Exge (x(s, X.s)] where xs is the restriction of x on S and S = [N]] S. Fol- lowing Lundberg al. (2020, Algorithm 1), the computation of [x( is described in Algorithm 9.
Recall that each probabilistic value can be expressed as
of (fx)
Σ Wa+1
SEINJV
where RV is non-negative with Ei (N-1) 1. Besides, d= is semi-value if and only if there exists Borel probability measure f over the closed interval [0, 1] such that for every k [M]
Wk / t -1-111))~aa(())
(10)
Therefore, nd (fx) is used to denote semi-values. If ya is some Dirac measure 6,, the resulting semi- value is a weighted Banzhaf value parameterized by и E [0, 1]. If u(A) x SΛA ==-1(1 =),- it leads to Beta Shapley value parameterized by (a, B); in particular, the parameter (1, 1) leads to the Shapley value.
Symmetric semi-values. A semi-value d" is said to be symmetric if w/ WN+1-A for every 1 S < N. In particular, the Shapley and Banzhaf values are symmetric. Combining Eqs. (7), (9) and (10), we have
[ Σ 11-1))--1~( (p))
6e (fx)
SCINIV
(t 1n) du(t).
In particular, if df is symmetric, we can derive
8² -- (+x)==
(12((1 - dx(t)
14

---

Published as a conference paper at ICLR 2026
Therefore, for symmetric semi-values, have
1 Fx(t / v
@ (fx)
(1- -N) (1) 1n(])
In other words, symmetric semi- can be derived from the gradient field of the objective in Eq. (6). This motivates averaging the gradients produced by our TreeGrad-Rane (Algorithms
and 11) to generate feature scores.
B POLYNOMIAL MANIPULATIONS LINEAR TREESHAP
In manipulating polynomials, the most expensive step is the multiplication of p(y) and (1 + y)d-des(r), the degree of each is at most D in the context. In general, polynomial multiplication quires O(D log D) time to compute using fast Fourier transform (Cormen et al., 2022, Chapter 30), which would lead to time complexity OLD log D) in total for computing @Shap (fx)) Nevertheless, since the polynomial (1 + y)d-dcg(p) is simple, Yu al. (2022) propose encode all polynomials of degree at most D - into vectors of dimension D using a Vandermonde matrix V E D i.e., each polynomial p(y) is encoded by its evaluation Vp at D different points, and then the multipli- cation can be computed in O(D) time using the encoded vectors. Since the inverse Vandermonde matrices can be computed once in O time (Eisinberg & Fedele, 2006), it does not increase the time complexity in total. Let p(y) and (()) be two polynomials of degree at most D - 1, by Yu et al. (2022, Lemma 2.5), the formula used evaluate & is (p(y), {(v)) (p. q) = (Vp. (V (V-I)Tq).. q)..
Numerical Instability. Empirically, we observe that numerically error grows as the number of nodes increases. To mitigate this numerical instability, the implementation of Linear TreeShap does not follow the O(LD)-time procedure." We illustrate this difference using Algorithm 3. Upon reaching a leaf (line 46), Linear TreeShap computes p(y) f fufe p(y). In line 48, it performs
(v) + traverse(ae, P(Y)), pb(y) + traverse(b,, ((y))) dmax f- max(deeg(Pa)) p(y) < Pv() (1 + demm<-dee(())) deg(pa(u)) + (b()) (1+ y) deg((ss))
(e)(ps(y)))
As a result, when evaluating & in line 52, the degree of G[v] is not fixed, and may vary from 1 to D. Consequently, given D nodes, the algorithm has to compute V for every d E [D]. where Va E Raxd denotes the Vandermonde matrix of the first d nodes. This effectively reduces the number of nodes involved each computation and thus partially alleviates the inherent numerical instability. However, this strategy increases the time complexity from O(LD) to O(D3 + LD).
C IMPLEMENTATION OF TREEPROB
Similar to Linear TreeShap, our TreeProb is composed of two procedures: (i) a traversing-down
procedure that for every leaf node E L, accumulates all the polynomial components from the root to v one by one and (ii) traversing-up procedure that decodes the accumulated polynomials and distributes the decoded results to all participating features. Starting from the root r, write P.-
(e1, ez...., e)P).) .(p.) in the order in which the edges are encountered as we traverse down the path P. the leaf node v. Then, TreeProh accumulates the polynomial components as follows:
1+ (1 Yee y), et exists,
p)-((y)
po(y)= + 1 and pe(v)= <
pC-1 (1+ Ne, v), otherwise.
Once it reaches the leaf node v, there Rucu PIr. (1) Gy). While traversing up, the formula
use is
EvEr Goly): (1 + (1+y)D-aae Degg(GG.)
(T2)) (6e 1)(
1 (v))
1 14%
http://wwwwaaa.oooo/o.eeeeee/e/a shap/fast. theer__tree_sha_c.
15

---

Published as a conference paper at ICLR 2026
Algorithm TreeProb
Input: Decision tree T = (V, B) with root r and depth D, instance x E R poly- nomial ((y) of degree min (D,N) - 1 with non-negative coefficients that satisfies
Ek=o Dmin(D.N)-1 (min(D.N)-) 9k+1 =1
k Output: Probabilistic value Φ
28
Function traverse (v, p(y) = 1)
29
e (my v)
30
if exists then
p(y)
31
p(y) 1 Vet
(1 + The .))
32
else
33
p(y) - ply) (1 + Ye .))
if v is leaf then
p(y) - Rufx ply) (1 y) minn -ogg(())
35
else
37
p(y) + traverse (a,, p(y)) + traverse (b. p(y))
38
e exists then
Glh t G[a p(y)
39
40
Glu] + Glu] +
41
dE < dr. + (7 - 1). (1tte (()))
42
return p(y)
43 Initialize G[u] = for every u E V
Initialize o On
45 traverse (a,)
traverse (b,))
47 return 6
where
D-1
D N- Wk+s+1 Σ
N
(- Σ
yt
(11)
which is derived by recursively applying the equality in Lemma 3. At first glance, this formula may appear complicated; however, it can be efficiently implemented using lines 47-51 of Algorithm 3. For semi-values d" (fx),, write (1) instead, which can be computed using Eq. (8).
Remark 1. Note that Eq. (11) is well-defined when N Z D. However, if N < D, can simply sel D N. By contrast, Eq. (8) is always well-defined. Therefore, we recommend applying
D - min(D, N) before running Algorithm 3.
Remark 2. For probabilistic values, it is more convenient to specify (V)((V) instead of deriving from w. particular, there must be DD-1 (D=1)qu++ where qu is the k-th coefficient of (9))
The pscudo-code of our TreeProb is presented in Algorithm 3. One may think that the space com- plexity OLLD). We remark that there are only O(D) polynomials that are needed on the spot and thus the complexity is O(D2 Therefore, for computing probabilistic values, the time and space complexities of TreeProb are O(LD) and O + L), respectively.
D How TO EVOLVE LINEAR TREESHAP INTO TREESHAP-K
How to avoid the use of Vandermonde matrices? As discussed in Appendix B, the role of Vander-
monde matrices is to save the computation time of the scaling Gy) (1 + dd performed every non-leaf node from O log D) O(D). Our observation is that such scaling can be
16

---

Published as a conference paper at ICLR 2026
performed just once for all (v()). Starting from the root, write P. (e1: Cg...., epp)) Cpp |) in the order encountered when traversing down the path Pe to the leaf node e. modified procedure for collecting the polynomial components is
Pe-1(y)
(1+ Ves v), ef exists,
1+7
Pu(y) t (1 (1+ v) and pe(v) +
Pe- Pe-1(y)
(1 (1+ Yee 8),
otherwise.
1+ y
similar technique is employed in Marichal & Mathonet (2011, Appendix E), and thus their pro- posed algorithm is free of Vandermonde matrices. It is worth pointing out that the assignment of Po(y) performed once and costs O(D²) time in a recursive way.
By traversing down in this way, we can store each polynomial p(y) = Ei= Pk+1V as its coeffi- cient vector p E IRD D-1 For updating (v)) < p(v) (1+7-y), we simply run 9: = Pk P with Note that this process costs (D) time and can be reversed in O(D) time. However, this reverse process is essentially solving linear equation, and we observe empirically that the corresponding condition number grows exponentially w.r.f. if 2
p-1 = +2
How TreeShap-K computes the Shapley value. What TreeShap-K K stores, instead, a vector 0r E RD+1 where oy represents the i-th coefficient of G.(y) (1 + D) D [F.l.
0. = loCx Σ 15|=k
cr SCF, Ihes Vi. Then, while traversing down, each d can be computed by
Oo < In+1 and O2 +- ( (0/-1 0 TT2)) ① Yeo of exists, (0 e + Yeer otherwise.
Here, suppose & E D+1 for + & + 2,, it
Pk - D + 1 - k
- 1 Ek 1
EN +
(12)
D+1
D+1
whereas y denotes the reverse process. The convention is {-1 = ED+ = O. Then, PaCr 1p.. 8r. What TreeShap-K K computes in the traversing-uy up procedure is
=
Shap (fx)
Σ (Th - 1) sum Σ
8" @
EEB
VEL.
where sum simply adds up all the entries. All in all, TreeShap-K proposed by Karezmarz et al. (2022, Appendix E) is summarized in Algorithm 4. We point out that the e operation essentially involves solving a linear equation, whose condition number, as shown in Figure 2, grows expo- nentially w.r.t. D (with y set to 1). Indeed, the substantial inaccuracy of TreeShap-K K is already confirmed by Karczmarz et al. (2022, Figure 1).
E ONE MORE ((L))-TIME AND O(D² L.-SPACE ALGORITHM FOR COMPUTING THE SHAPLEY VALUE
For completeness, we also summarize the technical details of one more O(LD)-time and O(D2 + L) L)-space algorithm for computing the Shapley value, which was developed by Yu et al. (2022) as their first version. Therefore, we refer to this algorithm Linear TreeShap V1. is totally different from Linear TreeShap, and is less numerically stable, 6 To our knowledge, its technical details are missing, probably due to its numerical instability. Nevertheless, it is with moment's thought to
saaee_ssapp/pee / blbb/ /main/ linear tteee_rteeee__ shap/1 inar__ree__happ sattappmubbba.mm .ammba.py.... py- The code therein cannot run, hut can he fixed by replacing the first three tree. with tree. max_depth
chttps://gitie
lines 145-146.
hhttps://githin wwtp//pwaw//////////oo//poo inear_tree saaree_shapblle ob/ma ma i /tstss//
correctness.cov
17

---

Published as a conference paper at ICLR 2026
Algorithm 4 TreeShap-K
Input: Decision tree T = (V, E) with root and depth D, instance x E RN Output: Shapley value
48
Function traverse (v, 0 M41 1M+1);
49
e e (mg + +)
50
e existy then
0 <
Tet Te
52
else
53
0 (0 1) o %
54
if v is leaf then
0 2oc.
55
56
else
0 - traverse (ay, 0) traverse (b.. 0)
e exists then
S8
1 1 t- 8 19h11-6
59
d(u) 0[u +
60
S1. < 01. (7e 1) sum(0[u] 7c)
62
return A
M mimmm) ND
64 Initialize 0[u] = OM+1 for every E V
Initialize Φ ON
" traverse (a,-)
" traverse (b,)
return Φ
decipher Linear TreeShap V1 from the code by observing that it uses %e rather than % when traversing down the tree. It is based on the fact that
Shap (fx) (bap((x) S/ Ee(1) di
where Et
Σ
t'(1 1) (((UU)) (x(S))
SCINRi
Since Et(() is a polynomial of degree at most N - 1, we can express Ex(t) as
N-1
E,(t)
Σ
aid.t
d=0
Then,
N-1
Shap (fx) (ha) = Σ
0g,d
d+1
d=0
Lemma 4. Replacing fx with Ry where (5) 2. er
I V5.0 for every S S [N], we have
ag, = 2n (7/,v - 1) Cr Σ
II
1).
SC
iEE
Proof. Observe that
Et(t) = go (7/,0 - -1) C.
Σ (11 - N-
Cr
SC[NI
JES
Cv II
= = - 1).
(1+t (13.0 - 1));
cr
jE[N]
from which the conclusion follows.
18

---

Published as a conference paper at ICLR 2026
Algorithm 5 Linear TreeShap V1
Input: Decision tree T = (V, E) with root r and depth D, instance x E RN Output: Shapley value
69
Function traverse (v, c = e1
70
+ (my +
et exists then
71
c (c (7et 1)) 1 (Te 1)
73
else
c cffff (7e- 1)
75
i is a leaf then
Rafa Cr
77
else
78
- traverse (av, c) + traverse (b,, c)
e exists then
Cl + Clh
80
C(uj Clu] +c
(C[u) B (Ye 1))a
Φt. + 11. (7e 1). Σ M+1
return c
M min(D,N)
85 Initialize Clu] = 0M+1 for every v E
Initialize Φ = On
n traverse (a,,)
traverse (b,)
89 return b
Accordingly, after Linear TreeShap VI traverses down the path P. (el, E2, ........,.... ,pp,)) it stores
vector L" E RD+1 where o Σ SCF, ==k-1
[7je 1) if k F. and 0 otherwise.
One nice property is that, after introducing null player (with 7A,v 1), t" DR1 remains unchanged. All in all, while traversing down, each e" can be computed by
(ce- B (7.t 1)) M (Te, - 1), e7 exists,
Co - er and and cτ
c--1 W (Tea 1),
otherwise.
where e1 E P++1 denotes the vector whose first entry is equal to and all other entries are equal to 0. Here, suppose d E D+1 for c + d (7 1). it
C = (- 1) d
whereas & denotes the reverse process. The convention is d 0. Then, L" 2. CIP. Algorithm 5 demonstrates how Linear TreeShap VI runs. In our inspection, observe that the condition number of E does not even exceed 100 when D = 100. However, its numerical error still blows up, which suspect is due to the repeated use of E.
F MISSING PROOFS
Proposition 2. Let π be a ranking induced by a probabilistic value 6itd (Jx) such that &% ((()((>)) 2 (fx) th (xx) For every S S N, St = {m(1),, (2)...., [ an optimal
solution to the problem
1 (g" 9 ([N] 8)) SCIN
maximize
where g" the best linear surrogate for fx. i.e. g" = arg min Bec EscIN) Ms41 (fx(() g(S))²
with C = {g gSS) = to Eiestt) The weights satisfy (i) m, 7N+1 2 0 and (ii) n = w, W
for 2 < N.
19

---

Published as a conference paper at ICLR 2026
Proof. As provided by Li & Yu (2024b, Theorem 2), there exists scalar C' R such that for every i E [N]
g ((+))) - (0) = (fx) C.
where IN R- is the all-one vector. Then, it is clear that S optimal to the problem
(g" (g" (5) - g" (M
arg max $C M,
by which the conclusion follows.
Proposition Suppose ((fx) E TR is linear in with N 3, which includes all probabilistic values. Then, there exist distinct sets S1 and S2 such that S1 # [N] \ S2 and
Rel(h; S1, = inf U:Do(S))SD((Sa)
inf [1 h(o(U)) + Du
h(o(U)) S 1.
Proof. This result is immediate if we can find two distinct subsets S1 and S2 satisfying S o [N] S2, and utility functions Un and U1, such that (U,) (U1), Du, (Si) S Doo (S2), and Du, (S1) > Du, (S2).
Observe that each U be represented subsets of [M]. Since & is a linear operator, its null space N has dimension at least 2 N. sufficient to find vector S + [N] \\ T and [sign(xs- - #[N]ys) sign(ær #[NTrr) 2.
vector X R whose entries correspond to all
., for which there exists distinct subsets S and T such that
Let P H... [ S): S C [N]] and then |P| 2 For each (S, S} E P. let Choice ((5, [N] $}) randomly choose one of the it contains. Then, let (Choico(S)::
P) and we have [ = 2N Define a linear operator L that maps each x to y 1=2~1 by setting
ys = .s-- i for every I. Notice that the dimension of the null space of exactly 2 Denote the null space of L by null I and write dim for dimension. By the rank-nullip theorem, there is
dim N dim mull Llv dim L(N).
Therefore,
dim L(N) = dim V dim null L|x 2 2 N - 2 2N-1122N1 22 N.
Given that N 3, we have dim L(N)= > indicates that we can find an such that least two entries of == L(x), say S and T, are nonzero. If sign(ys) = sign(Vr), set T + [N] T. O
Theorem 1. The vector of feature scores Ç returned by FreGGradRaanke, either using Algorithm
or 11, be expressed as S; EsgINIy W[(S; (Sx(S U {x(S) where wx(S;x) x) and Esgnyy w Moreover, verifies the axioms of dummy, equal treatment and monotonic- ity.
Let 2 + utility function and denote by G the set that contains all such utility functions.
The axioms of interest are listed in the below.
1. Linearity: d(c- U +U) = c o(U) + o(U') for every U,U" E & and e E R.
2. Equal Treatment: For some j,j E [N], if USUi)) = USSUj) for every S S (t,.),
then @i(U)= = (U)
3. Symmetry: 6UU a T) = =U)) o π for every permutation π of [N].
4. Dummy: For some i E [N] if there exists some C' E such that U(SU = U(() +
for every S [N] Then, (U) C.
5. Monotonicity: For some [N]. (i) US 2 U(S) for every C [N] \1, then
or(U) 2 0; (ii) Uf US) for every S C [N] \ then ox) < 0.
6. Efficiency: EiENn [0)==([[]] (0)) for every U g.
20

---

Published as a conference paper at ICLR 2026
Setting C. 0 in the dummy axiom yields the null axiom. As aforementioned, the axioms of lin- earity, dummy, monotonicity and symmetry uniquely characterize the family probabilistic values. By Li & Yu (2023, Appendix A), the symmetry axiom is equivalent to the axiom of equal treatment in the context.
Proof. Combing Eqs. (7) and (14), each VJx (z) can be expressed as
(z)x(z)=
Σ
(((S)/ (x()))
SCINTV
where wx) 2 0 and (.)) for every E [M]. Since Ç returned by Algorithm 2 is an average of gradients, it is clear that for every e [N],
Σ ((S fx(8)
SCINIV
where (S; 2 0 and EScINj (S; 1. The dependence of x comes from that different instances of x would induce different trajectories along which the gradients are accumulated and averaged. Suppose there exist feature e [NV] and a constant C E R such that fx(S U fx(5) + C for every S _ [N] \ i. In this case,
(zfx())=CC =
Σ wi(S) C for every E [0,1]*
SCINIV
On average, it is clear that G C. Therefore, < satisfies the dummy axiom. Similarly, one can verify that satisfies the monotonicity axiom.
Suppose there exist two features and such that (x Observe that are averaged over T graaddeetss. At the 1-th step, we denote the produced gradient by ((z((_1)), Note that we set z (0) = 0.5 1N. which corresponds to the Banzhaf value. Therefore, we already have (z)) 9, (z))). The next step is to prove by induction that (i) (z-)((
for every S S [N] ft,
g (x-1))) and 2, ((-1) 2) (1-1) (ii) for every Suppose is true at the t-th step, for the next step,
we have
(t)
= z (1-1) gi (z = 2 (1-1) - 9i (z (t-1)) = =2/
2i
Let wo(S; = Ihes 2i, m5; = II 2ÿ) and A = (x(SU -x fx(). For simplicity, we only consider the gradients of / (z). The other part fx(1N z) can be trivially included. Then,
(z)
Σ SCIMI
w(S; (S,
Σ SC(NIM(JJ)
(S): +
Σ
w(S wiSLjji2\mm,sSUU:))44444/.
SC MM(
Σ
Σ
(E(N
SC(N).(6.))
Σ
SEIMM
-g
Since gi ()) = (2) for every t, we have Ç; = Gy- Consequently, Ç satisfies the axiom of equal treatment. For Algorithm 11, can be proved similarly.
Lemma 3 (Generalization of Eq. (3)), Suppose p(v) is polynomial of degree N - 2, we have (p(v) (1 y), EN-I Wk+1 y²) (p(v), IN=2 (Wiet (444))"
21

---

Published as a conference paper at ICLR 2026
Proof.
N-1
2-2
N-2
N-2
(p(v) (1+ 8).
Σ
Wk+18 = Σ PkWk+1
Σ
P
Σ k=0
(W++1 + Wk+2)pm
k=0
k=0
k=
= (p(),,
(W++1 wx+2)1")
K=U
Corollary 1. TreeGrad-Shuu (Algorithm 7) computes Beta Shapley value with integral parameters using (IDD) time and O + L.) space. Without vectorization (Algorithm 6), its space complexity O()).
Proof. By linearity and (Dubey et al., 1981, Theorem 1(a')),
Shap @happ(x) (fx) = / (t 1x)dt = L/
Σ wetr
VR 1y)dt
Using Eq. (7),
V (L
E
(11-1)-11-1 Rg()),
8EIM]V
which corresponds to the weighted Banzhaf value parameterized by (Li Yu, 2023). Suppose j & F.,, and notice that () = (S) for every S S [N]. Then,
R. 1N)
Σ t0 ([ -
SCNNME
By removing all features not in F., have
(t-
Σ
t- ((1-t) (()- R((().
(13)
SCR.
Since |F S D, the degree of the polynomial V. 1x) ViTi Ix) at most
D 1. According to the Gauss-Legendre quadrature rule, we have
Shap (fx)= = Σ Ke VTx 1x).
According to Hale & Townsend (2013), {le)e and {ne)e can be computed in O(D) time.
Since each gradient (te 1v) can be computed in O(L) time using O(L) space, the space com- plexity is reduced by reusing the same allocated space. This proves the validity of TreeGrad-Shap. shown in Algorithm 6.
Proposition 3. Suppose the optimal set S* for the problem (5) is unique, then 1s- whose i-th entry is i S and otherwise is the unique optimal solution to the relaxed problem (6).
Proof. For simplicity, we write USS) = (fx(S)) fx([N] S)), and thus U(z) = 2 [F)((z)
Tx 2)). Let U = arg maxsc[N] USS). For each & (0,1)., notice that U(z is just weighted average of (U(S)) because
N = (1 2, + 2;) = 1.
Σ
I LES
z
[a- igs
II
(14)
SCINI
1=1
Therefore, (22) < U* For the sake of contradiction, suppose U(x) = U*, then there must exist
two distinct subsets S, and S₂ such that U(S) U(2)) = U* which contradicts the assumption that S* is unique. Therefore, we have (x( l
22

---

Published as a conference paper at ICLR 2026
Algorithm FreeGrad-Shap
Input: Decision tree T = (V, E) with root and depth D, instance x E R.,, integral parameter
() that specifies some Beta Shaple value
Output: Shapley value Φ
90 Initialize Φ ON
91 M + min () + + + 2
Generate
M 2
pair of weights and nodes {(Ke, (e)) according to the Gauss-Legendre quadrature // the closed interval [0, 1]
rule
for l = 1 1 do
Φ + ni TreeGrad(T, x, 1N) -t tz)a-
94
Algorithm 7 TreeGrad-Shap (Vectorized)
Input: Decision tree T = (V, E`) with root r, instance x E RV,, integral parameter (a, 3) that specifies some Beta Shaple value
Output: Shapley value Φ Function traverse (v, s b)
95
(my v)
if e exists then
98
s s s.
t
No No t)/(1 + 7et
// element-wise
else
100
8 + s. s- (1- t+ No -t)
v is leaf then
s s Paçe S
else
104
s + traverse (a,, s) + traverse (b,, s)
105
if exists then
106
H + H
H + H[ +
Φ1. + 11. + (7e (1) - Ta. t), re)
return
M- min( +NN))
110
111 Generate the weight vector &t E RM and the node vector t E RM according to the Gauss-Legendre
quadrature rule
// the closed interval [0, 1]
112 Compute b E M by by + ta -1 tz)a01111/1)00 /Bar,
Initialize H [ O& for every E V
114 Initialize Φ = On
traverse (a,))
116 traverse (b,)
return 6
Lemma 1. We have (, (7i, 1).
H.
where H,
Luri cr
IIJER, (1 (1-22 25
Proof. Similar to the derivation of Eq. (13), there is
V (2)
LoCu
(7i,0
Σ
II jES
(I
er
SCF.
JESUS
The proof is completed by noticing
[II
II (1 (1-22) (1)))
Σ SCFAM
II JES
II (1 (1- 22
jeSUi
JEP.
23

---

Published as a conference paper at ICLR 2026
Algorithm 8 TreeGrad (Full Procedure)
Input: Decision tree T = (V, E) with root r, instance X E RR point z E [0, [0,
Output: Gradient g
Function traverse (2, 8 = 1)
(my -1
if 2/e + 21. Te 0 then
121
e exists then
122
$ 1-
123
e a leaf then CaCe
else
126
8 + traverse-zero (a. 8, Le) + traverse-zers (6,, 8. Lc)
127
91. f 91. return 0
else
130
e exists then
1-21- +2 net (1 21 + 21 7c)
132
else
+-++ (1 21e + =1 Vo)
134
e a leaf then ca
else
137
8 + traverse (a,, 8) + traverse (6., 8)
if e exists then
H(h +- H Hhat]]
139
[[v] H [b] +
141
9h. + S. + (Te - 1)
-1, +8,
Hlv
return
Function traverse -erro (v, l):
144
e - (my u)
if le + then
146
21 + 21,% = 0 then
return 0
if e exists then
8 8t 21- 21 Net
(1 24e + 217
else
151
8 + 8 (1 21. + 76)
152
i is a leaf then
154
else
+ traverse-zero (ag 1) + traverse-zero (b., ()
return
Initialize H(u) 0 for every v E V
158
Initialize g = 0w
traverse (a,,)
160
traverse (b,))
return g
Eveet H.
Lemma 2. (z Eeen(Te - -1) 6-)
24

---

Published as a conference paper at ICLR 2026
Algorithm 9 Computation of fx
Input: Decision tree T = (V,5) b) with root instance X E IR subset S S [N]
Output: Realization of Ex.- (xs, Xs+)]
Function traverse (
163
e leaf then return Qr
165
L, E then
if 21, To then
167
return traverse (d.)
else
169
return traverse (b,)
170
else
return
traverse (a₂) She traverse (b,)
Go
172
return traverse (r)
Algorithm 10 Efficient Evaluation of fz(z)
Input: Decision tree T = (V, E) with root r, instance E RRN, point z E 10
Output: The evaluation of (z) Function traverse (v, 8 = 1)
173
(my + v)
if e existy then
176
8 + 1-21 t31
(1
21, + 21, 7c)
else
178
8 + s. (1 21 + 7e)
if v is leaf then
S Queu
180
else
182
8 traverse (ap, 8) traverse (b,, 8)
return
184
return traverse (a,) + traverse (b,)
Proof.
Let be fixed, one can verify that (I,, feEE, forms partition of I,,. Therefore,
H
vzfx(z)= = Enu 1) 1- 2171.
(Tr - 1) 1- 22 + 2570.0
vELr
EEE
DEL
By the definition of Lh,, we have Ti. Ye. and thus the conclusion follows.
G EXPERIMENTS
The full procedure TreeGrad is presented in Algorithm 8. The information of the datasets we employ is summarized in Table 1.
decision trees, additional experimental results are presented in Figures 6 and 7 for classification tasks, whereas results for regression tasks are shown in Figure 8. Our TreeGrad- Ranker also works for gradient boosted trees (Friedman, 2001). We train gradient boosted trees on the same datasets using GraadientBoostinnglaasii sor from the scikit-learn library. The corresponding results are presented in Figures 9-13. For classification tasks, the output of each gradient boosted trees model is be the logit of the selected class.
More experimental results.Usin
and GradientBoostingReggss
More experimental settings. For all trained decision trees, the only hyperparameter we control the tree depth D. The random seed of training is set to 2025 to ensure reproducibility, while all
25

---

Published as a conference paper at ICLR 2026
Algorithm 11 SereGGra--aakeer with ADAM
Input: Decision tree T (V, Σ') with rool instance X E R learning rate >> 0, iteration T.
Default hyperparameters of ADAM are: B1 0.9, B2 0.999 and e' 10-8
Output: Vector of feature scores Ç
188
Initialize 0.5 1N. Ç = ON. my O2 and Vo 0,
for / 1. .., T do
187
g { (TreeGrad x, 2) + TrooGrad x, 1N - 2))
Ç - { 7 -g
[-
189
m, + $1 -- (1 11))
190
Vi + - + (1- B2) .g²
m + -m/(11 1-8 -
191
192
V t ve/(1= - -13)
193
Z - t m./v N. +
194
z Proj(z)
// 24 f- min(max(0, 2;),
return Ç
Table 1: Summary of the datasets used in this work.
Datasel
#lnstances
#FFeutures
Link
Task
#Classes
FOTP (Bridge et al., 2014)
618
51
https: httgss://opmmmm/rr///////
classification
GPSP (Madco et al., 2013)
9, 873
32
halg:://tpemml.crg/////333
classification
jannis
83, 733
httgs:://oemm...cr//c//// classification
classificution
MinibooNE
2005)
130,064 06-1
50
ottger//openmm..cz////81111
philippine
5, 832
308
https://opemm..orrr//8lll1
classificution
spambase
4,60 4,601
57
classification
BT (Kawala et al., 2013)
583,
77
httast://opami.orrs////
regression
superconduct
21,
81
regression
wave energy
72,000
48
regression
other hyperparameters are left at their scikit-learn defaults. The tree depth used for each dataset is reported in the corresponding figure. For gradient boosted trees, set the number of individual decision trees to 5 for all datasets. Table summarizes both the sizes of the trained models and their performance the test datasets.
Experimental details for producing Figure 2. For plotting the condition number of TreeShap- K. we 7 1, which appears Eq. (12). For reporting the inaccuracy when computing the Shapley value, the used decision tree f is trained on the dataset Click_predictet small with 11 features.? 7 With N 11, it is tractable to compute the ground truths using Eq. (1). While varying the depth D, we report the average error || Φ1 over 5 different instances of x. The algorithm for running Linear TreeShap is from the public repository provided by Yu et al. (2022). 8 For fair comparison, the inaccuracy of Linear TreeShap (well-conditioned) is obtained by simply replacing the Vandermonde matrix used in Linear TreeShap with the well-conditioned one.
Further inaccuracy analysis. In Algorithm 3, the number of nodes is determined by M + min(D, .V). If we include TreeProb in Figure 2, .M would be fixed as 11, since quently, this setting would not reveal when TreeProb becomes numerically unstable. For complete- ness, we therefore also include TreeProb and TreeGrad-Shap by setting M + D. The corresponding results are shown in Figure 2. Specially, TreeProb (modified) refers to the variant that adopts the same numerical stabilization trick as Linear TreeShap, as described in Appendix B. Clearly, our TreeGrad-Sha is the only numerically stable algorithm, which further implies that TreeGrad itself numerically stable. The numerical error of TreeProb is already 10-8 when M 35, and increases to 10 when M = 65.
11. Conse-
/nttp:::/gpmmm.org/////
shap/fast. inarr_eeeee__rreeapp....
26

---

Published as a conference paper at ICLR 2026
Table 2: The sizes of the trained tree models and their performance the test datasets. We report
test accuracy for classification tasks and the coefficient of determination R for regression tasks.
Dataset
Decision Tree
Gradient Boosted Trees
FOTP R²/Ace
Depth
#1 #Leaves
#Nodes
R-/Acc
Depth
#Leaves
#Nodes
0,537
20
1,275
2,549
0.568
20
43,103
86,176
GPSP
0,498
10
481
961
0.572
10
11,195
22,365
janmis
0.588
40
11,050
22,099
0.613
40
365,809
731,598
MinibooNE
0.899
20
4,108
8,215
0.894
20
25,924
51,843
philippine
0.709
15
372
743
0.724
15
2,572
5,139
spambase
0,925
15
166
331
0.922
977
1,949
BT
0,901
50
408,461
816,921
0.609
50
2,042,440
4,084,875
superconduct
0.863
10
697
1,393
0.578
10
3,594
7,183
wave_energy
0.525
30
56,814
113,627
0.465
284,265
568,525
10a
Linear TreeShap
Lineer TreeShap (well-condikgnne)
10
TreeGrad-S5
TrerGraü-Shap w/o min
Runtime (s)
TreeProh
TreeGrad-Shie Shap
10->
ThoePob wio min
TreePrih (modified)
TreeGrad
10 8
TreeProb (modifled) wio min
Linear TreeShap
10
10-14
20
30
40 depth (a)
50
60
35
40
45
50
55
60
65
depth D
(b)
Figure 5: (a) The runtime of Linear TreeShap and our TreeGrad-Shae (Algorithm 7) for computing the Shapley value, and of our TreeGrad (Algorithm for computing the Banzhaf value. (b) The numerical errors of different algorithms.
Runtime analysis. We conduct experiments to compare the runtime of Linear TreeShap and our TreeGrad- Shap (Algorithm 7) for computing the Shapley value, and of our TreeGrad (Algorithm 1) for computing the Banzhaf value. Decision trees trained the BT dataset employed, as their sizes are the largest according to Table 2. The result presented Figure 5. Fach curve is averaged 200 instances, with shaded areas representing the corresponding standard deviation. In theory, the time complexities of Linear TreeShap and our TreeGrad-Shail are equally efficient. However, as shown in Figure the numerical error of Linear TreeShap can be up to 10 times larger than that of our Treaprad-Shap. In contrast, the time complexity of our TreeGrad is O(L).
The learning rate crucial for the conver- gence of maximizing the objective in Eq. (6). In particular, each 7 (x(z) can be efficiently eval- uated using Algorithm 10, which is derived from our TreeGrad (Algorithm 1) by removing the traversing-up procedure. Therefore,
How select and in TreeGrad-Ranee
choice of e can be guided by observing the changes in (Fx fx (1N z)) during gradient ascent. Specifically, we select the largest in the candi- date set 0.1,,0.1,005. 0.5, 5, 10,...) the provides consistent convergence in xxx - - 2)), which gives
5. Next, using decision trees, present the performance nations of T and e. The results obtained with gradient ascent are shown in Figures 14-18, whereas those for ADAM presented in Figures 19-23. Our observations
different combi-
(i) the resulting performance improves and converges as T increases: (ii) TreeGrad -anker with ADAM converges carlier than gradient ascent, as performance with ADAM reaches near convergence across all the used datasets at T 10; (iii) lower does not improve performance.
27

---

Published as a conference paper at ICLR 2026
TredGrat-flariie with
TreeGrad-flabket with ADAM
Setadtvvrtion
Dela-Delelion
Bete-joint
1.0
1.0
probabils
predicted probablijss
0.9
predicted probabll
0.0
0.8
0.8
0.7
0.7
0.7
0.6
0..66
10
20
50
100
200
300
20
probabiltty
0.9
prea cted probabiitt
pred cted probablligg
0.8-
0.8
0.7
0.6
0.6
0.6
3.4
0.4
MinibooNE (D) 20)
philippine (D 15)
spambase (D 15)
Figure 6: The trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or lower deletion curve indicates better performance. For our TreeGrad-Ranker we set T 100 and 5. the candidate Beta Shapley value that maximizes the Ins metric for each fx. whereas Beta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric Ins Del. The output of each f(x) is set to be the probability of its predicted class.
selects
GA
ADAM
Bata-insertonn
Buta-Duletion
Beta-joint
0.7
gred icted probability
Iredlcted grobabllits
0.0
0.5-
0.6-
0.4
0.3
0.4
0.2
0.3
0.0
20
50
100
150
200
250
20
0.5
prdicted probabiltyy
predicted probability
predicted probability
0.4
0.3
0.3
0.1
0.0
0.0
0.0
MinibooNE (D 20)
philippine (D 15)
spambase (D 15)
Figure 7: The trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or lower deletion curve indicates better performance. For our TreeGrad-Rankes the candidate Beta Shapley value that maximizes the Ins metric for each fx. whereas Beta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric Ins Del. The output of each f(x) ) is set to be the probability of a randomly sampled non-predicted class.
set T 100 and 5. Beta-Insertion selects
28

---

Published as a conference paper at ICLR 2026
TreeGrad Fanker with GA
TreeGrad Ranker with ADAM
Banahaf
Seta Inserton
Beta Deletion
Bota jeia-jintt
70
1.2
predicted value
prodicted value
80
0.8
0.3
100
0.2
0.4
0.1
0.0
0.0
20
10
50
20
43
60
10
0.0
prodicted value
-0.2
predicted
0.4
20
-2.15
-3.20
-0.9
BT (D) 50)
superconduct (D 10)
wave_energy (D 30)
Figure 8: The trained models decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or lower deletion curve indicates better performance. For our TreeGrad-Ranker the candidate Beta Shapley value that maximizes the Ins metric for each fx. whereas Beta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric Ins Del. The datasets used are regression tasks.
set 7 100 and 5. Beta-Insertion selects
Rankeer
TreeGrod Ranker
0.55
grobatiillss Bly
predicted probabiiltty
0.50
prodicted
20
prebablity
deddeddd probabiitty
0,400
predicted grabability
0.45
0.75
0.40
0.50
0.45
0.35
0.000
8.40
0,250
FOTP (D 20)
GPSP (D 10)
jannis (D 40)
All trained models are gradient boosted trees consisting of 5 individual decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or lower deletion curve indicates better performance. For our BneGrad--aanke we set T = 100 and = 5. Beta-Insertion selects the candidate Beta Shapley value that maximizes the Ins metric for each fx, whereas Beta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric lns Del. The output of each f(x) is set to be the logit of predicted class.
Figure 9:
29

---

Published as a conference paper at ICLR 2026
GA
TraeGrad ADAM
Bata-inertion
Duta Duletoniiion
Buta-joint
0.26
prodcttd probaan
probabiity
0.24
Rredictdd grobabis
2.622
0.225
0.000
0.175
0.16
0.125
0.000
0.16
0.12
0.10
10
20
10
20
0.18
probability
6.13
predicted probabiiity
gredicte probability
0.13
9.11
6.15
6.10
0.11
6.14
6:13
FOTP (D 20)
GPSP (D 10)
jannis (D 40)
Figure 10: All trained models are gradient boosted frees consisting of 5 individual decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher lower deletion curve indicates better performance. For our TreeGrad-Rankee
insertion curve we set = 100 and e = 5. Beta-Insertion selects the candidate Beta Shapley value that maximizes the Tns metric for each fx, whereas Deta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric Ins Del. The output of each fxx is set to be the logit of randomly sampled non-predicted class.
TreeGrad Rankeer with GA
TreeGrid Ranker with ADAM
Banahaf
Sota Insertion
Bota Delction
Bota jaint
0.7b
0.725
probabil
prodicted grobabiliity
200.700
0,700
8.63
Trobabi
0.675
0.650
02.625
0.650
0.600
8.25
0.55
0.575
80.00
0.550
0.578
0.50
200
250
prodicted prbaaiilty
cted probability
predicted prababillty
0.60
0.65
0.65
0.55
0.60
0.55
0.45
0.40
0.50
150
230
250
0.45
10
50
MinibooNE (D) 20)
philippine (D) 15)
spambase (D) 15)
Figure 11: All trained models are gradient boosted trees consisting of individual decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or lower deletion curve indicates better performance. For our SneeGrad-Ranker we set 100 and c 5. Beta-Insertion selects the candidate Beta Shapley value that maximizes the Ins metric for each fx, whereas Beta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric Ins Del. The output each f(x) is set to be the logit of its predicted class.
30

---

Published as a conference paper at ICLR 2026
TreeGrad Fanker with GA
TreeGrod Ranker with ADAM
Banahaf
Interinstrion
Beta Deletion
Bota joint
0.50
predicted prrdoabillg
.66
predicted prebaaiiltty
predicted prob.abling
0.45
0.05
0.50
0.40
0.30
0.35
100
150
200
250
200
10
20
40
50
0.45
prodicted probability.
grobabiiiyy
2.0455
prebability
0.375
0.45
0.425
0.400
0.350
2.40
60.375
0.350
0.500
0.325
20275
0250
0.275
MinibooNE (D 20)
philippine (D 15)
spambase (D 15)
Figure 12: All trained models are gradient boosted trees consisting of 5 individual decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve
lower deletion curve indicates better performance. For our TreeGrad-Ranker we set = 100 and e = 5. Beta-Insertion selects the candidate Beta Shapley value that maximizes the Tns metric for each fx- whereas Deta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric Ins Del. The output of each f(x is set to be the logit of randomly sampled non-predicted class.
TreeGrad Ranker with GA
TreeGrad Ronker with ADAM
Banzhaf
Beta-Insertion
Beta-Delelion
Bets-joint
48
0.20
predicted value
Prodicted valuee
0.44
0.30
50
6.2
388
36
0.00
0.0
34
predicted value
0.0
3.00
22
predicted value
+2.02
-2.04
-0.2
-..00
-3.03
26
20
42 10
BT (D -50)
superconduct (D 10)
wave eneve.energy (D 30)
Figure 13: All trained models are gradient boosted trees consisting of 5 individual decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or lower deletion curve indicates better performance. For our we set 100 and e = 5. Deta-Insertion selects the candidate Beta Shapley value that maximizes the Ins metric for each fx, whereas Beta-Deletion minimizes the Del metric. Beta-Joint selects the candidate that maximizes the joint metric Ins Del. The datasets used are regression tasks.
31

---

Published as a conference paper at ICLR 2026
GT -0
GA [T 50,c
GA c0
GA c00.
prddettd probabiity
predicted probabiity
0.7
prodicted coed probabiltty
0.8
0.7
0.6
0.8
0.0
0.4
0.3
0.3
0.4
predicted probabiito
0.6
predicted probablitt ity
predicted probabi
0.8
0.5
9.3
0.4
43
FOTP (D = 20)
GPSP (D = 10)
jannis (D = 40)
Figure 14: Results of TreeGrad-Ranker with GA. All trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion eurves. A higher insertion curve or a lower deletion curve indicates better performance. The output of each f(x) is set to be the probability its predicted class.
170,00,
GA
GA IT 50,6-5)
CAI7-100,
GA [7- c00,
0.40
arobabllity
probability
pred cted pww.bbaoo abllity
0.5
0.4
0.30
0.4
0.3
0.3
0.20
0.2
0.10
0.0
0.12
rebabiliy
0.18
prodicted probabiitty
0.15
0.125
6.14
0.100
16.12
6.00
0.050
8.04
0.025
0.02
0.000
FOTP (D 20)
GPSP (D 10)
jannis (D 40)
Figure 15: Results of FreeGrad-Ranker with GA. All trained models decision trees. The first row shows insertion curves, while the second presents deletion curves. higher insertion curve lower deletion curve indicates better performance. The output of each f(x) is set to be the probability randomly sampled non-predicted class.
32

---

Published as a conference paper at ICLR 2026
(T,10,0,
GA
1.0
1.0
prodectdd probabiity
predicted probabiitty
pre predicted probabiitty
0.0
0.7
0.7
0.7
10
20
30
40
50
50
100
150
200
250
300
20
-00
50
probabiitg
0.9
predicted probablity ity
predicted probabiigg Ity
0.8-
0.8
0.7
0.0
0.4
0.5
30
100
150
200
MinibooNE (D 20)
philippine (D 15)
spambase (D 15)
Figure 16: Results of TreeGrad- Ranker with GA. All trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion curves. higher insertion curve or lower deletion curve indicates better performance. The output of each f(x) is set to be probability its predicted class.
GA -0,
(0
50.c=5)
GA (M|7==00,e==)
[7
prddecedd prebabiltty.
cred/cted proba abilityy
credicted prebabiiity
0.6
0.5
0.6-
0.4
0.3
0.2
0.1
0.1
10
20
50
50
100
150
200
250
300
20
50
prodicted probabiltty
predicted probab/iity
predicred prolaabiltty ltty
0.3
0.3
0.3
0.2
0.2
0.1
30
0.0
100
150
200
0.0
50
MinibooNE (D 20)
philippine (D 15)
spambase (D 15)
Figure 17: Results of TreeGrad- Ranker with GA. All trained models are decision trees. The first
row shows the insertion curves, while the second presents the deletion curves. higher insertion curve or lower deletion curve indicates better performance. The output of each f(x) is set to be the probability randomly sampled non-predicted class.
33

---

Published as a conference paper at ICLR 2026
1AIT=10,E=5
GA IT 50,6=51
GA
600
GA 17 100, =
0.7
8
1.2
predicted value
prodicted value
80
0.0
10
0.2
0.4
0.1
0.0
0.0
20
10
50
20
43
60
80
0.0
2.00
prodicted value
2.05
-0.4
0.10
20
15
BT (D 50)
superconduct (D 10)
wave_energy (D 30)
Figure 18: Results of BeeGrad-Ranker with GA. All trained models decision frees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve lower deletion curve indicates better performance. The datasets used regression tasks.
ADAM [T=10,==
ADAM 10, c-
ADAM (T,
ADAM IT= 100
ADAM (T- 10-1000--11
0.8
1.0
pred cted grobabilig lny
gred ctee probabiity kvy
0.9
9.6
0.5
0.7
0.5
0.4
0.5
0.4
10
20
20
507
20
0.7
1.0
predicted abbbabylity
0.8
gredicted abilityyy
lcted probability
0.6
0.4
0.0
0.4
0.3
0.2
50
45
FOTP (7) 20)
GPSP (D 10)
jannis (D 40)
Figure 19: Results of TreeGrradRRnnkes with ADAM. All trained models are decision trees. The first
row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or a lower deletion curve indicates better performance. The output of each f(x is set to be the probability of its predicted class.
34

---

Published as a conference paper at ICLR 2026
ADAM
0.6
probmbility
8.35
predicted probabllitg
6.25
0.3
0.2
02
0.3
0.15
0.1
0.0
10
20
20
40
517
20
10
30
0.14
20.12
0.11
predicted probability
0.150
0.10
0.125
0.06
0.10
0.075
0.050
0.04
0.05
0.025
0.000
20
30 25
30
30
30
FOTP (D 20)
GPSP (D 10)
jannis (D 40)
Figure Results of oferrerrrrdRaan with ADAM. All trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or a lower deletion curve indicates better performance. The output of each f(x) set to be the probability of randomly sampled non-predicted class.
ADAM [T=10,,4 x=]]
ADAM [T=10, 5]
ADAM ADAM[TT- [T= -0
ADAM (7 100, 5]
ADAM [7=100, x-]
1.0
predicted probabiltty
0.9
predicted probability
0.9
predicted probability
0.8
0.5
10
20
50
100
150
200
250
20
50
1.0
1.0
1.0
predictd probabiltty
0.9
predicted probability
predicted probability
0.8
0.7
0.6-
0.7
0.5
0.5
10
20
30
40
50
50
100
150
200
250
300
0.3
20
40
50
MinibooNE (D) = 20)
philippine (D = 15)
spambase (D 15)
Figure 21: Results of FrreGrrad-Rankee with ADAM. All trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or a lower deletion curve indicates better performance. The output of each f(x) is set to be the probability of its predicted class.
35

---

Published as a conference paper at ICLR 2026
ADAM (7=1)
ADAM 1T=10, []
ADAM ADAM[TT (T=50,c-5]
ADAM [7+ 100, cm
ADAM [7=100,
20066
gred cted probability.
predicted celd probabollisg (5
probabilis
0.6-
0.5
0.4
0.3
0.2
0.1
0.0
0.0
20
100
150
200
0.5
predicted probabilty.
predicted cedlctedd probabiitty
predicted cted probability
0.4
0.4
0.7
0.3
0.2
0.1
0.1
10
20
0.0
50
100
155
200
250
100
10
20
50
MinibooNE (D = 20)
philippine (D = 15)
spambase (D = 15)
Figure 22: Results of o with ADAM. All trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or a lower deletion curve indicates better performance. The output of each ff f(x) is set to be the probability of randomly sampled non-predicted class.
0.6
predicted value
predicted value
1.0
0.5
80
predcted
0.4
0.6
0.2
35
3.05
30
predieted value
+2.05
predicted
25
--.2
-0.4
-3.00
-0.15
-0.3
20
40
80
20
43
60
100
10
20
30
40
BT (D) = 50)
superconduct (D) = 10)
wave_energy (D 330)
Figure 23: Results of TreeGrad-Ranke with ADAM. All trained models are decision trees. The first row shows the insertion curves, while the second presents the deletion curves. A higher insertion curve or lower deletion curve indicates better performance. The datasets used are regression tasks.
36


Reviews:
[{"review_id": "81U3JsBGii", "reviewer": "Reviewer_SCwW", "summary": "This paper deals with feature ranking of decision trees via probabilistic values, such as the well-known Shapley values. The quality of feature ranking is assessed with the insertion and deletion metrics. Empirically, optimizing these two metrics is closely related to optimizing a particular objective. The authors find that solving this optimization leads to generally unreliable probabilistic values. \n\nTo address it, this paper optimizes the multilinear extension of the objective via gradient ascent called TreeGrad. Then, the averaged gradient is used to estimate the probabilistic values of features. The proposed method is better on insertion and deletion metrics.", "questions": "-", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The effectiveness of proposed method is supported by experimental results. That is both insertion and deletion metrics are significantly better than baselines.\n2. I appreciate the authors’ dedicated efforts on the problem of feature ranking of decision trees.", "weaknesses": "1. The representation should be improved.\n\na) Too many abbreviation in abstract section (TreeGrad/TreeGrad-Ranker/TreeProb/TreeGrad-Shap/Linear TreeShap). Some of them are presented without further elaboration. \n\nb) The logic flow of introduction section is unclear. It arises a question: how reliable are probabilistic values in ranking features? However, it is unclear that whether the probabilistic values itself are unreliable or the optimization method is unreliable. If it were the former, the paper would fall apart.\n\nc) The contribution summary part in introduction section lacks a clear focus. The core contribution is TreeGrad. While TreeProb/TreeGrad-Shap/TreeGrad-Ranker are byproduct contributions. Thus, the author should highlight the development of TreeGrad.\n\nd) The overall representation lacks the description of key ideas and motivations. The current version is hard to follow and it should be restructured.\n\n2. The key contribution of this paper is using the multi-linear extension of objective and develop an algorithm to compute its gradient. However, it is unclear why the multi-linear extension is better. Is it possible to directly compute the gradient of original objective?", "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": "gQARbOiqul", "reviewer": "Reviewer_Kxc7", "summary": "This work focuses on constructing a feature importance ranking for tree models. The authors concentrate on building rankings based on deletion and insertion scores. While such rankings can be constructed naively in theory, this approach is NP-hard. Traditionally, probabilistic values have been used as scores for constructing rankings, including the popular Shapley values and the less popular Banzhaf values. The authors provide a theoretical explanation of why probabilistic values are not appropriate for this task. They then propose their own approach to constructing scores for ranking by formulating a new objective that should yield better ranking scores. They demonstrate how calculating gradients can be utilized in this framework. The authors show that their gradient methods can compute any probabilistic value, including popular Shapley values and improve upon existing methods. They implemented Shapley values calculation as a benchmark and compare their approach to existing methods, demonstrating improvements and explaining issues with previous approaches. The paper concludes with an empirical evaluation of ranging generated with TreeGrad-Ranker.", "questions": "* Regarding the use of gradient optimization and the specific step in Line 23 of Algorithm 2: Do you know if the optimization results typically converge to a global minimum or a local minimum? The landscape of this problem may differ from typical ML problems (like neural networks). Did the authors consider or experiment with alternative optimizers (e.g., SGD or ADAM)? For smaller datasets, is it possible to find the optimal solution to this problem and use it as a comparison baseline?\n\n* Theoretical Constraints (Impossibility Theorem) Is the work subject to the constraints of the relevant Impossibility Theorem from Bilodeau et al. (2024) ? Specifically, does this theorem hold for the values calculated in Algorithm 2, or do the methods presented in the paper mitigate these theoretical problems?\n\n* Scores as Feature Attribution - Did the authors consider using the scores generated by Algorithm 2 for feature attribution? These scores appear to fulfill the most important axioms for feature attribution. Have the authors explored whether they offer improved performance or desirable behavior in this context?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors clearly motivated the problem through Proposition 1, where they stated a type of impossibility theorem for probabilistic values.\nIn Proposition 2, they showed that the use of probabilistic values is equivalent to substituting linear surrogates for f(x), which provides a novel perspective on building rankings with probabilistic values.\n\n* They clearly stated that optimizing the proposed score can be formulated as gradient optimization and showed the exact form of this gradient.\n* The authors demonstrated an interesting connection between gradient calculation and calculating probabilistic values, introducing a new way of computing them (including Shapley values, which is an active and important research topic).\n\n* They identified problems in previous approaches and designed and conducted experiments to showcase these issues.\n\n* They evaluated the new ranking on multiple datasets with a varying number of features.", "weaknesses": "* *Proposition 1* - In this proposition, you assume that U is any function 2^N → R, which is of course true in terms of game theory. However, here we are in a use case where we have a model that takes all features and we calculate expected values (based on the conditional distribution given by the proportion in the tree). It seems that the tree plus the distribution that is also defined by the tree may be less expressive. In Bilodeau et al. (2024), the only requirement for the model class was to have 3 piecewise linear regions and non-zero probability outside of a neighborhood (though this was for marginal SHAP). Did you think about stating this theorem in the context of tree models?\n\n* Do I understand correctly that the proposed algorithm applies only to single decision trees? If so, this limits the scope of the paper, as gradient boosted trees are widely adopted and used very often. Single trees are more interpretable, but that is precisely what makes a feature ranking method for forests needed. Can it be extended to models containing multiple trees?\n\n* In the empirical section (Section 6), the hyperparameters of the model are not described. Only the implementation used is described. However, there is no information about the hyperparameter selection process - I think it would be important to ensure that these trees are reasonably well-tuned for the datasets. Also, the size of the trained models was not reported. (See also questions).\n\n* The authors evaluated their method using the insertion and deletion scores. There are also other methods for benchmarking the quality of rankings, e.g., Agarwal, Chirag, et al. \"OpenXAI: Towards a transparent evaluation of model explanations.\" The theoretical justification aligns with the fact that it works better for these scores; however, what about other metrics?", "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": "2ef00cWpk3", "reviewer": "Reviewer_WPUD", "summary": "This paper aims to address the reliability issue of probabilistic values of Shapley values and Banzhaf values. The authors proposed TreeGrad-Ranker, which leverages averaged gradients of the multilinear extension as a remedy for decision tree models. The method extends Linear TreeSHAP and achieves fast O(L) time calculation. It also outperforms existing approaches in terms of insertion and deletion metrics on nine empirical dataset.", "questions": "How to set T and $\\epsilon$ in practice?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper is rigorous in its definitions and provides solid theoretical justifications for propose work.\n2. The paper identifies the pitfalls of using probabilistic values and proposed an alternative optimization scheme.\n3. TreeGrad-Ranker empirically outperform Shapley values, Banzhaf values, Beta-Shapley in terms of insertion and deletion metrics on nine datasets.", "weaknesses": "1. The abstract introduces several newly proposed names (TreeGrad, TreeGrad-Ranker, TreeProb and TreeGrad-Shap), which makes it difficult to identify the central contribution. It would be clearer and more engaging if the abstract can focus more on the main problem the paper aims to solve.\n2. It’s very difficult to distinguish the performance of different methods in Figure 3 based on solely color. I recommend the authors use additional visual cues, such as distinct shapes, line types for different groups of variables, or just numerical values to demonstrate the proposed methods.\n3. Due to the lack of linearity for TreeGrad-Ranker, generalization to popular ensemble trees methods like random forests and XGBoost is non-trivial, which limits the practical usage of the method.\n4. Section 5 of the paper discusses the numerical instability of Vandermonde matrices in Linear TreeSHAP and uses the complex root of unity but does not cite prior work. In particular, the ill-conditioning problem of Vandermonde matrices and a similar solution for Linear TreeSHAP was previously mentioned in [1].\n\n[1] Jiang, Z., Zhang, M., & Zhang, D. (2025). Fast Calculation of Feature Contributions in Boosting Trees. Proceedings of the 41st Conference on Uncertainty in Artificial Intelligence (UAI).", "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": "ie2Hu3Mc5Q", "reviewer": "Reviewer_vun4", "summary": "The authors proposed TreeGrad, a way of computing feature importance via solving the multilinear extension of the joint optimization problem. They showed its theoretical guarantees and empirical effectiveness, comparing against other insertion / deletion based methods.\nThe authors also presented an improved algorithm for computing probabilistic values in decision trees (called TreeProb), and a more numerically stable variant of TreeShap (they call it TreeGrad-Shap).", "questions": "Minor suggestions:\n1. Line 82: ... decision trees serves as the backbone -> ... decision trees serve as the backbone\n2. The algorithm names are confusing, TreeGrad, TreeProb, TreeGrad-Shap, TreeGrad-Ranker \n3. Main figure 4 could improve its look, the contrast is not clear when it comes the the paper's method / baselines, especially in the bottom parts.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical analysis is thorough, especially the arguments in section 3, optimizing the joint makes a lot of sense\n2. Clear explanation of the algorithms, algorithms mentioned are listed clearly in the paper\n3. Strong experimental results, empirical evidence supports the authors' claims of their algorithms' effectiveness", "weaknesses": "1. Lack of a empirical run-time analysis: the authors claim a O(L) gradient-based method, when comparing with previous approaches with O(LD) complexity. However it is unclear how many gradient steps are enough (10? 100? from figure 3). I think it will be more beneficial to include an empirical run-time analysis.\n2. Does randomness affect the method? Since it's gradient based, does different random seed affect the model explanation? I will suggest some analysis around that as well.\n3. Also evaluation dataset seems to be of small-scale (9-datasets)", "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)