On the Limits of Sufficient Explanations

Klaus Weinbauer, Peter F. Stadler, Thomas Gärtner, Sagar MalhotraarXiv 2026 · arXiv

TL;DR

This paper mathematically proves that "sufficient explanations"—subsets of input features that guarantee a specific prediction—are often impossible to achieve for structured data like graphs and text. By introducing the concept of co-bounds, the authors provide a framework to measure the intrinsic limits of explainability for any dataset, showing that for many real-world tasks, no explainer can ever be fully "sufficient."

What Problem Does This Paper Address?

In machine learning, we often want to know why a model made a specific prediction. A popular approach is to find a "sufficient explanation": a part of the input (like a functional group in a molecule or a phrase in a sentence) that, on its own, ensures the model's output remains the same.

While researchers have developed many "post-hoc" explainers to find these snippets, we haven't had a formal way to determine if a task allows for such explanations in the first place. Most existing theory focuses on simple, fixed-size data (like images of a set resolution). This paper tackles the more complex world of structured data—graphs and strings of varying sizes—where a "part" of one instance might also be a "part" of a completely different instance with a different label. The authors ask: Is the failure to find a perfect explanation a flaw in our algorithms, or is it an inherent property of the data itself?

Methods

The authors build a formal bridge between classifiers and explanation methods using three components:

  1. Instance Space ($X$): The set of all possible inputs (e.g., all possible molecules).
  2. Classifier ($f$): The model mapping inputs to labels.
  3. Select Relation ($\preceq$): A formal rule defining what can be chosen as an explanation. For example, in graph classification, an explanation might be restricted to being a "node-induced subgraph."

The core of their method is the discovery of co-bounds. A co-bound is an instance $x$ that can be "selected" from another instance $x'$ that has a different label.

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).

The authors prove a fundamental theorem: A sufficient explainer exists if and only if there are no co-bounds in the task. They further extend this to "probabilistic sufficiency" (how likely a label is to stay the same under random perturbations) and "deletion sufficiency" (label stability when non-explanation parts are removed).

Datasets

The researchers evaluated their theory on ten diverse real-world datasets:

  • Graphs: AIDS (antiviral activity), MCF-7 (anti-cancer), MUTAG & Mutagenicity (molecular properties), NCI1 (chemical compounds), ENZYMES, and PROTEINS.
  • Strings: ToxinPred2 & ToxinPred3 (peptide toxicity) and SST-2 (sentiment analysis of text).

Key Insights and Ideas

  • The "In-Distribution" Barrier: Unlike many explainability issues blamed on "out-of-distribution" data (where the model sees something it wasn't trained on), co-bounds represent a fundamental conflict within the data distribution. If "great" is a positive feature but appears in the negative phrase "not great," then "great" is a co-bound that prevents it from being a sufficient explanation for positive sentiment.
  • Task-Level Limits: Sufficiency is not just a property of the explainer; it's a property of the task. The authors developed statistics like the Inter-class relation ratio ($\rho$) to quantify how "un-explainable" a dataset is before you even train a model.
  • The ENZYMES Paradox: They found that even if only a few instances are co-bounds (2.2% in the ENZYMES dataset), the "ripple effect" can be massive. To make ENZYMES "co-bound free" (and thus perfectly explainable), you would have to relabel 82% of the instances.
  • Selection Matters: Whether a sufficient explanation exists depends heavily on the "select relation." A task might be explainable if you only allow node-induced subgraphs but impossible if you allow any arbitrary subgraph.
Figure 2. Example of three different selection domains for graph classification. The instance space on the left contains a single trian- gle graph. Given an explanation formalism, such as node-induced, edge-induced, or any subgraph, we obtain different selection do- mains. Isomorphic explanations are equivalent in this case.

Key Results

The empirical analysis (summarized in the table below) shows that perfect sufficiency is a myth for most structured data tasks.

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.
  • Ubiquity of Co-bounds: 9 out of 10 datasets contained co-bounds. In the SST-2 sentiment dataset, a staggering 21% of instances were co-bounds.
  • Hard Upper Bounds: For the PROTEINS dataset, the authors calculated that the maximum achievable probabilistic sufficiency for certain instances is only 58%. No matter how good your explainer is, it cannot exceed this limit.
  • MUTAG: 14% of instances are co-bounds, leading to a minimum accuracy loss of 23% if one were to force the dataset to be perfectly explainable.

Limitations and Future Work

The authors acknowledge that their work focuses specifically on sub-instance based explanations (selecting parts of the input). It does not yet cover other popular explanation styles, such as:

  • Prototypes: Explaining by showing a similar example.
  • Counterfactuals: Explaining by showing what would have to change to get a different result.

Future work involves extending this formal framework to these other modalities to create a truly unified theory of the limits of machine learning interpretability.

Summary updated

Abstract

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.
BibTeX
@misc{weinbauer2026limits,
  author = {Klaus Weinbauer and Peter F. Stadler and Thomas Gärtner and Sagar Malhotra},
  title = {{On the Limits of Sufficient Explanations}},
  year = {2026},
  eprint = {2611.18163},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.18163},
}
Figure