A PSA on Shapley Values
13 min read
Lundberg & Lee introduced Shapley values to machine learning as SHAP [LL, NeurIPS ’17], and the years of arguing that followed conflate two objects: the game, a modeling choice, and the Shapley value, a fixed rule applied to that choice. I have spent the last few years co-writing Shapley estimation papers, and this is the announcement I wish I had read first. Keep the two apart, and the debates about what SHAP “should” report turn into debates about the game, where they belong.
The practical half of the announcement: when in doubt, fit gradient boosted trees to your coalition samples and run TreeSHAP.
The Value and the Game
Only one of the two objects is ever contested, so start with the other. A game on \(d\) players \([d] = \{1, \dots, d\}\) is a set function \(f : 2^{[d]} \to \mathbb{R}\) assigning a value to every coalition \(S \subseteq [d]\), whose complement is \(S^c = [d] \setminus S\). To split the value fairly, seat the players in a uniformly random order and pay each one the jump in value when they sit down, their marginal contribution to the players already seated. With two players there are only two orders, so we can check the scheme by hand. Take the game with \(f(\emptyset) = 0\), \(f(\{1\}) = 1\), \(f(\{2\}) = 0\), and \(f(\{1, 2\}) = 2\). Player 1 is paid \(1 - 0 = 1\) when seated first and \(2 - 0 = 2\) when seated second; player 2 is paid \(0\) when first and \(2 - 1 = 1\) when second. Averaging over the two orders gives each player’s expected payment:
\[ \tfrac{1}{2}(1) + \tfrac{1}{2}(2) = \tfrac{3}{2} \qquad\text{and}\qquad \tfrac{1}{2}(0) + \tfrac{1}{2}(1) = \tfrac{1}{2}. \]
Player 1 collects more than it earns alone because it also completes the pair’s synergy, and the two payments sum to \(f(\{1, 2\}) - f(\emptyset) = 2\): the scheme hands out exactly the value created. These expected payments are the Shapley values. For a general game, the Shapley value of player \(i\) is the same expected payment, a weighted average of \(i\)’s marginal contributions:
\[ \phi_i(f) = \sum_{S \subseteq [d] \setminus \{i\}} \frac{|S|!\,(d - |S| - 1)!}{d!}\, \big( f(S \cup \{i\}) - f(S) \big), \]
where the weight is the probability that a uniformly random ordering of the players seats exactly the coalition \(S\) before player \(i\). It is the unique rule satisfying a short list of fairness axioms: efficiency, that the values sum to \(f([d]) - f(\emptyset)\) as they did in the two-player check; equal treatment of interchangeable players; nothing for a player who never changes the value; and consistency across games. The one property we lean on throughout is linearity, that \(\phi_i\) acts linearly on the game:
\[ \phi_i(\alpha f + \beta f') = \alpha\, \phi_i(f) + \beta\, \phi_i(f') \qquad \text{for any games } f, f' \text{ and scalars } \alpha, \beta. \]
There is nothing to prove: the definition is a fixed linear combination of the \(2^d\) values of \(f\), so linearity holds term by term.
Notice what the definition leaves open: it says nothing about what the game is. Choosing \(f\) is where all the modeling happens.
The Game Is a Modeling Choice
Take the most common application, feature attribution. A trained model \(h\) maps a feature vector \(\mathbf{x} \in \mathbb{R}^d\) to a prediction, and we want to explain \(h(\mathbf{x})\) at one particular input. The players are the features, and we would like \(f(S)\) to mean “the prediction when only the features in \(S\) are revealed”. But \(h\) has no notion of a missing feature, so we must put something in the hidden slots, and every convention is a different game:
\[ f_{\text{base}}(S) = h(\mathbf{x}_S; \mathbf{b}_{S^c}), \qquad f_{\text{marg}}(S) = \mathbb{E}\big[ h(\mathbf{x}_S; \mathbf{X}_{S^c}) \big], \qquad f_{\text{cond}}(S) = \mathbb{E}\big[ h(\mathbf{X}) \mid \mathbf{X}_S = \mathbf{x}_S \big]. \]
Here \(h(\mathbf{x}_S; \cdot)\) pins the features in \(S\) to their observed values and fills the rest three ways. The baseline game substitutes a fixed reference input \(\mathbf{b} \in \mathbb{R}^d\). The marginal game averages the model over a random feature vector \(\mathbf{X} \in \mathbb{R}^d\) drawn from the data distribution, ignoring the correlation between hidden and revealed features. The conditional game averages over the hidden features conditioned on what was revealed.
To see how much the choice matters, take three fair-coin features in which \(x_2\) is a duplicate of \(x_1\) (the two always agree) while \(x_3\) is independent. The model \(h(\mathbf{x}) = x_1 + x_3\) never touches \(x_2\), the input is \(\mathbf{x} = (1, 1, 1)\), and the reference is \(\mathbf{b} = (0, 0, 0)\). Write \(\phi\) for the vector of the three Shapley values. Under baseline masking a hidden feature is a zero, so the game scores one point for revealing \(x_1\) and one for revealing \(x_3\). That game is additive, and (as the next section verifies) its Shapley values are the per-feature scores \(\phi = (1, 0, 1)\). The marginal game replaces each hidden feature by a fresh coin with mean \(\tfrac{1}{2}\), so every contribution halves: \(\phi = (\tfrac{1}{2}, 0, \tfrac{1}{2})\). The two totals differ because efficiency anchors each game at a different baseline, the reference input for one and the mean prediction for the other:
\[ h(\mathbf{x}) - h(\mathbf{b}) = 2 \qquad\text{versus}\qquad h(\mathbf{x}) - \mathbb{E}[h(\mathbf{X})] = 1. \]
The conditional game is the interesting one. Revealing \(x_2 = 1\) reveals \(x_1 = 1\), so the untouched duplicate has genuine marginal contributions and earns genuine credit: \(\phi = (\tfrac{1}{4}, \tfrac{1}{4}, \tfrac{1}{2})\). Every marginal contribution of \(x_3\) is exactly \(\tfrac{1}{2}\) (do you see why?), which gives \(\phi_3 = \tfrac{1}{2}\) directly, and symmetry plus efficiency split the rest evenly between the twins.
In the plot, all three answers are correct: they answer three different questions. Once translated, most “SHAP is wrong” arguments are arguments about which \(f\) matches the question being asked. And feature attribution is only one place games come from: in data valuation, \(f(S)\) is the test performance of a model retrained on the training subset \(S\); in federated learning, the performance of the clients in \(S\) together. Different applications, same fixed rule, and the same computational problem.
Games with Free Shapley Values
The definition of \(\phi_i(f)\) touches every one of the \(2^d\) coalitions, and for a generic black-box game there is no shortcut (\(2^{30}\) is already a billion evaluations, each a model call or an entire retraining). The way out is an asymmetry: some classes of games have closed-form Shapley values.
Additive games. Suppose the surrogate \(\hat{f}\) is affine, a constant plus a per-player score:
\[ \hat{f}(S) = b + \sum_{i \in S} c_i, \]
with constant \(b \in \mathbb{R}\) and per-player scores \(c_i \in \mathbb{R}\). By linearity we handle each term separately. The constant game \(S \mapsto b\) has no marginal contributions at all, so it contributes nothing to any \(\phi_i\). The singleton game \(S \mapsto c_i\, \mathbf{1}[i \in S]\), where \(\mathbf{1}[\cdot]\) is one when its argument holds and zero otherwise, hands \(c_i\) to player \(i\) in every ordering and nothing to anyone else. Summing the per-term values leaves each player with its own score:
\[ \phi_i(\hat{f}) = c_i. \]
Sparse polynomials, Möbius basis. The affine class carries no interactions, and the next class up does. Encode a coalition by its indicator vector \(\mathbf{z} \in \{0, 1\}^d\), with \(z_i = \mathbf{1}[i \in S]\). The monomial on a subset \(T \subseteq [d]\) is then the game worth one exactly when all of \(T\) shows up:
\[ \prod_{i \in T} z_i = \mathbf{1}[T \subseteq S]. \]
These monomials are the Möbius basis (also called the interaction basis), and the coefficient \(\beta_T\) on \(\mathbf{1}[T \subseteq S]\) is the pure interaction among the players of \(T\). Read the Shapley value of a single monomial straight off the axioms. Players outside \(T\) never change its value, so they are null; the players inside \(T\) are interchangeable; and for a nonempty \(T\) the total to split is \(\mathbf{1}[T \subseteq [d]] - \mathbf{1}[T \subseteq \emptyset] = 1\). Equal treatment splits that total evenly across the \(|T|\) members:
\[ \phi_i\big(\mathbf{1}[T \subseteq \cdot]\big) = \begin{cases} 1/|T| & i \in T, \\ 0 & \text{otherwise}. \end{cases} \]
By linearity, the Möbius-sparse polynomial \(\hat{f}(S) = \sum_{T} \beta_T\, \mathbf{1}[T \subseteq S]\) sums these single-monomial values:
\[ \phi_i(\hat{f}) = \sum_{T \ni i} \frac{\beta_T}{|T|}. \]
A single pass over the nonzero coefficients computes every \(\phi_i\).
Sparse polynomials, Fourier basis. The second expansion trades presence for sign. Write the parity of \(T\) on a coalition as
\[ \chi_T(S) = (-1)^{|S \cap T|}, \]
worth \(+1\) when \(T\) meets \(S\) in an even number of players and \(-1\) when odd; these are the Fourier basis, the Walsh–Hadamard characters. A player outside \(T\) never flips the parity, so it is null, the players inside \(T\) are interchangeable, and by efficiency they share the change from the empty coalition to the full one:
\[ \chi_T([d]) - \chi_T(\emptyset) = (-1)^{|T|} - 1. \]
That total vanishes when \(|T|\) is even and equals \(-2\) when \(|T|\) is odd, so equal treatment splits it evenly across the \(|T|\) members:
\[ \phi_i(\chi_T) = \begin{cases} -\,2/|T| & i \in T \text{ and } |T| \text{ odd}, \\ 0 & \text{otherwise}. \end{cases} \]
An even-order character is therefore invisible to the Shapley value, and that blindness is the mechanism behind the even–odd decomposition.
Trees. For a decision forest, Lundberg, Erion, Chen, DeGrave, Prutkin, Nair, Katz, Himmelfarb, Bansal & Lee [LE+, NMI ’20] showed that exact Shapley values can be computed in \(O(t \ell d^2)\) time for \(t\) trees with at most \(\ell\) leaves each and depth at most \(d\), rather than the naive \(O(t \ell\, 2^d)\). That algorithm is TreeSHAP, and it makes the exact Shapley values of a gradient boosted forest a subsecond operation.
This asymmetry drives every method that follows: the values are intractable for a black box, essentially free for an affine function, a sparse polynomial, or a boosted forest.
The Template
The asymmetry is not yet useful: the game you care about is the black box, not the affine function. So evaluate the game you have, and fit a surrogate whose Shapley values you can compute in closed form. Sample \(m\) coalitions \(S_1, \dots, S_m\), where \(m\) is the evaluation budget; evaluate \(f(S_1), \dots, f(S_m)\), the expensive part; fit a surrogate \(\hat{f}\) from a class with free Shapley values to the pairs \((S_j, f(S_j))\); return \(\phi_i(\hat{f})\), computed exactly. The four boxes in the figure are the whole method.
How much accuracy does the read-off give up? None beyond the fit, and linearity is the reason. Apply linearity to the difference of the true game and the surrogate:
\[ \phi_i(f) - \phi_i(\hat{f}) = \phi_i(f - \hat{f}). \]
The pipeline’s entire error is therefore the Shapley value of the residual game \(f - \hat{f}\). Choose a class rich enough that the residual is small and you are done. If you insist on unbiasedness, spend part of the budget on a cheap unbiased Monte Carlo estimate of \(\phi_i(f - \hat{f})\) and add it back. That is the adjustment column in the taxonomy below.
The template predates its own name. KernelSHAP, introduced by Lundberg & Lee [LL, NeurIPS ’17] alongside SHAP itself, fits an affine surrogate by weighted least squares and reports the fitted coefficients. Its weight on a coalition depends only on the coalition’s size \(\ell\), for \(0 < \ell < d\):
\[ w_\ell = \frac{1}{\ell\,(d - \ell)\,\binom{d}{\ell}}. \]
The weight grows without bound as \(\ell\) approaches \(0\) or \(d\), so the fit is pinned hardest on the smallest and largest coalitions, where the Shapley weights put their own mass. For a general game the affine class looks far too weak. Charnes, Golany, Keane & Rousseau [CGKR, ’88] showed otherwise: with this weighting, the weighted regression, solved over all \(2^d\) coalitions with the coefficients constrained to sum to \(f([d]) - f(\emptyset)\), has the Shapley values as its exact solution, for every game, however far from affine. Sampling coalitions merely approximates that full regression, so the affine misfit shows up as variance that vanishes as the sample fills in all \(2^d\) rows.
And here is the TL;DR instantiation: fit gradient boosted trees to the pairs \((S_j, f(S_j))\) and hand the forest to TreeSHAP. (Ask TreeSHAP to explain the all-ones indicator against the all-zeros baseline, so the game it masks with is exactly \(S \mapsto \hat{f}(S)\).) No custom kernel weights, no bespoke solver, no interaction bookkeeping: XGBoost plus the shap package, end to end. Boosted trees handle set functions with strong interactions well, though no theorem says they will fit yours: the affine surrogate above is the one with a guarantee attached, and this recommendation is empirical. Tree MSR, the same fit plus an unbiased residual correction, is the version with numbers attached: its average error over eight datasets at a budget of \(m = 40d\) is \(6.5\times\) lower than Permutation SHAP and \(2.6\times\) lower than LeverageSHAP [WLM, NeurIPS ’25]. That margin needs budget: with few samples the forest has not fit yet, and the estimator trails KernelSHAP.
The Taxonomy
The template says what every method has in common and nothing about how they differ. Essentially every modern method reads as a row of this table.
| Method | Surrogate | Sampling | Adjustment | Citation |
|---|---|---|---|---|
| KernelSHAP | Affine | Shapley kernel, i.i.d. | None | [LL, NeurIPS ’17] |
| LeverageSHAP | Affine | Leverage scores: uniform size, then uniform set, paired | None | [MW, ICLR ’25] |
| PolySHAP | Polynomial with chosen interaction terms | Kernel or leverage weights, paired | None | [FWM, ICLR ’26] |
| OddSHAP | Odd polynomial, terms nominated by a boosted-tree proxy | Paired, complement-symmetric weights | None | [FBKRW, ICML ’26] |
| RegressionMSR | Anything with free Shapley values; boosted trees in practice | Sample reuse: every evaluation updates every player | Unbiased Monte Carlo estimate of the residual game | [WLM, NeurIPS ’25] |
| ProxySPEX | Boosted trees, read out as a sparse Fourier polynomial | Uniformly random coalitions | None | [BAKEYR, ’25] |
| Adalina | A single constant, tuned online | Variance-optimal sizes, every sample reused | The constant, subtracted as a control variate | [LYL, ICML ’26] |
A few rows deserve a gloss. LeverageSHAP samples coalitions in proportion to their leverage scores in the kernel regression. My advisor Chris Musco and I prove that \(O(d \log d + d/\varepsilon)\) expected evaluations bring the fitted coefficients within a factor \(1 + \varepsilon\) of the optimal objective value of the full \(2^d\)-row regression, with constant probability. The bound is on that objective value, and relative error on the \(\phi_i(f)\) themselves follows at the cost of a factor measuring how much of the game the affine class misses. PolySHAP and OddSHAP lean on paired sampling, every coalition drawn with its complement, and OddSHAP fits only the odd interactions, the half the Shapley value can see. Tree MSR above is the boosted-tree instance of RegressionMSR. ProxySPEX runs the TL;DR pipeline at LLM scale, over uniform masks on hundreds of input features, then extracts the fitted forest’s largest Fourier coefficients and reads the Shapley values off the parity formula above. SPEX, of Kang, Butler, Agarwal, Erginbas, Pedarsani, Ramchandran & Yu [KB+, ICML ’25], recovers that same sparse Fourier expansion directly with a sparse Fourier transform. And Adalina strips the template to its minimum: a constant game has Shapley values all zero, so the read-off contributes nothing and the constant works as a control variate.
Read as a table, the whole design space is legible: pick a surrogate class expressive enough for your game and a sampling scheme you can analyze. The Shapley extraction at the end is never the hard part; the game, as always, is the modeling choice. And when in doubt: gradient boosted trees, then TreeSHAP.