Pith. sign in

REVIEW 5 major objections 5 minor 53 references

Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons

T0 review · 5 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read By training a network with a second head that produces a mask, SST yields concise sufficient-reason explanations in one forward pass, far faster than post-hoc search.

desk verdict Genuinely useful training-time sufficient-reason method with real speed gains, but the faithfulness evaluation is too aligned with the training objective to support the headline comparison by itself. read the letter →

arxiv 2502.03391 v3 pith:CAC5UAJ2 submitted 2025-02-05 cs.LG cs.LO

Shahaf Bassan , Ron Eliav , Shlomit Gur This is my paper · ORCID
classification cs.LGcs.LO
keywords sufficientreasonsminimalsubsetsself-explainingneuralnetworksfaithfulnesscardinalitylossdualpropagationmaskingstrategiesexplanationcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Minimal sufficient reasons—the smallest subset of input features that, held fixed at their observed values, keeps the model's prediction unchanged—are a natural form of explanation, but finding them after training is computationally intractable and relies on sampling out-of-distribution counterfactuals. The paper proposes sufficient subset training (SST), which trains the network to emit such a subset as part of its output, using a second explanation head and a dual forward pass that checks whether the masked input reproduces the original prediction. Two extra losses enforce that the subset is faithful and small, and the choice of how the excluded features are filled in (fixed baseline, random sampling, or adversarial perturbation) produces baseline, probabilistic, or robust sufficient reasons. Across MNIST, CIFAR-10, ImageNet, IMDB, and SNLI, SST finds explanations in microseconds to milliseconds that are generally smaller or more faithful—and often both—than those of Anchors, SIS, and gradient search, with comparable accuracy.

What carries the argument

The load-bearing mechanism is the learned explanation head $h_2$, a sigmoid output layer that shares hidden layers with the predictor $h_1$; thresholding it at $\tau$ selects the subset $S$. A second forward pass constructs the masked input $(x_S; z_{\bar S})$ by keeping $S$ at the original values and filling the complement with either a fixed baseline $z$, samples from a distribution $D$, or projected-gradient-descent adversarial perturbations, and the faithfulness loss $L_{\mathrm{fait h}} = \mathrm{CE}(h_1(x_S; z_{\bar S}), \arg\max_j h_1(x)_j)$ forces the subset to be sufficient. The cardinality loss $L_{\mathrm{card}} = \lVert h_2(x) \rVert_1$ pushes $S$ to be small, and the total loss is $L_{\mathrm{pred}} + \lambda L_{\mathrm{fait h}} + \xi L_{\mathrm{card}}$. The same dual-propagation construction appears in the hardness proofs, where the difficulty of verifying sufficiency over continuous domains is reduced to neural-network reachability and to CNF-SAT, Shortest-Implicant-Core, and Max-Clique.

What would settle it

Take a held-out evaluation where the complement of the sufficient reason is filled from a distribution completely different from the SST training mask—for example, train with baseline masking and evaluate with random token or patch substitutions, or use paraphrases of the input—and compare SST with post-hoc methods that are also evaluated under that same held-out rule; if SST's faithfulness margin over Anchors and SIS disappears or reverses, the central claim that training-time masking removes OOD sensitivity would be refuted.

Watch

Extended reading notes

Core claim

The central claim is that a neural network can be trained to generate concise sufficient reasons for its own predictions as an integral part of its output, and that doing so removes the two obstacles that plague post-hoc explanation search. The paper first sharpens those obstacles: it proves that finding a cardinally minimal sufficient reason for a ReLU network is NP-complete for baseline sufficiency, $\Sigma_2^P$-complete for robust sufficiency, and $\mathit{NPPP}$-hard for probabilistic sufficiency (Theorem 1), and that approximating the cardinally minimal size is NP-hard or $\Sigma_2^P$-hard (Theorem 2). It then shows that SST—optimizing the prediction loss plus a faithfulness loss between the masked-input prediction and the original prediction plus an $\ell^1$ cardinality loss—produces subsets that are faithful under the corresponding masking distribution, much smaller on image benchmarks than gradient-based and anchor-style methods, and obtained orders of magnitude more quickly. The authors report 99.28% robust faithfulness on MNIST with 1.42% average subset size, 90.43% robust faithfulness on CIFAR-10 with 12.99% size, and 0.46% mean subset size on ImageNet with 80.88% robust faithfulness, while language models retain accuracy within about one percentage point.

Load-bearing premise

The load-bearing assumption is that 'faithfulness' is correctly measured by the training-time masking rule: a subset is faithful when, after filling the excluded features with the baseline, random sample, or PGD perturbation used during SST training, the model still predicts the original class; if that metric overstates the quality of self-generated explanations, the reported efficiency and faithfulness gains over post-hoc methods may not transfer to other definitions of sufficiency.

Editorial extensions

If this is right

  • On image benchmarks, robust-masked SST explanations are produced in roughly $10^{-6}$ to $10^{-4}$ seconds per input, compared with 0.11 to 266 seconds for the post-hoc baselines, so sufficient-reason extraction no longer requires a separate expensive search step.
  • SST subsets are typically smaller than Anchors and gradient search and more faithful than SIS; on MNIST, SST reaches 99.28% robust faithfulness with a 1.42% mean mask, versus 97.51% at 8.98% size for Anchors.
  • The masking strategy is a tunable design choice: baseline masking yields larger subsets and generalizes across sufficiency settings on MNIST, while probabilistic and robust masking yield very small subsets but transfer less well to baseline evaluation.
  • The hardness theorems imply that no polynomial post-hoc algorithm can reliably find cardinally minimal sufficient reasons for general ReLU networks, so any scalable method must either relax optimality or change the training objective, the route SST takes.
  • Language models trained with SST maintain accuracy within about one percentage point while reaching 98.05% baseline faithfulness on IMDB, where similarity-based Anchors reaches only 23.37%.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the faithfulness metric is the loss SST is trained to minimize, part of the reported advantage may be a measurement artifact: post-hoc methods are scored under a masking distribution they never saw during training; a neutral test would let post-hoc methods tune their sampling distributions on the same objective.
  • The explanation head records what the model has learned to depend on under the chosen masking rule, not an independent ground-truth cause; if the training distribution shifts, the sufficiency of these masks should be re-verified rather than assumed.
  • SST's mask can be read as a learned feature-selection policy, so the method could be lifted to hierarchical or structured inputs—super-pixels, sentences, or groups of tokens—if the threshold and cardinality loss are applied at the group level; the paper's super-pixel experiment suggests this is feasible but currently less accurate than pixel-level masks.
  • A direct extension would be to train with multiple masking strategies per batch, which the paper identifies as future work; the cross-mask generalization numbers suggest such mixture training could produce a single model whose explanations are simultaneously faithful under baseline, probabilistic, and robust evaluation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper introduces sufficient subset training (SST), a method that augments a neural network with an explanation head that outputs a mask over input features. The model is trained with three losses: a standard prediction loss, a faithfulness loss that requires the prediction on the masked input (features in the selected subset fixed to their original values, complement replaced by a baseline, sampled values, or adversarial perturbations) to match the original prediction, and a cardinality loss that encourages small masks. The authors report complexity results showing that finding cardinally minimal sufficient reasons is intractable (NP-complete, Sigma_2^P-complete, or NP^PP-hard depending on the sufficiency notion), and provide approximation-hardness results. Empirically, SST is evaluated on MNIST, CIFAR-10, ImageNet, IMDB, and SNLI, comparing explanation size, runtime, and faithfulness against post-hoc methods Anchors, SIS, and gradient search (GS). The central claim is that SST produces succinct and faithful sufficient reasons substantially more efficiently than post-hoc methods while maintaining comparable predictive accuracy.

Significance. If the empirical results hold up, SST is a meaningful contribution: it moves sufficient-reason generation from expensive post-hoc search to a single forward pass, and the multi-domain evaluation (vision and language) supports generality. The paper also provides potentially useful hardness proofs and releases code. However, the central empirical claim is currently weakened by (i) a faithfulness metric that is aligned with SST's own training objective, (ii) absence of error bars or multiple-seed results, and (iii) a missing control that isolates the effect of the learned mask. The theoretical contribution also contains a proof inconsistency in the approximation-hardness reduction for baseline sufficient reasons. These issues are fixable and do not, in my assessment, invalidate the overall approach, but they require substantiation before the claims can be accepted.

major comments (5)
  1. [Section 5.1, Eq. (6), Table 1] The robust faithfulness metric is reported as the proportion of test points for which the extracted subset remains sufficient under an ℓ∞ ball, but the operational check is a PGD search over the complement using the same ϵ=0.12, 10 steps, and step size used in Eq. (6). SST is trained against this exact attack, so a high score can reflect invariance along the attack trajectory without satisfying Definition 2 for all z in the ball. Post-hoc methods are evaluated under this metric without having been trained for it, which may understate their true robust sufficiency. Please add a verification-based evaluation on at least MNIST (e.g., with a complete verifier), or, at minimum, evaluate with a stronger or different attack and report whether the PGD-based scores are stable.
  2. [Section 5, Tables 1-4] All quantitative comparisons are reported as single runs without error bars or multiple seeds. The differences between SST and post-hoc methods are sometimes small or reversed: in Table 1, on CIFAR-10, robust faithfulness for SST is 90.43% vs. 92.41% for GS; on ImageNet, SST is 80.88% vs. 90.92% for GS. These results do not statistically support the claim that SST is 'faithful' in addition to being efficient. Please provide mean±std over at least 3 seeds and significance tests for the main comparisons.
  3. [Section 4.1, Eq. (5)] The mask is defined by the hard threshold S := {i | h2(x)_i ≥ τ}, and the faithfulness loss is computed by propagating the masked input (x_S; z_\bar{S}) through the model. However, the paper does not describe how gradients of L_faith flow back to h2 through this discrete masking operation. Without a differentiable relaxation (e.g., Gumbel-sigmoid, soft mask, or straight-through estimator), the training objective in Eq. (4) is not well-defined. Please specify the exact gradient approximation used for the mask.
  4. [Appendix D, Lemma 10] The reduction from Max-Clique for baseline sufficient reasons contains an inconsistency: the theorem statement defines S := E \ C (an edge-set difference), while the proof asserts that vertices u,v ∈ C 'also belong to S' and that their features are modified from 0 to 1. If S is intended to be the complement of the clique (V \ C), then vertices in C are not in S and the argument about modified features is wrong. If S is intended to be C, then the reduction direction and the cardinality-minimality argument do not match Max-Clique. As written, the proof does not establish the NP-hardness of approximating cardinally minimal baseline sufficient reasons, and Theorem 2(ii) is not supported. Please correct the definition or provide a valid approximation-preserving reduction.
  5. [Section 5, Tables 1-4] The central contribution is a learned mask, but the experiments do not include a control in which the mask is chosen randomly or by an input-independent rule under the same dual-propagation training. Such a control is needed to attribute the observed gains to the learned selection mechanism rather than to the training procedure itself. Please add an ablation with a fixed/random mask of matched size, or with an SST variant in which h2 is not trained.
minor comments (5)
  1. [Abstract and Section 4] The abstract describes SST as a 'self-supervised training approach', but the training uses ground-truth labels and cross-entropy losses; 'self-supervised' is misleading. Consider 'self-explaining' or 'multi-task'.
  2. [Section 5.1, Figure 4] The direction of the effect of ξ on mask size is stated inconsistently: the Figure 4 caption says 'higher ξ increases mask size S', while the text says 'For greater ξ values, the cardinality of the mask is maximal' and 'As ξ → 0, the explanation size converges to 50%'. Please clarify whether larger ξ yields larger or smaller masks, and correct the wording.
  3. [Appendix F.1] The sentence about ImageNet training times is confusing: 'standard training using the robust masking configuration ran for 287056.81 seconds' is immediately followed by 'the parallel standard-training configuration for IMAGENET ran for 74141.85 seconds'. It is unclear which configuration is SST and which is standard. Please rewrite.
  4. [Section 3, Theorem 2] The theorem statement is typeset with missing superscripts ('n1−ϵ', 'n 1 2 −ϵ'), making the approximation factors hard to read. Please fix the notation.
  5. [Section 5.1 and Eq. (6)] The evaluation protocol for robust faithfulness is not fully specified: it is not stated whether the PGD attack at test time uses multiple restarts, the same number of steps as training, or the same initialization. Please state the exact test-time procedure.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SST's faithfulness evaluation is its own training objective measured on held-out inputs, not a fitted parameter renamed as a prediction, and the complexity claims rest on independent reductions.

full rationale

The paper's central derivation is a training procedure plus an empirical evaluation, not a quantity derived from its own definition. The faithfulness loss (Eq. 5) is a soft cross-entropy objective on masked inputs, while the reported faithfulness is the hard proportion of held-out test instances where the extracted subset preserves the prediction under the corresponding masking procedure. This is a standard train/test separation: the model is optimized on the training split and evaluated on the test split, so the reported numbers are empirical, not forced by construction. The robust faithfulness metric uses the same PGD attack used in training, which is a threat-model choice and a limitation of the robustness claim (attack-based rather than formally verified), but the paper operationally defines robust faithfulness via that masking procedure and never claims verified sufficiency over the whole ball. The theoretical results (Theorems 1 and 2) are supported by explicit reductions from CNF-SAT, Shortest-Implicant-Core, and Max-Clique, with prior work cited only for binary base cases; the extension to continuous domains is argued in the appendix and does not reduce to a self-citation. Self-citations such as Bassan & Katz (2023), Bassan et al. (2024), and Amir et al. (2024) appear in related-work context and evaluation conventions but are not load-bearing for the main derivation. No equation is shown to be identical to another by construction, and no fitted parameter is relabeled as a prediction, so no circular step meets the evidentiary bar.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The method relies on standard complexity-theoretic reductions from the cited literature, on the ReLU-encoding lemma, and on the domain assumption that the self-referential faithfulness objective is a valid measure of explanation quality. One ad hoc assumption is the claimed approximation-preservation of the Max-Clique reduction in Theorem 2(ii), which is not proven.

free parameters (5)
  • cardinality coefficient ξ = 10^-7 to 10^-11 (images), 10^-4 to 10^-8 (language)
    Grid-searched per benchmark and masking type; controls subset size vs faithfulness tradeoff (Eq. 4).
  • faithfulness coefficient λ = 1
    Fixed to 1 for all experiments; part of combined loss (Eq. 4).
  • selection threshold τ = 0.5
    Fixed default; explanation set S = {i | h2(x)_i ≥ τ}. Tradeoff shown in Appendix I.3.
  • robust masking radius ϵ = 0.12 (ℓ∞)
    Chosen by hand as a balance; used for PGD robust masking and evaluation.
  • PGD steps and step size = N=10, α'=10^-2
    Parameters of the adversarial masking procedure (Eq. 6).
assumptions (5)
  • standard math ReLU network encoding of Boolean circuits (Lemma 3) from Barceló et al. (2020)
    Used in all hardness reductions to convert CNF/DNF formulas to MLPs.
  • standard math Inapproximability of Shortest Implicant Core (Umans 1999) and Max-Clique (Håstad 1999)
    Basis for Theorem 2 approximation hardness.
  • domain assumption Faithfulness loss with target argmax_j h1(x)_j is a valid measure of sufficiency
    The paper equates training alignment with faithfulness; evaluation uses the same self-referential target (Eq. 5).
  • domain assumption Masked inputs (x_S; z_\bar{S}) during training are representative of evaluation-time OOD inputs
    SST's OOD mitigation rests on this; post-hoc methods do not get this training exposure.
  • ad hoc to paper The Max-Clique reduction in Lemma 10 is approximation-preserving
    The paper asserts the approximation result follows from the exact reduction without proving gap preservation; the mapping between clique size and sufficient-reason size is subtractive (n - ω), which does not generally preserve multiplicative approximation factors.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons." pith.science (2026). https://pith.science/paper/CAC5UAJ2

@misc{pith2026250203391,
  author       = {Pith},
  title        = {Pith review of: Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CAC5UAJ2}},
  note         = {Machine review of arXiv:2502.03391}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2502.03391 by the authors.

Figure 1
Figure 1. An example of a sufficient reason generated by a model trained with [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. An illustration of the dual propagation incorporated during sufficient subset training [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Examples of sufficient reasons produced by SST compared to the ones generated by post [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: The faithfulness-cardinality 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. Faithfulness-Cardinality Trade-off. Optimizing models train…
Figure 5
Figure 5. Figure 5: Explanations generated by SST using baseline vs. probabilistic masking. When each [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: Examples of comparisons between explanations generated by SST using superpixels with a [PITH_FULL_IMAGE:figures/full_fig_p031_6.png]
Figure 7
Figure 7. Figure 7: Examples of comparisons between explanations produced by [PITH_FULL_IMAGE:figures/full_fig_p033_7.png]
Figure 8
Figure 8. Figure 8: Examples of comparisons between explanations produced by [PITH_FULL_IMAGE:figures/full_fig_p034_8.png]
Figure 9
Figure 9. Figure 9: An ablation study comparing between different masking techniques for CIFAR-10 [PITH_FULL_IMAGE:figures/full_fig_p035_9.png]
Figure 10
Figure 10. Figure 10: Examples of comparisons between explanations produced by [PITH_FULL_IMAGE:figures/full_fig_p036_10.png]
Figure 11
Figure 11. Figure 11: An ablation study comparing different masking techniques for IMAGENET [PITH_FULL_IMAGE:figures/full_fig_p037_11.png]
Figure 12
Figure 12. Figure 12: IMDB sentiment analysis sufficient reasons that were inherently generated using SST [PITH_FULL_IMAGE:figures/full_fig_p038_12.png]
Figure 13
Figure 13. Figure 13: Sufficient reasons that were inherently generated using SST for the SNLI benchmark [PITH_FULL_IMAGE:figures/full_fig_p038_13.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 38 canonical work pages

  1. [1]

    Appendix E contains technical specifications, related to the models, and training

    Appendix D contains the proof of theorem ii. Appendix E contains technical specifications, related to the models, and training. Appendix F contains information regarding the training time of SST compared to standard training. Appendix Gincludes an experiment on the generalization of various masks across different sufficiency settings. Appendix H includes ...

    work page 2018

  2. [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 ϵ is provided as input), followed by an explanation of how we can extend this proof to a specificϵ-bounded domain. Given an instance ⟨f, S,x⟩ we can con...

    work page 2020

  3. [3]

    We will now begin by introducing the reduction for binary-input-output MLPs from the Shortest- Implicant-Core problem (Barceló et al

    Any boolean circuit ϕ can be encoded into an equivalent MLP over the binary domain {0, 1}n → {0, 1} in polynomial time. We will now begin by introducing the reduction for binary-input-output MLPs from the Shortest- Implicant-Core problem (Barceló et al. (2020)). The Shortest-Implicant-Core problem is defined as follows: Shortest Implicant Core: Input: A f...

    work page 2020

  4. [4]

    missingness

    Table 4: The generalization of various masking configurations to different sufficiency conditions. Masking Faithfulness Robust Probabilistic Baseline robust 99.28 99.32 11.82 MNIST baseline 98.91 98.38 96.52 probabilistic 98.85 99.11 8.16 SNLI baseline — 44.81 95.88 probabilistic — 95.35 93.12 IMDB baseline — 75.7 98.05 probabilistic — 95.67 77.7 Table 4 ...

    work page 2020

  5. [5]

    A Large Annotated Corpus for Learning Natural Language Inference

    Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A Large Annotated Corpus for Learning Natural Language Inference. arXiv preprint arXiv:1508.05326,

    arXiv

  6. [6]

    We first note a known inapproximability result for the Shortest-Implicant-Core prob- lem (Umans (1999)) which will be used to prove the inapproximability result for our case: Lemma

    Given a neural network classifier f with ReLU activations, and x ∈ Rn, ∀ϵ > 0 approximating cardinally minimal robust sufficient reasons withn 1 2 −ϵ factor (i.e., solving theR-MSR∗ query) is ΣP 2 -Hard Proof. We first note a known inapproximability result for the Shortest-Implicant-Core prob- lem (Umans (1999)) which will be used to prove the inapproxima...

    work page 1999

  7. [7]

    We acknowledge, however, that despite the difficulty of theMSR query being established through a reduction from the Shortest Implicant Core problem (as proven in Barceló et al

    Given a DNF formula ψ, then for all ϵ >0, approximating the Shortest Implicant Core of ψ to within factor n1−ϵ is ΣP 2 -Hard. We acknowledge, however, that despite the difficulty of theMSR query being established through a reduction from the Shortest Implicant Core problem (as proven in Barceló et al. (2020) and discussed in Lemma 1), this approach cannot...

    work page 2020

  8. [8]

    On the Reasons Behind Decisions

    Adnan Darwiche and Auguste Hirth. On the Reasons Behind Decisions. In ECAI 2020, pp. 712–720. IOS Press,

    work page 2020

Show all 53 references
  1. [9]

    33 Published as a conference paper at ICLR 2025 Figure 8: Examples of comparisons between explanations produced by SST compared to post-hoc approaches for CIFAR-10 J.3 IMAGENET Lastly, we present a comparative analysis of SST-based models and post-hoc approaches for IM- AGENET...

    2025

  2. [10]

    ERASER: A Benchmark to Evaluate Rationalized NLP Models

    Jay DeYoung, Sarthak Jain, Nazneen Fatema Rajani, Eric Lehman, Caiming Xiong, Richard Socher, and Byron C Wallace. ERASER: A Benchmark to Evaluate Rationalized NLP Models. arXiv preprint arXiv:1911.03429,

    1911 arXiv

  3. [11]

    Concept Embedding Models: Beyond the Accuracy-Explainability Trade-off

    12 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 th...

    2025

  4. [12]

    On Efficiently Explaining Graph-Based Classifiers

    Xuanxiang Huang, Yacine Izza, Alexey Ignatiev, and Joao Marques-Silva. On Efficiently Explaining Graph-Based Classifiers. In International Conference on the Principles of Knowledge Representa- tion and Reasoning 2021, pp. 356–367. Association for the Advancement of Artificial ...

    2021

  5. [13]

    On Explaining Decision Trees

    Yacine Izza, Alexey Ignatiev, and Joao Marques-Silva. On Explaining Decision Trees. arXiv preprint arXiv:2010.11034,

    2010 arXiv

  6. [14]

    Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation

    13 Published as a conference paper at ICLR 2025 Yacine Izza, Xuanxiang Huang, Antonio Morgado, Jordi Planes, Alexey Ignatiev, and Joao Marques- Silva. Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation. arXiv preprint arXiv:2405.08297,

    2025 arXiv

  7. [16]

    A Comprehensive Survey on Self-Interpretable Neural Networks

    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,

  8. [17]

    Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks

    Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J 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...

    2017

  9. [21]

    Logic-based Explainability in Machine Learning

    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,

    2022

  10. [22]

    On the Tractability of SHAP Explanations under Markovian Distributions

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

    arXiv

  11. [23]

    SELFEXPLAIN: A Self-Explaining Architecture for Neural Text Classifiers

    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 in Natural Language Processing, pp. 836–850,

    2021

  12. [24]

    Reachability is NP-Complete Even for the Simplest Neural Networks

    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. Springer,

    2021

  13. [25]

    A Symbolic Approach to Explaining Bayesian Network Classifiers

    Andy Shih, Arthur Choi, and Adnan Darwiche. A Symbolic Approach to Explaining Bayesian Network Classifiers. arXiv preprint arXiv:1805.03364,

    arXiv

  14. [26]

    Unsupervised Commonsense Question Answering with Self-Talk

    Vered Shwartz, Peter West, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Unsupervised Commonsense Question Answering with Self-Talk. arXiv preprint arXiv:2004.05483,

    2004 arXiv

  15. [27]

    Probabilistic Explanations for Linear Models

    Bernardo Subercaseaux, Marcelo Arenas, and Kuldeep S Meel. Probabilistic Explanations for Linear Models. arXiv preprint arXiv:2501.00154,

    arXiv

  16. [28]

    The many Shapley Values for Model Explanation

    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,

    2025

  17. [29]

    Comprehensive Attribution: Inherently Ex- plainable Vision Model with Feature Detector

    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,

    2025

  18. [30]

    Appendix B contains background for the computational complexity proofs

    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 B contains background for the computational complexity proofs. Appendix C cont...

    2025

  19. [33]

    concepts

    and advocates for training architectures that inherently provide interpretations for their decisions (Lee et al., 2022; Shwartz et al., 2020; Rajagopal et al., 2021; Guyomard et al., 2022; Guo et al., 2023; Zhang et al., 2022; Ji et al., 2025). This idea is closely related to ...

    2022

  20. [34]

    prototypes

    and representative training- data “prototypes”(Chen et al., 2019a; Keswani et al., 2022; Hong et al., 2023). Additionally, related work explores training interventions designed to improve feature selection capabilities (Lemhadri et al., 2021; Zhang et al., 2024; Jethani et al....

    2009

  21. [35]

    Given a neural network classifier f with ReLU activations, and x ∈ Rn, obtaining a cardinally minimal sufficient reason for ⟨f, x⟩ is (i) NP-Complete for baseline sufficient reasons (ii) ΣP 2 -Complete for robust sufficient reasons and (iii)NPPP-Hard for probabilistic sufficie...

    2020

  22. [36]

    Solving the R-MSR query over a neural network classifier f, an input x ∈ Rn, and (possibly), some ϵ > 0, where f has either discrete or continuous input and output domains is ΣP 2 -Complete. Proof. Our proof is an extension of the one provided by the work of Barceló et al. (20...

    2020

  23. [38]

    An implicant C for ϕ is a partial assignment of the variables of ϕ such that any assignment to the remaining variables evaluates to true

    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 to true. The reduction also makes use in the following Lemma (whose proof appears in Barceló et al. (2020)): Lemma

    2020

  24. [40]

    Conversely, if o2,2 = 0, then o2,1 = o2,2, and thus f ′ is classified under o2,1 by virtue of o2,1 ≻ o2,2

    This condition arises because if o2,1 ̸= 0, then it necessarily means that o2,2 > o2,1 23 Published as a conference paper at ICLR 2025 resulting in f ′ being classified under o2,2. Conversely, if o2,2 = 0, then o2,1 = o2,2, and thus f ′ is classified under o2,1 by virtue of o2...

    2025

  25. [41]

    We must demonstrate that under these circumstances, the prediction for f ′ still stabilizes at o2,2. For this particular feature zi, it is confirmed that: ReLU( 1 2 − zi) + ReLU(zi − 1 2 ) − 1 2 ̸= 0 (17) This also suggests that within the newly constructed hidden layers of f ...

    2025

  26. [42]

    Solving the P-MSR query on a neural network classifier f is NPPP-Hard. Proof. The reduction is derived by integrating the proof from Wäldchen et al. (2021) with Lemma

    2021

  27. [43]

    (2021)) established that finding a cardinally minimal probabilistic sufficient reason for a CNF classifier, given a discrete uniform distribution over{0, 1}n, is NPPP-Hard

    The work in (Wäldchen et al. (2021)) established that finding a cardinally minimal probabilistic sufficient reason for a CNF classifier, given a discrete uniform distribution over{0, 1}n, is NPPP-Hard. Using Lemma 3, we can transform ψ into an MLP f, applicable to either discr...

    2021

  28. [46]

    Given a neural network classifier f with ReLU activations, and x ∈ Rn, ∀ϵ > 0 approximating cardinally minimal probabilistic sufficient reasons withn1−ϵ factor is NP-Hard This result can be extracted from the inapproximability results for obtaining cardinally minimal probabili...

    2021

  29. [47]

    This reduction is approximation preserving, as both k′ := k and n′ := n, indicating that the same approximation ratio is preserved

    We begin with ψ and develop an MLP f, ensuring that a cardinally minimal sufficient reason applicable to f is also valid 26 Published as a conference paper at ICLR 2025 for ψ. This reduction is approximation preserving, as both k′ := k and n′ := n, indicating that the same app...

    2025

  30. [48]

    Given a neural network classifier f with ReLU activations, and x ∈ Rn, ∀ϵ > 0 approximating cardinally minimal baseline sufficient reasons with n1−ϵ factor is NP-Hard We will perform an approximation preserving reduction from the Max-Clique problem, which is known to be hard t...

    1999

  31. [49]

    From the previous claim, it follows directly that a sufficient reason S is of minimal cardinality if and only if the cardinality of E \ C is minimal (when C is a clique in G)

    This confirms that S is a sufficient reason concerning the baseline 1n. From the previous claim, it follows directly that a sufficient reason S is of minimal cardinality if and only if the cardinality of E \ C is minimal (when C is a clique in G). This is equivalent to requiri...

    2018

  32. [51]

    I A DDITIONAL ABLATION EXPERIMENTS In this section, we provide additional ablation results for our experiments

    Figure 6: Examples of comparisons between explanations generated by SST using superpixels with a 2 × 2 patch versus those based on individual pixels. I A DDITIONAL ABLATION EXPERIMENTS In this section, we provide additional ablation results for our experiments. Specifically, w...

    2022

  33. [52]

    However, excessively high or lowτ values tend to be more sensitive and may negatively impact certain key metrics

    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τ values tend to be more sensitive and may negatively impact certain...

    2025

  34. [2009]

    On Guaranteed Optimal Robust Explanations for NLP Models

    Emanuele La Malfa, Agnieszka Zbrzezny, Rhiannon Michelmore, Nicola Paoletti, and Marta Kwiatkowska. On Guaranteed Optimal Robust Explanations for NLP Models. arXiv preprint arXiv:2105.03640,

    arXiv

  35. [2011]

    Towards Deep Learning Models Resistant to Adversarial Attacks.arXiv preprint arXiv:1706.06083,

    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 arXiv:1706.06083,

    2025 arXiv

  36. [2012]

    Bert: Pre-Training of Deep Bidirectional Transformers for Language Understanding

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-Training of Deep Bidirectional Transformers for Language Understanding. arXiv preprint arXiv:1810.04805,

    arXiv

  37. [2016]

    Furthermore, the robust class of sufficient explanations studied in this work also connects to research in formal logic (Marques-Silva, 2023; Darwiche & Marquis, 2021)

    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., 2021). Furthermore, the robust class of sufficient explanations studied in this work also connects to research in formal logic (Ma...

    2021

  38. [2017]

    You Only Explain Once

    David A Kelly, Hana Chockler, Daniel Kroening, Nathan Blake, Aditi Ramaswamy, Melane Navarat- narajah, and Aaditya Shivakumar. You Only Explain Once. arXiv preprint arXiv:2311.14081,

    arXiv

  39. [2018]

    Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation

    Guy Amir, Shahaf Bassan, and Guy Katz. Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation. arXiv preprint arXiv:2408.03915,

    arXiv

  40. [2019]

    This Looks Like That: Deep Learning for Interpretable Image Recognition

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

    arXiv

  41. [2020]

    Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations

    Pablo Barceló, Alexander Kozachinskiy, Miguel Romero Orth, Bernardo Subercaseaux, and José Verschae. Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. arXiv preprint arXiv:2501.06078,

  42. [2021]

    Causal Explanations for Image Classifiers

    Hana Chockler, David A Kelly, Daniel Kroening, and Youcheng Sun. Causal Explanations for Image Classifiers. arXiv preprint arXiv:2411.08875,

    arXiv

  43. [2022]

    The Computational Complexity of Circuit Discovery for Inner Interpretability

    Federico Adolfi, Martina G Vilas, and Todd Wareham. The Computational Complexity of Circuit Discovery for Inner Interpretability. arXiv preprint arXiv:2410.08025,

    arXiv

  44. [2023]

    Local vs

    11 Published as a conference paper at ICLR 2025 Shahaf Bassan, Guy Amir, and Guy Katz. Local vs. Global Interpretability: A Computational Complexity Perspective. In Forty-first International Conference on Machine Learning,

    2025

  45. [2024]

    Learning to Faithfully Rationalize by Construction

    Sarthak Jain, Sarah Wiegreffe, Yuval Pinter, and Byron C Wallace. Learning to Faithfully Rationalize by Construction. arXiv preprint arXiv:2005.00115,

    2005 arXiv

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.