# ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets

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

## Key facts

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

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously](https://mlsanity.com/paper/1801.01489/) (2018)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [Neural Additive Models: Interpretable Machine Learning with Neural Nets](https://mlsanity.com/paper/2004.13912/) (2020)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Predictive Multiplicity in Classification](https://mlsanity.com/paper/1909.06677/) (2019)
- [Learning Model-Agnostic Counterfactual Explanations for Tabular Data](https://mlsanity.com/paper/1910.09398/) (2019)
- [Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems](https://mlsanity.com/paper/1907.09615/) (2019)
- [Efficient Search for Diverse Coherent Explanations](https://mlsanity.com/paper/1901.04909/) (2019)
- [Towards Robust and Reliable Algorithmic Recourse](https://mlsanity.com/paper/2102.13620/) (2021)
- [On the Existence of Simpler Machine Learning Models](https://mlsanity.com/paper/1908.01755/) (2019)
- [Exploring the Whole Rashomon Set of Sparse Decision Trees](https://mlsanity.com/paper/2209.08040/) (2022)
- [NICE: An Algorithm for Nearest Instance Counterfactual Explanations](https://mlsanity.com/paper/2104.07411/) (2021)
- [It's COMPASlicated: The Messy Relationship between RAI Datasets and Algorithmic Fairness Benchmarks](https://mlsanity.com/paper/2106.05498/) (2021)
- [Amazing Things Come From Having Many Good Models](https://mlsanity.com/paper/2407.04846/) (2024)
- [Inverse Classification for Comparison-based Interpretability in Machine Learning](https://mlsanity.com/paper/1712.08443/) (2017)
- [Robust Counterfactual Explanations for Tree-Based Ensembles](https://mlsanity.com/paper/2207.02739/) (2022)
- [Rashomon Capacity: A Metric for Predictive Multiplicity in Classification](https://mlsanity.com/paper/2206.01295/) (2022)
- [Robust Counterfactual Explanations for Neural Networks With Probabilistic Guarantees](https://mlsanity.com/paper/2305.11997/) (2023)
- [Interpretable Credit Application Predictions With Counterfactual Explanations](https://mlsanity.com/paper/1811.05245/) (2018)
- [A Path to Simpler Models Starts With Noise](https://mlsanity.com/paper/2310.19726/) (2023)
- [Exploring and Interacting with the Set of Good Sparse Generalized Additive Models](https://mlsanity.com/paper/2303.16047/) (2023)
- [The Rashomon Importance Distribution: Getting RID of Unstable, Single Model-based Variable Importance](https://mlsanity.com/paper/2309.13775/) (2023)
- [An Empirical Evaluation of the Rashomon Effect in Explainable Machine Learning](https://mlsanity.com/paper/2306.15786/) (2023)
- [Formalising the Robustness of Counterfactual Explanations for Neural Networks](https://mlsanity.com/paper/2208.14878/) (2022)
- [Scaling Guarantees for Nearest Counterfactual Explanations](https://mlsanity.com/paper/2010.04965/) (2020)
- [Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation](https://mlsanity.com/paper/2309.12545/) (2023)

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

- [Algorithmic Recourse of In-Context Learning for Tabular Data](https://mlsanity.com/paper/2605.31272/) (2026)
- [Algorithmic Recourse Under Competition](https://mlsanity.com/paper/2609.39877/) (2026)

## Abstract (arXiv)

Machine learning models now influence decisions that directly affect people's lives, making it important to understand not only their predictions, but also how individuals could act to obtain better results. Algorithmic recourse provides actionable input modifications to achieve more favorable outcomes, typically relying on counterfactual explanations to suggest such changes. However, when the Rashomon set - the set of near-optimal models - is large, standard counterfactual explanations can become unreliable, as a recourse action valid for one model may fail under another. We introduce ElliCE, a novel framework for robust algorithmic recourse that optimizes counterfactuals over an ellipsoidal approximation of the Rashomon set. The resulting explanations are provably valid over this ellipsoid, with theoretical guarantees on uniqueness, stability, and alignment with key feature directions. Empirically, ElliCE generates counterfactuals that are not only more robust but also more flexible, adapting to user-specified feature constraints while being substantially faster than existing baselines. This provides a principled and practical solution for reliable recourse under model uncertainty, ensuring stable recommendations for users even as models evolve.