# Even-if Explanations: Formal Foundations, Priorities and Complexity

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 48 references that are in the map.
- First posted on arXiv 17 Jan 2024.

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

- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Fine-tuning language models to find agreement among humans with diverse preferences](https://mlsanity.com/paper/2211.15006/) (2022)
- [Benchmarking and Survey of Explanation Methods for Black Box Models](https://mlsanity.com/paper/2102.13076/) (2021)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [On Generating Plausible Counterfactual and Semi-Factual Explanations for Deep Learning](https://mlsanity.com/paper/2009.06399/) (2020)
- [Logic Explained Networks](https://mlsanity.com/paper/2108.05149/) (2021)
- [On Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (2022)
- [Personalized Transfer of User Preferences for Cross-domain Recommendation](https://mlsanity.com/paper/2110.11154/) (2021)
- [Counterfactual Explanation Algorithms for Behavioral and Textual Data](https://mlsanity.com/paper/1912.01819/) (2019)
- [Foundations of Symbolic Languages for Model Interpretability](https://mlsanity.com/paper/2110.02376/) (2021)
- [Probabilistic Sufficient Explanations](https://mlsanity.com/paper/2105.10118/) (2021)
- [Even if Explanations: Prior Work, Desiderata & Benchmarks for Semi-Factual XAI](https://mlsanity.com/paper/2301.11970/) (2023)
- [The #DNN-Verification Problem: Counting Unsafe Inputs for Deep Neural Networks](https://mlsanity.com/paper/2301.07068/) (2023)
- [Cardinality-Minimal Explanations for Monotonic Neural Networks](https://mlsanity.com/paper/2205.09901/) (2022)
- [The Utility of "Even if..." Semifactual Explanation to Optimise Positive Outcomes](https://mlsanity.com/paper/2310.18937/) (2023)
- [Choose your Data Wisely: A Framework for Semantic Counterfactuals](https://mlsanity.com/paper/2305.17667/) (2023)
- [Interpretable Regional Descriptors: Hyperbox-Based Local Explanations](https://mlsanity.com/paper/2305.02780/) (2023)
- [The Computational Complexity of Dominance and Consistency in CP-Nets](https://mlsanity.com/paper/1401.3453/) (2014)
- [Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting](https://mlsanity.com/paper/1806.10018/) (2018)

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

- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI](https://mlsanity.com/paper/2601.09455/) (2026)
- [ExplAIner: A Declarative Query Language for Explaining Classification Models](https://mlsanity.com/paper/2607.06407/) (2026)
- [Explanations-Driven Active Feature Acquisition for Algorithmic Recourse](https://mlsanity.com/paper/2609.12179/) (2026)

## Abstract (arXiv)

EXplainable AI has received significant attention in recent years. Machine learning models often operate as black boxes, lacking explainability and transparency while supporting decision-making processes. Local post-hoc explainability queries attempt to answer why individual inputs are classified in a certain way by a given model. While there has been important work on counterfactual explanations, less attention has been devoted to semifactual ones. In this paper, we focus on local post-hoc explainability queries within the semifactual `even-if' thinking and their computational complexity among different classes of models, and show that both linear and tree-based models are strictly more interpretable than neural networks. After this, we introduce a preference-based framework that enables users to personalize explanations based on their preferences, both in the case of semifactuals and counterfactuals, enhancing interpretability and user-centricity. Finally, we explore the complexity of several interpretability problems in the proposed preference-based framework and provide algorithms for polynomial cases.