# Counterfactual Maps: What They Are and How to Find Them

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 28 references that are in the map.
- First posted on arXiv 9 Feb 2026.

## 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)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (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)
- [Preserving Causal Constraints in Counterfactual Explanations for Machine Learning Classifiers](https://mlsanity.com/paper/1912.03277/) (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)
- [Optimal Counterfactual Explanations in Tree Ensembles](https://mlsanity.com/paper/2106.06631/) (2021)
- [Conditional Generative Models for Counterfactual Explanations](https://mlsanity.com/paper/2101.10123/) (2021)
- [Amortized Generation of Sequential Algorithmic Recourses for Black-box Models](https://mlsanity.com/paper/2106.03962/) (2021)
- [Model-agnostic and Scalable Counterfactual Explanations via Reinforcement Learning](https://mlsanity.com/paper/2106.02597/) (2021)
- [Model-Based Counterfactual Synthesizer for Interpretation](https://mlsanity.com/paper/2106.08971/) (2021)
- [Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization](https://mlsanity.com/paper/2012.11782/) (2020)
- [Very fast, approximate counterfactual explanations for decision forests](https://mlsanity.com/paper/2303.02883/) (2023)
- [An exact counterfactual-example-based approach to tree-ensemble models interpretability](https://mlsanity.com/paper/2105.14820/) (2021)

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

- [Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms](https://mlsanity.com/paper/2605.06561/) (2026)
- [Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives](https://mlsanity.com/paper/2607.07762/) (2026)

## Abstract (arXiv)

Counterfactual explanations are a central tool in interpretable machine learning, yet computing them exactly for complex models remains challenging. For tree ensembles, predictions are piecewise constant over a large collection of axis-aligned hyperrectangles, implying that an optimal counterfactual for a point corresponds to its projection onto the nearest rectangle with an alternative label under a chosen metric. Existing methods largely overlook this geometric structure, relying either on heuristics with no optimality guarantees or on mixed-integer programming formulations that do not scale to interactive use. In this work, we revisit counterfactual generation through the lens of nearest-region search and introduce counterfactual maps, a global representation of recourse for tree ensembles. Leveraging the fact that any tree ensemble can be compressed into an equivalent partition of labeled hyperrectangles, we cast counterfactual search as the problem of identifying the generalized Voronoi cell associated with the nearest rectangle of an alternative label. This leads to an exact, amortized algorithm based on volumetric k-dimensional (KD) trees, which performs branch-and-bound nearest-region queries with explicit optimality certificates and sublinear average query time after a one-time preprocessing phase. Our experimental analyses on several real datasets drawn from high-stakes application domains show that this approach delivers globally optimal counterfactual explanations with millisecond-level latency, achieving query times that are orders of magnitude faster than existing exact, cold-start optimization methods.