Post-hoc explanation methods for neural networks are often heuristic and lack provable guarantees. A common alternative to such methods that was studied in recent years is to compute a cardinally-minimal subset of input features that is provably sufficient to determine the model's prediction. For general neural networks, however, finding such explanations is computationally intractable. In contrast, recent work showed that this problem becomes more tractable for a particular family of neural networks, namely neural additive models (NAMs), though standard NAMs are highly restrictive because they exclude feature interactions altogether. In this work, we study the computation of provably minimal and sufficient explanations for neural networks with restricted feature interactions, bridging the gap between fully general neural networks and purely additive models. We first prove that even with constant-order interactions, the problem is Σ2P-hard, implying that worst-case exponential complexity is unavoidable. We then identify two provably tractable settings: one based on sparsity in the interaction structure and another based on a stronger interaction-aware notion of sufficiency. Under either of these settings, we develop algorithms that compute provable explanations for neural networks with any-order interactions while retaining much of the computational efficiency of additive models. Empirically, we show that these explanations are significantly smaller and faster to obtain than those produced by standard algorithms, while being derived from models that achieve much higher accuracy than standard NAMs. Overall, our results help expand the class of neural networks that admit efficient provable explanations, while clarifying the fundamental role of feature interactions in shaping their complexity.
Table 1: Strong-sufficiency results on nine order-2 tabular benchmarks at ϵ=0.1 . Columns show test accuracy, mean explanation size ± standard deviation (% of features), and mean runtime ± standard deviation.
Figure 1: COMPAS under strong sufficiency. Combined explanation-size and runtime plot.
Table 2: Sparse-setting results on nine order-2 tabular benchmarks at ϵ=0.1 . Columns show test accuracy, mean explanation size ± standard deviation (% of features), and mean runtime ± standard deviation.
Figure 2: Higher-order results for sparse Any-Order NAMs for the Bike Sharing dataset. Explanation-size distributions for orders 2–4, comparing our method with lexicographic greedy and sensitivity-guided greedy search.
Appendix figures & tables19 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Adult: combined explanation-size and runtime plot under strong sufficiency.
Figure 4: Bike Sharing: combined explanation-size and runtime plot under strong sufficiency.
Figure 5: Breast Cancer: combined explanation-size and runtime plot under strong sufficiency.
Figure 6: California Housing: combined explanation-size and runtime plot under strong sufficiency.
Figure 7: Diabetes: combined explanation-size and runtime plot under strong sufficiency.
Figure 8: German Credit: combined explanation-size and runtime plot under strong sufficiency.
Figure 9: Heart Disease: combined explanation-size and runtime plot under strong sufficiency.
Figure 10: HELOC: combined explanation-size and runtime plot under strong sufficiency.
Figure 11: Adult under varying ϵ . Combined explanation-size and runtime plot.
Setting
Ours
Greedy
Greedy Sensitivity
ϵ=0.1
29.1 ± 14.4% / 130.5 ± 54.8 / 61/61
27.1 ± 10.3% / 2765.5 ± 1121.9 / 48/61
34.2 ± 7.5% / 3369.3 ± 695.3 / 11/61
Whole admissible space
61.2 ± 10.5% / 303.0 ± 453.1 / 60/61
53.5 ± 8.8% / 2820.5 ± 1223.1 / 51/61
53.5 ± 7.5% / 3196.4 ± 996.5 / 13/61
Appendix
Table 3: Heart Disease under strong sufficiency: ϵ=0.1 vs. the full admissible input space. Each cell reports mean size ± sd (%) / mean runtime ± sd (s) / solved instances.
Dataset
Model
Acc.
Size mean
Size med
Time mean (s)
Time med (s)
Bike Sharing
First-order
0.8800
1.74
1.0
1.651
1.082
Bike Sharing
Second-order
0.9232
4.02
4.0
61.279
26.505
Bike Sharing
Sparse second-order
0.9163
2.82
3.0
242.984
118.560
California Housing
First-order
0.8619
1.22
1.0
5.786
1.767
California Housing
Second-order
0.8886
1.57
1.0
71.860
7.564
California Housing
Sparse second-order
0.8777
1.26
1.0
49.813
18.113
Appendix
Table 4: First- vs. second-order NAM ablation on four datasets at ϵ=0.1 on the full test split.
Figure 12: Bike Sharing: combined explanation-size and runtime plots for the first-vs-second-order ablation across explained test points.
Figure 13: California Housing: combined explanation-size and runtime plots for the first-vs-second-order ablation across explained test points.
Figure 14: COMPAS: combined explanation-size and runtime plots for the first-vs-second-order ablation across explained test points.
Figure 15: Heart Disease: combined explanation-size and runtime plots for the first-vs-second-order ablation across explained test points.
Dataset
N
r (gap, ∣F(x)∣ )
Adult
6477
0.233
Bike Sharing
3017
0.057
Breast Cancer
105
− 0.138
California Housing
4070
0.360
COMPAS
357
0.787
Diabetes
154
− 0.055
Appendix
Table 5: Correlation between the ours-vs-greedy size gap and ∣F(x)∣ , under strong sufficiency ( ϵ=0.1 ).
Order
Acc.
Size mean
Size med
Time mean (s)
Time med (s)
2
0.9163
2.82
3.0
242.984
118.560
3
0.9180
2.90
3.0
913.630
634.051
4
0.9295
3.37
3.0
3500.879
3735.853
Appendix
Table 6: Bike Sharing higher-order ablation for sparse models at ϵ=0.1 (orders 2–4; full test split). Order 4’s statistics are computed only over the 1096/3450 (31.8%) examples that produced a usable explanation within the 3600s per-example budget; see text.
Dataset (# features)
Ours
Brute force
MHS
Diabetes (8)
0.82 ± 1.33 / 29.0 / 154/154
0.62 ± 1.13 / 41.0 / 154/154
4.81 ± 3.52 / 3600.1 / 72/154
California Housing (8)
1.57 ± 1.74 / 7.6 / 4070/4125
1.26 ± 1.49 / 6.5 / 4128/4128
1.17 ± 1.41 / 324.9 / 4128/4128
German Credit (20)
12.99 ± 2.85 / 110.3 / 199/200
n/a / n/a / 0/200
18.85 ± 3.40 / 3607.2 / 23/200
Heart Disease (13)
3.79 ± 1.87 / 116.8 / 61/61
2.07 ± 0.27 / 2783.6 / 14/61
11.77 ± 3.32 / 3603.1 / 8/61
Appendix
Table 7: Exact cardinally-minimal baselines vs. our method under strong sufficiency ( ϵ=0.1 ). Each cell reports mean size ± sd / median runtime (s) / solved instances.
Dataset
DNN acc.
SIAN acc.
Order
s
Size mean ± sd (%) / Runtime mean ± sd (s)
Diabetes
0.7532
0.7273
4
4
8.4 ± 15.0 / 66.1 ± 63.7
Heart Disease
0.8689
0.8361
3
3
16.5 ± 12.8 / 59.3 ± 40.6
Appendix
Table 8: SIAN-detected interaction models: predictive accuracy and certified explanations under strong sufficiency (full test split, ϵ=0.1 ).
Neural network interpretability studies how models represent information and make predictions, and how to explain, test, or control their internal computations.
Despite significant progress in post-hoc explanation methods for neural networks, many remain heuristic and lack provable guarantees. A key approach for obtaining explanations with provable guarantees is by identifying a cardinally-minimal subset of input features which by itself is provably sufficient to determine the prediction. However, for standard neural networks, this task is often computationally infeasible, as it demands a worst-case exponential number of verification queries in the number of input features, each of which is NP-hard. In this work, we show that for Neural Additive Models (NAMs), a recent and more interpretable neural network family, we can efficiently generate explanations with such guarantees. We present a new model-specific algorithm for NAMs that generates provably cardinally-minimal explanations using only a logarithmic number of verification queries in the number of input features, after a parallelized preprocessing step with logarithmic runtime in the required precision is applied to each small univariate NAM component. Our algorithm not only makes the task of obtaining cardinally-minimal explanations feasible, but even outperforms existing algorithms designed to find the relaxed variant of subset-minimal explanations - which may be larger and less informative but easier to compute - despite our algorithm solving a much more difficult task. Our experiments demonstrate that, compared to previous algorithms, our approach provides provably smaller explanations than existing works and substantially reduces the computation time. Moreover, we show that our generated provable explanations offer benefits that are unattainable by standard sampling-based techniques typically used to interpret NAMs.
We propose FAME (Formal Abstract Minimal Explanations), a new class of abductive explanations grounded in abstract interpretation. FAME is the first method to scale to large neural networks while reducing explanation size. Our main contribution is the design of dedicated perturbation domains that eliminate the need for traversal order. FAME progressively shrinks these domains and leverages LiRPA-based bounds to discard irrelevant features, ultimately converging to a formal abstract minimal explanation. To assess explanation quality, we introduce a procedure that measures the worst-case distance between an abstract minimal explanation and a true minimal explanation. This procedure combines adversarial attacks with an optional VERIX+ refinement step. We benchmark FAME against VERIX+ and demonstrate consistent gains in both explanation size and runtime on medium- to large-scale neural networks.
Ryma Boumazouza, Raya Elsaleh, Melanie Ducoffe +2
Airbus SAS, France · IRT Saint-Exupery, France · The Hebrew University of Jerusalem, Israel
Formal explainability provides mathematically grounded justifications for individual predictions. However, abductive explanations often exceed human cognitive limits by involving too many features, while probabilistic relaxations have remained largely limited to categorical classification. We present a unified framework for probabilistic explainability based on sparse, anchored linear models, applicable to both binary classification and continuous regression. By mapping instances to the Boolean hypercube, our linear explanations strictly generalize subset-based approaches: they capture both the magnitude and direction of feature contributions while enforcing a prescribed sparsity budget k. We show that minimizing the relevance error for such explanations is \ClassNPPP-hard when the underlying model is a neural network, and we relate this intractable objective to a tractable surrogate---the fidelity error. For a parameterized family of local distributions, the relevance error of any k-sparse explanation is bounded by its fidelity error up to a multiplicative factor that remains small locally. We address the resulting empirical problem using two complementary approaches: a Mixed Integer Programming (MIP) formulation that yields provably optimal empirical solutions while maintaining polynomial sample complexity, and a polynomial-time Iterative Hard Thresholding (IHT) algorithm with provable approximation guarantees. Empirical evaluations show that, unlike state-of-the-art baselines such as LIME and MAPLE, our explanations satisfy both the anchoring and sparsity constraints by construction, while consistently achieving lower relevance error.
Frederic Koriche, Jean-Marie Lagniez, Chi Tran
Computer science Research Institute of Lens (CRIL), UMR CNRS 8188, University of Artois, Rue Jean Souvraz SP 18, Lens, F-62307, France