# Efficient and Accurate Explanation Estimation with Distribution Compression

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 71 references that are in the map.
- First posted on arXiv 26 Jun 2024.

## Builds on (most cited first, 30 of 46)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [RISE: Randomized Input Sampling for Explanation of Black-box Models](https://mlsanity.com/paper/1806.07421/) (2018)
- [Captum: A unified and generic model interpretability library for PyTorch](https://mlsanity.com/paper/2009.07896/) (2020)
- [Dataset Condensation with Gradient Matching](https://mlsanity.com/paper/2006.05929/) (2020)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (2018)
- [Interpretable Counterfactual Explanations Guided by Prototypes](https://mlsanity.com/paper/1907.02584/) (2019)
- [Explaining by Removing: A Unified Framework for Model Explanation](https://mlsanity.com/paper/2011.14878/) (2020)
- [Visualizing the Effects of Predictor Variables in Black Box Supervised Learning Models](https://mlsanity.com/paper/1612.08468/) (2016)
- [Explaining individual predictions when features are dependent: More accurate approximations to Shapley values](https://mlsanity.com/paper/1903.10464/) (2019)
- [Dataset Condensation via Efficient Synthetic-Data Parameterization](https://mlsanity.com/paper/2205.14959/) (2022)
- [OpenML Benchmarking Suites](https://mlsanity.com/paper/1708.03731/) (2017)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [OpenXAI: Towards a Transparent Evaluation of Model Explanations](https://mlsanity.com/paper/2206.11104/) (2022)
- [Reliable Post hoc Explanations: Modeling Uncertainty in Explainability](https://mlsanity.com/paper/2008.05030/) (2020)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [The Out-of-Distribution Problem in Explainability and Search Methods for Feature Importance Explanations](https://mlsanity.com/paper/2106.00786/) (2021)
- [Towards Human-centered Explainable AI: A Survey of User Studies for Model Explanations](https://mlsanity.com/paper/2210.11584/) (2022)
- [A Rigorous Study of Integrated Gradients Method and Extensions to Internal Neuron Attributions](https://mlsanity.com/paper/2202.11912/) (2022)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Explaining Hyperparameter Optimization via Partial Dependence Plots](https://mlsanity.com/paper/2111.04820/) (2021)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles](https://mlsanity.com/paper/2401.12069/) (2024)
- [Extracting Class Activation Maps from Non-Discriminative Features as well](https://mlsanity.com/paper/2303.10334/) (2023)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)

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

- [Interpreting CLIP with Hierarchical Sparse Autoencoders](https://mlsanity.com/paper/2502.20578/) (2025)
- [Unifying Feature-Based Explanations with Functional ANOVA and Cooperative Game Theory](https://mlsanity.com/paper/2412.17152/) (2024)
- [Explanation Multiplicity in SHAP: Characterization and Assessment](https://mlsanity.com/paper/2601.12654/) (2026)
- [Birds look like cars: Adversarial analysis of intrinsically interpretable deep learning](https://mlsanity.com/paper/2503.08636/) (2025)

## Abstract (arXiv)

We discover a theoretical connection between explanation estimation and distribution compression that significantly improves the approximation of feature attributions, importance, and effects. While the exact computation of various machine learning explanations requires numerous model inferences and becomes impractical, the computational cost of approximation increases with an ever-increasing size of data and model parameters. We show that the standard i.i.d. sampling used in a broad spectrum of algorithms for post-hoc explanation leads to an approximation error worthy of improvement. To this end, we introduce Compress Then Explain (CTE), a new paradigm of sample-efficient explainability. It relies on distribution compression through kernel thinning to obtain a data sample that best approximates its marginal distribution. CTE significantly improves the accuracy and stability of explanation estimation with negligible computational overhead. It often achieves an on-par explanation approximation error 2-3x faster by using fewer samples, i.e. requiring 2-3x fewer model evaluations. CTE is a simple, yet powerful, plug-in for any explanation method that now relies on i.i.d. sampling.