What makes an Ensemble (Un) Interpretable?

We thank the reviewer for the constructive feedback, and for recognizing the significance of our work.

Discussion on more specialized ensemble schemes

We thank the reviewer for raising this point. While our complexity results are established for both majority voting and weighted voting inference methods - covering a broad range of possible ensemble configurations and commonly used ensembles - many of our findings extend to other types of ensemble methods as well. We touch on this briefly in Appendix A.1, where we discuss how our results extend to certain other ensemble configurations. Specifically, for meta-learner ensembles (as discussed in A.1), if the meta-learner can simulate majority or weighted voting - which is feasible even with simple models like linear classifiers, and certainly with neural networks - then the hardness results we present also extend to this setting. However, the membership results are more nuanced and would depend on the specific architecture of the meta-learner. Similarly, for dynamic ensembles, whenever the dynamic behavior reduces to a static configuration (e.g., fixed weights), the hardness results continue to hold. However, as with meta-learners, the membership results would depend on the particular characteristics of the dynamic mechanism. We will highlight these points more clearly in the final version.

Practicality aspects and relation to existing explainability schemes

We thank the reviewer for raising this important point. We will clarify and expand our discussion of these aspects in the final version of the paper.

We first emphasize that some of our results demonstrate the intractability of various explanation tasks, hence demonstrating that heuristic approaches may lack formal guarantees. For example, in the case of sufficiency-based explanations, this can imply that practical heuristics that are used in practice may produce explanations that are either insufficient (i.e., unfaithful) or suboptimal in terms of minimality - issues already noted in practical prior work that have examined these aspects (e.g., [1-2]). Similarly, for SHAP, our results suggest that heuristic methods like KernelSHAP or FastSHAP may significantly diverge from exact SHAP values.

For tree ensembles, many computational challenges become efficiently solvable when both the number of trees and the number of leaves per tree are bounded. Furthermore—and importantly—we will clarify in our practical discussion that many of these computations are also amenable to parallelization. Lastly, since our work establishes membership in classes such as W[1] and related complexity classes, some of these problems can be reduced to well-known problems within these classes (e.g., $k$-Clique), for which efficient heuristics are already available [e.g., 3–4]. This opens up an interesting direction for future research, where such heuristics could be leveraged to solve these problems more efficiently. We also agree that an exciting direction for future work lies in exploring additional forms of approximate guarantees - such as fully polynomial-time approximation schemes (FPTAS) or fully polynomial-time randomized approximation schemes (FPRAS) - as well as investigating relaxed versions of certain explanation definitions, which may offer improved tractability.

Given these considerations, the scalability of explanation methods like SHAP for tree ensembles largely hinges on the number of leaves per tree. When this number is relatively small, explanations remain tractable - even for considerably large ensembles such as those mentioned by the reviewer. However, a key and central practical insight from our results is that interpretability benefits, from a computational perspective, are greater when using fewer but deeper trees rather than many shallow ones - an insight that can influence the preferred tree structure when interpretability is the goal. In contrast, integrating linear models into ensembles can significantly hinder interpretability, even with just a few base models, due to a rapid increase in the complexity of generating explanations. This highlights the comparative advantage of decision-tree-based ensembles over those incorporating linear models from an interpretable lens. We believe the strong theoretical foundation laid by our work can inspire further practical exploration of these diverse aspects, and we will revise the final version to expand this practical discussion. We thank the reviewer for raising this important point!

[1] VeriX: Towards Verified Explainability of Deep Neural Networks (Wu et al., Neurips 2023)

[2] Using MaxSAT for Efficient Explanations of Tree Ensembles (Izza et al., AAAI 2022)

[3] Efficient Algorithms for Clique Problems (Vassilevska et al., Information Processing Letters)

[4] Efficient Maximum Clique Computation over Large Sparse Graphs (Chang et al., KDD 2019)

We thank the reviewer for the valuable feedback and for acknowledging the significance of many of our results.

Relation to Ordyniak et al. (KR, November 2024)

We appreciate the reviewer for highlighting the important connection to the recent and highly significant work by Ordyniak et al., published in KR in November 2024. Their work addresses several related concepts that are indeed relevant to ours. While our work was developed independently and focuses on many complementary aspects, we fully recognize the significance of their contributions and agree that our discussion should be improved to better reflect this connection.

We appreciate the reviewer highlighting certain intersections within a few propositions. However, we'd like to emphasize that these represent only a very small portion of our overall contributions and proofs, many of which the reviewer has positively acknowledged. Specifically, after careful examination, we found genuine intersections amounting to no more than 1–2 pages of proofs in total within dozens of pages of our proofs in the full 44-page appendix. Throughout our rebuttal, we will clarify this point with technical details and will further address and elaborate on this important related work in the final version. Nonetheless, we believe these refinements can be effectively addressed in a camera-ready revision, without requiring a new submission.

Technical elaboration. Much of our non-parameterized results are entirely independent of Ordyniak et al., including technically challenging results like Lemma E.5, which resolves a long-standing issue, and a complex dynamic programming algorithm for SHAP under linear models with unary weights.

Our parameterized results focus on three model classes: linear models, neural networks, and decision trees—of which the first two were not studied by Ordyniak et al. A key contribution is our intractability results for ensembles of a constant number of linear models (Pages 31–44), which reveal surprisingly sharp complexity contrasts with decision tree ensembles. We also analyze explanations like CC and SHAP using non-trivial proof techniques. Our analysis goes beyond majority voting to include weighted voting, which involves some intricate constructions. Although there is some intersection with Ordyniak et al. in the parameterized results for CSR/MCR/MSR on decision tree ensembles using majority voting, the bulk of our proofs for these classes are distinct as well—as we elaborate below.

For Proposition 4.2, our proof applies to a broader class of poly-subset-constructible models, including decision trees, linear models, neural networks, and more. We also cover the CC and SHAP queries. While there is some intersection in our results for CSR and MCR, our results for these are mainly corollaries and are not central to the technical core of this proposition—CSR isn’t even listed as a novel contribution of ours in Table 1, and we’ll revise MCR similarly. Finally, for the MSR query, we prove $\Sigma^P_2$-hardness via a non-trivial construction that goes beyond coNP-hardness.

Similarly, Proposition 5.1 applies to the broader class of poly-subset-constructible models—and extends the analysis to CC, SHAP. While the CSR/MSR/MCR results for decision trees intersect, this is again only an extremely brief corollary (lines 1685–1688 only). For Proposition 5.3, we agree on the MCR and CSR hardness proofs and will clarify this. However, our results also present non-trivial membership results—coW[1] for CSR, W[P] for MCR—and additional findings like #W[1]-hardness and membership results for SHAP and CC. We also analyze MSR, showing para-NP-hardness and containment in XNP. Lastly, while we agree Propositions 5.5/6 can be inferred from Ordyniak et al., in our work these too are presented more as direct corollaries rather than central contributions. We can clarify this by revising the very brief quarter-page section in the main text discussing these results, to make their connection to that work more explicit.

Summary. We fully acknowledge the highly valuable contributions of the work of Ordyniak et al. and agree with the reviewer that their work deserves a more thorough discussion. While there are some technical intersections, we believe they are minor. Our main contributions and the current structure of the paper—which emphasize the surprisingly contrasting behaviors across different model families (e.g., linear models vs. decision trees) and offer a nuanced analysis of the complexity gaps between base models and ensembles—can largely remain unchanged. We believe the clarifications regarding the connection to Ordyniak et al. are reasonable to address in a camera-ready revision, without requiring a separate submission. We will incorporate these clarifications by expanding on their work in the introduction, related work, and the relevant sections of the main text and appendix. We thank the reviewer for highlighting this very important point!

We thank the reviewer for the constructive feedback and for recognizing the importance of the results provided in our work.

The importance of complexity separations between base-models and ensembles

While the reviewer acknowledges the importance of some of our unexpected results, such as the substantial complexity differences between ensembles of decision trees and linear models, they question the value of including more intuitive findings — like the complexity gap between base models and their ensembles. We appreciate this and clarify that, although it is intuitive to expect ensembles to be more complex, the exact nature of this complexity gap is not at all well understood. Our results show that while such gaps often appear, they sometimes do not — highlighting the need to understand when and why they arise.

For instance, ensembles of neural networks do not lead to increased complexity, in contrast to ensembles of decision trees and linear models. Furthermore, we demonstrate that the presence of a complexity gap also depends on the type of explanation used — for instance, linear models and their ensembles exhibit no complexity gap under CC and SHAP. It is interesting to note, though, that when the weights of an ensemble of linear models are encoded in unary, the complexity gap for CC and SHAP does reappear. This finding emphasizes the importance of a linear model’s expressiveness in driving this effect and reveals another unexpected insight into how the complexity gap between ensembles and their base models varies across different settings.

To summarize, although the broad distinction between ensembles and base models might be anticipated, our findings reveal various subtle and nontrivial differences across settings — differences that depend on both the model type and the explanation method. This highlights the importance of a thorough and rigorous analysis of this dimension.

What structural properties drive the complexity explosion in linear models versus decision trees?

We thank the reviewer for this insightful question, and we will elaborate on this point further in the final version. Intuitively, decision trees have a leaf structure that allows for enumeration over possible outcomes — this enumeration becomes more complex in ensembles, but the increase is gradual. In contrast, linear models lack a comparable enumerable structure, making it impossible to iterate over possible assignments in a similar way. This leads to the surprising result that even a strikingly small ensemble of linear models can already render interpretation computationally intractable. We agree that exploring alternative base models or more structured approaches that retain the enumerable properties of decision trees is a promising direction for future research. We will include this direction in our final version. An important question moving forward is how to design models that balance expressivity and predictive power with the ability to compute explanations efficiently.

Impact of feature independence

We note that our work follows common conventions used in previous computational complexity studies of SHAP (e.g., [1,2]) and in standard implementations like KernelSHAP [3], by assuming feature independence. As the reviewer correctly pointed out—and as also noted in [1]—relaxing this assumption can render the computation of SHAP intractable. Intuitively, even when using a simple model such as a decision tree, a highly complex and expressive data distribution can dominate the computational burden, ultimately making the SHAP computation hard.

However, recent work [4] has shown that tractability can still be achieved under less expressive, but non-independent distributions, such as those exhibiting Markovian dependencies. Identifying broader classes of non-independent distributions that still allow efficient computation remains an important and interesting research direction. We believe that linking this line of research with our tractability results for SHAP presents a promising direction for future exploration. We appreciate the reviewer for raising this point and will incorporate it as a direction for future exploration.

Improving clarity of points

Following the reviewer’s comments, in the final version, we will enhance the technical presentation of the paper by simplifying some complexity-related notations, clarifying the intuitive expedition of the results, and reducing the density of certain propositions, as suggested. We thank the reviewer for highlighting these points.

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

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

[3] A Unified Approach to Interpreting Model Predictions (Lundberg et al., Neurips 2017)

[4] On the Tractability of SHAP Explanations Under Markovian Distributions (Marzouk et al., ICML 2024)