{"id":"c76c3159-d18e-435e-841d-051c5d42b8f2","arxiv_id":"2502.03391","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"SST trains models to produce concise sufficient reasons as an extra output, yielding faster and often smaller explanations than post-hoc methods like Anchors and SIS.","lead":"This paper trains neural networks to output a small set of input features that by itself determines the model's prediction, instead of explaining a frozen model afterward. The method, called sufficient subset training (SST), generates these explanations in a fraction of the time of prior post-hoc tools, with comparable accuracy on most benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Robust faithfulness is scored with the same PGD attack used in training, so Table 1 may measure attack-specific invariance rather than sufficiency over the whole ℓ∞ ball; a formal-verification check on MNIST would settle it.","rationale":"The reader's weakest assumption is that the faithfulness metric is the same objective SST is trained to optimize. I agree that this is a real weakness, and I sharpen it: the robust faithfulness metric is not merely aligned in distribution, it is aligned with a particular PGD attack that is used both for training and for scoring. Since Definition 2 requires sufficiency for every z in the ball, a PGD-based score is only a lower-bound proxy. A model can be robust to the specific attack trajectory while failing on other points in the ball. This is especially plausible for SST because the attack is generated using the same loss and parameters as training. The paper contains no formal verification evidence, so the reported robust faithfulness numbers do not establish the claimed robust sufficiency. The concrete test using a complete verifier would settle whether the proxy is accurate. I do not see this as a reason to reject the paper: the method may well be genuinely robust, and the post-hoc comparison could survive verification. But the central faithfulness claim should be conditional on either stronger verification or a clearly stated caveat that the reported numbers are attack-specific. The reader's conditional verdict is therefore appropriate. I also note the apparent issue in the Theorem 2 approximation-preserving reduction flagged by the reader, but that affects a motivational complexity contribution rather than the core empirical claim, so I do not treat it as the single most load-bearing concern.","tokens_in":31840,"tokens_out":7692,"duration_ms":83154,"concrete_test":"On the MNIST feed-forward SST model from Table 1, extract subsets for 100 test images and, for each subset, run a complete ℓ∞-ball sufficiency verification (e.g., Marabou or VeriX) at ϵ=0.12, checking whether h1's argmax equals h1(x) for all z with features in S fixed. Compare the verified-sufficiency rate with the reported 99.28% PGD-based faithfulness, and run the same verification on Anchors, SIS, and GS subsets for the same images. If SST's verified rate is close to 99.28% and at least as high as post-hoc verified rates, the concern is resolved; if the verified rate is materially lower, or post-hoc methods are higher under verification, the central faithfulness claim relies on an attack-specific metric and needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim is that SST 'produces succinct and faithful subsets substantially more efficiently than competing post-hoc methods.' In Section 5.1, robust faithfulness 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. SST's faithfulness loss is minimized against the same attack (same ϵ=0.12 and step count, Eq. (6)), so a high score can be achieved by invariance along the attack's trajectory without satisfying Definition 2 for all z in the ball. This is load-bearing because Table 1's comparison is built on this proxy. The concern is not merely formal: Table 4 shows SST's faithfulness is strongly mask-dependent (robust-trained MNIST drops to 11.82% baseline faithfulness), indicating the favorable score is tied to the training-time masking distribution. Post-hoc methods are evaluated under the same proxy without being trained for it, which may understate their true robust sufficiency if their subsets are actually verified-robust but missed by the attack. Thus the claimed faithfulness advantage is not independently established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":32003,"tokens_out":9436,"duration_ms":87684,"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":[{"comment":"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.","section":"Section 5.1, Eq. (6), Table 1"},{"comment":"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.","section":"Section 5, Tables 1-4"},{"comment":"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.","section":"Section 4.1, Eq. (5)"},{"comment":"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.","section":"Appendix D, Lemma 10"},{"comment":"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.","section":"Section 5, Tables 1-4"}],"minor_comments":[{"comment":"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'.","section":"Abstract and Section 4"},{"comment":"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.","section":"Section 5.1, Figure 4"},{"comment":"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.","section":"Appendix F.1"},{"comment":"The theorem statement is typeset with missing superscripts ('n1−ϵ', 'n 1 2 −ϵ'), making the approximation factors hard to read. Please fix the notation.","section":"Section 3, Theorem 2"},{"comment":"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.","section":"Section 5.1 and Eq. (6)"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely salvageable. The main empirical claim is plausible, and the efficiency gains are large and consistent, but the faithfulness metric is too closely aligned with SST's training objective to be the sole evidence for the faithfulness claim. The missing error bars and the absence of a random-mask control are standard requirements for an empirical paper of this type. The gradient-flow omission and the Lemma 10 inconsistency appear fixable. I recommend major revision rather than rejection: the authors should add a verification-based robust-faithfulness check (or a clear attack-agnostic evaluation), report statistics over multiple seeds, add the control ablation, and correct the theoretical proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea here is simple and worth taking seriously: train a mask head alongside the classifier, with a faithfulness loss that forces the masked input to keep the original prediction, plus a sparsity loss. It works. The authors show sufficient reasons can be generated in microseconds, versus seconds for Anchors, SIS, and gradient search, with comparable accuracy. I can see this being genuinely useful in practice, especially for auditing at scale.\n\nWhat is actually new: the dual-loss training scheme for self-explaining sufficient reasons is a clean idea, and the complexity results in Appendix C genuinely extend the binary-input results to continuous domains. The paper is clearly written, code is available, and the limitations section is honest about the doubled training cost and the accuracy loss on ImageNet. Table 4, showing how masking choices transfer between sufficiency notions, is useful empirical information rather than decoration.\n\nThe soft spots are real but not fatal. First, and most important: the faithfulness metric is the same objective SST is trained to satisfy. Robust faithfulness is evaluated with the same PGD attack configuration used in training (epsilon=0.12, ten steps), so Table 1 measures invariance along that attack's trajectories, not the Definition 2 condition over the whole l-infinity ball. A formal verification check on MNIST would settle whether the robust faithfulness numbers are real. As it stands, the comparison against post-hoc methods is not fully independent: they are being judged by a proxy their explanations were never optimized for. Second, there are no error bars or multiple seeds anywhere. Given that CIFAR-10 faithfulness differences are a few points, the ranking claims are not supported by the reported numbers alone. Third, the approximation-hardness proof for baseline sufficient reasons (Theorem 2, Appendix D) uses a reduction from Max-Clique in which sufficient-reason size equals |V| minus clique size. That mapping is not approximation-preserving in the stated n^{1-ε} factor, so the theorem needs a corrected proof or a softened claim. The other complexity results appear fine. Minor: the paper does not compare against self-explaining rationale methods (e.g., trained rationalizers or mask-based feature selection), which are the closest existing work; the 'first self-explaining framework' phrase needs qualification.\n\nWho is this for: researchers and practitioners who want sufficient-reason explanations at scale, and XAI folks interested in training-time interpretability. It deserves a serious referee: the method is novel, the efficiency gain is large, and the issues are fixable. I would send it to review, asking the authors to add error bars, replace the robust-faithfulness check with verification on at least one benchmark, and either fix or soften the baseline inapproximability theorem.","headline":"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.","tokens_in":32559,"tokens_out":5060,"would_cite":true,"duration_ms":48915,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["sufficient reasons","minimal sufficient subsets","self-explaining neural networks","faithfulness","cardinality loss","dual propagation","masking strategies","explanation complexity"],"falsifier":"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.","tokens_in":31569,"feed_emoji":"🧠","tokens_out":9413,"duration_ms":79865,"temperature":0.7,"pith_summary":"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.","feed_headline":"Self-explaining nets output concise reasons in one pass","feed_subtitle":"Training a mask head alongside prediction yields smaller, more faithful subsets in microseconds, not seconds.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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%."],"supporting_citations":[{"why":"Defines Anchors, the post-hoc probabilistic sufficient-reason baseline that SST is compared against on speed, size, and faithfulness.","marker":"Ribeiro et al. (2018)"},{"why":"Defines sufficient input subsets (SIS), the post-hoc baseline whose low faithfulness motivates SST's training-time objective.","marker":"Carter et al. (2019)"},{"why":"Establishes the computational complexity of minimal sufficient reasons in the binary setting that Theorem 1 extends to continuous and discrete domains.","marker":"Barceló et al. (2020)"},{"why":"Supplies the NPPP-hardness result for probabilistic sufficient reasons that Theorem 1 and its approximation corollary build on.","marker":"Wäldchen et al. (2021)"},{"why":"Documents the out-of-distribution counterfactual problem in post-hoc explanation search that SST aims to avoid.","marker":"Hase et al. (2021)"},{"why":"Provides the projected gradient descent attack used in SST's robust masking to define and optimize robust sufficient reasons.","marker":"Madry et al. (2017)"},{"why":"Supplies the BERT architecture and MASK token used as the baseline for language benchmarks and the baseline masking strategy.","marker":"Devlin et al. (2018)"},{"why":"Gives the Shortest-Implicant-Core inapproximability result used to prove Theorem 2's robust-case hardness.","marker":"Umans (1999)"},{"why":"Gives the Max-Clique inapproximability bound used for the baseline-case approximation hardness.","marker":"Håstad (1999)"}],"fun_headline_variants":["Self-explaining nets generate concise sufficient reasons directly","One-forward-pass self-explanations beat post-hoc subset search","Tiny faithful reasons generated by the net itself","Sufficient reasons learned, not mined: one-pass SST","Concise self-explanations without post-hoc search costs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Self-explaining nets generate concise sufficient reasons directly","One-forward-pass self-explanations beat post-hoc subset search","Tiny faithful reasons generated by the net itself","Sufficient reasons learned, not mined: one-pass SST","Concise self-explanations without post-hoc search costs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000626,"raw_usage":{"total_tokens":2906,"prompt_tokens":965,"completion_tokens":1941,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":1863}},"tokens_in":581,"tokens_out":1941,"duration_ms":13369,"temperature":1.0,"reasoning_tokens":1863,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T04:53:33.115401+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}