Additive Models Explained: A Computational Complexity Approach
Authors: Shahaf Bassan
Michal Moshkovitz
Guy Katz
Venue: NeurIPS 2025 poster ()
Keywords: explainability
computational complexity
XAI
explainable AI
interpretability
GAM
Generalized Additive Models
formal XAI
NAM
EBM
neural additive model
explainable boosting machine
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: A theoretical framework for analyzing the explainability capabilities of GAMs using computational complexity.

Abstract: Generalized Additive Models (GAMs) are commonly considered *interpretable* within the ML community, as their structure makes the relationship between inputs and outputs relatively understandable. Therefore, it may seem natural to hypothesize that obtaining meaningful explanations for GAMs could be performed efficiently and would not be computationally infeasible. In this work, we challenge this hypothesis by analyzing the *computational complexity* of generating different explanations for various forms of GAMs across multiple contexts. Our analysis reveals a surprisingly diverse landscape of both positive and negative complexity outcomes. Particularly, under standard complexity assumptions such as P$\neq$NP, we establish several key findings: (1) in stark contrast to many other common ML models, the complexity of generating explanations for GAMs is heavily influenced by the structure of the input space; (2) the complexity of explaining GAMs varies significantly with the types of component models used - but interestingly, these differences only emerge under specific input domain settings; (3) significant complexity distinctions appear for obtaining explanations in regression tasks versus classification tasks in GAMs; and (4) expressing complex models like neural networks additively (e.g., as neural additive models) can make them easier to explain, though interestingly, this benefit appears only for certain explanation methods and input domains. Collectively, these results shed light on the feasibility of computing diverse explanations for GAMs, offering a rigorous theoretical picture of the conditions under which such computations are possible or provably hard.

Additive Models Explained: A Computational Complexity Approach
Shahaf Bassan
Michal Moshkovitz Google Research mmi caaichall@ooo @google. com
The Hebrew University of Jerusalem shahaf. bassan@mail huji ac.
Guy Katz
The Hebrew University of Jerusalem g katz@mail huji. ac. il
Abstract
Generalized Additive Models (GAMs) commonly considered interpretable within the ML community, their structure makes the relationship between imputs and outputs relatively understandable. Therefore, it may seem natural hypothesize that obtaining meaningful explanations for GAMs could be performed efficiently and would not be computationally infeasible. In this work, we challenge this hypothesis by analyzing the computational complexity of generating different explanations for various forms of GAMs across multiple contexts. Our analysis reveals surprisingly diverse landscape of both positive and negative complexity outcomes. Particularly, under standard complexity assumptions such as PANP, we establish several key findings: (i) in stark contrast to many other common ML models, the complexity of generating explanations for GAMs is heavily influenced by the structure of the input space; (ii) the complexity of explaining GAMs varies significantly with the types of component models used - but interestingly. these differences only emerge under specific input domain settings; (iii) significant complexity distinctions appear for obtaining explanations in regression tasks versus classification tasks in GAMs; and (iv) expressing complex models like neural networks additively (e.g., as neural additive models) can make them easier to explain, though interestingly, this benefit appears only for certain explanation methods and input domains. Collectively, these results shed light on the feasibility of computing diverse explanations for GAMs, offering rigorous theoretical picture of the conditions under which such computations are possible or provably hard.
1 Introduction
Generalized additive models (GAMs) are a widely utilized family of models in ML 51 88 valued commonly for their interpretability 88 37 IB3 additive structure. Beyond being considered interpretable, the very assumption of "additive inter- pretability" is foundational one in the explainable Al community. For instance, many explanation techniques are designed to approximate additive behaviors (94), and metrics such as infidelity [12 assess explanation quality by measuring how well an additive approximation captures the effects of feature perturbations on the model's 's output. Furthermore, interpretable training approaches often seek to promote near-additive behavior in models within specific domains
25
38
74
29
48 40 84 87 47 114 due their
Since GAMs are commonly regarded as an interpretable class of ML models, may seem natural to expect that different types of explanations for their predictions can be computed efficiently, without encountering drastic computational intractability (e.g., hardnesss #P-hardness etc.). This
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

question also relates to growing body of research in the ML community focused on understanding the computational complexity involved in generating different types of explanations for various model
classes [16 104 18 These efforts span both inherently complex models like neural networks []] and
tree ensembles 12 where explanations are expected to be computationally hard to compute [66
as well as traditionally "interpretable" models such as decision trees 9 and monotonic classifiers [7
where computing explanations is expected to be more efficient [16 80 [8]
Our contributions. In this work, we investigate the computational complexity of generating various types of explanations for different classes of GAMs across range of contexts. We also question the assumption that such explanations are inherently efficient to compute, given the perceived interpretability of GAMs. Through a comprehensive analysis spanning a wide array of settings, we uncover a surprisingly diverse landscape - revealing both tractable (efficient) and intractable (hard) cases. Our findings reveal that the complexity of generating explanations is heavily influenced by several factors- including some unexpected ones that were not known to impact complexity in previously studied ML models.
Our analysis is structured around the following three dimensions:
1. Component model type used within the GAM: Here, we investigate several popular component models that are typically used in GAMs and span the interpretability spectrum, including: (i) Smooth GAMs - i.e., the classical use of splines [51]: (ii) Neural Additive Models (NAMs)
where each component is neural network; and (iii) Explainable Boosting Machines (FBMs) (37 which use boosted tree ensembles as their components.
2. Type of explanation considered: We study the complexity of generating a diverse set common feature selection task that considers selecting the minimal subset of features that satisfy the common sufficiency criterion (as well as two additional relaxations of this task); (ii) Minimum contrastive explanations - minimal changes to the input that would alter the prediction; (iii) Shapley value attributions assigning importance scores to features; and (iv) Feature redundancy identification - detecting redundant feature contributions.
of explanation types, including: (i) Minimum sufficient reasons
3. Input domain setting: We study three general types of input domains: (i) Enumerable discrete domain where each input variable takes values from constant set; (ii) Gen- eral discrete domain - where input values are discrete but not necessarily enumerable; (iii) Continuous domain where inputs take
features.
We prove complexity results for generating explanations across all configurations of these dimensions i... across every combination of component type x explanation type x input domain (see Table [ for a summary of the results). This uncovers diverse range of results including (i) efficient polynomial-time algorithms, (ii) intractability results (NP-hard, #P-hard, etc.), and (ii) pseudo- polynomial time results cases where the problem is generally intractable but becomes efficiently solvable when the GAM's weight coefficients are encoded in unary rather than binary. Intuitively, tractability suggests that although generating explanations for GAM may be intractable, reducing the precision of its coefficient weights can render the explanation task efficient.
Key Insights. Beyond the direct contributions that our results offer of both efficient algorithms and intractability outcomes, they also uncover several surprising insights into the computational nature of generating explanations for GAMs, as highlighted below:
The complexity of computing explanations for GAMs depends heavily on the input domain, unlike other MI. models where a variation based on the input domain is not observed. We show that for most explanation types we studied - like sufficient explanations, contrastive explanations, and Shapley values - computing explanations becomes exponentially harder in continuous and discrete settings compared to enumerable discrete ones. An interesting exception is the feature redundancy explanation, which is actually exponentially easier in the continuous case. This significant sensitivity to the input domain is surprising since it appears to be unique to additive models, as other ML models (c.g., decision trees, tree ensembles, neural networks) do not exhibit such diversity in complexity across input domains.
The complexity of obtaining explanations for GAMs largely depends on their compo- nent models, but this effect interestingly appears only in certain input domains. We

---

show that for all our explanation types, there are exponential differences in the complexity of generating explanations for GAMs, depending on the underlying component models (e.g., GAMs with splines are significantly easier to obtain explanations for than NAMs and EBMs). Interestingly, however, we uncover that this complexity distinction arises only the continuous and general discrete input domains, but not in the enumerable discrete domain.
An intriguing complexity separation shows that computing explanations for GAMs used for classification is strictly harder than for regression - but only for SHAP, not other explanations. We demonstrate this by proving polynomial-time results for the regression setting, in contrast to the classification setting, which is #P-Hard highlighting a notable complexity separation.
Some non-additive models (e.g,, neural networks) are harder to obtain explanations over compared to their additive counterparts (e.g,, NAMs), but this depends critically on the explanation type and input domain. We show that models typically hard to interpret -uuch as tree ensembles and neural networks, where computing explanations is at least NP-Hard - become tractable (e.g., solvable in polynomial time, or belonging to lower complexity classes) in their additive forms (e.g.. NAMs, EBMs). Interestingly, however, this phenomenon does not always occur and is highly sensitive to the type of explanation and the input domain.
Due to space limitations, we provide only a brief outline of the proofs for our claims Section 6 with the full proofs presented in the appendix.
2 Preliminaries
Complexity Classes. This paper assumes familiarity with basic complexity classes such as polynomial-time (PTIME), and non-deterministic polynomial-ting (NP, coNP). We also discuss the class EL' which includes problems solvable in NP with access coNP oracle and A which in- cludes problems solvable in PTIME with access to an NP oracle. Clearly, NP and coNP are contained in A and Eie and it is also widely believed that NP, coNP Ç A Ç El 10. Additionally, we cover #P, the class of functions that count the accepting paths of polynomial-ting Turing machines. Although not directly comparable since they focus on counting rather than decision problems, it is widely believed that the #P class is strictly "harder" than 23 which can be denoted as 27 C#P [T0]
nondeterministic
We consider a set of input features indexed by (1....,n) n.), where n E N, and denote an input instance
Setting.
(X1..... ; X.)). Each feature has domain X, such that the input space is defined as F : X1 x X₂ x x Xn. The predictive model f maps inputs from FF either to a regression output, f FF Id with dimension d N, or a classification label, ʃ : [c). where E N is the number of classes. For clarity in our proofs, we restrict f to have a one-dimensional output- i.e,, f: F - R in the regression case and ʃ : F - {0. 1) in the classification case though emphasize that our results extend to multi-dimensional outputs (see Appendix D for details). The majority of explanations we study are local, aiming interpret the model's prediction at a specific instance x E I - that is, to explain why fx) was predicted. However, we also consider some global explanations, which aim to interpret the overall behavior of f. independent of any particular input.
Generalized Additive Models (GAMs), A GAM f is defined as an additive model consisting of component models f2..... fv. Formally, in the regression setting, define:
f(x) = 80 + (x1 82f2(Xe) + ... (x.f
where Bo, ,.,...,,,,,, 8r E Q are the intercept terms and f(x) E IR is the regressor predictive value. For the scenario where f((x) is classification model, we assume a step function over the additíve
prediction, i.e., f(x) := step(30 (3o + (x)) + (x2) (.c.33 where we define the step
function as step(z)= 1 if z 0, and step(z) = 0 otherwise.
3

---

3 Dimensions of the Complexity Analysis
As previously mentioned, our detailed complexity analysis spans three distinct dimensions: (i) the input domain, (ii) the types of component models utilized within GAMs, and (iii) the explanation types. In this section, we elaborate each of these dimensions.
3.1 Dimension 1: The input domain
We study the following cases for the domain X; of feature E (I....n]: (i) when the domain is enumerable discrete, meaning each value x; is selected from a given set K. S Q of constant number [X] of possible assignments. Intuitively, these are scenarios where each input is limited to a predefined set of values, which is often relevant for cases such as tabular data certain language tasks; (ii) the discrete setting, or the general discrete setting, where A; represents any discrete input within range defined by maximum and minimum values expressed in binary with bits. This intuitively allows a broader range of discrete assignments for each input, while still operating within discrete domain. (iii) The continuous setting, where X; S R. which ensures guarantees across the entire infinite spectrum of the specified domain. Both discrete and continuous domains are widely used across various ML tasks, including those in vision and language tasks [46 52 36). We note that general discrete settings naturally encompass enumerable ones and are thus always at least as computationally challenging, whereas continuous settings do enable a direct comparison to either and can make problems either harder or easier to solve [68] 103 10
3.2 Dimension 2: The component model type
We consider diverse range of component models that can be integrated into GAM, spanning various levels of interpretability and reflecting commonly used approaches in the literature: (i) The classic spline-based models [51], where each component function is piecewise polynomial. In practice, these polynomials are typically restricted to a degree of at most three, yielding the widely used cubic splines [51], which will be our primary focus (though
often be extended to higher-order splines- see Appendix B). To distinguish these GAMs from the non-smooth variants, refer GAMs with spline-based components as Smooth GAMs. (ii) Neural Additive Models (NAMs) [ 30 TT0 [66] [O0], in which each component is a neural network with ReLU activations. (iii) Explainable Boosting Machines (EBMs) 337 [07 89], where each component function is boosted tree ensemble. We present the complete formal definitions of all model types in Appendix B.
results
3.3 Dimension 3: The explanation type
To explore various dimensions of GAM interpretability, we examine broad range of widely used explanation types drawn from the existing literature. Building upon prior computational complexity frameworks for evaluating explanations in ML models [16 6. [8], we formalize each type of explanation as an explainability query. Such a query takes a model I and x as inputs and aims to address specific questions, offering meaningful interpretation of the prediction fxx).
Sufficient reason Feature Selection. We consider the common sufficiency criterion for feature selection, used in popular explainability methods 993 35 58]. A sufficient reason is a subset of imput features, S _ [m). such that fixing the features in to their values in x E guarantees the prediction remains f fx), regardless of the assignment S. We write (xs; zg) for an input where takes values a sufficient reason for (f. x) iff for all z F: fxs: Zg) = fx).
from x and S from z. Formally,
common assumption in the literature is that smaller sufficient reasons (those with smaller |S)) are more useful 93 35 58) This motivates the search for cardinally minimal sufficient reasons, also called minimum sufficient reasons, and leads to our first explainability query:
MSR (Minimum Sufficient Reason): Input: Model f, input x, and d N Output: Yes if there exists some S C [m] such that S is a sufficient reason with respect to (f x) and |S| < d. and No otherwise.
To deepen our understanding of the complexity of sufficient reasons, we also examine two common related explainability queries that refine the MSR query [16] [8] (i) Cheek--SfficiettReeen (CSR),

---

which checks if a given subset S is sufficient reason; (ii) Count- Completions (CC), a generalized version of CSR that measures the fraction of completions preserving the prediction, capturing the probubility of maintaining the classification. Full formalizations appear in Appendix C.
Contrastive Explanations. An alternative way to interpret models is by identifying subsets of features that, when changed, could alter the model's prediction [45] [50]. We define s subset S S [n]] as contrastive if modifying its values can change the classification fxx), i... there exists z IF such
that f (xg: 2ş) * fx).. As with sufficient reasons, smaller contrastive subsets are typically assumed be more meaningful
45 50
57
86
motivating focus on cardinally-mintnn minimal contrastive reasons:
MCR (Minimum Change Required): Input: Model f. input x, and d N.
Output: Yes, if there exists some contrastive reason S such that |S| S d for fxx), and No otherwise,
Shapley Values. In the additive attribution setting, each feature E [mx] is assigned an importance weight di. A common method for assigning these weights is the Shapley value attribution index [76]
|S|!(n |8] - 1)! n!
(f.x)) =
E SCIIM
(((SU()))-(())
(2)
We use the standard conditional expectation value function c := Ex~D, [f(z) 2s = xx] [00 76..
Moreover, is standard in both complexity analyses 88 102 and practical SHAP methods like
KernelSHAP 766, we assume feature independence. See Appendix C for a full formalization.
SHAP (Shapley Additive Explanation): Input: Model f, input and E [r]] The shapley value (f,
Output:
Feature redundancy. For our final explanation form, study the complexity of determining whether a feature is redundant with respect to a model f. following the notion of redundancy
explored in prior work 6
18 53 43 Unlike the previous local explanation forms, this one is global
it checks if is redundant for all x E F. Formally, is redundant for all x, z E F, we have f(x) (M i1))
FR (Feature Redundancy): Input: Model f. and integer i. Output: Yes, if is redundant with respect to f, and No otherwise.
4 Main Complexity Results
We examine the complexity across all analyzed settings - spanning input domains (enumerable discrete, discrete, continuous), model types (NAMs, EBMs, Smooth GAMs), and explanation forms (CSR, MSR, MCR, FR, CC, SHAP). We distinguish between SHAP for regression and classification (SHAP-R SHAP-C), complexity split, which, For each setting, we provide novel complexity proof, beginning with a summary in Table]] [
explain in detail later, is unique to SHAP.
The results in Table I iddetiffy when explanations can be computed efficiently (e.g., in polynomial or time) and when they are computationally intractable (e.g., NP-Hard). central finding is the significant variation in complexity, influenced by factors such as the input domain, the type of component model, and whether the task is regression or classification. analyze this diverse landscape in depth and compare these complexity results to existing complexity results for non-additive models like neural networks and tree ensembles. In Section 6 we will outline the proofs underlying these complexity results.
geeudo-polynoneg
Section 5 we
5

---

Table 1: A summary of complexity results across all component-men model types, input domains, and explanations. Bold font emphasizes the most tractable complexity classes for each explanation.
Input Space
Component Type
CSR, MSR
MCR
FR
CC. SHAP-C
SHAP-R
Enumerable
#PC (Pseudo-P)
Any
PTIME
PTIME
coNP-C
PTIME
Discrete
Smooth GAMs
PTIME
PTIME
coNP-C
#P-C
PTIME
Discrete
NAMs, EBMs
coNP-H
NP-C
coNP-C
#P-C
#P-C
Smooth GAMs
PTIME
PTIME
PТIME
#P-C
PTIME
Continuous
NAMs, EBMs
coNP-H
NP-C
coNP-C
#P-C
#P-C
5 A Computational Interpretability Hierarchy for GAMs
Our results uncover a rich and varied landscape of complexity outcomes across different settings, which we analyze in this section. To present these complexity distinctions more elegantly, we adopt the notation from [16], indicating when one model strictly more computationally interpretable (e-interpretable) than another that is, when it belongs to strictly lower complexity class.
Definition 1. Let C1 and C2 be two classes of models and let Q be an explainabilityy query for which Q(C,) is in complexity class K1 and ((22) is in complexity class Kz. We say that C1 is strictly more c-interpretable than C2 with respect Q iff (C2)) hard for the complexity class K2 and Kr & K2-
5.1 The Sensitivity of Complexity to the Input Domain, in Contrast to Other ML Models
Our results reveal significant exponential complexity distinctions in explaining GAMs based on the input domain surprising finding, as such distinctions do not appear in other popular ML models (e.g., decision trees, tree ensembles, neural networks; see Appendix D for details). While explanations over enumerable discrete domains often computable in polynomial time, they become intractable in general discrete or continuous settings. The only exception is the feature redundancy query.
Theorem 1. GAMs over enumerable discrete settings are strictly more e-interpretable than GAMs over general discrete or continuous settings with respect to CSR, MCR, MSR, CC and SHAP.
The intuition is that in an enumerable discrete setting, the input space can be explicitly traversed evaluate each component fa allowing computations such minimum maximum component output computation - key for sufficient or contrastive reason queries as well as expected value computation, which essential for SHAP. However, in the general discrete or continuous setting, such iteration is infeasible, making these computations intractable.
However, interestingly, we discover that for one of the queries we analyzed the Feature Redundancy (FR) query, which seeks to determine whether a feature does not contribute to a model's prediction this type of explanation actually strictly easier obtain in the continuous setting compared the discrete or even the enumerable discrete settings:
Theorem 2. GAMs continuous input settings are strictly more c-interpretable than GAMs over enumerable discrete or general discrete input settings with respect to FR.
We highlight that these complexity gaps, tied to input domains, are unique to additive models. For other model types decision trees, neural networks, and tree ensembles no such gaps appear (see Appendix D for an elaborate discussion):
Observation 1. While there exist strict complexity gaps for the CSR, MCR, CC, SHAP, and FR queries between the different input setting configurations for GAMs, such complexity gaps do not hold for other ML models such as decision trees, tree ensembles, and neural networks.
5.2
The Significance of the Component Models on Complexity Depends on the Input Domain
We show that while computing some explanations for certain GAMs with more interpretable com- ponent models (such as splines) can be done efficiently, these same tasks may sometimes become intractable for GAMs consisting of uninterpretable component models (e.g., neural networks or boosted trees). We show that this phenomenon holds only in the continuous and discrete input spaces:

---

Theorem 3. GAMs over continuous or discrete inputs composed of splines (Smooth GAMs) are strictly more c-interpretable than GAMs with neural networks or tree ensembles (NAMs, EBMs).
However, we surprisingly demonstrate that this distinction between model components does not always hold and is dependent on the input domain. Specifically, we show that this gap emerges only in the continuous and discrete imput settings but not in the enumerable discrete setting. The intuition behind this result is that the enumerability of the input space mitigates the complexity originating from the component model itself, unlike in the discrete or continuous domains:
Observation 2. While there exist strict complexity distinctions between component models when computing explanations for GAMs in the discrete and continuous input domain, such complexity distinctions do not hold under the enumerable discrete input domain.
We also note that the result shown in this subsection, together with our findings in Subsection 5.1 on input domain sensitivity, offers a complementary perspective to empirical work such [39. These studies demonstrate that both the choice of component model and the form of data representation (i.e., input representation) substantially influence the learned functional structure of GAMs. Since differing functional forms naturally correspond to different levels of computational complexity, this aligns with our observation that the complexity of generating explanations is highly sensitive to these modeling choices.
5.3 Complexity Distinctions Between Regression and Classification, but Only for SHAP
In the context of SHAP explanations, reveal an intriguing complexity distinction between classifi- cation and regression GAMs. Specifically, we show that while SHAP explanations for regression tasks on Smooth GAMs (or general GAMs with enumerable discrete inputs) can be computed in polynomial time, the same problem becomes computationally intractable (#P-hard) for classification tasks. The intuition underlying this distinction is that the classification scenario introduces an ad- ditional "step" function, whose non-linearity violates the linearity axiom essential for establishing tractability in the regression setting. This result motivates the following:
Theorem 4. Regression Smooth GAMs and regression GAMs with enumerable inputs are strictly more c-interpretable than classification Smooth GAMs and classification GAMs with enumerable inputs with respect to SHAP.
We note that while SHAP allows for a direct comparison between regression and classification tasks, adapting our other explanation types - originally defined for classification - to regression requires redefining them (as in [109 61) to assess whether values lie within specified d-range. From complexity standpoint, these behave similarly to classification cases and do not produce the same distinctions observed with SHAP. We elaborate on this in Appendix D.
5.4 Additive vs. Non-Additive Complexity Depends on the Input Domain and Explanation
As noted in the introduction, the ML community often assumes that increasing a model's additivity improves interpretability. For instance, NAMs E 92 and EBMs 37 are generally seen more interpretable than standard neural networks and boosted trees, respectively. It thus seems natural to expect that explanations for additive models (e.g., NAMs) are easier compute than their non- additive counterparts. Our findings support this, showing a clear complexity gap between black box models and their additive counterparts. However, importantly, this gap is not universal - it strongly depends on the explanation type and the input domain. Table summarizes prior complexity results for neural networks and tree ensembles, alongside our new results for NAMs and EBMs.
Particularly, we show that in the enumerable discrete input domain, there exist many complexity gaps between the non-additive models neural networks and tree ensembles, and their additive counterparts (NAMs and EBMs) However, in the discrete and continuous input settings, while such complexity gap is apparent in the minimum-suffin reason (MSR) query, it is not apparent in the other queries. These observations lead us to the following corollary:
Theorem 5. NAMs and EBMs over enumerable discrete input settings are strictly more c-interpretable than neural networks and tree ensembles with respect to CSR, MSR, MCR, and SHAP for regression. However, NAMs and EBMs over general discrete or continuous input settings are strictly more c-interpretable than tree ensembles and neural networks with respect to MSR.
7

---

Table 2: Complexity distinctions in explaining non-additive black-box models tree ensembles (TEs) or neural networks (NNs), compared to their additive counterparts neural additive models (NAMs) and explainable boosting machines (EBMs). We emphasize in bold font cases where strict complexity separation exists between an additive and non-additive configuration.
Enumerable Discrete
Discrete, Continuous EBMs, NAMs
EBMs, NAMs
TEs, NNs
TEs, NNs
CSR
PTIME
coNP-C
coNP-C
coNP-C
MSR
PTIME
Σ NP-C coNP-C
CONP-H, in A
Σ -C
MCR
PTIME
NP-C
NP-C
FR
coNP-C
CoNP-C
coNP-C
CC. SHAP-C
#P-C (Pseudo-P)
#P-C (No Pseudo-P)
#P-C
#P-C
SHAP-R
PTIME
#P-C
#P-C
#P-C
6 Proof Outline of Complexity Results
We begin by summarizing the tractable results explanations that can computed polynomial time in Subsection 6.1 Next, in Subsection 6.2 we discuss a relaxed setting where tractabil- ity is preserved under unary-encoded weights, referred to as pseudo-polynomial time. Finally, Subsection 6.3 covers the intractable cases, such as NP-hardness and #P-hardness results.
6.1 Polynomial-Time Explanation Computations
Sufficient and contrastive reasons. We begin by analyzing the polynomial-time complexity of computing sufficient and contrastive reason queries (CSR, MSR, MCR). A key observation that by identifying the minimal and maximal values each component 3, (x;) can take, can rank features by their "importance". measured by how much altering each feature deviates the prediction. greedy algorithm, akin those in [16 78), then selects features by importance until minimal sufficient or contrastive reason is found. CSR is simpler, requiring only a sufficiency check for given subset. Thus, the main computational challenge lies in efficiently computing the min/max values of each fx,)) For enumerable discrete inputs, this can be done by enumeration; for smooth GAMs, these values can be computed analytically, even with general discrete or continuous inputs.
Proposition 1. Given any GAM over enumerable discrete domain, discrete or continuous domain, the CSR, MCR, and MSR queries are solvable in polynomial time.
Smooth GAM over
Feature redundancy for Smooth GAMs in continuous settings. Unlike the discrete enumerable discrete settings, where identifying strict feature redundancies is intractable (see Subsection 6.3) in continuous domains show that feature is strictly redundant if and only if its component B, (x,, identically zero - i.e., either 3; = 0 or fx(x)) = 0 for all x, For Smooth GAMs, this can be checked efficiently in polynomial time. This leads to the following proposition:
Proposition 2. Given Smooth GAM f over a continuous input space, the FR query can be obtained in polynomial time.
SHAP explanations in regression settings. When computing SHAP, polynomial cittomial-timeeeeee computation is feasible only for GAMs in regression tasks (classification intractability is discussed in Subsection (.3ectttoooo33........ 663) Leveraging the linearity axiom of Shapley values [76), we reduce the computation to evaluating the computations of B, EEz,D, [x,)] When the model is either discretely enumerable or supports efficient integration (e.g., in Smooth GAMs), these expectations can be computed in polynomial time.
Proposition 3. Given any regression GAM with enumerable discrete inputs, or given a regression Smooth GAM with discrete continuous imputs, then the SHAP query is solvable in polynomial time.
6.2 Pseudo Polynomial-Time Explanation Computations
Table shows that both CC and SHAP-C queries are intractable. However, if the GAM's internal encoding and input is given in unary (rather than binary) and the GAM has a polynomially bounded output, they become computable in polynomial time. This psendo-polynomial setting enables efficient computation when the encoding precision is bounded, using dynamic programming similar [16),

---

and detailed in our proofs. It applies to enumerable discrete domains (all component types), where enumeration makes En-D, (x:) tractable.
Proposition 4. Given any unary-encoded GAM over discrete, enumerable input domain with poly- nomially bounded output, the CC and SHAP-C queries admit a pseuulopolynomial- algorithm.
6.3 Intractable Explanation Computations
Sufficient and contrastive reasons. As shown in Subsection 6.1 finding cardinally minimal sufficient or contrastive reason in GAMs requires computing the minimal and maximal values of each fx(),) component. We show this is intractable for neural networks and tree ensembles, their exponential search space makes the problem computationally hard. The main difficulty is proving hardness even for single input-output instances, where lower expressivity demands constructions. We overcome this by reducing the instance to an equivalent n-dimensional input, mapping continuous general discrete regions to their relevant counterparts, yielding the following:
intricate
Proposition 5. Let there be NAM or EBM over discrete continuous inpul space, then solving the CSR query comp-Comee the MSR query is coNP-Hare and the MCR query is SP-Complete.
Feature redundancy. In contrast to the continuous case, where redundancy reduces to checking if 3, f(())) = 0, in discrete settings it requires verifying whether this value falls below the decision boundary task that is often computationally intractable:
Proposition 6. Given NAM, a Smooth GAM or an EBM under an enumerable discrete general Compleee
discrete setting, then the FR query
Intractability of SHAP and count completions. Finally, show that computing the SHAP and CC queries is generally #P-Hard by reducing to the model counting problem [102], implying intractability for EBMs and NAMs. While other settings are also intractable (see Subsection 6.2)
their complexity can be mitigated using
algorithms:
Proposition Given NAMs and EBMs over discrete or continuous settings, computing SHAP for regression tasks is C-Comllee Moreover, given any GAM over enumerable discrete, discrete or continuous setting- - computing the CC and SHAP queries for classification are --P-Compeeee
Practical Implications
Although our work is primarily theoretical, it provides several insights with practical relevance for practitioners working with GAMs. First, we identify a broad class of efficient polynomial-tine algorithms for computing explanations with different guarantees across diverse GAM settings. In fact, all of the tractable algorithms presented in this work (included the appendix) are not only polynomial-time, but even linear in the size of the GAM, underscoring their practical applicability.
Second, we show that techniques commonly used in machine learning practice can also make explanation methods computationally feasible. In particular, we identify two strategies that can transform otherwise hard explanation problems into tractable ones:
1. Input domaín transformations. We find that the computational complexity of generating explanations is highly sensitive to the structure of the input domain. Small changes in the domain can shift problems from intractable to tractable. This insight motivates the use of input transformations, such as discretization, a standard step in many GAM pipelines [37 [89] to reshape the input space in ways that make explanation computation efficient.
2. Quantization. Our pseuto-polynomial algorithms show that explanation problems that intractable in full generality become tractable when the GAM encoding is quantized. This suggests promising practical approach: by quantizing model coefficients, one can enable efficient computation of explanations that would otherwise be infeasible.
8 Related Work
Our work builds upon prior research exploring the computational complexity of obtaining various
types of explanations for ML models [16]
9
28
27
53
15
26
72
83
73
31
I
67]. This area

---

is closely tied to the subfield of interest known as formal explainable A/ [7,,24] 24]
which focuses on
explanations with mathematical guarantees [58] 109 62
43
20
64
17
32
where analyzing the
complexity of producing explanations with such guarantees plays central role (60 91
42 90
102.
Previous work has mainly examined the complexity of generating explanations for specific ML models, including black-box models like neural networks 12] [6] and interpretable models like decision trees 9 33 [5]] Closer to our work are studies on linear models T6 99, 788 - a simplified
form of GAMs - typically under binary input-output settings. In contrast, we offer a comprehensive analysis of a broad class of GAMs, covering diverse component models, explanation types, input assumptions, and approximation results. We elaborate further on related works in Appendix A.
Lastly, we note that some terms in our work have sometimes been referred to differently in prior literature. For instance, while the term sufficient reasons is widely used [16
it is also referred to as abductive explanations (59]. Moreover, subset-minimal sufficient reasons are closely related- though not identical to prime implicants in Boolean formulas [44 43 97 Simillarly, the CC query
23 [
corresponds to the ò-relevant set [104] 62 99 which checks if the completion count exceeds a given threshold 6.
9 Limitations and Future Work
As in prior work on the computational complexity of obtaining explanations, our analysis focuses on specific explanation definitions and component model types, though many other settings could certainly be explored. Nevertheless, we believe that our work provides a broad perspective across a wide array of popular explanation methods, component types, and input settings, highlighting various novel aspects of the explainability landscape for GAMs and establishing strong foundation for exploring additional settings in future research.
More concretely, our results open the door to a wide range of future practical implementations of our algorithms (see Section 9p. From a theoretical perspective. our analysis can be extended in several directions. A first promising avenue is to better understand how high-order interactions, which are widely used in GAMs varies across explanation types and component models. Another interesting direction is to study how structural assumptions over the GAM influence complexity. For instance, one may consider the effect of concurvity [71 (98.. In the extreme case of high concurvity, where smooth components are strongly correlated and behave almost like a single spline, the GAM may resemble a simpler function class, potentially making some explanation problems easier. Conversely, in the case of low concurvity, especially for explanation types that rely on interactions, the high separability between components may also offer computational advantages. Finally, for intractable settings, one can attempt to leverage automated reasoning tools, such as neural network verifiers [108] [06] or MILP/MaXSAT solvers for tree ensembles (56) [1] to obtain explanations. Moreover, while propose two central strategies for circumventing intractability, input transformations and quantization (see Section 9 exploring additional cireumvention approaches such approximation guarantees, probabilistic or statistical relaxations, and PAC-based guarantees remains an important direction for future research.
[8 75
70 48 affect the complexity of generating explanations, and how this
10 Conclusion
We present a theoretical framework for assessing the computational complexity involved in obtaining various forms of explanations for different types of GAMs. Our work uncovers a nuanced spectrum of results, demonstrating that the complexity of obtaining explanations for GAMs is sigmificantly influenced by (i) the input space domain (enumerable discrete, discrete, and continuous), (ii) the type of explanation (sufficient, contrastive, shapley value explanations, etc.), (iii) the underlying component model (e.g., neural networks, boosted trees, splines, etc.), (iv) and the distinction between classification and regression settings. Our findings reveal a broad range of unexpected and substantial complexity variations, driven by surprising factors such as the input domain which are not apparent in other ML models. We believe that our work lays the foundation for a wide range of implementations by enabling the development of tractable algorithms for computing explanations for GAMs in diverse settings. At the same time, it advances the theoretical understanding of these models by identifying when such explanations are computationally feasible and when they are not.
10

---

Acknowledgments
This work was partially funded by the European Union (ERC, VeriDeL., 101112713). Views and opinions expressed are however those of the author(s) only and do not necessarily 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. This research was additionally supported by a grant from the Israeli Science Foundation (grant number 558/24).
References
[1] F. Adolfi, M. Vilas, and T. Wareham. The Computational Complexity Circuit Discovery for Inner Interpretabilityy In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
[2] F. Adolfi, M. G. Vilas, and T. Wareham. Complexity-Theoretie Limits on the Promises of Artificial Neural Network Reverse- Engineering. In Proc. 46th Annual Meeting of the Cognitive Science Society (CogSci), 2024.
[3] R. Agarwal, L. Melnick, N. Frosst, X. Zhang, B. Lengerich, R. Caruana, and G. E. Hinton. Neural Additive Models: Interpretable Machine Learning with Neural Nets. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), 2021.
[4] D. Alvarez Melis and T. Jaakkola. Towards Robust Interpretability with Self-Explaine Neural Networks. In Proc. 32nd Conf. on Neural Information Processing Systems (NeurIPS), 2018.
[5] G. Amir, S. Bassan, and G. Katz. Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation. In Proc. 27th European Conf. on Artifical Intelligence (ECAT), 2024.
[6] M. Arenas, D. Baez, P. Barceló, J. Pérez, and B. Subercaseaux. Foundations of Symbolic Languages for Model Interpretability. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), pages 11690-11701, 2021.
[7] M. Arenas, P. Barceló, L. Bertossi, and M. Monet. The Tractability of SHAP-Score-Basel Explanations for Classification Over Deterministic and Decomposable Boolean Circuits. In Proc. 35th AAAI Conf. on Artificial Intelligence (AAAI), pages 6670-6677 2021.
[8] M. Arenas, P. Barceló, L. Bertossi, and M. Monet. On The Complexity of SHAP-Score- Explanations: Tractability via Knowledge Compilation and Non-Approximability Results. Journal of Machine Learning Research (JMLR), 24(63):1-58, 2023.
[9] M. Arenas, P. Barceló, M. Romero, and B. Subercaseaux. On Computing Probabilistic Explanations for Decision Trees. Proc. 36th Conf. on Neural Information Processing Systems (NeurIPS), pages 28695-28707, 2022.
[10] S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
[11] G. Audemard, tional Intelligibility of Boolean Classifiers. In Proc. 18th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pages 74 86, 2021.
S. Bellart, L. Bounia, F. Koriche, J. Lagniez, and P. Marquis. On the Computa-
[12] G. Audemard, S. Bellart, L. Bounia, F. Koriche, J.-M. Lagniez, and P. Marquis. On Preferred Abductive Explanations for Decision Trees and Random Forests. In Proc. 31st Int. Joint Conf. on Artificial Intelligence (IJCAI), pages (43-650, 2022.
[13] G. Audemard, F. Koriche, and P. Marquis. On Tractable XAI Queries Based on Compiled Representations. In Proc. Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pages 838-849, 2020.
[14] G. Audemard, J.-M. Lagniez, P. Marquis, and N. Szezepanski. Computing Abductive Expla- nations for Boosted Trees. In Proc. 26th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pages 4699-4711, 2023.
11

---

[15] P. Barceló, A. Kozachinskiy, M. Romero, B. Subsercaseaux, and J. Verschae. Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. In Proc. 3rd ACM on Management of Data, number 2, pages 1-26, 2025.
[16] P. Barceló, M. Monet, J. Pérez, and B. Subercaseaux. Model Interpretability through the Lens of Computational Complexity, In Proc. 34th Conf. on Neural Information Processing Systems (NeurIPS), pages 15487-15498, 2020.
[17] S. Bassan, G. Amir, D. Corsi, I. Refaeli, and G. Katz. Formally Explaining Neural Networks Within Reactive Systems. In Proc. 23rd Int. Conf. on Formal Methods in Computer-Aided Design (FMCAD), pages 1-13, 2023.
[18] S. Bassan, G. Amir, and G. Katz. Local vs. Global Interpretability: A Computational Com- plexity Perspective. In Proc. 41st Int. Conf. on Machine Learning (ICML), 2024.
[19] S. Bassan, G. Amir, M. Zehavi, and G. Katz. What makes an Ensemble (Un) Interpretable? In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
[20] S. Bassan, Y. Y. Elboher, T. Ladner, M. Althoff, and G. Katz. Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
[21] S. Bassan, Y. Elboher, T. Ladner, V. Şahin, J. Kretinsky, M. Althoff, and G. Katz. Provably Explaining Neural Additive Models. In Proc. 14th Int. Conf. on Learning Representations (ICLR), 2026.
[22] S. Bassan, R. Eliav, and S. Gur. Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons. In Proc. 13th Int. Conf. Learning Representations (ICLR), 2025.
[23] S. Bassan, S. Gur, S. Zeltyn, K. Mavrogiorgos, R. Eliav, and D. Kyriazis. Self-Explaining Neural Networks for Business Process Monitoring. 2025. Technical Report. htttps///arXiv 2503. 18067]
[24] S. Bassan and G. Katz. Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks. In Proc. 29th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pages 187-207, 2023.
[25] M. Bechler-Speicher, A. Globerson, and R. Graph Neural Additive Network. In Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), pages 90552-90578, 2024.
The Intelligible and Effective
[26] R. Bhattacharjee and U. Luxburg. Auditing Local Explanations is Hard. In Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), pages 18593-18632, 2024.
[27] G. Blanc, C. Koch, J. Lange, and L.-Y. Tan. A Query-Optimal Algorithm for Finding Counterfactuals. In Proc. 39th Int. Conf. Machine Learning (ICML), pages 2075-2090, 2022.
[28] G. Blanc, J. Lange, and L.-Y. Tan. Provably Efficient, Succinet, and Precise Explanations. In Proc. 35th Conf. on Neural Information Processing Systems (NeurlPS), pages 6129-6144 2021.
[29] S. Bordt and U. von Luxburg, From Shapley Values to Generalized Additive Models and Back. In Proc. 26th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pages 709-745, 2023.
[30] K. Bouchiat, A. Immer, H. Yèche, G. Ratsch, and V. Fortuin. Improving Neural Additive Models with Bayesian Principles. In Proc. 41st Int. Conf. on Machine Learning (ICMI., 2023.
[31] L. Bounia. Enhancing the Intelligibility of Boolean Decision Trees with Concise and Reliable Probabilisticc Explanations. In Proc. 20th Ini. Conf. on Information Processing and Manage- ment of Uncertainty in Snowledge-Based Based Systems (IPMU), volume 1174, pages 205-218, 2024.
12

---

[32] L. Bounia. Using Submodular Optimization to Approximate Minimum-Stee Size Abductive Path Explanations for Tree-Based Models. In Proc. 41st Conf. on Uncertainty Artificial Intelligence (UAT), 2025.
[33] L. Bounia and F. Koriche. Approximating Probabilistic Explanations via Supermodular Minimization. In Proc. 39th Conf. on Uncertainly in Artificial Intelligence (UAI), pages 216-225, 2023.
[34] M. Calautti, E. Malizia, and C. Molinaro. On the Complexity Global Necessary Reasons to Explain Classification. 2025. Technical Report. httpss//aarrrrrrppttttaxxvvvvvv 06766
[35] B. Carter, J. Mueller, S. Jain, and D. 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), pages 567-576, 2019.
[36] R. Cartuyvels, G. Spinks, and M.-F. Moens. Discrete and Continuous Representations and Processing in Deep Learning: Looking Forward. AI Open, 2: 2:143-159, 2021.
[37] R. Caruana, Y. Lou, J. Gehrke, P. Koch, M. Sturm, and N. Elhadad. Intelligible Models for Healtheare: Predicting Pneumonia Risk and Hospital 30-day Readmission. In Proc. of the 21th Int. Conf. on Knowledge Discovery and Data Mining (ACM SIGKDD), pages 1721-1730, 2015.
[38] C.-H. Chang, R. Caruana, and A. Goldenberg. NODE-GAM: Neural Generalized Additive Model for Interpretable Deep Learning. In Proc. 10th Int. Conf. on Learning Representations (ICLR), 2022.
[39] C.-H. Chang, S. Tan, B. Lengerich, A. Goldenberg, and R. Caruana. How Interpretable and Trustworthy are GAMs? In Proc. 27th Conf. on Knowledge Discovery & Data Mining (ACM SIGKDD), pages 95-105, 2021.
[40] H. Chen, Y. Wang, F. Zheng, C. Deng, and H. Huang. Sparse Modal Additive Model. Transactions Neural Networks and Learning Systems, 32(6):2333-2387 2020.
[41] H. Chen, H. Zhang, S. Si, Li, D. Boning, and C.-J. Hsich. Robustness Verification of Tree-Based Models. In Proc. 33rd Conf. on Neural Information Processing Systems (NeurIPS), 2019.
[42] M. C. Cooper and J. Marques-Sily On the Tractability of Explaining Decisions of Classifiers. In Proc. 27th Int. Conf. on Principles and Practice of Constraint Programming (CP), pages 21- 2021.
[43] A. Darwiche and A. Hirth. On the Reasons Behind Decisions. In Proc. 24th European Conf. on Artificial Intelligence (ECAI), pages 712-720, 2020.
[44] A. Darwiche and P. Marquis. A Knowledge Compilation Map. Journal of Artificial Intelligence Research (JAIR), 17:229-264, 2002.
[45] A. Dhurandhar, P.-Y. Chen, R. Luss, C.-C. Tu, Ting, K. Shanmugam, and P. Das. Explana- tions Based on the Missing: Towards Contrastive Explanations with Pertinent Negatives. In Proc. 32nd Conf. on Neural Information Processing Systems (NeurIPS), 2018
[46] O. Elkabetz and N. Cohen. Continuous vs. Discrete Optimization of Deep Neural Networks. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), pages 4947-4960, 2021.
[47] J. Enouen and Y. Liu. Sparse Interaction Additive Networks via Feature Interaction Detection and Sparse Selection. In Proc. 36th Conf. on Neural Information Processing Systems (NeurIPS), pages 13908-1888 13920, 2022.
[48] J. Enouen and Y. Liu. InstaSHAP: Interpretable Additive Models Explain Shapley Values Instantly. In Proc. 13th Int. Conf. Learning Representations (ICLR), 2025.
13

---

[49] T. Geibinger, R. Jaakkola, A. Kuusisto, X. Liu, and M. Vilander. Why This and Not That? A Logic-based Framework for Contrastive Explanations. Proc. 19th European Conf. on Logics in Artificial Intelligence (JELJA), pages 45-60. Springer, 2025.
[50] R. Guidotti. Counterfactual Explanations and How to Find Them: Literature Review and Benchmarking. Data Mining and Knowledge Discovery, pages 1-55, 2022.
[51] T. J. Hastie. Generalized Additive Models. In Statistical models in S, pages 249-307. Routledge, 2017.
[52] Y. Hong. Z. Wang. Q. Wu, and S. Gould. Bridging the Gap Between Learning in Discrete and Continuous Environments for Vision-and-Langunn Navigation. In Proc. of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition (CVPR), pages 15439-15444 2022.
[53] Huang, M. Cooper, A. Morgado, Planes, and J. Marques-Silva. Feature Necessity & Relevancy in ML Classifier Explanations. In Proc. 29th Int. Conf. Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pages 167-186, 2023.
[54] X. Huang, Y. Izza, A. Ignatiev, and Marques- Silva. On Efficiently Explaining Graph-Based Based Classifiers. In Proc. 18th Int. Conf. Principles of Knowledge Represenlation and Reasoning (KR), 2021.
[55] X. Huang and J. Marques-Sile Silla. Updates on the Complexity of SHAP Scores. In Proc. of the 33rd Int. Joint Conf. on Artificial Intelligence (IJCAI). pages 403-412, 2024.
[56] Ignatiev, Y. Izza, P. J. Stuckey, and Marques-Sine Silva. Using MaxSAT for Efficient Explana- tions of Tree Ensembles. In Pruc. 36th AAAI Conf. on Artificial Intelligence, pages 3776-3785, 2022.
[57] A. Ignatiev, N. Narodytska, N. Asher, and J. Marques-Sine Silla. From Contrastive to Abductive Explanations and Back Again. In Proc. Int. Conf. of the Italian Association for Artificial Intelligence (AIxAI), pages 335-355, 2020.
[58] A. Ignatiev, N. Narodytska, and J. Marques-Silva. Abduction-Bassd Explanations for Machine Learning Models. In Proc. 33rd AAAI Conf. on Artificial Intelligence, pages 1511-1519, 2019.
[59] Ignatiev, N. Narodytska, and Marques-Silva On Relating Explanations and Adversarial Examples. In Proc. 33rd Conf. on Neural Information Processing Systems (NeurIPS), 2019.
[60] Y. Izza, X. Huang, A. Ignatiev, N. Narodytska, M. Cooper, and J. Marques-Silva. On Comput- ing Probabilistic Abductive Explanations. Int. Journal of Approximate Reasoning, 159:108939, 2023.
[61] Y. Izza, X. Huang, A. Morgado, J. Planes, A. Ignatiev, and J. Marques-Silva. Distance- Restricted Explanations: Theoretical Underpinnings & Efficient implementation. In Proc. 2 Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pages 475-486, 2024.
[62] Y. Izza, A. Ignatiev, N. Narodytska, M. Cooper, and J. Marques Silva, Efficient Explanations with Relevant Sets, 2021. Technical Report. https: ///tpss//arxiv...o org/ abs/2106...2.../////// 00546)
[63] Y. Izza and J. Marques-Silva. On Explaining Random Forests with SAT. Proc. 30th Int. Joint Conf. Artificial Intelligence (IJCAI), 2021.
[64] Y. Izza, K. S. Meel, and J. Margues--SSsaaa Locally-Minima Probabilistic Explanations. 2023. Technical Report.
11831
[65] R. Jaakkola, T. Janhunen, A. Kuusisto. M. F. Rankooh, and M. Vilander. Explainability via Short Formulas: the Case of Propositional Logic with Implementation. Journal of Artificial Intelligence Research (JAIR), 83, 2025.
[66] Y. Jiao, C. J. Zdanski, J. S. Kimbell, A. Prince, C. Worden, S. Kirse, C. Rutter, B. Shields, W. Dunn, J. Mahmud, et al. NAISR: 3D Neural Additive Model for Interpretable Shape Representation. In Proc. 12th Int. Conf. Learning Representations (ICLR), 2024.
14

---

[67] H. Jin, A. Xue, W. You. S. Goel, and E. Wong. Probabilistic Stability Guarantees for Feature Attributions. 2025. Technical Report. htttps::/ar21v::250000 13787
[68] N. Karmarkar. A New Polynomial- Talymo Algorithm for Linear Programming. In Proc. of the 16th Annual ACM Symposium on Theory of Computing (STOC), pages 302-311, 1984.
[69] G. Katz, C. Barrett, D. L. Dill, K. Julian, and M. J. Kochenderfer. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. In Proc. 29th Int. Conf. on Computer Aided Verification (CAV), pages 97-117, 2017.
[70] M. Kim, H.-S. Choi. and J. Kim. Higher-Order Neural Additive Models: An Interpretable Machine Learning Model with Feature Interactions. 2022. Technical Report. htttttttttts///att
2209. 15409
[71] L. Kováes. Feature Selection Algorithms in Generalized Additive Models under Concurvity. Computational Stutistics, 39(2):461 -493, 2024.
[72] Kozzchinskiy, hnapriooiiyaaapoooiiiaaaaially of Sufficient Reasons for Decision Trees. 2023. Technical Report. https: 2304/ 2207
[73] E. S. Laber. The Computational Complexity of Some Explainable Clustering Problems. Information Processing Letters, 184:106437, 2024.
[74] J. Liu, C. Zhong, M. Seltzer, and C. Rudin. Fast Sparse Classification for Generalized Linear and Additive Models. Proc. 25th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), 151:9304, 2022.
[75] Y. Lou, R. Caruana, J. Gehrke, and G. Hooker. Accurate Intelligible Models with Pairwise Interactions. In Proc. of the 19th Int. Conf. on Knowledge Discovery and Data Mining (ACM SIGKDD). pages 623-631, 2013.
[76] S. Lundberg and S.-I. Lee. A Unified Approach to Interpreting Model Predictions. In Proc. 31 Conf. on Neural Information Processing Systems (NeurIPS), 2017.
[77] E. L. Malfa, A. Zbrzezny, R. Michelmore, N. Paoletti, and M. Kwiatkowska. On Guaran- teed Optimal Robust Explanations for NLP Models. In Proc. Int. Joint Conf. on Artificial Intelligence (ICCAI), 2021.
[78] J. Marques-Silva, T. Gerspacher, M. Cooper, A. Ignatiev, and N. Narodytska. Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay. In Proc. 34th Conf. on Neural Information Processing Systems (NeurIPS), pages 20590-20600, 2020.
[79] J. Marques-Silva and A. Ignatiev. Delivering Trustworthy AI through Formal XAL In Proc. 36th AAAI Conf. on Artificial Intelligence, pages 12342-12350, 2022.
[80] J. Marques-Silva and A. Ignatiev. No Silver Bullet: Interpretable ML Models Must be Explained. Frontiers in Artificial Intelligence, 6:1 1:1122 2023.
[81] R. Marzouk, S. Bassan, and G. Katz. SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism. In Proc. 39th Conf. on Neural Information Processing Systems (NeurIPS), 2025.
[82] R. Marzouk, S. Bassan, G. Katz, and D. la Higuera. On the Computational Tractability of the (Many) Shapley Values. In Proc. 28th Inf. Conf. on Artificial Intelligence and Statistics (AISTATS), pages 3691-3699, PMIR, 2025.
[83] R. Marzouk and C. De La Higuera. On the Tractability of SHAP Explanations under Markovian Distributions. In Proc. 41st Int. Conf. on Machine Learning (ICML), pages 34961-34986, 2024.
[84] H. McTavish, J. Donnelly, M. Seltzer, and C. Rudin. Interpretable Generalized Additive Models for Datasets with Missing Values. In Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), pages 11904-11945, 2024.
[85] C. Molnar. Interpretable Machine Learning. Lulu.com, 2020.
15

---

[86] R. K. Mothilal, A. Sharma, and C. Tan. Explaining Machine Learning Classifiers Through Diverse Counterfactual Explanations. In Proc. of Conf. on Fairness, Accountability, and Transparency (FAT*), pages 607-617, 2020.
[87] A. C. Mueller, J. Siems, H. Nori, D. Salinas, A. Zela, R. Caruana, and F. Hutter. GAMformer: Exploring In-Context Learning for Generalized Additive Models. In 3th Table Representation Learning Workshop at NeurlPS, 2024.
[88] J. A. Nelder and R. W. Wedderburn. Generalized Linear Models. Journal of the Royal Statistical Society Series A: Statistics in Society, 135(3)3700-344, 1972.
[89] H. Nori, R. Caruana, Z. Bu, J. H. Shen, and J. Kulkarni. Accuracy, Interpretability, and Differential Privacy via Explainable Boosting. In Proc. 38th Int. Conf. on Machine Learning (ICML), pages 8227-8237, 2021.
[90] S. Ordyniak, G. Paesani, M. Rychlicki, and S. Szeider. Explaining Decisions in ML. Models: A Parameterized Complexity Analysis. In Proc. 21 Int. Conf. Principles of Knowledge Representation and Reasoning (KR), number 1, pages 563-573, 2024.
[91] S. Ordyniak, G. Paesani, and Szeider. The Parameterized Complexity of Finding Concise Local Explanations. In Proc. 32nd Int. Joint Conf. on Artificial Intelligence (IJCAI), 2023.
[92] F. Radenovic, A. Dubey, and D. Mahajan. Neural Basis Models for Interpretability. In Proc. 36th Conf. on Neural Information Processing Systems (NeurIPS), pages 8414-8426, 2022.
[93] M. Ribeiro, Singh, and C. Guestrin. Anchors: High-Precision Model-Agnostic Explanations In Proc. 32nd AAAI Conf. on Artificial Intelligence, 2018
[94] M. T. Ríbeiro, S. Singh, and C. Guestrin. Why Should Trust You?" Explaining the Predictions of Any Classifier. In Proc. of the 22nd Int. Conf. on Knowledge Discovery and Data Mining (ACM SIGKDD), pages 1135-1144 2016.
[95] M. Sälzer and M. Lange. Reachability is NP-complete even for the Simplest Neural Networks. In Proc. 15th Int. Conf. on Reachability Problems (RP), pages 149-164, 2021.
[96] M. Sälzer and M. Lange. Reachability is NP-Complete Even for the Simplest Neural Networks. In Proc. 15th Int. Conf. Reachability Problems (RP), pages 149-164, 2021.
[97] A. Shih, A. Choi, and A. Darwiche. A Symbolic Approach to Explaining Bayesian Network Classifiers. In Proc. 27th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 5103-5111, 2018.
[98] J. Siems, K. Ditschuneit, W. Ripken, A. Lindborg, M. Schambach, J. Otterbach, and M. Genzel. Curve Your Enthusiasm: Concurvity Regularization in Differentiable Generalized Additive Models. In Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pages 19029-19057, 2023.
[99] B. Subercaseaux, M. Arenas, and K. S. Meel. Probabilistic Explanations for Linear Models. In Proc. of the AAAI Conf. Artificial Intelligence, volume 39, pages 20655-20662, 2025.
[100] M. Sundararajan and A. Najmi. The Many Shapley Values for Model Explanation. In Proc. 37th Int. Conf. on Machine Learning (ICML), pages 9269-9278, 2020.
[101] A. F. Thielmann, R.-M. Kruse, T. Kneib, and B. 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), pages 1783-1791. PMLR, 2024.
[102] G. Van den Broeck, A. Lykov, M. Schleich, and D. Suciu. On the Tractability of SHAP Explanations. Journal of Artificial Intelligence Research (JAIR), 14:851-8880 2022.
[103] S. A. Vavasis. Nonlinear optimization: complexity issues. Oxford University Press, Inc., 1991.
16

---

[104] S. Wäldchen, J. Macdonald, S. Hauch, and G. Kutyniok. The Computational Complexity of Understanding Binary Classifier Decisions. Journal of Artificial Intelligence Research (JAIR), 70:351-387, 2021.
[105] E. Wang, P. Khosravi, and G. Van den Broeck. Probabilistic Sufficient Explanations. In Proc. 30th Int. Joint Conf. on Artificial Intelligence (IJCAI), 2021.
[106] S. Wang, H. Zhang, K. Xu, X. Lin, S. Jana, C. Hsieh, and Z. Kolter. Beta-Crown: Efficient Bound Propagation with Per-Neuron Split Constraints for Neural Network Robustness Ver- ification. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), pages 29909-29921, 2021.
[107] D. Wei, Nair, A. Dhurandhar, K. Varshney, E. Daly, and M. Singh. On the Safety of Interpretable Machine Learning: A Maximum Deviation Approach. In Proc. 36th Conf. on Neural Information Processing Systems (NeurIPS), pages 9866 088669980, 2022.
[108] H. Wu, O. Isac, A. Zeljić, T. Tagomori, M. Daggitt, W. Kokke, Refaeli, Amir, K. Julian, S. Bassan, et al. Marabou 2.0: A Versatile Formal Analyzer of Neural Networks. In Proc. 36th Int. Conf. on Computer Aided Verification (CAV), pages 249-264, 2024.
[109] M. Wu, H. Wu, and C. Barrett. Verix: Towards Verified Explainability of Deep Neural Networks. In Proc. 37th Conf. Neural Information Processing Systems (NeurlPS), 2023.
[110] S. Xu, Z. Bu, Chaudhari, and I. Barnett. Sparse Neural Additive Model: Interpretable Deep Learning with Feature Selection via Group Sparsity. In Proc. Joint European Conf. on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 343-359, 2023.
[111] A. Xue, R. Alur, and E. Wong. Stability Guarantees for Feature Autributions with Multiplicative Smoothing. Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pages 62388 62411, 2023.
[112] C.-K. Yeh, C.-Y. Hsieh, A. Suggala, D. L. Inouye, and P. K. Ravikumar. On The (In) Fidelity and Sensitivity of Explanations. In Proc. 33rd Conf. on Neural Information Processing Systems (NeurlPS), 2019.
[113] C. Zhong, Z. Chen, J. Liu, M. Seltzer, and C. Rudin. Exploring and Interacting with the Set of Good Sparse Generalized Additive Models. In Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pages 56673-56699, 2023.
[114] H. Zhuang, X. Wang, M. Bendersky, A. Grushetsky, Y. Wu, Mitrichev, E. Sterling, N. Bell, W. Ravina, and H. Qian. Interpretable Ranking with Generalized aAdditive Models. In Proc. 14th ACM Int. Conf. on Web Search and Data Mining (WSDM), pages 499-507, 2021.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction of this work directly reflect the proofs establish and their implications.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We provide dedicated section outlining the limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
18

---

Justification:
Due to space limitations, we present only proof outline in Section 0 with all full and detailed proofs deferred the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA].
Justification:
This is theoretical work; thus, experimental reproducibility is not applicable.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
19

---

Answer:
[NA]
This a theoretical work; therefore, providing open access to data and code is not relevant.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
hetpolliigggiddeeCoototo /oaeeeeee/ooeSuubiiiaoo ssionlolccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [ÑA].
Justification:
This is theoretical work; therefore, hyperparameter details are not relevant.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA].
This is a theoretical work; therefore, experimental statistical testing is not relevant.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emrr bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
20

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA].
Justification: This is theoretical work; thus, information about computational resources is not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes].
Justification: We have reviewed the NeurlPS Code of Ethies Guidelines and verified that our paper fully complies with them.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: While explainability can have social implications, our work is theoretical in nature and therefore does entail any direct social consequences.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
21

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: Our work is theoretical and therefore does not necessitate the implementation of safeguards.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification: This is theoretical work; therefore, such assets are not relevant.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets.ppaerssttt package should be provided. For popular datasets, paperswi thcode. cow datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
22

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
This is theoretical work; therefore, such assets are not relevant.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
This is a theoretical work; therefore, no crowdsourcing experiments were relevant.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA].
Justification: This is theoretical study; therefore, no user studies were conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
23

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This is a theoretical work and does not involve any non-standard use of LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
24

---

Appendix
The appendix provides formal definitions and proofs referenced throughout the paper.
Appendix
A discusses extended related work.
Appendix formalizes the GAMs that were studied in this work.
Appendix provides additional details regarding the explainabilityy queries analyzed in this work.
Appendix contains possible extensions of our framework and its relationship to previous results.
Appendix contains the proof of Proposition
Appendix contains the proof of Proposition
Appendix contains the proof of Proposition
Appendix contains the proof of Proposition
Appendix contains the proof of Proposition
Appendix contains the proof of Proposition
Appendix contains the proof of Proposition
A Extended Related Work
In this section, we present a more technical overview of related work relevant to our framework. While all explanation queries we examine have been explored in prior studies, they were analyzed in the context of different models for neural networks []6] [22 and tree ensembles [91
65 34, 81]. Notably, some results 4 [9 are somewhat related to our setting, as NAMs and EBMs are instances of GAMs that incorporate neural networks or tree ensembles base models. However, demonstrated in work (e.g., Table 2), the shift from additive to non-additive structures leads to fundamentally different complexity behaviors, necessitating entirely distinct proof techniques for both membership and hardness results.
53] 42 102
82
49
54
Another line related work involves studies on the computational complexity of generating specific types of explanations for linear models (e.g., [6 99 [8 [02)). Some of the constructions used in our proofs draw upon ideas introduced in these works, and we reference them where appropriate for instance, the use of sorting algorithms in the MSR/MCR queries and dynamic programming
techniques for the CC and SHAP queries. That said, our study is the first to explore these explanations within the context of GAMs, while also addressing substantially broader and more diverse set of input settings, component models, and explanation types requiring us to tackle considerably more complex instances. For instance, proving hardness for various explanation queries general discrete and continuous domains models like NAMs and EBMs required novel constructions that differ substantially from those applicable to linear models.
B Generalized Additive Models
In this appendix, we outline the different generalized additive models (GAMs) analyzed in this work. Our focus will be GAMs used for either regression or classification tasks. For simplicity, assume the GAM produces a single output: a value in E for regression tasks or a single class from {0, 1} for classification tasks. However, our results can be extended to handle multiple regression outputs or labti-label classification. Specifically, we formalize a GAM for a regression task as follows:
f(x) = 3o + (x) + (2fe(xe) + +... (xfx(xx)
where f1...., fú represent uncorrelated functions X; R, and Bo B1, 32. . B, Q denote the intercept terms obtained during a training process. For classification tasks, we define similarly:
f(x) step Bn (. B2f2(xx) +... Bxfx(xx))
(4)
where we define the step function step(z) 1 if 2 0, and step(z) = 0 otherwise.
25

---

B.1 Component-Model Types
In this subsection, we define the component-model types discussed throughout the paper: (i) spline- based components within Smooth GAMs, (ii) neural network components within neural additive models (NAMs), and (iii) boosted tree components within explainable boosting machines (EBMs).
Spline components for Smooth GAMs. Here, we define each fi as the standard piecewise spline function, corresponding each component of the GAM [51]. Specifically, the domain X; for each feature x, is divided into intervals (a1, a2), [a2, az)..... [a-- G.]. and a polynomial is defined for each interval W. For E W, we write the polynomial as g(w) a, + f1-11"" +... + 02 ag. The function fx.)) is defined over the domain X; by assigning the value of the corresponding polynomial 9 for each interval. Typically, the polynomials used in GAMs are of degree most 3 (referred to as cubic splines), which is the assumption we adopt here. We note, however, that many of our results also extend to higher-order polynomial splines. In particular, all of our hardness results remain valid in these cases, as such splines are at least as complex as cubic splines. As for the membership results, our findings for enumerable discrete settings still apply, since they rely only on the assumption that inference over each component can be performed in polynomial time- condition satisfied by splines of any degree.
We also observe that in the simple case where each fx(x,) is the identity functioo - which is trivially captured by splines as well as other models the overall GAM f(x effectively reduces to standard linear model. This linear model can either be a regressor f(x) == So + 31x1 .... + BaXK
or classification model f(x) := step(3u 81x1 + ..... + 8gxx).
Neural network components for Neural Additive Models (NAMs). We denote a neural network f. consisting of 1 hidden layers (g' where j ranges from 1 to - 1) and single output layer (g'). The layers are defined recursively each layer g( is computed by applying the activation function σ0) to the linear combination of the outputs from the previous layer أاأ=او the corresponding weight matrix WOO), and the bias vector 665), This is represented as gاوو ;= (g (g(و)) + for each j in ,,...,t. L. The model includes weight matrices (W(11, W(()), t bias vectors (6(2) (ff2),..,,65) b(t),, and activation functions (a(1)..... ((())...,,,.))))
In this neural network, the function ʃ is defined to output f = ()) The initial input layer g()) is denoted by x, which serves as the model's input. The dimensions of the biases and weight matrices are specified by the sequence of positive integers da,... dd. We specifically consider weights and biases that are rational numbers, represented as WG) E (dd5-1xd, and b(o) E Qd: which are parameters optimized during training. Since the model is binary classifier for indices 1..... n. it follows that dg (since the input of each component includes only one feature) and d, = 1. The primary activation function (()) that we consider is the ReLU activation function, defined as ReLU(z) = max(0, z².. For classification tasks, we assume the output layer includes a sigmoid function. However, since our focus is on the post-hoc interpretation of the corresponding model, we equivalently assume, in the case of classification, the existence of a step function for the final layer activation.
Boosted tree ensemble components for Explainable Boosting Machines (EBMs) In this scenario,
we assume that each individual model si (x;) is boosted tree ensemble. We begin by formalizing decision trees, followed by an extension to tree ensembles. decision tree an acyclie-directed graph that serves as a graphical model for a function (. X + R in regression and L: X - {0, 1) in classification. This graph represents the given function as follows: (i) Each internal node v is associated with unique decision rule, assumed to be of the form 2 7 or x; < r for any (ii) Every internal node has exactly two outgoing edges corresponding to the values {0, 1} assigned to v. where 1 indicates the decision rule is satisfied, and 0 indicates it is not; (iii) Each leaf node is associated with a numerical value in IR (for regression tasks) or with an associated class j E [c] (for classification tasks). Consequently, assigning a value the input uniquely determines a path from the root to a leaf in the DT.
Q
Regarding tree ensembles, each fi consists of an ensemble of kt E N decision trees (defined earlier) .1y..., las, with each tree assigned a weight Φi E Q. In regression tasks, Jú is expressed as weighted sum of the individual tree outputs: f((x.) == (xt1(xx) + dxt2(x,) + ... + Pu (x,) + do. For
26

---

classification, the prediction corresponds to the class receiving the highest weighted vote: fi(x)) == arg jl Ei= 6; [[x) = 5], where is the indicator function.
C Additional Query Formalizations
Here, we define the two remaining queries discussed throughout the paper. the Check-Sufficier Reason (CSR) and Count Completions (CC) queries, both previously studied in [16 [8]. We then
elaborate on the computational complexity of computing Shapley values, as examined in this work.
The CSR query determines whether given subset S qualifies as a sufficient reason. More formally:
Check Sufficient Reason (CSR):
Input: A model f. an instance x, and subset S. Output: Yes, S is sufficient reason of (ʃ, x), and No otherwise.
For the CC query, consider relaxed variant of the CSR query. Rather than checking whether specific subset is sufficient, measures the relative proportion of feature completions that preserve the original prediction, assuming the remaining features independently and uniformly distributed. We begin by defining the completion count for a given subset:
cS.f.x) = 1z E X33 fxx;2as) f(x)
(5)
1 E 131511
Where X5 denote the joint domain of the input features X, for all i B. The CC query is then defined as follows:
CC (Count Completions):
Input: Model f, input x, and subset of features S.
Output: The completion count fxx).
We present here more detailed formalization of the Shapley value attribution method used in the paper. The Shapley value is defined as follows:
|
|S] - -1)! (c(S v(S))
&e of.f))
Σ
(6)
n!
SCINMM
where v(S) is the value function, and
the common conditional expectation value function
vSS) = E,=D,,f(2 (z) 2s = xsl 100 76). We follow common conventions in frameworks that assessed the computational complexity of computing Shapley values [8] [102, well as practical frameworks that compute Shapley values, such as the kernelSHAP method the SHAP libary (76), and assume that each input feature is independent of all other features. In the discrete settings, every feature i E [z) assigned some probability value [0, 1). These are called product distributions in the work of [ or fully-factorized in the work of [T02. Formally, given some set of discrete values
[n] x [K] + [0, 1]. For example, p(2, 7) = ÿ. implies that the probability of feature i = 2, to be set to the value ie = 7 is g. independent distribution over iff:
[k], we can describe probability function
Then we can define Dp as an
Pr(x)
II p(i.5) :E(n])x
The uniform distribution is a special case of Dp. obtained by setting p(i) = for every i E [n]. In the continuous setting, we define a probability function p(x,) E [0, for each feature x, Under the feature independence assumption, the joint probability for the continuous input setting given by Pr(x) == [[ee(>) p(x.). Additionally, we assume that p(x:) satisfies certain basic computational propertics specifically, that the sum Σjex, p(i.j) can be computed in polynomial time (which
27

---

term poly-summability). or in the continuous case, that integration over 2 can be done in polynomial time (termed poly-enumerability). These conditions are satisfied by many common distributions, including the uniform distribution, where each input is assigned a fixed probability.
D Framework Extensions and Relationship to Previous Results
Regression, Probabilistic and Multi-Label Classification. In this segment, we discuss extensions of our framework to broader output configurations, relevant relaxations, and how these settings relate to existing works.
Our definitions can potentially be relaxed to incorporate probabilistic notions of sufficiency [104 62
105], multi-output classification, applications within bounded c-ball regions [109 61 77 In
particular, the framework could extend beyond binary classification to cover regression or probabilistic
classification. For example, in regression setting where f F + R, sufficient reason may be defined as a subset S C {l,...,n.]
n. of input features such that:
Zz E F zs) - [xx]l 5
(8)
for given 6y-norm and some d E [0, 1]. Other notions discussed in our work such as contrastive explanations and the definition of feature redundancy - can similarly be adapted to this framework. From computational complexity standpoint, transitioning to regression for these queries does not change the underlying complexity, as the problem effectively reduces to binary decision: whether the output is above or below some threshold d. Provided that is not fixed, hardness results naturally extend to cover the full domain. Likewise, membership results continue to rely on guessing witness assignments within this domain. This stands in sharp contrast to the unique SHAP query, differs significantly between regression and classification
whose behavior and thus complexity settings, as shown in our work. The same reasoning extends to multi-output classification. In terms of hardness, results established for the single-ouiput setting carry over directly. For membership results - whether they establish polynomial-time tractability or membership in higher complexity classes - it is important to note that they do not rely on the binary nature of inputs. Instead, they are based on guessing witness assignments and verifying conditions such as ((x::z) = f(x) or 2xs; # fx), which apply similarly in both single- and multi-output configurations.
The input setting impact on other ML models. In the main paper, we noted that while the input setting plays a significant role in shaping the computational complexity of explanation tasks in GAMs, prior studies on other ML models - specifically decision trees, neural networks, and tree ensembles - have not demonstrated a similar complexity separation based on the input domain. In this section, we provide a detailed justification for this claim, explaining why existing results suggest that such separations do not occur for these models. We begin with the simpler case of decision trees and tree ensembles. Intuitively, transitioning from a discrete to a continuous input domain does not alter the fundamental behavior of these models, they compute piecewise constant functions (or an ensemble of such functions) and their split rules do not depend on specific input configurations. More concretely, prior work has shown that the complexity results for sufficient and contrastive explanations extend to continuous domains (see, e.g.,(54)), and similar extensions hold for counting- based explanations such as SHAP (e.g..115)) Lastly, since tree ensembles are simply aggregations of l decision trees, the same proofs naturally extend to them as well.
In the context of neural networks, hardness results are already established even for Boolean input settings - this holds for the CSR, MCR, MSR, and CC queries [16), the FR query [8] and the SHAP query [102]. These results directly imply hardness in the enumerable discrete setting and, by extension, in the general discrete setting as well. Furthermore, (95] (building on (691) demonstrated that satisfiability instances over binary inputs can be reduced to continuous input cases by introducing additional activation gadgets. This reduction, in turn, implics that the same hardness results hold for all these queries in the continuous setting.
Regarding membership results, prior work has already established that these results hold for binary inputs [6, 18 [02). The same membership arguments - typically based on guessing a witness assignment - extend naturally to enumerable and general discrete domains, where the guess involves q-bit vector instead of a binary input. Additionally, [55 demonstrate that verifying satisfiability queries for MIPs with ReLU activations over continuous inputs is in NP. The key idea is to guess the activation pattern of each ReLU and then solve a corresponding linear program, which is solvable in
28

---

polynomial time. The CSR query (with S = () effectively negates satisfiability query, implying that CSR remains coNP-complete for continuous MLPs. Recall that the MSR query for MLPs is known to be X. -complete [16], due to its use of a coNP oracle to check whether subset is sufficient (i.e., solving the CSR query). Since CSR extends continuous domains, the same reasoning carries over to MSR. Similar logic applies to the CC and SHAP queries, which are counting analogues of these reductions [66] [02 7l. Altogether, these results underscore that for neural networks, the complexity class of each query remains stable across input domains, unlike the distinct separations seen in GAMs.
E Proof of Proposition I
Proposition 1. Given any GAM over an enumerable discrete domain, or a Smooth GAM over discrete or continuous domain, the CSR, MCR, and MSR queries are solvable in polynomial time.
Proof. To start, present the polynomial-time algorithms applicable to the enumerable discrete setting, which hold for any GAM. We then extend our discussion to Smooth GAMs over general discrete and continuous domains.
We divide the proof for the three explainability queries - CSR, MCR, and MSR - for GAMs enumerable discrete settings into three separate lemmas, each establishing the corresponding complexity result. We note that the proofs across all these settings follow a similar structure to those used for linear models [16 99 78), with the main distinction being the need to account for the dependency on computing the minimum and maximum values of each component model fi(x;) to resolve the query.
Lemma 1. The CSR query can be solved a GAM I over an enumerable discrete input space in polynomial time.
Proof. Let there be some instance (ʃ, x, S) where f is a GAM. We note that given some feature can evaluate its maximum negative affect (which will call, similarly to [16], its "penalty" by fixing it to the (negative) affecting edge of the domain X. Formally, we define:
Pr = [min [3 f((x)) X; E X.} if f(x)> >
(9)
max (3, f(x:) X; X3} otherwise
Since the values Xr are enumerable discrete, both min f((x;) x; E X:} as well as max [3: fx(x;) x; }. can be determined in polynomial time by simply iterating over any possible value of x, We can then compute all possible p; values in polynomial time. We can then simply check whether:
sign Σ B fi(x,)+ + Σ Dr2+ Bb) sign( Σ f. + Bb) 20 SES
(10)
JES
SEn
We recall that (Eien 8 fx(,) )+ + 30) represents the value of the input x when passed through f (prior to the step function), and (Eres B3 fx()) + Ejes Py + S0) denotes the value for the input vector zs); where this value is maximally distant from the value of x when passed through for all z E F (again, prior to the step function). Consequently, the signs of both sums align if and only if both are either positive or negative. This means the sign of the prediction f(x) before the step function matches the sign of fxx;; 7s) before the step function. Since (xs; z.) 3 represents the vector whose value through f achieves the maximal distance from x when passed through f (before the step function), the following equality holds if and only if, for any possible z' E F. the predictions of over x and (xs; z'z)) are both positive (or both negative) before the step function. Therefore, after applying the step function, it holds that Vz E F, fx)) = fxs:: 4g)) which holds by definition if and only if S is sufficient reason concerning (f.x).
Lemma 2. The MCR query can be solved for a GAM I over an enumerable discrete input space in polynomial time.
Proof. Given an instance (ʃ, x, k), we use the same definition as in Lemma T of ps to denote the "penalty" of each feature i in the GAM. We perform the following algorithm (Alg D. which computes
29

---

a cardinally minimal contrastive reason. We assume, without loss of generality, that f(x) = 1. The alternate case, where f(x) can be addressed similarly by reversing Line which will accordingly reverse the steps in the proof.
Algorithm 1 Cardinally Minimal Contrastive Reason Search
Input f.x
1: Compute all values for every i E [n]]
2: F f (I......m
Features for iteration
3: O
> The current sufficient reason
4: Sort in descending order by the value of 02 := B.,xx - P; for each
5: for each E F do
6:
if signn Eies Br [i(x;) Ejes Ps + (6) sign(Eien Br (x(,)) + 30) < then
7:
Break end if
8:
9: S S
10:
end for
11:
return
D S is cardinally minimal contrastive reason
We note that the computations of all values (Line in Algorithm D can be computed in polynomial time due to our assumption of an enumerable discrete input space. The discrete input space means that for any x; we can simply iterate over the entire domain X, in polynomial time and hence obtain both min ( fx;;) x; E X as well as max fx(x)) x; &). Hence, it is clear that the algorithm runs in polynomial time.
To establish the correctness of our Lemma, it remains demonstrate the validity of the algorithm: Lemma 3. Algorithm 7 obtains a cardinally minimal contrastive reason for (f.x).
Proof. We will first prove that algorithm | produces valid contrastive reason for (J, In Lemma we established that if the inequality sign (Eres Be f((x,) + Ejes Pj + 30)
sign (Eren ((x.) + Bo) 2 O holds, then S serves as sufficient reason for (J.x). Simi- larly, if the relation sign EEes 8: f((x,) + Ejes Pj + Ba) sign (Eien Bi f(((x) + 8)) 2 0 holds, then 5 is sufficient reason, which implies by definition that S is not contrastive reason. Therefore, the following equivalence holds: if and only if sign EEeS B: fx(()) + Ejes + 80)
sign (Eien 3 fix..) + (6) < O, then S is contrastive reason with respect to (f.x). We will now demonstrate that the generated
S is cardinally minimal contrastive reason with respect to x). Let 1 < l S n represent the last feature added to S in line 10 of algo- Then, for 5" = $ \ {f), it follows that: sign (Ees B; fx(x) + EjES' Pj + Bo)
rithm
sign
ViEn 8 (x,,) + 9b)) 2 0, implying that S' is not a contrastive reason for (f,x).
Recall that was sorted descending order according to the values v; == 3, fi (x:) ps, and S" therefore represents the subset of size [5"| that maximizes Ejes (B) fx((,) Pj) and hence also maximizes the difference
Σ B: f((x,) + Bb) SEA
Σ (x(x) $e
+ Σ JES'
PS + +)) Σ (gg (x,,)) p.))
(11)
jES
This implies that any subset S"
C [n] of size 18"|
>
S satisfies:
sign (Eess B. fx(x)) + EjES' Pj + 30) sign (Eeen B. fx(x;) + 30)
0. indicating
that S" is not contrastive reason for (f. x). Overall, we have shown that S is a contrastive reason for xf.x), and that any subset S" of size SS"| 2 |S"| is not contrastive reason for (f. x). By
definition, |S'| = [S] - 1, so we have established that there is no subset of size [S] - or smaller that is contrastive reason for (ʃ, x). This confirms that S is cardinally minimal contrastive reason for (f, x).
30

---

Having established that algorithm I produces a cardinally minimal contrastive reason for S, solving the MCR query polynomial time simply requires running the algorithm and verifying if [|| 2 thereby completing our proof.
L
Lemma 4. The MSR query can be solved for GAM f over enumerable discrete input space in polynomial time.
Proof. Given an instance (f.x, k). we will show that the MSR query can be resolved polynomial time. For a specific feature i, we will again (as in Lemmal I refer to its "penalty" as the maximum negative impact it can exert on the prediction fxx). Formally, we define p; == m f.(x)) X; fx(x;) 33 E Xr} otherwise. Furthermore, we require measure for the value of feature when it fixed. We define e := 3 f((x)) Pt- Note that when Eiein] 3; fi fx(x) + S0 < 0, i.e. when f(x) = 0, "good score" will be highly negative one. Thus, specifically define t; (Be (x;) pt) sign ( Diew ma] B: fx,)) 8o). However, for simplicity, we will assume without loss of generality that f(x) > O, and therefore v; == 3: fi(x.) - p:- Intuitively, v; reflects the value of feature i when it is held constant rather than allowed to take any value, thereby influencing the penalty score p;. With these definitions, we are prepared to propose the following algorithm for obtaining cardinally minimal sufficient reason for the given instance (f, x).
X if f(x
O, and P; max
Algorithm 2 Cardinally Minimal Sufficient Reason Search
Input f.x
1: Compute all values u; Pe for every i [n]
2: F P=< (1,.....,77
Features for iteration
3: S+0
>> The current sufficient reason
4: Sort F' in descending order by the value of U; == Bi fx(x)) pp for each
5: for each E F' do
6: if sign(E 3, fi(x,) + Es + Bo) sign(E B: f((x,) + (b) 2 0then
7:
Break
8:
end
9:
S 5 S-SU [S}
10:
end for
S is cardinally minimal sufficient reason Lemma 5. Algorithm obtains a cardinally minimal sufficient reason for (f,x).
11:
return S
Proof. First let us prove that Algorithm 2 provides valid sufficient reason. This result is straight- forward since we have proven in Lemma that S is a sufficient reason of (f, x) iff the condition sign (e 3: fx(,,) Ejes + Po) sign(E 3x fx,)) + 30) 2 0 holds.
We will now demonstrate that the generated S a cardinally minimal sufficient reason with respect to (f,x), Let 1 < l S n represent the last feature added to S in line of algorithm [ Then, for S :=
S {f), it follows that: sign Eie 3r f((,)) + EjES' Pj + 3o) -sign (Eien Bg fx(x) + 30) <
0, implying that S' not a sufficient reason for (f.x).
Recall that F' was sorted according to the values := 3, fx() - pt in descending order, and S' therefore represents the subset of size |S'| that maximizes Ejes (3g [x(x) - Py) and hence S represent the subsets that minimizes the difference Ejes' (8) (x,) Pj). This is equivalent to stating that S' represents the set of size SS' that minimizes:
Σ B: f((x))) + Σ Ps 30) RES
B, f((x)) + B0) iE
Σ [(3 (8 -p,) (12)
JES
JES'
This implies that any subset S" [n] for which |S"| < SS and hence also S"
S satisfies:
sign (EEEo B, [xxx)) Ejes' Pj Bo) sign (Eien B f((x:) (8) 0. indicating that S
contrastive reason for (f, x), and hence that S" is not sufficient reason for (f.x). Overall,
31

---

have shown that S' is a sufficient reason for (f.x), and that any subset S" of size |S"| < |S") is not sufficient reason for (f.x): x). By definition, |S"| |
|S| - 1, so we have established that there is no subset of size |S| 1 or smaller that is sufficient reason for (f, x). This confirms that S is cardinally minimal sufficient reason for (f.x).
C
Having established that algorithm produces a cardinally minimal sufficient reason for S, solving the MSR query in polynomial time simply requires running the algorithm and verifying [S] 2 k. thereby completing our proof.
Having established the complexity results for the three explanation types in the enumerable discrete input setting, we now our attention the general discrete continuous input setting, focusing on the case of Smooth GAMs. In fact, we will show that this claim holds for a broader class model families, including other tractable components like decision trees:
Lemma 6. Given Smooth GAM over general discrete continuous input setting then the CSR, MCR and MSR queries can be obtained in polynomial time.
Proof. We have established in Lemma [ Lemma 2
and Lemma that, assuming the minimum and maximum viable values for each model component fi can be determined within the domain X; the CSR, MSR, and MCR queries can be computed in polynomial time. We will now demonstrate this for each corresponding component model.
First, consider the case where each fi is the identity function (i.e., f is linear model). In this case, determining the minimum and maximum values each domain is straightforward and can be done in polynomial time. For cubic splines, this result extends naturally, it involves iterating over each defined region of the piecewise polynomial ft- For each region, we evaluate the value of fi at the domain edges and at the extreme points, which can be found by solving a polynomial equation of degree (achievable in polynomial time). Among these values (edges and polynomial extremes), the minimum and maximum are selected. If X; is general discrete set, we iterate over the continuous region representing X, find the extreme points as before, and for each extreme point, identify the two nearest discrete points within X, - one above and one below. From this set of viable extreme points of the discrete domain Xg we then select the minimum and maximum values.
We note that this proof applies not only to Smooth GAMs but to any model where the minimum and maximum attainable values of each fa can be computed in polynomial time. This includes, for example, decision trees. In the case where fa is decision tree, iterate over all leaf edges (representing all viable values of f.) and select the minimum and maximum values from these leaves. This process can also be completed in polynomial time with respect the size of the tree.
F Proof of Proposition] 2
Proposition Given a Smooth GAM f over continuous input space, then the FR query can be obtained in polynomial time.
Proof. We will prove this for more general class that includes any GAM f defined over continuous inputs, where the output fxx is continuous, and for which both min (f) and m (i)) can be computed in polynomial time for any feature The polynomial
computation of m and max ff } for splines has been proven in Lemma I Furthermore, since splines are defined as piecewise polynomials, it is clear that f(x a continuous function. Therefore, proving the complexity results for the FR query for this family of classifiers will also encompass GAMs defined over splines.
We first note that by definition a feature is redundant with respect to f if and only if for any x', X., Z; holds that fx (3 x;) = fxx( (s 2,) (or in other words, changing the value of feature cannot cause the classification to change. We will prove the following claim:
Lemma 7. Let there be some GAM f where both the input domain X is continuous, and the output fxx is continuous. Let assume that is redundant with respect to (f)) and that f is not trivial (in
32

---

other words. a function that always outputs 1 or always outputs 0). Then, it holds that for all x; E X, (x,(
Proof. First we recall that by definition i redundant with respect to f iff for any x', X,, it holds
that fxx (oMaa) = /ux x:). In other words, this implies that:
[100 + (x)((xx) +.... 3 (x: (x:-1) + B ( + + (aJn((x) 2 0jΛ
'180 + 31 (xi) + +... fx((x) ) 2 O]]
(13)
VIl + (1f((x)) +... +---11-- (x:- + 1 + (xx)x(x)) < <0jA
1100 + B1 (xi) +... (a(x)) < <O]]
Let us assume for contradiction that for any x, the term Bg +.. 16-1fi B141fi+1 (x.()) + +.. +
+
f&fxx(X) is always strictly positive or always strictly negative. Since i is
redundant, follows that adding the term (x,, to the rest of the sum cannot cause the classification to "flip." meaning the overall term cannot change from positive to negative or vice versa. This implies that the entire sum 90 + (x1) +... + Bs fa (xxx) for any is always positive or always negative, which contradicts the assumption that f is non-trivial. Therefore, there must necessarily exist some x, z E X' such that 30 f (x1) + ... 1 (x, + f +... + B&fA (x₂) is positive, and 3o (1)i(z)) + .... + 8i-18--11111 (z, + fi+1fi+1 + Bu.f(Zz) is negative (or vice versa).
Moreover, since X is continuous, we can select and z such that Bu + (1f1(x1) + +... 84-1f--
B:+1f++1 ( + + f&fa (xx) and Bo + f1 (z1) +... -(-1f(-1((()) (1-ff+1(22,+)) + .... fafx are infinitesimally close to the decision boundary. We will denote these points as either 0+ or representing an infinitesimally close value that is either above or below O. Now, assuming there exists some X such that B: fx(()) is negative, we can take an infinitesimally small value for 30 + fi + .... .....7 Bi 1f (x;-1) 8
+... fi above the decision boundary (0+) such that adding 3.5. (x,) causes the decision to become negative. The analogous condition holds for the opposite direction of the decision boundary (assuming there exists some X for which (x(() is strictly negative). Consequently, the only way for i to be redundant is if, for every x E X,, it holds that (xx) = 0, thereby concluding the proof of the lemma.
C
We will now use the previous Lemma to describe simple volynomial-time algorithm for solving this task. The algorithm iterates over all features i from 1 to n. Since fi is a spline, we can compute the minimal and maximal values fx, and (xx, in polynomial time. If either both terms are equal to 0 or 3, = O, we return that is redundant. Otherwise, we return that it is not. The correctness follows from the correctness of Lemma 7 the continuity of X, and the continuity of (x) (a result of working with splines). This concludes the proof.
G Proof of Proposition 2
Proposition Given any regression GAM with enumerable discrete inputs, or given a regression Smooth GAM with discrete or continuous inputs, then SHAP query is solvable in polynomial time.
Proof. We divide the proof into three separate lemmas. First, we establish the claim for general GAMs under the enumerable discrete setting. Next, we address Smooth GAMs over general discrete domains. Finally, we prove the claim for Smooth GAMs over continuous domains.
Lemma 8. Assuming is a regression GAM over an enumerable discrete imput space F, then solving SHAP for (f,x, i) can be solved in polynomial time.
Proof. For a certain value function e(S), given the assumption of feature independence and the additive structure of f. we have:
33

---

e(S) BeND,11(2 zs xsl
1Bng (Xs:
Er (
E
II
p(e,j)
MEP
(14)
E E p(e,)))
(xfe(xe) +
Σ
Bef;(Z;) +0)
ZEF BE(n]
EES
jE8
Σ
(efe(xe) Σ
BAND, [3,f +
EES jES
Now, have that:
(1)
Σ (efe(x)) + E
E EaD 1x,,(,1,[(22]]]1 +80)
RE RESU(()
}E8((}
Σ Befe(xe) Σ EzND,
[3,f 1, (6)=
(15)
EES
jEB
Bef((x,) E (8 (x(f((x:) 18 (,
By incorporating it into the SHAP formulation, we obtain:
| |S| 1)!
o.([x)=
Σ
(u(SU(i))
n!
|
|S|
1)!
(Bif((x)) 1xN,,1&tf(xx]]]]]
(16)
n!!
SCNNM
B: (fi(x))) (f.,,() n
where the last equation follows from the fact that the inner product does not depend on S, and from the well-known result that the sum of the Shapley values, Esgm))(3 [91(0=11 simplifies to 1 through a telescoping sum. By definition, fx;;) can be computed in polynomial time. Furthermore, since the domain X; is enumerable discrete, Ez-D,, (fa()) can also be computed in polynomial time by evaluating Σjex; (i,,)) (where the equivalence holds again by utilizing the feature independence property), thereby completing the proof.
Lemma Given a GAM I over a general discrete input space, obtaining the SHAP query for regression can be solved in polynomial time.
Proof. We note that until our last step proving tractability for the enumerable discrete setting in Lemma & which involved showing that Ez-D, (f(z))) can be computed in polynomial time (by evaluating Σjex, p(i,)))((z,)) this point also apply to the general discrete case. In the general setting, correctness follows directly from the polyssummability property of the distribution D,. thereby establishing tractability.
we did not assume explicit enumerability. Thus, all results up to
C
Lemma 10. Given a GAM I over a continuous input space with poly-integrable components, obtaining the SHAP for regression can be solved in polynomial time.
Proof. The proof will be similar to the discrete scenario. For a certain value function v(S), given the assumption of feature independence and the additive structure of f. we have:
34

---

e(5) (f zs xs}
Big [fs:
BEND (Xs:
| -
JEE
(17)
/ (p(z) (efe((Xe) Σ (ef)(Zz) + (0))
FES
jES
Σ Befe(x)) + Σ
E [3,f
EES
jES
Now, the following condition holds:
(1)) v(S)
Σ Befe(x:) +
E (, +
FE RESU(()
JES((H)
Σ Befe(xe) Σ EEDD, (3,ff(z)) + -b0)
(18)
ES
jEB
Bef((x:) 1,
Bx(f((x;) Ey (fi(z;))
Incorporating it into the SHAP formulation yields:
Σ | |S| 1)!
x((fx)==
(u(S ((S))
|
|S| 1)!
(Bif((x)) (Bxf(x))
(19)
n!!
SCAIM
B1 (fi(x)) (f.,,(( n
The final equality follows from the fact that the inner product is independent of S, along with the well-known identity that the of Shapley coefficients, Esgmjy 1811(2-188-12 evaluates via a telescoping argument. By definition, (x;) computable polynomial time. Thus, the question of whether the SHAP value is polynomial-time computable reduces to whether (fiz)) can be computed in polynomial time. Under the feature independence assumption, we observe that:
x!
(f(2)) =
p(z)f((z:) = J
(z(z.)
(20)
NEX;
Since f((2,) is a smooth function bounded by degree 3, and p(z,) is poly-integrable, follows by definition that (f(zz, can be computed in polynomial time by evaluating the integral S.ex, (z.)) This completes the proof.
H Proof of Proposition
Proposition 4. Given any unary-encoded GAM over discrete, enumerable input domain with poly- nomially bounded output, the CC and SHAP-C queries admit a pseudo-polynomial-in algorithm.
We will divide the proof into two lemmas, addressing the CC and SHAP queries separately, beginning with the CC case.
35

---

Lemma 11. Given any unary-encoded GAM over a discrete, enumerable input domain with polyno- mially bounded outpu,, the CC query admits a pseudo-polynomine polynomial time algorithu.
Proof. We prove this by reducing the CC problem when weights are provided in unary to variant of the counting version of the classic #Knapsack problem, which we refer to as #Mulii-Choice Knapsack. We then show that #Multi- algorithm. Our proof follows a similar structure to that of [[6], who addressed linear models over binary domains, but introduces additional complexity to handle arbitrary enumerable discrete input configurations. In particular, whereas the proof [66] addresses this problem via a reduction to #Knapsack, approach reduces it to the #Multi-Choice Knapsack setting.
Knapsack can be solved via a dynamic programming
# #Multi-Choice Knapsack:
Input: w == (Wi..... W,) where each wi is a non-negative integer weight, a vector of sets (Si,..., ,n, where each set St contains fixed number of associated integers, and a target integer C which denotes the capacity.
Output: (x.) S1 x... S.. Eign WiT; S &CH
We observe that this problem resembles the classic # #Knapsack problem the counting variant of Knapsack- - except that each variable x; ranges over a set St of enumerable integers, rather than being restricted to {0, 1}. This range of possible values corresponds to the outputs of the GAM. Since we assume that the GAM uses an enumerably discrete unary input encoding and that its outputs are polynomially bounded, it follows that the set of possible outputs is itself polynomially bounded with respect to the input encoding (and therefore also unary). The work of [6] reduces the CC query for Perceptrons (i.e., linear models over binary inputs with unary weights) to the classic # *Knapsack problem via a polynomial-time reduction, where C' is set to the bias b of the linear model. We observe that applying the same reduction except replacing binary inputs with sets of enumerable discrete values representing the enumerable set of unary-encoded possible outputs of the GAM yields an instance of the #Multi- Chiiice Knapsack problem instead (and the target integer C equals the intercept 90 of the GAM instead of the bias b of the linear model). Thus, it remains to show that #Multii Choice Knapsack is solvable in weuuo-polynomial time, which we do by adapting the standard dynamic programming algorithm typically used for this problem (and also discussed in (16).
The algorithm will be constructed as follows: given an instance of #Multi-Choice Knapsack which includes w = wa), (Si,.... S,), and C, we can define the following quantity:
DP[[[C] = [( xn) E S x x...X x S. Σ w. S CH
(21)
The final result for the #Multi- Knapsack (and consequently for the CC query) is given by the value of DP[n][6.. This can be computed using an iterative dynamic programming approach based on the following inductive step:
DP 1][[] DP + Σ DP s]
(22)
sinS
We carry out this iterative computation starting from the standard dynamic programming base case (as in the classic Knapsack and #K #Knapsack algorithms, and also noted in [16): DP [ = 0 for all a < and [P 1 for all 2 Given the pseudo-polynomia. nature of the problem, a polynomial number of iterations suffices to compute the final value D [b], which yields the solution to the MMulii-Choice Knapsack and, consequently, the answer to the CC query in this setting.
C
Lemma 12. Given any unary-encoded GAM over a discrete, enumerable input domain with polyno- mially bounded output, the SHAP query admits sseudo-polynomite
algorithm.
Proof. We build on the proof introduced by [102] which showed that the computation of SHAP for a model and some input can be reduced to the computation of Ez-D, (f)) in polynomial time, given that we assume feature independence. Hence, are only left to prove that Ez-D, (f()) can
36

---

be obtained in pseudo-pol polynomial time for GAMs over enumerable discrete input spaces. We note that the following holds:
Ex [[(x] = D 81 (i(z)) + +.... [n(()))
(23)
Since we assume that the input space X' is enumerable discrete, computing De (f reduces to counting the number of assignments (21,...,,Tx) S1 X x... x Sn such that 60 + 81 f((Z))
Bn ...+ f (zn) 2 0. This equivalent to counting assignments where -i=1" f( 2 Bg.
Setting the threshold C' == So. the problem becomes an instance of the #Multi- problem described in Lemma H As shown in that lemma, this problem can be solved in pseudo- polynomial time via dynamic programming approach. Therefore, the SHAP query for classification over GAMs with enumerable discrete input domains is also solvable pseudo-polynomial time.
#Multi-Choice Choice Knapsack
I Proof of Proposition 5
Proposition 5. Let there be NAM EBM over discrete contentious input space, then solving the CSR, and MSR queries are coNP Complee,, and the MCR query is NP-Complete.
Proof. We will divide the proof into several lemmas, beginning with NAMs and then proceeding to EBMs. For each model, will first establish the results for CSR, followed by MCR, and finally the MSR query. We will also start with continuous domains and then explain how to extend the results to general discrete domains each case.
Lemma 13. Given a NAM f, an input x E FF and an integer E N, where f is defined over either continuous input space general discrete input space, then obtaining the CSR query is coNP- Complee.
Proof. Membership. the general discrete setting, the proof is straightforward. One can guess a set of assignments corresponding to the features S. This is feasible because the domain of each feature i, denoted X, is defined by minimum and maximum value, each represented with at most bits. Moreover, any value in the domain can also be expressed with at most q bits. Therefore, any value for a feature in S be determined by guessing the bit values for each feature representation. Denote the guessed values for S zg, and select arbitrary assignments for the features in S (chosen from their respective domains).
This allows to construct vector z that includes both the guessed values for 3 and the arbitrarily chosen values for S. We then verify whether (g)) * fxx), which can be done in polynomial time. If this condition holds, it implies that not a sufficient reason for (S, x). thereby establishing membership in coNP.
In the continuous setting, the situation becomes more intricate, as guessing a witness assignment for the input is not feasible. This is because the size of the encoding is no longer polynomial and may even be finite. However, as shown in a similar proof from (96), for neural network with ReLU activations, one can, instead of guessing the input assignment, guess the activation status of each neuron (either active or inactive).
Once the activation status of each neuron is established, and assuming all remaining constraints are linear, finding satisfying assignment for the neural network reduces to solving linear programming problem. In our case, this indeed holds, since it involves setting lower and upper bounds for each input (corresponding to the minimum and maximum permissible values X; for each feature i E S) and equality constraints for features in S. For the output constraint, we impose a condition that either greater or less than zero, depending on the opposite of the classification result for f (x). this linear program yields feasible solution, it demonstrates that f fxs; z + fx), hence proving membership in coNP.
We begin by establishing hardness through the (complementary of) the neural network verification problem, which has been examined in [69] and [96), among numerous other studies. This problem, known be NP-Complete [69] (66, is formalized as follows:
Hardness.
37

---

Neural Network Verification:
Input: A neural network f : TR - IR. bounded continuous domain X' over the input space, and a bounded continuous domain )' over the output space.
Output: Yes, if there exists some x E X' and some y E y such that f(x) = y. and No otherwise
We will prove hardness by reducing from the (complementry of) the Neural Network verification problem, which is known to be NP-Complete [69 166. We note that while the authors in both [69 and [96] descrihe this as a more general problem for wny piec-wise linear specification over the input and output (and not only for bounded domains), in practice the hardness result that were proven from the classic SA7 problem were performed for specificacations of this form (bounding both the input and the outputs). Hence, the NP-Hardness of these problems holds from these reductions. Moreover, as noted by [96]- - hardness remains for neural networks consisting of a single output neuron, and hence we can assume that our neural network is actually of the form f R + R.
We will begin by establishing an intermediate proof for our claim, which is even a stronger one that was obtained by [96). Particularly, will prove that the neural network verification problem remains NP-Hard even for a model with both a single input and a single output. We will later demonstrate why this hardness result also applies to the general discrete input setting.
Lemma 14. Given neural network IR + R, bounded continuous input domain X, and bounded continuous output domain y, then solving the neural network verification problem over f is NP-Hard.
We will begin by establishing hardness for the continuous domain and then demonstrate why these results extend the general discrete domain. Now, let there be a neural network f : Rd -> with a bounded continuous input domain X, and bounded continuous output domain V First, we will show how to reduce I' into a model f": RR - R, with some continuous bounded domain 2" over the (individual) input of f' and the same output domain V for which it holds that there exists some x E y E y for which f(x) = y if and only if there also exists some E X" for which f'(x') = y.
We first note that given some value o, that is obtained by some arbitraty neuron in an MLP, it possible to construct the calculation of 0j == loi| in the preceding layers by incorporating the following procedure:
0j = Re:LU(a)) + (-1 Rel.U(- = los|
(24)
which can be computed by simply adding two additional neurons in the preceding layers with 1 and -1 weight and connecting them both to another preceding layer. We hence, will consider, for simplicity that for any o,, 0ソ := lo,| can be computed by a constant number of preceding layers. We also note that given some o we can simply compute:
oj ReLLU(o:) + ReLU(-o:) =
(25)
meaning that single value of a neuron can be passed to the subsequent layers with a simple identity transformation with that construction. We will hence regard the identity construction as a valid one as well. Lastly we regard the following construction:
0j = (o. - -1= = max 0)
(26)
We observe that, as previously mentioned, the proof in [6] was derived from the CNF-SAT problem.
initially assuming the input space X' := {0, 1)" Consequently, we will specifically demonstrate hardness for the neural network verification problem involving a model of the form f R + R by reducing from the neural network verification problem over a model of the form f (0,
Furthermore, we observe that the input domain required for our model f is a bounded continuous domain X, defined by minimum and maximum values represented in binary. For simplicity and clarity, we demonstrate how to reduce a model f, defined over the domain X' := [o, 2n 1). to the domain {0, 1)". This reduction is achieved through a binary search construction over [0, 2 and can be generalized to any bounded continuous domain X, where the minimum value of X corresponds to 0 and the maximum value corresponds to 2n
38

---

Reducing the continuous domain [0, 2" 1] for an individual feature to the discrete domain {0, 1) for n features. The construction of f is as follows. Following the first input neuron o" we will connect it to a neuron in the preceding layers which calculates: og == ReI.U(oD - 2n-1) 1) and of := (eo)) - (e 22-1)). We connect of to the first neuron from layer of via linear transformation, i.e., of == of. We also set 0f og ReL.U(t))
We now move on and construct another hidden layer over which we compute of := ReLU - and of : (o}) ReLU(o} 2) We connect of to the second neuron in the of layer via a linear transformation, i.e., we compute dg == =o. We then again set o3 := ob ReLU and of := Ro - 2 and continue performing this entire process recursively, i... for the i'th iteration in this process we construct oj := ReLU(o) 2"-1), of == ReLU(()) - ReLU 2 ").0) == dg ReLU(o)) and connect imput in the of layer of via línear transformation, i.c.. d' oj.
The following construction takes some arbitrary assignment og in the range [0] and performs set of binary decisions, each time decreasing 2 and continuing with the remainder. This process hence gives us in the first neuron of positive value iff on is larger than 2n-1, and otherwise will be assigned a O. The second neuron oe will get a positive value iff the remainder after decreasing 2n- is larger than 0, and otherwise will be set to 0. The third neuron og will get a positive value iff the remainder of what is left, while decreasing 2n- from it is larger than 0, and otherwise. it will be assigned 0. This continues for every i. It is straightforward
show that for a value of = |æ]] for some 0 2 x 2 2" it holds that we can equivalentley describe o' as binary vector of size n which is equivalent to the binary value of z, where each "1" value in place in the binary vector corresponds to some positive assignment in place i in the vector o', and each "0" value in place in the binary vector corresponds to some assignment in the of vector.
We now will describe an additional transformation over o' that we do befor connecting it to get o" which we will connect to the first hidden layer of the original one in I (and hence to the preceding layers in f as well). First, let us observe that for the following construction:
2 ReLU(( - x>) + ReLU(x - 1)
(27)
it holds that if 0 S x then = 1. We hence can define the additional hidden layer o" which comes after of such that for each of we define:
of == ReLU(11
o 0 + ReI.U( of - 1) 2n
1
(28)
2
Since the range of the original individual input of f': 0 is in [0, 2n), then we have that each remainder that is propagated into the of layer is also in the range [0.2"]. We hence get that for any positive instance that was propagated into o' (and represents its corresponding binary vector) its output will be equal to exactly 1 in o".
We connect layer o" to the remaining hidden layers from the original f. We note that the continuous domain [0, 2n] over the single input neuron in dº in f is mapped exactly to any possible binary vector {0. 1)" in layer o". The preceding layers after o" are identical between f and f' and hence we have that:
maxx)((02--11)
ma. and minx min minnc((..)-f(a))) (29)
We connect layer o" to the remaining hidden layers from the original f- We note that the continuous domain [0, [0,2"] over the single input neuron in o in ff is mapped exactly to any possible binary vector {0, 13mh in layer o". The preceding layers after o" are identical between ff and f'. Thus, for any x E [0, 2n.1_, we can consider the binary representation of the lower value within the range that maps to {o, 1) (denoted as x'), satisfying f'(x') = fxx. This demonstrates more specifically that there exists X X,y E y such that f(x) = y and only if there exists some x' X {0, 1)" for This hence concludes the proof of our Lemma.
which (x) = f(xx)
Extending the proof to the general diserete setting. We observe that the construction we developed for f' relies on performing binary search over the features within [0, 2n-1), mapping them into
39

---

the discrete input space 0, 1" by associating each value with its corresponding lower value in the binary domain. If we consider the domain X' := [0. 2= to consist solely of discrete binary values represented with n bits, the mapping functions identically. In this case, instead of assigning lower value for each mapping, the values are mapped exactly. Consequently, it straightforward to conclude that the hardness proof remains valid when X' is assumed to be general discrete.
Finalizing the proof. We have established that the neural network verification problem for a neural network with one input and one output, where the input domain is either continuous or general discrete, is NP-Hard. We now aim to leverage this hardness result to demonstrate that the CSR query for a NAM defined over either a general discrete or continuous domain is corP-Hard. We observe that the hardness proof we derived applies to a specific scenario which the output specification ) mandates that the prediction of f(x) must be positive (i.e., fxx 2 0). Consequently, we will demonstrate hardness by reducing such an instance - a neural network with a single input and output, a bounded input domain X, where the task is to determine whether f (xx 2 0 - to the (complement of) the CSR query.
Given a model f and an input specification X', we construct a NAM f' consisting of only one MLP, fi : f. We start by selecting an arbitrary assignment x E X and checking if f(x) < 0. If this condition is satisfied, we define the weight of the corresponding model as 31 == 1 and set the bias term as 3g == 0. Furthermore, we initialize the subset := 0. It easy to see that if there exists a satisfying assignment z E X' for which f(z) 2 0, then [n] == {1} is contrastive reason, since and thus 0 is not a sufficient reason for (f''
1 = (z) * f'(x)
.)). In summary, we have constructed an instance of the CSR query where S (the empty set) acts as sufficient reason for xf",)) if and only if no satisfying assignment exists for the neural network f.
For the second case, where fx) 2 O, we construct f' in the same way, but this time setting the weight 31 =- 1, while keeping B0 0 and S == 0. Similarly, we observe that if there exists satisfying assignment z E X' such that f(z) 2 0, then [n]] == {1} serves as a contrastive reason, as 0 0= fz) + f'(x)= 1, implying that 0 is not sufficient reason for (J", x)). To summarize, we have constructed a CSR query instance where S (the empty set) serves as sufficient reason for (f', if and only if no satisfying assignment exists for the neural network f.
This establishes that obtaining the CSR query for a NAM, where X' is defined as either a general discrete continuous input domain, is coNP-Hard.
Lemma 15. Given a NAM f, an input x E F, and an integer l E N. where f is defined over either a continuous inpul space or a general discrete input space, then the MCR query is NP-Complete.
Proof. Membership. For proving membership in NP, follow the exact same procedure used for proving membership in coNP for the CSR query in Lemma [3 However, instead of verifying that f(x) * [xx;; we check that [xx = [xx;; while introducing additional constraint that |S| < k. Since these conditions can still be determined in polynomial time (with the difference being
that we now demonstrate the existence of an instance, rather than the lack of one), this establishes membership in NP.
Hardness. We have proven in Lemma 14 that the neural network verification problem for neural network with one input and one output, where the input domain is either continuous or general discrete, is NP-Hard. We now aim to leverage this hardness result to demonstrate that the MCR query for a NAM defined over either a general discrete or a continuous domain is NP-Hard.
We observe that the hardness proof we derived applies to a specific scenario in which the output specification y' mandates that the prediction of fx) must be positive (i.c., fx) 2 0). Consequently, we will demonstrate hardness by reducing such an instance- a neural network with single input and output, a bounded input domain X. where the task is to determine whether f(x) 2 0 to the MCR query.
Given a model f and an input specification X, we construct a NAM f' consisting of only one MLP, fi := f. We start by selecting an arbitrary assignment x E X' and checking if fx) < 0. If this condition is satisfied, we define the weight of the corresponding model as 31 == and set the bias term as 30 : O. Furthermore, we set k := 1. It is easy to see that if there exists satisfying assignment
z E X' for which f(z) 2 O, then [m] == (1) a contrastive reason, since 1 = f'(z) # J' (x) = 0 and
thus there exists contrastive reason of size 1 for (f', x).
40

---

For the second case, where f(x) 2 0, we construct f in the same way, but this time setting the weight 31 == 1. while keeping 5o == and, again, setting k := 1. Similarly, we observe that there exists a satisfying assignment E X' such that f(z) 2 0. then [n) == (1} serves as a contrastive reason, as = (z) * (xx = 1, implying that there exists contrastive reason of size 1. To summarize, we have constructed an MCR query instance where there exists a contrastive reason of size k := 1 if and only there exists a satisfying assignment for the neural network f.
This establishes that obtaining the MCR query for a NAM, where X' is defined as either a general discrete or continuous input domain, is NP-Hard.
C
Lemma 16. Given a NAM f. an input x E F, and an integer k E N. where f is defined over either a continuous input space or general discrete input space, then obtaining the MSR query is coNP- comp-Con
Proof. Hardness. We have proven in Lemma 14 that the neural network verification problem for neural network with one input and one output, where the input domain is either continuous or general discrete, is NP-Hard. We can now leverage this hardness result to demonstrate that the MSR query for a NAM defined over either a general discrete or a continuous domain is coNd-Hard.
We, again, can observe that the hardness proof we derived applies to specific scenario in which the output specification Y' mandates that the prediction of [(x) must be positive (i.e., f(x) > 0). Consequently, we will demonstrate hardness by reducing such an instance
neural network with a
single input and output, a bounded input domain X, where the task is to determine whether f(x) 2 to the (complement of) the MSR query.
Given model f and an input specification X, we construct a NAM f' consisting of only one MLP, fi := f. We start by selecting an arbitrary assignment x E X and checking if f(x) < 0. If this condition is satisfied, we define the weight of the corresponding model 31 == and set the bias term as 30 := O. Furthermore, we set k == 0. It is easy to see that if there exists a satisfying assignment z E X for which fz) 0, then [n]] == {1} is a contrastive reason, since 1 = f'(z) + (x) 0 and thus there does not exist a sufficient reason of size O for (J",
For the second case, where fx) > 0, we construct f' in the same way, but this time setting the weight 31 := -1, while keeping 3g := O and, again setting k == O. Similarly, we observe that there exists a satisfying assignment E X' such that f() O, then [n] (1) serves contrastive reason, as = f' (z) * f'(x)= = 1, implying that there exists a contrastive reason of size 1, and hence there does not exist sufficient reason of size 0. To summarize, we have constructed an MSR query instance where there does not exist a sufficient reason of size == 0 if and only if there exists a satisfying assignment for the neural network f.
This establishes that obtaining the MSR query for a NAM, where X' is defined as either a general discrete continuous input domain, is Hard. We note that a recent result by [21 strengthens this bound for the optimization variant, showing that the continuous version of the problem is in fact Olop n)) -hard under metric reductions (see Section B.5 of the appendix).
Regarding membership, although showing that the problem lies in Eg is straightforward (as the same task is known to be in Σf for general neural networks [66),, we refer the reader to recent result in (1). which shows that the optimization variant of the problem is in FPNP FPNP(O(n)) (see Section B.5 of the appendix). This, turn, implies that the corresponding decision variant considered here belongs to A
Having completed the proofs for all NAM instances, we now turn to proving the complexity results for EBMs. We will break down the proof into separate lemmas, each handling the complexity argument for one of the explanation types (CSR, NCR, and MSR), starting with the continuous case and then extending to the general discrete case.
Lemma 17. Given an EBM over either a continuous or general discrete input space, then the CSR query is coNP- Compleee
Proof. Membership. Although we can directly prove membership for EBMs, we choose to establish via a reduction to NAMs. Given that the same task already shown to be coNP-complete for NAMs, and since coNP is closed under polynomial-time reductions, this approach immediately yields
41

---

membership in coNP. A key advantage of this proof is that it extends naturally to other queries such as MCR and MSR since the same reduction applies them as well.
We can directly reduce any EBM to a NAM by transforming each boosted tree ensemble Si into a neural network f/- This is done by converting each decision tree into neural network, following the method proposed in [16 [ To account for the ensemble structure, we introduce an additional hidden layer that assigns weight dj to each tree A standard weighted sum over the outputs then yields a neural network equivalent to the original boosted ensemble. This transformation preserves equivalence for any given input.
Hardness. We perform a reduction from the classic tautology problem (TAUT) for 3-DNFs (which is cONP-Comples defined follows:
TAUT (Tautology):
Input: A boolean 3-DNF formula v == 4 V222...... V. Output: Yes, if ab is a tautology and No otherwise.
We will begin by proving the hardness for the general discrete input space and then explain how to extend the results to the continuous input space. Given a DNF é == 4 V l2 V... ... V bm we will construct an EBM f := (ff)). i.e., the EBM is composed of only one boosted tree. It worth noting that reducing DNFs to boosted trees has been proposed in previous work [63]. However, our situation differs because the boosted tree fi defined over only one input feature 2j and operates on some input space X', i.e., f1 X - IR and f: X' - 13.
We recall that Φ is defined over set of n literals X1, X2....... X,, and m clauses. Given Φ will construct a boosted tree model fi (which will thereby define f == (fi)) and set the general discrete input space X; to encompass any possible integer within the range (0,2" 2 1]. Each feature X; will be associated with its corresponding bit representation in a vector containing n bits.
We note that fi has one input, X1, defined over the domain X,. The model f1 will be ensemble comprising m decision trees. Each decision tree's input is the feature X1. Consider a clause : C1 A C2 A c3, where each conjunct is clause within XX, or its negation. For each conjunct 4 == C1 A C2 A Ca. we will construct a decision tree corresponding to that conjunct.
This decision tree will have three splits, one for each feature C1, C22 C3. Assume, without loss of generality, that these features are represented by Xj, X2, and X,, where each feature may also be represented negatively as X,. Xg, or X,. The splits of the tree will check conditions such as X1 2 2 X1 2 2h, or x1 2 2 (representing literals Xy, XR. X1, respectively), or X1 < 2 X1 < 2 or X1 2 (representing literals X,, Xx, X1, respectively). If all three conditions are satisfied, the tree will output a value of 1; otherwise, it will output 0.
In this scenario, tree number 5 in the constructed boosted tree ensemble fi will perform three splits: first, it will check if x; > 2 then whether x; < 2², and finally whether x; 2 2'. If all three conditions hold true, the tree will output a value of 1. Otherwise, it will output 0. The terms (the weights of each tree in fi) will all be set to For the intercept terms of f. we will set B = and 3n = -1. This defines the full construction of the EBM f. Additionally, we will set S == 0. Finally, we construct the input which is any integer within the range [0, 2n - 1]. as follows: First, we form a binary vector x' E (0, 1 in the following way: we start by choosing an arbitrary conjunct from cI...., Cm. For specific conjunct, we assign the corresponding literals to their respective bits in the vector, while assigning any values to the remaining bits. For instance, consider the clause c; == X1 A X, A Xg. In this case, we create a vector x' where xi == 1, X == O, and X = 1, while the other features in x' (besides features 1, 5, and 8) are assigned arbitrary values. We then define the input as the integer represented by the binary vector x'. In summary, the entire reduction constructs (f. x. S), where f is the constructed EBM defined over the input space X; for the single feature x; of f, x the constructed input, and S ===00 0 is the constructed (empty) subset.
For example, consider the conjunct 65 := X
We will now prove that ø is a tautology if and only if S :- 0 is sufficient reason for (f.x). From our construction of x (the integer representation of the binary vector x', which expands binary bits representing literals from given conjunet). it follows that for the specific conjunct c, over which x' was constructed, the corresponding tree in the ensemble will reach a terminal node with value
1. Consequently, since all other trees output either 0 or 1, and given the intercept term 8n 1,
42

---

we have f(x) = 1. Knowing that f(x) = 1. proving that S 0 is a sufficient reason is equivalent to showing that for any z, it holds that f(x) = 1 = fzz. Conversely, proving that S = 0 is not a
sufficient reason amounts to demonstrating the existence of some z such that f((x = 1 + f(z) = 0.
From our construction, we know that for any assignment of literals z' {0, 1) over d, if a conjunct is satisfied, propagating z (the integer representation of the binary vector z') through the i-th tree of the ensemble will yield a terminal node with value I. Since the outputs of all other trees are either 0 or 1, it follows that (z) 2 1. Including the intercept 6o- = -1, we get f(z) = f(x).
On the other hand, if for some assignment reach terminal nodes with value O, resulting in fzz = 0 + 1 fx). Thus, if there exists an assignment over ø that evaluates to false (i.e.. o is not tautology), there will exist assignment
{0. 1]
conjunct in á is satisfied, all trees will
such that f(z 0 # 1 = f(x), implying that S == 0 is not a sufficient reason for (ʃ: x). Conversely, if no such assignment exists (i.e., 6 is a tautology), then for any z, it holds that fx) 1 = fz),
implying that 1 is a sufficient reason. This concludes the proof.
Finally, we note that, for simplicity, we assumed X,, the domain of the single input X1, to be general discrete domain containing all integer values within [0, 2n - 1]. However, the result also holds if Xi is defined as the entire continuous domain [0, 2" 1]. Notably, in our construction of the single tree ensemble fi within the EBM, the decision rule checking whether 2 2* or x < 2 applies equally to the entire continuous domain. Thus, the hardness results extend to the continuous domain as well.
L
Lemma 18. Given an EBM over either a continuous or general discrete input space, then obtaining the MCR query is NP-Complete.
Proof. For membership, we can use the same reasoning as in Lemma 17 where the given EBM is reduced to an equivalent NAM. Since NP is closed under polynomial reductions, Lemma [8 establishes membership in NP.
For hardness, reduce from the (complement) of the CSR query for EBMs, which we have shown to be coNP-CCmplete. Specifically, we established coNP-hardness for the CSR query by reducing from the TAUT problem to CSR when S : 0. Consequently, we prove hardness by reducing from CSR in the special case where == 0. Given an instance (f. x, S := 0), where f is an EBM, we construct an instance (J,x, k = n); where remains the same EBM, and k n corresponds to setting & of the MCR query to match the input dimension size. We observe that 5 = 0 a sufficient reason for (f, x) if and only if S is not a contrastive reason for (f, x). Thus, S = 0 is a sufficient
reason for (f, x) if and only if no contrastive reason of size exists for x)), thereby establishing the reduction.
Lemma 19. Given an EBM over either a continuous or general discrete input space, then the MSR query is CoNP-CComplet
Proof. For membership, the same reasoning as in Lemma 17 and Lemma 18 applies, where the given EBM is reduced to an equivalent NAM. As coNP closed under polynomial-time reductions, Lemma 17 confirms membership in coNP.
For hardness, we reduce from the CSR query for HBMs, which has been shown to be coNPP-omplete. Specifically, coNP-hardness for the CSR query was established by reducing from the TAUT problem to CSR when S := 9. Accordingly, hardness is proved by reducing from CSR in the specific case where S = 0. For an instance (f, x, S := 0) where ff is an EBM, we construct an instance (f.x, k 0), where of remains the same EBM and k corresponds to setting i of the MSR query. It is observed that S = ( if and only if a sufficient reason of size 0 exists for (f,x). x), thereby establishing the reduction.
J Proof of Proposition
Proposition 6. Given a NAM, a Smooth GAM or an EBM under an enumerable discrete or general discrete setting, the FR query is coNP-Compler
43

---

Proof. Membership. Given GAM f defined over either an enumerable discrete or general discrete imput space, and an input feature i [n], we can guess two imput assignments for feature i: x, such that x; * 7, This is achievable due to the discrete nature of the input space: by selecting single input for each coordinate in the enumerable discrete case, or by choosing a binary vector in the general discrete case. We can additionally guess some assignment for the features [n] \ {i), which we will denote by x' (and the correctness holds for the same reasoning). Now, (n x,) o M 2,), then by definition, is not redundant with respect to (f, thereby completing the membership proof. We note that this membership result holds regardless of the specific type of GAM - applies to any GAM, provided that the inference of its components can he performed in polynomial time. Therefore, it directly extends to models such as NAMs, EBMs, and Smooth GAMs.
Hardness. The study in [8 established coNP-Hardnes for the FR query (referred to there as G-FR) for linear classifiers over binary input space. Given that this represents a specific instance of the enumerable discrete input setting, where the explicit values X; for each feature x; are {0, (0,1] (and is therefore also a particular case of the general discrete input setting). the coNP-hardness results apply these settings well. We note that linear models are particular instance of Smooth GAMs, NAMs and EBMs, where each component f. is taken to be the identity function. Since each of these model types (neural networks, tree ensembles, and piecewise polynomial splines) can trivially be represented as constant identity functions that always produce the same output, the hardness result naturally extends EBMs, Smooth GAMs, and NAMs.
K Proof of Proposition 7
Proposition Given NAMs and EBMs over discrete or continuous settings, computing SHAP for regression lasks is P-Copllete Moreover, given any GAM over enumerable discrete, discrete or continuous setting- computing the CC and SHAP queries for classification are #P- #P-Complete
Proof. We will divide the upcoming proof into two distinct lemmas.
Lemma 20. Given NAMs and EBMs over discrete or continuous settings, computing SHAP for regression tasks is #P-Hard.
Proof. We will start by proving the results for NAMs. First, similarly the proof in Lemma [ we will assume we are dealing with a single input-output neural network, and hence, hardness for this scenario will directly apply to full NAMs. We base the reduction based on the results obtained by 7 and [102] which showed that computing SHAP for model f and an input x is at least hard as the model counting problem for f. under the uniform distribution assumption (and this clearly shows hardness for the more general distribution setting). CNF formulas can be reduced in polynomial time to neural networks, as was shown by multiple studies [16 69 95 [8] (and this claim actually holds even for boolean circuits (T6). As shown by [69] and later refined by (95), neural network defined over a continuous domain can be reduced to the discrete case, thereby transferring the hardness results to the continuous setting as well.
In Lemma 5 we showed that a neural network verification problem for full network can be reduced to one involving single input-output pair. Since the former is known to be hard via a reduction from CNF-SAT [69 (95), this implies that the counting version of CNF-SAT can likewise be reduced to counting the number of satisfying assignments in single input-output neural network. This yields a parsimonious reduction, establishing # harddnsss.. As EBMs can be reduced from NAMs (as we show in Lemma 5), this hardness result extends to EBMs as well.
O
Lemma 21. Given any GAM over an enumerable discrete, discrete or continuous setting- computing the CC and SHAP queries for classification are # P-Hadd..
Proof. Hardness results for GAMS persist because they apply even to linear classification models, which are a special case of GAMs. Consequently, the hardness remains for GAMs. Specifically, for the CC query, this result was established by [66, and for the SHAP query, was demonstrated by [122]. Linear models can be viewed as special case of Smooth GAMs, NAMs, and EBMs, where
44

---

each component function f; is simply the identity function. Since neural networks, tree ensembles, and piecewise polynomial splines can trivially replicate this behavior by acting as constant identity functions that yield fixed output, the hardness result directly extends to EBMs, Smooth GAMs, and NAMs.
45


Reviews:
[{"review_id": "UCepy1odK0", "reviewer": "Reviewer_zumg", "summary": "This paper discusses Generalized Additive Models from complexity theoretic perspective, challenging the hypothesis that obtaining meaningful explanations for GAMs could be performed efficiently and would not be computationally infeasible. \n\nThe analysis is outlined in three dimensions. component model type, type of explanations, and input domain setting. There are several key findings that the analysis shows, including the heavy impact from input domain and component type on the GAM explanations and the hardness of explanations for classification task from SHAP model. In addition, depending on the explanation types and input domain,  some black-box model like neural networks are harder to explain compared with the additive models like NAM. \n\nThe paper further details each finding along with proof in the appendix.", "questions": "1. Why is the LIME not included in the selection?", "limitations": "None.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Overall, I found the results presented in this paper quite interesting. I am not an expert in complexity analysis so I can fully verify the details of the proof. \n- The paper has covered a wide range of models such as smooth GAM,  EBM, NAM, and SHAP. \n- The paper also covers a wide range of explanations from Shapley attributes to counterfactual explanations. \n\nWeaknesses\n- It might be more convincing to show results with experiments.", "was_revised": true, "final_justification": "I thank the authors for the detailed explanations. I changed my score accordingly. However, as mentioned, I am not an expert in this the complexity analysis. Thus, I would keep my confidence score.", "rebuttal": "We thank the reviewer for their valuable and constructive feedback and for acknowledging the significance of our work. See our response below.\n\n**The choice of explanation definitions and why LIME is not analyzed**\n\nThe literature offers a wide variety of explanation notions. To reflect this natural diversity, our work considers a broad range of commonly used explanation definitions. These include identifying minimal sufficient feature subsets, generating contrastive explanations that alter the model’s prediction, detecting feature redundancy, and assigning importance scores to features using the widely adopted Shapley value framework. While other explanation notions may also be of interest, we believe that our selection captures a wide array of central facets of how models are typically interpreted. Moreover, a further advantage worth noting of the definitions we chose to study is that they are grounded in formal, well-defined semantics, which enables a rigorous analysis of the computational complexity involved in computing them. These choices are consistent with prior work on the computational complexity of generating explanations for models beyond GAMs (e.g., see [1–5]).\n\nIn particular, while LIME is also a popular additive feature attribution method (like SHAP), analyzing its complexity is trickier. This is because LIME constructs a local linear surrogate model using sampled perturbations, a process that lacks a precise and direct formalization suitable for complexity-theoretic analysis. In contrast, SHAP's clear mathematical formulation makes it more suitable for complexity analysis. That said, we agree with the reviewer that studying the complexity of generating local surrogate-based explanations, whether for GAMs or other models, is an interesting and valuable direction. We will mention this as a possible avenue for future research and thank the reviewer for raising this point.\n\n**Follow-up experimental works of our findings**\n\nWe thank the reviewer for acknowledging the importance of our theoretical contributions. While our work is indeed theoretical, we believe it is closely tied to practical considerations and can serve as a strong foundation for a wide range of future experimental studies involving GAMs. In particular, we present a broad set of efficient algorithms for computing several highly desirable explanation types and clearly delineate the conditions under which such explanations are tractable or provably hard.\n\nOur analysis also highlights central structural parameters of GAMs that impact computational feasibility — including the input domain (a central theme of our work), model coefficient precision (where quantization can make otherwise intractable problems tractable), and the type of component models used (e.g., splines, neural networks, tree ensembles). We fully agree that exploring experimental applications of these insights is an important direction for future work. \n\nHowever, as noted by the reviewer as well as other reviewers, our paper already presents a very broad and detailed theoretical analysis across a wide range of complexity-theoretic settings. Due to space constraints, we were not able to include experiments, too, as we believe they could potentially represent a separate line of work on their own. That said, we believe the strong theoretical foundation we provide in this work is comprehensive enough by itself and is well-suited to support such future studies. We will elaborate on some of the future directions we see as valuable in the final version and thank the reviewer for highlighting this point.\n\n[1] Model interpretability through the lens of computational complexity (Barceló et al., Neurips 2020)\n\n[2] On Computing Probabilistic Explanations for Decision Trees (Neurips 2022)\n\n[3] On the Tractability of SHAP Explanations (Van den Broeck et al., JAIR 2022)\n\n[4] On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results (Arenas et al., JMLR 2023)\n\n[5] Local vs. Global Interpretability: A Computational Complexity Perspective (Bassan et al., ICML 2024)"}, {"review_id": "sq9tWCbx5V", "reviewer": "Reviewer_gmVs", "summary": "This paper analyzes the computational complexity of generating explanations for generalized additive models (GAMs), including spline-based GAMs, neural additive models (NAMs), and explainable boosting machines (EBMs). It formalizes the hardness of producing four types of explanations across different types of input domains (enumerable discrete, general discrete, and continuous). One of the most interesting insights is that, unlike for other model classes (e.g., decision trees or neural networks), the tractability of explanations in GAMs depends on the nature of the input domain. In a somewhat counterintuitive result, certain explanation types are shown to be strictly easier in continuous input spaces than in discrete ones. The paper contributes to the theory of explainable AI by highlighting structural distinctions that affect the computational feasibility of explanation, even for models typically viewed as interpretable.", "questions": "- Are any of the intractable explanation queries known to admit efficient approximation schemes or heuristics in practice? If so, a discussion of this would improve the practical significance of the work.\n- Do the complexity results extend to GAMs with pairwise or higher-order interactions, such as those implemented in EBMs with interaction terms?\n- How do the theoretical results relate to known empirical inconsistencies in GAM explanations (e.g., contradictory attributions across model classes [Chang KDD 2021])? If the authors can connect their results to these empirical observations, it would strengthen the paper’s impact.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- A welcome contribution to formal explainable AI, in a field often dominated by heuristics and empirical metrics.\n- Provides a clean, well-structured taxonomy of explanation types and complexity results.\n- The finding that explanation complexity for GAMs is sensitive to the input domain is genuinely interesting and distinguishes additive models from other common model families.\n\nWeaknesses:\n- While technically correct, many of the hardness results (e.g., for NAMs or EBMs) are not surprising given the high capacity and unbounded VC dimension of these models.\n- No empirical demonstrations or approximation strategies are provided, and the practical relevance of the theoretical results is limited.\n- The paper does not engage with prior empirical work on inconsistencies in GAM explanations, which could help contextualize the formal findings.\n- The writing is a bit wordy, and repeatedly frames results as “surprising,” even in cases where the conclusions could be understood directly from known properties. This undermines the impact of the more novel insights.", "was_revised": true, "final_justification": "Thank you for your detailed response to my and other reviewer comments.\n\nI appreciate the clarifications regarding the role of input domain in explanation complexity and the potential extensions to interaction terms. Your comments on approximation strategies and prior empirical work help clarify the broader context of the results.\n\nThat said, most of the rebuttal focuses on future revisions rather than new contributions or clarifications within the current submission. The points raised around practical relevance, empirical connections, and approximation techniques are still left to the domain of future work.\n\nI continue to view the paper as a technically sound theoretical contribution with an interesting, though perhaps unsurprising, result about domain-sensitive explanation complexity in GAMs. However, the practical utility remains limited, and I am keeping my score unchanged at a borderline accept.", "rebuttal": "We thank the reviewer for their valuable and constructive feedback and for acknowledging the importance of our work. See our detailed response below.\n\n**Better clarifying the unexpectedness of certain findings**\n\nWe thank the reviewer for raising this point. As the reviewer noted, some of the findings in our work may indeed seem surprising. For instance, the sharp complexity differences observed in additive models depending on the input domain contrast with the behavior seen in other ML models. Moreover, the fact that complexity in GAMs varies *inconsistently* across input domains, with continuous domains sometimes making explanation computation harder and other times easier, also stands out as unexpected.\n\nThat said, we agree that certain findings may indeed seem less surprising — such as the general observation that computing explanations for GAMs can, in *some* configurations, be computationally challenging. As the reviewer correctly pointed out, this result can perhaps align with intuitive expectations based on the unbounded VC dimension of GAMs in some settings. Still, even in these seemingly more expected cases, our results reveal significantly *diverse* complexity distinctions that depend on the specific configuration of component model type, input domain, and explanation type.\n\nOverall, we certainly agree with the reviewer’s suggestion that we should more carefully qualify terms like “surprising” or “unexpected” and explain their exact meaning. Our intention was to highlight results that deviate from typical patterns, such as the significantly different complexity behavior of additive models compared to other ML models or the inconsistent role of the input domain. Nonetheless, we agree that such terms can be subjective, and we will revise the final version to clarify their usage and provide more precise context.\n\n**Extension to higher-order interaction GAMs**\n\nWe thank the reviewer for this excellent question. We agree that exploring the complexity of explanations under higher-order interactions is a very interesting direction. The answer depends heavily on how such interactions are defined — for instance, whether we allow a fixed number $k$ of interaction terms or an unbounded number of interactions up to degree $k$ — as well as on the specific configuration of explanation type, component model, and input domain, which our work shows significantly affect complexity. In some cases (e.g., for SHAP or feature redundancy identification), adding a small number of interactions may be handled with straightforward extensions of our existing algorithms. In contrast, our algorithms for computing explanations like sufficient or contrastive reasons, which rely on sorting features by importance, may become more complicated. In general, while some explanation types could extend naturally to handle interactions, others may exhibit new complexity behaviors that warrant deeper investigation. We see this as a very interesting and fundamental direction for future research, and in the final version, we plan to discuss it further, providing complexity extensions for some simple cases and framing the broader “price of interaction” as a central open direction for a full and thorough investigation in future work.\n\n**Relation to prior work on the interpretation and inconsistencies of GAMs**\n\nWe believe that our work, as highlighted by the reviewer as well as other reviewers, offers a unique and previously unexplored perspective on the explainability of GAMs by focusing on the computational aspects of generating explanations. That said, we recognize that some of our findings indeed relate to existing ideas in the literature concerning interpretability and inconsistencies in GAMs, and we agree with the reviewer that improving the discussion of these connections would further strengthen our work.\n\nOne clear connection to prior work lies in the observation that GAMs with more complex or non-linear component models are often harder to interpret than those built from simpler components. This observation has been noted in several prior studies (e.g., [1-3]) and aligns with some of our own findings (see Table 1 and Section 5.2), which show that explanation computation can indeed become more difficult for GAMs with more expressive components. However, our results also reveal that this is not a universal rule — the complexity of obtaining explanations depends heavily on both the type of explanation and the nature of the input domain. We hence believe that this new perspective offers a more nuanced and rigorous understanding of when and why some of these interpretability challenges arise.\n\nA second connection to prior work lies in the widely held assumption that additive models are inherently more interpretable than their non-additive counterparts, which is a central motivation for their use. Although this assumption is often treated as self-evident, our work offers a new computational perspective: we demonstrate that transitioning from non-additive models (such as neural networks) to additive ones (such as NAMs) can indeed simplify the computation of explanations. However, we find that this advantage is also not universal; it depends on the specific pairing of input domain types and explanation forms, which once again highlights the value of this computational angle.\n\nFinally, we agree with the reviewer that incorporating a discussion of inconsistencies, such as those identified by Chang et al. (KDD, 2021) and related work, would enhance our paper, and we intend to include this in the final version. These studies underscore the importance of *data fidelity* in interpreting GAMs, demonstrating that models with similar predictive performance but different architectures (e.g., splines vs. EBMs) can vary significantly in their bias-variance tradeoffs. This points to the *high sensitivity* of learned GAM functions to both the underlying data distribution and the chosen component models. Although this prior work is empirical and differs from our computational perspective, both lines of research highlight a shared insight: the component structure and input representation in GAMs have a crucial role in shaping the model’s functional form — which, in turn, directly influences both its interpretability and the complexity of generating explanations. We thank the reviewer for highlighting this additional perspective. We plan to incorporate this discussion into our final version, and we agree it will help strengthen our work’s connection to broader discussions in the literature.\n\n\n**Approximation and circumvention schemes for intractable results**\n\nWe thank the reviewer for raising this point. While our work presents a broad range of results characterizing both strict tractability and intractability of explanation computations across various settings, it also highlights two particularly promising avenues for circumventing intractability in otherwise hard cases.\n\nThe first avenue involves *pseudo*-polynomial algorithms. These results demonstrate that although the general problem may be intractable, if one assumes that the coefficients of the GAM are quantized (i.e., represented with bounded precision), the problem becomes computationally efficient to solve.\n\nThe second avenue stems from our findings on how the input domain influences complexity. In some cases, changing the input configuration offers a practical workaround to intractability. For example, we show that while explanation computation may be intractable over a continuous or general discrete input space, it becomes tractable when the domain is an enumerable discrete set (or vice versa) — suggesting that input quantization, or other input transformation techniques, can enable efficient computation.\n\nWe also agree with the reviewer that further exploration of additional complexity circumvention strategies is an important direction for future work. For instance, can we develop fully polynomial-time approximation schemes (FPTAS) or fully polynomial-time randomized approximation schemes (FPRAS) that approximate the *size* of sufficient or contrastive explanations? Additionally, are there other structural parameters, beyond input representation and coefficient precision, that could render intractable explanation tasks tractable?\n\nWe will make sure to include these open directions as part of our discussion of future work and will also better emphasize the above two circumvention strategies in the final version.\n\n[1] Interpretable Machine Learning (Molnar et al.)\n\n[2] How Interpretable and Trustworthy are GAMs? (Chang et al., KDD 2021)\n\n[3] Neural Additive Models: Interpretable Machine Learning with Neural Nets (Agarwal et al., Neurips 2021)"}, {"review_id": "JuxripOEtU", "reviewer": "Reviewer_mpma", "summary": "Generalized additive models are a popular class of glassbox machine learning methods which are easily interpretable through the shape functions of each feature which detail each feature's contribution to the output. However, in order to make actionable decisions based on generalized additive models one requires further explainability methods such as minimum sufficient reason. The present paper presents computational complexity results for several explainability methods which depends on the input domain and the model class of the additive components and problem type (regression or classification). This is a theory paper without experiments.", "questions": "-", "limitations": "-", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I am unfamiliar with complexity theory and hence did not check the math. \n\n### Strengths:\n- The paper is well-structured, polished and easy to read. I would only suggest to add more intuition here and there as mentioned below (minor).\n- All theoretical contributions are well summarized in section 4 and 5.\n\n### Weaknesses:\n- Could you add a discussion on how the complexities you derived relate to concurvity [see e.g. Kovács (2024)]? Would stronger concurvity lead to higher computational complexity in some way?\n- Can you add a discussion relating your results to a reader (like myself) who is unfamiliar with complexity theory? What could be actionable consequences of your findings for a data scientist?\n\n#### (Minor):\n- I think it would help a reader new to the field to add intuition to the explanation types in section 3.3, for example mention a real-world scenario in which this explanation might be useful. For example for minimum sufficient reason it could be to ensure that a loan application is approved only based on certain attributes and that the decision is not based on others. For minimum change required it could be to determine the minimum change in a feature required to go get a customer from non-buying to buying.\n\n### References:\n- Kovács, L. Feature selection algorithms in generalized additive models under concurvity. Comput Stat 39, 461–493 (2024). https://doi.org/10.1007/s00180-022-01292-7", "was_revised": true, "final_justification": "The authors addressed all of my concerns, I think they made the paper both more accessible to readers unfamiliar with complexity theory as well as more rounded by including a discussion on concurvity.", "rebuttal": "We thank the reviewer for their valuable and constructive feedback and for acknowledging the significance of our work. See our detailed response below.\n\n**Actionable consequences of complexity results**\n\nWe thank the reviewer for acknowledging the theoretical contributions of our work. Although the focus of our paper is theoretical, we believe it offers many valuable practical insights for practitioners working with GAMs. Notably, our study introduces a wide range of *efficient algorithms* for computing several widely used and well-regarded explanation types from the literature — such as minimum sufficient reasons, minimum contrastive reasons, identifying feature redundancies, and exact SHAP explanations. We present algorithms in this paper demonstrating that, for many configuration choices (as outlined in Table 1), these computations can be solved in polynomial time. Moreover, we will clarify more explicitly in the paper that our algorithms are not just polynomial, but are *linear* in the size of the GAM, highlighting their practical applicability.\n\nMoreover, even in cases where we establish intractability, we sometimes provide *pseudo*-polynomial algorithms. These algorithms become highly efficient when the GAM’s coefficients are quantized (i.e., have limited precision), unlike the even more desirable general tractable cases, which do not rely on such assumptions. This presents an additional practical strategy for practitioners, who can quantize a GAM’s precision weights to facilitate more efficient explanation computation.\n\n\nFinally, we believe that our many *intractability* proofs (e.g., NP-hardness, #P-hardness) also offer critical practical guidance by delineating which types of explanations are computationally feasible and which are not. One especially relevant insight is that the modeling of the *input space* has a critical impact on tractability — unlike other ML models where such a dependency has not been observed. This has practical implications for how practitioners configure GAMs (in terms of the choice of input domain and component types) when aiming to obtain specific forms of explanations efficiently. For example, practitioners may choose to reconfigure the input space, particularly by applying transformations such as discretization, quantization, or switching between discrete and continuous domains (and vice versa), to enable efficient explanation computation, depending on the specific explanation type of interest.\n\n\nWe thank the reviewer for highlighting this important point and will discuss these aspects in detail in the final version of the paper.\n\n**Relation of complexity results to the concurvity of GAMs**\n\nWe thank the reviewer for raising this interesting point regarding concurvity in GAMs, particularly in connection with the work by Kovács et al. Our analysis does not rely on any structural assumptions such as low concurvity — all of our tractability results (i.e., polynomial-time algorithms) hold for *any* GAM, regardless of the level of concurvity, as long as the configuration of input domain, component type, and explanation type is fixed. In other words, the efficiency of our algorithms remains unchanged whether the model exhibits high or low concurvity.\n\nThat said, while our intractability results (e.g., NP-hardness, #P-hardness) hold in general, introducing additional structural assumptions on the GAM could, in some cases, reduce the complexity of computing explanations — depending on the specific assumption, explanation type, input domain, and component models. In this regard, we agree that concurvity is a particularly interesting parameter to investigate. For example, consider two extreme cases: in the case of very high concurvity, where the smooth components are highly correlated and effectively behave similarly to even a single spline, the GAM may resemble a simpler function class, which could make certain explanation tasks easier. Conversely, in scenarios of very low concurvity, especially when considering explanation types that depend on the interaction between features, the high separability of components might also lead to computational advantages. Naturally, the precise implications depend on the exact formal definition of concurvity and the specific configuration of the input domain, explanation task, and component models. We agree that this is a valuable and interesting direction, and we will include a discussion of potential structural assumptions worth exploring, with particular focus on concurvity and its connection to Kovács et al., in the final version.\n\n\n**Real-world scenarios of explanation definitions**\n\nWe thank the reviewer for this valuable suggestion and fully agree with its importance. Following this, we plan to include in our final version real-world examples to illustrate each of the explanation definitions presented in our work. For instance, in the context of loan applications, a user may be interested in identifying a minimal subset of input features that alone suffice to predict a loan approval or denial (a minimum sufficient reason), or in providing an actionable explanation for what specific minimal change would be required to flip the application decision from rejection to approval (a minimum contrastive reason). Feature redundancy identification can be particularly relevant in domains like healthcare, where recognizing that a certain criterion, such as blood pressure, is redundant can have significant implications for diagnosis or treatment decisions. SHAP attributions, which assign additive importance scores to features, can be widely applicable across tasks involving tabular data, computer vision, and more. We agree that including such examples will help clarify the explanation types and improve the paper’s accessibility, and we will incorporate them into the final version."}, {"review_id": "EA25S9xaoa", "reviewer": "Reviewer_gVvN", "summary": "**Because I am not an expert in GAMs and even less in computational‑complexity theory, I attach a low confidence score to all judgments below.**\n\nThe paper studies how hard it is provably to compute several popular explanation types for GAMs. \nAcross three axes (input-space discreteness, component model class, and regression vs. classification task), the authors present polynomial-time algorithms, NP/coNP hardness, and #P hardness results, summarized in Table 1. Key insights include \n(i) complexity often hinges on whether the input domain is enumerable, discrete, or continuous; \n(ii) splines, neural additive models (NAMs), and explainable boosting machines (EBMs) yield different hardness profiles; and \n(iii) SHAP is tractable for regression but #P-hard for classification.", "questions": "- Q1. How do these theoretical complexity results translate to practical computational differences on real datasets of typical sizes?\n- Q2. Are there good polynomial-time approximation algorithms for the cases proven to be intractable?\n- Q3. How common are the different input domain scenarios in real-world applications of GAMs?\n- Q4. Could the analysis be extended to other explanation methods commonly used in practice (integrated gradient, banzhaff indices, sobol' indices) ?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strenghts**\n\n- The framework / splitting of the research into (input, component, task) make the reading of the article pleasant and also more easily accessible, thank you.\n- The authors occasionally extract intuitive explanations, for example, why classification SHAP becomes hard once a step function breaks linearity, which helps readers who lack deep complexity background. Their pseudo-polynomial algorithms show the results are not purely negative; they identify practical levers (weight precision) to regain tractability.\n\n**Weaknesses**\n\n- M1. My main concern is about limited practical relevance: While theoretically interesting, many of the complexity distinctions may not matter in practice. Can you elaborate or help translate your finding into any actionable insight ?\n- M2. Type of explanations: The analysis relies heavily on specific mathematical definitions of explanation types that may not align with how practitioners actually use or interpret GAM explanations (maximally activating example, gradient...). The theoretical definitions might be too narrow for practical explainability.\n- M3. Related to M1, Missing empirical validation: As a purely theoretical work, there's no validation of whether the complexity distinctions translate to meaningful differences in real-world computational performance or whether the theoretical worst-case scenarios occur in practice.\n\nNow for the minors weaknesses,\n- m1. dense presentation: The paper is quite technical and may be difficult to access for researchers who aren't specialists in computational complexity theory, potentially limiting its impact.\n- m2. limited discussion of approximation algorithms: While the paper establishes intractability results, it doesn't explore whether good polynomial-time approximation algorithms might exist for the hard cases.\n- m3. typo: “continous”\n- m4. lines 221–230 \"often relevant for tabular data\"; a citation to a real tabular application using enumerable GAMs would help.", "was_revised": true, "final_justification": "I keep my borderline-accept rating. The rebuttal provides helpful clarifications and outlines possible extensions, but the work still lacks empirical grounding to show whether the complexity distinctions have practical impact. Even small experiments or runtime comparisons would help connect theory to application. I am not an expert in GAMs or computational complexity, so I give low weight to my judgment here, but I remain unconvinced of the practical utility despite the theoretical solidity.", "rebuttal": "We thank the reviewer for their valuable and constructive feedback and for acknowledging the importance of our work. See our detailed response below.\n\n**Actionable insights and practicality of the theoretical results**\n\nWe thank the reviewer for recognizing the theoretical significance of our work and for their appreciation of both the novel results and their presentation. While the paper is indeed theoretical, we believe it offers many important practical insights for GAM practitioners. In particular, our study introduces a broad set of *efficient algorithms* for computing widely used and well-established explanation types from the literature — including minimum sufficient reasons, minimum contrastive reasons, feature redundancy detection, and exact SHAP attributions.\n\nAs demonstrated in Table 1, we prove that many of these computations are solvable in polynomial time across various GAM configurations. Moreover, we will make it clearer in the final version that our tractable algorithms are not only polynomial but also *linear* in the size of the GAM, emphasizing their practical usability.\n\nFor example, in loan applications, a practitioner may seek a minimal feature subset that guarantees approval (a minimum sufficient reason) or the smallest change needed to reverse an undesired rejection (a minimum contrastive reason). In healthcare, identifying redundant features, like blood pressure being irrelevant to any prediction, can be critical for making decisions. SHAP values, which assign exact importance scores, are widely used in fields like tabular data and computer vision. Our results pinpoint when such explanations can be computed efficiently, guiding practitioners in configuring a GAM accordingly and applying our algorithms.\n\nIt is also important to mention that even in cases where we establish intractability, we sometimes provide *pseudo*-polynomial algorithms that become efficient when the GAM’s coefficients are quantized, that is, restricted to limited precision. While these are less broadly applicable than our polynomial-time algorithms, they still offer a practical solution for users working under reasonable constraints. In particular, a practitioner can configure a GAM with quantized weights and still efficiently compute the desired explanation using our algorithm.\n\nMoreover, we believe our intractability results (e.g., NP-hardness, #P-hardness) also offer practical value by identifying which explanations are computationally feasible and which are inherently hard. One particularly important insight is that the *input domain* plays a crucial role in determining tractability — a dependency that has not been found on other popular ML model classes. This observation can guide practitioners in configuring GAMs (in terms of both input encoding and component selection) to enable efficient explanation generation. \n\nFinally, we fully agree with the reviewer that, while our work establishes hardness results in certain settings, investigating heuristic approaches to overcome these computational challenges is a valuable and promising avenue for future research. Our *tractable* algorithms are tailored to specific configurations (e.g., particular component types or input domains) and thus cannot be directly extended to the intractable cases. Nonetheless, we believe that these algorithms, together with the computational boundaries they outline, can offer a strong foundation for the development of heuristics that may bypass some of the established hardness barriers in generating explanations. Designing such heuristics would likely require significant algorithmic design and constitutes a meaningful research challenge in its own right. We will highlight this as a central direction for future work and believe our contributions provide a strong basis for initiating such efforts.\n\nOverall, we thank the reviewer for highlighting these important points and will incorporate a thorough discussion of them in the final version.\n\n\n**Possible extensions to additional explanation forms**\n\nWe agree with the reviewer that, while our framework captures a broad range of widely-used explanation types, other explanation notions are certainly worth exploring. Indeed, many of our proof techniques can be extended to additional forms. For example, *Banzhaf values*, that were mentioned by the reviewer, share key complexity-theoretic properties with Shapley values, and some of our Shapley-based proof techniques (e.g., using the linearity axiom) naturally carry over.\n\nSimilarly, when computing minimum sufficient or contrastive reasons, our algorithm identifies the minimum or maximum viable values for each GAM component and ranks them accordingly. As a result, a subroutine of this algorithm can also be used to generate *maximally activating examples* — an explanation type noted by the reviewer. In the case of SHAP explanations, which require expected value computations, a subroutine of that algorithm can be extended to support *variance*-based approaches such as *Sobol indices*, which also rely on expectation calculations. More broadly, many explanation methods involve identifying critical values, ranking components, or computing expectations — all of which align with the core procedures used in our algorithms.\n\nIn summary, we agree that extending the analysis to additional explanation types is a promising direction for future work. While we believe that our current focus captures a rich and representative subset of widely-used and practically relevant explanation methods, we also believe that the breadth of algorithmic and proof techniques developed in this work provides a strong theoretical foundation for analyzing further explanation forms in future work. We thank the reviewer for raising this point and we plan to incorporate a thorough discussion of this matter in our final version.\n\n**Approximation and circumvention schemes for intractable results**\n\nWhile our work offers a broad characterization of both tractable and intractable cases for explanation computation across a variety of settings, it also identifies two particularly promising strategies for circumventing intractability in otherwise hard cases.\n\nThe first strategy involves *pseudo*-polynomial algorithms. These show that, although the general problem is intractable, assuming quantized GAM coefficients (i.e., bounded precision) renders the problem efficiently solvable.\n\nThe second strategy builds on our findings regarding the role of the input domain in shaping complexity. In some cases, reconfiguring the input space provides a practical workaround. For instance, while explanation computation may be intractable over general discrete or continuous domains, it becomes tractable when the input is enumerable (or vice versa for other explanations). This suggests that input quantization, or a different transformation technique, can enable efficient computation. \n\nWe also agree that additional complexity circumvention strategies represent an important avenue for future work. For example, can we design fully polynomial-time approximation schemes (FPTAS) or randomized schemes (FPRAS) to approximate the *size* of sufficient or contrastive explanations? Furthermore, are there structural properties, beyond input representation and coefficient precision, that could make intractable explanation problems tractable?\n\nWe will incorporate these open directions into our discussion of future work and highlight the two strategies above more prominently in the final version. We thank the reviewer for bringing this up.\n\n**The common use of different input domains in GAMs**\n\nYes, all the input domain types we analyze are commonly used in practice when working with GAMs and typically depend on how the underlying features are represented in the data ([1–3]). For instance, in the standard tabular task of loan prediction, features like *age* or *monthly income* can often be modeled as continuous, as they represent values over a continuous range. In contrast, features such as *occupation* (“teacher”, “engineer”, “unemployed”), *gender*, or *loan purpose* (“business”, “wedding”, “education”, etc.) are typically modeled as discrete inputs with a fixed and enumerable set of options. However, other features like *user name* or *ID* are also discrete, yet effectively non-enumerable due to the vast number of potential unique values.\n\nIt is also worth noting that different input representations can often be transformed into one another. In GAMs, discretization is a common practice (e.g., [1,3]). For example, in our loan application example, continuous inputs like *age* or *salary* can be left as-is, discretized into broad (non-enumerable) buckets, or even quantized into a small enumerable set of categories. Our complexity results highlight how the input domain has a substantial impact on the feasibility of computing various explanation types, and this suggests practical mitigation strategies: by adjusting how input features are represented, practitioners can potentially improve the efficiency of explanation computation. We appreciate the reviewer’s point on this matter and plan to expand on this discussion in the final version of the paper.\n\n\n**Presentation and other minor suggestions**\n\nWe thank the reviewer for these helpful suggestions! Following these remarks, we will use the additional space in the final version to provide more background and intuitive explanations regarding the computational complexity aspects of the paper. We will also fix the noted typo and include the missing reference. We appreciate your careful reading!\n\n[1] Intelligible Models for HealthCare: Predicting Pneumonia Risk and Hospital 30-day Readmission (Crauna et al., KDD 2015)\n\n[2] Axiomatic Interpretability for Multiclass Additive Models (Zhang et al., KDD 2019)\n\n[3] Accuracy, Interpretability, and Differential Privacy via Explainable Boosting (Nori et al., ICML 2021)"}]

Author rebuttal:

Meta-review: This paper explores the complexity requirements associated with generating 'explanations' in generalized additive models (GAMs), a popular, expressive class of 'interpretable' models.

The topic is clearly of relevance to the NeurIPS community, and the paper presents novel results.

At the same time, some reviewers express concerns about exposition, and a failure to convince readers of the practical utility of this analysis - or actionable insights arising from it.

Nevertheless, all reviewers return some form of 'accept' in their reviews.  In my post-rebuttal correspondence with them, I asked if any was willing to argue against 'accept'.  None has.

As reviewers largely indicated lower confidence, and did not seem strongly enthusiastic, I have recommended accepting the paper as a poster.
Decision: Accept (poster)