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

Gleilson Pedro Fernandes, Thiago Alves Rocha · 2026

Read Concisely Explaining the Doubt: Minimum-Size Abductive Explanations for Linear Models with a Reject Option by Gleilson Pedro Fernandes, Thiago Alves Rocha (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14096.txt.

Introduction

Fernandes and Rocha tackle short explanations for why a linear model refuses to decide on a case. Models in health and finance may abstain when proof is thin, and users need the reason. Abductive explanations stay faithful to the model but can be hard to compute, and the smallest ones are harder still. Past work covers linear models without rejection, or gives non-minimal explanations with rejection. Their work takes on that harder combined problem.

Catalog record

CREATORGleilson Pedro Fernandes, Thiago Alves Rocha
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58160
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14096

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Concisely Explaining the Doubt: Minimum-Size Abductive Explanations for Linear Models with a Reject Option Gleilson Pedro Fernandes, Thiago Alves Rocha Abstract 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. 1 Introduction Machine learning systems have been increasingly incorporated into decision-making processes that directly affect people’s lives, such as medical diagnosis, credit approval, and applications in the justice system. In these scenarios, it is not sufficient for a model to achieve high predictive accuracy. It is equally fundamental that its decisions can be understood, audited, and considered trustworthy by human users and regulatory bodies. This challenge has driven advances in Explainable Artificial Intelligence (XAI), whose central goal is to make model behavior more transparent and justifiable. However, explanations are only truly useful in practice when they combine three essential properties: interpretability, fidelity to the underlying model, and computational efficiency. Methods that sacrifice fidelity in favor of speed may induce users into a false sense of confidence, especially in high-risk domains [ 20 , 29 , 31 ] . In this context, abductive explanations, grounded in formal logic, have received significant attention [ 15 , 22 ] . Such explanations identify non-redundant subsets of features that are sufficient to support a model decision, regardless of the values taken by the remaining features, thereby offering strong guarantees of fidelity [ 15 , 10 ] . However, these explanations are not necessarily of minimum size, which can hinder interpretability, as smaller explanations are easier for human decision-makers to inspect, communicate, and act upon. Furthermore, obtaining such explanations typically requires exploring an exponential combinatorial space, making exact approaches impractical for medium- and large-scale models, particularly in the case of deep neural networks with high-dimensional inputs [ 15 ] . Recent work [ 21 , 6 ] have shown that, for specific classes of models, it is possible to circumvent these limitations by exploiting structural properties. In particular, linear classifiers allow the efficient derivation of minimum-size abductive explanations in log-linear-time, by leveraging the bounded domain of the input features [ 21 ] . Most existing explanation methods implicitly treat all predictions in the same way, regardless of the level of uncertainty associated with them. This becomes problematic in scenarios where the model operates under high uncertainty, which are common in high-stakes domains. To address this issue, a reject option allows models to abstain when the available evidence is insufficient to support a reliable conclusion [ 8 , 12 , 14 ] . While the reject option improves decision safety by preventing unreliable predictions, it also raises a fundamental explanatory question: “ why was a given instance rejected?” [ 4 ] . From an XAI perspective, rejection does not eliminate the need for explanations; rather, it changes their role. Instead of justifying a specific predicted outcome, explanations for rejected instances must clarify the conditions under which the model is unable to reach a reliable conclusion, so that human experts can understand the source of uncertainty and decide how to proceed [ 28 , 24 ] . In this setting, minimum-size abductive explanations become particularly important. Explanations based on a small number of features more clearly expose the sources of uncertainty in the model’s decision process, facilitating efficient inspection and informed intervention by human experts. Linear models with a reject option could also be particularly valuable as surrogate explainers for complex predictors. Instances falling within the surrogate model’s rejection region might correspond to areas of high uncertainty in the original predictor. Rather than forcing potentially misleading explanations, rejection may signal the limits of the surrogate’s reliability. In this setting, minimum-size abductive explanations computed for rejected instances can help expose a smallest set of features that is sufficient to characterize this uncertainty, supporting efficient inspection and informed human intervention. We leave for future work the exploration of minimum-size abductive explanation techniques using linear surrogate models with a reject option for explaining complex predictors. In light of the considerations above, we propose MINABRO ( MINimum-size ABductive explanations for linear models with a Reject Option ). MINABRO explicitly accounts for the presence of a reject option in linear models. For accepted predictions, MINABRO employs a greedy algorithm adapted from [ 21 ] , which was originally designed for linear classifiers without a rejection mechanism. Our adaptation provably computes minimum-size abductive explanations for linear models with a reject option while preserving the same log-linear time complexity as the original method. For rejected predictions, MINABRO relies on a 0 – 1 ILP (Integer Linear Programming) formulation to compute minimum-size abductive explanations of rejection. Although this formulation is NP-hard in theory, our experimental results show that it remains computationally efficient in practice and often outperforms the linear-programming-based approach of [ 28 ] , which computes abductive explanations but does not guarantee minimum size. Our experimental evaluation on ten public datasets demonstrates the advantages of MINABRO over two reference methods: Anchors, a sampling-based heuristic, and AbLinRO, a logic-based method that employs linear programming. While both MINABRO and AbLinRO ensure full fidelity to the underlying model, AbLinRO does not guarantee that the resulting explanations are of minimum size. Regarding computational efficiency, MINABRO is orders of magnitude faster than both reference mthods, maintaining stable execution times even in high-dimensional scenarios like MNIST. Notably, even when solving the NP-hard formulation for rejected instances, MINABRO remains more efficient than the linear-programming-based AbLinRO. Furthermore, while the heuristic nature of Anchors leads to shorter but unfaithful explanations, MINABRO provably achieves the smallest possible explanation size among the ones that guarantee full model fidelity. Furthermore, MINABRO consistently produces more concise explanations than AbLinRO, particularly for rejected instances, where explanations tend to be larger. This difference is further illustrated through a visual example of a rejected digit

Read the complete text