# Concisely Explaining the Doubt: Minimum-Size Abductive Explanations for Linear Models with a Reject Option

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 34 references that are in the map.
- First posted on arXiv 14 Mar 2026.

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

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [SelectiveNet: A Deep Neural Network with an Integrated Reject Option](https://mlsanity.com/paper/1901.09192/) (2019)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Machine Learning with a Reject Option: A survey](https://mlsanity.com/paper/2107.11277/) (2021)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks](https://mlsanity.com/paper/2210.13915/) (2022)
- [On Validating, Repairing and Refining Heuristic ML Explanations](https://mlsanity.com/paper/1907.02509/) (2019)
- [Computing Abductive Explanations for Boosted Trees](https://mlsanity.com/paper/2209.07740/) (2022)
- [Delivering Inflated Explanations](https://mlsanity.com/paper/2306.15272/) (2023)
- ["Even if ..." -- Diverse Semifactual Explanations of Reject](https://mlsanity.com/paper/2207.01898/) (2022)
- [Explaining Reject Options of Learning Vector Quantization Classifiers](https://mlsanity.com/paper/2202.07244/) (2022)
- [Model Agnostic Local Explanations of Reject](https://mlsanity.com/paper/2205.07623/) (2022)
- [Most General Explanations of Tree Ensembles (Extended Version)](https://mlsanity.com/paper/2505.10991/) (2025)
- [Logic-based Explanations for Linear Support Vector Classifiers with Reject Option](https://mlsanity.com/paper/2403.16190/) (2024)
- [Knowing What You Cannot Explain: Learning to Reject Low-Quality Explanations](https://mlsanity.com/paper/2507.12900/) (2025)
- [Generalizing Logic-based Explanations for Machine Learning Classifiers via Optimization](https://mlsanity.com/paper/2603.01870/) (2026)

## Abstract (arXiv)

Trustworthiness in artificial intelligence depends not only on what a model decides, but also on how it handles and explains cases in which a reliable decision cannot be made. In critical domains such as healthcare and finance, a reject option allows the model to abstain when evidence is insufficient, making it essential to explain why an instance is rejected in order to support informed human intervention. In these settings, explanations must not only be interpretable, but also faithful to the underlying model and computationally efficient enough to support real-time decision making. Abductive explanations guarantee fidelity, but their exact computation is known to be NP-hard for many classes of models, limiting their practical applicability. Computing minimum-size abductive explanations is an even more challenging problem, as it requires reasoning not only about fidelity but also about optimality. Prior work has addressed this challenge in restricted settings, including log-linear-time algorithms for computing minimum-size abductive explanations in linear models without rejection, as well as a polynomial-time method based on linear programming for computing abductive explanations, without guarantees of minimum size, for linear models with a reject option. In this work, we bridge these lines of research by computing minimum-size abductive explanations for linear models with a reject option. For accepted instances, we adapt the log-linear algorithm to efficiently compute optimal explanations. For rejected instances, we formulate a 0-1 integer linear programming problem that characterizes minimum-size abductive explanations of rejection. Although this formulation is NP-hard in theory, our experimental results show that it is consistently more efficient in practice than the linear-programming-based approach that does not guarantee minimum-size explanations.