Additive Models Explained: A Computational Complexity Approach

We thank the reviewer for their valuable and constructive feedback and for acknowledging the importance of our work. See our detailed response below.

Actionable insights and practicality of the theoretical results

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

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

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

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

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

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

Overall, we thank the reviewer for highlighting these important points and will incorporate a thorough discussion of them in the final version.

Possible extensions to additional explanation forms

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

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

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

Approximation and circumvention schemes for intractable results

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

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

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

We 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?

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

The common use of different input domains in GAMs

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

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

Presentation and other minor suggestions

We 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!

[1] Intelligible Models for HealthCare: Predicting Pneumonia Risk and Hospital 30-day Readmission (Crauna et al., KDD 2015)

[2] Axiomatic Interpretability for Multiclass Additive Models (Zhang et al., KDD 2019)

[3] Accuracy, Interpretability, and Differential Privacy via Explainable Boosting (Nori et al., ICML 2021)

We thank the reviewer for their valuable and constructive feedback and for acknowledging the significance of our work. See our detailed response below.

Actionable consequences of complexity results

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

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

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

We thank the reviewer for highlighting this important point and will discuss these aspects in detail in the final version of the paper.

Relation of complexity results to the concurvity of GAMs

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

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

Real-world scenarios of explanation definitions

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

We thank the reviewer for their valuable and constructive feedback and for acknowledging the importance of our work. See our detailed response below.

Better clarifying the unexpectedness of certain findings

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

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

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

Extension to higher-order interaction GAMs

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

Relation to prior work on the interpretation and inconsistencies of GAMs

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

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

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

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

Approximation and circumvention schemes for intractable results

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

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

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

We 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?

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

[1] Interpretable Machine Learning (Molnar et al.)

[2] How Interpretable and Trustworthy are GAMs? (Chang et al., KDD 2021)

[3] Neural Additive Models: Interpretable Machine Learning with Neural Nets (Agarwal et al., Neurips 2021)

We thank the reviewer for their valuable and constructive feedback and for acknowledging the significance of our work. See our response below.

The choice of explanation definitions and why LIME is not analyzed

The 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]).

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

Follow-up experimental works of our findings

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

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

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

[1] Model interpretability through the lens of computational complexity (Barceló et al., Neurips 2020)

[2] On Computing Probabilistic Explanations for Decision Trees (Neurips 2022)

[3] On the Tractability of SHAP Explanations (Van den Broeck et al., JAIR 2022)

[4] On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results (Arenas et al., JMLR 2023)

[5] Local vs. Global Interpretability: A Computational Complexity Perspective (Bassan et al., ICML 2024)