Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons
Authors: Shahaf Bassan
Ron Eliav
Shlomit Gur
Venue: ICLR 2025 Poster (2025)
Keywords: XAI
explainability
explainable AI
self-explaining neural networks
Formal XAI
sufficient reasons
abductive explanations
interpretability
feature selection
Primary area: interpretability and explainable AI
TL;DR: A method to generate concise and faithful sufficient explanations for predictions using self-explaining neural networks

Abstract: *Minimal sufficient reasons* represent a prevalent form of explanation - the smallest subset of input features which, when held constant at their corresponding values, ensure that the prediction remains unchanged. Previous *post-hoc* methods attempt to obtain such explanations but face two main limitations: (1) Obtaining these subsets poses a computational challenge, leading most scalable methods to converge towards suboptimal, less meaningful subsets; (2) These methods heavily rely on sampling out-of-distribution input assignments, potentially resulting in counterintuitive behaviors. To tackle these limitations, we propose in this work a self-supervised training approach, which we term *sufficient subset training* (SST). Using SST, we train models to generate concise sufficient reasons for their predictions as an integral part of their output. Our results indicate that our framework produces succinct and faithful subsets substantially more efficiently than competing post-hoc methods while maintaining comparable predictive performance.

Published as a conference paper at ICLR 2025
EXPLAIN YOURSELF, BRIEFLY! SELF-EXPLAINING NEURAL NETWORKS WITH CONCISE SUFFICIENT REASONS
Shahaf Bassan 1:2,
Ron Eliav!.3, 1.3 Shlomit Gur!
IBM Research', The Hebrew University of Jerusalem². Bar-Ilan University shahaf. bassan@mail. huji. sajjiie. ac.il
ABSTRACT
Minimal sufficient reasons represent a prevalent form of explanation - the smallest subset of input features which, when held constant at their corresponding values, ensure that the prediction remains unchanged. Previous post-hoc methods attempt to obtain such explanations but face two main limitations: (i) Obtaining these subsets poses computational challenge, leading most scalable methods con- verge towards suboptimal, less meaningful subsets; (ii) These methods heavily rely on sampling of-distribution input assignments, potentially resulting in counterintuitive behaviors. To tackle these limitations, we propose in this work a self-supervised training approach, which we term sufficient subsel training (SST). Using SST, we train models to generate concise sufficient reasons for their predic- tions as an integral part of their output. Our results indicate that our framework produces succinct and faithful subsets substantially more efficiently than competing post-hoc methods, while maintaining comparable predictive performance. Code is available at: https: //tp://ggtttbbttt/ wwtpt///ttt//////////ttt ma in/ ICLR25
INTRODUCTION
Despite the widespread adoption of deep neural networks, understanding how they make decisions remains challenging. Initial attempts focused additive feature attribution methods (Ribeiro et al. (2016): Lunddbrg & Leee 2017);; (Sundararajan et al.) (2017)), which often treat the model's behavior as approximately linear around the input of interest. Á different line of techniques, such as An- chors (Ribeiro et al. (2018) and SIS (Carter et al. (019)), seek to pinpoint sufficient subsets of input features that ensure that prediction remains unchanged. Here, the goal often involves finding the smallest possible sufficient subset, which is typically assumed to provide a better interpreta- tion (Ribeiro al. (2016); Carter et al. I et al. (019); Barceló et al. (0200: Wäldchen
ct al. (2021)).
Building this foundation, we adopt the common notation of sufficient reason (Barceló al. (2020): Darwiche & Hirth (2020): /Arenas et al. (2022) to refer to any subset of input features S that ensures the prediction of classifier remains constant. We categorize previous approaches into three broad categories of sufficiency, namely: (i) baseline sufficient reasons, which involve setting the values of the complement 3 to a fixed baseline; (ii) probabilistic sufficient reasons, which entail sampling S from specified distribution; and (iii) robust sufficient reasons, which aim to confirm that the prediction does not change for any possible assignment of values to 5 within a certain domain.
Several methods have been proposed for obtaining sufficient reasons for ML classifiers (baseline. probabilistic, and robust) (Ribeiro al. (2018); Carter al. (2019): Ignatiev et al. (2019); Wang et al. (2021a): Chockler et al. (001)). These methods are typically post-hoc, meaning their purpose is to interpret the model's behavior after training. There are two major issues concerning such post-hoc approaches: (i) First, identifying cardinally minimal sufficient reasons in neural networks is computationally challenging (Barceló et al. (2000); Wäldchen et al. (202I)), making most methods either unscalable prone to suboptimal results. (ii) Second, when assessing if subset S is sufficient reason, host-hoc methods typically fix S's values and assign different values to the features of S. This mixing of values may result in out----dist (OOD) inputs, potentially misleading

---

Published as a conference paper at ICLR 2025
Original Image
SST (inherent)
class: "cat"
Anchors (post-hoc)
GS (post-hoc)
SIS (post-hoc)
An example of a sufficient reason generated by model trained with sufficient subset training (SST) on the IMAGENET dataset, compared those generated by post-hoc methods on standard-trained models. While explanations from Anchors and GS are larger, those from SIS are less faithful and lack subset sufficiency (details in the experiments in Section 55. SST generates explanations that are both concise and faithful, while performing this task with significantly improved efficiency. Additional examples appear appendix
Figure 1:
the evaluation of S's sufficiency. This issue has been identified as a significant challenge in such methods (Hase et al. (2021): Vafa et al. (202T): Yu et al. (2023); Amir et al. (2024)), frequently leading to the identification of subsets that do not align with human intuition (Hase et al. (202
Our contributions. We start by addressing the previously mentioned intractability and OOD concerns, reinforcing them with new computational complexity findings on the difficulty of generating such explanations: (i) First, we extend computational complexity results that were limited only to the binary setting (Barceló et al. (2020); Wäldchen et al. (202T) to any discrete or continuous domain, showcasing the intractability of obtaining cardinally minimal explanations for much more general setting; (ii) Secondly, we prove that the intractability of generating these explanations holds for different relaxed conditions, including obtaining cardinally minimal baseline sufficient reasons as well as approximating the size of cardinally minimal sufficient reasons. These results reinforce the computational intractability of obtaining this form of explanation in the classic post-hoc fashion.
Aiming to mitigate the intractability and OOD challenges, we propose a novel self-supervised approach named sufficient subset training (SST), designed inherently produce concise sufficient reasons for predictions in neural networks. SST trains models with two outputs: (i) the usual predictive output and (ii) an extra output that facilitates the extraction of sufficient reason for that prediction. The training integrates two additional optimization objectives: ensuring the extracted subset is sufficient concerning the predictive output and aiming for the subset to have minimal cardinality.
We integrate these objectives using dual propagation through the model, calculating two additional loss terms. The first, the faithfulness loss. validates that the chosen subset sufficiently determines the prediction. The second, the cardinality loss, aims to minimize the subset size. We employ various masking strategies during the second propagation to address three sufficiency types. These include setting 5 to constant baseline for baseline sufficient reasons, drawing S from a distribution for probabilistic sufficient reasons, using adversarial attack S for robust sufficient reasons.
Training models with SST reduces the need for complex post-hoc hoc computations and exposes models to relevant mixed inputs, thereby reducing the sensitivity of subsets to OOD instances. Moreover,
2

---

Published as a conference paper at ICLR 2025
method's versatility enables its across any neural network architecture. We validate SST by testing on multiple architectures for image and language classification tasks, using diverse masking criteria. We compare on standard (i.e., classification only) models. Our results show that SST produces sufficient reasons that are concise and faithful, more efficiently than post-hoc approaches, while preserving comparable predictive performance. Figure illustaates an example of sufficient reason generated by SST, in comparison post-hoc explanations.
saiiiing-geeratter explanations with those from popular post-hoc methods
2 FORMS OF SUFFICIENT REASONS
In this work, our focus is on local interpretations of classification models. Specifically, for a model f R" Re and input TRD, aim explain the prediction [xx). Formally, define a sufficient reason (Barceló ct al. (2020); Darwiche & Hirth (2020); Arenas et al. (2022) any subset of features S S [n]. such that fixing S their values in x. determines the prediction f(x). We specifically want the prediction (xss; zg) to align with f(x), where (xs:Zg) denotes an input for which the values of S are drawn from x E R" and the values of 5 are drawn from z E IR.. If S includes all input features, i.e., S = {L.... n. it is trivially sufficient. However, it is common to seek more concise sufficient reasons (Ribeiro et al. (2018); Carter et al. (2019); Ignatiev er al. (2019): Barceló er al.] (2020); Blanc et al. (2021); Wäldchen et al. (2021)). Another consideration the choice of values for the complement set S. We classify previous methods into three general categories:
Definition Given a model f. an instance x E I and some baseline z E R", we define S nL) baseline sufficient reason of (f,x) with respect to iff it holds that:
arg argmax f(xsizs), = arg max fxx);
(I)
The baseline z represents the "missingness" of the complementary set S, but its effectiveness, is highly dependent on choosing a specific z. While it feasible use small number of different baselines to mitigate this dependency, such approach is not practical across broader domains. However, in certain cases, employing baselines may be intuitive, especially when they carry specific significance in that scenario. For instance, in the context of language classification tasks where f represents transformer architecture, z could be assigned the widely recognized MASK token, which is utilized during pre-training phases address the concept of "missingness" in tokens (Devlin al. (2018)).
Conversely, sufficiency can imply that the values of S dictate the prediction, regardless of any assignment to S in some domain. This definition is particularly useful in cases where striet sufficiency of 5 is imperative, such as in safety-critical systems MMaques-Silvy & Ignatiev (2022);
[gnatiev et al. (2019); Wu al. (2024b)). There, the presence of any counterfactual assignment over S may be crucial. While in some instances the domain of 3 is unlimited (Ignatiev et al. (201)); Marques-Silve Silva Ignatiev (2022)), ), a more feasible modification is to consider limited continuous domain surrounding x (Wu et al. (2024b) La Malfa et al. (2021); Izza et al. (2024)). We define this kind sufficiency rationale as robust sufficient reasons:
Definition Given a model f and an instance x R", we define S f1, fl.....m n) as robust sufficient reason of (f. x) an Ey-norm ball B of radius ep iff it holds that:
Vz E Byr (x). [arg max f(xs; = arg max f(x),b
s. (x) (z Rd ||x 2/1p S {p)
However, it is not always necessary to assume that fixing the subset S guarantees a consistent prediction across an entire B5 (x) domain. Rather, when S is fixed, the classification may be maintained with a certain probability (Ribeiro et al. (2018); Blanc et al. (0021): Wäldchen et al. (2021); WWan et al. (2021a)). We refer to these probabilistic sufficient reasons. Under this framework, fixing S and sampling values from according to a given distribution ensures that the classification remains unchanged with a probability greater than - 6:
3

---

Published as a conference paper at ICLR 2025
Definition 3. Given model f and some distribution DD over the input features, define S - {I....,n] n as a probabilistic sufficient reason of (f,x) with respect to 'D iff:
Pr larg max f(z), = arg max f(x); Ls = xs] 21-8
(3)
2>D
where Xs denotes fixing the features of S in the vector z to their corresponding values in x.
PROBLEMS WITH POST-HOC MINIMAL SUFFICIENT REASON COMPUTATIONS
Intractability. Obtaining cardinally minimal sufficient reasons is known be computationally challenging (Barceló et al. 20200; Wäldchen et [ (202T), particularly in neural netowrks (Barceló al. (2020); Adolfi al. (2024); Bassan al. (2024). Two key factors influence this computational challenge - the first is finding a cardinally minimal sufficient reason, which may be intractable when the input space is large. This tractability barrier common all of the previous forms of sufficiency (baseline, probabilistic, and robust). A second computational challenge can emerge when verifying the sufficiency of even a single subset proves to be computationally difficult. For instance, in robust sufficient reasons, confirming subset sufficiency equates to robustness verification, a process that by itself is computationally challenging (Katz al. (2017): (ääzzr & Langel (202T)) The intractability of obtaining cardinally minimal sufficient reasons is further exemplified by the following theorem:
Theorem 1. Given neural network classifier f with ReLU activations and RR", obtaining cardinally minimal sufficient reason for (f.x) is (i) NP- uP-Complete for baseline sufficient reasons (ii) EP Complete for robust sufficient reasons and (iii) NP .Hard for probabilistic sufficient reasons.
The highly intractable complexity class Σn encompasses problems solvable in NP time with constant- time access coNP oracle, whereas NP includes problems solvable in NP time with constant-ting access to probabilistic PP oracle. More details on these classes are available in Appendix B For our purposes, it suffices to understand that NP ç Ei and NP & NpPP is widely accepted (Arora & Barak (2009), highlighting their substantial intractability (problems that are significantly harder than NP-Complete problems).
Proof sketch. The full proof is relegated to Appendix C We begin by extending the complexity results for robust and probabilistic sufficient reasons provided by (Barceló et al. (2020); Wäldchen et al. (2021)), which focused on either CNF classifiers or multi-layer perceptrons with binary inputs and outputs. We provide complexity proofs for a more general setting considering neural networks over any discrete continuous input or output domains. Membership outcomes to continuous domains stem from realizing that instead of guessing certificate assignments for binary inputs, one can guess the activation status of any ReLU constraint. For hardness, we perform a technical reduction that constructs neural network with a strictly stronger subset sufficiency. We also provide a novel complexity proof, which indicates the intractability of the relaxed version of computing cardinally minimal baseline sufficient reasons, via a reduction from the classic CNF-SAT problem.
To further emphasize the hardness of the previous results, we prove that their approximation re- mains intractable. We establish this through approximation-present Implicant-Cone Core (Umans (1999)) and Max-Clique (Håstad (1999h) problems (proofs provided in Appendix D):
reductions from the Shortest-
Theorem 2. Given neural network f with ReLU activations and x E IR", (i) Ve approximating cardinally minimal robust sufficient reasons with n factor is Σlf -Hard, (ū) de approximating cardinally minimal probabilistic or baseline sufficient reasons with factor n l-c is -ard.
These theoretical limitations highlight the challenges associated with achieving exact computations or approximations and do not directly apply to the practical execution time of methods that employ heuristic approximations. Nevertheless, many such methods, including Anchors (Ribeiro al. (2018) and SIS (Carter et al. (2019), face issues with scalability and often rely on significant assumptions. For instance, these methods may substantially reduce the input size to improve the tractability of features (Ribeiro et al.] (2018); Carter et al. (2019)) or concentrate on cases with a large margin between the predicted class's 's output probability and that of other classes (Carter al. (2019). )
Sensitivity to OOD counterfactuals. Methods computing concise sufficient reasons often use algorithms that iteratively test inputs of the form (xs;25), comparing the prediction of (x3;23)
4

---

Published as a conference paper at ICLR 2025
with fx) to determine S's sufficiency (Ribeiro al. (2018) Carter al. (2019 Chockler et al. (2021)) ). A key issue is that (xg:Zg) might be OOD for f. potentially misjudging S's sufficiency. Iterative approaches aimed at finding cardinally minimal subsets may exacerbate this phenomenon, leading to significantly suboptimal or insufficient subsets. A few recent studies focused on NLP domains (Hase et al. (202T): Vafa et al. (202T)), aimed enhance model robustness to OOD counterfactuals by arbitrarily selecting subsets S and exposing models to inputs of the form (x5;25) during training. However, this arbitrary masking process lacks clarity on two important questions (i) which features should be masked, and (ii) how many features should be masked This, in turn, poses a risk of inadvertently masking critical features and potentially impairing model performance.
SELF-EXPLAINING NEURAL NETWORKS WITH SUFFICIENT REASONS
To address the earlier concerns, train self-explaining neural networks that inherently provide concise sufficient reasons along with their predictions. This eliminates the need for costly post- computations and has the benefit of exposing models to OOD counterfactuals during training.
4.1 LEARNING MINIMAL SUPFICIENT REASONS
Our model is trained to produce two outputs: the initial prediction and an explanation vector that pinpoints concise sufficient reason for that prediction. Each element the vector corresponds to a feature. Through a Sigmoid output layer, we select a feature subset S where outputs surpass a threshold More formally, we learn some: h Rn R x [0, 1]" where for simplicity we denote: h(x) := (hą (x), f22 (x)), for which hı denotes the prediction component and h2. derived from final Sigmoid layer, denotes the explanation component; both share the same hidden layers. The sufficient reason is taken by identifying S == {i (x); 2 7. To ensure S is sufficient, we perform a dual propagation through h, wherein the second forward pass, a new masked input is constructed by fixing the features in S to their values in x and letting the features in S take some other values z. The masked input (Xs; zg) is then propagated through This process is illustrated in Figure]
alyarn (be (5, urgmax, k0,
0Lcora (10l)
(x)
Suf ficient recson: $
Jeput (Xg)
hg (x,:z;)
Inputt x
Musking
hidder layers
hidden layers
(x)
Oh (1).
dw
Figure 2: An illustration of the dual propagation incorporated during sufficient subset training
Besides the prediction task, optimize additional objectives ensure that S is both sufficient and concise. Our training incorporates three distinct loss terms: (i) the prediction loss, Lypreds (ii) a faithfulness loss, Lfathh, enhancing the sufficiency of concerning (h1, x). and cardinality loss, Loard, minimizing the size of S. We optimize these by minimizing the combined loss:
(h) = (h) + Ao (h) + & Leara(h))
(4)
Here, we use the standard cross entropy (CE) loss as our prediction loss. i.e., Lpred(h) := Leg(h, t), where t is the ground truth for We use CE also in the faithfulness loss, which ensures the sufficiency of S by way of minimizing the discrepancy between the predicted probabilities of the masked input hy (x5; zg) and the first prediction hy (x):
5

---

Published as a conference paper at ICLR 2025
faith (h) == LC arg max h1 (x)j), s.t. 5: {i h2(x); 2 2
Training a model solely to optimize prediction accuracy and faithfulness may often result in larger sufficient reasons, as larger subsets are more likely to sufficient. Specifically, the largest subset S : (1....... f2, n always qualifies sufficient, irrespective of the model or instance. Conversely, excessively small subsets may compromise prediction performance, leading to a bias towards larger subsets when these are the only objectives considered.
Hence, to train our model to produce concise sufficient reasons, we must include a third optimization objective aimed at minimizing the size of S. We incorporate this by implementing cardinality loss which encourages the sparsity of S. by utilising the standard Lj loss, ie., Leara(h) == ||/2(x)]]-
4.2 MASKING
As noted earlier, during the model's second propagation phase, a masked input (xs; is processed by our model's prediction layer h1. The faithfulness loss aims to align the prediction of h1 (xs;zş) closely with hi (x). A key question remains on how to select the values for the complementary features S. We propose several masking methods that correspond the different forms of sufficiency:
1. Baseline Masking. Given a fixed baseline E RR, we the features of S to their corresponding values in and propagate h1 (xs; zz), optimizing S to constitute baseline sufficient reason with respect to z.
2. Probabilistic Masking. Given some distribution D, sample the corresponding as- signments from D(z|zs = xs) and propagate h1 (xs: optimizing S to constitute as probabilistic sufficient reason concerning D.
3. Robust Masking. To ensure the sufficiency of S across the entire input range of B (x), we conduct an adversarial attack on x. Here, we fix the values of S and perturb only the features in 3. This approach involves identifying the "hardest" instances, denoted by B (xs: zg). and optimizing the prediction of hı (X'gizz) to assimilate that of and updating it over projected gradient descent (PGD) steps (Madry et al. (2017))
(Xgizz) Zgzzz)
by (x). We achieve this by initially setting (Xs; Zg)u randomly within
(6) where is the step size, and 11 is the projection operator. This process is similar to adversarial training (Shafahi et al. (201)), with the difference of not perturbing the features in S.
(xs: II (Xs: a sign (xx73) Lpred (h (XSi
EXPERIMENTS
We assess SST across image and language classification tasks, comparing the sufficient reasons generated by our approach to those from state-of the-art post-hoc methods. Following common conventions (Wu et al. (2024b); Ignatiev et al. (2019); Bassan & Katz (2023)) ). we evaluate these subsets on three metrics: (i) the mean time taken to generate a sufficient reason, (ii) the mean size of the sufficient reasons, and (iii) the mean faithfulness, i.e., how sufficient the subsets are. Particularly, when evaluating faithfulness, we categorize the results into three distinct types of sufficiency: baseline, probabilistic, and robust faithfulness. Each category measures the proportion of test instances where the derived subset remains sufficient under baseline, probabilistic, or robust masking.
5.1 SUFFICIENT SUBSET TRAINING FOR IMAGES
We train SST-based models on three prominent image classification tasks: MNIST (Deng (01 digit recognition using feed-forward neural network. CIFAR- 10 (Krizhevsky et al. (2009) using Resnet18 (He et al. (2016)) and IMAGENET using a pre-trained Resnet50 model (He et al. (2016)). To simplify the training process, set the threshold
0.5 and the faithfulness coefficient at 1, conducting the grid search exclusively over the cardinality coefficient ç. Full training details can be found in Appendix E We assess the inherent sufficient reasons generated by SST and

---

Published as a conference paper at ICLR 2025
compare them with those from coanndrrd-triinee models using post-hoc methods: Anchors (Ribeiro) jet al. (2018), SIS (Carter et al. (2019)), and a vision-based technique (Fong & Vedaldi (2017) which term gradient search (GS).
Robust Sufficient Reasons in Images. In image classification tasks, is common to evaluate the robust sufficiency of the identified sufficient reasons, by ensuring they remain sufficient across continuous domain (Wu et al.] (2024b) Ignatiev et al. (2019); 9); Bassan Katz (2023)). We aim to explore the ability of SST-based models to generate such subsets, initially training all models using robust masking with a PGD & (e 0.12) attack on the features in S, as described in section 4.2 Further details on the selection these results against subsets produced by the aforementioned post-hoc methods over standard-trained models (i.e., with only prediction output, and no explanation) and examine their capacity uphold robust sufficiency. Figure 3 illustrates visualizations of these results, while Table [ provides summary of the empirical evaluations.
0.12 can be found Appendix [ We subsequently assess
Table 1: SST with robust masking vs. post-hoc methods. Results depict average explanation size (%) 10-minute timeouts (%), average time (seconds), and robust faithfulness (%)
MNIST
CIFAR-I0
IMAGENET
Size
T/O
Time
Faith.
Size
T/O
Time
Faith.
Size
T/O
Time
Faith.
Anchors
8.98
0
0.11
97.51
20.88
86.47
20.29
1.09
118.6
88.94
SIS
2.35
0
4.34
98.08
0.87
0.14
195.25
84.64
0.15
0
262.42
77.32
GS
40.36
0
1.13
97.56
60.7
14.61
92.41
78.97
266.5
90,92
SST
1.42
0
#10 6
99.28
12.99
1=
90.43
0.46
Rs R=10
80.88
Originial Image
Anchors
GS
Figure 3: Examples of sufficient reasons produced by SST compared to the ones generated by post- hoc approaches for MNIST, CIFAR- 10, and IMAGENET. Additional examples appear in appendix [
Results in Table|[indicate that across all configurations, SST generated explanations with substantially greater efficiency than post-hoc methods. SST typically produced smaller explanations, especially in all comparisons with GS and Anchors, and in MNIST against SIS. Additionally, SST explanations often demonstrated greater faithfulness, notably MNIST against all post-hoc methods, and in CIFAR- 10 compared to Anchors and SIS. Typically, SIS offered concise subsets but at the cost of low faithfulness, while GS provided faithful explanations that were considerably larger. Anchors yielded more consistent explanations, yet they were often either significantly larger or less faithful compared
7

---

Published as a conference paper at ICLR 2025
to SST. Separately, concerning the accuracy shift for SST, MNIST showed minor increase of 0.15%, whereas CIFAR-10 1- experienced a decrease of 1.96%, and IMAGENET saw a reduction of 4.7%. Of course, by reducing the impact of the cardinality and faithfulness loss coefficients, one maintain accuracy on all benchmarks, but this may compromise the quality of the explanations.
Different Masking Strategies for images. We aim analyze different masking strategies for SST in image classification, focusing on MNIST. We utilize two additional masking methods: probabilistic masking, where the assignments of features in the complement S sampled from a uniform distribution to enhance probabilistic faithfulness, and baseline masking, where all the features in S set to zero (using the trivial baseline == 0,)), hence optimizing baseline faithfulness. This specific baseline is intuitive in MNIST due to the inherently zeroed-ou border of the images. We compare these approaches to the same post-hoc methods as before, evaluating them based on their baseline, probabilistic, or robust faithfulness, and present these results in Table 2
Table 2: SST (different masks) vs. post-hoc methods: Mean explanation size (%), accuracy gain (%), mean inference time (seconds), and baseline, probabilistic, and robust faithfulness (%).
Masking
Size
Acc. Gain
Time
Faithfulness Probabilistic
Robust
Baseline
Anchors
8,98
0.11
97.51
91.06
16.06
SIS
2.35
4.34
98.08
90.72
46.1
GS
40.36
1.13
97.56
94.11
16.72
robust
1.42
+0.15
110 6
99.28
SST
baseline
23.69
-1.26
110
96.52
probabilistic 0.65
+0.36
100
99.11
Results in Table demonstrate the impact of SST with various masking strategies. Each strategy improved compared to post-hoc methods in its respective faithfulness measure. Robust and prob- abilistic masking strategies produced very small subsets and even slightly increased accuracy. In contrast, the baseline masking strategy resulted in larger subsets and a larger accuracy drop. This likely occurs because setting the complement S to fixed baseline strongly biases the model towards OOD instances, whereas uniform sampling or a bounded e-attack are less prone to this issue.
Cowuuunnss--ardinalln Trade-off. Optimizing models trained with SST involves a trade-off between two primary factors: (i) the size of the generated sub- set and (ii) the faithfulness of the model. For instance, full set explanation (S := {1,.... n1)) scores low terms of the optimization for small subset sizes but empty set explanation (S : 0) achieves the best score for subset size due to its minimal cardinality but gener- ally exhibits poor faithfulness.
Putthfiiness
Cardinatity
1.0
Postiiituee (ime)
0.8
0.0
guarantees perfect faithfulness. Conversely,
our experiment, aim to illustrate this trade-off, which can be bal- anced by altering the cardinality loss coefficient g. Greater values emphasize the subset size loss com- ponent, leading to smaller subsets at the cost of their faithfulness. Conversely, smaller & values reduce the component's 's impact, resulting in larger subsets with better faithfulness. Figure 4 provides a comparative analysis of this dynamic using the MNIST dataset with baseline masking. For greater & values, the car- 0, the
20-11
30-13
10-11
13mm
Dartlmality Zane /Seffficten E (Eng Scale)
Figure 4: The faithfulness-cardinnltty tradeoff in baseline-masking SST models for MNIST with varying cardinality loss coefficients, shows that higher increases mask size S but reduces faithfulness, and vice versa.
dinality of the mask is maximal. As explanation size converges to 50% of the input. We believe this happens because the threshold is set to the default value of 7 0.5 (see Appendix El for more details). resulting in the arbitrary selection of a 50% sufficient subset due to random initialization at the beginning of training. This subset is likely sufficient determine the prediction its (as demonstrated in Table even 23.69% of
8

---

Published as a conference paper at ICLR 2025
the imput may be sufficient for prediction). Consequently, the cardinality loss coefficient gets very close to zero, the parameters of the explanation component (i.e., h2, as discussed in Section remain nearly unchanged throughout training, with the explanation size fixed 50%.
5.2 SUFFICIENT SUBSET TRAINING FOR LANGUAGE
Table 3: Baseline/probabblistic SST (B-SST, P-SST) vs. post-hoc techniques: Mean inference time (seconds), 10-minute timeouts (%), mcan explanation size (%), and probabilistic and baseline faithfulness (%)
IMDB
SNLI
Time
T/O
Size
P-Faith.
B-Faith.
Time
T/O
Size
P-Faith.
B-Faith.
Anchors
22.42
20.05
1.12
89.1
39.6
94.78
3.6
10
35.24
40.24
S-Anchors
19.65
12.26
1.16
89.14
23.37
160.92
9.76
18
28.55
33.94
SIS
14.9
0
22.57
88.97
97.89
23.13
0
12.74
44.84
49.29
B-SST
R=0
0
28.96
98.05
R10
0
39
95.88
P-SST
1:10
0
49.7
95.67
110
0
53.69
95.35
We assess our results using two prevalent language classification tasks: IMDB sentiment analy- sis (Maas et al.] (20TT) and SNLI (Bowman et al. (2015)). All models are trained over BERT base (Devlin et al. (2018)). We implement two typical masking strategies for testing sufficiency in language classification (H (Hase al. (202T): Vafa et al. (202T): ): (i) using the pre-trained MASK token from BERT (Devlin et al. (2018)) as our baseline (baseline masking) and (ii) randomly sampling features uniformly (probabilistic masking). We evaluate the performance of SST- ---genrrttedd subsets against post-hoc explanations provided by either Anchors or SIS. In the Anchors library, additional method assesses sufficiency for text domains by sampling words similar to those masked, leading us to two distinct configurations which denote as: Anchors and Similarity-Auclar
(S-Anchors).
that in the language setting, similarly to vision, SST obtains explanations much more efficiently than post-hoc methods. Although SST produces larger subsets than post-hoc methods, these subsets are significantly more faithful. For instance, SST achieves baseline faithfulness of 98.05% on IMDB, compared only 23% for S-Anchors. The convergence of SST towards larger subsets likely stems from our optimization of both faithfulness and minimal subset cardinality, Increasing the cardinality loss coefficient may yield smaller subsets but could decrease faithfulness. Separately, SST maintained comparable accuracy levels for both of these tasks the decrease in accuracy for IMDB was 0.87% and 0. 0.89% with probabilistic and baseline masking, respectively. For SNLI, probabilistic masking resulted in 0.61% drop, whereas baseline masking saw smaller decrease of 0.32%.
Cassline-Sufffciene (negative): found this movie really hard ... wandering off the tv ... Don't bother with it.
Probabilistic Suuuliiitti-Sfffiiinny (negative):
found this movie realfy hand wandering off the
Figure 5: Explanations generated by SST using baseline vs. probabilistic masking. When each token in the complement S is replaced with the MASK token, the prediction stays negative. In the probabilistic setting, the prediction remains negative when values from S are randomly sampled. Further examples can be found in Appendix
Explanations generated using probabilistic masking were larger on average compared to those generated using baseline masking. This is likely because random token perturbations present more challenging constraint than fixing the MASK token. Figure 3 illlustrras two explanations produced by SST using probabilistic or baseline masking for IMDB. Although both are intuitive, the baseline sufficient reason suffices by fixing only specific relevant terms like "don't 't" and "off", These terms are enough to preserve the negative classification when all other tokens are fixed to the MASK token. However, the probabilistic subset has larger negating phrases like "wandering off the TV" or "really hard" because it involves random perturbations of the complementary set, which may potentially shift the classification positive.

---

Published as a conference paper at ICLR 2025
6 RELATED WORK
Post-hoc sufficient reason techniques. Some common post-hoc approaches include An- chors (Ribeiro et al. (2018)), or SIS (Carter et al. (2019)) and typically seek to obtain concise subsets which uphold probabilistic sufficiency (Wang et al. (2021a); Ribeiro et al. (2018); Blanc al. (202T) baseline sufficiency (Hase et al. (202T) Chockler al. (202T: De Young al. (2019)) A different set of works is dedicated to obtaining robust sufficient reasons, where sufficiency determined for some entire discrete or continuous domain. These are often termed abductive
explanations (Igmatiev et al. (219);; Bassan et al. (2023)) or prime implicants (Ignatiev et al. (2019);
Shih et al. (2018)). Due to the complexity of producing such explanations, they are commonly obtained on simpler model types, such as decision trees (Izza et al. (2020), tree ensembles (Izza
& Marques-Sine Silva (202I): [gnatiev et al. (2022)) linear models (Marques-Silva et al. (2020). or
small-scale neural networks (Ignatiev et al. (2019); La Malfa et al. (2021) Bassan & Katz (023)).
Self-explaining neural networks. Unlike post-hoc methods, some techniques modify training to improve explanations (Ismail et al. (2021); Chen et al. (2019b); Hase et al. (2021); Vafa et al.
(202 Yan & Wang (2023)) or develop self-explaining models that inherently provide interpretations
for their decisions. Self-explaining models typically provide inherent additive feature altributions, assigning importance weights to individual or high-level features. For example, [Chen et al. (2019a)
and [Wang & Wang (202I) describe model outputs by comparing them relevant "prototypes" while Alvarez Melis & Jaakkola (2018) derive concept coefficients from feature transformations.
Other approaches, like those by Aggawal et al. (202T) and Jain al. (020), focus feature-specific neural networks or apply classifiers to snippets for NLP explanations, respectively. Kohh et al. (2020)
predict outcomes based on high-level concepts. Due to their focus on additive attributions, these methods generally operate under the implicit or explicit assumption that the model's behavior can be approximated as linear under certain conditions (Yeh et al. (2019): : Lundberg & Lee (2017)). This assumption is crucial as it underpins the approach of decomposing model's output into independent, additive contributions from individual features, and may hence overlook nonlinear interactions among features (Slack et al. (2020); Ribeiro al. (2018); Ych et al. (2019)). In contrast, we propose self-explaming framework that provides a distinct form of explanation - sufficient reasons for predictions which do not depend on assumptions of underlying linearity (Ribeiro et al. (2018)) To our knowledge, this is the first self-explaining framework designed to generate such explanations.
7 LIMITATIONS
A primary limitation of SST is the need to tune additional hyperparameters due to multiple op- timization objectives. We simplified this by conducting grid search solely over the cardinality loss coefficient& Ç, as detailed in Appendix [+ Additionally, the dual-propagation training phase is twice more computationally demanding than standard training, and this complexity escalates with challenging masking strategies, such as robust masking (see Appendix for more details). However, this investment training reduces the need for complex post-training computations, as highlighted in Section Lastly. overly optimizing our interpretability constraints can sometimes reduce predictive accuracy. Our experiments showed this was true for IMAGENET, though all other benchmarks retained comparable accuracy levels (within 2%, and under 1% for all tagguage-mode benchmarks). Interestingly, accuracy even improved under some configurations for MNIST classification. Future research endeavors could further investigate the conditions under which SST can be utilized not only for its inherent explanations but also to enhance predictive accuracy.
8 CONCLUSION
Obtaining (post-hoc) minimal sufficient reasons a sought-after method of explainability. However, these explanations are challenging to compute in practice because of the computationally intensive processes and heavy dependence on OOD assignments. We further analyze these concerns and propose framework to address them through sufficient subset training (SST). SST generates small sufficient reasons as an inherent output of neural networks with an optimization goal of producing subsets that are both sufficient and concise. Results indicate that, relative post-hoc methods, SST provides explanations that are consistently smaller or more faithful (or both) across different models and domains, with significantly greater efficiency, while preserving comparable predictive accuracy.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This research was funded by the European Union's Horizon Research and Innovation Programme under grant agreement No. 101094905 (AI4GOV). We also extend our sincere thanks to Guy Amit, Liat Ein Dor, and Beat Buesser from IBM Research for their valuable discussions.
REFERENCES
Sravanti Addepalli, Samyak Jain, Gaurang Sriramanan, and Venkatesh Babu. Scaling Adversarial Training to Large Perturbation Bounds. In European Conference on Computer Vision, pp. 301-316. Springer, 2022.
Federico Adolfi, Martina G Vilas, and Todd Wareham. The Computational Complexity of Circuit Discovery for Inner Interpretability. arXiv preprint arXiv:2410.08025, 2024.
Rishabh Agarwal, Levi Melnick, Nicholas Frosst, Xuezhou Zhang, Ben Lengerich, Rich Caruana, and Geoffrey E Hinton. Neural Additive Models: Interpretable Machine Learning with Neural Nets. Advances in neural information processing systems, 14:4699-47111 2021.
David Alvarez Melis and Tommi Jaakkola. Towards Robust Interpretability with Self-Explaining Neural Networks, Advances in neural information processing systems, 31, 2018.
Guy Amir, Shahaf Bassan, and Guy Katz. Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation. arXiv preprint arXiv:2408. 03915, 2024.
Marcelo Arenas, Pablo Barceló, Miguel Romero Orth, and Bernardo Subercaseaux. On Computing Probabilistic Explanations for Decision Trees. Advances in Neural Information Processing Systems, 35:28695-2877 28707, 2022.
S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
Gilles Audemard. Steve Bellart, Louenas Bounia, Frédéric Koriche, Tean-Marie Lagniez, and Pierre Marquis. On the Computational Intelligibility of Boolean Classifiers. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 18. pp. 74-84--8 14-86,222 2021.
Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis. On Preferred Abductive Explanations for Decision Trees and Random Forests. In Thirty-First International Joint Conference Artificial Intelligence (ICCAI-22), pp. 643-650. International Joint Conferences on Artificial Intelligence Organization, 2022a.
Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis. Trading Complexity for Sparsity in Random Forest Explanations. Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 5461-5469, 2022b.
Pablo Barceló, Mikaël Monet, Jorge Pérez, and Bernardo Subercaseaux. Model Interpretability through the Lens of Computational Complexity. Advances in neural information processing systems, 33:1 13:15487-15448, 2020.
Pablo Barceló, Alexander Kozachinskiy, Miguel Romero Orth, Bernaroo Subercaseaux, and José Verschae. Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. arXiv preprint arXiv:2501.0600 066078 2025.
Shahaf Bassan and Guy Katz. Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks. In International Conference Tools and Algorithms for the Construction and Analysis of Systems, pp. 187-207. Springer, 2023.
Shahaf Bassan, Guy Amir, Davide Corsi, Idan Refacli, and Guy Katz. Formally Explaining Neural Networks within Reactive Systems. In 2023 Formal Methods in Computer Design (FMCAD), pp. 1-13. IEEF, 2023.
11

---

Published as a conference paper at ICLR 2025
Shahaf Bassan, Guy Amir, and Guy Katz. Local vs. Global Interpretabilityy: A Computational Complexity Perspective. In Forty- first International Conference on Machine Learning, 2024.
Guy Blanc, Jane Lange, and Li- YinY Tan. Provably Efficient, Succinct, and Precise Explanations. Advances in Neural Information Processing Systems, 34:6129-6141, 2021.
Paul J Blazek and Milo M Lin. Explainable Neural Networks that Simulate Reasoning. Nature Computational Science, 1(9):60--618, 2021.
Ryma Boumazouza, Fahima Cheikh-Alili, Bertrand Mazure, and Karim Tabia. ASTERYX: A model- Agnostic SaT-basEd appRoach for symbolic and score-based explanations. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 120-129, 2021.
Louenas Bounia and Frederic Koriche. Approximating Probabilistic Explanations via Supermodular Minimization. In Uncertainty in Artificial Intelligence, pp. 216-225, PMLR, 2023.
Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A Large Annotated Corpus for Learning Natural Language Inference. arXiv preprint arXiv:
2015.
Brandon Carter, Jonas Mueller, Siddhartha Jain, and David Gifford. What Made You Do This? Understanding Black-Box Decisions with Sufficient Input Subsets. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 567-576. PMLR, 2019.
Chaofan Chen, Oscar Li, Daniel Tao, Alina Barnett, Cynthia Rudin, and Jonathan K Su. This Looks Like That: Deep Learning for Interpretable Image Recognition, Advances in neural information processing systems, 32, 2019a.
Jiefeng Chen, Xi Wu, Vaibhav Rastogi, Yingyu Liang, and Somesh Jha. Robust Attribution Regular- ization. Advances in Neural Information Processing Systems, 32, 2019b.
Hana Chockler and Joseph Y Halpern. Explaining Image Classifiers. arXiv preprint ariiv:2401.173777 2024.
Hana Chockler, Daniel Kroening, and Youcheng Sun. Explanations for Occluded Images. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1234-1243, 2021.
Hana Chockler, David Kelly, Daniel Kroening, and Youcheng Sun. Causal Explanations for Image Classifiers. arXiv preprint arXiv:2411.08875 2024.
Martin C Cooper and João Marques-Silva. Tractability of Explaining Classifier Decisions. Artificial Intelligence, 316:10384) 2023.
Adnan Darwiche and Auguste Hirth. On the Reasons Behind Decisions. In ECA/ 2020, pp. 712-720. IOS Press, 2020.
Adnan Darwiche and Pierre Marquis. On Quantifying Literals in Boolean Logic and its Applications to Explainable AL. Journal of Artificial Intelligence Research, 72:285-328, 2021.
Li Deng. The mnist Database of Handwritten Digit Images for Machine Learning Research [best of the web]. IEEE signal processing magazine, 19(6):141-1444 2012.
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- Tre-Training of Deep Bidirectional Transformers for Language Understanding. arXiv preprint htt.:1880.04805. 2018.
Jay Young Sarthak Jain, Nazneen Fatema Rajani, Erie Lehman, Caiming Xiong, Richard Socher, and Byron C Wallace. ERASER: A Benchmark Evaluate Rationalized NLP Models. arXiv preprint arXiv:1911.03429, 2019.
Ouns El Harzli, Bernardo Cuenca Grau, and Ian Horrocks. Cardinality-mnnimal minimal Explanations for Monotonic Neural Networks. In Proceedings of the Thirty-Secone International Joint Conference Artificial Intelligence, pp. 3677-3685, 2023.
12

---

Trade-off. Advances in Neural Published as a conference paper at ICLR 2025
Mateo Espinosa Zarlenga, Pietro Barbiero, Gabriele Ciravegna, Giuseppe Marra, Francesco Giannini, Michelangelo Diligenti, Zohreh Shams, Frederic Precioso, Stefano Melacci, Adrian Weller, et al. Concept Embedding Models: Beyond the Eccuracy-Explainatee Information Processing Systems, 35:21400-21413, 2022.
Thomas Fel, Mélanie Ducoffe, David Vigouroux, Rémi Cadène, Mikael Capelle, Claire Nicodème. and Thomas Serre. Don't Lie to Me! Robust and Efficient Explainability with Verified Pertur- bation Analysis. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16153- 16163, 2023.
Ruth C Fong and Andrea Vedaldi. Interpretable Explanations of Black Boxes by Meaningful Perturbation. In Proceedings of the IEEE international conference computer vision, pp. 3429 3437, 2017.
Hangzhi Guo, Thanh H Nguyen, and Amulya Yadav. Counternet: End-to-Br Training of Prediction Aware Counterfactual Explanations. In Proceedings of the 29th ACM SICKDD Conference on Knowledge Discovery and Data Mining, pp. 577-589, 2023.
Victor Guyomard, Françoise Fessant, Thomas Guyet, Tassadit Bouadi, and Alexandre Termier. VCNet: A Self-Explaining Model for Realistic Counterfactual Generation. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 437-453. Springer, 2022.
Joseph Y Halpern. Actual Causality. MiT Press, 2016.
Peter Hase, Harry Xie, and Mohit Bansal. The Out-of-Distrrbuut Problem in Explainability and Search Methods for Feature Importance Explanations. Advances in neural information processing systems, 34:3650-3666 2021.
Johan Håstad. Clique is Hard to Approximate within n/sup 1-/spl epsiv. 1999.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Dat Hong, Tong Wang, and Stephen Baek. Protorynee-interpreaable Text Classification via Prototype Trajectories. Journal of Machine Learning Research, 24(264):1-39, 2023.
Xuanxiang Huang, Yacine Izza, Alexey Ignatiev, and Joao Marques-Silva. On Efficiently Explaining Graph-Based Classifiers. In International Conference the Principles of Knowledge Representa- fion and Reasoning 2021, pp. 356-367. Association for the Advancement of Artificial Intelligence (AAAI), 2021.
Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silvaa Abduction-based Explanations for Machine Learning Models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1511-1519, 2019.
Alexey Ignatiev, Yacine Izza, Peter Stuckey, and Joao Marques-Sine Silla. Using MaxSAT for Efficient Explanations of Tree Ensembles. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3776-3785, 2022.
Aya Abdelsalam Ismail, Hector Corrada Bravo, and Soheil Feizi. Improving Deep Learning Inter- pretability by Saliency Guided Training. Advances in Neural Information Processing Systems, 34: 66726-26739, 2021.
Yacine Izza and Joao Marques-Silva. On Explaining Random Forests with SAT. In 30th International Join! Conference on Artificial Intelligence (IJCAI 2021). International Joint Conferences on Artifical Intelligence (UCAI), 2021.
Yacine Izza, Alexey Ignatiev, and Joao Marques-Sile Silva. On Explaining Decision Trees. arXiv preprint arXiv:2010. 1034, 2020.
13

---

Published as a conference paper at ICLR 2025
Yacine Izza, Xuanxiang Huang, Antonio Morgado, Jordi Planes, Alexey Ignatiev, and Joao Marques- Silva. Restriced Explanations: Theoretical Underpinnings & Efficient Implementation. arXiv preprint arXhv:2405.08299 2024.
Sarthak Jain, Sarah Wiegreffe, Yuval Pinter, and Byron C Wallace. Learning to Faithfully Rationalize by Construction. arXiv preprint arXiv:2005.00115. 2020.
Neil Jethani, Mukund Sudarshan, Yindalon Aphinyanaphongs, and Rajesh Ranganath. Have We Learned to Explain?: How Interpretability Methods can Learn to Encode Predictions in their Interpretations. In International Conference Artificial Intelligence and Statistics, pp. 1459- 1467. PMLR, 2021.
Yang Ji, Ying Sun, Yuting Zhang, Zhigaoyuan Wang, Yuanxin Zhuang, Zheng Gong, Dazhong Shen, Chuan Qin, Hengshu Zhu, and Hui Xiong. A Comprehensive Survey on Self-Interpretable Neural Networks. arXiv preprint arXiv:2501. 15638, 2025.
Xiangjian Jiang, Andrei Margeloiu, Nikola Simidjievski. and Mateja Jamnik. ProtoGate: Prototype- based Neural Networks with Global-to- Loball Feature Selection for Tabular Biomedical Data. In Proceedings of the 41st International Conference Machine Learning, pp.
2024.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. In Computer Aided Verification: 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I 30, pp. 97-117. Springer, 2017.
David A Kelly, Hana Chockler, Daniel Kroening, Nathan Blake, Aditi Ramaswamy, Melane Navarat- narajah, and Aaditya Shivakumar. You Only Explain Once. arXiv preprint arXiv:2311110811, 2023.
Monish Keswani, Sriranjani Ramakrishnan, Nishant Reddy, and Vineeth N Balasubramanian. Proto2Proto: Can you Recognize the Car, the Way I Do? In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10233-10243) 2022.
Eunji Kim, Dahuin Jung, Sangha Park, Siwon Kim, and Sungroh Yoon. Probabilistic Concept Bottleneck Models. In International Conference on Machine Learning, pp. 16521-16540. PMLR, 2023.
Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept Bottleneck Models. In International conference on machine learning, pp. 5338-5348. PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers of Features from Tiny Images. 2009.
Emanuele La Malfa, Agnieszka Zbrzezny, Rhiannon Michelmore, Nicola Paoletti, and Marta Kwiatkowska. On Guaranteed Optimal Robust Explanations for NLP Models. arXiv preprint 10Xi:22005.03640, 2021.
Seungeon Lee, Xiting Wang, Sungwon Han, Xiaoyuan Yi, Xing Xie, and Meeyoung Cha. Self- Explaining Deep Models with Logic Rule Reasoning. Advances in Neural Information Processing Systems, 35:3203-3216, 2022.
Ismael Lemhadri, Feng Ruan, Louis Abraham, and Robert Tibshirani. Lassonet: A Neural Network with Feature Sparsity. Journal of Machine Learning Research, 22(127):1-29, 2021.
Scott M Lundberg and Su-In Lee, A Unified Approach to Interpreting Model Predictions. Advances in neural information processing systems, 30, 2017.
Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning Word Vectors for Sentiment Analysis. In Proceedings of the 49th anmual meeting of the association for computational linguisties: Human language technologies, pp. 142-150, 2011.
14

---

Published as a conference paper at ICLR 2025
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks, arXiv preprint vrXiv:1706.06082 2017.
Emanuele Marconato, Andrea Passerini, and Stefano Teso. Glancenets: Interpretable, Leak-Proof concept-based Models. Advances in Neural Information Processing Systems, 35:21212-212277, 2022.
Joao Marques-Silva. Logic-based Explainability in Machine Learning. In Reasoning Web. Causal- ity. Explanations and Declarative Knowledge: 18th International Summer School 2022, Berlin, Germany, September 27-30, 2022, Tutorial Lectures, pp. 24-104, Springer, 2023.
Joao Marques-Silva and Alexey Ignatiev. Delivering Trustworthy AI Through Formal XAI. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 12342-12350, 2022.
Joao Marques-Silva Thomas Gerspacher, Martin Cooper, Alexey Ignatiev, and Nina Narodytska. Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay, Advances 2020.
in Neural Information Processing Systems,
Joao Marques-Silee Silva, Thomas Gerspacher, Martin C Cooper, Alexey Ignatiev, and Nina Narodytska. Explanations for Monotonic Classifiers. In International Conference Machine Learning, pp. 7469-7479. PMLR, 2021.
Reda Marzouk and Colin de La Higuera. On the Tractability of SHAP Explanations under Markovian Distributions. In Forty-first International Conference on Machine Learning.
Reda Marzouk, Shahaf Bassan, Guy Katz, and Colin de la Higuera. On the Computational Tractability of the (Many) Shapley Values. arXiv preprint 2522:25502.2220 2025.
Sebastian Ordyniak, Giacomo Paesani, and Stefan Szeider. The Parameterized Complexity of Finding Concise Local Explanations. In IJCAI, pp. 3312-3320, 2023.
Dheeraj Rajagopal, Vidhisha Balachandran, Eduard H Hovy, and Yulia Tsvetkov. SELFEXPLAIN: A Self-Explaining Architecture for Neural Text Classifiers. In Proceedings of the 2021 Conference on Empirical Methods Natural Language Processing, pp.
2021.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why Should I Trustt You?" Explaining the Predictions of Any Classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135-1144, 2016.
Marco Tulio Ribeiro, Sameer Singh. and Carlos Guestrin. Anchors: Precissen Model-Agnostic Explanations. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Marco Sälzer and Martin Lange. Reachability is NP-Complete Even for the Simplest Neural Networks. In Reachability Problems: 15th International Conference, RP 2021, Liverpool, UK, October 25-27, 2021, Proceedings 15, pp. 149-164, 1699164.555 Springer, 2021.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial Training for Free! Advances in neural information processing systems, 32, 2019.
Andy Shih, Arthur Choi, and Adnan Darwiche. A Symbolic Approach to Explaining Bayesian Network Classifiers. arXiv preprint / 2018
Vered Shwartz, Peter West, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Unsupervised Commonsense Question Answering with Self-Talk. arXiv preprint arXiv:2004.054: 05483, 2020.
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling Lime and Shap: Adversarial Attacks on Post Hoc Explanation Methods. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pp. 180-186. 2020.
Bernardo Subercaseaux, Marcelo Arenas, and Kuldeep Meel. Probabilistic Explanations for Linear Models. arXiv preprint arXiv:2501.00154 2024.
15

---

Published as a conference paper at ICLR 2025
Mukund Sundararajan and Amir Najmi. The many Shapley Values for Model Explanation. In International conference on machine learning, pp. 9269-9278 PMLR, 2020.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic Attribution for Deep Networks. In International conference on machine learning, pp. 3319-3325 PMLR, 2017.
Christopher Umans. Hardness of Approximating/spl Sigma//sub 2//sup p/minimization problems. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 465 474. IEEE, 1999.
Christopher Umans. The Minimum Equivalent DNF Problem and Shortest Implicants. Journal of Computer and System Sciences, 63(4):597-611, 2001.
Keyon Vafa, Yuntian Deng, David Blei, and Alexander Rush. Rationales for Sequential Predictions. In EMNLP, 2021.
Stephan Wäldchen, Jan Macdonald, Saseha Hauch, and Gitta Kutyniok. The Computational Com- plexity of Understanding Binary Classifier Decisions. Journal of Artificial Intelligence Research, 70:351-387 2021.
E Wang, P Khosravi, and G Van den Broeck. Probabilistic Sufficient Explanations. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021a.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. Beta-crown: Efficient Bound Propagation with Per-Neuron Split Constraints for Neural Network Robustness Verification. Advances in Neural Information Processing Systems, 34:29909-29921. 2021b.
Yipei Wang and Xiaoqian Wang. Self-Interprettale Model with Transformation Equivariant Interpre- tation. Advances in Neural Information Processing Systems, 11-2359--272,, 2021.
David S Watson, Limor Gultchin, Ankur Taly, and Luciano Floridi. Local Explanations via Necessity and Sufficiency: Unifying Theory and Practice. In Uncertainty in Artificial Intelligence, pp. 1392. PMLR, 2021.
Haoze Wu, Omri Isac, Aleksandar Zeljić, Teruhiro Tagomori, Matthew Daggitt, Wen Kokke, Idan Refaeli, Guy Amir, Kyle Julian, Shahaf Bassan, et al. Marabou 2.0: Versatile Formal Analyzer of Neural Networks. In International Conference on Computer Aided Verification, pp. 249-264944 Springer, 2024a.
Min Wu, Haoze Wu, and Clark Barrett. Verix: Towards Verified Explainability of Deep Neural Networks. Advances neural information processing systems, 36, 2024b.
Yutaro Yamada, Ofir Lindenbaum, Sahand Negahban, and Yuval Kluger. Feature Selection using Stochastic Gates. International Conference on Machine Learning, pp. 10648-10659, PMLR, 2020.
Jingquan Yan and Hao Wang. Self- leff-Interpretable Time Series Prediction with Counterfactual Explana- tions. In International Conference on Machine Learning, pp. 391 10-39125.. PMLR, 2023.
Junchen Yang, Ofir Lindenbaum, and Yuval Kluger. Locally Sparse Neural Networks for Tabular Biomedical Data. In International Conference Machine Learning, pp. 25123-25153, PMLR, 2022.
Chih-Kuan Yeh, Cheng- Yu Hsieh, Arun Suggala, David I Inouye, and Pradeep K Ravikumar. On the (in) Fidelity and Sensitivity of Explanations. Advances in neural information processing systems, 32, 2019.
Jinqiang Yu, Alexey Ignatiev, Peter J Stuckey, Nina Narodytska, and Joao Marques-Sine Silva. Eliminating the Impossible, whatever Remains Must be True: On Extracting and Applying Background Knowledge in the Context Formal Explanations. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4123-4131 2023.
16

---

Published as a conference paper at ICLR 2025
Xianren Zhang, Dongwon Lee, and Suhang Wang. Comprehensive Attribution: Inherently Ex- plainable Vision Model with Feature Detector. In European Conference on Computer Vision, pp- 196-213. Springer, 2024.
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Cheekong Lee. Protgnn: Towards Self- Explaining Graph Neural Networks. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 36, pp. 9127-9135, 2022.
17

---

Published as a conference paper at ICLR 2025
Appendix
The following appendix is organized as follows:
Appendix
A
contains extended background on sufficient explanations and related work.
Appendix contains background for the computational complexity proofs.
Appendix contains the proof of theorem
Appendix contains the proof of theorem
Appendix contains technical specifications, related the models, and training.
Appendix contains information regarding the training time of SST compared to standard training.
Appendix G includes an experiment on the generalization of various masks across different suffi-
eiency settings.
Appendix H includes an experiment on the extension of SST to simplified inputs.
Appendix contains additional ablation results.
Appendix contains supplementary results.
A EXTENDED RELATED WORK AND BACKGROUND
Sufficiency- explanations. cufficienncybaseed explanations are widely sought-after approach in explainability, with numerous methods proposed to achieve them (e.g.. (Ribeiro et al. 2018 Carter al. 20199] Ignatiev et al., 2019; Bassan & Katz (023)). The core idea is to identity a minimal subset of features that determine a prediction, allowing one to focus on the essential "reason" for the outcome while excluding non-relevant features. Notably, unlike the more prevalent additive attribution methods (Ribeiro et al. 2016 Lundberg & Lee [017 Sundararajan al. 2017). these explanations do not depend on approximate linearity assumptions (Ribeiro et al. 2018; Ych et al.) 2019). From human perspective, prior research has demonstrated their effectiveness; for instance, seeing multiple sufficiency-bart based explanations helps users predict model decisions more accurately compared to relying on additive attributions (Ribeiro al. 2018)
The concept of sufficient explanations has been extensively explored in the literature. The general notion of sufficient explanation is closely linked to ideas from actual causality (Halpern) 2016) and
has been examined in several works [Chockler et al., 2021 Chockler & Halpern] 2024] Chockler et al.
2024, Kelly et al., 2023] Watson et al.) (021). Furthermore, the robust class of sufficient explanations studied in this work also connects to research in formal logic (Marques-Silvaa 2023: Darwiche & Marquis 202T).
the broader case where the cp perturbation unbounded, such explanation are
sometimes reterred to as abductive explanations (Ignatiev et al. (2099) Ordyniak et al. 2023 Bassan
al. 2023). A related but distinct concept that of prime implicant (Shih et [018]] ggnatiev
et al. 2019). Given the high computational complexity of deriving such explanations (Barceló
ct al. 2020), significant research has focused on identifying simplified models where explanation
computation remains tractable (Cooper & Marques Mlaruues-Silval 2023 Audemard et al. [02II. Examples
of such models include decision trees (Izza et al. |020 Huang et al. 1021]] Bounia & Koriche 2023)
KNNs (Barceló al. 2025), ), tree ensembles (Izza & Marques-Silva [021] Ignatiev et al. 2022
Audemard et al.] 2022h [Boumazouza et al. (002). linear models (Marques-Silve et al. 2020
Subercaseaux et al. (2024), monotonic models (Marques-Siik
al. 2021 Harzli al. 2023 and
small-scale neural networks (Ignatiev et al., 2019 Wu et al.] 2024b La Malfa et al. 202] Bassan &
Katz 2023). These explanations are often facilitated by neural network verifiers (Wang el 202Tb
Wu et al. 2024a Fel et al.) 2023).
Self-explaining models. The concept of self-explaining neural network (SENN) was first introduced by (Alvarez Melis & Jaakkola 2018) and advocates for training architectures that inherently provide
interpretations for their decisions (Lee et al. 2022, Shwartz et al. 2020 Rajagopal et al., 202T
Guyomard et al. |022 Guo et al. / al. 2022 et al. al. (025). This idea is closely re related
to other research on learning human-understanne undde-ntntdrtttaeleeeeeee "concepts" (Koh et al, 2020 Blazek & Lin 202
Espinosa Zarlenga et al.| 2022 Marconato et al. 2022 Kim et 2023) and representative training-
data "prototypes" (Chen et al. 201 20 Keswani et al. 2022 Hong et al. 2023). Additionally, related
work explores training interventions designed improve feature selection capabilities (Lemhadri
et al.
2021 Zhang et al. 2024 Jethani et al. 2021 Jiang et al.) 2024 Yang et al. 2022
Yamada
al.
2020
18

---

Published as a conference paper at ICLR 2025
B COMPUTATIONAL COMPLEXITY BACKGROUND
In this section, we will introduce formal definitions and establish a computational complexity background for our proofs.
Computational Complexity Classes, We start by briefly introducing the complexity classes that are discussed in work. It is assumed that readers have basic knowledge of standard complexity classes which include polynomial time (PTIME) and nondeterministic polynomial time (NP and coNP). We also will mention the common complexity class within the second order of the polynomial hierarchy, ΣnG- This class encompasses problems solvable within NP, provided there is access to oracle capable of solving co-NP problems in O(1) time. It is generally accepted that NP and co-NP are subsets of 2/ though they are believed to be strict subsets (NP, co-NP Ç 2/ (Arora & Barak (2009)) Furthermore, the paper discusses the complexity class PP. which describes the set of problems that can be solved by a probabilistic Turing machine with an error probability of less than for all underlying instances.
Multi Layer Perceptrons. Our hardness reductions are performed over neural networks with ReLU activation functions. We assume that our neural network is some function f. R IR where n is the number of input features and is the number of classes. The classification of f is chosen by taking arg max, [x) For us to resolve cases where two or more distinct classes are assigned the same value, we assume that the set of classes is ordered (i: i2.... > ic). and choose the first maximal valued class. In other words, there exist a set of ordered classes , i E [c] for which > > ... > and fx) _... fx) arg max, fxx;; then, without loss of generality, i1 is chosen as the predicted class.
In the described MI.P, the function defined to output f == gX)), The first (input) layer ())) is x E R" The dimensions of both the biases and the weight matrices are represented by sequence of positive integers
d. We focus on weights and biases that are rational, or in other words, w E Qd xd, and (60 E Qrd, These parameters were obtained during the training f. From previous definitions of the dimensions of f it holds that do and de We focus here ReI.U/ activation functions. In other words, (()) is defined by ReI.U(x)) = max(0,
C PROOF OF THEOREM 1
Theorem 1. Given a neural network classifier with ReLU activations, and R", obtaining cardinally minimal sufficient reason for (f,x) is (i) NP-Complete for buseline sufficient reasons (ii EhP CComllete for robust sufficient reasons and (ii) NP?P -Hard for probabilistic sufficient reasons.
Proof. We follow computational complexity conventions (Barceló et al. (2020); Arenas et al. (022) focusing our analysis on the complexity of the decision problem which determines if a set features constitutes a cardinally minimal sufficient reason. Specifically, the problem involves determining
whether a subset features C (1....n) n2) qualifies as sufficient reason while also satisfying (S) < k. This formulation is consistent with and extends the problems addressed in earlier research (Barceló jet al. p Arenas et al. 2022): Wäldchen et al. (202T)). The complexity problem is defined as
follows:
MSR (Minimum Sufficient Reason):
Input: A neural network f, and an input instance R".
Output: Yes if there exists some S C (1,...,,) such that is a sufficient reason with respect to (J, x), and No otherwise
We observe that earlier frameworks evaluating the complexity of the MSR query concentrated on cases where {0, 1)" more straightforward scenario. Our focus extends to broader domains encompassing both discrete and continuous inputs and outputs. We are now set to define our queries, aligning with the definitions of sufficiency outlined in work:
19

---

{0, 1) and polynomially validate whether Published as a conference paper at ICLR 2025
P-MSR (Probabilistic Minimum Sufficient Reason):
Input: A neural network f. some distribution D over the features, S 6 1, and x.
Output: Yes if there exists some S S fI.....n)) such that S is probabilistic sufficient reason with respect to (f, x), D and 6, and No otherwise
R-MSR (Robust Minimum Sufficient Reason):
Input: A neural network f. an input instance x E RR, and (possibly) some > 0.
Output: Yes if there exists some S ( n) such that S is robust sufficient reason with respect to (f. (over the e-ball surrounding x, or over an unbounded domain) and No otherwise
B-MSR (Baseline Minimum Sufficient Reason):
Input: A neural network f. an input instance x E RR", and some baseline z E IR"..
Output: Yes if there exists some S (1,-..,m) n) such that S is baseline sufficient reason with respect to (f, x), and z, and No otherwise
We will begin by presenting the complexity proof for the R-MSR query:
Lemma 1. Solving the R-MSR query over a neural network classifier f. an input x E R", and (possibly), some E > O, where f has either discrete or continuous input and output domains is Dg Complete.
Proof. Our proof is an extension of the one provided by the work of Barceló et al. (2020), who provided similar result for multi-layer perceptrons that are restricted to binary inputs and outputs. We expand on this proof and show how it can hold for any possible input and output discrete or continuous domains.
Membership. In the binary instance, proving membership in Σn can be done by guessing some subset of features S and then using coNP oracle for validating that this subset is indeed sufficient concerning (f, x). When dealing with binary inputs, validating that a subset features is in coNP is trivial since one guess some assignment # (xxs; (x) holds.
When addressing continuous domains, the process of guessing S remains consistent, but the method for confirming its sufficiency changes. This alteration arises because the guessed certificate z may be polynomially bounded by the input size and could be unbounded. When guessing values in R. it becomes crucial to consider limit on their size, which ties back to the feasibility of approximating these values with sufficient precision.
To determine the complexity of obtaining cardinally minimal sufficient reasons, it is often helpful to first determine the complexity of a relaxed version of this query, which simply asks for the complexity of validating whether one specific given subset is sufficient reason. We will use this as a first step in solving our unresolved inquiry for proving membership for continuous domains. The problem of validating whether one subset is sufficient is formalized as follows:
CSR (Check Sufficient Reason):
Input: neural network f. a subset C (1,...,,n) n.), and an input instance x E IR", and possibly
some E 0.
Output: Yes, if S' is a sufficient reason with respect to (f, x) (over some ball, or over an unbounded domain), and No otherwise
The process of obtaining a cardinally minimal sufficient reason (the MSR query) computationally harder than validating whether one specific subset is sufficient (the CSR query). However, it is often helpful to determine the complexity of CSR, as a step for calculating the complexity of MSR.
We adopt the proof strategy from Sälzer & Lange 2021), which demonstrated the complexity that the complexity of the NW-Reechhbilityy problem is NP-Complete - an intricate extension of the initial proof in Katz al. (2017). Intuitively, in continuous neural networks, rather than guessing binary inputs as our witnesses, we can guess the activation status each ReLU constraint. This approach allows us address the verification of neural network properties efficiently using linear
20

---

Published as a conference paper at ICLR 2025
programming. We begin by outlining the NN-Reachabilityy problem as defined by Sälzer & Lange (021I::
Definition 1. Let R - R be neural network. We define the specification & property that is a conjunction of linear constraints Qin on the imput variables X and a set of linear constraints Dou on the oulput variables Y. In other words, &b Φia (X) ) A Done(
NNReach (Neural Network Reachability):
Input: A neural network f. input specification din (x), and output specification dout (y) Output: Yes there exists some x E R" and some y E I such that the specification & holds, i.e., Oin (x) is true and out (y) is true, and No otherwise
Lemma 2. Solving the CSR query for neural networks with continuous input and output domains can be polynomially reduced to the NNReach problem.
Proof. We will begin by demonstrating the unbounded version (where no e is provided as input), followed by explanation of how we can extend this proof to a specific e-bounded domain. Given an instance (f, S, x) we can construct an instance (J. Pin: Pout) for which we define 6in as a conjunction of linear constraints: X; = X; for each E S. We use X;
to denote assignment of the input variable X, to the assignment x, E IR. Assume that f(x) is classified to some class (i.c., holds that fxx;; fx); for all i + t). Then, we define Pout as a disjunction of linear constraints of the form: Y, < Y, for all i 7 t.
S is sufficient reason with respect to (f.x) if and only if setting the features X to there corresponding despect
values in x determines that the prediction (xx always stays l. Hence, S is not a sufficient reason and only if there exist some assignments E RR" and assignment y R for which all features in X are set to their values in x and fx) is not classified to f. implying that for all i * it holds that fx)) < fx); This concludes the reduction. This reduction can be readily adapted for scenarios where sufficiency is defined within a bounded domain. This involves specifying that for all E S, we include constraints such as: X; S X; + and X; X; - C.
Finishing the Membership Proof. Membership of MSR for continuous input domains can now be derived from the fact that we can guess some partial assignment some subset S E [I....n] n1 of size k. Then we can utilize Lemma to incorporate coNP-oracle which validates whether S is sufficient concerning (f, x) over the continuous domain R..
Hardness. Prior work (Barceló et al. (0200) demonstrated that MSR is Eg- -hard for MLPs limited to binary inputs and outputs. To comprehend how this proof might be adapted to continuous domains, we will initially outline the key elements of the proof in the binary scenario. This involves a reduction from the Shortest- Shortest-Implicane Implicant-Core problem, which known to be EP -Complete (Umans 2001h). We begin by defining an implicant for Boolean formulas:
Definition Let & be a boolean formula. An implicant C for à is a partial assignment of the variables of & such that any assignment to the remaining variables evaluates true.
The reduction also makes use the following Lemma (whose proof appears in Barceló et al. (2020)) Lemma 3. Any boolean circuit & can be encoded into equivalen! MLP over the binary domain (0. 10 + {0, 1} in polynomial time.
We will now begin by introducing the reduction for binary-input-outee MLPs from the Shortest- Implicant-Canl problem (Barceló al. 2020)). The Shortext-Implicm- problem defined as follows:
Shortest Implicant Core:
Input: A formula in disjunctive normal form (DNF) ő = t V Vt2..... .. V t, an implicant C' of Φ and an integer k.
Output: Yes, if there exists an implicant C' C in of & of size k. and No otherwise
Initially, we identify X, as the set of features not included in t,. Subsequently, each variable x; X. can be divided into l: distinct variables 2/. a......f ++1 For each (1....,k k 1}, we can
21

---

Published as a conference paper at ICLR 2025
construct new formula g by substituting every instance of the variable zy in X with af.. Finally, we can define o' as the conjunction of all the x(0) formulas. In summary:
16 Gla + uy Var E Xcl.
k+1
The reduction then applies Lemma to transform d' into an MLP f with binary inputs and outputs. also constructs vector setting the value to 1 for all features in t, that are positive literals, and 0 for the rest. According to the reduction in Barceló et al. (2020), then (Ø, C, E Shortest Srarttest-mplicant-CCe if and only if there exists a subset S of size l such that, when S is fixed to its values in then f(xs; zgg) consistently predicts 1, for any assignment z E {0, 1 This implies that (Ø) C, k) E Shortest-Implican--CCn
and only if (f,x, k) EMSR for MLPs with binary inputs and outputs, demonstrating that MSR for binary-input-ouppu MLPs is 21 -Hard.
However, it is important to note that the previous lemma may not apply when the MLP in question does not exclusively handle binary inputs and outputs. We will now demonstrate how we can transform f another MLP f', in polynomial time. We then will prove that when defined such that f : {0. 1 + {0, } and f' is defined such that f' R - R22 a sufficient reason of size k exists for (f.x) if and only one exists for (f',, x). This reduction will extend the reduction from the toortest-Implicantt
to MSR for MLPs with non-binary inputs and outputs, thereby providing proof of 23 -hardness for non-binary inputs and output MLPs.
Typically, f' will be developed based on f. but it will include several additional hidden layers and linear transfornations. To begin, we will introduce several constructions that are crucial for this development. We will specifically demonstrate how these constructions can be implemented using only linear transformations or ReLU activations, allowing them to be integrated into our MLP framework. The initial construction we will discuss was proposed by Sälzer & Lange 2021
= :eRUU x)) ReLU(x -
1
(8)
In Sälzer & Lange 22211, it is demonstrated that the construction is equivalent
i otherwise
x
From this, it can be directly inferred that 2 if and only if a o and 2 / for any other values of E R. This construction will prove useful in our reduction. We will also utilize second construction, which described as follows:
2 ReLU(z) + (-1) ReLU(-x) = |x
(10)
The reduction. We will now explain how convert f into the appropriate f' ensure the validity of our reduction. We begin with the foundational structure of f as the skeleton for f'. Initially, we add extra neurons to the first hidden layer and link them the input layer as follows. Each input feature x; is processed through series of computations, which, leveraging the two constructions previously mentioned, can be performed solely using ReLUU activations. Specifically, for each feature x, compute:
X == ReLUUReLUU 1
1 x;) + ReLU
)
2
2
1
(-1) ReLLL
x,) - ReLU(x, 2 2
(11)
2
1 - x,) + ReLUUxx
1
ReLU 2
2 2
22

---

Published as a conference paper at ICLR 2025
The existing structure of (and thus f') features single output neuron, which, when given input from the domain x E {0, 1)", returns a single binary value from {0.1}. 1}. Let us denote the value of this output neuron o1. To develop f', we introduce additional hidden layers that connect sequentially after 01- Initially, we link or to two new output neurons, denoted 01,1 and 01,2- These neurons configured as follows: 01,2 is directly tied or with linear transformation of value effectively making 01,2 For the other output, we establish the weights and biases through the following computation:
01,1 Re)
(12)
It is evident that the following equivalence is maintained:
01,1 { if 01 =0 01 =1
(13)
We will now outline the construction of the output layer of f', which consists of two outputs: 02,1 and 02,2- Adhering to our formalization of MLP, we assume the following order: 02, > 02,2, without loss of generality. This means that in cases where a specific assignment Z R is processed through f' and results in 02, = 02.,, then f' is classified under class 02.1. Conversely, f is classified as class 02,2 only if the value at 02,2 is strictly larger than that 02,1. The constructions for 02,1 and 02 as follows:
2,11 := ReLU((),1) + (-1) ReLU(-o1,1)
+ Σ X
<E(ml
(14)
02,2 = ReL:))()())))(((1
(-1) ReLU(-01,2)
Σ
x 02,1
8E/m]
Which is equivalent to:
02,1 = 10,,1 Σ x//
iE(ml
(15)
0222 : |01,2| +
x + 02,1
AE(m]
Reduction Proof. We will now establish the correctness of the reduction. Once more, we will begin by establishing correctness for the unbounded domain (where no e is provided as input), before outlining the necessary adjustments for the bounded domain. Initially, by design, we note that x {0, 1 because the input vector, derived from the Shortest-Implican--orr features. Following the specified construction of x where all positive features in f, within the formula o' are set to 1, and all other features are set to O, it results in t, evaluating to True. Consequently, d' evaluates true, thereby causing / to evaluate 1. This means that when is processed through the single output value 0₁ is determined to be 1. Since the connections from the input layer to the output 0₁ f remain unchanged from those in f. when input into f'. o₁ also evaluates 1.
contains only binary
From the design of f', we observe that 01,1 0 and 01.2 1. Given that x comprises only binary values, our earlier construction ensures that all x, values are equal 0. Consequently, this results in: 02,1 = 0 and 02 = 1, leading to the classification of under class 02,2-
Additionally, we observe that by definition, 2 for all which implies that invariably holds that:
[02.1 =00111 +
Σ
0
A [02.2 101.21 + Ex+ 02 2
(16)
xE(m]
Since the precedence 02,1 > 02,2 is established, it follows that f' is classified under class 02,1 if and only if 02,1 0. This condition arises because if 02,1 O, then it necessarily means that 02,2 02,1
23

---

Published as a conference paper at ICLR 2025
resulting in being classified under 02,2- Conversely, if 02 O, then 02,1 02,2, and thus f is classified under 02,1 by virtue of 02.1 > 02.2-
Assuming that (ø, C, k) E Shortest- CiportestIIplliant-Corr as previously mentioned, it follows that there is a subset of features, each of size k, where fixing the features to their values in x results in the output 01 in I' consistently remaining
irrespective of how the features in S are set within the binary domain {0, 1)". However, we need to establish a more robust claim that this sufficiency extends to any values assigned the features of S from the continuous domain
R". Specifically, we need to demonstrate that when the values of the features in S are fixed as they are in x, the prediction of f consistently remains at 02 no matter what real values are assigned the features in S. We have established that fixing the values of S to those in x results in or in f consistently equaling irrespective of how the values of S are set within {0, 1)". Given that x o for all under our conditions, it follows that both 02,1 and 02 are greater than O. We have previously demonstrated that if 02.1 > O, then I' is classified as 02,2- Therefore, for any potential assignment of the features in S within the domain {0, 1)", f' is classified under 02,2- Since the original prediction is 02,2, this confirms that there is indeed a subset S of size k, which, when fixed at their values, ensures that the prediction of f' remains consistently at 02,2-
Let us consider the scenario where the values for the complementary set S are sourced not exclusively from the {0, 1 domain, meaning they are derived from z E R" {0, 1}"". In more precise terms, there exists least one feature within S such that for the assignment E IR", z; o and x; * O. We must demonstrate that under these circumstances, the prediction for f" still stabilizes at 02,2. For this particular feature 2,, it confirmed that:
1 ReLUCS z,) + ReLUUZ, - -5) +
(17)
This also suggests that within the newly constructed hidden layers of f', there are some x values such that:
x |ReLU(, 1 z;) ReLUUz, - ) 2
1
(18)
We now can conclude that:
22,1 = 101,1+ Σ x 0
(19)
<E(m)
Consequently, of is classified under class 02,2 even when the features in are assigned values from the domain IR \ {0, 1)". In summary, this indicates that there exists a subset S which consistently remains sufficient for (f", x) when assessing sufficiency across any possible value in R".
For the converse direction of the reduction, let us assume that (ø, C, k) & Cinpteest-Implicnt-CC This implies that there is no subset S of size k or smaller such that ff consistently evaluates to class o when the values of come solely from the binary domain (0, 13"". This also means that for any subset S of size & or smaller, there exists some E 10, 13" where f(xs: Zg) is evaluated to 0 (resulting in a misclassification). Since (xs; ) is entirely binary, all hidden neurons x² evaluate O, leading to 02,1 = 0 and thus, f' is misclassified to 02,1. This overall demonstrates that there is no subset S of size or less that is sufficient concerning {,",, x), when the sufficiency of assessed relative to R". This completes the reduction.
We now need to demonstrate how to adjust the following reduction when e is an input parameter, with the sufficiency of S restricted to e-ball rather than being unbounded. The reduction can simply set E > 1. Since x E {0, 13",, the sufficiency of is then defined over a continuous e-ball that includes all inputs in (0, 1}". Let's refer to this domain F. In our reduction, we have shown that any contrastive assignment achievable in f' must also be achieved over the domain {0, 1)". Thus, sufficiency for S in the domain IR" \ {0. 1) equivalent to sufficiency in IF {0, 1)",, which implies that our reduction is applicable even in such boundeed domain.
24

---

Published as a conference paper at ICLR 2025
Lemma 4. Solving the B-MSR query over neural network classifier with either continuous or discrete input and output domains is NP-Complete.
Proof. We begin by proving membership. Membership in NP is established because one can guess a subset of features S and then verify whether xxx::'s) * fxx and whether |S| I k.
Hardness. We demonstrate hardness by presenting a reduction from the classic CNF-SAT problem, which is known be NP-Complete and defined as follows:
CNF-SAT:
Input: A formula conjunctive normal form (CNF): Φ
Output: Yes, if there exists assignment the literals of ø such that & is evaluated to True, and
No otherwise
We denote 1, as vector of size n containing only 1's, and O,, as a vector of size containing only O's. Given some input o, we can first assign 1, to ø (setting all variables to True). If o evaluates to True, then there exists Truth assignment to Φ. so the reduction can construct some trivially correct encoding. We can hence assume that ((1,) = O. We now denote the following:
2 = (x) x2 A An.,
(20)
= 02
o', is no longer a CNF, however, we can still use Lemma 3 to transform ø' into an MLP which behaves equivalently ø' under the domain {0, 1)". The reduction then finally constructs (f, 1,, x' == O,, nt 1). 1).
We first note that (x) 1, and hence both ø' (x( 1 and f(x) = 1. If (o) E CNF-SAT, then there exists an assignment of variables that evaluates ø to True. This means there is some assignment in {0, 13"d that evaluates f to True. Since we have assumed that this is not the assignment it must be some assignment x' E {0, 1 * This implies that there exists an assignment of size < n that evaluates 1, to True. Consequently, there exists subset S where |S] s k and f[1s; s; 0g) = fxx::xg) = 1 f(1,).
1n.
For the second direction, we assume that (Ø) & CNF-SAT. This implies that no assignment evaluates True. Consequently, there is no assignment with fewer than n variables that evaluates Φ2 (x) Azz A... A...Ar,)) to True. Therefore, there is no assignment of size k = n 1 or less that evaluates either á or Φ True. From this, we conclude that there is no subset S S [n] of size less for which (xg: x * f(x) f(1,) 1, thus completing the reduction.
Lemma 5. Solving the P-MSR query on a neural network classifier f is NP -Hard.
Proof. The reduction is derived by integrating the proof from Wäldchen et al.
2021 with Lemma
The work in (Wäldchen et al. (202T)) established that finding a cardinally minimal probabilistic sufficient reason for a CNF classifier, given a discrete uniform distribution over {0, 1)", is NP?P -Hard. Using Lemma 3 we can transform &a into an MLP f. applicable to either discrete or continuous domains. This allows us to construct (f,x'= == x, k' = k) and define D as the uniform distribution over {0, 13mh. Given that x is an input for a CNF classifier, directly follows that E {0, 13a, hence follows that cardinally minimal probabilistic sufficient reason for & exists if and only if one exists for (f. x) concerning the distribution D. thereby completing the reduction.
We observe that since the previous proof establishes hardness over the uniform distribution, this hard- ness persists under any distributional assumption that includes this distribution, such independent distributions or more expressive ones, like the Markovian distributions examined by (Marzouk & de La Higuera), the Hidden Markov modeled distributions examined by (Marzouk al. 2025
25

---

Published as a conference paper at ICLR 2025
D PROOF OF THEOREM II
Theorem 2. Given a neural network classifier J with ReL.U activations, and x E R", (i) > upproximating cardinally minimal robust sufficient reasons with n²- factor is En -Hlad, (i) Ve it is factor n
approximate cardinally minimal probabilistic or baseline sufficient reasons with
Proof. We follow common conventions and when discussing the inapproximability of obtaining cardinally minimal sufficient reasons, refer to the aptimization-versinn of these problems, or in other words obtaining cardinally minimal sufficient reason, instead of asking whether there exists such a subset of size (which is the decision version). To avoid confusion, will refer to these problems as R-MSR", B-MSR" and P-MSR*. We start by proving the first complexity class:
Lemma 6. Given neural network classifier J with ReLU activations, and E ER, Ve > 0 approximating cardinally minimal robust sufficient reasons with n "acctrr (i.e., solving the R-MSR* query) is Di -Hard
Proof. We first note known inapproximability result for the Shortest-mppliaane Core prob- lem (mmans (1999) which will be used to prove the inapproximability result for our case:
Lemma 7. Given a DNF formula vh, then for all e >> 0, approximating the Shortest Implicant Core of to within factor n--e is S.f- -Hard.
We acknowledge, however, that despite the difficulty of the MSR query being established through a reduction from the Shortest Implicant Core problem (as proven in Barceló et al. (2020) and discussed in Lemma| I this approach cannot directly utilized because the reduction is not necessarily approximation preserving. Specifically, the reduction discussed in Lemma I which follows Barceló eet al.] (2020), involves an MLP with an input space considerably larger than that the boolean formula. If the input size of the boolean circuit is then the input size of the constructed MLP in the worst-case scenario will be n (k + 1).
Note that if l n, the problem has trivial solution. Therefore, addressed for cases where n. > k, or equivalently n 2 k + 1. Let us denote the optimal solution for the MSR query MLPs as OPT and the optimal solution for the shortest implicant core as OPTCORE. Given that k remains constant in both reductions, it follows that OPT OPTCORE. However, we still need to demonstrate that the same approximation ratios are applicable.
assume the problem is
Let us suppose there exists some > O such that an algorithm can solve the optimization problem of obtaining a cardinally minimal sufficient reason for MLPs with approximation factor of n We will denote the solution provided by this algorithm as k'. Consequently, we observe that:
k' S OPT (n (k + 1)) - = OPTCORE (n (k + 11)+
(21)
OPTCORE (n -n) OPTCORE: nn' 1-22r < OPT n I-c
This results in an n 1-c factor approximation algorithm for the shortest implicant core problem. Con- sequently, conclude that approximating the optimization problem of obtaining robust cardinally minimal sufficient reasons is Ef -Hard to approximate within factor of n
Lemma 8. Given neural network classifier f with ReLU activations, and E R2, Ve 0 approximating cardinally minimal probabilistic sufficient reasons with n--ee factor is NP-Hard
This result can be extracted from the inapproximability results for obtaining cardinally minimal probabilistic sufficient reasons for CNF classifiers that were proven by Wäldchen al, (2021) This result is as follows:
Lemma 9, Given CNF classifier, sb. and some instance x, for all e obtaining a probabilistic sufficient reason concerning (3),x) under the uniform distribution defined over {0, 1 , is NP-Hard approximate within factor !
Using Lemma 3
We begin with and develop MI.P f, ensuring that cardinally minimal sufficient reason applicable is also valid
we can replicate the process described under Lemma 5
26

---

Published as a conference paper at ICLR 2025
for v. This reduction is approximation preserving, both K' := k and ní' n. indicating that the same approximation ratio is preserved. Consequently, the hardness results established for CNF classifiers are equally applicable to any MLP with discrete continuous input domains.
Lemma 10. Given a neural network classifier with ReLU activations, and x R", Ve >> 0
approximating cardinally minimal baseline sufficient reasons with n - factor is NP-Hard
We will perform an approximation preserving reduction from the Max- Cli-ueique problem, which is known to be hard to approximate. The problem is defined as follows:
Max-Clique:
Input: A graph G (V, E)
Output: clique in G (i.e., subset of vertices C' S V where each two vertices in C' are adjacent), which has maximal cardinality.
The following inapproximabilit result is known for the Max-Clique problem (Hástad (1999) ):
Lemma 11. Given a graph G = (V, for any > 0 is NP-Hard to approximate the maximum clique of G with approximation factor factor 1
We now present
reduction from the Max- Max-Clique problem B-MSR" for neural networks. Consider a graph G = (V, E). We define a Boolean formula & that corresponds G. vé will have [V] variables: .1,.... TV (each variable representing a vertex in the graph). We define & as follows:
pupproximatioo-ppreerrviii
(-Iw V mxx)
(22)
(2.))
Using Lemma 3 encode sb into MLP f. We assert that subset C C V constitutes maximal clique if and only if S = E \ C/ is a cardinally minimal baseline sufficient reason for (f, 0,) with respect the baseline 1,2
First, we note that f(O,.) = 1, since all variables are set to True in this case. Therefore, a sufficient
reason for f concerning the baseline 1, would be a subset of features such that setting the features in S to keeps the classification 1. We will prove that C' is a clique in G if and only if S = E a sufficient reason for (f, O,,) concerning the baseline 1,,
If C' is not a clique in G. there exist vertices u, E C' such that (u, v) & E. Therefore, the clause W V- -r is included in vb Given that u, E C, they also belong to 3, and their features are modified from assignment to a 1 assignment.
a result, - - = False, leading & = False and s0 1g) = 0. This demonstrates that in this case, S is not sufficient concerning the baseline 1, Conversely, y, if C' a clique in G. then for any (u, v) E C, (u, v) clause -r V - in vh. both J.. and Ia remain fixed at the value 0, resulting in ~r,, V -x,- True and thus f0s: 1)) 1. This confirms that is a sufficient reason concerning the bascline 1,,
This ensures that for any
From the previous claim, it follows directly that sufficient reason S is of minimal cardinality if and only if the cardinality of E' \ C is minimal (when is a clique in G). This equivalent to requiring that C' has maximal cardinality, thereby concluding proof.
E TECHNICAL SPECIFICATIONS
We provide detailed model specifications for reproducibility purposes. While our evaluations are conducted on specific benchmarks, the SST methodology can be adapted to any neural network classifier. We compare the sufficient reasons derived from SST-trained models with explanations from post-hoc methods on traditionally trained models. To ensure a fair comparison, we perform a separate grid search for each configuration to determine the optimal model. For traditional models, we optimize based solely on validation predictive accuracy, whereas for SST models, we consider a combination of accuracy, faithfulness, and subset cardinality. For SST-based models, consistently
27

---

Published as a conference paper at ICLR 2025
set the threshold value := 2 and the faithfulness coefficient À := 1, conducting the grid search focusing only on the learning rate a and the cardinality coefficient ç.
We begin by outlining general training details applicable to either all image or all language classifica- tion tasks, followed by a discussion of benchmark senchmark-speciffe implementations.
E.1 IMAGE CLASSIFICATION EXPERIMENTS
All image classification configurations underwent grid search across various learning rates a, with values {10-2 2 1003101-000 3 101+0+
1,00+110 1010 10 10-? for both standard and SST training.
conducted for the cardinality coefficient & options: {10-5, 10-6, ,10-- 10-8, 10-8, 110--10-110 10-11). All models were trained using the Adam optimizer, batch size of 64, and held-out validation and test sets. For robust masking, PGD 2 attack with : 0.12 was used, consisting of 10 steps each of size a' == 10-2 The value of e == 0.12 was selected strike balance between allowing a sufficiently large perturbation for learning, while avoiding excessive distortion of the image. On one hand, this creates a challenging task for learning (as opposed to smaller perturbations). On the other hand, prevents excessive distortion (as might occur with larger perturbations), which could result in the complementary set S containing images that are entirely outside the desired distribution. Lastly, we apply black background mask the MNIST images, both for SST and post-hoc approaches, leveraging their naturally zeroed-out borders, which provides a clearer interpretation of the portions of the digit that fall within the sufficient reason. Moreover, for CIFAR- 10 and IMAGENET images, select images from these benchmarks where specific object highlighted against a white background. The sufficient reasons for these images are depicted over the itself. This approach is applied consistently for both SST and the post-hoc methods.
For SST, additional grid searches
white background, allowing the explanation to remain focused the object
E.2 LANGUAGE CLASSIFICATION EXPERIMENTS
All language classification experiments utilized pre-trained Bert-base (Devlin et al. (2018) model (applicable to both standard training and SST). The grid search focused on learning rates a = {2e 3e 55-5. $]. which are the typical values used for optimizing pre-trained Bert models (Devlin ctt al. (018)). ). For SST, an additional grid search was conducted for the cardinality coefficient
options {10- 10-5 10 10-7 10 3. Optimization was performed using the standard Adam W optimizer, with batch size of 32 and held-out validation and test sets.
E.3 MNIST
We trained simple feed-forward neural network consisting of two hidden layers with sizes 128 and 64, respectively. The experiments were conducted using four Intel(R) Xeon(R) Gold 6258R @
2. 2.70GHz CPUs. For the standard training scenario, the optimal configuration selected was a = 10-1
For the SST-based models, the optimal configurations were: for robust masking == 10 and
E = 10 10-7, and for both probabilistic masking and baseline masking, a == 10-3 and { == 10-7
E.4 CIFAR-10
We train ResNet18 8 architecture (He et al. (2016) (which is not pre-trained) our base model using four Intel(R) Xcon(R) Gold 6258R @ 2.70GHz CPUs and one Nvidia A100-SXM4-80GE GPU. We batch size of 64 and the Adam optimizer. For the robust masking-based SST configuration, the chosen hyperparameters are a = 10-3 and & == 10-8.
E.5 IMAGENET
We train an SST- model a pre-trained ResNet50 (He et (2016)) for IMAGENET classifica- tion using nine Intel(R) Xeon(R) Gold 6258R 2.70GHz CPUs and one Nvidia A100-SXM4-80GB GPU. The optimal configuration for robust masking 10-6 and & := 10-9.
28

---

Published as a conference paper at ICLR 2025
E.6 SNLI
We train our models using a pre-trained Bert-base (Devlin et al. (2018) on the SNLI classification task. The training is conducted on 16 Intel(R) Xeon(R) Gold 6258R CPUs at 2.70GHz and one Nvidia A A100-SXM4-80GI GPU. For standard training on SNLI, the optimal learning rate was set at == De In the SST scenario. the best configuration with probabilistic masking was a == 2 and { = 10-?, whereas, for bascline masking, it was a := 2e and & 10
E.7 IMDB
Our models were trained using a Bert-base (Devlin et al. (2018) pre-trained on IMDB sentiment analysis. The setup included 16 Intel(R) Xeon(R) Gold 6258R CPUs at 2.70GHz and one Nvidia A100-SXM4-80GB GPU. The optimal setting for standard training on IMDB was established at 2e For SST, the most effective configuration with probabilistic masking was == 2e and
{ = 10 while for baseline masking. it was a == 2 and 5 := 10-6.
F TRAINING TIME
One drawback of our approach is its higher computational demand compared conventional training. Specifically, the dtal-propagation procedure we employ doubles the training cost. This increase is more pronounced with complex masking techniques like robust masking, which involves an adver- sarial attack at each iteration, slowing down the process and potentially complicating convergence. These issues are similar to those encountered adversarial training (Shafahi et al. (2019). However, we argue that this additional training effort reduces the necessity for computationally intensive cost-computations to derive concise sufficient reasons, as highlighted in our paper. Furthermore, future studies could investigate various strategies to improve the efficiency of our training method, drawing on techniques used in adversarial training (Shafahi et al. (2019)).
We now will highlight the training time gain incorporated by SST for each particular benchmark, as opposed to a standard training configuration.
F.1 IMAGE CLASSIFICATION TASKS
For MNIST, Standard training required 311.03 seconds (over 43 epochs), whereas baseline-maskee SST was completed in just 26.55 seconds (over 2 epochs). This significant speed increase in the training, despite involving a propagaaton process, was primarily due the optimal learning rate for SST with baseline masking being set at 10-3, compared to 10 for standard training. For probabilistic masking, the training duration was 180.83 seconds (over 11 epochs), where the enhanced efficiency stemmed, again, from achieving optimal results at a higher learning rate. However, robust masking, which is more computationally demanding, took substantially longer, clocking in at 1796.90 .999 seconds (over 49 epochs). For IMAGENET, standard training using the robust masking configuration ran for 287056.8 81 seconds (over 22 epochs) while the parallel Htandard-rraiiing configuration for IMAGENET ran for 74141.85 seconds, over 43 epochs (around times faster). For CIFAR- 10, SST using the robust masking that was mentioned in the paper took 3159.15 seconds (over 53 epochs) compared standard training which took 477, 477.42 seconds (over 49 epochs).
F.2 LANGUAGE CLASSIFICATION TASKS
For IMDB sentiment analysis, standard training ran for 4974.33 seconds (over 1 epoch), while SST with baseline masking ran for 9713.42 1.242 seconds (over 2 epochs) and SST with probabilistic masking clocked at 21516.37 seconds (over epochs). For SNLI classification, standard training ran for 5353.71 seconds (over epochs), while SST with probabilistic masking ran for 6084.66 seconds (over epoch), SST with baseline masking ran for 10440 seconds (over epochs).
G GENERALIZATION BETWEEN SUFFICIENCY SETTINGS
In this section, we examine SST's ability to generalize across different types of sufficiency configura- tions. Our work considers various sufficiency forms, including baseline, probabilistic, and robust
29

---

Published as a conference paper at ICLR 2025
masking configurations. Users select the masking procedure that aligns with their preferred sufficiency criterion. Stricter sufficiency constraints typically lead the model to select larger subsets, while looser constraints result in smaller ones. However, training SST with specific masking config- uration for one form of sufficiency does not necessarily ensure strong generalization to other forms. potential approach to improve generalization is train SST with multiple masking configurations, such as varying the masking setting across batches - an avenue worth exploring in future work. Nevertheless, even when trained with a single masking configuration, there are cases where one sufficiency form may implicitly imply another, particularly when it encompasses other forms. For instance, uniform sampling within a bounded perturbation may be naturally subsumed by a robust masking strategy applied to the same perturbation.
We conducted an additional experiment in which we trained each model from the experiments in Tables
2 and 3 (covering MNIST, SNLI, and IMDB) to evaluate the impact of different masking configurations on various forms of sufficiency. The results are presented Table
Table 4: The generalization of various masking configurations to different sufficiency conditions.
Masking
Faithfulness Probabilistic
Robust
Baseline
robust
99.28
99.32
11.82
MNIST
baseline
98.91
98.38
96.52
probabilistic
98.85
99.11
8.16
baseline
44.81
95.88
SNLI
probabilistic
95.35
93.12
baseline
75.7
98.05
IMDB
probabilistic
95.67
77.7
Table 4 presents pressens results highlighting key generalization patterns across different tasks. For language tasks, we observe the following: In SNLI, probabilistic masking demonstrates high baseline faithful- ness, whereas baseline masking exhibits considerably lower probabilistic faithfulness, suggesting superior generalization under probabilistic constraints. In IMDB, both probabilistic and baseline masking achieve moderate faithfulness in the opposite masking configuration. In the MNIST ex- periment, more intricate dynamic emerges. Robust masking and probabilistic sampling remain within bounded Ep domain, while the baseline configuration is significantly out-of-distribution (OOD), making the baseline task more challenging. This is reflected in the larger subset size (23.69%) produced by SST for the baseline compared the robust and probabilistic settings. As a result, the larger sufficient reason derived from the bascline generalizes well across other configurations, maintaining high faithfulness. Conversely, subsets from probabilistic and robust masking generalize effectively to each other but perform poorly on the baseline, likely due to the baseline's pronounced OOD nature. These findings emphasize the complex interaction between domain selection, sampling distribution, and baseline properties in influencing generalization. We believe further exploration into the generalization capabilities of SST across masks presents an exciting research direction.
G.1 DISCUSSION ON VARIATIONS OF THE FAITHFULNESS METRIC
Similar the challenges that arise when generalizing across different sufficiency configurations, a similar concern extends to the evaluation of explanations - specifically, the computation of faithfulness. As with many explanation frameworks, defining a sufficient reason can be ambiguous. particularly due to the varying interpretations of "missingness" in the complement. Our work addresses this inherent limitation, which is prevalent in many post-hoc methods, by evaluating and training explanations across diverse sufficiency formulations. However, we recognize that no single definition can fully encapsulate a model's internal behavior, and this limitation also applies to faithfulness metrics assessing the sufficiency of subsets. This issue is widespread in many XAI methods, including SHAP (Sundararajan & Najmil 2020). and metrics such as infidelity (Yeh et al. 2019), where different treatments of "missing" features lead to variations in explanation definitions and evaluation metrics. By exploring diverse sufficiency criteria, our work contributes to a more comprehensive understanding of this class of explanations.
30

---

Published as a conference paper at ICLR 2025
H EXTENSIONS TO SIMPLIFIED INPUT SPACES
It is evident that SST can be trained using simplified input spaces instead of individual features such as pixels or tokens. These simplified spaces - such as super-pixels, sentences, or other meaningful units can, in some cases, enhance the human interpretability of the resulting explanations, as explored in previous works (e.g.. (Ribeiro et al. 2016 2018)). To evaluate this approach, we conducted an experiment on MNIST and CIFAR- 10, using a straightforward simplified input setting of 2 pixel patches. Accordingly, we adjusted the output vector to match the number of super- seper-pixels and applied masking at the level of these simplified inputs.
For consistency, we used the same hyperparameter choices as in the original (non-simpline input space) grid search. However, dedicated grid search for this specific configuration could yield improved results. Our findings indicate that, for MNIST, the average explanation size was 4. 4.26%, with 90.53% faithfulness and minimal accuracy drop of -0.34%. In contrast, for CIFAR-IO, we observed -4.54% accuracy drop, 91.74% faithfulness, and explanation size of 22.93%. These results suggest that, under this particular setting. the original (non-simplified) input space produced better overall performance metries. However, from human interpretability standpoint, simplified inputs can provide more intuitive and comprehensible explanations. We include examples these simplified explanations alongside their regular counterparts in Figure 6
Originial Image
SST
SST (super-pixels)
Figure 6: Examples of comparisons between explanations generated by SST using superpixels with a
2 x patch versus those based on individual pixels.
I ADDITIONAL ABLATION EXPERIMENTS
In this section, we provide additional ablation results for our experiments. Specifically, we examine the effects of varying both the ép perturbation and the step size in the robust masking experiments, as well as adjusting the selection threshold parameter. The results are summarized in Tables 5 5 7 with detailed discussion of each experiment provided separately.
1.1 VARYING THE Ep BOUUD IN ROBUST MASKING
We perform an ablation study by varying the attack in robust masking on CIFAR-10, using the same configurations in our main experiment. In general, increasing ep makes more challenging to satisfy the sufficiency conditions of the explanation. Consequently, users can select different values based on the desired "degree" of sufficiency. higher Ep can lead to larger explanation sizes and/or reduced faithfulness, depends on the relative weighting of different loss coefficients during training, which influence the optimization objectives.
it may result in decreased model accuracy. The specific metric affected
As shown in Table 5 increasing Ep within our configurations generally leads to lower faithfulness and larger explanation sizes. However, note that excessively large values of ep can reduce the effectiveness of gradient perturbations, well-known issue in adversarial training (Addepalli et al. 2022). Thus, it is not surprising that at very high perturbations (e.g., above 0.25), model accuracy deteriorates significantly. Addressing the challenges posed by such large perturbations, which is also relevant to adversarial training, remains open problem for future research.
31

---

Published as a conference paper at ICLR 2025
Table An ablation study examining the effect of varying 6p perturbations in robust masking on the CIFAR- 10 benchmark.
Table 6: An ablation study examining the effect of varying a: the step size in robust masking (with fixed Ep := 0.12 perturbation) on the CIFAR- 10 benchmark.
Ep (%)
Acc. (%)
Faith. (%)
Size (%)
0.01
-0.13
99.31
10.2
a (%)
Ácc. (%)
Faith. (%)
Size (%)
0.05
+0.7
95.09
0.91
1/255
-0.66
89.47
12.01
-1.38
91.46
9.78
2/255
-2.22
89.9
19.7
0.12
-1.96
90.43
12.99
3/255
-1.13
89.74
10.93
0.15
-1.45
88.03
11.91
4/255
-2.12
90.83
17.28
0.2
-3.32
85.34
23.49
5/255
-1.96
90.43
12.99
0.25
-4.58
79.9
17.48
6/255
-0.08
89.25
7.2
0.3
-9.92
78.88
33.9
7/255
-1.32
90.21
9.78
0.35
-3.97
70.94
19.2
8/255
-1.91
90.44
15.09
0.4
-10.25
64.95
34.53
9/255
-1.68
90.27
12.89
0.45
-14.68
64.95
34.53
10/255
-2.71
89.15
17.27
0.5
-14.09
68.05
31.99
I.2
VARYING THE STEP SIZE a IN ROBUST MASKING.
We conduct an ablation study by adjusting the step size a in adversarial training on CIFAR-10, while keeping the adversarial perturbation Cp fixed 0.12. The results are presented in Table Similar to adversarial training, smaller values of a yield adversarial examples that are closer to the original input, whereas larger values generate more distant examples. Importantly, the faithfulness measure present quantifies the proportion of test instances that remain sufficient under robust mask for each configuration, all computed using the same attack strategy (i.e., with the same a value). These findings demonstrate that model can adapt to different values, producing relatively compact and faithful explanations. However, a substantial increase in step size leads to a decline in accuracy.
Table 7: An ablation study examining the effect varying the selection threshold in probabilistic masking on the CIFAR-10 benchmark.
(0-1 range)
Acc. Gain (%)
Faith. ( (%)
Size (%)
0.1
+0.39
73.88
3.96
-0.61
81.22
5.81
0.3
-0.23
81.26
2.55
0.4
-1.57
84.68
9.80
-0.09
87.54
9.08
0.6
-1.62
88.32
12.26
0.7
-1.79
96.44
11.80
-2,08
86.97
12.63
0.9
-1.24
86.43
6.65
I.3 VARYING THE SELECTION THRESHOLD
Lastly, we performed an ablation study on different values of trained with probabilistic masking on CIFAR-10. The results are presented Table Overall, as observed in the results, our method adapts to varying values of by optimizing the model to learn different weights within the explanation component output vector. However, excessively high or low T values tend to be more sensitive and may negatively impact certain key metrics. For instance, a low setting of == 0.1 resulted in reduced faithfulness (73.8%%) while high setting of r := 0.8 led to lower accuracy (-2.08%). contrast, setting == 0.5 yielded comparable accuracy (-0.09%).
J SUPPLEMENTARY RESULTS
In this section, will present additional results support evaluations.
32

---

Published as a conference paper at ICLR 2025
J.1 MNIST
We begin by offering more image samples to contrast post-hoe explanations generated over MNIST
with SST explanations trained using robust masking, for comparison purposes.
Originial Image
SST
Anchors
6
Figure 7: Examples of comparisons between explanations produced by SST compared to post-hoc approaches for MNIST
J.2 CIFAR-10
We now transition to showcasing further comparison findings for CIFAR-10, contrasting post-hoc explanations with those generated using SST and robust masking techniques.
To further illustrate examples of explanations under various masking configurations, we conducted an ablation study using SST-based explanations on CIFAR-10. We implemented baseline masking by zeroing out the complement 5' (the trivial baseline: z z: On), probubilistic masking, where we sampled features over S from uniform distribution either over the entire input domain (e : 1) or within bounded region surrounding x (E 0.12). Additionally,
performed robust masking by exccuting a PGD foo attack within an = 0.12 ball with 10 steps each size ;= 10-2
Regarding average explanation sizes: robust masking accounted for 12.99%, probabilistic masking with = 0.12 was 9.40%, probabilistic masking with e == was 50.75% 60.75% and baseline masking was 50.8%. The average faithfulness 89.77% for baseline masking, 87 .92%% for bounded- bounded-probabillie probabilistic masking, 90.43% for robust masking, and only 15.95% for bubounded-probabbile masking. Results presented in Figure
33

---

Published as a conference paper at ICLR 2025
Originial Image
Anchees
Figure 8: Examples of comparisons between explanations produced by SST compared to post-hoc approaches for CIFAR-10
J.3 IMAGENET
Lastly, we present comparative analysis of SST-based models and post-hoc approaches for IM- AGENET. Since IMAGENET inputs are high-dimensional and individual pixels are too small to be discernible to the human eye, patch each pixel with the surrounding x 5 pixels, centering the corresponding pixel for visualization purposes. This approach applied in all visualizations of IMAGENET image results, including both SST and post-hoc methods.
In this segment, we also perform an ablation study to evaluate the performance of IMAGENET using different masking techniques. We train IMAGENET using either robust masking through PGD foo attack within an e == 0.12 ball, taking 10 steps each of size a' == 10-2, or probabilistic masking by sampling features uniformly from the same = 0.12 ball around x. The average explanation size was 0.07% for probabilistic masking (compared to 0.46% for robust masking), with faithfulness score of 80.05% (compared to 80.88% for robust masking).
J.4 IMDB
We now offer more examples of sufficient reasons produced by SST-based models, beginning with cases of IMDB sentiment analysis. As noted in the main paper, subsets derived via probabilistic masking tend to be larger compared to those from baseline masking. This difference arises because the randomness of perturbing various tokens imposes stricter constraint than simply applying
34

---

Published as a conference paper at ICLR 2025
Origitial Imago
Baseline
(x 0.12)
Rebuat
Probuhilistic = 0.12)
Probabilidti [c 1)
">>
Figure 9: An ablation study comparing between different masking techniques for CIFAR-10
fixed MASK token. Figure 12 provides further comparisons between explanations obtained through probabilistic and baseline masking methods.
35

---

Published as a conference paper at ICLR 2025
Original
Figure 10: Examples of comparisons between explanations produced by SST compared to post-hoc approaches for IMAGENET
36

---

Published as a conference paper at ICLR 2025
Robust (e 0.12)
Probabilistic (c= 0.12)
Originial Image
Figure 11: An ablation study comparing different masking techniques for IMAGENET
37

---

Published as a conference paper at ICLR 2025
Saafline-Sufticienee (negative):
Probabilistic-uufficiii (negative):
"It was lerribly bad acting dumb story. Not even a would enjoy ... Something to switch off if possible."
"It was terrilyy bad aeting dumb story even a kid would enjoy Somerhing to switeh off if possible."
Treeline-Sufticinnce (negative):
Cuobabilistic-Suffiiieeee (negative):
Worst movie ever. Mentally- scarre. Help me. It was that bad. TRUST ME!!!"
Worst movie ever. Mentally- yoarred Help me. It was that bad. TRUST ME!!!
Maseline-Suffiiiien (positive):
Probabilistti- CiiabllistieSSufficiennyyy (positive): has everything a movie should have. You really should Get this one."
"It evervzhing movie should have. You really should Get this one."
Baseline Sufficiency (negative):
Probabilistic Sufficiency (negative):
"a huge mistake by doing this film The best word describe is STUPID!
"a huge mistake by doing this film The best word to describe it STUPID!
Figure 12: IMDB sentiment analysis sufficient reasons that were inherently generated using SST (baseline probabilistic)
J.5 SNLI
Here, we illustrate examples of sufficient reasons generated by SST-based models for the SNLI classification tasks. In this task, the input contains both a premise and hypothesis and the classi- fication task is to determine the nature of their relationship, categorized as follows: (i) entailment, where the hypothesis is logical consequence of the premise; (ii) contradiction, where the hypothesis is logically inconsistent with the premise; and (iii) neutral, where the hypothesis neither logically follows from nor contradicts the premise.
Probabilistic Sufficient reason (contradiction):
"Premise: A man wearing dark fonee boots, green cape. and g hat with hee big features on the front is sitting.
Lyyothessis: A man in @ red cape and a hat with three feathers sirs by himself."
Baseline Sufficient reason (neutral);
"Premise: old man pink pole ... with small child standing
Hypothesis: An old glephant through telescope small child standing next to him.
Probabilistic Sufficient reason (contradiction):
"Premise: ... black leather shirt trench- coat ... faces away ... visible just front of her.
Hypothesis: ... black leather Irench
walks awwny with her bag strapped to her shoulders.
Figure 13: Sufficient reasons that inherently generated using SST for the SNLI benchmark
38


Reviews:
[{"review_id": "TcTu45eTUb", "reviewer": "Reviewer_NPb3", "summary": "This paper proposes a new training method called Sufficient Subset training, which proposes learning neural networks with a dual objective that first predicts the label but also predicts a mask of sufficient inputs that is enough to predict the object. They show that training a network this way gives faithful sufficient subset explanations, that are often smaller than those generated with post-hoc methods, and much faster to produce.", "questions": "- What's stopping the model from learning a \"cheating\" solution such as it almost always only looks at a certain subset of the inputs and this subset is always the explanation? This would probably not be what we want?\n- What is the robustness of your different masking strategies on Table 2 and Table 3 when evaluated in a setting not trained on?\n- Is the epsilon ball used too small? Theoretically the robust sufficient reasons case should be harder than baseline etc, but seems like you can learn much smaller explanations with this method. As an extreme case, an adversarially robust model could have a sufficient explanation of size 0 and still be faithful in this metric, but this seems pretty detached from the idea of sufficient explanation.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Very well written, the description of previous works in terms of 3 definitions is particularly clear and helpful. \n- Interesting theoretical results justifying the use of training time intervention\n- Clever and relatively simple method\n- Some good results, especially on MNIST", "weaknesses": "- Decent loss in performance/overall less impressive results on ImageNet and BERT\n- Table 2 and 3 missing sufficiency results of your models on the metric it wasn't trained on. Seems unfair to report baselines on all metrics but your methods only under the best metric.\n    - I'm worried the self-explanation might overfit to the specific training scenario and not work well in other settings.\n- Having very disjoint input sets looks pretty weird for image explanations, what do you think is the use case for this type of explanation? Overall could use some more discussion on why sufficiency explanations are useful/what is the proposed use case. Have you experimented with favoring more continuous regions?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wWPwe53eD0", "reviewer": "Reviewer_GpEy", "summary": "The authors propose a novel training framework called Sufficient Subset Training, aimed at generating minimal sufficient reasons as integral outputs of neural networks. \n\nUnlike post-hoc methods that face computational challenges and out-of-distribution (OOD) concerns, SST directly incorporates the explanation generation process during training. \n\nThis is achieved by adding dual propagation and integrating two additional losses: (i) a faithfulness loss for ensuring sufficiency and (ii) cardinality loss for promoting minimal subsets. The method is validated through experiments on various image and language tasks, demonstrating that it provides concise, faithful, and efficient explanations, outperforming several post-hoc methods at finding minimal subset.", "questions": "- Could we incorporate some prior like finding mask in a lower dimensional subspace (7x7 grid of the original image) to allow a smoother explanation and more tractable problem for the model ? I think this would be valuable for both interpretability purpose and theoretical verficiation (it become easier to generate gt).\n- How does the method's approach compare when applied to more interpretable models (e.g., decision trees)?\n- Can the SST approach provide insights into potential biases in training data by analyzing consistent feature patterns?\n\n\n**Overall, while the theoretical considerations and framework of the paper are strong, the practical interpretability of models remains underexplored. Despite this, the proposed method is an interesting step toward integrating explanation generation within model training, justifying an acceptance with room for further practical development.**", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The introduction of SST as a self-explaining mechanism is novel and could be impactful for fields focusing on model interpretability.\n- The paper thoroughly defines different sufficiency types and explains how SST addresses them through tailored masking strategies.\n- The experiments cover a range of datasets and architectures, showing that SST can be applied across different domains.\n- The theoretical analysis on the intractability of obtaining minimal sufficient reasons adds depth to the contribution.", "weaknesses": "However, I have identified some issues, both major (**M**) and minor (**m**), that require attention.\n\n**M1** Real Practical Insights Are Limited:  while the theoretical framework and empirical demonstrations are solid, the practical insights into what we learn about the internal workings of neural networks are minimal. The method emphasizes explanation generation without significantly advancing our understanding of how or why models arrive at decisions. Addressing this could bridge the gap between theoretical contributions and **practical interpretability**.\n\n**M2** Validity of Faithfulness Metrics: the paper does not thoroughly discuss the potential limitations of the faithfulness metric used in the evaluation. Faithfulness as defined could lead to explanations that superficially appear sufficient but do not align with internal mechanism or key feature used by the model. Say it otherwise, the model may be using completely different strategy to classify x and xS; zS¯.\n\n**M3** Limited Hyperparameter Discussion: the paper mentions tuning the cardinality loss coefficient but provides no analysis on the impact / visual results of tuning the hyperparameters. What are the results of adjusting \\( \\tau \\), step size \\( \\alpha \\) in robust masking. A sensitivity analysis would add valuable context.\n\nNow for the minors (**m**) issues:\n\n**m1** Related Work Section Is Limited:  \nThe related work section lacks depth, with insufficient coverage of recent advancements in XAI and self-explaining methods, especially those published in top venues over the last few years.\n\n**m2** Justification for Masking Strategies:  \nThe choice of certain masking strategies (e.g., baseline and probabilistic) could be better justified. Also, could some baseline lead to better results / scores ? Overall, the rationale for selecting these over alternative approaches should be discussed in more detail.\n\n**m3** Typos and Clarity:  \nI havent found a lot of typo, just \"probablistic\" (should be \"probabilistic\").", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vdjWQDBoiZ", "reviewer": "Reviewer_wp7b", "summary": "This paper aims at the generation of minimal sufficient reasons for model decision explanation. The authors provide theoretical results on the intractability of getting cardinally minimal explanations under specific settings, showing the difficulty of this problem. The authors also propose a new self-supervised approach called sufficient subset training to reduce cost for generating faithful sufficient reasons and reduce sensitivity to OOD examples.", "questions": "1. In Table 2, how is the faithfulness of SST training using different masking strategy in training? It will be interesting to see if model trained with specific masking stretagy also generalizes to other faithfulness metrics. \n2. In Figure 4, is Cardinality Mask Size (%) axis refering to the percentage of mask size? According to the figure, cardinality goes to 0.5% instead of 50% as discussed in Line 428-429.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper provides rigourous theoretical results on the computational complexity of generating minimal sufficient reasons in different settings. \n* The paper is well-written and easy to follow. \n* The proposed SST method provides an elegant and computationally efficient way to generate a sufficient reason. The experiment results show strong scalibility to larger datasets.", "weaknesses": "While the paper presents rigorous theoratical results and a novel empirical method, it's a bit unclear to me how these two contributions are connected. Discussion on how the theoratical analysis motivates the SST method could make the paper more integrated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)