# Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 7 May 2026.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Interpretable Counterfactual Explanations Guided by Prototypes](https://mlsanity.com/paper/1907.02584/) (2019)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Counterfactual Explanations and Algorithmic Recourses for Machine Learning: A Review](https://mlsanity.com/paper/2010.10596/) (2020)
- [Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems](https://mlsanity.com/paper/1907.09615/) (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)
- [Optimal Counterfactual Explanations in Tree Ensembles](https://mlsanity.com/paper/2106.06631/) (2021)
- [Optimal Decision Diagrams for Classification](https://mlsanity.com/paper/2205.14500/) (2022)
- [Very fast, approximate counterfactual explanations for decision forests](https://mlsanity.com/paper/2303.02883/) (2023)
- [Counterfactual Maps: What They Are and How to Find Them](https://mlsanity.com/paper/2602.09128/) (2026)

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

- [Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives](https://mlsanity.com/paper/2607.07762/) (2026)

## Abstract (arXiv)

Trust in counterfactual explanations depends critically on whether their recommended changes are truly minimal: suboptimal explanations may vastly overshoot the actual changes needed to alter a decision, and heuristic errors can affect individuals unevenly, giving some users relevant recourse while assigning others unnecessarily costly recommendations. Consequently, we study the problem of computing optimal counterfactual explanations for tree ensembles under plausibility and actionability constraints. This is a combinatorial problem: for a fixed model, counterfactual search boils down to selecting consistent branching decisions and threshold-defined regions under a distance objective. We exploit this structure through CPCF, a constraint programming (CP) formulation in which numerical features are encoded as interval domains induced by split thresholds, while discrete features retain native finite-domain representations. This yields a compact finite-domain formulation that supports multiple distance objectives without continuous split-boundary search. We then place CPCF in a broader comparison across mathematical programming paradigms: we extend a maximum Boolean satisfiability (MaxSAT) formulation, originally designed for hard-voting random forests, to soft-voting ensembles, and compare against the current state-of-the-art mixed-integer linear programming (MILP) optimal approach. Across ten datasets and three types of tree ensembles, we analyze scalability, anytime performance, and sensitivity to distance metrics. We observe that CP achieves the best overall performance. More importantly, our results identify regimes in which the specific strengths of each paradigm make it best suited: CP is most versatile overall, MaxSAT handles hard-voting ensembles particularly well, and MILP remains competitive in amortized inference settings with a moderate number of split levels.