TreeSHAP

Shapley values give a principled way to split credit for a prediction among its input features, but computing them exactly, in general, requires averaging a feature's marginal contribution across every possible ordering of all the other features — a computation that grows exponentially with the number of features and is intractable beyond a handful of them. KernelSHAP handles this for any model by sampling feature subsets and fitting a weighted linear approximation, trading exactness for tractability. TreeSHAP does something better, but only for tree-based models: it computes the exact Shapley values in time that grows polynomially — proportional to the number of trees, times leaves, times tree depth — rather than exponentially, by exploiting the fact that a tree ensemble's structure already encodes exactly how each feature routes a prediction.

The trick is that a tree already tells you, path by path, precisely which feature caused a decision to go left versus right at every split. TreeSHAP walks each tree once, tracking — for every possible subset of features "known" so far — what fraction of training data would have reached each node, and combines these path-based statistics using a clever bookkeeping scheme so that the exact Shapley value falls out without ever having to enumerate subsets explicitly. The exactness matters: KernelSHAP's sampled approximation can vary slightly between runs and needs enough samples to converge; TreeSHAP gives the same, exact answer every time, and does it fast enough to run on every row of a production dataset routinely.

Worked example

Consider a tiny single tree used to flag suspicious trades, splitting first on order size (>10,000 shares vs not) and then, within the large-order branch, on time-to-close (last 5 minutes vs not). Say the tree's leaves predict a 5% suspicious-flag probability at the root-level baseline, 8% for large orders regardless of timing, and 22% for large orders placed in the last 5 minutes. For one specific 15,000-share order placed 2 minutes before close, TreeSHAP computes each feature's contribution by comparing predictions along the path actually taken against what "not knowing" that feature would give, averaged with the correct combinatorial weights across the two features. Order size's contribution comes out to about $8\% - 5\% = 3$ percentage points (the jump from the baseline to knowing only order size), and time-to-close contributes the remaining $22\% - 8\% = 14$ points (the jump from knowing order size to knowing both) — and because there are only two features here, TreeSHAP's exact path-based computation and a manual conditional-probability calculation agree exactly, which is the guarantee TreeSHAP provides in general, just computed far more efficiently for ensembles with hundreds of trees.

What this means in practice

TreeSHAP is why SHAP became the default attribution method for gradient-boosted trees and random forests specifically — it's fast enough to compute exact, consistent attributions for every prediction a production model makes, not just a sample, which matters when explanations feed into monitoring dashboards, trade-surveillance systems, or compliance reports that need to run at scale. Its exactness and speed are specific to tree ensembles; switching to a neural network means falling back to KernelSHAP, integrated gradients, or another method built for that model class.