# From Decision Trees to Boolean Logic: A Fast and Unified SHAP Algorithm

arXiv: https://arxiv.org/abs/2511.09376 · HTML: https://mlsanity.com/paper/2511.09376/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 58 references that are in the map.
- First posted on arXiv 12 Nov 2025.

## Builds on (most cited first, 14 of 14)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [Consistent Individualized Feature Attribution for Tree Ensembles](https://mlsanity.com/paper/1802.03888/) (2018)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [shapiq: Shapley Interactions for Machine Learning](https://mlsanity.com/paper/2410.01649/) (2024)
- [CatBoost: unbiased boosting with categorical features](https://mlsanity.com/paper/1706.09516/) (2017)
- [Fast TreeSHAP: Accelerating SHAP Value Computation for Trees](https://mlsanity.com/paper/2109.09847/) (2021)
- [The Shapley Value of Tuples in Query Answering](https://mlsanity.com/paper/1904.08679/) (2019)
- [GPUTreeShap: Massively Parallel Exact Calculation of SHAP Scores for Tree Ensembles](https://mlsanity.com/paper/2010.13972/) (2020)
- [SHAP values via sparse Fourier representation](https://mlsanity.com/paper/2410.06300/) (2024)
- [Understanding Interventional TreeSHAP : How and Why it Works](https://mlsanity.com/paper/2209.15123/) (2022)

## Built on by (most cited first, 3 of 3)

- [Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions](https://mlsanity.com/paper/2605.04497/) (2026)
- [ConfoundingSHAP: Quantifying confounding strength in causal inference](https://mlsanity.com/paper/2605.10533/) (2026)
- [Woodelf++: A Fast and Unified Partial Dependence Plot Algorithm for Decision Tree Ensembles](https://mlsanity.com/paper/2605.14578/) (2026)

## Abstract (arXiv)

SHapley Additive exPlanations (SHAP) is a key tool for interpreting decision tree ensembles by assigning contribution values to features. It is widely used in finance, advertising, medicine, and other domains. Two main approaches to SHAP calculation exist: Path-Dependent SHAP, which leverages the tree structure for efficiency, and Background SHAP, which uses a background dataset to estimate feature distributions. We introduce WOODELF, a SHAP algorithm that integrates decision trees, game theory, and Boolean logic into a unified framework. For each consumer, WOODELF constructs a pseudo-Boolean formula that captures their feature values, the structure of the decision tree ensemble, and the entire background dataset. It then leverages this representation to compute Background SHAP in linear time. WOODELF can also compute Path-Dependent SHAP, Shapley interaction values, Banzhaf values, and Banzhaf interaction values. WOODELF is designed to run efficiently on CPU and GPU hardware alike. Available via the WOODELF Python package, it is implemented using NumPy, SciPy, and CuPy without relying on custom C++ or CUDA code. This design enables fast performance and seamless integration into existing frameworks, supporting large-scale computation of SHAP and other game-theoretic values in practice. For example, on a dataset with 3,000,000 rows, 5,000,000 background samples, and 127 features, WOODELF computed all Background Shapley values in 162 seconds on CPU and 16 seconds on GPU - compared to 44 minutes required by the best method on any hardware platform, representing 16x and 165x speedups, respectively.