Provably Explaining Neural Additive Models
Authors: Shahaf Bassan
Yizhak Yisrael Elboher
Tobias Ladner
Volkan Şahin
Jan Kretinsky
Matthias Althoff
Guy Katz
Venue: ICLR 2026 Poster (2026)
Keywords: explainability
XAI
explainable AI
formal verification
sufficient explanations
Primary area: interpretability and explainable AI
TL;DR: Our approach constructs provably sufficient and (globally) cardinal-minimal explanations for neural additive models with improved runtime complexity.

Abstract: 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.

Published as a conference paper at ICLR 2026
PROVABLY EXPLAINING NEURAL ADDITIVE MODELS
Shahaf Bassan"
Yizhak Yisrael Elboher'
Tobias Ladner
Volkan Şahin² Jan Křetínský Matthias A
Guy Katz*
1 Hebrew University of Jerusalem, Israel,
2 Technical University Munich, Germany,
3 Masaryk University, Czech Republic Contact: shahaf. bas aujji.ac.i
yi zhak. mooherrmaiin huji acc il, tobias. ladner@tum, de
ABSTRACT
Despite significant progress in post-hoc explanation methods for neural networks, many remain heuristic and lack provable guarantees. A key approach for obtain- ing explanations with provable guarantees by identifying subset of imput features which by itself is provably sufficient to determine the pre- diction. However, for standard neural networks, this task often computationally infeasible, as it demands worst-case exponential number of verification queries in the number of input features, each of which NP-hard. this work, we show that for Neural Additive Models (NAMs), recent and more interpretable neu- ral network family, we can efficiently generate explanations with such guarantees. model-specific algorithm for NAMs that generates provably cardinally pardinally-minimall minimal explanations using only a logarithmic number of verification queries in the number of input features, after 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 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 previ- ous algorithms, approach provides provably smaller explanations than existing works and substantially reduces the computation time. Moreover, we show that generated provable explanations offer benefits that unattainable by stan- dard sampling-bas based techniques typically used to interpret NAMs.
pordinallymminima
We present
INTRODUCTION
Various methods have been proposed to explain neural network predictions. Classic additive feature attribution approaches such as LIME (Ribeiro al. 2016), SHAP (Lundberg & Leel 2017). and IG (Sundararajan et al. (017)) assume near-linear behavior in a local region around the instance. Other methods, like Anchors RRbeiir et al. 2018) and SIS (Carter et al. 2019). aim identify (nearly) sufficient subset of input features - referred to here as an explanation - that determines the prediction. While Anchors and SIS rely on probabilistic sampling and lack provable sufficiency guarantees, recent work has shown that neural network verification tools can serve as a backbone for
generating provably sufficient explanations (Wu et al.) 2023 Bassan Katz 2023 La Malfa et al.)
2021
Izza et al. 2024), making them particularly valuable in safety-critical domains (Marques- Silva & Ignatiev 2022]. In this context, smaller sufficient explanations are typically preferred, as
minimality considered additional key interpretability property (Ignatiev et al. 2019 Carter
ct al.
2019 Darwiche & Hirth 2020; Ribeiro et al. 2018 Barceló et al.) 2020b).
However, while such explanations are highly desirable, generating them for standard neural net- works is notoriously computationally challenging (Barceló et al.) (020b). In particular, obtaining cardinall-minimaa explanations, requires, in the worst case, exponential number of neural net-
work verification queries (Barceló et al.) 2020b: [gnatiev et al. 2019 Bassan & Katz 2023), each
Equull contribution.

---

Published as a conference paper at ICLR 2026
being NP-hard (Katz al. 2017 7 Sälzer & Lange 2021), rendering the task infeasible even for toy examples (Igmatiev et al., 2019). Consequently, existing methods focus on uubset-minimal explana- tions (Wu et al.] 2023 Bassan & Katz 2023 Bassan et al. 2025b), which are typically suboptimal in size, potentially l large, and thus less informative than their cardinally minimal counterparts. More- over, even these approaches remain limited to relatively small models, they still require linear number of verification queries (Wu et al. 2023 Bassan et al., 2025c).
sufficient explanations is provably in- tractable for general neural networks, a natural question arises: Can certain neural architectures with more interpretable structures enable efficient computation of such explanations? Although this task remains challenging even for simplified models such as binarized neural networks or those with a single hidden layer (Adolfi et al., 2025 Barceló et al. 2020a Sälzer & L.nge 202T), we show in this work that it becomes tractable e for a different class of neural architectures previously unexplored in this context: Neural Additive Models (NAMs) (Agarwal et al. 202T). NAMs are widely adopted
Our contributions. Since computing cardinally-minine
architecture that has received significant attention in recent years (Agarwal al. 2021 Radenovic
ct al. 2022; Bechler-Speicher et al. 2024; Kim et al., 2024 Zhang et al. 2024). By enforcing an
additive structure over input features, NAMs support interpretable, per-feature contributions while maintaining the expressive capabilities of neural networks.
Our NAM-specific algorithm vs. previous algorithms. Unlike existing algorithms that require linear number of verification queries in the number of input features for subset-minimal explanations an exponential number for eardinally-minimad ones our approach exploits the additive struc- ture of NAMs to compute provably cardinally minimal explanation subsets using only a logarithmic number of verification queries. This is realized by introducing a highly parallelized preprocessing step each operating independently on a small univariate component of the NAM - enabling a substantial overall efficiency gain. As a result, our method yields explanations that are both provably sufficient and cardinally minimal,, far more efficiently than standard algorithms typically applied to neural networks. Experiments using sfate-of-the-art verifiers confirm that our algorithm generates explanations substantially faster and produces notably smaller subsets than prior approaches.
Our provable NAM explanations vs. standard sampling interpretations. NAMs are typically interpreted by sampling input points and visualizing the behavior of each univariate function (Agar- wal et al. 202T Radenovic et al.) 2022). Thanks to their additive structure, these models allow per-feature contributions to be examined individually. We show that purely sampling- maased based meth- ods can yield misleading interpretations, whereas our provably sufficient explanations avoid this by design, underscoring their importance in safety-critical domains.
Overall, our work advances explanations with provable guarantees in two ways: (i) it introduces the first method for certifiable explanations in NAMs, boosting their trustworthiness in safety-critical settings, and (ii) by efficiently generating provable explanations, NAMs - unlike general neural networks open path toward interpretable architectures where such guarantees can be derived at scale. A central challenge ahead is to design models that balance high expressivity and accuracy with efficient provable explanations, and we view our work significant first step in that direction.
2 PRELIMINARIES
2.1
NOTATION
We denote scalars with lower-case letters, vectors with bold lower-case letters, and sets in calli- graphic font. The i-th entry of a vector x is denoted by x, For n E N. let [m] = {l..... n].
2.2 NEURAL NETWORK VERIFICATION
Neural network verification aims verify certain input-output relationships of neural networks. For a neural network f: RT > R a neural network verifier formally proves that there does not exist an
input R where both input specification (x), and unsafe output specification ooou (x)) hold at the same time. Although this problem is NP-hard (Katz et al.) 2017] Sälzer & Lange 202
these tools have seen rapid scalability improvements in recent years (Kaulen al. 2025).
2

---

Published as a conference paper at ICLR 2026
2.3 NEURAL ADDITIVE MODELS (NAMS).
A neural additive model (NAM) f for a regression task, where f: R= - R. is defined as:
k
f(x) = Bo Σ f((x)),
(1)
where each f:: - R is univariate neural network, Po E IR is the intercept, and f denotes the full NAM. For binary classification, we assume that an additional step function applied: f(x) := where step(z) if 2 2 0 and step(z) = 0 otherwise. In the multi-class setting with classes, the logit for class [c] is given by [x() $3.0 Σ Jz,e(xs), and the model predicts f(x) ;= arg max f)
step(00 + 1 fi(x:)),
In this work, we develop algorithms for all three settings - (i) regression, (ii) binary classification, and (ii) multi-class classification - but for clarity, we focus the main presentation on the binary classification case, with extensions for the other settings provided in Appendix E
PROVABLY SUFFICIENT EXPLANATIONS FOR NEURAL NETWORKS
We begin by reviewing standard algorithms developed for general neural networks that identify provably minimal sufficient explanations. We note that we focus on post-hoc sufficient explanations a specific input E IR"" i.e., for the output f(xx,, and post-hoc indicates that the explanation generated after the model has been trained.
Sufficient Explanations. A common method for interpreting the decisions of classifiers involves identifying subsets of input features S C [ni] such that fixing these features their specific values guarantees the prediction remains unchanged. Specifically, these techniques guarantee that the clas- sification result remains consistent across any potential assignment within the complementary set == [x]] S. While in the classic setting features the complementary set are allowed to take on any possible feature values (Ignatiev et al. 2019 Darwiche & Hirth 2020 Bassan & Katz 2023), a more feasible and generalizable version restricts the possible assignments for S to a bounded fp-
region (Wu et al. 2023; La Malfa al., 2021 Izza et al. 2024). We use (xs:&g) E R" denote an assignment where the features of S are set to the values of the vector x E IR and the features of S are set to the values of another vector x E R² within the Gp-region.
Definition 1 (Sufficient Explanation). Given neural network f. an input IK", perturbation radius Ep E R_, and subset S S [n]] we say that S is a sufficient explanation concerning the query (J, x, S, ep) on an f--norm ball By of radius Ep E IR,, around x iff holds that:
VX E B
{(xs;tg)= = f(x),
with B (x) = {5 [R"
x S cp}.
We define suff(f, x, S, cp) = 1 iff S constitutes sufficient explanation with respect to the query (f. x, S, (p), and suff x, S, cp) otherwise.
Def. can be formulated proposed by prior studies, which employed these techniques to validate the sufficiency of specific
neural network verification query (Sec. 2.2
This method has been
subsets (Wu et al. 2023 Bassan & Katz 2023 La Malfa et al. 202 Izza et al. 2024)..
Minimal Explanations. Evidently, selecting the entire input set as the subset S, that is, setting S == [n). yields a sufficient explanation. Nonetheless, the prevailing consensus in the literature is that smaller subsets tend to be more informative or meaningful (Ribeiro et al.) [2088] Carter et al.) 2019 Barceló et al. 2020b Ignatiev et al. 2019). Consequently, there is considerable interest in denttifynng subsets that are not only sufficient but also satisfy some notion of minimality. We focus on two specific minimality criteria: cardinality minimality and subset minimality.
Definition (Minimal Sufficient Explanations). Given a neural network f, an input R", and subset S C [n] that is a sufficient explanation concerning (f, x, S, S,)p) on B of radius ep. then:
1. We say that a cardinally-minimat sufficient explanation (Barceló et al. 2020a Bassan let al. 2024) concerning (f. x. S, {p) iff there does not exist a sufficient explanation S concerning (J, x. S', {p) with S (S).
3

---

Published as a conference paper at ICLR 2026
NAM with unperturbed imput.
(b) Subset-minimal explanation of size
(e) Cardinally -iimmaal explanation of size
Zetat
1-0.8
P.S.
F2593 2-15
Autel 2-13
Autt 2-15
Zute)
Jaco3
Figure 1: Comparison of a subset-minimal explanation and cardinally-minimal explanation of NAM. Both explanations (in yellow) ) (b) and (c) are minimal, as perturbing any additional feature can lead the overall output become negative.
2. We say that S is subset-minimal sufficient explanation (Arenas al. 2022 Ignatiev al. 2019 concerning (J, x, S, e,) iff any S' C S is not sufficient explanation concerning Xx S', Gp).
Minimal sufficient explanations can also be determined using neural network verifiers. This process requires executing multiple verification queries to ensure the minimality of the subset. Alg. out- lines such a procedure (Ignatiev et al., 2019 Wu et al. 2023 Bassan & Katz, 2023). The algorithm begins with an explanation encompassing the entire feature set 7 and iteratively tries to exclude a feature from S, each time checking whether S \ {i} remains sufficient. If S {i} is still sufficient, feature i is removed; otherwise, subset-minimal sufficient explanation is obtained. Such a subset-minimal explanation of NAM is visualized Fig. T along with a cardinally-mine minimall explanation.
retained the explanation. This process is repeated until a
Algorithm Greedy Subset Minimal Explanation Search
Input: Neural network f: I² + R input x E R", perturbatiin radius cp E R.+
1: S + [n]
2: for each feature i E [n] do
suff(f, x, S, Ep) holds
3: if' suff(ff x, S {i}, Ep) then
4:
S+5 {i}
5: end if
6: end for
7: return S
S is a subset-minimdt explanation concerning (S, x, S ep)
PROVABLY CARDINALLY-MININS SUFFICIENT EXPLANATIONS FOR NAMS
While generating cardinally-minimal sufficient explanations is computationally expensive for gen- eral neural networks, present highly efficient algorithm for NAMs in this section. NAMs generally considered very interpretable due to the univariate functions, but sufficient guarantees can only be obtained through formal verification avoid misleading conclusions (Fig 2 Our algorithm consists of two main stages: (i) As preprocessing step, we compute an "importance" interval for each feature [n] based on the univariate functions f; obtain total ordering. (ii) This allows us to perform binary search over the sorted intervals to identify the cardinally-minn minimal sufficient explanation.
All full proofs are provided in Appendix
4.1 STAGE - PARALLEL INTERVAL IMPORTANCE SORTING
This subsection outlines the first stage of our algorithm, which involves determining an ordering of the feature importance to be used in the subsequent phase. We adopt notion of "importance" similar to that of (Barceló et al. 2020a), originally used for binary linear threshold models. Specifically, say that feature [ more "important" than feature o i if perturbing feature i causes
4

---

Published as a conference paper at ICLR 2026
(a) Local neighborhood.
(b) Sumpling vs. verification.
fi(N1)
0.5
15 18
0.2 0.6 0.8
0.2 0.5
X
fs(oa)
11.5
0.2 0.0 0.8
0.2 0.6
(x)
0.2
0.2 055
Figure 2: Sufficient explanations NAMs: (a) Users must examine the neighborhood of an input for proper interpretation; e.g, users might wrongly conclude that feature 1 from the FICO HELOC dataset alone determines a positive output, but small changes in features 15 or 18 can flip the classi- fication. (b) Outputs of continuous neighborhoods can be misleading if not verified, since sampling may miss extrema. For example, users might wrongly believe based on sampling that all features but feature 1 only have positive outputs and thus fixing feature 1 will always lead positive output of the entire NAM; however, the output of feature can become so negative to flip the classification.
larger change in the final prediction f(x) than perturbing feature j. In particular, we measure the derivation towards the decision boundary to flip the classification. Thanks to the additive structure of the NAM, this analysis can be conducted independently for each univariate component f:: R - I. allowing for direct comparison of their individual importance.
Without loss of generality, let us assume that our binary classifier predicts f(x) = 1, meaning that 30 + >i fi(x.) 2 O (the case f(x) O follows symmetrically). In this setting, we perturb the input to each univariate component fi individually and measure how much the overall prediction decreases, i.e., towards the decision boundary. Therefore, for each i [ri], we want to find
arg min f((x:)) 5.EB." (x.)
However, in contrast to the binary linear threshold models studied in (Barceló et al.) 2020b), ex- actly determining these minimal values is usually computationally infeasible Katz et al. (2017). Fortunately, we do not need to find the exact minimum but only bounds [4, uj] C R such that 4 S f((x)) S u, with sufficient precision to establish a total order over the input features. The procedure is outlined in Alg. 2
Alg. 2 operates in parallel across each univariate component of the NAM. For each component, the algorithm begins by issuing incomplete verification query to obtain initial lower bound fo (&... denoted by 4 and u4 evaluated over the domain &; E B (x,). Subsequently, each thread independently conducts a binary search using verification queries rowing in on the true lower bound fx()). To quantify the deviation of the unperturbed output f (x;) from these bounds, we define the relative differences Al; and Au.. After each iteration within every parallel thread, the algorithm evaluates whether a full, non-overlapping sorting of all pairs (Al1, Aut)....................... (Al,, Au,, is possible. If such an ordering cannot yet be achieved, the bounds get iteratively refined. Finally, the ordering according to the determined importance is returned.
iteratively refine [4, uz]. nar-
While the initially computed bounds ag B, enclose the entire output domain of each component i E [n], the binary search narrows the bounds down around the minimum
f((;;) (or maximum for fx) = 0); thus, no longer covering the entire domain. As f; (x;) ) is just a scalar, this total order can be determined using a complete verifier.
This non-overlapping ordering provides rigorous measure for the impact of perturbing a single feature through its corresponding component function fx(x;). This sorting forms the foundation for the next phase of the algorithm, which identifies provably cardinally-minima sufficient subset. The following proposition formalizes this first step of the argument:
Proposition 1. Given a NAM f. an input x E R and a perturbation radius Ep E R.,, let Alg. Ag. 2 return lotal list order over the input features according to their importance. Then, the following
5

---

Published as a conference paper at ICLR 2026
Algorithm 2 Parallel Interval Importance Sorting
Input: NAM f, input x E R", perturbation radius Ep IR+,
1: for each feature E [n] in parallel do
2: Extract initial bounds 0g 3g for f(().) such that &, B37 (x.)
3: 4 4 0s uj < 3
4: while True do
5:
my < litt
6:
if verify( VX, E BG (x.), [(())) 2 m, then
7:
4 + my
8:
else
9:
U4 4- mi
10:
end if
11:
Al 6 fx(x. 44 Au; + f((x,) - u4
12:
if for all * it holds that: Au; Al or Auj 2 A4, then
13:
break
14:
end if end while
15:
16:
end for
17:
return arg sort([(A),, Am))), (Al,, Aun))) in ascending order
holds: For any sufficient explanation S that includes feature i, and for any feature & S such that i 2 in the list ordering, the set S {i) [j} also a sufficient explanation.
Complexity. The complexity of Alg. 2 governed by the use of parallel processors, where each processor independently carries out a binary search. This binary search iteratively partitions based on the Au; and A4, bounds and terminates once the bounds of two distinct univariate components no longer overlap. Given the initial gap between the upper and lower bounds, a - fx()). for each component ft. and the precision for component fa defined by its minimal separation from the adjacent features in the sorted ordering - namely, & == min ما Auel, | Au4 ||] with Šoo ÂnD denoting the bounds in the last iteration. We can now prove that the number of neural network verifier calls is bounded by (parallelized) logarithmic term, as formalized in the following proposition. Limitations and optimizations are further discussed in Appendix D
Proposition 2. Given P parallelized processors, Alg. performs overall number of Tp(n)
((2))ogg) max4e(m) B B
(log( (max;E())
B BL-a.
calls to the neural network veri-
E,
fier, each univariate component f((),, where min Á4441 Au,, Su,-al).
The edge case & + While Alg. 2 scales logarithmically with respect to the precision gap between optimal values of the univariate components, this gap could be arbitrarily small in theory. We address this edge case in Appendix [D.I show that - even when & approaches zero the algorithm is still guaranteed to terminate after linear number of steps in the size of the model encoding, given a model with ReL.U activations. This remains substantial improvement over the exponential worst-case behavior known for general neural networks. Crucially, empirical results demonstrate that, in practice, this parameter is never close to zero, enabling an efficient sorting phase. A detailed ablation of this parameter provided in Appendix F55
4.2 STAGE 2 FEATURE SELECTION BASED THE DERIVED FEATURE INTERVAL.S
In this subsection, we will describe the second part of our algorithm that can obtain a provably cardinally-minimal sufficient explanation, given the derived interval orderings that were obtained from Alg. 2 In contrast to binary linear models (Barceló et al.] 2020b). where the exact maximum and minimum contribution of each feature is known and one can simply select the top-k features, NAMs do not offer this convenience. For NAMs, we only have access to bounds on each univari- ate component, and thus we must explicitly certify that fixing certain features is indeed sufficient. However, to the total order, logarithmic number of verification queries in the number of input features. However, to simplify the presentation of this algorithm, will start by presenting naive greedy approach that runs in
apply binary search to obtain the explanation, resulting in

---

Published as a conference paper at ICLR 2026
linear number of steps similar to the one proposed by (Barceló et al. 2020b). and then move to presenting the binary-seart approach. The naive approach is depicted in Alg.
Algorithm 3 Greedy Cardinally- Minimall Linear Explanation Search
Input: NAM f. input x E R", perturbation radius Ep E +
1: + [n]
2: for each feature i [n], ordered by Alg. do
suff x, S, ep) holds
3: if suff([ X, S {i) 6p) then
4:
S {i) 5: end if
6: end for
7:
return S
S is cardinally carrihall-miniiddeeeeaaaatto explanation concerning (f, S. (p)
Alg. Cclosely mirrors the operation of Alg. It begins by initializing the explanation S to the full feature set [n], and then iteratively removes features, updating S \ {i}, until reaching a mini- mal explanation. However, unlike Alg. [ which is only guaranteed to converge more challenging objective of finding mandinally-minimall suf- ficient explanation. This stronger guarantee is enabled by the total ordering (Al,, Au.); computed by Alg. which ranks the features by their importance. This leads the following proposition:
subset-minimal
explanation, Alg. converges
Proposition 3. Given NAM f. an input x E IR" and perturbation radius Ep E IR+, Alg, per- sufficient explanation. This stands in contrast
forms (n) queries and returns a cardinally Alg. which is only guaranteed return a subset-minimal sufficient explanation.
Alg. 3 can be significantly enhanced by replacing the linear ordering with a binary search strategy (Alg. Crucially, this step is not possible with the naive, unsorted approach (Alg. [T. it does not guarantee convergence to minimal explanation. This is because, in an arbitrary feature ordering, there may multiple points at which non-sufficient subset becomes sufficient, making the binary search unreliable. In contrast, imposes structured sorting features, which allows Alg. f to
dettinally-minime explanation, and may not even yield subset-
the preprocessing step in Alg. 2 reliably converge to cardinally-mining sufficient explanation using only logarithmic number of queries.
Algorithm 4 Greedy Cardinally- Minimal Logarithmic Explanation Search
Input: NAM f, input x E R", perturbation radius Ep E IR+
1: F < total order of features (Alg. 2
2: [-1
3: while 7 uudu do
4: m f _
5: if' suff(f, x, F [[m]], ep) then
6:
m
7:
else
8:
u 4- m
9: end if
end while
11: S [F[1), F(mm]]
Fim]]
12: return
S is cardinally-minimal explanation concerning (f, x, S, ep)
Proposition 4. Given NAM f. an input x E I",, and a perturbation radius Ep E R4, Alg. performs (log(n)) queries and returns a cardinallymminiall sufficient explanation.
Overall complexity results. By combining Alg. P with Alg. 4 we obtain a cardinally-minima explanation for (f,x, This unified algorithm yields a substantial efficiency gain, reducing the worst-case requirement of an exponential number of verification queries to only logarithmic num- ber of (parallelized) queries. The first segment of these queries operate by rumning verification queries univariate components fa of the model, which are far smaller, and hence to verify than direct queries to f. The resulting complexity bound is formalized the following theorem:
efficient

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of average explanation size and computation time.
Brcast Cancer
CREDIT
FICO HELOC
Method
Size (4)
Time [8] (
Size (L)
Time [s] (L)
Size (4)
Time (
Ours
4.00
35.60+1..3 1.34
3.76-:2.2
132.67 36.76
5.59 1.80
317.92+
Lexieographic
16.08=5.44 44
631.92777.22 .23
12.42=6.45
473.63+128.88
15,60+7.85 7.3
146. 166.16+18800
Scnsitivity
16.27=5.57
636.79=87.44 44
3.82+1.84
407.93+126.66 63
9.45#55900
250.09#148.4
Theorem 1. Running Alg. 2 and Alg. 4 obtains a cardinally minimll sufficient explanation with (log( max (1) queries to fi(-) compo-
(n(n) = O log( |a (8-aa) p-n O log
nents, plus Ollog v) queries to f(.). In contrast, standard algorithms require O(2") verification queries to f()) for cardinally-minine explanation, or (n) verification queries to f-) for only a
subset-minima explanation.
As discussed earlier, our complexity analysis is parameterized by the separation between the minima of the univariate components &, which is typically non-negligible in practice, though some & may be small. To address this, we show that running Alg. 2 followed by Alg. takes time linear in the encoding size of the model. We further prove matching query bounds: the task can be solved with at most linear number of queries, and any algorithm requires at least a logarithmic number of queries in the encoding size of f.
Theorem 2. (Informally.) Let f be NAM, x E IR" an input, and Ep E R. Computing the size of cardinally cardinally-iniiaal minimal sufficient explanation for {f.x. Ep) requires, in the worst case, most (m)) queries to an NP oracle (Claim [ and at least (log(m)) such queries (Lemma 5 where m is the encoding size of J. Moreover, running Alg followed by Alg A terminates after at most (mm) queries (Proposition
5 EVALUATION
Experimental Setup. We implemented our main algorithmic approach (Alg. 2 followed by Alg. 4 using a-3-CROWN as the backend verifier, the current state-of-the-art in neural network verifica- tion (Wang et al. 202T Zhou et al. 2024 Kotha al. 2023 Kaulen al.) 2025 Chiu et al. 2025). We conducted extensive experiments on four widely used tabular-data benchmarks in the context of NAMs (Agarwal et al. 2021 Radenovic et al. 2022): (i) Breast Cancer, (ii) CREDIT, (iii FICO HELOC, all of which are prominent in safety-critical domains. We adopted the same model architec- tures prior work in the NAM literature (Agarwal et al. 2021 Radenovic al. 2022). Evaluation details, additional experiments, and ablation studies are in Appendix
5.1 OUR ALGORITHM VS. PREVIOUS ALGORITHMS
We begin by comparing our results with prior algorithms proposed in the literature for obtaining provably minimal sufficient explanations. Since our method targets the much stronger notion of cardinally-minimal sufficient explanations for the first time, any naive baseline - that computes such explanations by exhaustively enumerating all 2n input subsets, verifies their sufficiency, and selects the one with the smallest cardinality would not finish with reasonable timeouts. Thus, we compare our approach to the more scalable task of finding subset-minimal explanations, weaker notion of minimality, using the standard greedy algorithm employed by previous works (Wu et al.
2023 Bassan et al. 20256) Izza et al. 20244] Ignatiev et al,, 2019 La Malfa et al.] 2021 (Alg. []. feature orderings.
Because subset-minint
explanations depend
consider two setups: (i)
basic lcxicographic ordering of features, and (ii) a more sophisticated reverse- sensitivity ordering,
following prior approaches (Wu et al. 2023 Bassan et al. 2025b Izza et al. 2024 Wu al. 2024b).
The results in Tab. demonstrate that our proposed algorithm achieves substantial improvements in both computation time and explanation size over previous algorithms. Beyond reducing explanation size compared to standard
explanation algorithms (which follows by necessity, since enforce stronger notion of minimality), method also achieves substantial runtime gains,
8

---

Published as a conference paper at ICLR 2026
(a) Breast Cancer
(b) CREDIT
(c) FICO HELOC
Explanation size
30
30
20
20
20
10
10
10
0
200
400
600
800
0
200
400
600
800
200
400
600
800
Time [s]
Time [s]
Time [s]
Ours
Naive
Sensitivity
Figure 3: Explanation size over time for all datasets.
Table 2: Comparison against purely sampling -ased approach.
CREDIT
FICO HELOC
Method
Size
Time [s] (1)
Sufficiency (7)
Size
Time [s] (1)
Sufficiency [%]] (f)
3.76+12.62
132.67 +63
100.00
5.59 1.60
317.92+ 222.0222222
100.00
Sampling 2. 2..71
5.10.1.226
31.37
3.0413.05
6. 6.89.12.57
25.49
despite solving much harder task. This ad advantage stems from our NAM--peccfii algorithm, which requires only logarithmic number of parallelized queries rather than linear number executed over univariate components fi, which are much faster to verify.
5.2 EXPLANATION PROGRESSION IN TIME
To further assess the advantages of our algorithm over prior methods, we analyze the explanation sizes produced by approach in comparison to subset-mininal methods and track their evolu- tion over time. This analysis is illustrated in Fig. 3 The results show that while subset-minimal approaches converge slowly and often stagnate in local minima. Our method though it begins later due to the preprocessing step in Alg. 2 which sorts features with only a logarithmic number of parallelized queries - quickly outpaces them once sorting is complete. At this point, it requires significantly fewer queries, relying only on a binary search over the sorted features as in Alg. 4 This second phase not only substantially faster but also provably attains the cardinally-mining explanation, i.c., the global optimum, unlike
approaches.
5.3 COMPARISON TO PURELY SAMPLING BASED METHODS
NAMs are generally viewed as very interpretable as their univariate functions Si for each feature al- low for simple visualizations (such as in Fig. 2). Most commonly, these visualizations are obtained through sampling over the respective feature domain to get good approximation of each univariate function. However, we show in this experiment that this discretization through sampling and the resulting interpretations can be misleading. Peaks and other extrema that are missed through sam- pling can lead to insufficient explanations, which can be fatal in cartty-critical domains. An extreme case is abstractly depicted in Fig. Db. but we have also observed insufficient explanations in practice. To demonstrate this, we evaluate 000 evenly-spaced samples instead of each verification query. After the explanations are generated, we test their sufficiency using a, 3-CROWN (Tab. ( On the CREDIT and FICO HELOC datasets, more than half of the explanations obtained through sampling could not be verified. In contrast, all our explanations are sufficient by construction.
6 RELATED WORK
Formal XAL Our work relates to the field of formal XAI Marques-Sini Silva 2023). which seeks ex- planations with provable guarantees. Prior efforts have developed sufficient explanations for models

---

Published as a conference paper at ICLR 2026
such decision trees (Huang al. 2021 linear models (Marques- Silva et al., 20200 Subercaseaux
jet al., ).25), and tree ensembles Izza & Marques-Site 2021; Ignatiey et al., 2022 Audemard
et al. 2022b 2023). Other relevant works are obtaining minimal suffccient exp lanations for neu-
ral networks LLa Malfa et al. 2021 Wu et al. 2023 Izza et al., 2024 Bassan et al.. 2023 2025b),
which rely neural network verification queries. While such verifiers have become more scalable in recent years, computing such explanations is still costly, often requiring many (linear or exponen- tial) verification queries. Our method takes step toward reducing this cost by focusing on neural network families with more interpretable structure, and particularly look into NAMs.
Closer to our setting is the work of Harzli al. (2023). which studies cardinally minimal sufficient explanations for monotonic neural networks, another interpretable model class. There, monotonicity simplifies certifying sufficiency, while minimality remains challenging. In contrast, for NAMs, certi- fying sufficiency is substantially harder, but minimality becomes easier due to the additive structure.
Also related to our work is the study of Barceló et al.] (2020b), which shows, among many results, that cardinally minimal sufficient explanations can be computed in polynomial time for linear (Per- ceptron) models over binary inputs, using ideas such as sorting and selecting features. However, obtaining the same type of explanation for neural additive models over continuous inputs, which are far more expressive, introduces new algorithmic challenges: (i) computing and refining bounds for each univariate component using scalable neural network verification methods (Wang et al. 202T), (ii) parallelizing the certification of univariate components rather than the full network, and (iii) em- ploying more efficient selection phase that leverages these outer bounds, sorts the components, and applies a logarithmic search to obtain a cardinally minimal sufficient explanation more efficiently.
Neural Additive Models (NAMs). NAMs extend Generalized Additive Models (GAMs) (Hastie Nelder & Wedderburn] 1972), a classic interpretable family of ML models (Caruana et al.
2017
Zhong et al.) [023] Liu al., 2022 Bordt & von Luxburg 2023] EEnueen & Liu| 2025 Chen et al. 2020). by replacing each univariate component with a neural network, thereby combining in-
2015
terpretability with expressivity. First introduced by (Agarwal al. 202T). NAMs achieved compet- itive accuracy on tabular tasks and were applied in healthcare and COVID-19 modeling. Subsequent works suggested potential refinements of their training and architecture (Radenovic et al., [202]] Chang et | [202]] Bouchiat et al. 2024] Xu et al. 2003) and proposed additional variants (Bechler-
Speicher et al. 2024 Jiao et al. 2024) and applications (Thielmann et al. 2024).
7
LIMITATIONS
Like all methods that obtain provably minimal and sufficient explanations, our approach depends on invoking neural network verification queries, which do not yet scale to state-of-the-an models. Still, neural network verification has advanced rapidly in recent years (Kaulen et al.] 2025 Chiu et al.) 2025
Wu et al.) 2024a), and the scalability of our approach will improve alongside it. Importantly, our method offers two substantially critical improvements: (i) it reduces the number of queries from exponential (or linear, in relaxed tasks) to logarithmic, and (ii) it operates
univariate components fr. where verification is far cheaper since the certified models are small and more interpretable by design compared the entire large model f. Together, these make our algorithm far more practical for NAMs. and we show that it indeed efficiently produces explanations on standard benchmarks where prior algorithms fail. Our approach also relies on a complete verifier, which often come with numeric tolerances and timeout restrictions. A more detailed discussion on this can be found in Appendix D
CONCLUSION
Provably minimal and sufficient explanations represent a highly desirable goal in explainability, as they offer certifiable guarantees on both faithfulness and conciseness. For standard neural net- works, however, this task is computationally prohibitive, requiring an exponential number of verifi- cation queries. We present a NAM-specific algorithm that reduces the complexity from exponential to logarithmic parallelized queries, achieving dramatic gains in both speed and explanation size. Moreover, show that these explanations reveal insights into NAMs that sampling based methods cannot capture. Our work thus makes provable explanations feasible in practice and opens the door to extending them across other interpretable neural network families.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLED
The work of Elboher, Bassan, and Katz was partially funded by the European Union (ERC. VeriDeL, 101 101112713). Views and opinions expressed are however those of the author(s) only and do not nec- essarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. The work of Elboher, Bassan, and Katz was additionally supported by a grant from the Israeli Science Founda- tion (grant number 558/24). The work of Ladner, Şahin, and Althoff was supported by the German Research Foundation (Deutsche Forschunggemeinschatt DFG) under grant number AL 1885/33-,, 1. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union, or any other granting authority.
REFERENCES
Federico Adolfi, Martina Vilas, and Todd Wareham. The Computational Complexity of Circuit Discovery for Inner Interpretability. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
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. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), 2021.
David Alvarez Melis and Tommi Jaakkola. Towards Robust Interpretability with Self-Explaining Neural Networks. In Proc. 32nd Conf. on Neural Information Processing Systems (NeurIPS), 2018.
Guy Amir, Shahaf Bassan, and Guy Katz. Hard to Explain: On the Computational Hardness of In- Distribution Model Interpretation. In Proc. 27th European Conf. on Artifical Intelligence (ECAI), 2024.
Alaa Anani, Tobias Lorenz, Mario Fritz, and Bernt Schiele. Pixel-level Certified Explanations via Randomized Smoothing. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
Marcelo Arenas, Pablo Barceló, Miguel Romero Orth, and Bernardo Subercaseaux. On Computing Probabilistic Explanations for Decision Trees. In Proc. 35th Inf. Conf. on the Advances Neural Information Processing Systems (NeurlPS), pp. 28695-287000 2022.
S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
G. Audemard, Bellart, L. Bounia, Koriche, Lagniez, and P. Marquis. On the Computa- tional Intelligibility of Boolean Classifiers. In Proc. 18th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp. 14-86,22 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 Proc. 31st Int. Joint Conf. on Artificial Intelligence (ICCAI), pp. 643-650, 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. In Proc. 36th AAAI
Conf. on Artificial Intelligence, pp. 5461-5469, 2022b.
Gilles Audemard, Jean-Marie Lagniez, Pierre Marquis, and Nicolas Szezepanski. Computing Ab- ductive Explanations for Boosted Trees. In Proc. Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 4699-4711, 2023.
Steve Azzolin, Sagar Malhotra, Andrea Passerini, and Stefano Teso. Beyond Topological Self- Explainable GNNs: A Formal Explainability Perspective. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
P. Barceló. M. Monet, J. Pérez, and B. Subercaseaux. Model Interpretabilityy through the Lens of Computational Complexity. In Proc. 34th Conf. on Neural Information Processing Systems (NeurIPS), pp. 15487-15498, 2020a.
11

---

Published as a conference paper at ICLR 2026
Pablo Barceló, Mikaël Monet, Jorge Pérez, and Bernardo Subercaseaux. Model Interpretability Through the Lens of Computational Complexity. Proc. 33rd Int. Conf. on Advances in Neural Information Processing Systems (NeurlPS), pp. 15487-15498, 2020b.
Shahaf Bassan and Guy Katz. Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks. In Proc. 29th Inf. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 187-207, 2023.
Shahaf Bassan, Guy Amir, Davide Corsi, Idan Refaeli, and Guy Katz. Formally Explaining Neural Networks Within Reactive Systems. In Proc. 23rd Inf. Conf. on Formal Methods in Computer- Aided Design (FMCAD), pp. 1-13, 2023.
Shahaf Bassan, Guy Amir, and Guy Katz. Local vs. Global Interpretability: A Computational Complexity Perspective. In Proc. 41st Int. Conf. on Machine Learning (ICML), pp. 3133-3167, 2024.
Shahaf Bassan, Guy Amir, Meirav Zehavi, and Guy Katz. What makes an Ensemble (Un) Inter- pretable? In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025a.
Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Matthias Althoff, and Guy Katz. Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025b.
Shahaf Bassan, Ron Eliav, and Shlomit Gur. Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025c.
Shahaf Bassan, Shlomit Gur, Sergey Zeltyn, Konstantinos Mavrogiorgos, Ron Eliav, and Dimosthe- nis Kyriazis. Self Exllanxxg Neural Networks for Business Process Monitoring. 2025d. Techni- cal Report. hhttps://arXia. 2503
Shahaf Bassan, Michal Moshkovitz, and Guy Katz. Additive Models Explained: A Computational Complexity Approach. In Proc. 39th Conf. on Neural Information Processing Systems (NeurIPS), 2025e.
Shahaf Bassan, Xuanxiang Huang, and Guy Katz. Unifying Formal Explanations: A Complexity- Theoretic Perspective. In Proc. 14th Int. Conf. on Learning Representations (ICLR), 2026.
Maya Bechler-Speicher, Amir Globerson, and Ran Graph Neural Additive Network. Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), pp. 90552-90578, 2024.
The Intelligible and Effective
Guy Blanc, Jane Lange, and Li- Yang Tan. Provably Efficient, Succinct, and Precise Explanations. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), pp. 6129-6141, 2021.
Guy Blanc, Caleb Koch, Jane Lange. and Li- Li-Yang Tan. A Query-Optimal Algorithm for Finding Counterfactuals. In Proc. 39th Int. Conf. on Machine Learning (ICMI), pp. 2075-2090, 2022.
Sebastian Bordt and Ulrike von Luxburg. From Shapley Values Generalized Additive Models and Back. In Proc. 26th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 709-745, 2023.
Kouroche Bouchiat, Alexander Immer, Hugo Yèche, Gunnar Ratsch, and Vincent Fortuin. Im- proving Neural Additive Models with Bayesian Principles. In Proc. 41st Int. Conf. Machine Learning (ICML), pp. 4416-4443, 2024.
Ryma Boumazouza, Fahima Cheikh-Alili, Bertrand Mazure, and Karim Tabia. ASTERYX: A model-Agnostic SaT-basEd aopRoach for sYmbolic and score- based eXplanations. In Proc. 30th ACM Int. Conf. on Information & Knowledge Management (CIKM), pp. 120-129, 2021.
Ryma Boumazouza, Raya Elsaleh, Melanie Ducoffe, Shahaf Bassan, and Guy Katz. FAME: For- mal Abstract Minimal Explanation for Neural Networks. In Proc. 14th Int Conf. on Learning Representations (ICLR), 2026.
12

---

Published as a conference paper at ICLR 2026
Louenas Bounia. Enhancing the Intelligibility of Boolean Decision Trees with Concise and Reliable Probabilistic Explanations. In Proc. 20th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-Boud Baaeeeddde-Beeddddd Systems (IPMU), volume 1174, pp. 205-218, 2024.
Louenas Bounia. Using Submodular Optimization to Approximate Minimum Size Abductive Path Explanations for Tree-Based Models. In Proc. 41st Conf. on Uncertainty in Artificial Intelligence
(UAI), 2025. 2025.
Louenas Bounia and Frederic Koriche. Approximating Probabilistic Explanations via Supermodular Minimization. In Proc. 39th Int. Conf. on Uncertainty in Artificial Intelligence (UAI), pp. 216- 225, 2023.
Christopher Brix, Stanley Bak, Taylor T. Johnson, and Haoze Wu. The Fifth International Ver- ification of Neural Networks Competition (VNN-COMP 2024): Summary and results. 2024. Technical Report. https: /tttp:://arxi::2112...
Brandon Carter, Jonas Mueller, Siddhartha Jain, and David Gifford. What Made You Do This? Understanding Black-Box Decisions with Sufficient Input Subsets. In Proc. 22nd Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 567-576, 2019.
Rich Caruana, Yin Lou, Johannes Gehrke, Paul Koch, Mare Sturm, and Noemie Elhadad. Intelligible Models for Healthcare: Predicting Pneumonia Risk and Hospital 30-day Readmission. In Proc. 21 ACM Int. Conf. on Knowledge Discovery and Data Mining (SIGKDD), pp. 1721-1730, 2015.
Chun-Hao Chang, Rich Caruana, and Anna Goldenberg. NODE-GAM: Neural Generalized Addi- tive Model for Interpretable Deep Learning. In Proc. 9th Int. Conf. on Learning Representations (ICLR), 2021.
Hong Chen, Yingjie Wang, Feng Zheng, Cheng Deng, and Heng Huang. Sparse Modal Additive Model. IEEE Transactions on Neural Networks and Learning Systems, (200))3333888777 2020.
Hong-Ming Chiu, Hao Chen, Huan Zhang, and Richard Y Zhang, SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightnsss of Semidefinite Programming. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
Daniel Dadush, Bento Natura, and László Végh. Revisiting Tardos's Framework for Linear Pro- gramming: Faster Exact Solutions Using Approximate Solvers. In Proc. 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 931-942, 2020.
Adnan Darwiche. Logic for Explainable AI. In Proc. 38th ACM/IEEE Symposium Logic in Computer Science (LICS), pp. 1-11, 2023.
Adnan Darwiche and Auguste Hirth. On the Reasons Behind Decisions. In Proc. 24th European Conf. on Artificul Intelligence (ECAI), pp. 712-720, 2020.
Adnan Darwiche and Chunxi Ji. On the Computation of Necessary and Sufficient Explanations. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 5582-5591, 2022.
Alessandro De Palma, Greta Dolcetti, and Caterina Urban. Faster Verified Explanations for Neural 2512.
Networks. 2025. Technical Report.
Ruediger Ehlers. Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks. In Proc. 15th Int. Symposium on Automated Technology for Verification and Analysis (ATVA), pp. 269-286 Springer, 2017.
James Enouen and Yan Liu. InstaSHAP: Interpretable Additive Models Explain Shapley Values Instantly. In Proc. 13th Int. Conf. Learning Representations (ICLR), 2025.
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 Perturba- tion Analysis. In Proc. IEEE/CVE Conf. on Computer Vision and Pattern Recognition (CVPR),
pp. 16153-16163, 2023.
13

---

Published as a conference paper at ICLR 2026
Claudio Ferrari, Mark Niklas Mueller, Nikola Jovanović, and Martin Vechev. Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boul -ouudddd. In Proc. 10th Int. Conf. on Learning Representations (ICLR), 2022.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen Petar Tsankov, Swarat Chaudhuri, and Mar- tin Vechev. A12: Safety and Robustness Certification of Neural Networks with Abstract Interpre- tation. In Proc. IEEE Symposium on Security and Privacy (S&P), pp. 3-18. IEEE, 2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the Effectiveness of terval Bound Propagation for Training Verifiably Robust Models. 2018. Technical Report.
https://arXiv: 181.xxxi:11000.21111
Itamar Hadad, Shahaf Bassan, and Guy Katz. Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees. In Proc. 14th Int. Conf. on Learning Representations (ICLR), 2026.
Ouns Harzli, Bernardo Cuenca Grau, and Ian Horrocks. Cardinality-Mnnimal Explanations for Monotonic Neural Networks. In Proc. 32nd Int. Joint Conf. Artificial Intelligence (ICAI), pp. 3677-3685, 2023.
Trevor Hastie. Generalized Additive Models, In Statistical Models pp. 249-307. Routledge, 2017.
Xuanxiang Huang, Yacine Izza, Alexey Ignatiev, and Joao Marques-Silva. Silla. On Efficiently Explaining Graph-Basee Based Classifiers. In Proc. 18th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), 2021.
Alexey Ignatiev, Nina Narodytska, and Joao Marques- Silva. Abduction-Basse Explanations for Machine Learning Models. In Proc. AAAI Conf. on Artificial Intelligence, pp. 1511-1519, 2019.
Alexey Ignatiev, Yacine Izza, Peter Stuckey, and Joao Marques-Silva. Using MaxSAT for Efficient Explanations of Tree Ensembles. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 3776- 3785, 2022.
Yacine Izza and Joao Marques-Silva. On Explaining Random Forests with SAT. In Proc. 30th Int. Joint Conf. on Artifical Intelligence (ICCAI), 2021.
Yacine Izza, Xuanxiang Huang, Antonio Morgado, Jordi Planes, Alexey Ignatiev, and Joao Marques- Silva. Distance-Restricn Explanations: Theoretical Underpinnings & Efficient Implementation. In Proc. 21st Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp- 475-486, 2024.
Yining Jiao, Carlton J. Zdanski, Julia S. Kimbell, Andrew Prince, Cameron Worden, Samuel Kirse, Christopher Rutter, Benjamin Shields, William Dunn, Jisan Mahmud, et al. NAISR: A 3D Neural Additive Model for Interpretable Shape Representation. In Proc. 12th Int. Conf. on Learning Representations (ICLR), 2024.
Helen Jin, Anton Xue, Weiqiu You, Surbhi Goel, and Eric Wong. Probabilistic Stability Guaran- tees for Feature Attributions. In Proc. 39th Conf. Neural Information Processing Systems (NeurIPS), 2025.
Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. In Proc. 29th Int. Conf. on Computer Aided Verification (CAV), pp. 97-117, 2017.
Guy Katz, Derek A. Huang, Duligur lbeling, Kyle Julian, Christopher Lazarus, Rachel Lim, Parth Shah, Shantanu Thakoor, Haoze Wu, Aleksandar Zeljić, David L. Dill, Mykel J. Kochenderfer, and Clark Barret. The Marabou Framework for Verification and Analysis of Deep Neural Net- works. In Proc. 29th Inf. Conf. Computer Aided Verification (CAV), pp. 443-452. 2019.
14

---

Published as a conference paper at ICLR 2026
Konstantin Kaulen, Tobias Ladner, Stanley Bak, Christopher Brix, Hai Duong, Thomas Flinkow, Taylor T. Johnson, Lukas Koller, Edoardo Manino, Thanh Vu H. Nguyen, and Haoze Wu. The 6th International Verification of Neural Networks Competition (VNN-COMP 2025): Summary and Results. 2025. Technical Report. /tttps://arxiv:25122.. 19007
Young Kyung Kim, Juan Matias Di Martino, and Guillermo Sapiro. Generalizing Neural Addi- tive Models via Statistical Multimodal Analysis. Transactions on Machine Learning Research (TMLRR, 2024.
Suhas Kotha, Christopher Brix, J. Zico Kolter, Krishnamurthy Dvijotham, and Huan Zhang. Prov- ably Bounding Neural Network Preimages. In Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS). pp. 80270-80290, 2023.
Mark W. Krentel. The Complexity of Optimization Problems. In Proc. 18th Annual ACM Sympo- sium Theory of Computing (STOC), pp. 69-76, 1986.
Emanuele La Malfa, Agnieszka Zbrzezny, Rhiannon Michelmore, Nicola Paoletti, and Marta Kwiatkowska. On Guaranteed Optimal Robust Explanations for NLP Models. In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 2658-2665, 2021.
Faezeh Labbaf, Tomáš Kolárik, Martin Blicha, Grigory Fedyukovich, Michael Wand, and Natasha Sharygina. Space Explanations of Neural Network Classification. In Proc. 37th Int. Conf. on Computer Aided Verification (CAV), pp. 287-303, 2025.
Chu Min Li and Felip Manya. MaxSAT, Hard and Soft Constraints. In Handboook of Satisfiability, pp. 613-631. IOS Press, 2009.
Jiachang Liu, Chudi Zhong, Margo Seltzer, and Cynthia Rudin. Fast Sparse Classification for Gener- alized Linear and Additive Models. In Proc. 25th Int. Conf. on Artificial Intelligence and Statisties (AISTATS), pp. 9304, 2022.
Scott M. Lundberg and Su-In Lee. A Unified Approach to Interpreting Model Predictions. In Proc. 30th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2017.
Emanuele La Malfa, Agnieszka Zbrzezny, Rhiannon Michelmore, Nicola Paoletti, and Marta Kwiatkowska. On Guaranteed Optimal Robust Explanations for NLP Models. In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), 2021.
J. Marques-Sile Silva, T. Gerspacher, M. Cooper, A. Ignatiev, and N. Narodytska. Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay. In Proc. 33rd Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 20590-20600, 2020.
Joao Marques-Sikee Silla. Logic-Basce Based Explainability in Machine Learning. In Proc. 18th Int. Sum- mer School Reasoning Web. Causality, Explanations and Declarative Knowledge, pp. 24-104, 2023.
Joao Marques-Silva and Alexey Ignatiev. Delivering Trustworthy AI Through Formal XAI. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 22342-12350, 2022.
Joao Marques-Silva and Alexey Ignatiev. No Silver Bullet: Interpretable MI. Models Must be Explained. Frontiers in Artificial Intelligence, 6:1 1:1222, 2023.
Joao Marques-Silva Silva, Thomas Gerspacher, Martin Cooper, Alexey Ignatiev, and Nina Narodytska. Explanations for Monotonic Classifiers. In Proc. 38th Int. Conf. on Machine Learning (ICML), pp. 7469-7479, 2021.
Reda Marzouk and Colin De La Higuera. On the Tractability of SHAP Explanations under Marko- vian Distributions, In Proc. 41st Int. Conf. on Machine Learning (ICML), pp. 34961-34986, 2024.
Reda Marzouk, Shahaf Bassan, and Guy Katz. SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism. In Proc. 39th Conf. on Neural Information Processing Systems (NeurIPS), 2025a.
15

---

Published as a conference paper at ICLR 2026
Reda Marzouk, Shahaf Bassan, Guy Katz, and De la Higuera. On the Computational Tractability of the (Many) Shapley Values. In Proc. 28th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), 2025b.
Mark N. Müllle, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev. PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximations. In Proc. 6th ACM on Programming Languages (POPL), pp. 1-33, 2022.
John Ashworth Nelder and Robert WM Wedderburn. Generalized Linear Models. Journal of the Royal Statistical Society Series A: Statistics in Society, 135(3)3370-384, 1972.
Filip Radenovic, Abhimanyu Dubey, and Dhruv Mahajan. Neural Basis Models for Interpretability.
In Proc. 36th Conf. on Neural Information Processing Systems (NeurlPS), pp. 8414-8426, 2022.
M. Ribeiro, S. Singh, and C. Guestrin. "Why Should I Trust You?" Explaining the Predictions of any Classifier. In Proc. 22nd Int. Conf. on Knowledge Discovery and Data Mining (SIGKDD), pp. 1144, 2016.
M. Ribeiro, S. Singh, and C. Guestrin. Anchors: High-Precision Model-Agnostic Explanations. In Proc. 32nd AAAI Conf. on Artificial Intelligence, 2018.
Marco Sälzer and Martin Lange. Reachability is NP-Complete even for the Simplest Neural Net- works. In Proc. 15th Int. Conf. on Reachability Problems (RP), pp. 149-164, 2021.
Zhouxing Shi, Qirui Jin, Zico Kolter, Suman Jana, Cho-Jui Hsieh, and Huan Zhang. Neural Network Verification with Branch-and Bound for General Nonlinearities. In Proc. 31st Int. Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 315-335, 2025.
A. Shih, A. Choi, and A. Darwiche. A Symbolic Approach to Explaining Bayesian Network Clas- sifiers. In Proc. 27th Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 5103-5111, 2018.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An Abstract Domain for Certifying Neural Networks. In Proc. 3rd ACM on Programming Languages (POPL), pp. 1-30, 2019.
Jules Soria, Zakaria Chihani, Julien Girard-Satabin, Alban Grastien, Romain Xu-Darme, and Daniela Cancila. Formal Abductive Latent Explanations for Prototype-Basee -Bseed Networks. In Pruc. 40th AAAI Conf. on Artificial Intelligence, 2025.
Bernardo Subercaseaux, Marcelo Arenas, and Kuldeep Meel. Probabilistic Explanations for Linear Models. In Proc. 39th AAAI Conference on Artificial Intelligence, pp- 20655-20662, 2025.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic Attribution for Deep Networks. In Proc. 34th Int. Conf. on Machine Learning (ICML), pp. 3319-3328, 2017.
Anton Frederik Thielmann, René-Marcel Kruse, Thomas Kneib, and Benjamin Säfken. Neural Additive Models for Location Scale and Shape: A Framework for Interpretable Neural Regression Beyond the Mean. In Proc. 27th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 1783-1791, 2024.
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating Robustness of Neural Networks with Mixed Integer Programming. In Proc. 7th Int. Conf. on Learning Representations (ICLR), 2019.
Jorge R. Vera. On the Complexity of Linear Programming Under Finite Precision Arithmetic. Math- ematical Programminng 80(1):91-12) 1998.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsich, and J. Zico Kolter. Beta-Crown: Efficient Bound Propagation with Per-Neuron Split Constraints for Neural Network Robustness Verification. In Proc. 35th Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 29909-29921 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: A Versatile Formal Analyzer of Neural Networks. In Proc. 36th Int. Conf. on Computer Aided Verification (CAV), pp. 249-266, 2024a.
16

---

Published as a conference paper at ICLR 2026
Min Wu, Haoze Wu, and Clark Barrett. Verix: Towards Verified Explainability of Deep Neural Net- works. Proc. 36th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2023.
Min Wu, Xiaofu Li, Haoze Wu, and Clark Barrett. Better Verified Explanations with Applications to Incorrectness and Out-of-Distribttion Detection. 2024b. Technical Report. https: 2409. 03060
Shiyun Xu, Zhiqi Bu, Pratik Chaudhari, and Ian Barnett. Sparse Neural Additive Model: Inter- pretable Deep Learning with Feature Selection via Group Sparsity, In Proc. 27th Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pp- 343-359, 2023.
Anton Xue, Rajeev Alur, and Eric Wong. Stability Guarantees for Feature Attributions with Multi- plicative Smoothing. In Proc. 37th Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 62388-62413, 2023.
Weiqiu You, Helen Qu, Mareo Gatti, Bhuvnesh Jain, and Eric Wong. Sum-of-partss Self-Attrbbting Neural Networks with End-to-End Learning of Feature Groups. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
Jinqiang Yu, Alexey Ignatiev, Peter Stuckey, Nina Narodytska, and Joao Marques-Sin Silva. Eliminat- ing the Impossible, Whatever Remains Must Be True: On Extracting and Applying Background Knowledge the Context of Formal Explanations. In Proc. 37th AAAI Conf. on Artificial Intel- ligence, pp. 4123-4131, 2023.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient Neural Network Robustness Certification with General Activation Functions. In Proc. 32nd Conf. on Neural Information Processing Systems (NeurlPS). pp. 4939 4949, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho Jui Hsich. Towards Stable and Efficient Training of Verifiably Robust Neural Networks. In Proc. 8th Ins. Conf. on Learning Representations (ICLR), 2020.
Wei Zhang, Brian Barr, and John Paisley. Gaussian Process Neural Additive Models. In Proc. 38th AAAI Conf. on Artificial Intelligence, number 15, pp. 16865-16872, 2024.
Chudi Zhong, Zhi Chen, Jiachang Liu, Margo Seltzer, and Cynthia Rudin. Exploring and Inter- acting with the Set of Good Sparse Generalized Additive Models. Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pp. 56673-56699, 2023.
Duo Zhou, Christopher Brix, Grani Hanasusanto, and Huan Zhang. Scalable Neural Network Verification with Branch-and bound Inferred Cutting Planes. In Proc. 38th Conf. Neural In- formation Processing Systems (Newrips), 2024.
17

---

Published as a conference paper at ICLR 2026
Appendix
The appendix contains all proofs, optimizations, additional settings, and additional experiments that were mentioned throughout the paper:
Appendix
contains extended background on neural network verification and formal XAI. contains formalizations that will be used throughout the proofs.
Appendix
Appendix
contains the proofs of Prop. to
Appendix contains theoretical discussion and practical optimizations the importance sorting.
Appendix contains extensions to multi-class classífication and regression tasks.
Appendix contains all experimental details and ablation studies.
Appendix contains an L.M usage disclosure.
A EXTENDED BACKGROUND ON NEURAL NETWORK VERIFICATION AND FORMAL XAI
Neural Network Verification. Neural network verification provides provable guarantees about the behavior of a neural network over a continuous input region. Classical SMT- and MILP-based
approaches (Katz et al. 2017] Wu al. 2024a Katz et al., 2019 Tjeng et al. 2019 Ehlers 2017)
encode ReLU networks and specificcttions as logical or mixed -ittger constraints, yielding exact guarantees but scaling only to toall-to-medium models. Abstract interpretation methods (Singh et al. 2019] Gehr et al., 20088 Ferrari et al. 2022 Müller et al.] 2022) instead propagate layer-wise over-approximations. producing fast yet incomplete robustness certificates. A major breakthrough came with linear-relaxation-beee based bound propagation, notably CROWN (Zhang et al., 2018) and its extensions (Wang et al.) [02T]] Chiu et al. 2025 Zhou et al., 2024; Shi et 2025), which compute tight dual linear bounds and function either scalable incomplete verifiers strong relaxations within exact search procedures. Modern branch-and- bound (BaB) frameworks build on these relax- ations to achieve complete verification scale. In particular, a-3-CROWN and related variants now dominate VNN-COMP (Brix et al.) 2024). handling models with millions of parameters. Recent advances include tighter relaxations (e.g., SDP hybrids (Chiu et al. (2025)) cotting-plane enhance- ments (Zhou et al., 2024), and support for non- non-ReLU nonlincarities (Shi et al.) 2025). Today. verifi- cation methods can routinely certify robustness for moderately large CNNs and ResNets, although significant challenges remain for transformers, highly complex architectures, and richer temporal or relational specifications.
Formal XAI. Our work is part of line of research known as formal expluinable Al (formal XAI) Marques- Silva & Ignatiev] 2022], which investigates explanations equipped with provable guarantees (Yu et al. [023] Darwiche & Jil 2022 Darwiche [2033 Shih et al. 2018 Azzolin et al.)
2025 Audemard et al. | 2021). Because producing such guaranteed explanations is often computa- tionally intractable (Barccló et al. 2020al Bassan et al. 2026 Marzouk et al.) 2025a Marzouk & De La Higuera 2024 Amir et al. 2024; Blanc et al. 2021 2022). much of the literature has concentrated more restricted model classes (Marques-Sil Silva & Ignatiev 2023). including deci- sion trees (Bounia 2025 Arenas et al. 2022 Bounia 2024 Bounia & Koriche| (023), monotonic models (Marques-Silve Silva al. 2021 Harzli et al. 2023), and ensembles (Audemard al.) 2023
2022a Ignatiev et al. 2022 Bassan et al. 2025a Boumazouza et al., 2021). Related to our works, are frameworks that have obtained such explanations for neural networks (Malfa et al. | Bas- san et al. [223 Hadad et al., 2026: Wu et al. 2023 Labbaf et al. 2025 De Palma et al. [025]] Fel
let af. [023] Soria al. 2025). Due the high computational complexity of this problem, several approaches aim to alleviate it through abstractions (Bassan et al. |025b] Boumazouza et al. 20266)
smoothing techniques (Xue et al.) 2023 Jin et al. [025]] Anani et al. 2025), or self-explainngg frame-
works (Alvarez Melis & Jaakkola 2018 Bassan al. 2025c d) You et al. 2022). Another related line of work studies explanations with provable guarantees for linear models (Marques Silva et al.
MMaquue-SSllva 2020 (Subercaseaux et al. (2025), which form restricted subclass of additive models, well the theoretical analysis of (Bassan et al., (022e)), which investigates the computational complexity of generating such explanations for these models.
18

---

Published as a conference paper at ICLR 2026
B FORMALIZATIONS
B.1 COMPUTATIONAL COMPLEXITY CLASSES
We assume readers are familiar with the standard complexity classes polynomial time (PTIME) and nondeterministic polynomial time (NP, coNP); see [Arora & Barak (2009) for introduction. NP and coNP capture the complexity of decision problems - problems whose output is simply "yes" or "no"". In contrast, FP is the functional analogue of PTIME, describing the class of function problems whose outputs may be arbitrary values and can be computed in polynomial time.
We assume that the readers are familiar with the basic complexity classes of polynomial-tine (PTIME), and non-deterministic polynomial-time (NP, coNP) (see an introduction in Arora & Barak 2009 ). NP and coNP are problems that address decision problems. meaning they determine the complexity of problems with yes/no answer. The complexity class FP is the functional variant of PTIME (meaning it returns function as an output rather than a yes/no answer), and describes the class of function problems that can be solved in polynomial time.
The complexity class OptP of functions computable by taking the maximum (or minimum) of the output values over all accepting paths of an NP machine. Alternatively, function F: Σ" + Z is in OptP if there exists a polynomial p(.) and a polynomial -imnia computable function G: > x {0, 1 }o(x) + which we call the value function such that for every input E Σ"
F(X)
max G(X,Y), (E(0,1)00X))
(3)
where Y is witness of polynomial length, the function G can be computed in deterministic poly- nomial time, and the integer output G(X, Y) is polynomially bounded in n |X] We say that problem is in [p)][=(n)] if the solution F(X) is bounded by 2(n).
The class FPNP(=( [=[n) consists of all function problems computable in polynomial time using most 2(2) queries an NP oracle. The seminal work of (Krentel 1986) established that [n)] S [2))) and moreover that every function in FP (n) can be computed by solving an appropriate OptP[z(n)] optimization problem followed by a polynomial-time postpro- cessing step, provided that =(n) satisfies the "smoothness" condition defined in (Krentel 1986).
In functional or optimization problems, a common convention is to work with metric reduc- tions (Krentel [986).. Formally, given some f.g: - - a metric reduction from to g is pair of polynomial time computable functions Ti E f(x) (x, g(T (x))).
x N + N such that for all x E D' we have
B.2 UNIVARIATE NEURAL NETWORK FORMALIZATION
In this subsection, we will formalize the univariate neural network components f:: TR -> IE under our analysis. Let there be a univariate neural network component f with k layers, and an input x E R The output of y == [x) E IR is obtained as follows:
h
h La (h ()),,,,,
y= [s).
where we use La 1 - R to denote the operation of layer & and is defined
La := "Wihh~1 +b").
with the weight matrix denoted as We E QuuXmu- bias vector ba E Q and activation function a: R Re and number of neurons 74 N. Following standard conventions, we assume that all weights and biases are rational numbers encoded binary (as they correspond to trained parameters stored with fixed machine precision), and can be written in the form & for some p, N.
We additionally assume that a is the standard ReLU activation ReLU(x) = max(0, x) function. A NAM is regression or classification model whose core computation takes the form (xx) +
fx,) + 3p. where each f. is a univariate neural network and Bg E Q. We define the size of a univariate component f; as the total bit-length of all its weights and biases, and the size of the full model f as the sum of the sizes of all univariate components f, together with the bit-length of the global bias term So.
19

---

Published as a conference paper at ICLR 2026
Although we present the formulation in the standard feedforward setting, this entails no loss of generality: any model with arbitrary connections can be converted into an equivalent feedforward network by inserting intermediate layers and adding zero-weight connections so that the computa- tional graph becomes acyelie without changing its function. Moreover, ReL.U networks can trivially express basic algebraic operations such addition, scalar multiplication, and the rectifier max(0, x), and can therefore represent any composition of these operations. Consequently, restricting attention feedforward ReLU architectures is fully general for our purposes.
C PROOFS
C.1 PROOF OF PROPOSITION 1
Proposition 1. Given a NAM f. an input x E I" and a perturbation radius Ep E R.,, let Alg. 2 return total list order the input features according to their importance. Then, the following holds: for any sufficient explanation that includes feature i, and for any feature j & such that i j in the list ordering, the set S {i) U {j} is also sufficient explanation.
Proof. We recall that we have assumed in Alg. 2 that f(x yields positive prediction, i.e., it is classified as 1. Accordingly, the final list of bounds [[ [(-/], Auz), ( Auz),... (Á/n: Aux)] is derived by taking the minimum possible value of each fi f&x and computing lower and upper bounds for (x,) - fX,).. The proof we present applies symmetrically to the case where the prediction is negative: in that case, we instead take the maximum value of fi (K;) and bound f. ((,)) fx,). We defer detailed discussion of that case to later. Since we are assuming f (x) 2 0, the condition that a sufficient explanation with respect to (f, x, 6p) means that:
VX E B (x).
((xs:8s) 2 0 +
min f(xs: Xs) 2 0.
(4)
kx
The value of (xxs; is obtained by fixing the features in S to x and perturbing the complementary features S to values from X. Owing to this construction, and to the additive form of the NAM f. which can be expressed as fxx) == Exetoi f((x)), we can establish the following statements:
Σ م4 S (fx(.)) tE5
min Σ (xx)) <
Σ Sun =
KE (x) 188
555
Σ S (fi(())
min f((8.))
E(f(()) f((xx)) S Σ
Aut +
KE (X)
TES
tES
SE5
(5)
Σ ~4 <
[(x)
Σ s((x))
Σ
min ((x:) <
Σ
Aut 4
XE (x)
IES
(Ein]
LES
LES
LES
Σ AES
L4 < (f(x)
min xE (x)
((x;
Σ
Auc.
tE5
Given our earlier assumption in Equation we know that Eies Sut 2 0. sUbiME {i). By applying the same line of reasoning as before, we obtain:
Now define S
Σ au. s (f())
min ((xs:; XEB (x)
S Σ Aus 4
LES'
LES'
(6)
Σ Lu. + مt, UL S (f(x) FES
min xx
f(x:: 5
Au + Auj Auy.
rES
Since we assume that i < in the ordering of [()), Sui) (Al2, Suz). (Âlm, Sun) and that the bounds are non-intersecting. it follows that Ll, ÁI, 2 0 and Au, Aus 0. Consequently, we obtain that (f (f(x)-mingen)" min (x) f(xs; X )) is bounded both above and below by smaller values than (f(x) min (x) f(xs: This in turn implies that:
20

---

Published as a conference paper at ICLR 2026
(x(x)
min ((xs;Kg)) - (f(x) xEB,(x) (x)
min ((xs;Ks) 00 =
xc (x)
min (Xs:
min SER, (x)
(Xs Xg. S.
se (x)
Moreover, since e (()) (x) [xxs: K5) is non-negative by Equation it follows that:
min xE
f(x:; min (xx: 0
SEB (x)
(8)
VX E (x).
f(xs:88) 20.
which establishes that S' constitutes sufficient explanation for (f, x, Ep), thereby concluding this part of the proof.
We now turn to the symmetric case, where fxx < 0. In this setting, Alg. is applied symmetrically by taking the maximum admissible value of each (x:) and deriving corresponding upper and lower bounds for (x:) - fx,.). [(S),, Au, ). (112, Auz)..... (Óin, Su,,)] is now sorted in descending importance values, instead of ascending. Given the assumption that f(x) < 0, the requirement that constitutes a sufficient explanation with respect to (S, x,x <p) can be expressed as:
VR E
f(xsi 8g) <0 + max f(xs: <0 kE)
Analogous to earlier case, leveraging the additive structure of the NAM f. which can be written as fx) == Eig(n) (x.), together with the definitions of (xs; xg) and of the bounds Ál, and Au, we can derive the following chain of statements:
Σ S E max f((x)) f((x))) S Σ Au =
LES BE (x)
Σ 54.
Σ max
fe(e)) f((x))
(f((x)) f((x:))
Σ
Au
" (x)
FES
LES
EES
SES
(10)
Σ YI S Σ max (x + Σ ((()))
Σ [xxx, S Σ
Au
KEB (x)
LES
EE
(E(m)
tE$
Σ E4 <
max f(xs:As) f(x)) < Σ
Aue.
xE (x)
tES
(ES
Since know that Eles Au, 2 and by defining S' = S U [i} \ (i) as before, we can now derive that:
< max f(xs:;8g)) f(x)) < Σ Au REB,P(x)
LES'
LES'
(11)
Σ Lt, Ât Li tES
((xs; S Σ Au, + Au, Auz.
max B (x)
t55
As before, since we assume i < j in the ordering of [(Á,, Lu)), (ال2, Suz)... (Sin, Au,)), } and given that the bounds are non-intersecting, together with our assumption that this list sorted by decreasing values, it follows that Át, Ál, and Su, - Au, 2 0. Consequently, we obtain a different outcome: namely, max max (x) (f(xs; f(x)) bounded above and below by strictly larger values than m (w) (f(xs: fx)). This in turn implies that:
21

---

Published as a conference paper at ICLR 2026
max f(x): [(x)) - max f(xs:8g) f(x)) 0 x (x)
B= (x)
(12)
max f(x)::8)) xeB (x)
max f(xs: Kg) S. R (x)
Moreover, since Equation 9 eensures that maxien (x) (xs; Kg) s)) is negative, we obtain:
max xE (x) s(xs; S max f(xs; <0-
xEB7(x) (x)
(13)
Vx (x) f(xs;;8.) <.
This establishes that S' is sufficient explanation for (f. x, cp). With this, the negative case for f(x) resolved, and together with the positive case, the proof complete.
C.2 PROOF OF PROPOSITION 2
Proposition 2. Given parallelized processors, Alg. 2 performs an overall number of Tp(n)
=
o ((# (())) max4e(n] B.-ax
O (lo maxie|m] m) calls to the verifier, each on p-nn
((()) component, where & == min min( Au,1, مt, 1l.
Proof. The algorithm terminates once no two univariate functions S4 and ʃ3 have overlapping bounds. Because the procedure relies on binary search, each phase divides the current interval into two. Initially, the gap between the upper and lower bounds for feature i is exactly a, - (x.). The precision achieved for feature limited by the smaller of the two distances: either the distance to the bound of the feature directly above it in the ordering (i+ 1) or the one directly below it (i 1). Accordingly, we denote the overall precision for feature by &a as:
& == min Sw,,, بكر Su--113
(14)
Overall, given the binary-search procedure, where the interval is split at each iteration, we define the number of splits performed for single feature as:
B
0
< E1
2
(15)
Bi a'
h;
< 0 log(
Consequently, the feature on which the maximum number of splits is carried out, denoted by kmax- is:
O max [log(
Br (a-a))))
kmaa S
(16)
iE[n]
Each feature i E [n]] is therefore bounded by at most kinzz verification queries. Consequently, the total workload is upper bounded by n kman- and when distributed across p threads, this yields the following parallelized complexity result (n)::
Tn(n) s O(()) kmaz) s =0((2) log mmxx
Br (=a)) &
(17)
iE[m)
This completes the proof.
22

---

Published as a conference paper at ICLR 2026
Ty(m) S O((2) kima)) S (0(2)) max (log
max 0zi 3g
))
(18)
iE m) &,
C.3 PROOF OF PROPOSITION
Proposition Given NAM f, an input x E R", and perturbation radius Ep RR, Alg. per- forms (m) queries and returns a cardinally-minina, sufficient explanation. This stands in contrast Alg. which only guaranteed return a subset minimal sufficient explanation.
Proof. We begin by noting that the algorithm proceeds iteratively, making |n| calls to the query suff(f, S \ (1), sp). Each such query can be encoded using neural network verifier, which implies that the algorithm requires (nn) invocations total. We now turn to proving that Alg. B indeed produces cardinally-mining prove that Alg. provides a valid sufficient explanation. This result is straightforward since the last condition that is checked is that: suff(f, x, S [t], Ep), and after this condition is met S is updated to be S {i} and is returned. Hence, by definition, the sufficiency of the returned subset is satisfied.
sufficient explanation with respect (/ x, Ep). First, let us
perdinally-miniiee sufficient explanation with respect to (f. Gp). Let 1 < E represent the last feature that was attempted to be removed from in Alg. 3 Then, for S' : S {e), it follows that: suff(f, x, S', (p) does not hold true, implying that S' is not sufficient explanation for (f, x. Cp). We begin by proving first lemma that will help us proving our proposition:
We will now demonstrate that the generated set S is
Lemma 1. Given a NAM f. let Alg. 2 return the sorted, non-intersecting list of pairs: [(A11, Au1), (Ólz, Suz)..., (Ain, {u Then, the following holds: if S that denotes the top |8] features ordered by [(S), Au1), (Al2, Suz)..... (Âlns Lun)] is not sufficient explanation concerming xf,x, Ep), then any subset S' C [n] of size [S] is also not a sufficient explanation con- cerning cp).
Proof. We begin by noting that S S [n] is not sufficient explanation with respect to (f. (p). Assume, for contradiction, that there exists some S' * S of the same cardinality as S that is a sufficient explanation with respect to (f.x. Since both and S' have equal size, we can map each feature in S' with one in S according to their position in the ordering ((4), Au,), (ól2,
Au,)),
By definition, S consists of the top |S| features in this ordering. Consequently, under the mapping, each feature in S' is mapped to feature of strictly higher equal rank in S. Now consider sequence of replacements: at each step, replace a feature of S' with its corresponding equivalent or higher-ranked feature from S. [rop.pensure that each such replacement preserves sufficiency, since a "lower-ranked" feature is being swapped for a "higher-ranked" one. Iterating this process eventually transforms S' into S, while preserving sufficiency throughout. Thus, S must itself be sufficient explanation with respect to (J,x, 6p) contradicting the initial assumption that it not. This completes the proof.
From Lemma since the features in S' { are the features with the highest |S'|
|
orderings, it holds that any subset S" C [m]] of size |S'| is not sufficient explanation. To conclude the remaining parts of our proof, we now will make use of another lemma:
Lemma 2. Let there be some f. x, and Ep. Then, ifS C [n] is not a sufficient explanation concerning (f.x, then any S' S is not sufficiett explanation w.t (f,x, Cp))-
Proof. I C [n] is not a sufficient explanation with respect (f, x, Ep), then:
3z By s(xs; 2g) + f(x).
(19)
Assume, towards contradiction, that there exists some S' C S which a sufficient explanation. In other words:
V (x)
s(xs;; (xx).
(20)
23

---

Published as a conference paper at ICLR 2026
However, consider vector z' obtained by fixing the features in S' to the features in S S'S' also to x, and setting all remaining coordinates according to z. By the earlier implication from Equation 20) must then have that: f z'z)) * fx) and this contradicts the assumption that S' is sufficient (Equation 19
We now proceed with the remaining part of proving our proposition. Since we know that there is no explanation of size |S'| |8| concerning (f.x, Gp) from the previous part of the proof, now can use the result in Lemma to conclude that none of the subsets of these subsets of size |S"] not sufficient explanation too, which implies that there does not exist any explanation of size lower or equal to |S'| 1 which is a sufficient explanation of (f. xpt), which proves that S is a cardinally-minimal sufficient explanation, hence concluding the proof.
C.4 PROOF OF PROPOSITION 4
Proposition 4. Given NAM f. an input x RR, and a perturbation radius 6p E RR,, Alg. performs (I)) queries and returns a cardinally-minima sufficient explanation.
Proof. We will show that, given the ordering of features [(St1, Su1), (óكg, Suz).... (An, Aun) there exists exactly one index i E [n] such that S = [i + 1] is a sufficient explanation while S' not. Moreover, this statement holds for any ordering. Our proof follows as a consequence of lemma closely related to Lemma [ which we restate and establish below:
Let there be some f, x, and Ep. Then, i E [n] is sufficient explanation concerning (f.x, Ep), then any S' for which S C S' is also sufficient explanation w.r.f (p))
Lemma 3.
Proof. This follows directly from Lemma 2 Since S is known to be sufficient explanation, assume for contradiction that there exists some S' S [n]] with S C S' such that S' is not a sufficient explanation. By Lemma 2 this would imply that subset S" C S' could be sufficient explanation contradicting the fact that S C S' is sufficient.
To conclude the proof of the proposition, consider iterating over the features sequentially according to their ordering. We begin with the empty set @ and test whether it is sufficient explanation with respect to (f, x, cp). If it is not, we proceed by adding features one at a time: first {1}. then {1,2), then {1, 2,,2,3, and forth. Eventually, we encounter some feature E [m] such that [i] is sufficient with respect to (f, x, (p)
(.).., By Lemma 3 any S satisfying [i] C S is also sufficient. Hence, the unique
transition from insufficiency to sufficiency occurs between [ - 1] and [i]. and there can be no later index j > i for which [j] reverts to being non-sufficient before becoming sufficient again.
Since we have already established this claim, it follows that the binary search in Alg. which halts upon identifying the first feature where [t] is sufficient but [ 1] is not, will return the same subset as the iterative "naive" Alg. 3 which incrementally traverses features in a greedy manner and outputs [t]. Moreover, Prop. shows that Alg. 3 always converges to a cardinally- explanation. Consequently. Alg. must also converge to this same meddinallymmiimee explanation, but with only (llg(nn) sufficiency checks rather than On.). This completes the proof.
C.5 COMPUTATIONAL COMPLEXITY RESULTS ON FINDING MIDNNALLY-MINIMAA SUFFICIENT EXPLANATIONS NAMs
In this subsection, study the nature of the computational complexity of obtaining cardinally min- imal sufficient explanations for NAMs. For clarity of presentation, we begin by formally defining and naming the computational problem under consideration.
Minimum Sufficient Explanation for NAMs (MSE-NAM).
Input. A NAM f: R - {0, 1}. input E R", and E Q perturbation around x.
24

---

Published as a conference paper at ICLR 2026
Output. The smallest i E N for which S _ [n] is a sufficient explanation concerning (f. c), such that |S] = k.
The proof is divided into membership component and hardness component. We begin by proving membership.
Claim 1. The MSE-NAM problem is in FPP where N represents the model size encoding.
Proof. We establish membership in FPNP (O()) by demonstrating that the problem can be solved via an Op)) computation followed by polynomial-time post-processing step, which to- gether place the problem in FP* [PNN] (Krentel 1986). We begin with the first part of the proof:
Lemma 4. Consider a ReLU neural network f: R" + R", an input x E R", and a radius c E Q Define the e-ball around as (x) == {z R": X; cs 2, Sx; + e) for all i [n]. Then, the problem of computing max P. (x) (f(z) + ... + f()).) lies in (P)]
Proof. We prove this lemma by expressing our problem as a special case of the neural network reachability problem introduced by Sälzer & Lange (202T). In their formulation, broad class of input specifications t/in and output specifications Vous is supported. For our purposes, we restrict to particularly simple instance of their framework: each input feature x; is constrained by rational lower and upper bounds 4, u, E Q within thin and each output feature y; is constrained by the same type of bounds within Voutt That is, we only consider specifications of the form 4 < < u, and 4 S y; I Uj which are directly supported in the formulation of [aäzzrr & Lange 2021
We now
proceed to formally define the neural network reachability problem.
Neural Network Reachability (NNReach) (Sälzer & Lange 2021). Input. A neural network model f: R. Vin Xx,...., ..)....,,. and an output specification (Y
Ra with ReI.U activations, an input specification
Output. Yes if there is x RR" such that thin (x) and (f are true.
Sälzer & Lange (202T) showed that the NNReach problem lies in NP. Since input assignments cannot be guessed directly as witnesses in continuous domain, their approach instead guesses the activation pattern (active/inactive) of every neuron. Once this activation-status is fixed, the network becomes a purely linear system, and the reachability question reduces a linear program (LP) over all input variables X1...., Xx, output variables yI:.... and additional auxiliary variables corresponding to neuron operations. This LPP can then be solved polynomial time, establishing NP membership.
We now will describe the NNReach problem in our specific context. We now have a model f: R -> R" (meaning the output vector y is of size rt). We take the input specification thin to be set to be x; -- S X; S X; + e for each x; and taking no output specification over y. We know via the result of (Sälzer & Lange, 202T) that this problem is in NP. We now can define the mapping function G(X,Y) (within our definition of the complexity class OptP in Appendix B such that Y E {0, 1}p((X(1) is the witness assignment used by (Sälzer & Lange 2021 to show membership in NP for the NNReach problem (the activation status of each ReLU), {0, 1 p((l)) denotes the set of all 0-1 assignments to active/in-active neurons within the linear program, and the function G defines the same linear program as in (Sälzer & Lange 202T) while solving the task of maximizing the value ofy, + Y2 + ... Yn, (the sum of all output values). The result for single witness will give this maximal value in the e-ball region around x, for one specific linear region in the domain determined
by the witness guess of activation statues Y. However, by taking
F(X) = max C(X,Y),
(21)
(E(D.))o(X))
F(X) will give us the maximum value out of all of the aforementioned maximal values in the e- ball region around x that are determined by guessing activation statues of neurons. This, together, (z)),,, which shows that this problem
implies that the F(X)= = max (f(z)) + + + + is in OptP. Now, since this optimal is a solution to some linear program defined over the paramters of the model - know that it is finite and bounded by the precision of the program's 's parameters. Suppose each weight and bias in every univariate model f; is encoded as a rational number Pi with 4; 4. N, given in binary. Let p' and o' denote the maximum numerator and denominator of weights/biases appearing anywhere in the overall model f, and define d' := max([p'), lg A naive upper bound on the magnitude of the optimal LP solution is (dd)), where m is the number of
25

---

Published as a conference paper at ICLR 2026
weights and biases in f, which in turn can be encoded using O(m log(d)) bits, and is particularly linear in N. This shows that this problem is particularly in OptP(O(N).
After establishing that the optimization step lies in (VV), we now complete the member- ship proof for FPNP [O[N] for our original problem by describing the required polynomial post- processing. The first observation is that the result proven for any Rel.U-activater neural network f: JR + R (Lemma 4 also applies to networks of the form 3o + f1 (X₂) + ... + In (x,), i.e., the inherent structure of NAM models where each f. is itself univariate ReLU network. This fol- lows because such a sum is again a neural network under the same formalization. maximizing minimizing the full expression Bo fi(x1) +...+++. + fn (x,, reduces to maximizing or minimizing each univariate component fx(x,) independently. After carrying out this procedure equiva- "collapse" to discrete singular points - allowing us to apply either Alg. 3 or Alg. 4 to compute
this structure,
maximize each univariate component, this yields total ordering over the features lently, all bounds in Alg. 2
aurdinall-minimas sufficient explanation (as proven in Prop. B) and return its size k. Since the entire procedure consists of an OptP (O()) computation followed by polynomial-timg post-processing step, the overall problem belongs to [O()) This concludes the membership proof.
Lemma 5. The MSE-NAM problem is (I))))( -Hard under metric reductions.
Proof. To prove hardness, our main reduction will be from the Maximum satisfiability (MaxSAT) problem, which is known to be OptP OptP[O[log' (log( N -complete (Krentel 1986). Before introducing this problem formally, we first recall the relevant background notion of CNF -ati-aafiiiaiility (SAT):
Consider set of Boolean variables XI....,X,, E (0, 1}. Let m denote the number of clauses. For each 1 < i < m, we define the clause C₁ as follows:
C X V X..2V.... .........
(22)
where each literal j.j is an element of X,,, E (XI..... Xn, -X1, ...... -X, and kę e N denotes the number of literals appearing in clause C.. The full CNF formula @ is then given by:
Φ = C1 A C2 A... - Cm-
(23)
For instance, take the following CNF formula Φ:
Φ = (X1,1 V V VI ) A (X2,1 V V (22 A... A (Xm,k, V... V Xm.km)) (X7 X2 V3 Xs) (X2) A (Xs -X)).
(24)
We say that clause C, or the entire formula Φ satisfiable there exists Boolean assignment E 1) to the variables
},} that makes it evaluate to true. For instance, in the example above, assigning X; = 1, X2 = 1, and X, satisfies all three clauses Ct, C2 and Ca. and therefore satisfies 6 well. This leads us to the classical definition of the SAT problem:
CNF Satisfiability (SAT).
Input. A Boolean formula @ in CNF. Output. Yes, if Φ is satisfiable, and No, otherwise.
In our setting, we also rely on the optimization versions of these problems, specifically the MaxSAT problem (Li & Manya 2009), which asks for an assignment that maximizes the number of satisfied clauses, equivalently:
Maximum SAT (MaxSAT). Input. A Boolean formula in CNE
Output. The maximum number of simultaneously satisfied clauses, i.e.,
max 1
[cC, satisfiable a))
(25)
Before presenting the proof, we first formalize several auxiliary problems that will be needed. We begin by recalling the Neural Network Reachability (NNReach) problem of Sälzer & Lange (202))
26

---

Published as a conference paper at ICLR 2026
which previously used for establishing membership. That work shows that NNReach is NP- Hard. Moreover, it proves that hardness persists even for networks with a single output and under very simple input specifications, namely, when each imput feature x; is constrained only by the bounds 0 S X; S (Theorem 3 in their paper). Importantly, all reductions in (Sälzer & Lange) 2021) proceed by first showing hardness over binary input domain 10,1)" and subsequently extending the construction to the continuous domain [0, As a result, NP-hardness holds in both settings. Building on this, we frame the restricted version of the neural network reachability problem considered in their work as Restricted Neural Network Reachability (R-NNReach), which was established be NP-Hard in Sälzer & Lange (021).
Restricted Neural Network Reachability (R-NNReach).
Input. A neural network f: (0, 13 + RR an input specification t/in (X,,...... Xn) set to: Vin = Niz1 X; 2 0 A S 1 and an output specification (y), set to: Voou := y= for some r E Q
Output. Yes if there is an x E RR" such that vhnn (x) and (x)) are true.
We will also introduce an additional variant of this problem that will support our maximization- related proofs:
Maximum Restricted Neural Network Reachability (MR-NNReach).
Input. A neural network f: {0, 13" - R, an input specification vimm (K1,.... .......,,, Xn,) set to: vinn =
Niz X; 2 0 x; S L.
Output. The maximal value of fx) for which eiin cin(() is true.
We will break down the rest of the proof into four central parts:
Lemma demonstrates how the NNReach problem, specifically its restricted variant, R- NNReach, which was originally obtained via reduction from CNF-SAT (Sälzer & Lange) Katz et al. 2017), can be extended to support a reduction from the Maximum SAT problem. In particular, the lemma establishes that MaxSAT admits polynomial-time duction to MR-NNReach.
2021
2. Lemma 7 demonstrates that by incorporating an additional technical gadget, similar to the construction in (Sälzer & Lange 2021) but requiring non-trivial technical adaptation, we can extend the hardness result to the continuous domain. In particular, this shows that the reduction continues hold when considering function f: [0,1]" RR
3. Lemma g shows that a ReLU network can implement a binary decomposition procedure, and that this construction can be layered on top of our model. This, in turn, demonstrates that the reduction from MaxSAT to MR-NNReach continues to hold even for fi that is a univariate network of the form f:: {0, 1,.... 2" 1} R. Lemma 9 then further extends this reduction to the fully continuous setting, i.e., to functions of the form ft: R + IR
4. Lemma 10 provides reduction from MaxSAT to MSE-NAM by constructing NAM containing m univariate copies of the formula & that are constructed via Lemma 9 (where is the number of clauses in the original CNF). This construction allows us to recover the exact MaxSAT optimum, thereby establishing that the problem is OptP[O(loge N) -ardd
Lemma 6. The MaxSAT problem can be reduced in polynomial time to MR-NNReach.
Proof. We begin by revisiting the NP-hardness proof from (aälzer & Lange 2021). which provides a technical correction to the original argument in (Katz et al.) 2017). This correction addresses subtleties that arise when extending the reduction from the Boolean domain to the continuous setting a point we will return to later. For the moment, ignoring this distinction, the two reductions are effectively identical. We present this construction first. The idea is to reduce CNF formula with m clauses to a ReLU-activare neural network f {0, 1}" follows:
n + R. which can be formalized as
y
ma 1- Σ f((x)))
(26)
where fx(,,) X,* if X appears positively in C,. and xx) 1 - Xy,x if it appears negatively. The corresponding neural network can then be constructed in a direct manner, since both linear transformations and (0. operations readily expressible using ReL.U units. This
27

---

Published as a conference paper at ICLR 2026
reduction explicitly established in both (Katz al., 2017) and (Sälzer & Lange 2021 As
shown therein, it follows immediately that for any Boolean assignment a E [0, 1 to Ø, we have:
max(0, 1- - f((x;))) =0 3> C is satisfied by a.
(27)
From this point, it is straightforward to show that imposing an output constraint of Vou := y m holds if and only if every clause in is satisfied. From here, it is straightforward to prove that when setting an output constraint aout of y = m, it holds that the formula is satisfied and only if all clauses in encodes the number of satisfied clauses. Consequently, the same reduction immediately yields a polynomial-tin reduction from MaxSAT to the MR-NNReach problem.
satisfied. Moreover, observe that in this construction the output value y already
Lemma 7. The MaxSAT problem can be reduced in polynomial time to MR-NNReach when defined over a neural network of the form f: [0,1]* 1]" I.
Proof. We now shift the reduction from the binary input domain {0, 1}" to the continuous region 10.1 To do so, we employ technique analogous to the Bool* gadgets introduced in (Sälzer & Lange 202T). We begin by briefly recalling the role of Bool gadgets in the standard CNF-SAT reduction, specifically, how they allow one to migrate a hardness proof from discrete Boolean domain to a continuous one. We then describe how this construction can be adapted to our setting.
In the standard reduction from SAT to the R-NN-Reach problem, the authors of (Sälzer & Lange 2021 propose the following construction.
x:) + max (1, x, 2) max (0, 1 y max (0, 2
Σ f((x)))) (m 1=0
n 2 (28)
The term + / is omitted in their presentation, but including here does not affect the correctness of the reduction and will later help streamline our exposition. As demonstrated in (Sälzer & Lange 2021 the expression z; max(0, 1 xx) + max(0, X; })) evaluates to:
if < 4
(29)
X; 2
otherwise
Thus, we have that (0, 2 x:) + max(0, () 0 if and only if E (0.1). This gadget therefore forces each binary feature to take value of either 0 or In practice, (Sälzer & Lange 2021) implement this in their reduction by imposing output constraint your requiring y m. This is because the expression:
Σ m0 1
10,
Σ ((x)))
2=0
which refer as the "maximal-clauses optimization term", is always non-positive. Conse- quently, in order to enforce y = m, it must hold that the following term:
(ma 1 - x;) max0maxx.. -xx---1 1)
which we refer to as the "binary-value regularizer term", always evaluates to exactly a As ex- plained earlier, this occurs if and only if every x; takes strictly binary value in (0, 1).
2
We now aim to apply an analogous transition, from binary inputs to continuous domains, in order to output constraints; the
reduce MaxSAT to problem. In the MaxSAT case, note that there objective is simply to maximize the number of satisfied clauses. Intuitively, we want to maximize the maximal-clause optimizer term while simultaneously enforcing that the binary-value regularizer
28

---

Published as a conference paper at ICLR 2026
term remains exactly 2. which, as before, holds if and only if all variables x; take values strictly in {0, 13.
However, when using the construction of (Sälzer & Lange 2021) described in Equation 30 jointly maximizing all components may, in some cases, prioritize increasing the maximal-clause optimizer term the expense of the binary regularizer. This cause the input variables to drift away from strictly binary values. To prevent this, we need to amplify the "weight" of the binary regularizer so that maximizing it is always strictly preferable. One way achieve this is by maximizing term of the following form:
:: C. ma (0, x:) +max(0, 2) Σ max(0, 1
Σ fxxx;))) (m C.n, (30)
We can now set C == |0| + 1, noting that the term below can still be implemented by neural network simply by adjusting the appropriate weight. With this choice of C, we obtain the following property for y:
Claim 2. The maximal value of y when is taken from [0, 11th is equal to the maximal value of when x is taken from {0, 1)"".
Proof. Assume, for the sake of contradiction, that the maximum attainable value of y is achieved at some imput for which at least one coordinate satisfies x; (0, 1). Suppose in particular that x; 2 2. Then, by Equation 29 we have:
1 1 - x:) + max(0, x; 2) x; 2 max 0, 2
(31)
We show that raising the value of x; to exactly strictly increases the value of y. Suppose the current value is x, = e. Increasing it to increases the binary value regularizer term by C = e- (lø) + 1). Importantly, regardless of how this change affects the maximal clause optimizer term, even if it leads to a decrease in that decrease cannot exceed (lo) + 1) e, since this term contains strictly fewer than |6| + summands. Consequently, the net effect is that y increases, implying that the current value of was not maximal.
Now suppose that x; < 1. In this case, Equation 29 implies that:
1 max(0,, 5 xx) + max(0, x; (/ 2
(32)
We now show that decreasing the value of x; to exactly 0 increases the value of Let the current value be x; := Reducing to 0 increases the binary value regularizer term by e-C +l)) As argued earlier, although this change may affect the maximal clause optimizer term and may even decrease y - the decrease is bounded above by (lØ) + 1) c, since this term contains strictly fewer than @0) + +1 components. Consequently, the net value of must increase, contradicting maximality.
Lemma 8. Let there be some input region: D, := |0, 2 1) Z. is possible to construct in polynomial time a ReLU neural network f: D. + (0, 1)"h with polynomial size such that f(x) bin(x), where bin(x) is the binary decomposition vector of x.
Proof. We begin by mapping a single discrete value x E 1......., - 13 to its corresponding binary representation using a polynomial-size ReLU network. This step performs the classic binary decomposition procedure, which is outlined in Algorithm 5
We construct the neural network directly implement the mathematical operations of the algorithm. Starting from the input integer x provided to f. the network proceeds through n iterations, where each iteration consists of three sequential layers. At iteration i, the values r", q and b' encode the corresponding intermediate values maintained by the algorithm. The value 5² at each iteration is passed through residual connection the i-th component o, of the output layer vector Formally,
29

---

Published as a conference paper at ICLR 2026
Algorithm 5 Binary Decomposition
Input: integer z, number of bits n with 0 S x < 2"
1: r x-2 I
2: for each = to do
3:
q - r/ 1--
4: if' 2 then
5:
b; +
6:
-----
7:
else
8:
b; + 0 end if
9:
end for each
11:
return (bu..... bn
Op-1
ReL.U
ReLU
ReL.
ReL.U
ReL.U
ReL.
ReL.U
ReL
ReI.U
p
8
p4
5²
,2
g=-1
Figure 4: The computation of the binary decomposition defined in Equation output vector Og...., .n-1 representing the binary decomposition.
33
with input and the
the construction is defined follows:
r.
g' =max(0, 2n-1-i 1),
b² max(0, (0,2" 2" q²) max (2 g¹) 1);
(33)
p-1 -p 2n-1- max (0, b²),
o, = b¹,
the input provided to We illustrate this construction in Fig. Although this construction is not optimized, it still has polynomial size and can be implemented using ReLU activations. In particular, all required operations exact ReLU constraints, addition, multiplication, and subtraction can be realized through standard neuron and weight configurations.
where T
By induction, the neural network precisely simulates the algorithm. At iteration computes 2--1 = 2n-1 If x 2 2n then q² receives a positive value in the range [_,.1]] (the lower bound follows from the assumption that x a discrete value in (0, 1,..,,..,2 2n-1)) }). If < 2n-1, then of is set 0. When q' O. the corresponding bit b' is also set to 0 and mapped directly to the output When q² is positive necessarily within [ 1] due to discreteness - b² is set to 1. The value of r is then updated exactly as prescribed by the algorithm, and the same process continues recursively for each iteration. All steps mirror the standard binary decomposition algorithm, and their correctness follows immediately from that correspondence. The only modification concerns computation of b', which remains valid as long as the g² values stay above I. This condition
0, the model
r"
za
always holds because the input assumed to discrete in the range (0...., 2n-13, JJ, ensuring that all values 6² and r' remain discrete throughout the computation. Consequently, the final outputs Op, On-1 correctly represent the binary decomposition of
Claim 3. It is possible to construct in polynomial time ReLU neural network f: [0, R with polynomial size such that {0, 1)" C 1)) S [0,1]", 1)"", where we denote f(00, 1]) : {f(() x e [0, 1)).
30

---

Published as a conference paper at ICLR 2026
Proof. We construct the neural network f as follows. First, apply linear transformation to the input layer z that multiplies it by 2" 1. This scales the input so that, in the first hidden layer, obtain single neuron y whose range is precisely [0, 20, - 1]. Next, feed this neuron y into the construction from Lemma X That lemma establishes that every discrete value in the domain {0, ,,...,,, 2nd -} is mapped to its corresponding n-bit binary representation. Since these binary representations cover the entire space {0, 1)", the image of our network f. when restricted inputs where y {0, I,..., 2n - 13. already contains all binary vectors. Moreover, because the actual domain of is the full interval 00, 2" 1| - which strictly contains all discrete values {0, 1......."" 2 1 it follows that {0, 1)" remains within the image of the overall model f-
For the second part of the proof, namely, establishing that f((O, 1)) S [0, 1]", we observe that in the construction of Lemma 8 each output neuron o, fed the value of b' = max(0, 2n g²) max(0, (2 q - 1). By construction, this expression always evaluates to a value in the interval [o, 1] for any real-valued q'. Consequently, every output coordinate lies in [0, 1]. completing the proof.
Lemma 9. The MaxSAT problem can be reduced in polynomial time to MR-NNReach when defined over a neural network of the form f: R E.
Proof. In this proof, we show that the reduction from MaxSAT to MR-NNReach established for neural networks of the form f:: [0, 1|" - IR (Lemmal) remains valid even when the target model
has the form f: IR > R. Since the MR-NNReach problem includes input constraints t/in requiring
each input variable x; satisfy 0 S x; < suffices to consider models with domain [0. 1]. Using
Claim 3 we construct a neural network f:: [0, 1] - IR" whose image satisfies {0. 1)" [(0, 1)) C [0, 1].1 Next. we apply the construction from Lemma to obtain a model f [0, 1jmh - R whose maximum value over [0, 1]" corresponds exactly to the optimal value of the MaxSAT instance.
Importantly, that reduction explicitly enforces that any maximizer of f'(x) must satisfy x E (0, 1). even though the domain is [0, 1]" We now define g == f" f. and for clarity denote the components by 9f == andd
and gy == f', so that g = 9r o 9y- The constraints introduced in Lemma still apply to the inner component gf, ensuring that its maximal value is attained only on Boolean inputs. Moreover, Claim guarantees that the range of g includes all Boolean vectors {0, 13" and excludes any point outside [0, 1la Therefore, the maximal value attainable by gr when composed with gf is exactly the same as the maximal value attainable by f over [0, 1j" Consequently, the overall reduction continues to hold for neural networks of the form f: R TR, completing the proof.
Lemma 10. There exists meiric reduction from MaxSAT to MSE-NAM.
Proof. Given the CNF formula d, we first apply Lemma 9 to reduce it univariate neural network f:: R- R. We pick an arbitrary value x; E [0. 1). Let us assume for simplicity that fx,) = r. We can "normalize" this value by appending an additional final layer with weight 1 and bias -r, yielding a modified model f' for which (x:) 0 (though, for ease of notation, we continue to write f)- Note that under this transformation, the optimal value of f also shifted by r. Furthermore, we note that by appending an additional layer with weight -1, we can "mirror" the univariate component, yielding -fi- We then construct NAM consisting of m² univariate components -/i. We now form a vector x E {0, 1)m² by repeating the x; value m² times. We set e = [0, 1] and define the intercept of the NAM as So == m² This completes the construction of the corresponding MSE- NAM instance. We now observe that it holds that:
m
f((x)) + Bu = - m² > 0
(34)
In other words, this means that fx) receives the positive label, i.c., f(x) = 1. Let us assume that some explanation S is sufficient explanation of size kt For S to indeed qualify as sufficient, it must
31

---

Published as a conference paper at ICLR 2026
satisfy the following:
-E (xx
Σ
max fi(z:) + 30 20 = Σ e0 iES
max fi(z:) + 30 20 -
(0,1
1ES
:ES
(35)
max fz,), 1 m²
m2
-|5| max
fi(z:) + m² 2 0 E
E
|8|
m² k
This implies that sufficient explanation of size & exists if and only if:
(m² - k) max fz:) S m²
(36)
This also implies that sufficient explanation of size k' does not exist if and only if:
m²
(m² k') max fi(z;) > m + m² k' E
(37)
e|0,1 fi(z,)
We additionally note that c f((x;) S m m, since at most m clauses can be satisfied. Therefore, it follows that:
(38)
e|o.] fi(z.)
Moreover, by applying Equation 37 to any subset that not sufficient explanation of size k', we obtain that:
m
m e(01] (zz)
m² k' >
m² k' 2 m +1
(39)
Putting everything together, we have established that there no sufficient explanation of size k'' and only if m² - k 2 m + Now, assume that an explanation S of size k is cardinally-minime This implies that S satisfies Equation 36 and moreover, every explanation of size k 1 fails to be sufficient. Hence, Equation 37 holds when we set K' ;= k 1, yielding m²² (k 1) Z m +
which is equivalent to m² k 2 m. We therefore obtain the following conclusion:
m²
m²
max f((z)) E
< m - k
(40)
m (k- 1)
Moreover, the following relation follows directly from simple algebraic manipulation:
m²
m²
m² m² - k + 1 (m² - k) (m² - k) (m² - + 1) (m² - k)) (m² 1 ++1)
m²
(41)
m² m²
(k 1)
Hence, we obtain that:
m²
1722
m²
2 (k- 1) < max fi(zi) < E[
m² (k: 1) +
(42)
(m2 - k:) (m² - 1: +
Since we know that m2 k 2 m, it immediately follows that m² - k + > m. Altogether, we obtain:
m 2
m²
max f((z;) < m² - (k: - 1) x.E
+1
(43)
m² - (k 1)
Overall, under our construction we obtain that e|o,, fz(),) is always confined to an interval whose width is strictly less than 1. From Lemma 9 we already know that ea.,, fi (z;) equals the MaxSAT value of á minus r (the amount subtracted during the normalization step). Since the MaxSAT optimum is an integer, it follows directly that m0.1 f((z,) + r is an integer as well.
Moreover, the interval m==(K-T3 +T, m (k-1) + + 1] must contain exactly one integer because it
m²²
m²
contains max, 1) f((z, and its length is strictly less than 1. Consequently, given the encoding of 6 into the NAM instance and into the MSE-NAM problem, we can construct a simple polynomial-
time function that, from the value of k computes the unique integer in this interval recovering the optimal number of satisfiable clauses of ø.
32

---

Published as a conference paper at ICLR 2026
D ON THEORY AND PRACTICE OF IMPORTANCE SORTING
D.1 THE THEORETICAL WORST CASE BEHAVIOR OF THE PARAMETER &
We recall the previous Proposition number of steps equal to:
where we have shown that our algorithm performs a total
B, 2 I
04
E
kg S O log
B -1=-))1
(44)
A natural question is what happens when ε approaches O, when the interval - becomes very large. In the following, we show that in such cases, our algorithm is still guaranteed to terminate after linear number of queries in the size of the representation of the model given that each weight Wi and bias b,j in every univariate model is encoded as rational number Pi.1 with q.... E N, given in binary.
91,5
Proposition 5. Let f be a NAM with ReLU activations. Then, the process of running Alg. 2 followed by Alg. Bor Alg. terminatte after at most a linear number of queries to neural network verifier, with respect to the size of the model f's encoding.
Proof. We show this proposition in three stages: (i) Firstly, we demonstrate that for each i E [n]]. the bit-length of the minimal value of the e' i'th univariate function, namely minze B. (xx) (z:)) where B, (x,) the c-ball around x;, finite and is bounded by the encoding size of fi. (ii) Secondly, we show that the bit lengths of the verification bound parameters o;, 33 are also bounded by the encoding size of Ji. (iii) Finally, we use this claim to show that Alg. 2 terminates after at most a linear number of queries to a neural network verifier with respect to the model size encoding, from which it is straightforward to establish that running this algorithm, followed by either Alg. 3 or Alg. 4 also must terminate after most linear number of queries. We start off with the first part of the claim:
Lemma 11. Consider a univariate ReLU neural network component St: R- RR an imput X E Q and a radius E Q. Define the e-ball around x; as B, (xx) == {z, E R: x; - 2, S X4 E} for all i E [n]. Then, (i) is finite, with a bit length that is bounded by the encoding size of fr-
Proof. We prove this claim for some general univariate model ft. However for ease of presentation, we will define copy "g" of Si, i.e., 9: R + IR such that g == Ji to avoid repetitive usage of the subscript i. We will particularly prove that min (z(2 is finite with bit length that is bounded by the encoding size of g. We use the 0 subscript in z0 to denote the fact that it's the "O" input layer in the ReLU model (i.e., the input layer).
As our NAM has ReLU activations, the minimal value, i.c., the value for which min (,, (g) (g() is obtained, is the solution to some linear program whose constraints are directly determined by the model's weights and biases. This observation is standard cornerstone of neural-network verifica- tion. For completness, we provide a more explicit formalization here. As shown by (Sälzer & Lange, 2021), once the activation pattern (active/inactive state) of every ReLU constraint is "guessed", the verification query reduces to a linear program with the model parameters defining its constraints. is therefore the minimal value of an LP problem induced by
The minimal value (x) a "guess" of the activation patterns.
More particularly, given that we "guess" all activations ay,* {0, 1} for each ReLU constraint that is the j'th variable of layer k, then can define the following LP: minimizing 9(29), subject to the input specifications: x E < 20 < x + E, the linear specifications that are specified by h #-1 bt, for all l where K E N denotes the number of layers in g, and the ReLU specifications that are given by setting z hay and haj 2 0 if ajjx = 1, or z!z = 0 and haj S 0 if aj. 0, where z denotes the output variables in layer k. The output g(2º) that is minimized within the linear program is simply the value of the variable z" (the value of the last output layer).
It is well known that any solution of linear program admits finite precision (Vera 1998 Dadush et al. 2020). where a naive upper bound on the percision of the solution is O(n L) where n are the number of variables and I. is the maximum bit-length of any input coefficient. Hence, similarly,
33

---

Published as a conference paper at ICLR 2026
in the LP that we have described, if m, denotes the overall number of weights and biases in and let d denote the maximal bit length of any parameter in the model (i.e., weights/biases), meaning 2d itself denotes the magnitude of this encoding, then the maximal value in turn can be encoded using O( d) bits, which is linear in the encoding size of fi.
It follows immediately that the optimal value of this linear program namely, the minimum attained within a fixed linear region - is finite and bounded by the numeric precision of the program's 's parameters. Furthermore, since ming"e B, (w)) (g())) is realized as the minimum over one of these linear regions determined by at least one activation pattern Oj,k, the same bound on bit-length applies to e (x) (g(= as well.
By Lemma 11 it follows that & (as defined in equation 2). which represents the smallest gap between two minimal univariate values over continuous domain, also admits finite precision. In particular, its bit-length bounded by max.e(1.....n) (m, log(d)) We can now proceed to the remaining part of the proof:
Lemma 12. Given that the weights, the biases, and the inpul interval of an univariate model fi have maximal bit length of at most di the output interval's bounds as and B, are finite and their bit length is bounded by m di where my is the number of parameters in ft.
Proof. The parameters 3, and a; can be obtained using wide range of cound-propagationn tech- niques developed in neural network verification. Even under "naïve" approach such as Interval Bound Propagation (IBP) (Zhang et al., 2020; Gowal et al. 2018) - which propagates bounds layer by layer by computing an outer approximation each step and exploiting the monotonicity of ReLU activations - the resulting bounds still have a (very loose) worst-case linear bit-length in the model size.
Formally, for each k E [ks], where k is the number of layers of the univariate model, the values of the propagated interval in the k'th layer, denoted a Sh, can be computed from the interval of the (I: 1)'th layer, k-1 ,186-1 using the weights and biases of the k'th layer via interval arithmetic:
a =
min at S
(ReLU(W* + +b)),
g
max Ige59k
(ReLU(W*> x+ +*)).
where a" 2; and g0 increase the bit-length. A multiplication can increase the bit-length by at most d,, and an addition increase it by most 1. Thus, calculating 8 + 1 in layer k which consists of element- wise multiplications of a أ-1 g.- with numbers of maximal bit-length d,, followed by summation and adding the bias- increases the bit-length by at most d; (from multiplications) and by at most my in total (from additions across all layers). As a result, the bit-length of a* 8h can be at most dy + lg larger than that of * 1--_, where Eg is the number of parameters in the k' layer.
- e. Since ReLU(x) max(0, x),, the activation does not
Let L denote the number of layers in f.. We can then bound the bit-length of the output interval values:
d: L+
Σ 4 S d, m, +
Σ l S d. m, + m m,(d; + 1). AE[M]
kE[N]
Overall, the propagated input bounds have bit-length at most Om, d.).
Now, using Lemma IT and Lemma 12 we can conclude the proof for Prop. 5 Particularly, in every iteration of the loop in Alg. 2 Line 5 halves the bounds of the verification problem and thereby decrease by the bit length the approximated minimal values. Line 12 then checks, for every pair of univariate networks fi, fj (i, E [n]), whether either the lower bound of fa is greater than or equal to the upper bound of fj- or vice versa. By Lemma TT the minimal values fr and Jj have bit length bounds of m4 m, d bits, respectively. Moreover, from Lemma 12 the bit lengths of a,,,; 3r are bounded from above by m, (d 1).
Consequently, the terms 3: a; and & can both be represented using at most O (m d) bits. thus, binary search over this quantity will require no more than O (m an-d d) steps. Specifically, after a linear number of steps in d, the condition in Line 12 must be satisfied: for every pair of i, [n], either the lower bound of f. will match the upper bound of fy. or the lower bound of fy will match the upper bound of fa including the case where the true minimal values are equal.
34

---

Published as a conference paper at ICLR 2026
Put differently, execute parallel threads, and after at most linear number of iterations in the encoding size of the largest univariate function (itself linear the total function size), Prop. 5 ensures termination. Furthermore, since Alg. Sl and Alg. I respectively run in linear logarithmie time in n (which is likewise linear in the model encoding size), it follows that the overall procedure terminates after most linear number of queries in the model encoding size.
We note that since this bound is linear in the model encoding size, it represents substantial im- provement over the exponential worst-case complexity observed in general neural networks (Barceló al. 2020b).
Relation to verifier and machine precision. In practice, it is highly unlikely to reach this worst- case bound on precision (see Appendix F.55 empirical evidence). Hypotheticallly, even the verifier or machine precision will dominate this parameter. Moreover, our experiments show that the values of & trained NAMs are in fact rarely exactly on the decision boundary. Consequently, in our em- pirical evaluations, the effective precision parameter governing the runtime is Ê.. As demonstrated in our experiments - where we efficiently compute cardinally minimal explanations for commonly used NAMs and in the ablation study of this parameter in Appendix F.5 this yields a substantial improvement overall runtime.
D.2 PRACTICAL. OPTIMIZATIONS FOR IMPORTANCE SORTING
While analyzing the behavior of Alg. 2 in practice we noticed that the algorithm makes unnecessar- ily many verifier calls in certain edge cases. We briefly mention these here, along with our (sound) optimizations based on heuristics. As in Sec. 4.1 we consider the case where f(x) = 1. which requires us find bounds [4, uz] for the exact minimum value fx(x;) for each feature i [n]. The case (xx 1 follows symmetrically. The two edge cases we consider deal with cases where the exact minimum value is (close to) either of the bounds:
Lower bound close to exact minimum. Please note that as we iteratively refine the bounds using neural network verification calls, the verifier sometimes gives a counterexample x' along with the verification result. We can use min(fi(x)) m) as new upper bound for the minimum u; (Alg. 2 line 9). We observed that, in practice, this speeds up the sorting process, particularly as the verifier often returns counterexample z' that is close or the exact minimum. This works well in practice for the case [0, u,] on NAMs with ReLU activations, as x just has to hit the same piece-wise through fi-
linear region containing xf, which gets mapped
Upper bound close to exact minimum. It also sometimes occurs that the upper bound u; is already (close to) the exact upper bound. Thus, instead of iteratively running verification queries until 7, converges to u, it helps to directly test if tq ô can still be reached for some small ó E R.. A good heuristic to switch this test is if the verifier concludes that f(x;) E [m,, u:] but unable to return a counterexample demonstrating this (as the verifier has to hit u; more or less exactly given it's close proximity f(x))) ))
These two optimizations often reduce the number of verifier calls described in Prop. 2 to very few verifier calls. practice, we have seen that often only 3 verifier calls per feature are required to determine the total ordering.
E EXTENSIONS TO ADDITIONAL SETTINGS
E. EXTENSION TO MULTI-CLASS CLASSIFICATION
For multi-class classification, let us assume the winner class f(x) arg max fx( (Sec. 2.3). Then, we can distinguish between two cases: (i) winner-vs.-ed -all explanations, and (ii) all pair-wise winner-vs--one explanations, where each case can be reduced to a binary classification task, where the new binary network in (i) given by f(x) = fc(x) maxfş4 fy (x), and for (ii) by (x) = fx) - (x), j E [n], with the class corresponding to the original winner class t. Then, can apply Alg. and Alg. to generate the respective explanations.
35

---

Published as a conference paper at ICLR 2026
E.2 EXTENSION REGRESSION
Let us assume we want to find the subset S that is sufficient to determine that the prediction will always be larger than some deviation R+ to the original output (the same result for finding the same guarantee for a prediction which is smaller will be symmetricly opposite). The first part of the algorithm will be identical the case of binary classification with a positive outcome (the other use-case will align with negative outcome).
Algorithm Regression: Parallel Interval Importance Sorting
Input: NAM f, input E R", perturbation radius Cp IR+
for each feature [n] parallel do
2: Extract initial bounds ag 3g for f((X,) such that & E By (x.)
3: 4 Cg U; f 3
4: while True do
5:
m, < 4tt.
6:
verify( VX, E B7 (xi), f((x)) 2 m, then
7:
4 + mi
8:
else
9:
W4 mi
10:
end if
A4; < (x:) -4 Au; fi(x:) ui
12:
if for all + it holds that: Aue 2 Al or Aug 2 Al, then
Break
14: end if
end while
16:
end for
17:
return arg 1 .... (Aln, Au,))) in ascending order
Now we move on to the second part of the algorithm for the regression case:
Algorithm Regression: Greedy Cardinally-Minimi Linear Explanation Search
Input: NAM f. input x E R", perturbation radius sp E I44, output deviation 6 E I4
1: S [[]]
2: for each feature i E [n]. ordered by Alg. do
b Suff(f, x, S, 6, ep) holds
3: if suff(f, S {i), 6, Ep) then
4:
S+S
5: end if
6: end for
7: return
S is cardinally-minimad explanation concerning (S, x, 6, (p)
which is the same algorithm we used for binary classification (Alg. 3). but where now the evaluation of suff' evaluates to checking whether fixing the feature subset S ensures that the output remains larger than the original input by less than 8. Given this result, this can be extended to our logarithmic version (Alg. 4 as well:
F EXPERIMENTAL DETAILS AND ABLATION STUDIES
F.I DATASET EXPERIMENTAL DETAILS
Datasets. We evaluate our approach four widely used benchmark datasets (Agarwal et al.) 2021 Radenovic et al. 2022). covering both classification and regression tasks. The Breast-Cancer dataset contains 569 samples with 30 numeric features per sample. to classify tumors as malignant or benign. The CREDIT dataset includes 1, 000 samples with 20 attributes each, for assessing loan repayment probability. The FICO HELOC dataset comprises 10, 459 samples with 23 financial and demographic features, for predicting creditworthiness. These datasets collectively allow us evaluate the performance and robustness of method across different problem types, input
36

---

Published as a conference paper at ICLR 2026
Algorithm 8 Regression: Greedy Cardinally-Minimaa Logarithmic Explanation Search
Input: NAM f, input X E R", perturbation radius Ep 1R., output deviation ò IR+
1: total order of features (Alg. 6
2:
1 {
<-
3: while 1 u do
4:
f- -
5: if suff( ff. x, {F[1).... F[m]] 6, (p) then
6:
1 +
7: else
8:
u m
9: end if
end while
11: S S [F[I]..... F(m]}
return
S is cardinally-miniimde explanation concerning (S. x, 6, 6p)
Table 3: Varying perturbation radius on all datasets.
Breast Cancer
CREDIT
FICO HELOC
Size (4)
Time [s] (1)
Size (
Time [s] (4)
Size (4)
Time [s] (L)
0.01
4.00:14.24
35.6011.34
0.1
4.45+33.98
115.08+73.48
1.79++1007
86.76+:88.21
2.77+1.62
131.31-141.9
0.2
6.29+3.50
143.81+121.27
2.80+22.07
97.16+34.45
3.88
136.82+77.99
0.5
9.7612.77
146.01164.76
3.76:1.62
132.67436.76
5.5911.80
317.92+:22.07
dimensions, and domain characteristics. Models. We trained 3 binary classification NAMs on the first three datasets, and a regression NAM on the last model. We follow the standard architectures in (Agarwal et al. 2021 Radenovic et al., 2022), and train for each feature network with hidden layers of size (64, 64, 32). The accuracy of the models for Breast Cancer, CREDIT, and FICO HELOC are 97.37%, 94.92%, and 69.02%, respectively.
Evaluation. All presented results are averaged over 50 samples with a time out 600s, perturba- tions
the --o-m the normalized input and perturbation radius 0.5 used if not stated otherwise. We filtered trivial samples where, e.g-, all features are returned as an expla- nation. For the Breast Cancer dataset, we use e 0.01 for interesting comparison to the local strategies. Our experiments are running on Ubuntu 24.04 machine with 64GB RAM and 13th Gen Intel(R) Core(TM) 17-1365U. The CREDIT experiments are run on Ubuntu 24.04 machine with a Intel(R) Xeon(R) Platinum 8380 CPU @ 2.30GHz and two NVIDIA A100-PCIE with 40GB. If otherwise specified, all experiments were limited to 32 CPU threads. In figures, we show the median along with a shaded region depicting the 75% quantiles.
F.2 ABLATING THE PERTURBATION RADIUS
In formal XAI, the generated explanations heavily depend on the chosen perturbation radius e. In Tab. 3 we show how the size and generation time of the explanation change with varying Gener- ally, the explanation size and the generation time increase with e, which is expected as previously ob- tained minimal explanations indeed become insufficient and the verification queries become harder to solve as is increased. Please note that for 0.01, insufficiently many samples for proper averages were found where the explanation is non-trivial on CREDIT and FICO.
F.3 NUMBER OF PROCESSED FEATURES OVER TIME
In this experiment, we demonstrate how our approach - after the initial sorting phase - pro- cesses the features much quicker to obtain cardinally-minime explanation, it only requires logarithmic number of verification queries to do so. This even outperforms approaches that obtain subset-minimal approaches, including the time needed sort the features (Fig. 5).
37

---

Published as a conference paper at ICLR 2026
(a) Breast Cancer
(b) CREDIT
(c) FICO HELOC
#Processed features [%
1
0.8
0.8
0.8
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0
0
0
200
400
600
800
200
400
600
800
0
200
400
600
800
Time [s]
Time [s]
Time
[s]
Ours
Naive
Sensitivity
Figure Number of processed features over time.
CREDIT
30
1
Explanation size
=
2
8
20
32
10
0
50
100
150
200
250
300
Time [s]
Figure A comparison of explanation generation with different number of processors
F.4 UNDERSTANDING THE PARALLELIZATION ABLATING THE NUMBER OF PROCESSORS
A key factor influencing the runtime of our approach particularly the sorting of univariate com- ponent importances in Alg. iss the number of processors allocated for parallelizing the logarithmic binary search. To assess this effect, conducted an ablation study with varying processor counts.
Fig. 6 illustrates the impact of parallelization on both explanation size and computation time. In particular, the time to sort the features according to their importance (Alg. ( can be reduced as the number processors p increases, as the bound refinement can be parallelized. In contrast, the subsequent explanation generation (Alg. 4 is barely impacted by the number of processors p. Im- portantly, even with only a single processor (i.e., no parallelization), our algorithm still computes cardinal-minimal explanations harder task than subset-minimal ones thus improving expla- nation size and computation time by design (compare to Fig, 3
F.5 ABLATION STUDY ON NEAR IDENTICAL FEATURES
Our approach relies on an efficient importance sorting of the features (Sec. 4.1 This subsection provides further insights into the required precision to effectively sort them (Prop. 2
We first show the frequency of each required precision in our datasets in Fig. The impact of these precisions on the sorting time is visualized in Fig. 8 These results show that required precision not arbitrarily small (smallest around 10 $), and the sorting time is also influenced by other factors, such as the verifier, in practice. This implies that, in practice, sorting based on the parameter & is highly effective, which aligns with, and helps explain, the strong empirical performance observe when computing cardinally minimal explanations for NAMs.
To isolate the effect, created ablation study using synthetic neural network with near identical feature networks f.. i E [2], where only the bias in the last layer of f2 is shifted slightly. Thus, a large bias shift corresponds overlap between the computed bounds, and small bias shift
38

---

Published as a conference paper at ICLR 2026
(a) Breast Cancer
(b) CREDIT
(c) FICO HELOC
0.15
0.3
0.1
Frequency
0.1
0.2
0.05
0.05
0.1
5
6
4
2
10
log ( (min)g(((((s)))
log (E))
log (minig(m)(E.))
Figure Frequencies of the required precision to sort the features according to their importance.
(a) Breast Cancer
(h) CREDIT
(c) FICO HELOC
00
T0
Sorting time [s]
400
150
400
200
100
200
oc8
90
50
0
8
7
-5
-6
-4
10
5
0
log [minge (n) (E:))
log ( (minke())) (E+))
log (minkg (5.))
Figure 8: Impact of the required precision on the sorting time.
results in nearly identical bounds. We use the same network architecture as the ones trained on the real data sets, and do not apply any optimizations discussed in JppendixDD.2jin this study. We record the sorting time for different bias values starting from (no overlap even for initial bounds) down to 10-7 (almost entirely overlapping) in Tab, 4 We observe that the sorting time only increases linearly with the order of magnitude of bias shift (corresponding to {,) due the binary search, confirming result in Prop.
G DISCLOSURE: USE OF LARGE LANGUAGE MODELS (LLMs)
A large language model (LLM) engaged solely writing aid to polish language and enhance expression. played no role generating research idcas, designing the study, conducting the analysis, interpreting results. These aspects performed entirely by the authors.
Table 4: Influence of near identical features on the sorting time on synthetic example.
Bias Shift
Sorting Time [s]
0.08
0.1
7.58
0.01
12.71
0.001
16.24
0.0001
20.95
0.00001
28.37
0.000001
31.54
0.0000001
36.57
39


Reviews:
[{"review_id": "EWw1viy5FE", "reviewer": "Reviewer_Bqyn", "summary": "A computationally-efficient, novel method to compute explanations with provable guarantees for Neural Additive Models (NAMs). The explanations are guaranteed to be the smallest in size, globally. The method claims to be efficient in generating such certified explanations.", "questions": "- Does the method support discrete input features (I suppose so, could you confirm)?\n- What is the impact of perturbation radius $\\epsilon_p$? \n- Has the local subset minimality been introduced in the narrative exclusively to ensure a feasible experimental campaign while comparing against naive baselines?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Certifying explanations is a key open research direction: the research problem highlighted by the authors is well-defined and relevant to the ML community. To the best of my knowledge this is the first approach specifically designed for NAMs \n- Logarithmic number of verification queries required is a step forward compared to baselines. Formal complexity analysis included.\n- Convincing experimental campaign, aligned with best-practice in the community. Performance of the approach shows interesting increase over baselines, both in size reduction and time required to generate an explanation (which is a welcome contribution).\n- Paper is clear and the authors train of thought is well articulated.", "weaknesses": "- Limited impact, as the proposed method is applicable to NAMs only by design.\n- Although evaluation is convincing, the adopted proxy quality metric for explanations is size, where smaller = better. A human assessment of the perceived quality of the resulting explanations would have made the work stronger - although I acknowledge this is a significant addition to the work (i.e. yes, consensus in the literature is the smaller the better, but what if the resulting explanations are *too* small, and therefore too course grained to capture a use case subtleties?)\n- The paper could use a running example across the paper section, to further clarify some of the key concepts (e.g. globally and locally cardinal-minimal feature subset). The HELOC example in Figure 1 is popular enough to be a good candidate.", "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": "jO4h06yElo", "reviewer": "Reviewer_f9gy", "summary": "This paper focuses on explainable artificial intelligence and aims to provide concise explanations for the predictions made by Neural Additive Models (NAMs). The primary issue addressed in this study is as follows: given a classifier $ f $ represented by a NAM, an input data instance $ x $ that requires an explanation, and a ball $ B $ centered at $ x $, the goal is to identify a feature subset $ S $ of the minimum size. This subset must ensure that for every instance $ z $ within the ball $ B $, if the values of $ z $ and $ x $, restricted to the features in $ S $, are indistinguishable, then the classifications made by $ f $ for both $ z $ and $ x $ are the same. Such an explanation $ S $ is referred to as a (ball-restricted) minimum-size abductive explanation or a minimum-size sufficient reason.\n\nTo address this problem, the authors propose a two-stage method. In the first stage, the univariate functions $ f_i $ are sorted based on their importance intervals. In the second stage, a minimal-size explanation $ S $ is derived using a greedy approach. The paper includes formal proofs for the correctness and complexity of this method, and it presents comparative experiments conducted on four different datasets that support the theoretical findings.", "questions": "The following comments and questions are related to the aforementioned weaknesses.\n\n**C1.** What is the computational complexity of finding minimum-size sufficient reasons for the class of NAMs? Is this problem in NP? In other words, does the decision version of the problem have a polynomial-time certificate? Additionally, is the problem NP-hard, or is it even more difficult?\n\n**C2.** As mentioned earlier, Barcelo et al. (2020) have demonstrated that the problem known as \"Minimum Sufficient Reason\" (MSR) is in P for the class of linear threshold functions (LTs). Essentially, MSR is the decision version of the problem being explored in this study, where the class of LTs is replaced by the class of NAMs, and the instance space is defined as a ball centered at $x$. For the class of LTs, Barcelo et al. advocate a strategy that involves sorting each feature $x_i$ based on its importance, which is measured by the weight $w_i$ and the class $f(x)$. The next step is to determine whether the top $k$ features in this ordered list provide a sufficient explanation for $x$ and $f$.\n\nIf I’m not mistaken, this study adopts a similar strategy, with the primary challenge being the computation of the minimum value of each univariate function $f_i$ over a specified ball centered at $x$. Therefore, it is important to discuss the overall approach in comparison to Barcelo et al.’s strategy, as well as to elaborate on the concept of using \"non-intersecting intervals\" to approximate feature importances.\n\n**C3.** As mentioned earlier, the primary innovation of this study is to compute an ordering of “non-intersecting” intervals, from which the final explanation is derived. From this perspective, it is essential to demonstrate that the main algorithm (Alg. 2) is correct. Assume without loss of generality that $f(x) = 1$ with $x = (1,1)$ and consider two univariate functions, $f_1$ and $f_2$, where the minimum of $f_1$ (over the ball centered at $x$) is slightly below the minimum of $f_2$.  Does the algorithm guarantee that, at the end of the final iteration, the output intervals $(l_1, u_1)$ and $(l_2, u_2)$ satisfy the property $u_1 < l_2$ (indicating that $x_1$ precedes $x_2$ in the final ordering)? Additionally, how many iterations of the main loop are required to derive such intervals?\n\nRegarding the last question, the complexity analysis appears to be flawed. Again, consider the two univariate functions $f_1$ and $f_2$. Here, assume that $f_1(z) = f_2(z) = w$, where $w$ is a constant scalar. According to Line 12 of Algorithm 2, the algorithm terminates when $\\Delta u_1 \\geq \\Delta l_2$. However, if $\\Delta u_1 = \\Delta l_2$, we find that $\\xi_1 = 0$. This situation suggests that the runtime complexity might be infinite. Therefore, I am unconvinced that $\\xi$ is the appropriate parameter for the complexity analysis of the algorithm, particularly when the global minima of different univariate functions are identical.\n\n**C4.** The paper currently has several clarity issues that make it difficult to follow. For instance, the $i$th entry of a vector $\\mathbf{x}$ is sometimes denoted as $\\mathbf x_{(i)}$ (as defined in Line 93) and at other times as $x_{(i)}$ (in Section 4.1). Additionally, the explanation is occasionally referred to as $\\mathcal{S}$ (in the main paper) and other times as $S$ (in Lemmas 2 and 3). Furthermore, the center of Figure 1 appears to be misplaced, and there are missing references (indicated by symbol ??) in the Appendix.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "**S1.** The problem of computing minimum-size sufficient reasons is $\\Sigma_p^2$-hard for neural networks (Barcelo et al., 2020). Therefore, it is reasonable to explore simpler model classes that can lead to efficient algorithms with a reasonable number of calls to an NP oracle. In this context, Neural Additive Models are a rational choice.\n\n**S2.** Experimental results across four datasets demonstrate that concise explanations can be generated in a reasonable amount of time.", "weaknesses": "**W1.** The computational complexity of finding minimum-size sufficient reasons for the class of NAMs has not been proven. Identifying the corresponding complexity class (P, NP, $\\Sigma_p^2$) is crucial for justifying the overall interest in this approach.\n\n**W2.** Barcelo et al. (2020) have already demonstrated that the problem is solvable in polynomial time for linear threshold functions. Essentially, the theoretical results presented in this study are just an extension of their previous work, with the primary innovation being the computation of an ordering of non-intersecting intervals. I am not entirely convinced that this alone is sufficient for publication in ICRL.\n\n**W3.** The correctness and runtime complexity of the main algorithm used to compute a total ordering of non-intersecting intervals (Alg. 2) appear to be flawed. In particular, the runtime complexity tends toward infinity as the value of $\\xi$ approaches zero.\n\n**W4.** The clarity of the paper could be improved. Currently, there are several issues related to notation. Additionally, the organization of the paper could benefit from the inclusion of some proofs (or at least sketches of proofs) for the most significant results.", "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": "vX0lZAngLb", "reviewer": "Reviewer_mvRn", "summary": "This paper presents a novel algorithm for computing provably cardinality-minimal explanations for Neural Additive Models (NAMs). The authors focus on post-hoc, per-instance explanations: given a trained NAM f and an input x, they seek to compute a subset of features S \\subseteq [n]that is sufficient to guarantee the same prediction under bounded perturbations of the remaining features (an\n\\epsilon-ball). Among all sufficient subsets, the goal is to find one of minimum cardinality (the global optimum).\n\nThe paper provides a novel contribution to the state-of-the-art in the broad area of explainability with provable guarantees (in this case, minimality). The paper focuses on NAMs, which to the best of my knowledge it is still a Still a niche but growing area in the interpretability subfield. They are Not widely used in industry production pipelines yet. but research interest persists. In fact,  (NAMs) occupy an interesting middle ground in machine learning — they’re not mainstream, but they are important in specific contexts where interpretability and nonlinear modelling both matter. Their main limitation is that in a pure NAM, features don’t interact directly because the model assumes additivity. This means that the effect of each feature x_i on the output y is independent of any other feature x_j, which can be a strong limitation in some practical settings.\n\nThe proposed algorithm proceeds in two stages. In the first stage each univariate subnetwork f_i(x_i) is verified independently to estimate its influence on the model’s decision. This is done via parallelised binary search over feature importance intervals. In Stage 2, after sorting features by importance, a binary search identifies the globally cardinal-minimal sufficient subset of features that provably determines the model’s prediction. This reduces complexity from exponentially many calls to the network to logarithmically many.\n\nExperiments on standard tabular benchmarks demonstrate feasibility and show smaller, faster provable explanations than prior methods; sampling-based visualisations were also shown to be unreliable in some cases, whereas the proposed method always produces verifiably sufficient explanations.\n\nOverall, I am supportive of this paper. It makes a meaningful and well-justified contribution to formal explainability by showing that NAMs enable efficient computation of globally minimal sufficient explanations -- something previously infeasible for general neural networks. With minor revisions, I feel that this paper is a valuable contribution to the state of the art.", "questions": "Suggestions.\n\n(1) Expand on practical verifier settings, in particular timeout and floating/rounding issues.\n\n(2) Add an ablation that shows performance as a function of the separation parameter or a synthetic example with near-identical features.\n\n(3) Cite and comment on the work by El Harzli et al. at IJCAI-2023.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Strengths.\n\n(1) Addresses an important formal-XAI problem (provable minimal explanations) and achieves a stronger guarantee (global cardinality minimality) than most prior work for neural networks.\n\n(2) Elegant exploitation of the additive NAM structure to reduce verification complexity.\n\n(3) Clear algorithmic presentation with theoretical propositions and proofs in the appendix.\n\n(4) Empirical results convincingly illustrate both efficiency and the need for provable guarantees.", "weaknesses": "Limitations / concerns.\n\n(1) The guarantees rely on an exact, sound verifier and on refining intervals until importance bounds separate. In practice, verifier soundness, numerical issues, or timeouts can undermine the provable guarantees; the authors acknowledge this but more discussion of practical mitigations (timeouts, numerical tolerances) would be useful.\n\n(2) The attractive complexity (logarithmic verifier calls) is obtained assuming parallel refinement across features. The number of wall-clock verifier calls depends on available parallelism; the paper states the complexity in terms of ρ processors. If you cannot parallelise, wall-clock time will be higher (though still fewer full-model queries than naive approaches). \n\n(3) The method requires refining per-feature bounds until features’ importance intervals separate (so a total order exists). If two features have extremely close effects, the required precision may be tiny, increasing verification cost. The complexity bound explicitly depends on that precision factor. The propositions report complexity in terms of that separation quantity.\n\n(4) The related work is largely comprehensive, but the paper omits a relevant reference on computing cardinality-minimal explanations for a different class of networks (monotonic fully-connected networks). That work should be cited and briefly contrasted. While that setting differs from NAMs (monotonic FCNs vs. additive univariate subnetworks), the goals and guarantees are similar; I recommend citing and briefly contrasting that work to highlight how different architectural restrictions enable tractable exact explanations.\n \n@inproceedings{DBLP:conf/ijcai/HarzliG023,\n  author       = {Ouns El Harzli and Bernardo Cuenca Grau and Ian Horrocks},\n  title        = {Cardinality-Minimal Explanations for Monotonic Neural Networks},\n  booktitle    = {Proceedings of the Thirty-Second International Joint Conference on\n                  Artificial Intelligence (IJCAI) 2023},\n  pages        = {3677--3685},\n  publisher    = {ijcai.org},\n  year         = {2023},\n  doi          = {10.24963/IJCAI.2023/409}\n}", "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": "MthqrzzFcv", "reviewer": "Reviewer_uiyA", "summary": "This paper proposes a new algorithm to extract cardinal-minimal sufficient explanations for Neural Additive Models (NAMs).\nIt does so by exploiting key design choices of NAMs, showing how this family of models supports explanations with guarantees.\n\nThis is achieved as follows. First, the paper introduces a method to rank features based on how much they influence the final prediction. Then, after this ranking is obtained, an algorithm is discussed to exploit this order to efficiently explore which features to remove from the current sufficient explanation until a cardinal-minimal explanation is obtained.", "questions": "**Q1:** In line 2 of Alg. 2, how is the operation $\\\\in$ implemented? Is this a uniform random sampling?\n\n**Q2:** How is the proposed algorithm applicable to NAMs for data types different from tabular data, like images and graphs ?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Making minimal sufficient explanations scaling is a timely and valuable research direction.\n\n- The proposed idea is simple but effective\n\n- The paper flows well\n\n- The paper is formal and precise in its claims", "weaknesses": "### Proof of Proposition 3 is unclear\n\n- **W1:** In line 842, the authors write *Let 1 ≤ l ≤ n represent the last feature added to $S$ in line ?? of Alg. 3*. However, I do not understand what this statement refers to, as in no part of Alg. 3 features are added to $S$.\n\n- **W2:** In line 843, the authors write *Then, for $S^{'}= S \\setminus \\\\{ l \\\\}$, it follows that: $suff(f, x, S, \\epsilon)$ does not hold true, implying that $S^{'}$ is not a sufficient explanation*, but it is unclear why this is true. I feel there could be some writing issues in this paragraph that prevent me from understanding the proof.\n\n\n\n### Definition of Sufficient explanation\n\n- **W3:** Definition 1 expresses the condition $\\\\forall \\\\tilde{x} \\\\in B_p^{\\\\epsilon_p}(x)$, where $B_p^{\\\\epsilon_p}(x) = \\\\{\\\\tilde{x} \\\\in R^{n} | ...\\\\}$. However, this condition seems to be impossible to satisfy, as real numbers are dense and therefore would require to run the sufficiency check for an infinite number of $\\\\tilde{x}$.\n\n\n- **W4:** The set of allowed perturbations is defined over an $\\\\epsilon$-ball around $x$. Nonetheless, defining a fixed $\\\\epsilon$ for every feature could hinder some feature-specific behaviors induced by, for example, different magnitudes of features. For example, let us consider a binary feature representing the gender of a person (0=male, 1=female), and a function $f_i(x_i)$ shaped as: $f_i(x_i)=100$ if $x_i < 0.5$, and  $f_i(x_i)=-100$ if $x_i >= 0.5$. Then a value of $\\\\epsilon=0.1$ will not be able to check for the sufficiency of the explanation when the gender of the person is switched from male to female, as this feature will be assigned zero importance even if its true impact is actually very high.\n\n\n### Figure 1 unclear\n\n- **W5:** Figure 1 is difficult to interpret, and its description is not self-contained. I suggest improving its description. For example, the part on *users might wrongly believe that only feature 1 yields negative outputs, while feature 2 can also flip the classification* is non-trivial to a non-expert reader.\n\n\n**Minors**\n\n- Propositions 2 and 3 are in reverse order in the Appendix.\n\n- The link between lines 46 and 47 is a bit unclear. In fact, while the first sentence in the paragraph is referred to sufficient explanations, the following sentence refers only to cardinal-minimal explanations, and not cardinal-minimal sufficient explanations, making the context of the sentence less clear.\n\n- In line 52, the authors write: *Consequently, existing methods focus on (locally) subsetminimal explanations which are typically suboptimal in size, potentially large, and thus less informative than their globally minimal counterparts*, which is, however, not clear why this is true without further context. I would recommend adding an explanation of why this is the case.\n\n\n- I personally find the wording local vs global sufficient explanation a bit misleading, as this could be confused with standard notions of local (instance-level) and global (model-level) explanations. I believe cardinal-minimal and subset-minimal are already discriminative enough and may not need further quantifications.", "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)