首页 > AI前沿 > On the Limits of Sufficient Explanations

On the Limits of Sufficient Explanations

arXiv机器学习 2026-11-13 21:38 9 阅读 查看原文

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.