Authors: Klaus Weinbauer, Peter F. Stadler, Thomas Gärtner, Sagar Malhotra
Organizations: Machine Learning Research Unit, TU Wien, Wien, Austria · Bioinformatics Group, Leipzig University, Leipzig, Germany · Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany · Santa Fe Institute, Santa Fe, NM U.S.A.
We formally characterize the conditions under which sufficient explanations exist for classifiers on structured data such as graphs and strings. We focus on post-hoc explainers that select parts of the input as sufficient explanations. An explanation is sufficient if the selected part alone ensures the predicted label. Sufficient explanations have been widely adopted across data modalities, including graphs, strings, and images. However, a unified formal analysis of sufficient explanations remains missing. We bridge this gap with four main contributions: (i) We define a general explanation formalism consisting of an instance space, a classifier, and a select relation. The select relation specifies which potential sub-instances or feature subsets can be selected as explanations from each instance; (ii) We show that the existence of sufficient explainers is fully characterized by the interplay between the classifier and the select relation; (iii) We extend this analysis to practically relevant variants of sufficiency, including probabilistic sufficiency and deletion sufficiency; (iv) Based on the formal analysis, we devise statistics that bound the maximum achievable sufficiency for a given task. We evaluate these statistics on language, protein, and molecular classification datasets and find that full sufficiency is unattainable on most of them. Since these bounds hold for every explainer, they provide a task-level reference against which any explainer's sufficiency can be judged in absolute terms.
Figures & tables
Figure 1: A co-bound—a non-sufficiency witness—in the MUTAG dataset for subgraph-based explanations. The mutagenic molecule on the left is a subgraph of the non-mutagenic molecule on the right. Every subgraph of the mutagenic molecule also appears in the non-mutagenic molecule. Hence, a subgraph cannot explain the mutagenicity of this molecule sufficiently. 14% of all instances in MUTAG are co-bounds (see Table 1 ).
Figure 2: Example of three different selection domains for graph classification. The instance space on the left contains a single triangle graph. Given an explanation formalism, such as node-induced, edge-induced, or any subgraph, we obtain different selection domains. Isomorphic explanations are equivalent in this case.
Figure 3: Graphs are classified according to connectedness. A subgraph explanation for the connected instance x1 can never be sufficient because the instance x1 is also a subgraph of the disconnected instance x2 .
Dataset D
Instances
Co-bounds
In classes
Min acc loss l
Inter-class relation ρ
Min prob sufficiency M
Runtime
Graphs
AIDS
1933
81(4.2%)
1/2
17%
47%
91%
2min
MCF-7
27488
1046(3.8%)
2/2
6.9%
11%
97%
3h
MUTAG
183
25(14%)
2/2
23%
46%
73%
14s
Mutagenicity
4333
13(0.3%)
2/2
0.35%
9.6%
>99%
1h
NCI1
4032
171(4.2%)
2/2
9.7%
27%
96%
16min
ENZYMES
595
13(2.2%)
4/6
82%
81%
18%
21min
Table 1: Existence of co-bounds in molecular, protein, and natural language classification datasets. A co-bound is a witness for an insufficiently explainable class. For graphs the select relation is subgraphs, and for strings it is substrings. The runtime is the wall-clock time of finding co-bounds on an Intel(R) i9-12900KF CPU (no parallelization). Graph datasets are used as provided by Morris et al. (2020) . Isomorphic duplicates are reduced to one copy, or removed if they occur in more than one class. See Appendix E for co-bound examples.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Two-variable-propositional-logic example with partial truth assignment as select relation. The instance space is an antichain. Thus, there exists a sufficient explainer independent of the classification task. The unbounded selection order on the right emerges by restricting the instance space to uniform value assignments. In this setting every explainer is sufficient.
Package
Version
License
datasets
4.8.5
Apache-2.0
ipykernel
7.4.0
BSD-3-Clause
nbconvert
7.17.1
BSD-3-Clause
networkx
3.6.1
BSD-3-Clause
numpy
2.4.3
BSD-3-Clause
pandas
3.0.1
BSD-3-Clause
Appendix
Table 2: Software packages and their licenses.
Figure 5: Co-bound from AIDS dataset with (node/edge-induced) subgraph select relation.
Figure 6: Co-bounds from MCF-7 dataset with (node/edge-induced) subgraph select relation.
Figure 7: Co-bounds from MUTAG dataset with (node/edge-induced) subgraph select relation.
Figure 8: Co-bounds from Mutagenicity dataset with (node/edge-induced) subgraph select relation.
Figure 9: Co-bounds from NCI1 dataset with (node/edge-induced) subgraph select relation.
Figure 10: Co-bounds for class 0 from ENZYMES dataset with (node/edge-induced) subgraph select relation.
Figure 11: Co-bounds for class 1,4, and 5 from ENZYMES dataset with (node/edge-induced) subgraph select relation.
Figure 12: Co-bounds from PROTEINS dataset with (edge-induced) subgraph select relation.
Figure 13: Co-bounds from PROTEINS dataset with node-induced subgraph select relation.
Figure 14: Co-bounds from ToxinPred3 dataset with substring select relation.
Figure 15: Co-bounds from SST dataset with substring select relation.
We present MiSS, a black-box, query-based framework for explaining 3D point cloud classifiers through perturbation-relative sufficiency reasoning. MiSS treats a superpoint partition as an interpretable abstraction layer and asks whether the original prediction can be certified from a minimal coalition of geometric regions under a specified perturbation distribution. Unlike abductive explainers that require Boolean feature spaces or white-box logical encodings of the predictor, MiSS separates candidate proposal from verification: a weighted MaxSAT procedure proposes coalitions using a heuristic adaptive cardinality floor, certified exact-size fallback, a safely tightened upper bound, blocking clauses, and a surrogate acquisition heuristic learned from previous oracle evaluations, while a blackbox statistical oracle decides sufficiency from prediction queries. The system returns a statistically verified sufficient coalition as a binary attribution, with minimum cardinality guaranteed when certified search completes. Experiments on ModelNet40 and ShapeNet with PointNet and PointMLP classifiers show higher precision and coverage than rule-based baselines in most settings, with lower explanation time than exhaustive search.
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 FPNP 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
Large language models (LLMs) are increasingly deployed in high-stakes domains, where free-text explanations such as chain-of-thought and post-hoc rationales are used to justify model outputs. Yet it remains unclear whether these explanations are sufficient, i.e., if they contain enough information to explain the model's output-generating process. We generalize classical sufficiency from feature attributions to arbitrary explanations and prove that explanation sufficiency can change depending on the input distribution, which must be explicitly defined for LLM explanations. We propose using the LLM itself to generate alternative inputs conditioned on an explanation, capturing its beliefs about possible inputs. We formalize self-consistent sufficiency as a goal for free-text explanations and introduce an information-theoretic metric, SCSuff, that enables evaluation of free-text explanations without relying on predefined biases or shortcuts. Our experiments show that SCSuff agrees with targeted perturbation tests where applicable and demonstrate that explanation sufficiency can vary with the input distribution. We find LLM explanations are generally insufficient and weakly correlated with model size, accuracy, or output entropy. Analysis of final-token hidden states shows that top and bottom SCSuff scores can be predicted from internal representations, suggesting that SCSuff can guide detection and improvement of sufficient LLM explanations. The code for this paper is available at https://github.com/rajesh-lab/self-consistent-sufficiency .