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

Gleilson Pedro Fernandes; Thiago Alves Rocha

cs.LGMar 14, 2026

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

Authors: Gleilson Pedro Fernandes, Thiago Alves Rocha

Organizations: Instituto Federal do Ceará (IFCE), Brazil

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.

Figures & tables

Dataset	# Explained Instances	# Features	$t^{+}$	$t^{-}$	Rejection Width	Rejection Rate (%)	Accuracy w/o RO (%)	Accuracy w/ RO (%)
Banknote	412	4	0.01	$-0.35$	0.36	58.74	61.41	94.71
Vertebral Col.	93	6	1.10	$-0.07$	1.17	37.63	76.34	86.21
Pima Indians	231	8	0.07	$-0.01$	0.08	1.30	74.46	75.00
Heart Disease	90	13	0.19	$-0.11$	0.30	42.22	85.56	96.15
Credit Card	2563	29	4.47	$-0.01$	4.48	0.35	99.73	99.96
Breast Cancer	171	30	0.97	$-0.01$	0.98	19.88	93.57	98.54

Table 1: Summary of datasets and experimental setup, including the number of instances explained, classifier calibration parameters, and classifier performance metrics.

Dataset	MINABRO		Anchors		AbLinRO
Dataset	Clas.	Rej.	Clas.	Rej.	Clas.	Rej.
Banknote	1.38 $\pm$ 0.28	1.47 $\pm$ 0.26	140.89 $\pm$ 266.85	64.97 $\pm$ 87.47	167.94 $\pm$ 46.66	237.13 $\pm$ 48.21
Vertebral Col.	1.43 $\pm$ 0.24	1.61 $\pm$ 0.26	422.66 $\pm$ 582.89	159.62 $\pm$ 102.17	284.73 $\pm$ 29.44	383.43 $\pm$ 56.99
Pima Indians	1.64 $\pm$ 0.48	1.85 $\pm$ 0.08	501.58 $\pm$ 447.69	1332.36 $\pm$ 889.97	345.53 $\pm$ 71.27	332.56 $\pm$ 10.83
Heart Disease	1.64 $\pm$ 0.27	1.96 $\pm$ 0.21	1099.30 $\pm$ 373.09	1174.24 $\pm$ 391.55	528.83 $\pm$ 42.57	973.86 $\pm$ 128.96
Credit Card	1.92 $\pm$ 0.40	2.80 $\pm$ 0.84	189.01 $\pm$ 325.32	32682.01 $\pm$ 15838.11	1192.66 $\pm$ 142.95	1678.53 $\pm$ 371.69

Table 2: Average execution time and standard deviation (ms) for classified and rejected instances.

Dataset	MINABRO		Anchor		AbLinRO
Dataset	Acc.	Rej.	Acc.	Rej.	Acc.	Rej.
Banknote	2.86 $\pm$ 0.65	2.60 $\pm$ 0.70	1.37 $\pm$ 0.99	1.04 $\pm$ 0.34	2.86 $\pm$ 0.65	2.73 $\pm$ 0.67
Vertebral Col.	4.34 $\pm$ 1.04	5.06 $\pm$ 0.23	2.03 $\pm$ 1.57	1.86 $\pm$ 0.54	4.41 $\pm$ 0.97	5.06 $\pm$ 0.23
Pima Indians	4.17 $\pm$ 1.20	8.00 $\pm$ 0.00	2.49 $\pm$ 0.97	5.33 $\pm$ 1.70	4.60 $\pm$ 1.22	8.00 $\pm$ 0.00
Heart Dis.	7.15 $\pm$ 1.41	6.84 $\pm$ 1.27	2.63 $\pm$ 0.66	2.79 $\pm$ 0.73	7.44 $\pm$ 1.46	6.61 $\pm$ 1.51
Credit Card	15.76 $\pm$ 1.42	17.33 $\pm$ 5.10	0.19 $\pm$ 0.39	7.56 $\pm$ 0.83	20.33 $\pm$ 1.56	20.44 $\pm$ 3.95

Table 3: Average explanation size (number of features) for classified and rejected instances.

Figure 1: Comparison of explanations for a rejected digit in the MNIST (3 vs. 8) task. Red pixels indicate features included in the explanation. Left: Original digit, which is rejected by the trained logistic regression classifier with reject option. Center: MINABRO explanation. Right: AbLinRO explanation.

Explore similar work

Sep 16, 2026

Probabilistic Linear Explanations

Formal explainability provides mathematically grounded justifications for individual predictions. However, abductive explanations often exceed human cognitive limits by involving too many features, while probabilistic relaxations have remained largely limited to categorical classification. We present a unified framework for probabilistic explainability based on sparse, anchored linear models, applicable to both binary classification and continuous regression. By mapping instances to the Boolean hypercube, our linear explanations strictly generalize subset-based approaches: they capture both the magnitude and direction of feature contributions while enforcing a prescribed sparsity budget

k

. We show that minimizing the relevance error for such explanations is \ClassNPPP-hard when the underlying model is a neural network, and we relate this intractable objective to a tractable surrogate---the fidelity error. For a parameterized family of local distributions, the relevance error of any

k

-sparse explanation is bounded by its fidelity error up to a multiplicative factor that remains small locally. We address the resulting empirical problem using two complementary approaches: a Mixed Integer Programming (MIP) formulation that yields provably optimal empirical solutions while maintaining polynomial sample complexity, and a polynomial-time Iterative Hard Thresholding (IHT) algorithm with provable approximation guarantees. Empirical evaluations show that, unlike state-of-the-art baselines such as LIME and MAPLE, our explanations satisfy both the anchoring and sparsity constraints by construction, while consistently achieving lower relevance error.

Frederic Koriche, Jean-Marie Lagniez, Chi Tran

Computer science Research Institute of Lens (CRIL), UMR CNRS 8188, University of Artois, Rue Jean Souvraz SP 18, Lens, F-62307, France

Explainable Artificial Intelligence Mixed-Integer QP

Ask PDF

Jul 7, 2026

ExplAIner: A Declarative Query Language for Explaining Classification Models

The XAI community has studied a wide range of queries and scores for explaining predictions of ML models. From a data management perspective, this proliferation of explanation notions calls for declarative query languages in which such notions can be specified, combined, and analyzed uniformly. In this paper, we develop such a framework for Boolean models. We first revisit FOIL, an interpretability query language for black-box models, and show that it has two fundamental limitations: it cannot express central optimality-based explanation queries, and its evaluation problem over decision trees is hard for every level of the polynomial hierarchy. We then introduce ExplAIner, a query language based on FOIL with an extended vocabulary and a layered structure. We show that ExplAIner can express a broad family of explanation notions, including abductive, contrastive, feature-based, and distance-based queries. We also prove that the evaluation problem for each query in ExplAIner belongs to the Boolean hierarchy over every class of Boolean models for which some basic predicates can be evaluated in polynomial time. In particular, that property holds for deterministic and decomposable Boolean circuits. Finally, we introduce Opt-FOIL, an optimization-oriented fragment of ExplAIner for computing explanations that are minimal with respect to strict partial orders, and prove that its evaluation problem is in

\mathrm{FP}^{\mathrm{NP}}

under the same tractability assumptions. These complexity results have a direct algorithmic consequence: a fixed ExplAIner query can be evaluated with a fixed number of calls to a SAT solver, while a notion of explanation specified in Opt-FOIL can be computed with a polynomial number of such calls. This is particularly relevant in formal XAI, where SAT solvers have been successfully used to compute explanations for several classes of ML models.

Marcelo Arenas, Pablo Barceló, Diego Bustamante +3

Pontificia Universidad Católica de Chile, Chile · Carnegie Mellon University, USA

Explainable Artificial Intelligence Interpretable ML

Ask PDF

Mar 16, 2026

Hypothesis Class Determines Explanation: Why Accurate Models Disagree on Feature Attribution

The assumption that prediction-equivalent models produce equivalent explanations underlies many practices in explainable AI, including model selection, auditing, and regulatory evaluation. In this work, we show that this assumption does not hold. Through a large-scale empirical study across 24 datasets and multiple model classes, we find that models with identical predictive behavior can produce substantially different feature attributions. This disagreement is highly structured: models within the same hypothesis class exhibit strong agreement, while cross-class pairs (e.g., tree-based vs. linear) trained on identical data splits show substantially reduced agreement, consistently near or below the lottery threshold. We identify hypothesis class as the structural driver of this phenomenon, which we term the Explanation Lottery. We theoretically show that the resulting Agreement Gap persists under interaction structure in the data-generating process. This structural finding motivates a post-hoc diagnostic, the Explanation Reliability Score R(x), which predicts when explanations are stable across architectures without additional training. Our results demonstrate that model selection is not explanation-neutral: the hypothesis class chosen for deployment can determine which features are attributed responsibility for a decision.

Thackshanaramana B

SRM Institute of Science and Technology, India

Feature Attribution Explainability Evaluation Model Selection

Ask PDF