# Optimal Counterfactual Explanations in Tree Ensembles

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 11 Jun 2021.

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

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [Algorithmic Recourse: from Counterfactual Explanations to Interventions](https://mlsanity.com/paper/2002.06278/) (2020)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Preserving Causal Constraints in Counterfactual Explanations for Machine Learning Classifiers](https://mlsanity.com/paper/1912.03277/) (2019)
- [A survey of algorithmic recourse: definitions, formulations, solutions, and prospects](https://mlsanity.com/paper/2010.04050/) (2020)
- [The Hidden Assumptions Behind Counterfactual Explanations and Principal Reasons](https://mlsanity.com/paper/1912.04930/) (2019)
- [Efficient Search for Diverse Coherent Explanations](https://mlsanity.com/paper/1901.04909/) (2019)
- [Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking](https://mlsanity.com/paper/1706.06691/) (2017)
- [FOCUS: Flexible Optimizable Counterfactual Explanations for Tree Ensembles](https://mlsanity.com/paper/1911.12199/) (2019)
- [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020)
- [Convex Density Constraints for Computing Plausible Counterfactual Explanations](https://mlsanity.com/paper/2002.04862/) (2020)
- [BRPO: Batch Residual Policy Optimization](https://mlsanity.com/paper/2002.05522/) (2020)
- [Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization](https://mlsanity.com/paper/2012.11782/) (2020)

## Built on by (most cited first, 30 of 36)

- [GLOBE-CE: A Translation-Based Approach for Global Counterfactual Explanations](https://mlsanity.com/paper/2305.17021/) (2023)
- [Computing Abductive Explanations for Boosted Trees](https://mlsanity.com/paper/2209.07740/) (2022)
- [Finding Regions of Counterfactual Explanations via Robust Optimization](https://mlsanity.com/paper/2301.11113/) (2023)
- [Efficient XAI Techniques: A Taxonomic Survey](https://mlsanity.com/paper/2302.03225/) (2023)
- [Achieving Diversity in Counterfactual Explanations: a Review and Discussion](https://mlsanity.com/paper/2305.05840/) (2023)
- [Trained Random Forests Completely Reveal your Dataset](https://mlsanity.com/paper/2402.19232/) (2024)
- [Global Counterfactual Explanations: Investigations, Implementations and Improvements](https://mlsanity.com/paper/2204.06917/) (2022)
- [Generating collective counterfactual explanations in score-based classification via mathematical optimization](https://mlsanity.com/paper/2310.12822/) (2023)
- [The Risks of Recourse in Binary Classification](https://mlsanity.com/paper/2306.00497/) (2023)
- [On the Safety of Interpretable Machine Learning: A Maximum Deviation Approach](https://mlsanity.com/paper/2211.01498/) (2022)
- [Explainable Data-Driven Optimization: From Context to Decision and Back Again](https://mlsanity.com/paper/2301.10074/) (2023)
- [Learning Decision Trees and Forests with Algorithmic Recourse](https://mlsanity.com/paper/2406.01098/) (2024)
- [Generating Likely Counterfactuals Using Sum-Product Networks](https://mlsanity.com/paper/2401.14086/) (2024)
- [Counterfactual Explanations for Model Ensembles Using Entropic Risk Measures](https://mlsanity.com/paper/2503.07934/) (2025)
- [Very fast, approximate counterfactual explanations for decision forests](https://mlsanity.com/paper/2303.02883/) (2023)
- [Prediction without Preclusion: Recourse Verification with Reachable Sets](https://mlsanity.com/paper/2308.12820/) (2023)
- [Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles](https://mlsanity.com/paper/2408.16167/) (2024)
- [From Counterfactuals to Trees: Competitive Analysis of Model Extraction Attacks](https://mlsanity.com/paper/2502.05325/) (2025)
- [Realistic Counterfactual Explanations with Learned Relations](https://mlsanity.com/paper/2202.07356/) (2022)
- [Don't Explain Noise: Robust Counterfactuals for Randomized Ensembles](https://mlsanity.com/paper/2205.14116/) (2022)
- [Support Vector Machines with the Hard-Margin Loss: Optimal Training via Combinatorial Benders' Cuts](https://mlsanity.com/paper/2207.07690/) (2022)
- [Algorithmic Recourse with Missing Values](https://mlsanity.com/paper/2304.14606/) (2023)
- [One-for-many Counterfactual Explanations by Column Generation](https://mlsanity.com/paper/2402.09473/) (2024)
- [Counterfactual Maps: What They Are and How to Find Them](https://mlsanity.com/paper/2602.09128/) (2026)
- [Supervised Feature Compression based on Counterfactual Analysis](https://mlsanity.com/paper/2211.09894/) (2022)
- [PACE: Prune-And-Compress Ensemble Models](https://mlsanity.com/paper/2605.06278/) (2026)
- [Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms](https://mlsanity.com/paper/2605.06561/) (2026)
- [Local and Regional Counterfactual Rules: Summarized and Robust Recourses](https://mlsanity.com/paper/2209.14568/) (2022)
- [Decomposing Counterfactual Explanations for Consequential Decision Making](https://mlsanity.com/paper/2211.02151/) (2022)
- [Inverse classification with logistic and softmax classifiers: efficient optimization](https://mlsanity.com/paper/2309.08945/) (2023)

## Abstract (arXiv)

Counterfactual explanations are usually generated through heuristics that are sensitive to the search's initial conditions. The absence of guarantees of performance and robustness hinders trustworthiness. In this paper, we take a disciplined approach towards counterfactual explanations for tree ensembles. We advocate for a model-based search aiming at "optimal" explanations and propose efficient mixed-integer programming approaches. We show that isolation forests can be modeled within our framework to focus the search on plausible explanations with a low outlier score. We provide comprehensive coverage of additional constraints that model important objectives, heterogeneous data types, structural constraints on the feature space, along with resource and actionability restrictions. Our experimental analyses demonstrate that the proposed search approach requires a computational effort that is orders of magnitude smaller than previous mathematical programming algorithms. It scales up to large data sets and tree ensembles, where it provides, within seconds, systematic explanations grounded on well-defined models solved to optimality.