Research map / Learning theory and algorithms / Prediction and decision losses

Counterfactual Maps: What They Are and How to Find Them

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Compact interpretable model classes · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces counterfactual maps, compressing a tree ensemble into labeled hyperrectangles and indexing each target class with a volumetric KD-tree, enabling exact, certified nearest-region counterfactual queries in milliseconds after one-time preprocessing.

Problem

Computing globally optimal counterfactual explanations for tree ensembles is either heuristic without optimality guarantees or exact via MIP/SAT per query, which is too slow for interactive use.

Approach

Treat counterfactual search as nearest-region search over the hyperrectangle partition induced by a tree ensemble (generalized Voronoi cells), precompute a per-class volumetric KD-tree, and answer queries via branch-and-bound with an exactness proof, then project onto the nearest rectangle.

Key results

• CF-Maps generates 1000 optimal counterfactuals in 1.4 to 45 ms-scale totals (e.g., 1.4 ms on CP, 32.1 on PD) versus OCEAN's 618.7 to 42983.2 for the same set (Table 2).
• Heuristic baselines are suboptimal: LIRE distance ratio up to 3.4x, FT up to 3.2x with failure rates up to 93.2% on BC, and DiCE up to 4.8x.
• CF-Maps preprocessing is costly (e.g., 556.7 on BC and 467.5 on PD for 100 depth-5 trees), far exceeding OCEAN's per-dataset preprocessing time.

Surprising findings

• CF-Maps preprocessing time (up to ~468-557 units) exceeds OCEAN's total time on some datasets, so amortization only pays off over many queries.
• Feature Tweaking fails to return valid counterfactuals for most queries on larger forests (e.g., 93.2% on BC with 100 trees).

Limitations

• Preprocessing (partition extraction via BA-Trees and KD-tree build) is the dominant cost and may not scale to large ensembles.
• Node counts can be very large (e.g., about 2.5 million KD-tree nodes on BC), with memory growing with the partition size.
• Only random forests of depth up to 7 and small tabular datasets are evaluated; gradient-boosted trees are not reported.

Experimental setup

Datasets: Breast Cancer Wisconsin COMPAS FICO Pima-Diabetes Seeds

Benchmarks: Breast Cancer Wisconsin COMPAS FICO Pima-Diabetes Seeds

Metrics: preprocessing time query latency (total time for 1000 counterfactuals) failure rate %F distance ratio D relative to optimum

Baselines: OCEAN Feature Tweaking LIRE DiCE

Builds on: born-again tree ensembles (BA-Trees) OCEAN Feature Tweaking LIRE DiCE

Closest papers by meaning

• LeapFactual: Reliable Visual Counterfactual Explanation Using Conditional Flow Matching (NeurIPS 2025 · similarity 0.88)
• Rethinking Visual Counterfactual Explanations Through Region Constraint (ICLR 2025 · similarity 0.87)
• CounterFlowNet: From Minimal Changes to Meaningful Counterfactual Explanations (NeurIPS 2026 · similarity 0.87)
• Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theory (NeurIPS 2024 · similarity 0.86)
• Robust Stochastic Graph Generator for Counterfactual Explanations (AAAI 2024 · similarity 0.86)
• A General Search-Based Framework for Generating Textual Counterfactual Explanations (AAAI 2024 · similarity 0.86)