What makes an Ensemble (Un) Interpretable?
Authors: Shahaf Bassan
Guy Amir
Meirav Zehavi
Guy Katz
Venue: ICML 2025 poster (2025)
Keywords: interpretability
explainable AI
Primary area: social_aspects->accountability_transparency_and_interpretability

Abstract: Ensemble models are widely recognized in the ML community for their limited interpretability. For instance, while a single decision tree is considered interpretable, ensembles of trees (e.g., boosted trees) are often treated as black-boxes. Despite this folklore recognition, there remains a lack of rigorous mathematical understanding of what particularly makes an ensemble (un)-interpretable, including how fundamental factors like the (1) *number*, (2) *size*, and (3) *type* of base models influence its interpretability. In this work, we seek to bridge this gap by applying concepts from computational complexity theory to study the challenges of generating explanations for various ensemble configurations. Our analysis uncovers nuanced complexity patterns influenced by various factors. For example, we demonstrate that under standard complexity assumptions like P$\neq$NP, interpreting ensembles remains intractable even when base models are of constant size. Surprisingly, the complexity changes drastically with the number of base models: small ensembles of decision trees are efficiently interpretable, whereas ensembles of linear models remain intractable, even with a constant number of models. We believe that our findings provide a more robust foundation for understanding the interpretability of ensembles, emphasizing the benefits of examining it through a computational complexity lens.

What makes an Ensemble (Un) Interpretable?
Shahaf Bassan' Guy Amir?
Meirav Zehavi
Guy Katz'
Abstract
imbalanced or noisy datasets effectively (Dong et al., 2020; Sagi & Rokach, 2018).
Ensemble models are widely recognized in the ML community for their limited interpretability. For instance, while a single decision tree is con- sidered interpretable, ensembles of trees (e.g.. boosted trees) are often treated as black-boxes. Despite this folklore recognition, there remains lack of rigorous mathematical understanding of what particularly makes ensemble (un)- interpretable, including how fundamental factors like the (i) number, (ii) size, and (iii) type of base models influence its interpretability. In this work, we seek to bridge this gap by applying concepts from computational complexity theory to study the challenges of generating explanations for vari- ous ensemble configurations. Our analysis uncov- ers nuanced complexity patterns influenced by var- ious factors. For example, we demonstrate that un- der standard complexity assumptions like P NP, interpreting ensembles remains intractable even when base models are of constant size. Surpris- ingly, the complexity changes drastically with the number of basc models: small ensembles of deci- sion trees are efficiently interpretable, whereas in- terpreting ensembles with even constant number of linear models remains intractable. We believe that our findings provide a more robust foundation for understanding the interpretability of ensem- bles, emphasizing the benefits of examining it through computational complexity lens.
However, a significant challenge with ensemble models is their perceived lack of interpretability (Guidotti et al., 2018; Sagi & Rokach, 2021: Hara & Hayashi, 2018; Bénard et al., 2021; Kook et al., 2022). The reason behind this straight- forward - utilizing several models simultaneously makes the decision-making process inherently more complex, and thus more challenging to understand. For instance, while it is feasible to trace the decision-makinn path in a single decision tree, this level of straightforward traceability is not achievable in tree ensembles (Sagi & Rokach, 2021; Hara & Hayashi, 2018; Bénard et al., 2021).
Despite general acknowledgment of this issue in the ML community, some fundamental questions remain regard- ing the precise nature of what makes an ensemble (un)- interpretable. For instance: (i) How much "harder" is it to interpret ensembles compared to their base models? Is the difference in complexity polynomial or exponential? (ii) How does the interpretability of ensembles vary de- pending on the type of explanation used? (iii) How does the interpretability depend on the type of base models? (iv) How do structural parameters, such the number of base models or the size of individual models, influence interpretability? For example, is an ensemble with many small models more interpretable than one with a few large models? Does this answer depend on the explanation type or the nature of the base models? (v) Does simplifying an ensemble by re- ducing the number or the size of base models enhance its interpretability?
In this work, we aim to address these questions by exam- ining the interpretability of ensembles through the lens of computational complexity. The computational investigation of interpretability has been explored in several recent stud- ies (Barceló al., 2020; Bassan et al., 2024; Arenas et al., 2021a; Adolfi et al., 2025). Notably, (Barceló al., 2020) introduced the term "computational interpretability" formal and mathematical approach to assessing interpretabil- ity, distinguishing it from the more common emphasis on human-centerd understanding (Rudin et al., 2022). Within computational interpretability, a model is considered inter- pretable if explanations for its decisions can be generated efficiently (i.e., is "casy" to explain). Conversely, if gen-
1. Introduction
Ensemble learning is widely acclaimed technique in ML that leverages the strengths of multiple models instead of relying on single one. This approach has been proven to enhance predictive accuracy, mitigate variance, and handle
'The Hebrew University of Jerueslaem *Cornell University 2 (Ben-Gurion University of the Negev. Correspondence to: Shahaf Bassan <shahaf, bassan @ muji..ujj..c.il>..
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

What makes an Ensemble (Un) Interpretable?
erating explanations is computationally challenging, the model is classified uninterpretable.
Even ensembles with significantly small base models remain hard to interpret. Interestingly, we demon- strate that in general setting including all the in- stances we examined - ensembles consisting of even constani-size base models remain computationally in- tractable to interpret (e.g., NP, > #P-Hard). From a practical standpoint, this means that even if a practi- tioner attempts to simplify an ensemble by drastically reducing the sizes of its base models, the overall en- semble remains computationally infeasible to interpret, highlighting strikingly negative complexity result.
Our Contributions. We perform a formal analysis to inves- tigate the interpretability of ensemble models by studying the computational complexity of deriving various types of explanations in different settings and comparing these com- plexities to those of their individual base models. Our work encompasses a wide range of complexity scenarios, focus- ing on five distinct explanation types examined in previous research (Barceló et al., 2020; Bassan et al., 2024; Van den Broeck et al., 2022). These include (i) feature selection explanations (covering three relevant forms), (ii) contrastive explanations, and (iii) Shapley value feature attributions.
Even ensembles with only two linear models are al- ready computationally hard to interpret. We present another strong negative complexity result that applies broadly: across all analyzed settings, ensembles of linear models (often regarded as highly interpretable) become intractable to interpret, when consisting of only two linear models. This underscores how rapidly the integration of linear models leads to significant loss of interpretability, resulting in a substantially negative complexity outcome in highly simplified scenario.
We additionally explore broad range of ensemble configu- rations encompassing various interpretability scenarios and examine three key factors: (i) the rype of base model, (ii) the number of base models in the ensemble, and (iii) the size of the base models. To examine diverse base-model types, we focus on three widely used base models that span the extremes of the interpretabiliiyy spectrum: (i) linear models, (ii) decision trees, and (iii) neural networks. To examine the number and size of base models, we explore their impact through concepts from parameterized complexity (Downey & Fellows, 2012), key area of computational complex- ity that examines how various structural parameters affect complexity behavior.
1.2. Positive Complexity Corollaries
Ensembles with a small number of decision trees can be interpreted efficiently. Surprisingly, we ob- serve strikingly different complexity behaviors be- tween ensembles of linear models and those of decision trees. We present more optimistic complexity results, demonstrating that reducing the number of decision trees in an ensemble (e.g.. Random Forests, XGBoostt allows for tractable (poly-time) computation of various explanation types- - unlike in the case of linear models. These findings open the door to practical and efficient algorithmic implementations in this context.
1.1. Negative Complexity Corollaries
Ensembles are computationally hard to interpret (and the explanation type matters). We provide a range of intractability results (NP, Σ #P-Hardness, etc.) for generating multiple types of explanation, for diverse ensembles, emphasizing foundational limita- tions of computing explanations for these models. In- terestingly, within these intractability results, we un- cover substantial complexity differences among the analyzed explanation forms, demonstrating that certain forms are significantll more challenging than others.
We believe these corollaries provide a more rigorous, and mathematically grounded perspective on ensemble inter- pretability. While some of our results confirm common ML beliefs, others reveal unexpected complexity variations based on model type, number, and size, underscoring the importance of complexity analysis in this context.
Ensembles are substantially less interpretable than their base models (but the base model type matters). To demonstrate that the intractability arises from the ensemble aggregation itself, we establish strict com- plexity separations between explaining an ensemble's base models (e.g., linear models, decision trees) which can often be done in polynomial or linear time and explaining the ensembles themselves, which is computationally intractable (e.g., Narh)rd). This high- lights, from a computational standpoint, that ensembles are (exponentially) "less interpretable" than their base models. Interestingly, we also show that no such com- plexity gaps exist for ensembles consisting of more expressive base models like neural networks.
Due to space constraints, we include an outline of our vari- ous theorems and corollaries within the paper, and relegate the complete proofs to the appendix.
2. Preliminaries
Complexity Classes. This paper assumes that readers have basic understanding of standard complexity classes, in- cluding polynomial time (PTIME) and nondeterministic polynomial time (NP and coNP). We also discuss the com- mon class within the second order of the polynomial hier- archy, ET This class contains problems that can be solved
2

---

What makes an Ensemble (Un) Interpretable?
within NP when provided access an oracle capable of solving coNP problems in constant time. It clearly holds that NP, coNP S ; and it is also widely believed that NP, (Arora & Barak, 2009). The paper addition-
regression, SVMs). While our focus is on classification models, many findings also apply regression (see Ap- pendix E), making them relevant for methods like linear regression. Although we primarily address homogeneous ensembles (identical model types), several results extend to heterogeneous ensembles (mixed model types), as detailed in Appendix E.
coNP _ 2 ally discusses the complexity class #P which represents the total count of accepting paths in a polynomial-time nonde- terministic Turing machine. It is widely believed that 2 & #P (Arora& & Barak, 2009).
3.2. Explanation Types
Setting. We consider set of n input features {l..... n), represented by assignments x := (Xi...., Xn). within a fea- ture space F. The classifier f : F F [c], where c E Ni is the number of classes, is analyzed through local explanations that interpret predictions for specific instances x. We note that for clarity, we follow common conventions (Arenas et al., 2021a; Wäldchen et al., 2021; Barceló et al., 2020; Bassan et al., 2024; Adolfi et al., 2025) and assume Boolean inputs and outputs (i.e., F- == (0, 1)", := 1). This simpli- fication aids readability, but our findings extend to discrete or real-valued inputs and multi-class classifiers. See Ap- pendix E for additional information.
We focus on several widely recognized forms of explana- tions from the literature. In line with previous research (Bar- celó et al., 2020; Arenas et al., 2021a; Bassan et al., 2024), we conceptualize each type of explanation as an explain- ability query. An explainability query takes both f and x as imputs and aims to address specific inquiries while providing some type of interpretation for the prediction f(x).
Sufficient reason Feature Selection. We consider the com- mon sufficiency criterion for feature selection, which based on common explainability methods (Ribeiro et al., 2018; Carter et al., 2019; Ignatiev et al., 2019a). A sufficient reason is subset of input features, S C [n]. such that when we fix the features of S to their corresponding values in X E If, then the prediction always remains fx),, regardless of any different assignment to the features in the subset 3. We use the notation of (x3;2g) to denote an assignment where the values x are assigned S and the values of z are assigned to S. We can hence formally define S to be sufficient reason with respect to (f.x) iff it holds that for all z E F: / (xs: = fxx)
3. Base-Model and Explanation Types
We aim to explore the interpretability of ensembles through a computational complexity perspective, encompassing as broad and diverse a range as possible. To achieve this, we analyze the complexity of various ensembles composed of base models spanning different points on the interpretabil- ity spectrum. Additionally, we examine the complexity of generating a wide array of explanation forms commonly studied in the literature.
A typical assumption that is made in the literature suggests that smaller sufficient reasons (that is, those with a lesser cardinality of (SS) are more useful than larger ones (Ribeiro et al., 2018; Carter et al., 2019; Ignatiev et al., 2019a). This leads to a particular interest in obtaining cardinally minimal sufficient reasons, also referred to as minimum sufficient reasons, and consequently to our first explainability query:
3.1. Ensemble and Base-Model Types
We define an ensemble as classification function consisting of k base models, each itself a classification function. Since our focus is on post-hoc explanations, we analyze the ensem- ble's inference process, specifically for majority voting and weighted voting inference. These approaches cover a broad range of ensembles, including boosting, voting, and bagging ensembles (see Appendix B for details). In majority voting, the ensemble prediction is determined by the majority vote among the k base models, while in weighted voting, pre- dictions are aggregated based on weights assigned to each model. We examine three types of base models: (i) axis- aligned decision trees (following conventions (Barceló et al., 2020; Arenas et al., 2021a; Bassan et al., 2024)), (ii) linear classifiers, and (iii) neural networks with ReLU activations. Formal definitions can be found in Appendix B.
MSR (Minimum Sufficient Reason): Input: Model f' input x, and d E N Output: Yes if there exists some S C [n]] such that S is a sufficient reason with respect to (f. x) and |S] < d, and No otherwise.
To provide a comprehensive understanding of the complex- ity results of sufficient reasons, we study two additional common feature selection explainability queries (Barceló et al., 2020; Bassan et al., 2024) which represent refine- ments of the MSR query: (i) The Check- Sarcc--Sfffcient-Reee Reasoon (CSR) query, which, given subset S, checks whether is a sufficient reason; (ii) The Count- Comp--Comtesionss (CC) query, which represents generalized version of the CSR query, where given a subset of features, we return the relative por- tion of assignments that maintain a prediction. This form
This formalization encompasses wide range of ensemble techniques, including random forests, boosted trees (e.g., XGBoost), and other diverse ensembles composed of deci- sion trees, neural networks, or linear models (e.g., logistic
3

---

What makes an Ensemble (Un) Interpretable?
of explanation relates the probability of maintaining a classification. Due space constraints, relegate the full formalization of the CSR and CC queries to Appendix D.
the ensemble's ' constituent base models. We are partieularly interested in cases where there exists strict computational complexity gaps between the two settings (e.g.. solving Q for single base model can be performed in polynomial time, whereas solving it for the ensemble is NP-Complete). Identifying such gaps is particularly important as they pin- point the specific situations where the ensemble aggregation process directly influences the (lack of) interpretability. To identify these gaps, we use the notion of c-interpretabiilty (computational interpretability) as defined in (Barceló et al., 2020)::
Contrastive Explanations. An alternative approach to in- terpreting models involves examining subsets of features which, when modified, could lead to a change in the model's classification (Dhurandhar et al.. 2018: Guidotti, 2022). We consider a subset S _ [n] as contrastive if changing its val- ues has the potential to alter the original classification (x); or, more formally, if there exists some Z E EF for which fxxgizs # fx). Similarly to sufficient reasons, smaller contrastive reasons are generally assumed to be more mean- ingful. These represent the minimum change required to alter the original prediction. Hence, also natural to focus on cardinally-minimal contrastive reasons.
Definition 4.1. Let C₁ and C2 be two classes of models and let Q be an explainability query for which Q(C,) is in complexity class K₁ and Q(C2) is in complexity class K2. We say that Ci is strictly more c-interpretable than C2 with respect to Q iff Q(C2) is hard for the complexity class K₂ and K1 & K2.
MCR (Minimum Change Required): Input: Model f. input and d E N.
4.1. Complexity Gap in Simple Base Models
Output: Yes, if there exists some contrastive reason S such that |S| S d for fx),, and No otherwise.
We begin with examining two types of base-modee known for their simplicity and interpretability - decision trees and linear models. Our results affirm the existence of a complexity gap when an ensemble consists of these base- models, as depicted in Table 1. Our initial complexity results are presented the following proposition, with the proof provided in Appendix F:
Shapley Values. In the additive feature attribution setting, each feature i E [n]] is assigned an importance weight Φi- common method for allocating weights is by using the Shapley value attribution index (Lundberg & Lee, 2017), defined as follows:
Proposition 4.2. Ensembles of decision trees and ensembles of linear models are (i) coNP-Complete with respect to CSR, (ii) NP-Complete with respect to MCR, (iii) D -Complete with respect to MSR, (iv) #P-CCmplet with respect to CC, and (v) # HP-Hard with respect to SHAP.
|S|((= - |S| 1)! (U(SU(i))= n!!
d.(f,))== =
Σ SCNNM
Where the results for majority-voting decision tree ensem- bles under the CSR and MCR queries were shown in (Or- dyniak et al., 2024), and we provide all of the remaining results. Based on these findings, we leverage our previously established notation to deduce an interpretability separation between ensembles of decision trees/linear models and their corresponding base models:
where v(S) is the value function, and we use the com- mon conditional expectation value function vSS) == (f-D,,,(z)) = xs) (Sundararajan & Najmi, 2020; Lund- berg& & Lee, 2017).
In our complexity analysis, we assume feature indepen- dence, which follows common practice in computational complexity frameworks (Arenas et al., 2023; Van den Broeck al., 2022), as well in practical methods for computing Shapley values, such as the KemneSHHA ap- proach in the SHAP library (Lundberg & Lee, 2017). For a complete formalization, refer to Appendix D.
Proof Sketch. We build upon proof from (Izza & Marques- Silva, 2021) that reduces DNF formulas to random forest models to demonstrate that computing prime implicants for random forests is D -Compleec. We expand this by show- ing that DNF formulas can be transformed into ensembles of decision trees or linear models in polynomial time, fitting our broader category of poly-subser constructable functions which efficiently represent any disjunction of literals. We confirm that decision trees and linear models belong to this category and proceed to obtain the complexity of various queries through reductions: particularly, the MSR query re- duction is obtained from the Mhortest-Implican -ore prob- lem (Umans, 2001). We note that while (Audemard et al., 2022b) aims to address the MSR query through a reduction
SHAP (Shapley Additive Explanation): Input: Model f. input x, and E [n] Output: The shapley value (f,x).
4. Ensemble vs. Base-Model Interpretability
We seek to compare the complexity of solving an explain- ability query Q for an ensemble, to that of solving for
4

---

What makes an Ensemble (Un) Interpretable?
Table 1. TThe "complexity gap" when interpreting single model and an ensemble of models the case of decision trees and linear models. Cells highlighted in blue represent novel results, presented here: whereas the rest were already known previously.
Decision Trees
Linear Models
Base-Modee
Ensemble
Base-Modee
Ensemble
Check Sufficient Reason (CSR)
PTIME
coNP-C
PTIME
coNP-C
Minimum Contrastive Reason (MCR)
PTIME
NP-C
PTIME
NP-C
Minimum Sufficient Reason (MSR)
NP-C
CC
PTIME
D -C
Count Completions (CC)
PTIME
#PCC
#P-C
#PC
Shapley Additive Explanations (SHAP)
PТIME
#P-H
#P-C
#P-H
from minimal unsatisfiable sets to DNFs, there is a noted technical gap in this proof (details in Appendix F.5), also observed in other similar proofs (Huang et al., 2021). To the best of our knowledge, we are the first address this issue effectively with non-trivial approach, enabling to confirm 21 Harddnes for DNFs and related ensembles of www-s-ubee-constutaabbl functions.
sult: this holds for any explainability query whose complex- ity class remains consistent under polynomial reductions, including all K-CCmmlete queries within the polynomial hierarchy (e.g.. PTIME, NP, E and their corresponding counting classes (e.g., #P).
Proposition 4.5. There is no explainability query Q for which the class of neural networks is strictly more interpretable than the class of ensemble-neura networks.
Theorem 4.3. Decision trees are strictly more c- interpretable than ensembles of decision trees with respect CSR, MSR, MCR. CC, and SHAP. The same result holds for linear models (and ensembles of linear models) with respect to CSR, MSR, and MCR.
The proof is provided in Appendix H. The result is intuitive: since ensemble of neural networks can be reduced to single network in polynomial time, no distinct complex- ity classes (closed under polynomial reductions) differ in complexity between interpreting a single model and an en- semble. We generalize this property to other models, calling it closed under ensemble construction.
In the previous theorem, there is no complexity gap for the CC and SHAP queries in the context of lincar models. Nevertheless, it is still possible to demonstrate complexity separation if assume that the weights and biases are given in unary form, concept often termed as sseudo-polynonng time. This is demonstrated in the following proposition, with its proof provided in Appendix G.
Definition 4.6. We say that class of models C is closed under ensemble construction if given an ensemble f con- taining models from C, can construct in polynomial time model g C for which Vx F, F, fx) g(x).
Proposition 4.4. While CC and SHAP can be solved in pseudo-pole polyommmal time for linear models, ensembles of lin- ear models remain # H--Hard even if the weights and biases given in unary. Therefore, assuming that the weights and biases are given in unary, linear models are strictly more c-interpretable than ensembles of linear models with respect to CC and SHAP.
Clearly, the aforementioned property correlates the ex- pressiveness of the base model and does not apply to linear models decision trees (assuming P-ANP).
5. Impact of Base-Model Count and Size on Ensemble Interpretability
Proof sketch. The findings for ensembles are derived from those in Proposition 4.2. We base the pseudo-polynomial algorithm for CC on the work of (Barceló al., 2020). Additionally, we achieve similar outcomes for SHAP using a non-trivial dynamic programming algorithm that solves the SHAP query for Perceptrons in pseudo-polynomial time.
Up until now, our analysis did not consider any structural parameters. For example, the MCR query is polynomial- time solvable for a single decision tree, but becomes NP- Complete for an ensemble of models. This raises ques- tions about how different parameters, such as the size of the participating pase-models and the number of base models, contribute to this effect. We explore these aspects by us- ing parameterized complexity (Downey & Fellows, 2012), an important branch of computational complexity theory, to study how different parameters affect the entire com- plexity of interpreting ensembles. We begin by outlining some fundamental concepts in parameterized complexity,
4.2. No Complexity Gap in Complex Base Models
We revealed a complexity gap between interpreting simple models (e.g., decision trees, linear models) and their ensem- ble counterparts. However, our findings show no such gap for neural networks. In fact, we establish a much stronger re-
5

---

What makes an Ensemble (Un) Interpretable?
Intractable settings:
k 2 3-
any base models
K 2
Tractable settings:
any k
Figure 1. Illustration of insights from our parameterized complexity results: even highly simplified ensembles with constant-sizz base models (c.g., three base models) remain intractable interpret. Moreover, ensembles with just two linear models already pose intractability, highlighting the substantial difficulty of interpreting linear model ensembles, even in simplified cases. However, reducing the number of trees tree ensembles (e.g., Random Forest, XGBoost) can make explanation computation tractable the number trees fixed.
which are crucial for this study. In this field, we deal with two-dimensional instances denoted as (X,, k) where X' rep- resents the original encoding, and is a specified parameter. We briefly describe the three main scenarios in parameter- ized complexity.
any 2 3, meaning that even for a significantly small k, the problem is intractable - unlike FPT and XP.
Extensions of parameterized complexity. We briefly men- tion extensions of parameterized complexity counting problems (Flum & Grohe, 2004) and higher orders of the polynomial hierarchy (de Haan, 2019) (e.g.. Eg)). This in- cludes the #W Whiierarchy, extending the W-hierarchy to counting problems, where it believed that FPT & #W[1] Ç # #[[2] S ... # W[P] Ç XP. Similarly, XNP extends XP to the second order of the polynomial hierarchy, with XNP C para-E2 (de Haan & Szeider, 2017). The concept of para- NP also generalizes to other classes, including para-coNP, para- and para-#P (de Haan, 2019), where problem is para-K- K-Hd if it remains XC-Hard when k is constant.
1. Problems solvable in (1) time. This is the best- case scenario concerning the parameter l and includes fixed parameter tractable (FPT) problems concerning k. meaning their complexity is primarily controlled by the parameter k. For example, the Vertex-Cover problem is FPT when & is the vertex cover size, allowing efficient solutions even for large graphs if k is small.
2. Problems solvable in ((()))( time. This class in- cludes XP problems, solvable in ((12))))) time. For fixed k. they are polynomial-time solvable, but large | can make them hard, even for small k. The W-hierarchy (Downey & Fellows, 2012), including [[]] for 2 1 and W[P], pro- vides finer classification within XP. For example, Clique is W[1]-Cos [rmpleeoe Here, t relates to the Boolean circuit depth used in reductions (Appendix C), with W[P] allowing arbitrary depth. It is assumed that FPT Ç. W[1] Ç W[2] C... S XP (Downey& & Fellows, 2012). Thus, XP prob- lems lack FPT algorithms and remain inefficient to solve for W[1]-Hard cases if X'| grows arbitrarily large.
5.1. Impact of Base-Modes Sizes on Ensemble Interpretability
We start by studying how the sizes of an ensemble's base models influence its interpretability. In this setting, we take the size of the largest base model in an ensemble as our parameter k. We prove that with this parameterization, all of the aforementioned explainability queries become intractable already for constant value of k.
3. Problems that NP-Hard when k is constant. At the extreme of the parameterized complexity spectrum is para- NP, representing the highest sensitivity to the parameter k. A problem is para-NP-Hard it remains NP-hard even when & is fixed. Assuming PANP, we have XP C para-NP. For example, the Graph-Coloring problem is NP-Hard for
Proposition 5.1. models, decision trees neural networks, parameterized by the maximal base-model size is (i) para-coNP Complete with respect to CSR, (ii) (iii) para-E? -Complete with respect to MSR, (iv) para-# # P- Complete with respect to CC, and (v) para-# aara-#P P-Hard with respect to SHAP.
An ensemble consisting of either linear
with respect to MCR,
6

---

What makes an Ensemble (Un) Interpretable?
Proof Sketch. The proof appears in Appendix J. To prove Dara-NP/para-coNP hardness for MCR and CSR, we re- duce from the NP-Complete Subset-Sum Problem to the problem of solving CSR/MCR for ensembles consisting of only two Perceptrons. To establish para-5:2- -Hardness for MSR, we employ a more intricate reduction from the lesser- known Generalized Subset-Sum Problem (GSSP) (Schaefer & Umans. 2002; Berman et al., 2002), a 2/ -Complete prob- lem. This reduction demonstrates that solving MSR in ensemble of only five perceptrons is already Hardd
(v) para-# P-Hard with respect SHAP.
5.2.2. THE NUMBER OF DECISION TREES IN AN ENSEMBLE
Unlike ensembles composed of linear models, ensembles of decision trees (including widely used models like random forests and XGBoost) yield more optimistic complexity re- sults. Specifically, explanations become computationally tractable when the number of trees in the ensemble is re- duced. The precise degree of tractability, however, varies depending on the type of explanation:
The results for majority-voting decision tree ensembles un- der the CSR and MCR queries were shown in (Ordyniak et al., 2024), and we present here the remaining results. The proof of Proposition 5.1 appears in Appendix and provides a negative outcome regarding the interpretability of ensem- bles. The proposition implies that the uninterpretability of ensembles is not result of the sizes of the participating base models, but rather of the aggregation process itself, such as the majority vote in voting ensembles. This implies that even if we reduce the size of our corresponding models to a constant size, the ensemble still remains intractable to interpret, and hence uninterpretable from a complexity perspective. This result applies to all of our base-model types, ensembles, and explanation forms.
XP tractable explanations. We demonstrate that four of the five queries analyzed (CSR, MCR, CC, and SHAP) fall within XP, with some also belonging to lower complexity classes in the W-hierarchy (the full proofs are relegated in Appendix K.1).
Proposition 5.3. For ensembles of k-decision trees, (i) the CSR query is co [oW[1]- ICCopllte: (ü) the MCR query is W[1]- Hard and in W[P]: (ii) the CC query is Compleee: and (iv) the SHAP query is # W [1 [1)-dard and in XP.
Proof Sketch. Membership for the CSR query established through a many-to-one FPT reduction the complementary version of the k-Clique problem, while hardness was shown by (Ordyniak et al., 2024). The CC query extends these results, as the counting versions of these tasks are # #[[1] Complete. # [[1 | -Hardness for SHAP can be inferred from the complexity of CC, given that the tractability of SHAP is linked to model counting (Van den Broeck et al., 2022). For membership, a more detailed proof places SHAP within XP, which is made possible by the assumption of feature independence. Specifically, when the distribution is uniform, SHAP is proven to be # W [1] J-Copplete (see Lemma K.6). Lastly, while hardness of the MCR query was demonstrated by (Ordyniak et al., 2024), its membership is established by reducing it to the weighted circuit satisfiability (WCS) problem for circuits with arbitrary depth.
5.2. Impact of Number of Base-Models on Ensemble Interpretability
A more intricate dynamic emerges when we take the num- ber of base models that participate in the ensemble as our parameter k. Table 2 shows our parameterized complexity results under this setting. The results for neural networks are straightforward since they are closed under ensemble construction. Decision trees and linear models however re- veal an interesting trend while linear models lose their tractability with constant number of models in the ensem- ble, tree ensembles tend to remain XP-tractable, meaning they can be solved in polynomial time when the number of base models is fixed. The following subsections explore these findings in more detail.
Intuitively, this result indicates that these types of explana- tions can be computed in polynomial time when the number of trees in the ensemble is fixed. The levels of tractabil- ity, corresponding to different explanation types, align with various classes within the W-hierarchy.
5.2.1. THE NUMBER OF LINEAR MODELS IN AN ENSEMBLE
We find that ensembles of linear models become hard to interpret with only constant number of base-models. In- terestingly, we demonstrate that this property holds quite generally, as it applies across all the explanation types we analyzed, as stated in the following proposition, with the proof provided in Appendix J:
XNP tractable explanations. The only explainability query that is not in XP for tree ensembles the minimum suffi- cient reason (MSR) query. This makes sense since this problem is known to be NP-Hard only for a single decision tree (Barceló et al., 2020), and hence it is Mara-NP-Hard for an ensemble of k trees. However, we can show a similar behavior, by proving its membership in XNP, the variant of XP for the second order of the polynomial hierarchy (Flum & Grohe, 2004). This is illustrated in the following proposi- tion, with its proof provided in Appendix I..
Proposition 5.2. k-ensembles of linear models are (i) para- coNP Complete with respect to CSR: (ii) parm-NP-Complete with respect to MCR; (iii) para- -Complete with respect to MSR; (iv) para-# P-Complete with respect to CC, and
7

---

What makes an Ensemble (Un) Interpretable?
Table Parameterized complexity classes for explainahility queries of ensemble models, parametrized by the numher of models participating in the ensemble, k.
Decision Trees
Linear Models
Neural Networks
Check Sufficient Reason (CSR)
CoW[I]-C
para-coNP-C (k=2)
para-coNP-C (k=1)
Minimum Contrastive Reason (MCR)
WIIH-H, WIP]
para-NP-C (k=2)
para-NP-C (k=1)
Minimum Sufficient Reason (MSR)
para-NP-H (k=1), in XNP
para----- -C (k=5)
para-22-C -C (k=1)
Count Completions (CC)
#W[1J-C
para-ffP-C (k=1)
para-#P-C (k=1)
Shapley Additive Explanations (SHAAP)
#W[1]-H. in XP
para-HP-C (k=1)
Para-IP-C
Proposition 5.4. The MSR query for a k-ensemble of deci- sion trees is para-NP-Hare and in XNP.
of each tree is arbitrarily large), it possible to develop FPT algorithms solve these queries. This follows from the fact that all the aforementioned algorithms have runtime of O(m)). This leads to the following conclusion, which can also be inferred from (Ordyniak et al., 2024) for majority- voting tree ensembles under the CSR and MCR queries and we extend this result to all remaining settings:
Proof Sketch. To prove membership, we devise algo- rithm that initially computes all minimal contrastive rea- sons during a preprocessing phase in (()''() time. In the second phase, the algorithm leverages the Minimal -itting- Set (MHS) duality between sufficient and contrastive rea- sons (Ignatiev et al., 2020b), allowing the algorithm to non- deterministically identify the MHS among all minimal con- trastive reasons.
Proposition 5.6. If the maximal number of leaves in each tree m is constant, there exist FPT algorithms that solve the CSR, MCR, CC, and SHAP queries for k-ensembles of and hence the size of the ensemble [f', is arbitrurily large).
decision trees (even if the size [fal of each
Intuitively, while this query is NP-Hard when ls is constant, its membership in XNP suggests it remains significantly more tractable compared to para-E -Hard problems (as en- countered with the MSR query for ensembles of linear mod- els). When is fixed, these problems can be addressed us- ing NP oracles (e.g.. SAT solvers (Moskewicz al., 2001)), whereas para-Ei; E.- -Hard problems demand worst-case ponential number of queries to such solvers.
5.2.3. TREE ENSEMBLES VS. LINEAR MODEL ENSEMBLES
The previous subsections showed that decision tree and linear model ensembles exhibit very distinct behaviors when parameterized by the number of base models k. giving rise to the following corollary:
Although the MSR query is not in XP, a relaxed version is This version seeks a subset-minimal (or "locally minimal") sufficient reason, i.e., a subset $ _ [n] that a sufficient reason, where removing any from makes it no longer sufficient. This result was previously shown in (Ordyniak al., 2024); in Appendix M, discuss its connection to our other findings.
Theorem 5.7. k-ensemble decision trees are strictly more c- c-interpretable than k-ensemble linear models with respect to CSR, MSR, MCR, CC, and SHAP.
From a practical perspective, if a practitioner seeks to sim- plify an ensemble by reducing the number of base models, this simplification enhances computational interpretability for decision tree ensembles. However, this is not the case for ensembles composed of linear models, where interpretabil- ity becomes intractable even with just two linear models. Notably, these complexity challenges also extend to het- erogeneous ensembles. In other words, any ensemble that includes a mix of model types and only two linear models is already intractable to interpret.
Proposition 5.5. Obtaining subset-minimal sufficient rea- son for a k-ensemble of decision trees is in XP.
FPT tractable explanations. Although the previous XP- tractable explanations are relatively more tractable for tree ensembles (compared to ensembles of linear models) and solvable polynomial time with a fixed number of trees, our results show they are either W[1] or coW[l]-hard. Thus, assuming FPT _ W[1], no FPT algorithms exist to solve these queries in (210()) g(k) time (Downey & Fellows, 2012). Consequently, they are not primarily driven by the pa- rameter & and grow more challenging as tree size increases.
Finally, Proposition 5.6 shows that algorithms for CSR, MCR, CC, and SHAP decision tree ensembles run not only in XP but in FPT time with a fixed number of leaves per tree, even for arbitrarily large input spaces and tree sizes. In contrast, ensembles of linear models remain computation- ally intractable unless the model size- - and thus the input space size is constrained, even with just two models.
However, if we assume that the number of leaf nodes m in each tree bounded by a constant (even if the total size [,s]]
8

---

What makes an Ensemble (Un) Interpretable?
6. Practical Implications
including this work and others, in Appendix A.
While our work is theoretical, it offers key insights for prac- titioners focused on ensemble interpretability. Specifically, we show that generating explanations for ensembles is sub- stantially intractable, with exponential gaps compared to single base-models This remains true even for ensembles with constant-sized base models, indicating that using en- sembles with small base-models alone does not improve interpretability from a computational standpoint. A key practical takeaway, however, is that using ensembles with fewer but deeper trees is computationally more favorable than many shallow ones. This observation can guide tree architecture choices when interpretability is priority. Con- versely, incorporating linear models even with only a few models- - can drastically increase complexity. This un- derscores& a substantial comparative advantage for decision- tree-based ensembles over those using linear models.
Another line of work focuses obtaining explanations with formal guarantees on tree ensembles by encoding them as propositional logic formulas and then solving these queries with Boolean satisfiability (SAT) (Izza & Marques-Silva 2021), Maximum satisfiability (MaxSAT), (Ignatiev et al., 2022), Mixed integer linear programming (MILP) (Parmen- tier & Vidal, 2021; Chen et al., 2019) or satisfiability modulo (SMT) (Ignatiev et al., 2019c) solvers.
Finally, in our work, we used terms that have sometimes ap- peared in the literature under different names. For example, "sufficient reasons" " are also called abductive explanations (Ignatiev et al., 2019b). Subset minimal sufficient reasons are related, though not identical, to prime implicants in Boolean formulas (Darwiche & Marquis, 2002). Similarly, the CC query aligns with the concept of 8-relevant set (Wäldchen et al., 2021; Izza et al., 2021), which identifies whether the completion count exceeds a threshold 8.
More concretely, our tractability results yield polynomial- time algorithms for computing explanations. While some cases are W[I]-, coW[l]-. #W[l]-hard, bounding the number of leaves per tree makes them FPT-tractable, en- abling efficient computation even for arbitrarily large ensem- bles. Many of these tasks also support parallelization, boost- ing performance. Finally, since our problems fall within well-studied classes like W[1], they can be reduced to canon- ical problems like k-Clique, for which effective heuristics already exist (Vassilevska, 2009; Chang, 2019; Chen al., 2019), opening new directions for practical applications.
8. Limitations and Future Work
Similarly to other studies on the computational complexity of obtaining explanations, our work is limited to specific explanation forms and base-model types. However, we believe it still offers a broad overview of various formats and settings, covering diverse facets of ensemble interpretability and laying the groundwork for exploring the complexity of additional forms future work. Moreover, while most of our findings extend from classification to regression, some require further investigation, as discussed in Appendix E, along with other potential extensions and open problems.
7. Related Work
Our work relates to the field of formal XAI, which focuses on explanations with mathematical guarantees (Marques- Silva et al., 2020). Previous studies have explored the com- putational complexity of generating such explanations for various ML models (Barceló et al., 2020; Bassan et al., 2024; Adolfi et al., 2025). Here, we focus on the complexity of ensemble models and their interpretability. Prior work has examined the complexity of interpretations for specific ensembles (e.g., random forests) (Izza et al., 2021; Aude- mard et al., 2022b; 2023; Huang & Marques- Silva,, 2024) and used parameterized complexity to distinguish between shallow and deep neural networks (Barceló et al., 2020) or parameterize explanations by size (Ordyniak et al., 2023). In a more recent and independent study, the notable work by (Ordyniak et al., 2024) examines the complexity of var- ious explainability queries - primarily local and global abductive and contrastive explanations, which correspond to our CSR, MSR, and MCR queries- - under different pa- rameterizations, including those related to majority-voting ensembles of models such as decision trees, lists, and sets. We provide a more technical and comprehensive discus- sion of all relevant prior computational complexity results,
9. Conclusion
We introduce a complexity-theortti framework for evalu- ating the interpretability of ensemble models. Our study encompasses a wide range of popular explanation forms, base-model types, and varying structural parameters, such as the number and size of base models. We believe our findings offer a significantly more rigorous understanding of some of the fundamental factors shaping the interpretabil- ity limitations of ensembles. While some of our results support widely held assumptions in the MI. community, others are unexpected and surprising for instance, the sig- nificantly differing impacts of base-model sizes, numbers, and types across various contexts. These insights provide novel perspective on ensemble interpretability. informing both the practical development of explanation algorithms (the tractable cases) and a deeper understanding of scenar- ios where explanations may be infeasible to obtain (the intractable cases). Overall, we believe that our work un- derscores the importance of computational complexity in advancing our understanding of interpretability in ML.
9

---

What makes an Ensemble (Un) Interpretable?
Impact Statement
Arenas, M., Barceló, P., Bertossi, L.,, and Monet, M. On the Complexity of SHAP-Score-Baser Explana- tions: Tractability via Knowledge Compilation and Non- Approximability Results. Journal of Machine Learning Research (JMLR), 24(63):1-58, 2023.
We acknowledge the potential social implications of inter- pretability, Our work provides a deeper understanding of the circumstances under which explanations can or cannot be obtained efficiently. However, our work is predominantly theoretical, we believe it does not have any immediate or direct social ramifications.
Arora, S. and Barak, B. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
Audemard, G., Bellart, S., Bounia, I.., Koriche, F., Lagniez, J.-M., and Marquis, P. On Preferred Abductive Explana- tions for Decision Trees and Random Forests. In Proc. 31 Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 643-650,24 2022a.
Acknowledgments
This work was partially funded by the European Union (ERC, VeriDeL, 101113).... Views and opinions expressed however those of the author(s) only and do not neces- sarily 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). The work of Amir was further supported by scholarship from the Clore Israel Foundation.
Audemard, G., Bellart, S., Bounia, L.., Koriche, F., Lagniez, J.-M., and Marquis, P. Trading Complexity for Sparsity in Random Forest Explanations. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 5461-5469, 2022b.
Audemard, G., Lagniez, J.-M., Marquis, P., and Szezepan- ski, N. Computing Abductive Explanations for Boosted Trees. In Proc. 26th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 4699-4711, 2023.
References
Adolfi, F., Vilas, M., and Wareham, T. The Computational Complexity of Circuit Discovery for Inner Interpretability. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
Barceló, P., Monet, M., Pérez, J., and Subercaseaux, B. Model Interpretability through the Lens of Computational Complexity. Proc. 33rd Int. Conf. on Advances in Neural Information Processing Systems (NeurlPS), pp. 15487- 15498, 2020.
Alvarez Melis, D. and Jaakkola, T. Towards Robust In- terpretability with Self- Neural Networks. In Proc. 31st Int. Conf. on Advances in neural information processing systems (Neurips), 2018
Barceló, P., Kozachinskiy, A., Orth, M., Subercaseaux, B., and Verschae, J. Explaining k-Nearest Neighbors: Abduc- tive and Counterfactual Explanations. 2025. Technical Report. https: / //a///iivvv////// 2501 06078.
Amir, G., Bassan, S., and Katz, G. Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation. In Proc. 27th European Conf. on Artificul Intelligence (ECAI), 2024.
Barrett, C. and Tinelli, C. Satisfiability Modulo Theories. Handbook of model checking, pp. 305-343, 2018.
Bassan, S. and Katz, G. Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks. In Proc. Int. Conf. on Tools and Algorithums for the Con- struction and Analysis of Systems CicemssTAAAA (TACAS), pp. 187-207, 2023.
Arenas, M., Baez, D., Barceló, P., Pérez, J., and Suber- caseaux, B. Foundations of Symbolic Languages for Model Interpretability. Proc. 34th Int. Conf. Advances in Neural Information Processing Systems (NeurIPS), pp. 11690-11701, 2021a.
Bassan, S., Amir, G., Corsi, D., Refacli, I., and Katz, G. Formally Explaining Neural Networks Within Reactive Systems. In Proc. 23rd Int. Conf. on Formal Methods in Computer-Aided Design (FMCAD), pp. 1-13, 2023.
Arenas, M., Barceló, P., Bertossi, L., and Monet, M. The Tractability of SHAP-Score-Baar Explanations for Clas- sification Over Deterministic and Decomposable Boolean Circuits. In Proc. 35th AAAI Conf. on Artificial Intelli- 2021b.
Bassan, S., Amir, G., and Katz, G. Local vs. Global Inter- pretability: A Computational Complexity Perspective. In Proc. 41st Int. Conf. on Machine Learning (ICML), 2024.
gence, pp.
Arenas, M. Barceló, P., Romero, M., and Subercaseaux, B. On Computing Probabilistic Explanations for Decision Trees. Proc. 35th Int. Conf. on Advances in Neural Infor- mation Processing Systems (NeurIPS), pp. 28695-28707, 2022.
Bassan, S., Elboher, Y. Y., Ladner, T., Althoff, M., and
Katz, G. Explaining. Fast and Slow: Abstraction and Refinement of Provable Explanations. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025a.
10

---

What makes an Ensemble (Un) Interpretable?
Bassan, S., Eliav, R., and Gur, S. Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons. In Proc. 13th Int. Conf. on Learning Represen- tations (ICLR), 2025b.
Chockler, H., Kelly, D., Kroening, D., and Sun, Y. Causal Explanations for Image Classifiers. 2024. Technical Report, https: hat//:aaivviii:1111 http:///axxv:::210399893 08877
Cooper, M. C. and Marques- ing Classifier Decisions. Artificial Intelligence, 2023.
Tractability of Explain-
Bassan, S., Gur, S., Zeltyn. S., Mavrogiorgos, K., Eliav, R., and Kyriazis, D. Self- Explainnng Neural Networks for Business Process Monitoring. 2025c. Technical Report.
Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. Param- eterized Algorithms, volume Springer, 2015.
https: /atps://arxiv:: 2800.
Bénard, C., Biau, G., Da Veiga, S., and Scornet, E. Inter- pretable Random Forests via Rule Extraction. In Proc. 24th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 937-945, 2021.
Darwiche, A. and Hirth, A. On the Reasons Behind Deci- sions. In Proc. 24th European Conf. on Artifical Intelli- gence (ECAI). pp. 712-720, 2020.
Berman, P., Karpinski, M., Larmore, L., Plandowski, W., and Rytter, W. On the Complexity of Pattern Matching for Highly Compressed Two-Dimensn Wwo-Dimensional Texts. Journal of Computer and System Sciences, 65(2):332-350, 2002.
Darwiche, A. and Ji, C. On the Computation of Necessary and Sufficient Explanations. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 5582-5591, 2022.
Darwiche, A. and Marquis, P. A Knowledge Compilation Map. Journal of Artificial Intelligence Research (JAIR), 17:229-264, 2002.
Bhattacharjee, R. and Luxburg, U. Auditing Local Expla- nations is Hard. In Proc. 37th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp- 18593-18632, 2024.
de Haan, R. Parameterized Complexity Results for the Ke- meny Rule in Judgment Aggregation. In Proc. 22nd Eu- ropean Conf. on Artificial Intelligence (ECAI), pp. 1502- 1510, 2016.
Blanc, G., Lange, J., and Tan, L.-Y. Provably Efficient, Succinct, and Precise Explanations. In Proc. 35th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 6129-6141, 2021.
de Haan, R. Parameterized Complexity in the Polynomial Hierarchy. Springer, 2019.
Blanc, G., Koch, C., Lange, J., and Tan, L.-Y. A Query- Optimal Algorithm for Finding Counterfactuals. In Proc. 39th Int. Conf. on Machine Learning (ICML), pp. 2075- 2090, 2022.
de Haan, R. and Szeider, S. Parameterized Complexity Classes Beyond Para-NP. Journal of Computer and Sys- tem Sciences, 87:16-57, 2017.
Bounia, L. and Koriche, F. Approximating Probabilistic Explanations via Supermodular Minimization. In Proc. 39th Int. Conf. on Uncertainty in Artificial Intelligence (UAI), pp. 216-225, 2023.
Dhurandhar, A., Chen, P.-Y., Luss, R., Tu, C.-C., Ting, P., Shanmugam, K., and Das, P. Explanations Based on the Missing: Towards Contrastive Explanations with Pertinent Negatives. In Proc. 31st Int. Conf. on Advances Neural Information Processing Systems (NeurIPS), 2018.
Calautti, M., Malizia, E., and Molinaro, C. On the Com- plexity of Global Necessary Reasons to Explain Classi- fication. 2025. Technical Report. https: 2501. 06766.
Dick, K., Hall, S., and Umans, C. Improved Inapproxima- bility Factors for Some Σ p, 2009. Technical Report.
Carter, B., Mueller, J., Jain, S., and Gifford, D. What Made You Do This? Understanding Black-Box Decisions with Sufficient Input Subsets. In 22nd Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 567-576, 2019.
Dong, X., Yu, Z., Cao, W., Shi, Y., and Ma, Q. A Survey on Ensemble Learning. Frontiers of Computer Science, 14: 241-258, 2020.
Downey, R. and Fellows, M. R. Parameterized Complexity. Springer Science & Business Media, 2012.
Chang, L. Efficient Maximum Clique Computation Over Large Sparse Graphs. In Proc. 25th ACM Int. Conf. Knowledge Discovery & Data Mining (SIGKDD), pp. 529-538, 2019.
Flum, J. and Grohe, M. Describing Parameterized Com- plexity Classes. Information and Computation, 187(2): 291-319, 2003.
Chen, H., Zhang, H., Si, S., Li, Y., Boning, D., and Hsich, C.-.. Robustness Verification of Tree-Based Models. In Proc. 32nd Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2019.
Flum, J. and Grohe, M. The Parameterized Complexity of Counting Problems. SIAM Journal on Computing, 33(4): 892-922, 2004.

---

What makes an Ensemble (Un) Interpretable?
Gorji, N. and Rubin, S. Sufficient Reasons for Classi- fier Decisions in the Presence of Domain Constraints. In Proc. AAAI Conference Artificial Intelligence, pp. 5660-5667, 2022.
Ignatiev, A., Izza, Y., Stuckey, P. J., and Marques-Sitva, J. Using MaxSAT for Efficient Explanations of Tree Ensem- bles. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 3776-3785, 2022.
Guidotti, R. Counterfactual Explanations and how to find them: Literature Review and Benchmarking. Data Min- ing and Knowledge Discovery, pp. 1-55, 2022.
Izza, Y. and Marques-Silva, J. On Explaining Random Forests with SAT. In Proc. 30th Int. Joint Conf. on Artifi- cal Intelligence (IJCAI), 2021.
Guidotti, R., Monreale, A., Ruggieri, S., Turini, F., Gian- notti, F., and Pedreschi, D. A Survey of Methods for Explaining Black Box Models, ACM computing surveys (CSUR), 51(5):1 42, 2018.
Izza, Y., Ignatiev, A., Narodytska, N., Cooper, M., and Marques-Shn SSlva, J. Efficient Explanations with Rele- vant Sets. 2021. Technical Report. mitts:///arke
Hara, S. and Hayashi, K. Making Tree Ensembles Inter- pretable: A Bayesian Model Selection Approach. In Proc. 21st Inf. Conf. on artificial intelligence and statistics (AIS-
Izza, Y., Huang, x., Ignatiev, A., Narodytska, N., Cooper, M., and Marques-Silva, J. On Computing Probabilistic Abductive Explanations. Int. Journal of Approximate Reasoning, 159:108939; 2023.
TATS), pp. 77-85, 2018.
Huang, X. and Marques-Silva, J. Updates the Complexity of SHAP Scores. In Proc. of the 33rd Int. Joint Conf. Artificial Intelligence (IJCAI), pp. 403-4444440 412, 2024.
Izza, Y., Huang, X., Morgado, A., Planes, J., Ignatiev, A., and Marques-Silvaa J. Distance- Restricted Explanations: Theoretical Underpinnings & Efficient implementation. In Proc. 21st Int. Conf. on Principles of Knowledge Rep- resentation and Reasoning (KR), pp. 475-4855--668 2024.
Huang, X. Izza, Y., Ignatiev, A., and Marques- Silva, J. On Efficiently Explaining Graph-Based Classifiers. In Proc.
18th Int. Conf. on Principles of Knowledge Representa- tion and Reasoning (KR), 2021.
Jin, H., Xue, A., You, W., Goel, S., and Wong, E. Probabilis- tic Stability Guarantees for Feature Attributions. 2025, Technical Report. https: aar//rrvvvvv/////////ea////aaavt : 2504. 13787.
Huang, X., Cooper, M., Morgado, A., Planes, J., and Marques-Silye Silva, J. Feature Necessity & Relevancy in ML Classifier Explanations. In Proc. 29th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 167-186, 2023.
Katz, G., Barrett, C., Dill, D. L., Julian, K., and Kochen- derfer, M. J. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. In Proc. 29th Inf. Conf. on Computer Aided Verification (CAV), pp. 97-117, 2017.
Ignatiev, A., Narodytska, N., and Marques-Silva, Abduction-Baann Explanations for Machine Learning Models. In Proc. 33rd AAAI Conf. on Artificial Intel- ligence, number 01, pp. 1511-1519, 2019a.
Kook, L., Götschi, A., Baumann, P. F., Hothorn, T., and Sick, B. Deep Interpretable Ensembles. 2022. Technical Report. /ettps://axivv:::e 12729.
Ignatiev, A., Narodytska, N., and Marques-Silvaa J. On Relating Explanations and Adversarial Examples. In Proc. 32nd Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2019b.
La Malfa, F.,, Zbrzezny, A., Michelmore, R., Paoletti, N., and Kwiatkowska, M. On Guaranteed Optimal Robust Explanations for NLP Models. In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), pp.
2021.
Ignatiev, A., Narodytska, N., and Marques-Sile Silva,, J. On Validating, Repairing and Refining Heuristic MI. Expla- nations. 2019c. Technical Report. https://aaat //axiv: 1907.02505.
Lundberg, S. and Lee, S.-L. A Unified Approach to Interpret- ing Model Predictions. Proc. 30th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2017.
Ignatiev, A., Cooper, M., Siala, M., Hebrard, E., and Marques-Silee Silva, J. Towards Formal Fairness in Machine Learning. In Proc. 26th Int. Conf. on Principles and Practice of Constraint Programming (CP), pp. 2020a.
Marques-Sike Silva,, and Ignatiev, A. Delivering Trustworthy AI through formal XAI. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp.
2022.
Marques-Silva, J., Gerspacher, T., Cooper, M., Ignatiev, A., and Narodytska, N. Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay. Proc. 33rd Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 20590-20600 2020.
Ignatiev, A., Narodytska, N., Asher, N., and Marques-Sike J. From Contrastive to Abductive Explanations and Back Again. In Proc. Int. Conf. of the Italian Association for Artificial Intelligence, pp. 2020b.
12

---

What makes an Ensemble (Un) Interpretable?
Marques-Silva, J., Gerspacher, T., Cooper, M. C., Ignatiev, A., and Narodytska, N. Explanations for Monotonic Classifiers. In Proc. 38th Int. Conf. Machine Learning (ICML), pp. 7469-7479, 2021.
Subercaseaux, B., Arenas, M., and Meel, K. Probabilistic Explanations for Linear Models. In Proc. 39th AAAI Conf. on Artificial Intelligence, number 19, pp. 20655-20662, 2025.
Marzouk, R. and De La Higuera, C. On the Tractability of SHAP Explanations under Markovian Distributions. In Proc. 41st Int. Conf. on Machine Learning (ICML), pp. 2024.
Sundararajan, M. and Najmi, A. The Many Shapley Val- ues for Model Explanation. In Proc. 37th Int. Conf. on Machine Learning (ICML), pp. 9269-9278, 2020.
Umans, C.
The Minimum Equivalent DNF Problem and Shortest Implicants. Journal of Computer and System Sciences, 63(4):597-611, 2001.
Marzouk, R., Bassan, S., Katz, G., and la Higuera, D. On the Computational Tractability of the (Many) Shapley Values. In Proc. 28th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), 2025.
Valiant, L. The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing, 8(3):410-211, 1979.
Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., and Malik, S. Chaff: Engineering an efficient SAT solver. In Proc. 38th Annual Design Automation Conf., pp. 530- 535, 2001.
Van den Broeck, G., Lykov, A., Schleich, M., and Suciu, D. On the Tractability of SHAP Explanations. Journal of Artificial Intelligence Research (JAIR), 74:851-880 2022.
Ordyniak, S., Paesani, G., and Szeider, S. The Parameter- ized Complexity of Finding Concise Local Explanations. In Proc. 32nd Int. Joint Conf. on Artificial Intelligence (IJCAI), 2023.
Vassilevska, V. Efficient Algorithms for Clique Problems. Information Processing Letters, 109(4):254-257, 2009.
Ordyniak, S., Paesani, G., Rychlicki, M., and Szeider, S. Explaining Decisions in ML Models: A Parameterized Complexity Analysis. In Proc. 21st Int. Conf. on Princi- ples of Knowledge Representation and Reasoning (KR), pp. 563-573, 2024.
Wäldchen, S., Macdonald, J., Hauch, S., and Kutyniok, G.
The Computational Complexity of Understanding Binary Classifier Decisions. Journal of Artificial Intelligence Research (JAIR), 10:351-387,2022
Parmentier, A. and Vidal, T. Optimal Counterfactual Expla- nations in Tree Ensembles. In Proc. 38th Int. Conf. on Machine Learning (ICML), pp. 8422-8431, 2021.
Wang. E.,, Khosravi, P., and Van den Broeck, G. Probabilistic Sufficient Explanations. In Proc. 30th Int. Joint Conf. on Artificial Intelligence (IJCAI), 2021a.
Ribeiro, M., Singh, S., and Guestrin, C. Anchors: High- Precision Agnes-Ag Explanations. In Proc. 32nd AAAI Conf. on Artificial Ontelligence, 2018.
Wang. S., Zhang, H., Xu, K., Lin, X., Jana, S., Hsieh, C.-J,, and Kolter, J. Z. Beta-Crown: Efficient Bound Propagation with Per-Neuron Split Constraints for Neural Network Robustness Verification. In Proc. 35th Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 99909-29921, 2021b.
Rudin, C., Chen, C., Chen, Z., Huang, H., Semenova, L.,, and Zhong, C. Interpretable machine learning: Funda- mental principles and 10 grand challenges. Statistic Sur- veys, 16:1-85, 2022.
Wu, H., Isac, O., Zeljic, A., Tagomori, T., Daggitt, M., Kokke, W., Refaeli, I., Amir, G., Julian, K., Bassan, S., al. Marabou 2.0: A Versatile Formal Analyzer of Neural Networks. In Proc. 36th Int, Conf. on Computer Aided Verification (CAV), pp. 249-264, 2024a.
Sagi, O. and Rokach, L. Ensemble Learning: A Survey. Wiley Interdisciplinary Reviews: Data Mining and Knowl- edge Discovery, 8(4):c1249, 2018
Sagi, O. and Rokach, L. Approximating XGBoost with an Interpretable Decision Tree. Information Sciences, 572: 522-542, 2021.
Wu, M., Wu, H., and Barrett, C. Verix: Towards Verified Explainability of Deep Neural Networks. In Proc. 36th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2024b.
Sälzer, M. and I Lange, M. Reachability is NP-complete even for the Simplest Neural Networks. In Proc. 15th Int. Conf. on Reachability Problems (RP). pp. 149-164, 2021.
Xue, A., Alur, R., and Wong, E. Stability Guarantees for Feature Attributions with Multiplicative Smoothing. In Proc. 36th Int. Conf. on Advances Neural Information Processing Systems (Neurips), pp. 62388 008466221,,1-1 2023.
Schaefer, M. and Umans, C. Completeness in the Polyno- mial Time Hierarchy: A Compendium. SIGACT news, 33
(3):32-49, 2002.
13

---

What makes an Ensemble (Un) Interpretable?
Yu, J., Ignatiev, A., Stuckey, P. J., Narodytska, N., and
Marques-Silvas J. Eliminating the Impossible, Whatever Remains Must be True: On Extracting and Applying Background Knowledge in the Context of Formal Expla- nations. In Proc. 37th AAAI Conf. on Artificial Intelli gence, number pp. 4123-4131 2023.
14

---

What makes an Ensemble (Un) Interpretable?
Appendix
The appendix contains formalizations and proof' that were mentioned throughout the paper:
Appendix contains an extended discussion of related work.
Appendix B contains formalizations of base-model types and ensembles.
Appendix C contains background on parameterized complexity.
Appendix D contains additional formalizations concerning explainability queries.
Appendix E contains information regarding possible expansions of our framework to (i) discrete and continuous input/output domains, (ii) regression tasks, and (iii) heterogeneous ensembles.
Appendix contains the proof of Proposition 4.2.
Appendix G contains the proof of Proposition 4.4.
Appendix H contains the proof of Proposition 4.5.
Appendix contains the proof of Proposition 5.1.
Appendix J contains the proof of Proposition 5.2.
Appendix K contains the proof of Proposition 5.3.
Appendix L contains the proof of Proposition 5,4.
Appendix M contains the proof of Proposition 5.5.
A. Extended Related Work
This section provides a more detailed discussion of related work and key complexity results explored in previous research.
The Complexity of Computing Explanations. Our work builds on a growing body of research analyzing the computational complexity of generating various types of explanations with different guarantees across a wide range of MI. models (Barceló
et al., 2020; Amir al., 2024; Bhattacharjee & Luxburg, 2024; Adolfi al., 2025; Blanc et al., 2022; Huang et al., 2023; Arenas et al., 202 Cooper & Marques-Silvaz 2023). Prior studies have examined the complexity of computing explanations based on sufficiency (Barceló et al., 2020; Bassan et al., 2024), contrastiveness (Blanc et al., 2022; Cooper & Marques-Silva 2023; Barceló et al., 2020), Shapley values (Marzouk et al., 2025; Marzouk & De La Higuera, 2024; Van den Broeck et al.,
2022; Arenas et al., 2023), and probabilistic reasoning (Izza et al., 2023; Blanc et al., 2021; Wäldchen et al., 2021). These analyses span a variety of model classes - from inherently interpretable models like linear classifiers (Subercaseaux et al., et al., 2021), KNNs (Barceló et al., 2025), and decision trees (Bounia & Koriche, 2023; Arenas al., 2022; Huang et al., 2021)- to more complex black-box models such neural networks (Adolfi et al.,
2025), monotonic models (Marques-Sine
2025; Bassan al., 2024; Barceló al., 2020), where the computational challenges are typically greater.
The Complexity of Computing Explanations for Ensembles. Most closely related to our work are studies that analyze the complexity of generating explanations for ensemble models. Notably, (Izza & Marques Silva,, 2021) show that computing a subset-minimal sufficient reason for a random forest is DP -complete, a result extended by (Audemard et al., 2023) to weighted voting ensembles. The significant work of Audemard et al. (2022b) establishes complexity results for sufficient and contrastive reasons in majority-voting tree ensembles - results we expand upon in the relevant sections. More recently, the highly notable work of (Ordyniak al., 2024) provide a thorough parameterized complexity analysis for majority-voting ensembles of decision trees, decision lists, and sets, considering both explanation-size parameters and structural parameters of the models. We elaborate on the connection to their results throughout the paper and in the appendix. Lastly, both (Huang & Marques-Silve 2024) and (Marzouk et al., 2025) analyze the complexity of computing SHAP values on different models, which include tree ensembles; our work extends these findings by exploring additional ensemble settings and introducing new parameterized results.
Formal XAL. More broadly, our work lies within the subfield of formal XAI (Marques-Siee Silva Ignatiev, 2022), which seeks to provide explanations for ML models with formal guarantees (Ignatiev et al., 2020a; Bassan & Katz, 2023; Darwiche & Hirth, 2020; Darwiche & Ji, 2022; Ignatiev al., 2019a; Audemard et al., 2022a; Bassan et al., 2025a). Such explanations are typically obtained using formal reasoning tools like SMT solvers (Barrett & Tinelli, 2018) (e.g., for tree ensembles (Audemard et al., 2022b)) or neural network verifiers (Katz et al., 2017; Wu et al., 2024a; Wang et al., 2021b) (e.g., for neural networks (Izza et al., 2024; Bassan et al., 2023)), or by performing other manipulations such as relaxing the sufficiency definitions (Jin et al., 2025; Izza et al., 2023; Wang et al., 2021a; Chockler et al., 2024; Jin et al., 2025), applying smoothing (Xue et al., 2023), or using self-explaining methods (Bassan et al., 2025b; Alvarez Melis & Jaakkola, 2018:
15

---

What makes an Ensemble (Un) Interpretable?
Bassan et al., 2025c). A central concern in the area of Formal XAT is the computational complexity of generating these explanations (Barceló al., 2020; Wäldchen et al., 2021; Cooper & Marques-Silva, 2023; Bassan et al., 2024; Blanc et al., 2021; Amir et al., 2024; Adolfi et al., 2025; Barceló et al., 2025; Calautti et al., 2025; Ordyniak et al., 2023).
B. Ensembles and Base-Mode! Types
In this appendix, we describe the various ensembles that are incorporated in our work and the corresponding base-model types that consist in these models.
B.1. Ensemble Formalization
Numerous well-known ensemble techniques exist; however, our research is geared towards post-hoc interpretation, thus we emphasize the inference phase rather than the training of these ensembles. Our analysis focused on ensemble families that utilize either majority voting weighted-voting methods during inference. This includes bagging ensembles such random forests, which implement segjority-voting-oee Adaboost, which employ weighted voting for inference. Moreover, we will examine how all of our results hold to either hari-voting or soft-voting inference as well as the potential to apply our findings to alternative inference techniques such as weighted averaging, or meta-model decision inference. Such inference techniques are commonly found in other ensemble types like stacking ensembles, or those utilized in regression tasks.
inference, and boosting ensembles like XGBoost, Gradient Boosting, and
Majority Voting Inference.
In majority voting inference, the condition f(x) 1 is satisfied if and only if there are least [ base-models within an ensemble f where f((x) 1. Put simply, the decision for fx) is determined by the majority consensus of the models involved in f. Formally, for any x E FF we define f as follows:
f(x) f(x)= - {
if K (((1)(x)=1)) = H = otherwise
2 [2
(2)
Weighted Voting Inference.
For weighted voting inference, consider weight & E Q that describes the importance of each model participating in the ensemble. Considering this is binary classification, we can define the prediction as being determined by the sign of the total aggregation of all weights. Formally, for any x E F we define f as follows:
[(x) = slep( Σ fxx)x(x))
(3)
15t5n
where step(z) = + z z2 0.
Weighted voting is harder than majority voting: When examining the explainability query Q, our analysis aims to evaluate the complexity classes of two families of ensembles: majority voting ensembles, denoted as CM, and weighted voting ensembles, denoted as Cw. It is straightforward to demonstrate that the following relationship is true:
Lemma B.1. Let C denote class of models, CM the class of majority voting ensembles of models from C, and Cw. the class of weighted voting ensembles of models from C. Then for any explainability query Q it holds that Q(C)) Sp Q(Cw).
Proof. The lemma holds by simple reduction that starts with majority voting ensemble and constructs weighted voting ensemble f' where each weight is assigned an equal attribution. In other words: of for all i E [n].
The previous statement holds technical significance as it simplifies the process of establishing complexity class completeness results for both CM and Cw:
Observation 1. For proving that the complexity of solving both Q(Cx)) and Q(Cw) are complete for some complexity class K. (closed under polynomial reductions), suffices to prove membership for (Cw) and hardness for (CCm)
16

---

What makes an Ensemble (Un) Interpretable?
From this point forward, whenever we mention the computational complexity of ensemble of models in our text, it applies to both majority voting ensembles and weighted voting ensembles, as we prove the completeness of complexity classes for both families. We highlight this differentiation in our proofs, which are applicable to both types of ensembles.
Extension to Soft Voting. In contrast to hard voting that is common in the binary classification setting, within probabilistic classification soft voting can also be implemented. In this case, each model fi in the ensemble outputs some given probability value i.e, Si [0, 1]. Then, in the case of majority soft voting, the inference is computed by:
fi(()
[(x) = slep( Σ
(4)
15:5n
whereas in weighted seft voting the inference is computed by incorporating equation for each fi FFFFF + [0, 1].
We start by defining property that will be used in the next lemma. We say that a class of models f F [0, 1] is scalar multiplicatiiee if given some constant À E IK and for all f E C. we construct, in polynomial time model I' E C for which f Xf-
Lemma B.2. Let C denote class of models, Cw the class of weighted (hard) voting ensembles of models from C. Csw. the class of (soft) weighted voting ensembles of models from C, and CsM., the class of (soft) majority voting ensembles of models from C. Then for any explainability query Q it holds that Q(Cw) =p Q(Csw) =p Q(Csm). The only restriction is for the condition ((Cw) 2p Q(CsM) and it is that Cw is scalar multiplicative.
Proof. Given soft majority voting ensemble f. we can construct a weighted hard (voting) ensemble f' for which each weight (x) ;= [i(x) For the other direction, given weighted hard (voting) ensemble f. and assuming that Cw is scalar multiplicative, we can construct soft majority voting ensemble f'. We do this by, for every E [m], constructing [x) = Φ: fi(x) (since Cy being scalar multiplicative.. Overall, from these two reductions, we get that Q(Cw) = (C
For the second part of the claim - we start with a weighted hard voting ensemble and construct weighted soft voting ensemble f' by assigning each weight (x)x) = (x)x)) For the other direction, given a weighted soft voting ensemble f we construct a weighted hard voting ensemble f by setting (x(x) == (x(x) fx(). Overall, this implies that Q(Cw) =p QCCsw).
Lemma B.2 establishes that our proof' (including those for membership and hardness) apply seft-voting ensembles, both for majority and weighted voting scenarios. This is because our proofs are conducted within the framework of weighted (hard voting ensembles), and all the complexity classes we consider are closed under polynomial reductions.
(Weighted) Averaging. In the regression setting, another common inference technique involves weighted averaging of all base-model predictions. Formally, given set of regression base-models f; + R. then we define f by incorporating equation over each ft. In essence, this is the same formalization as that of majority soft voting, and hence Lemma B.2 focus regression, must also consider
holds for this family of inference models well. However, when shifting different formalizations of some of the query forms discussed in our paper, such as the definition of a sufficient reason. We discuss these specific adjustments for the regression setting under Appendix E.
Meta learner decision. Another common ensemble inference method often used in stacking ensembles involves employing meta-model to aggregate the outputs of the k base models. In our particular scenario, this involves model g {0, 10, + {0, 1), which is trained to classify the outputs from each base model f. within specified domain. It is important to note that if g can function as a majority voting system among the k models - a capability all analyzed model types possess, including neural networks, linear classifiers, and decision trees - then all the hardness findings discussed in this paper automatically apply to this setup as well. For instance, a stacking ensemble comprising a constant number of linear base-models remains intractable to interpret, as demonstrated in Proposition 5.2. However, the examination of membership results that were presented in this paper will vary depending on the type of model used for the meta-model g.
17

---

What makes an Ensemble (Un) Interpretable?
B.2. Base-Model Types
In this subsection, we formalize the three base-model types that were analyzed throughout the paper: (i) (axis-aligned) decision trees, (ii) linear classifiers, and (iii) neural networks with ReLU activations.
Decision Trees. We regard a decision tree is an acyclic-directed graph and serves as a graphical model for the function f. This graph embodies the given Boolean function in the following manner: (i) Each internal node e is associated with unique binary input feature from the set {..... r . (ii) Every internal node v has precisely two outgoing edges, corresponding to the values (0. }} which are assigned to u; (iii) In the decision tree, each variable is encountered no more than once on any given path a; (iv) Each leaf node is labeled either True or False.
Thus, assigning a value the inputs x E F uniquely determines specific path a from the root to a leaf in the decision tree. The function f(x) is assigned 1 if the terminal node leaf is labeled True, and 0 if it is labeled False. The size of the decision tree, denoted as [/] is measured by the total number of edges in its graph. We additionally assume that the decision tree permits different varying orderings of the input variables {1....,n) _ across any two distinct paths, a and a'. This ensures that no two nodes along any single path a share the same label.
Neural Networks. We focus on neural networks with ReLU activations. It is straightforward to show that any neural network using ReLU activations can be straightforwardly transformed into a fully connected network by assigning "missing" connections weight and bias of for any non- conneceee neurons. Following standard conventions (Barceló et al., 2020; Bassan al., 2024; Adolfi al., 2025), we assume the network is fully connected. In other words, our analysis pertains to multi-layer perceptrons (MLPs). Formally, an MLP, denoted by f, consists of t - 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 وهه) to the linear combination of the outputs from the previous layer g(و-1), the corresponding weight matrix WU), and the bias vector (00, This is represented as g(و) := أام ( (g((5-)) + B60) for each j in {1....,t) t). The model includes f weight matrices (W()).... W(')), t bias vectors (b(2),... ..., ((9),, and activation functions (o ..........!!! (!)).
In the described MLP, the function is defined to output f = glt) The initial input layer g0)) is denoted by x {0, 1)". which serves as the model's input. The dimensions of the biases and weight matrices are specified by the sequence of positive integers {do, ................................ de }. We specifically focus weights and biases that are rational numbers, represented as W()) E Q44-ixd, and b0) E Q4, which are parameters that are optimized during training. Given that the model is a binary classifier for indices {l,... n.....,..... it follows that dg = n and de = 1. The primary activation function (6) that we focus on is the ReLU activation function, defined as reLU((x) = max(0. (0, x), except for the output layer, where a sigmoid function is typically used for the classification. Since our focus is only on the post-hoc interpretation of the corresponding model, we will equivalently assume the existence of a step function for the final layer activation, where we denote step(z) = + z 0.
Linear Classifiers. A linear classifier is essentially equivalent to a single-layer MLP classifier, which corresponds to a Perceptron model. To emphasize this equivalence also important for establishing the technical significance of hardness proof' for linear classifiers that extend to neural network classifiers we will refer to them as perceptrons throughout this work. This terminology is consistent with prior research on the subject (Barceló et al., 2020; Bassan et al., 2024). Formally, a perceptron represents a single-layer MLP or in other words t = 1. It is defined by the function fx) = step((w- xx) - 6) with belonging to the set of rational numbers, and w being a matrix in Qaxd. Consequently, for the perceptron function f it holds without loss of generality that (xx = 1 if and only if (w x) + b 2 O.
C. Parameterized Complexity Background
In parameterized complexity, we deal with parameterized problems T. C Σ* x N where Σ is some finite alphabet. The elements of the paramaterized problems are hence two-dimensional instances denoted as (X, k) where A' represents the original encoding and k is the parameter.
C.1. Parameterized Reductions
FPT Reductions. The parameterized complexity classes that we will discuss here are closed under a specific kind of reductions, known as fixed-parameter tractable (FPT) reductions. A given mapping Φ Σ" x N - Σ" x N between instances from a parameterized problem P1 to another parameterized problem P2 is an FPT reduction iff it holds that (i) (X, k) is in Pj if and only if o(X, k) is in Pa; (ii) there exists a computable function g for which K' S g(k) when k'' is the parameter of
18

---

What makes an Ensemble (Un) Interpretable?
((X,)) k);; and (iii) ((x,k) k) can be computed in (2(1())) g((k) time for some computable function g'.
FPT Parsimonious Reductions. For the counting version of FPT reductions (Flum & Grohe, 2004), given two paramterized counting problems F: Σ" x N + N, and G Σ x N + N we define an FPT parsimonious reduction from F to G as an algorithm that computes for any instance (X, k) of F an instance (), E) of G in time 91 (k) | such that l S g2(k) and F(X, k) = G(), e). for some computable functions 91, 92 : N - N, and a constant c E N.
C.2. Parameterized Complexity Classes.
We now will formalize the parameterized complexity classes that are relevant for this work.
FPT. A problem is fixed parameter tractable (FPT) concerning k iff there exists a (2000)) g(k) time algorithm solving the problem for some computable function g.
XP and the W-Hierarchy. The class XP describes all problems that can be solved in (((2))(k)) time for some computable function g- This class additionally encompasses the W-hirerchy (Downey & Fellows, 2012), which can be described using boolean circuits. We recall that a boolean circuit C' is represented as a rooted directed acyclic graph. Nodes with no incoming edges are referred to as input gates, and the singular node without any outgoing edges is the ouiput gate. The internal nodes of the circuit are designated as OR, AND, or NOT gates. NOT gates are characterized by having exactly one incoming edge. AND and OR gates can have up to two incoming edges, termed small gates, or more than two, termed large gates. The depth of a circuit is measured by the longest path of edges from any input node to the output node. The wefi of circuit refers to the largest number of large gates on any path from an input node to the output node. An assignment for C maps the input gates to binary values (0.1). The hamming weight of an assignment reflects the count of input gates assigned the value 1, This assignment determines the output at each gate based on its specific function. A circuit is satisfied by an assignment if it results in the output gate producing value of 1.
We can now characterize the W Hierarchy through reductions to the general Weighted Circuit Satisfiability problem (WCS), which is defined as follows:
Weighted Circuit Satisfiability (WCSICt,&)
Input: A boolean Circuit C' with weft at most & and depth at most d, and an integer k.
Parameter: k Output: Yes, if C' has a satisfying assignment of Hamming weight exactly k
We then say that a problem Q belongs to W[t) if there is an FPT reduction from Q to WCS[C for some fixed constant d. If there exists an FPT reduction from Q to WCS[Cr,a), where the constructed circuit C is allowed have arbitrary weft t, then we say that Q belongs to W [P]. It widely believed that the following relation holds (Downey & Fellows, 2012):
FPT Ç WIL] S W|] C... & c C
(5)
XNP. Our paper will also briefly discuss the XNP complexity class (de Haan & Szeider, 2017), which is generalization of the XP class to the second order of the polynomial hierarchy. XNP describes the set of problems that can be solved by non-deterministic algorithm in ( time for some computable function g. It is widely believed that XNP S para-E?p
The # -Hirerrchy. The W-Hierarchy can be extended to its equivalent counting based hiearchy, which termed the # W Whheerrryyyy (Flum& & Grohe, 2004). Similarly the W -heerrrhhy, where we use the problem aCS[C&,a], we now denote # #WCSICr,al as the problem of counting the number of assignments of Hamming weight l for Boolean circuit C with depth d and weft (that is not fixed constant, but may depend on the size of C). Similarly to the W W-hiearchy, we define #W[t) as any problem Q for which there exists an FPT parsimonious reduction from Q to # #WCS[Ct,al for some constant t. If t is arbitrary, then Q is in [P]. Similarly to the W-hierarchy, it here too is believed that:
FPT S #W(1 & #W c & #WD & #W[P) XP XP
66)
Para-NP. A problem is in para-NP concerning some paramater i if there exists a non-deterministic algorithm which solves the problem in ((1))00)) g(k)) time for some computable function g. A problem is para-NP-Har if and only if the non non-parameterized problem is NP-Hard when & is set to some constant.
19

---

What makes an Ensemble (Un) Interpretable?
Beyond Para-NP. Other relevant classes are the extensions of the para-NP class other classes, such as para-coNP, para-222 etc. (Flum & Grohe, 2003). Let K. be classical complexity class. Then para-K. is the class of all parameterized complexity problems P. with P S D" x N, for which there exists alphabet II, computable function g N + I1", and problem Q _ E" x II' such that X' E K and for all instances k) E Σ" x N of P we have:
(K. = (X.g(k)) EQ
Intuitively, the class para-K contains all problems that are in K. after a pre-computation involving the parameter. Put differently, a problem is in para-K. it can solved by two algorithms P and A. where IP is arbitrary and A has resources that are constrained by K. The pre-computation that is performed by P involves only the paramater, which then transforms into a string g(k). Then, the second algorithm A solves the problems given g(k) from the pre-computation and the original input 2, with resources that are constrained by the complexity class K. We define problem as para-K--Hane if there exists an FPT-reduction from any problem in para-K to it. Alternatively, a problem is -ara-d--ardd if it is K-Haard even when & is constant, (Flum& & Grohe, 2003; de Haan, 2016). is widely helieved that the following relations hold (Downey & Fellows, 2012; Flum Grohe, 2004):
XP para-NP, XNP para-2
D. Additional Query Formalizations
Here, we define the two remaining queries referenced throughout the paper: the Check-Sufficiem-RReasoo (CSR) and Count Completions (CC) queries, which have also been analyzed in previous works (Barceló et al., 2020; Bassan al., 2024). We will then provide further details on the computational complexity analysis of computing Shapley values, as discussed the paper.
The CSR query answers whether specific subset S is sufficient reason. More formally:
Cheek Sufficient Reason (CSR):
Input: A model f. an instance x, and a subset S. Output: Yes, if S is a sufficient reason (f,,),, and No otherwise.
For the CC query we consider a relaxed version of the CSR query which instead validating whether a specific subset is sufficient or not, asks for the relative portion of assignments maintaining a given prediction, given that the other features are independently and uniformly distributed. We start by defining the completion count of a given subset:
c(,,,x) 2z {0, 1) f(xs:zs) = f(x)
(9)
1(z E {0, 1)151
Now, the CC query is defined as follows:
CC (Count Completions):
Input: Model input and subset of features S. Output: The completion count c(S, x,x
We provide here more expanded formalization of the shapley-value that is incorporated in the paper. The shapley value attribution is:
S |S| 1)! (e(SU (1)) - v(S))
(.(x)) =
(10)
n!!
SC
where u(S) is the value finction, and we use the common conditional expectation value function (.-,, = xs] (Sundararajan & Najmi, 2020; Lundberg Lee, 2017). We follow common conventions frameworks that assessed
20

---

What makes an Ensemble (Un) Interpretable?
the computational complexity of computing exact calculations of Shapley values (Arenas et al., 2023; Van den Broeck al., 2022), as well as practical frameworks that compute Shapley values, such as the kernelSHAP method in the SHAP libary (Lundberg & Lee, 2017), and assume that each input feature is independent of all other features, or in other words, every feature E [n] is assigned some probability value [0, 1), i.e., : [n] + [o, 1]. These are called product distributions in the work of (Arenas et al., 2023) or fully factorized in the work of (Van den Broeck et al., 2022). We then formally define our distributions Dp (x) as:
Dx(x) = ( II p(i)
(II i=(m|xx,=1
( II (1 (L-D(i))
(11)
(E(m],x;=0
Clearly the uniform distribution is a special case of Dp. obtained by setting p(i) = 2 for every i E [n].
E. Framework Extensions
Input and Output Domains. To make our proofs cleaner and easier understand, we followed common conventions (Bar- celó et al., 2020; Arenas et al., 2022; Wäldchen et al., 2021; Arenas et al., 2021a; Bassan et al., 2024) and presented them using boolean input and output values. It should be emphasized that our analysis is not confined to binary input feature domains but is also applicable to features with A possible discrete values, where is any integer. Furthermore, we can modify our method to include inputs incorporating continuous input domains. We will next provide a short overview of the various contexts in which this extension is applicable.
Regarding MLP explainability queries, earlier research indicates that the complexity of a satisfiabillit query on an MLP extends to scenarios involving continuous inputs. Specifically, the work of (Katz et al., 2017) and (Sälzer & Lange, 2021) proves that verifying an arbitrary satisfiability query on an MLP with ReLU activations, over a continuous input domain, remains NP-complete. The CSR query mentioned in this work, when S == @ is akin to negating a satisfiability query, and this implies that the CSR query in MLPs remains coNP complete for the continuous case as well. We recall that the complexity of the MSR query for MLPs is ΣJ -Complete (Barceló et al., 2020). This complexity arises from the use of a coNP oracle, which determines whether subset of features sufficient, essentially addressing the CSR query. Given that CSR can also be adapted handle continuous outputs, the logic applied CSR can similarly be applied demonstrate that the MSR query can be extended to continuous domains.
For Perceptrons, the completeness proofs remain valid in continuous domain for the explainability queries. The continuity of inputs does not alter the membership proofs, for the same reasons that hold for MLPs. For hardness proofs, notice that all reductions that were derived from the subset sum (SSP) problem (or generalized subset sum (GSSP) problem), can be adjusted to substitute any call to max(2; 24, } } in our original proof with max([z;, 2,]).
Finally, the proofs that apply to tree classifiers (or ensemble tree classifiers) for queries are equally valid for continuous inputs. This extension continuous inputs was demonstrated by previous works (see for instance, (Huang et al., 2021)). This logic implies also to the complexity of ensembles consisting of the aggregation of few decision trees.
Regression and Probabilistic Classification. Another avenue for extending our framework could involve redefining the explanation forms we have proposed to be more flexible, allowing them to be applied to different contexts such as probabilistic classification or regression.
Potential relaxations of our definitions might include integrating probabilistic concepts of sufficiency (Wäldchen et al., 2021; Izza et al., 2021; Arenas et al., 2022; Wang al., 2021a), applying them within bounded e-ball domains (Wu et al., 2024b; Izza et al., 2024; La Malfa et al., 2021), or focusing meaningful distributions (Yu et al., 2023; Gorji & Rubin, 2022). Additionally, our definitions could be expanded beyond binary classification to address regression or probabilistic classification scenarios. For instance, in the context of a regression model f IF + IR, sufficient reason might be defined as a subset S C (1,....,n n] of input features such that:
Vz E F - 8
f())ll
(12)
for some 0 < 5 < and an appropriate normn Other notations explored in our work, such as contrastive explanations, can also be adapted within this framework. It is important to note, however, that some complexity results related to Shapley values may differ when transitioning from classification to regression. For example, while computing Shapley
21

---

What makes an Ensemble (Un) Interpretable?
values for linear regression models is computationally feasible, the same task may become intractable when applied to classification (Van den Broeck al., 2022).
Homogeneous and Heterogeneous Ensembles. The complexity analysis primarily focuses on homogeneous ensembles (ensembles containing base models of the same type). However, most of our results extend to heterogeneous ensembles as well. Clearly, all hardness results for homogeneous ensembles also apply to heterogeneous ensembles and will always align with the "hardest" complexity class among the associated models. For example, consider an ensemble composed both linear models and decision trees. Suppose that for some explainability query Q, interpreting an ensemble of linear models KI-Complete for complexity class Kj, and interpreting an ensemble of decision trees is K2-Complete for complexity class K2. If we assume, without loss of generality, that 1 Ç K22, then heterogeneous ensemble consisting of both linear models and decision trees will be KC2-Hard. This holds for both our non-parameterized results (Section F) and parameterized results (Section 5). For instance, according to Proposition 4.2, for an ensemble comprising decision trees and Perceptrons, computing the MSR query would be Σς- Hardd Furthermore, based on Proposition 5.3 and Proposition 5.2, obtaining the MCR query for a heterogeneous ensemble containing both Perceptrons and decision trees is para-NP- Hard (though when the ensemble consists only of decision trees, this query is in coW[1]).
F. Proof of Proposition 4.2
Proposition F.1. Ensembles of decision trees and ensembles of Perceptrons are (i) CoNP-CCoples with respect to CSR, (ii) NP-Complete with respect to MCR, (iii) Σ -Complete with respect to MSR, (iv) # P-Comllete with respect to CC, and
(v) P-Hardd with respect to SHAP.
Proof. We will, in fact, prove this claim for a broader class of models, which we define as poly-ssbsett-cnnstreeee models (and for the MCR query we will require an additional constraint). We will then demonstrate that both decision trees and Perceptrons fall into this category. Intuitively, aell-suubett-coostuutbbb models are those for which, given partial assignment over subset X5, we can polynomially construct function that returns 1 if and only if the features in S are assigned the values in x. More formally:
Definition F.2. We say that a class of models C is poly-subset constructable iff given an assignment x E F, and a subset S .n). it is possible to construct a model f E C, in polynomial time, for which for all y E F it holds that:
{
if y otherwise
f(y)
(13)
to
We will start by proving that each one of the models analyzed within our framework are poly-subset constructable: Lemma F3. Perceptrons, decision trees, and MLPs are all poly-subset constructable.
Proof. We will begin with decision trees. Given an assignment x and a subset S, we can simply construct decision tree with single accepting path a that corresponds the partial assignment of the features in S with their respective values from It clearly follows that Vz IF, fxx: 1. Additionally, for any y F that does not match the assignments of on S, we have that f(y)= = 0.
For Perceptrons, given some input E F and a subset S, we construct a perceptron with n input features. The single hidden layer h² is constructed as follows:
is x, xx
h
if x; =
(14)
if iES
We additionally define the single bias term as follows:
ba :
Σ (o xx)
(15)
clearly satisfies that:
22

---

What makes an Ensemble (Un) Interpretable?
Σ 15t5
(16)
Moreover, it holds that:
Σ
4 h
Σ
4 h-
Σ
4
Σ iESAX==0
4
(17)
iESAX, =1
iESAx;=
iESAX, =1
Now assume some assignment (xs:2g) for any F. It satisfies that:
f(xs:z)) = step(
Σ
(xS:ZS)
Σ
1 (xs:zg); - Σ (h) x;) +22
1ESAX
RESAx;=0
Isisn
(18)
Σ
24 11 + 5) stepl 2
iESARE=1
Now assume some assignment y E for which does not match the values over x. holds that:
f(y) = step( Σ tESAX,=1
Σ
y: y
Σ (n x:) + x;)]++/)
tESAx
13i5h
(19)
SpplieSAAE -
Σ (h) x:) +x
18i5n
Hence concluding the construction.
C
The construction for Perceptrons clearly holds for MLPs as well.
Lemma F4. Let o be DNF o = t1 v... V...Vt. tn formula, and let be a poly-subser constructable class of functions. Then, is possible to construct, in polynomial time, a hard voting ensemble f consisting of 2n base-models fi E C.
Proof. We follow a similar reduction to the one proposed in previous work, which demonstrated that obtaining a prime implicant on a random forest is D -Complete (Izza & Marques-Sike Silva, 2021). The key distinction here is that we need to show that our result holds for any poly-subset constructable class.
Let 4 ... in be DNF formula. First, construct n models (fi, : fn), where each model corresponds to its respective clause t,. This construction can be completed in polynomial time, given that assume C is poly-subset constructable. Each clause f; corresponds to partial assignment of values based on the literals that appear in f;- For example, if 4; := x, A x A Xù. then L; represents partial assignment of the features = {i, k} with the corresponding assignment of 101.
We can now leverage the fact that C is poly-subset constructable build a model f, corresponding to each such that for all (1....,7 n), fx) (x). To complete the ensemble f, we add n models that always return True, denoted f -i, f 1 Our final ensemble is f := (Ji,..., - fn, fi .. fá-1) )). If ④i is true, then at least one clause is satisfied, meaning that at least 2n-1 models in f return True, and therefore f is True. If o is false, all models fi...., fn return False, which means that at least n > 2n-1 models return False, and thus is false. This concludes the construction.
Lemma F.5. Let C be some poly-subser constructable class. Then the MSR query for k ensemble of models from C is EP- -Complete
Proof. Membership is evident since we can guess an assignment of features S of size k. and then use a coNP oracle to verify that S is indeed sufficient. In other words: Vz E F, f(xs:zg) = fxx). Next, we will prove Σ/ -ar-Herdssss We begin by briefly discussing proof proposed by (Audemard al., 2022b), highlighting a technical gap this proof, which
23

---

What makes an Ensemble (Un) Interpretable?
also appears in different proof from (Huang et al., 2021). Finally, we will present an alternative proof that resolves this technical issue.
A techincal gap in previous reductions. We begin by referring to previous reduction proposed by (Audemard et al., 2022b) (Proposition 5), which demonstrates that the MSR query for random-forest classifiers is 22 -Hard. This is essentially the same objective as our proof, though in our case, we extend the result to a more general class of classifiers (those that are poly-subset constructible) rather than just decision trees. The proof relies on a reduction from the problem of finding minimal unsatisfiable sets (MUSs) of size k. a problem frequently discussed in this context (Ignatiev et al., 2019b). We will first point out an existing gap in this proof, which appears to be similar to gaps in other proof's suggested in previous works ((Huagg al., 2021), Proposition 7). Afterward, we will present how this gap can be addressed, and demonstrate that the aforementioned problem is indeed E -Hard. To the best of our knowledge, we are the first to propose a solution to resolve this gap.
The approach behind the reductions in (Audemard et al., 2022b; Huang et al., 2021) begins with a given CNF á == ei A... A 6m and an integer k. For each clause, the reductions define I, == G V 8;, introducing a new variable 8; (referred to in (Huang et al., 2021) as the selector variable, and denoted in (Audemard et al., 2022b) by ys). Then, they define 6' : 1 A2...... A bm. which is still valid CNF. Negating o' produces a DNF equivalent to -ø¹. The work in (Huang et al., 2021) halts the reduction at this point, as their focus is on proving hardness for DNF classifiers. (loweee,(Audemen, et al., 2022b) proceeds further by reducing the DNF classifier to an ensemble of decision trees (via a procedure similar to the one provided in LemmaF.4, which reduces a DNF to more general ensemble of poly-subset constructable functions), Next, both reductions assume x to be a vector containing only "I"s. The core argument in both reductions is that any selection of clauses {c,..... d from Cl...., Cm corresponds to selecting & features { s from $1...., 8m. Consequently, they claim that a minimal unsatisfiable set in e of size h corresponds to a sufficient reason of size k involving the variables 8m ʃ.
:
However, we identify technical gap in these reductions. In the DNF proof from (Huang et al., 2021) and the decision tree ensemble proof from (Audemard et al., 2022b), the features that can be included in a sufficient reason may include not only the selector variables 81, . 8m (or equivalently y1, VV2..... Vm in (Audemard et al., 2022b)), but also the original variables 21, I2,..... x from the CNF ø. Consequently, a sufficient subset may be chosen that includes both selector and original variables, which does not guarantee equivalence between the two problems.
An alternative approach that avoids the technical gap. Instead of reducing minimal unsatisfiable sets to DNFs and then transforming them further, we will take different approach. We will reduce from the Σi eef-Comeeeee Shortest Implicant Core problem (Umans, 2001) for DNFs, problem that is related but not entirely equivalent to finding cardinally minimal unsatisfiable sets.
It is already known that computing the MSR query over MLPs is ΣJ -Had (Barceló et al., 2020), and this complexity result can be derived from the Shortext-imlicaatt-or problem, not through DNFs, but rather through boolean circuits. Specifically for MLPs, this reduction leverages the fact that any boolean circuit can be reduced an MLP, making the reduction more adaptable. For ensembles, however, a more complicated approach is needed (which will enable its incorporation to DNFs). We begin by introducing the Shortest Implicant Core problem, first defining implicant, followed by the formal definition of the Shortest-Implicant-Con problem:
Definition F.6. Consider & as a boolean formula over the literals { An implicant C := 2/22. 2j of is detined as a partial assignment over ø's literals (for all 1 S i < I, a! is equal to either xj or TG and each x contains an instance of a different literal), ensuring that any completion of this assignment results in evaluating true.
For example for the DNF furmula: & = x 32 V 2132233, we have that 21 is an implicant of d since any completion of T132 evaluates é True. We now detine the Shortest thorrest-Implicant---e Core problem as follows:
Shortest Implicant Core:
Input: A DNF Formula @ := 11 V... V tn. and an integer k.
Output: Yes, if there exists an implicant C' C t, of o of size k, and No otherwise.
is firstly important to mention that the Shortest-Implicant Implicant problem for a reduction from the MSR query since the core tn is important for representing the specific local assignment x E F for which the sufficient reason is provided. Additionally, since we are working with DNFs and not general
problem is generally more suitable than the Shortest-
24

---

What makes an Ensemble (Un) Interpretable?
boolean circuits, it is known that the Shortest-Implicant problem for DNFs is GC-Complete (Umans, 2001), which is class that is strictly less complex than -
We will start by briefly presenting the proof presented by (Barceló et al., 2020) for reducing the Shortest Implicant Core problem to the problem of solving the MSR query for MLPs. We will then discuss the desired modifications needed in order to produce this problem for ensembles containing poly-subset constructable functions instead.
For example, let us assume we have the following DNF formula:
35 V 72 V T3T6 V Z13244 V 212325
(20)
A straightforward approach to reduce Shortest Implicant Core MSR to construct an MLP that is equivalent to ø. which is feasible since any Boolean circuit can be reduced to an MI.P (Barceló al., 2020). For the input x, we can create an input where the features corresponding to t (in this case, features 1, 3, and 5 are in C*) are set to 1, while the remaining features can be assigned other values.
There is an issue with this construction. The problem that the sufficient reason in the constructed MLP may include features that are not part of fn. Specifically, if we set == 2, we observe that no implicant of size exists for Φ, yet setting features and to 1 determines the prediction of f'(x), indicating that a sufficient reason of size 2 does exist. To address this issue, (Barceló et al., 2020) suggests constructing a different formula follows:
8'
(11a5 V saar V Daal V vrasaa 2133)5))
(21)
We then once again transform this formula into an equivalent MLP f. which is possible since, as mentioned before, any Boolean circuit can be transformed into MLP. More generally, this construction is formalized as follows. Let X. denote the set of variables that are not mentioned in 4. Then, ø' will be defined as:
6 = =b0 + 2 for all Φ E Xel
1+1
(22)
(0)
However, in our case, the following construction does not apply directly. This is because, as proven in Lemma F4, any DNF can be transformed into an equivalent ensemble of poly- constructable functions. However, this does not necessarily imply that reduction as in (Barceló et al., 2020).
reduce any Boolean circuit such models, and since ø' is longer DNF, we cannot apply the same
Instead, we will address this issue differently. Starting with the DNF o. we will create a new DNF, ø', which includes only the literals from L,. We will subsequently demonstrate that any implicant C C ln for e also serves as an implicant for ø'. To facilitate this construction within polynomial time, we rely on the fact that any term t; in ø aside from f,. has at most a constant size. We will thus formalize our problem as follows:
Shortest Implicant Core (Constant DNF): Input: An integer k, constant integer d O(1), and DNF Formula = V... V the where for any 1 i n 1, contains less than d literals. Output:
Yes, if there exists an implicant C S t, of á of size k. and No otherwise.
Claim 1. Shortest Implicant Core (Constant DNF) is -Hadd.
Proof. We note that this proof directly follows from the hardness proof of the Eo. -hardness of the Shortest-Implican problem (Umans, 2001). The hardness is established using reduction from QSAT,, where each term in ø is constructed from a 3-DNF formula conjoined to another constructed 3-DNF. This setup results in a DNF where each term in ø is of constant size. Consequently, it follows that the Shortest Implicant Core, where each term in (t1....,ty. 1 is constant size, is also - -hard to decide.
25

---

What makes an Ensemble (Un) Interpretable?
We will first demonstrate how, from DNF := : V... tt,, where the size of any (fi....tn-1) is bounded by some d, we can construct another DNF ø' in polynomial time and size, where d' exclusively includes literals from &, This approach allows us to later use t, directly as our desired x E IF in the reduction. We will also demonstrate that any implicant C' S tn for & equally serves as an implicant C C t, for d'.
The construction. The idea is that if a term 4 in e includes literals not present in ln we can "eliminate" these non-6n elements by iterating over all possible assignments that cover the literals not included in t, (and this number is polynomial, as each term in é is of constant size). Formally, let there be DNF == t V 12 V... tn- For each i; where 1 S i let us denote as the subset of literals from 4 which do not participate in on First, we define ø' to be the disjunction of any for which 1 I i S n - 1 and r; is empty (in other words the "part" of the DNF that only contains assignments of literals that appear in t.).
1,
Now, for each t,, if r; is not empty, we consider every subset S S (t2....,fn-1} where the size of S is I 2 We use (2i, ab.. . to represent the literals participating in r;. By iterating through S, we can verify whether any is encompassed by S U t4. Consider, for example, T; == z137. The literals involved are {21, .77. Assume S = [21 [Z17g29], [zιz]] Here, every potential assignment to 21 (which includes (11=7), [7) ( (z)=7)) is encompassed by S U.4. Another example of subset S such that S U 44 covers all assignments is: 5 := { [mr1s)) [r1æ7=s]] However, the subset $ = =.) [ا] [x10>] fails to enable S U &2 to cover all assignments since it misses the assignment TΙæ7. It is worth noting that validating whether S covers all literal assignments can be done in linear time with respect to |S], as each ty E S accounts for covered assignments, allowing us to save each covered assignment and, after iterating through the entire S, check whether all assignments were covered.
potential assignment for {zi, xb..... ..,,..,,,.. [
For each li, we initatie a set S.. For each S that iterate on concerning 4; if we have that S U U4 covers all assignments of literals of r2 we will add Anes FT to Sy. Now, we are in position to define our refined DNF formula:
8' I
V IV 4]]vm
(23)
15i5m-1 668,
We first note that the construction of d" is polynomial, For each t, we iterate over all subsets of size 2 2:l or less. Overall the number of subsets we iterate is bounded by:
E Igiga=1 15/52
n H)
Σ Igisn-1
Σ
R²)
Σ (2 . n2 222" S
15552/n
Igisn-1
(24)
Σ
(2
n
S n (2 n²")
1sisn-1
and since d is constant, the derived term is polynomial in n. We have that both the runtime of constructing d" as well as the size of o" are polynomial in n. We now will prove the following lemma regarding the construction:
Claim 2. Any C' C fn is an implicant for & if and only if it is an implicant for s".
Proof. If C' C in is an implicant, this indicates the existence of a subset S C (f1,..., fn } such that the partial assignment C' ensures any completion of C' within Vues t evaluates to true (thereby guaranteeing that any completion of C' within ø also evaluates to true). Initially, we assume that each & E S incorporates literals from f,- This leads to the identification of this subset as a subset of terms in ø', and consequently in o". Thus, we identify a subset S' C {t',...., ...,,,,, ).m)). where ... ) represents the terms of d²,, satisfying Vt,es 4 = V,,ss 4. Therefore, any extension of C' in V 4 that holds true, ensures that any extension of C' in Vtyesr tą is true (and by extension, any completion of C in d"). This leads us to conclude that C' is also implicant of o".
Revisiting our earlier notation, let r; represent the set of literals from 4 that are absent in I,p. For any 4 E S where is non-empty, it is required that all assignments to the literals of ri are covered by S (failing which, there will be an assignment making V,,es & untrue). Essentially, S consists of each t, where r; is non-empty, including terms that cover all assignments for r,, and potentially terms where ry is empty (which would then be included in d'). We observe that any assignment covering all assignments for r; can be at most of size 2 This assignment will be generated by our approach
26

---

What makes an Ensemble (Un) Interpretable?
and incorporated within Vs,s 4 and subsequently in e².. Consequently, we identify a subset S' C (1/,... ......... :. where ff/.....: (m)) are the terms of 6² such that V1,ss f2 = Ves 41. Thus, any completion of C over V Uess that proves true, equally confirms that any completion of C over V ves & is true (and thus any completion of C' over ø is true). Ultimately, this demonstrates that C' is also prime implicant of 6".
For the second direction, let us assume that C' is an implicant for d". Consequently, there is a subset 5 S (t/,-.., kmm of terms from ø", denoted by "i....,mm. where any completion of over Viyesr 4 invariably results in true (thus guaranteeing any completion of over o" is true). If S entirely within d', it follows that S is also part of Φ, and therefore, there exists a corresponding set S' S (tl....,tor ] in which any completion of C' over Va & is true, as is any completion of C' over Φ5. Therefore, C' is also implicant of Φ.
Now, if S includes terms that are not from &', these must be assignments in the form of A ri, where S is subset of {t),..., } and covers all potential assignments over the literals of r; for some t4 E [tl.... J. Consequently, we can select the terms from each S", as well as those from d', to form a corresponding subset S' S {ft....,t.. f. It is important to note that all terms S' that lack any literals from in are part of o' and thus appear equivalently in both and S". Additionally, for any term & S S' where ri & 0, all assignments over the literals in 71 are covered by both S and S'. Therefore, we conclude that VG,S 4 Va,es 4; thus, if any completion of C confirms that Viess 4 is true, also confirms that Vues t is true (and thus Φ). Ultimately, this shows that C' is also prime implicant of o, completing the proof of the claim.
C
This claim proves that a prime implicant C S in of size l exists for o if and only if a prime implicant C S tn of size k exists for &", thus concluding that the Shortest Implicant Core problem for constant DNF Eip -Hard.
C
Concluding the reduction. We now finalize our proof for reducing the Shortest-Impliant--Con (Constant DNF) to the MSR for an ensemble of poly-subset constructable functions. Given tuple (ø, C, k, d), we can construct o' from & in polynomial time, a task feasible particularly because d is constant, Utilizing Lemma F.4, we convert ø' into an equivalent ensemble f of poly-subset constructable functions. Notably, the literals in o' are exclusively those from tn. Therefore, we use εn to construct our input vector, where any positive assigmment in C' is represented as a "1" in x and any negative assignment as a "0". For example, if t := X1X2X3, we would set == (101).
Now, since the input x includes only features present in f, we can assert that an implicant in tn of size le for ø' exists if and only if sufficient reason of size k exists for x). Given that any implicant C in ln for ø' also serves as implicant C in o, it follows that an implicant of size k for é exists if and only if there is a sufficient reason of size k for (f,x), x), thereby completing our reduction.
In contrast to the MSR query which was non-trivial, for the CSR, MCR, CC, and SHAP queries we can incorporate similar reductions to other works (Izza et al., 2021) which show hardness for DNFs, since we know that ensemble which is encompassed by models from class that is poly-subset constructable, can be reduced to DNFs (Lemma F.4).
Lemma E.7. Let C be some poly-subset constructable class of functions. Then the CSR query for a ensemble of models from C is CoNP-Complete
Proof. While these results can be derived from the notable works of (Audemard et al., 2022b) and (Ordyniak et al., 2024) in the specific setting of majority-voting decision tree ensembles, we provide a direct proof here for the more general class of poly-subset constructable models, covering both majority and weighted voting schemes. Membership in coNP is straightforward since we can guess an assignment z E and verify whether ((xs;zs) + [x) to determine if S is not sufficient reason. For the hardness result, we can apply the same proof provided by (Barceló et al., 2020), which involves reduction from the tautology (TAUT) problem for DNFs. In their work, DNFs are reduced equivalent MLPs to for MLPs. Similarly, in our case, we can utilize the exact same reduction since, in Lemma F.4, we demonstrated that any DNF can be reduced to an ensemble of models from C, where C is poly-subset constructable. This leads to the conclusion that the problem is coNP-complete.
establish
In the specific case of MCR, we will establish the complexity of the problem for a set of models that remains puly-subset
27

---

What makes an Ensemble (Un) Interpretable?
constructable, but also adheres to an additional property, which we define as being "closed under symmetric construction". This property is formalized as follows:
Definition F.8. Let C be class of functions. Then C. is closed under symmetric construction iff for any f C, then -f can be constructed in polynomial time.
We will prove that ensembles of decision trees, Perceptrons, and MLPs all satisfy the aforementioned property:
Lemma E9. The class of ensembles of decision trees, the class of ensembles of MLPs, and the class of ensembles of Perceptrons are all closed under symmetric construction. In other words, suppose we are given f- an ensemble of k models Jn....;J that are all either Perceptrons, decision trees, or MLPs; then, f =f can be constructed in polynomial time.
Proof. We first note that negating individual decision trees, Perceptrons, and MLPs can be done in polynomial time, as demonstrated by (Amir et al., 2024). Applying this transformation to any decision tree Si within the ensemble results in negating the entire model f. The only asymmetric element in this negation arises in majority voting "1" classification occurs iff [ of the models are classified "1"-and the negation effectively changes the ensemble to classify "1" iff 1 models are classified as "1". This asymmetry can be addressed by constructing an additional model, when needed, that always classifies "1". This can be done using Perceptrons, decision trees, or MLPs. Similarly, in weighted voting ensembles, asymmetry may arise due to the distinction between strict and non-strict inequalities. In other words, while classifies as "I" iff Eisish Φ; 2 0, in the negated model f", it will classify as "1" iff Σ Cisisk & >> O. This can again be resolved by adding an extra model fi that always classifies "1" with very small weight, thereby addressing this issue. Given that any weight in Js. Φi, is a rational number Pi the weight of the newly constructed model can be set to q1 q2 ... qk- This additional model will correct the asymmetry in cases where the weighted sum of all models is exactly zero, allowing the ensemble to be negated.
a
We are now prepared to prove the following claim, which will establish that solving MCR for ensembles of decision trees, Perceptrons, and MLPs is No-complete. This result follows directly from Lemma F.9 and Lemma F.3.
Lemma F10. Let C be some poly-subset constructable class functions, which is also closed under symmetric construction. Then the MCR query for a k ensemble models from C is NP-Complete.
Proof. Similarly to CSR, although these results can be derived from the notable works of (Audemard et al., 2022b) and (Ordyniak et al., 2024) in the specific case of majority-voting decision tree ensembles, we present a direct proof for the more general class of poly-subset constructable models, encompassing both majority and weighted voting schemes. Membership holds because we can guess subset S and check whether [S] S and f(x;izs) # f(x), which confirms the existence of contrastive reason of size d.
For hardness, we can use similar proof to (Barceló et al., 2020), which demonstrates that the MCR problem is NP-Hard for MLPs. They reduce the problem from the Vertex-Cover problem, which is NP-Complete. To achieve this, given graph G = (V, E), they construct an equivalent CNF formula:
A Vz.) (a,))E
(25)
and encode the CNF formula as an equivalent MLP. In Lemma F.4, we proved that any DNF can be reduced to an ensemble with puly-subset constructable base-model functions. However, to extend the proof of (Barceló et al., 2020) to apply to our ensembles, must show that any CNF can also be transformed into an ensemble constructed from these models. This is possible because the family of models C is not only poly-subset constructable but also closed under symmetric construction. We begin by proving the following relation:
Claim 3. Let à be CNF o == t1 A... A t.tttforrmnn formula, and let C be poly-subset constructable class of functions. Then, it is possible to construct, in polynomial time, a hard voting ensemble f consisting 2n both a pulyesubset constructable class, and is closed under symmetric construction.
2n - base-models fi E where C is
Proof. We begin by negating @ in polynomial time and derive a DNF formula equivalent to -6. From Lemma F.4, we know that any DNF can be transformed in polynomial time into an ensemble of models f (since C is poly-subset
28

---

What makes an Ensemble (Un) Interpretable?
constructable). Given that is also closed under symmetric construction, we can negate / and construct -f in polynomial time. Thus, we obtain ensemble f' -f equivalent é, completing proof.
C
We can now conclude our proof, as we know that ensembles of decision trees, Perceptrons, and MLPs are all poly-subset constructable and closed under symmetric construction. Therefore, any CNF can be reduced to an equivalent ensemble composed of models from this class, allowing us to leverage the vertex-cover problem to establish NP-Hardness.
L
Lemma F.11. Let C be some poly-subset constructable class of functions. Then the CC query for a ensemble of models from C is # PCComlleee
Proof. Membership is straightforward by definition. For the hardness result, we can reduce from the Model Counting problem for DNFs, which is known to be # H-rr (Valiant, 1979). Given a DNF Φ, we can construct an equivalent ensemble of poly-subset constructable functions using Lemma F.4 and set S = 0 for the CC query. Thus, solving CC equivalent to model counting, and the reduction holds.
C
Lemma F.12. Let some poly-subset constructable class of functions. Then the SHAP query for k ensemble of models from C is #--Hard
Proof. We follow the proof of (Arenas et al., 2021b), which demonstrated a connection between computing SHAP under fully factorized distributions and the model counting problem. The following relation is established:
#f = f(x) 2n
Σ LE(I....,..
o((f.x)
(26)
where #f represents the number of positive assignments of and é denotes the Shapley value. This establishes that computing SHAP is at least as hard as the model counting problem. Since, as shown Lemma F.4, any DNF can be constructed into an ensemble of poly-subset constructable functions, and model counting for DNFs is known to be # H-Hr (Valiant, 1979), this concludes the proof, demonstrating #P- P-Hardness for computing SHAP.
G. Proof of Proposition 4.4
Proposition G.1. While the CC and SHAP queries can be solved in pseudo-polynomian time for Perceptrons, ensemble- Perceptrons remain # --Hard even if the weights and biases are given in unary.
Proof. For the CC query, we refer to the results from (Barceló et al., 2020), which demonstrated that when the weights and biases are provided in unary, the CC query can be solved in polynomial time for perceptrons. However, according to the findings in Proposition F.1, when the weights and biases are not given in unary, the CC query is # #-Coompeete for ensembles of perceptrons.
For the SHAP query, a proof that was proposed by the work of (Arenas al., 2023) which showed connection between the computation of shapley values for models (under some mild conditions) and the following portion:
HD, S,)x
=
Σ Ef xs]
(27)
Specifically, this relationship applies models that closed under conditioning, defined as follows:
Definition G.2. A model f F + {0.1) is closed under conditioning if given some assignment x E and some subset S E [n], we can construct in polynomial time function f - {0, 1} for which it holds that for all y e F: fy( (ss:
29

---

What makes an Ensemble (Un) Interpretable?
The connection between models that are closed under conditioning and the computation of HD, is follows (Arenas et al., 2023):
Lemma G.3. Let there be a model I which is closed under conditioning. Then solving the SHAP query for I and any i E [n] can be reduced, in polynomial time, to the problem of computing HD,
To apply this lemma our scenario, we begin by proving the following claim: Claim 4. Any perceptron f := (w, b) is closed under conditioning.
Proof. Given a perceptron f : (w. b). an assignment x F, and subset S E [m], we can construct a second perceptron f' = (w', B), where w' == g.. In other words, "zero-out" all the feature values in corresponding to the set S and leave the features in S unchanged. Additionally, we define b' b Eiesx:=1 It now holds that for any y E If:
f( = Σ w y; +b iE(n)
Σ w' y; + iES
Σ iES
W y, + (6+
Σ w:) =
iESx;=1
Σ
W y; + (b
Σ w:)
(28)
iES
iESx:=1
Σ EES
W y, (b+
Σ iESx==1
Wi X
Σ NESx=00
W; x,) = f(xs:ys)
C
Now, we only need prove that when the weights and biases perceptron f are given unary, (S, can be computed in polynomial time. This will complete our proof that the SHAP query can be solved in pseudo-polynomial time for perceptrons. We use the notation sim(z, to denote the set of features S such that for all i E S, it holds that z, X We begin by demonstrating the following relations:
HD, (S,k)
Σ
Ex-D,
[[(z)/s = xsl
SChn),SS=
[sim(z,)) x)
Σ
II
(p(1)
II (1-p(i))) f(z)
xEI XEB,|simm(xx))22
iE(n],z=1
iE(n],4=0
|simm(z,)))
Σ
II iE(n]
(p(i)
II (1-p(i)) [m(m)a;=0
xEF, (sxmm
|sim(z,x)
Σ
(p(i)
II sE|m],,
(1 (1-p(1) p(i)))
(29)
ZEF, 2EF,| (tsmmssmxmxx////ff/
sE[n],2;=1
i=n
Σ
(p(1)
II <E(n]2,;0
(1 - p(i)))
j=k
zEF, /sim (x,x)
ZER,
iE[n],,;1
II aE|n|
(p(1)
II iEfn].:==0
(1 (1-p(i))) (1()==1) =
j=k
ZEF. (sim(siima))))=
j=n
Σ
Σ
II
(p())
II iE|n],z;=0
(1 (1-p(i))) 1 [E 462))60)
jmn
ZE3, [=s((2))=
sE|n],2,=1
We define M := max(w)== + 1. Next, we define the vector w' as follows:
M if =1
=1 if =
(30)
W; + M
We finally define T : b+ (iE W.). We now prove the following relation:
30

---

What makes an Ensemble (Un) Interpretable?
Claim 5. Given some integer 1 S S n, the following relation between and w' holds:
Σ
Σ SC
(31)
is equivalent to iterating over all subsets S S [m]] [S| = j and taking the values of the features in S to be those of x and those of 3 to be -x. In other words, iterating over all vectors of the form (Xs; Xg for which |S| = j. From this, we can derive the following relation:
Proof. We start by noting that the iterating over all vectors E FF for which |simi(z, x)] =
Σ
Σ
(E w22
(E:: wo(N)-x)+620) =
REB (
ScIn],1S==/
(32)
Σ
1 1(Es (oxe) (.())))
S[(n
We can continue and show that the new relation holds the following:
Σ
((Eis w,
(-x)))))6023
SC 1Cmm),S|=$
(33)
Σ
(. wi)+020
We move to the second term and prove that the following holds:
1 1 (E W/STM ScIn],SS
Σ
Σ s[mn][$8
1 (-w
Σ 8Cmn]|s|=
W:ST)
W.ST)
(34)
Σ
SCIN,
Σ 1 LE (-W.) w. Evess, We W. LiE8s, wiSb]
S((n
Σ
1( wit Eo wi+b20)
Scin
Hence proving the equivalence.
We hence can equivalently derive in that HD, k) is equivalent
n
II
(p(1) ic(n (x=1-x)))
II
(1-1(1))) -1 [Liss W(ST+M))
(35)
j=
| j
(xos-x)))) =1
We now will conclude the proof by proving the following claim: Claim 6. (S, can be computed in polynomial time.
31

---

What makes an Ensemble (Un) Interpretable?
Proof. We will demonstrate how HD, (S, k) can be computed in polynomial time. This will be done using dynamic programming algorithm that computes portion of this sum, utilizing the notation of DP. Speccfically,, for all i N, é No such that S ki-t is n., and for all C e 2, define:
DP f=
II scim] (x: otherwise
Σ (
(p(r))
II
(1 (1- (--prr)) if Eieswi
(36)
where, for any i, E N such that it does not hold that 1 < S S n, we define DP E Given some
1 S j S n, if we take n, C = T + Mj, and - := j (i.e., 8 == -),, we find that DP Mj][j] is equal to:
Σ ISISi
(p(i)) VE xx)
II
II
(1- (1)p(i)) 1 (ETes w(S++M.))
(37)
Thus, we ultimately obtain that:
DP MMlb] - DP + MMj - -1] 1]=
II
(p(i)
(1 (1- ((-)(i))) (xs:xx))))
II
12ires wIST+M-
(38)
|S|= (xs)))-) -1
Therefore, assuming that [ can be computed in polynomial time, we can iterate over all j S k S n and compute [P]]][C][]] for each j. thereby calculating HDP overall. To simplify the presentation, we define:
R(x, S,1)
II
(p(r))
II
(1- (1-(()))
(39)
(xs
r=(0),x6:-xx),==
Thus, we can simply express it as:
Σ sci
S,i,
if Eies
DP
(40)
otherwise
For our final step. we will now prove the correctness of our dynamic programming algorithm:
Lemma G.4. There exists polynomial dynamic programming algorithm that computes DP[i]CC]jioo any C and any SeSis issin n.
Proof. We present the following inductive relation:
DP HP[++1](0 [|[ =]=
DP (1-1 + DP[i - - - if
(41)
DPE[C 4 p() + DP -
- (1-p(()) if x; x=x;00 = 0
We also define that [C 0 for any i, C. < 0 and further define that when i 0, then DP[|]CC|L] = 1. We begin with the induction base, i.e., when i = 1. If l > 1, then we have DP[[][C][[ - E 0, which satisfies our conditions. The only remaining case is when = 0. In the case that x; 1:
DP[[[Cc[[ f] DPU D (1 p(1)) + DP s =1][0] -p(1)
(42)
DP[O[[C sı][0] p(1)
32

---

What makes an Ensemble (Un) Interpretable?
If it also holds that 81 C, obtain:
DP[1][C]] - 4 DP s1|[0] p(1) = p(1) = R(x,(81),11
(43)
However, if 81 > C we gel that:
DP[]] 4 DP -1][0] p(1)
(44)
As required. For the other scenario, we get that if X; it holds that:
DP - = (p(1)) DP[O][C s1][0] p(1)
(45)
DP[O|IC =1][0] (1- p(1))
it additionally holds that $1 S C, then we have:
DP a DP =1][0s (1-p(1)) (01() 12xx 15
(46)
However, if $1 C' we get that:
DP[[| 4 DP s1][0] - (1-p(1)) =
(47)
as required. For the inductive step, we assume correctness holds for some E N and show that:
DP + 1| 1- DPП[CС p(1) + DPLiIC
(1 11---l]-1-pppppppl (1-v(i))
Σ
R(k,x, S,i) - p(i++)) 1)+
Σ
R(k, (1-pl) p(i + 1)) =
(48)
Σ
R(K,x, S,1) -(i+ +1+
Σ
R(k,,,S,i) (1 - p(i 1))
R(k. x, 1
C
We conclude by presenting the complete algorithm described for computing HDP (S, k)) with the following pseudocode:
Algorithm 1 Computing (S,
Input f. x, S, k
1: T + +++b+( X) w:)
2: HD, +0
3: for each j < do
4: Hd, + HD, + (1) (DPnn][T Mf M(j 1)Il 1))
5: end for each
6:
7:
return HDP
The following proof demonstrates that solving the SHAP query for Perceptrons can be done in polynomial time, assuming the weights and biases are provided in unary.
33

---

What makes an Ensemble (Un) Interpretable?
H. Proof of Proposition 4.5
Proposition H.1. There is no explainability query for which the class of MLPs is strictly more c-interpretable than the class of ensemble-MLLP
Proof. We will specifically prove this claim for a much larger set of functions that we will refer as models that are closed under ensemble construction:
Definition H.2. We say that class of models C is closed under ensemble construction if given ensemble f containing models from C, we can construct in polynomial time model g E C for which v'x E IF, f(x) g(x).
We first note that from the definition of a model that is closed under ensemble construction, the following claim holds: Let there be a class of models C, which is closed under ensemble construction. Let us denote Cg as the class of ensemble models that consist of base-models from class C. Then for any explainability query Q: then it holds that Q(CE) Sp Q(C). Now, if Q(C) belongs to a complexity class that is closed under polynomial reductions, it hence must hold that Q(CF) does not belong to a strictly harder complexity class. We are now only left to prove the following claim:
Claim 7. Let CMLP denote the class of models that are represented by MLPs. Then CMLP is closed under ensemble construction.
Proof. Consider a model f comprising i individual MLPs denoted as f1..... fk We can devise new MLP, f", by integrating the hidden layers from each fi. Specifically, s''s first hidden layer is constructed by concatenating the first hidden layers of fi...., fk. and similarly for subsequent layers up to the highest number of layers present in any fi. For models with fewer layers, we introduce "dummy" layers equipped with weights of 1 and biases of O, effectively passing their last actual output through unchanged. In this initial setup, the layers in f corresponding to each f, are only linked to their respective preceding layers within the same ft, thus lacking full connectivity across the different models fj such that j * i. To amend this, connectivity can be enhanced by adding inter-layer connections with weights of and biases of O, ensuring each layer does not influence the next across the different sub-models.
Finally, we observe that the constructed f' outputs & distinct values corresponding to the outputs of each model fi,-... Su (the output value prior to the step function). We need to introduce a new output layer to f' to implement a majority voting mechanism. This is conceptualized as a weighted voting process where each model fa is assigned a specific weight ox. This can be realized by adding a fully connected layer that consolidates the & outputs into a single output in the final layer of f'. In this layer, each output E {1....,k: k} is assigned a weight w; := :., and we set the bias of this last layer to O. Consequently, applying a step function over f' results in output that represents a weighted majority vote of the ensemble f. Additionally, a non-weighted majority vote can be modeled in the setting where all weights Φ1 = Φ2 ... Φx equal. We thus establish that f' CMLP, and that for all z E F, f(z) fz(z thereby confirming that CMLP is closed under ensemble construction.
I. Proof of Proposition 5.1
Proposition L11. An ensemble consisting of either Perceptrons, decision trees, or MLPs, parameterized by the maximal base-model size is (i) para-coNP Complete with respect to CSR, (ii) Mara-NP-Compled with respect to MCR, (iii) para- D. -Complete with respect to MSR, and (iv) para-#P- P-Complete with respect to CC, (v) para-# # P-Hard with respect to SHAP.
Proof. Membership is straightforward from the definition of para-K. and the completeness of all the non-paramaterized versions to each corresponding complexity class K. as proven in Proposition F.I. For example, the non-parameterized version of CSR for an ensemble of Perceptrons, decision trees, or MLPs Compleee The same holds for the other complexity classes.
Hardness. The reduction for the CSR query was provided as direct reduction from the TAUT problem. Since TAUT is hard when restricted to 3-DNFs as well, then hardness for an ensemble consisting of constant sized-base lines is straightforward (for any A > 3). In the case of the MCR reduction, the result already holds for any k = 2 since the reductino inherently produces ensembles consisting of input dimensions of at most 2. For the CC query.
Finally, in the case of MSR, we note that the Shortest Implicant Core problem in its classic form presented by (Umans, 2001)
34

---

What makes an Ensemble (Un) Interpretable?
describes general DNFs and restricted DNFs. However, in consequent work (Dick al., 2009), it was proven that the Shortest implicant problem for DNFs with constant term size is also E -Hard.
J. Proof of Proposition 5.2
Proposition J.1. k-ensemble- Perrepprrosss are (i) para-coNP Complete with respect to CSR, (ū) respect MCR, (iii) para--if-Commpe -Complete with respect to MSR, and (iv) para-# P- P-Hard with respect CC and SHAP.
with
Proof. All membership results are direct result from the non-parameterized complexity results F.I, and from the reasons described under the proof of Proposition I.1. We now will prove each hardness result seperattley.
Lemma J.2. The CSR query for k-ensemble Perceptrons is para-coNP Hard.
Proof. We will equivalently prove that the CSR query for an ensemble containing only 2 perceptrons coNP Complete. We will reduce from the Subset-sum problem (SSP), which is classic NP-Complete problem.
SSP (Subset Sum):
Input: (21, P2, -..; zn) set of positive integers and a positive (target) integer T
Output: Yes, if there exists subset $ S (I, such that Eies 24 T, and No otherwise.
We reduce CSR for an ensemble with k = 2 of Perceptrons from SSP. Given some ((=1, "2,...; ;n)) Tn), the reduction
constructs the two following Perceptrons fi := (wl b1) and f2 == (w?, b2),, where w == (-21, - 22... -...... 2n.).
bj 7 1 w2 == (21, 22,..., 2,), and b2 == - 2. The reduction constructs (f (fi, f2), x == 0n, = 0), and
2. O₂ denotes a vector of size n where all values are set to O.
First, we notice that:
fi(x) = f1(0.) =T - 1 2
A
(49)
1
f2(x) = f2(0.)) =
2 <0
Since fi (x( is positive and f2(x) is negative, then the ensemble f (f),f) returns 1 for the input x (is positive), by definition.
If ((11, 22, ,.,)
SSP then there does not exist subset of features S' (1, ..) such that Eies 2; T. Since these are integers, this implies that any subset S" C 21, n) is either equal or greater than T + or equal and smaller than T - 1. Let mark S' as some subset for which it holds that Lies 2 T + 1. Let us denote x' = (1 0z.). Or in other words x' denotes a vector where all the values in S' are set to 1 and the rest to 0. It clearly holds that:
1(x)
Σ w/
+b,
Σ 2 b4b
(50)
iES'
3
-(T+1)++
2 = <0
also holds that:
35

---

What makes an Ensemble (Un) Interpretable?
12(x) = Σ x
w] + b2
VES'
Σ
24 + 22
(51)
İES'
(++1++
00
This implies (x(' is negative and f2(x') is positive, and overall get that for the ensemble f it holds that f(x') is positive.
Now, let us assume that Eies 24 S - 1. Again, let us denote x' = =(1sr; Og.). It clearly holds that:
f1(x') Ex,
wi
bb
iES
Σ
24 b
(52)
iES'
1
-(T -T
2 >0
It also holds that:
[x(x) Σ
X',
w/
b2
Σ
2 52
(53)
YES"
1
(T (T-1)+ 2
< 0
2
Implying, that under this scenario the opposite case occurs: fi(x') is positive and fa(x') is negative, and overall we get again that for the ensemble f holds that f(x') is positive.
This shows, that for any feasible value of x', fxx') is positive, and this implies that S 0 is sufficient reason of (f,x=0,,)
If 2..,, & SSP, this means that there does exist subset S S {1..... n) for which Eies 2 T. We again denote x' = (1st; 0g:). ). It holds that:
f1(x)=
w|
bb
iE
Σ 24 + b
(54)
iES!
(T) 2
<0
It also holds that:
f2(x) = Σ x . w/ bby=
Ex
Σ
2, + by
(55)
iES'
1
+-)(-TT
< 0
2
2
36

---

What makes an Ensemble (Un) Interpretable?
This means that both [1(x) and fxxx)) negative and hence the ensemble f(x') is also negative. Since f(x) f(O,,) is positive, it holds that S is not sufficient reason of (f,)), which concludes the reduction.
C
Lemma J.3. The MCR query for a k-ensemble of Perceptrons is para-NP Hard.
We will equivalently show that the MCR query for ensemble of k=2 Perceptrons is NP-Complete. We refined version of the SSP problem - kSSP, which is also known to be NP-Complete.
kSSP (k Subset Sum):
Input: (Z), #2,...; =n) set of positive integers, a positive integer k, and a positive (target) integer T', Output: Yes, if there exists a subset C (1,2...., n) such that S = and Eies 2 = T, and No otherwise.
We reduce MCR for ensemble with 2 Perceptrons from kSSP. Given some ((21, 22, ,n))..,2n).................)).),
2n), k. T),, the reduction constructs the two following Perceptrons fi := (w² b1) and f2 == (w? b2),, where w = (-21, =22.... 2n), ) bj : T 2 w² == (21, 22........ 2n), and b2 := - 2. The reduction constructs (f := (fi, f2), == On, k), and O,
denotes a vector of size n where all values are set to O.
First, we notice that:
fi(x) = f1(0,) T 1
A 2
(56)
f2(x) = f2(0,)) = -- <0
2
Since (x) is positive and f2(x) is negative, then the ensemble f (2), returns for the input x (is positive), by definition.
If ((21, :2,...; 2n), k. TT & SSP then there does not exist subset of features S' C (1,2....,,)) such that Σ 2; T. Since these are integers, this implies that any subset S C (1, of size k is either equal greater than T + 1 or equal and smaller than T 1. Let mark S' some subset of size & for which it holds that Eies' 2i 2 T + 1. Let us
denote x' = (1s:; 0s:). Or in other words x' denotes a vector where all the values in S' are set to 1 and the rest to 0. It clearly holds that:
1(x)= Ex', VEST
w/
+b,
24 bb
(57)
İES'
1
3
<0
2
2
It also holds that:
f2(x)) = Σ X', w +
VES!
Σ 24 + by
(58)
İES!
1
(T + +++++((-T-
0
2
This implies fi (xx) is negative and f2(x') is positive, and overall we get that for the ensemble f it holds that f(x') is positive.
Now, let assume that Eiesr 2, S T 1. Again, denote x' (1 0g:). It clearly holds that:
37

---

What makes an Ensemble (Un) Interpretable?
f1(x)= = Σx' x
w
+ bb
iES
Σ
2j
bb
(59)
iES'
1
-TT (I
>0
2
It also holds that:
f2(x) = Σ X's w + b2
LES'
Σ 4 2
(60)
3 <0
(T - ()-1)) 2
Implying, that under this scenario the opposite again that for the ensemble f it holds that fxx' is positive.
occurs: fi(x') is positive and fa(x') is negative, and overall get
This shows that for any subset S" of size k the value of f(x') remains positive. Since the value of f(x) is also positive, this implies that there is no contrastive reason S' of size l with respect to (f, x). This also clearly implies that there is no contrastive reason S' of size smaller than i with respect (f,x).
If ((11, ..,... zn), T SSP, this means that there does exist subset S' S {1, .I,..., n) of size ls for which Eses 2, T. We again denote x' (1gr; 0g.)). It holds that:
fi(x) = Σx
X
w/
+ b
iES!
Σ
24 +
(61)
iES!
1
- +T
<0
2
It also holds that:
f2(x)) = Σ X w + +b
iES!
Σ 24 b2
(62)
iES!
(T) --T (-T- <0
This means that both (xx) and fx(x') are negative and hence the ensemble f(x') is also negative. Since f(x) f(O,) is positive, it holds that there exists a contrastive reason (S') of size & with respect to (f, x), concluding the reduction.
Lemma J.4. The CC and SHAP queries are para-# P-Hard for a l ensemble of Perceptrons.
Proof. The Hardness of the CC query follows from the fact that this problem is already #P H--Hard for single percep- tron (Barceló et al., 2020) (k- = 1). For the SHAP query, we follow the proof suggested by (Arenas et al., 2023) who showed a connection between the exact computation of shapley values computations and the model counting problem. Given some model f, we define #f the number of assignments which output 1. More formally: #ʃ l[z
f(z) = 1}}. (Arenas
38

---

What makes an Ensemble (Un) Interpretable?
al., 2023) showed the following connection for the specific where Dp is taken to be the uniform distribution. It holds that for all F it holds that:
#f #f=2" - Σ (((fx))
(63)
8E|n]
where the following relation is consequence of the well-known efficiency property of shapley values. This result establishes a direct reduction from the SHAP query to the model counting problem. Moreover, the model counting problem is simply a private case of the CC query where S == This establishes a polynomial reduction from the CC to the SHAP query. We hence conclude that SHAP also # P-rdd for an ensemble consisting of only a single Perceptron.
C
Lemma J.S. The MSR query for k-ensemble of Perceptrons is E Compleete
Proof. Membership. We establish membership in para-E2 using the direct definition of the complexity class since non-deterministically guess subset S and then utilize coNP oracle verify whether S is sufficient.
Hardness. We will equivalently show that the MSR query for an ensemble of k Perceptrons is ΣS -Hadd. First, we will present the Generalized Subset Sum problem, which known to be Σ complete-complete (Schaefer & Umans, 2002).
GSSP (Generalized Subset Sum):
Input:
Two vectors of positive integers u = (n, .2...., Un) and (V1, V2,..., Vm), and positive (target) integer T. 1)' such that for any binary vector y {0, 1). it holds that: Output: Yes, if there exists a binary vector 1),
E (x: u.) I v2) # T; and No otherwise.
We will actually use very close modified version of this problem which we term k-Generalized Subser Sum, which requires an additional constraint that the size of the vector x is equal to some input integer More formally, the problem is defined as follows:
k-GSSP (e-Generalized Subset Sum): Input: Two vectors of positive integers (U1, U2..... un) and v (V1, V2,... ... Vm). an integer k and a positive (target)
integer T.
Output: Yes, if there exists binary vector {0, 13' such that ||x|| k, and for any binary vector y E {0, 13m it holds that: D/m1 (x; u,) + DyEl), v2) * T; and No otherwise.
We next prove the following claim: Claim 8. The query k-GSSP ΣP -complete-hardd
Proof. We present polynomial time reduction from GSSP to k-GSSP, enabling us to conclude that k-GSSP is EP- hard. Given (u (n) U2,.... u.), v (V1, V2,.... Vmn) T), define some G 0. The reduction then constructs (u' = (n, + G, U2 + G...,, uj G, GI....,, i-th occurrence of the value G)..
= (V1, V Vm), k = 1 = T (1 (I-G)) (where G; is the
First, assume that (u, v, T) E GSSP. By construction, this implies that:
3x E 13
Vy (0, 13
Ex D v2) F
(64)
Let an element of (0, 13. Therefore, for this x, the following holds:
Vy E (0, 1)mh
>. Dل (x: u.) + (y, V2) T
(65)
We express: [|x|]] = r $ I. Next, we divide the / summations into two parts: the first sum will include the corresponding values in u with non-zero coordinates in x, and the other part will include the remaining values u. For simplicity and
39

---

What makes an Ensemble (Un) Interpretable?
w.l.o.g., we also reindex the coordinates accordingly so that, w.l.o.g,, all nonzero coordinates the first ones of (this w.l.o.g. since binary vector x' E {0, 1 where the first coordinates are identical to the given vector and the remaining coordinates are constructed as follows: the first (Z - r) coordinates of the second half, i.e., coordinates (1 + 1) to (21 r) of x', will be "1", while the remaining coordinates of x', i.e., from (2l r + 1) to (21), will be "0"
reorder the corresponding coordinates in accordingly). Next, given this x, can construct new
2 = (X, u/) =
E u') + Ei (x/ u/) + D (x) u/) E 21 21 (x/ u/)
(66)
E (x, (u, + G)) + 1i (0 (u, + G)) + - (1 G) + 2- G)
-x u.) + (r G) + ((1-))
And as (w.l.o.g.) the last (1-r) r) coordinates for x are "0", it follows that for this constructed x', we can sum up to (and not "only" r):
(x u/) E (x. u,) + (1 G)
(67)
Now, suppose, by contradiction, that for this constructed x', it holds that:
By E (0, 2x u/) 1 v,)==1 =
(68)
Then, according to Eq. 67, it follows that:
By E {0,1) (x, u,) (1. vy) = T
(69)
And from the definition T T
+ (1 G). we infer from our assumption that:
By 10, (x
u.) + (I-G) 2m 2y, T + E E 13 (x: u.) + ولا vy) =
(70)
However, this contradicts the outcome from Eq. 65 concerning this specific Therefore, our assumption is incorrect, and thus for the constructed x' E 1). with ||x||] I = W,, it follows that:
Vy E (0, 13
(x u() + 2 #
(71)
Therefore, we can conclude that: (u', v K, T") k-GSPP Now, suppose (u, v, T) & GSSP. This implies that Vx {0, 1/::
By E (0. 1)
1x= u:) + Ey=n(y, V2) T
(72)
We need prove that this implies the following:
VX' E 10 s.t ||x'|| k3, D ( u() + و (yg v') = T"
(73)
By E 10,
Let us assume, for the sake of contradiction, that this is not the case, i.e.:
||x||1 K, 2 u&) + ااااا V2) T
E (0. 21 s.t
(74)
vy E (0, 13
40

---

What makes an Ensemble (Un) Interpretable?
Let E {0,1)² 1) represent binary input x' E {0, 1322 Therefore, ||x'|; k' = Assume 1 S 8 < corresponds the number of "1" entries in x' located in the first I coordinates of u', with the remaining (K' s) (1 s) "1" entries of x' located in the second half of u'. Further, assume without loss of generality that the first coordinates of x are "I", and similarly, without loss of generality, that the first (1-3 s) coordinates of ((0+1)....11 (i.e., the second half of x's coordinates) represent the locations of the remaining (1 - s) "1" values. Therefore, we establish that for this x':
Vy E 10,
E u + 11=0+1 (x) u!) + D u()+
>0 21 s+1 (x) u/) + 2 vj) # T'
wy 1)" Ex u/) + E (0- + 2 (x) +f+
(75)
Σ - (0 u') + و v/) T
E (0,")", E u') + -ب (x/ u') + و vy) #
vy E 1), E (u; + G)) + - (x) G) + -2 (8; T
Similarly, by partitioning the summation and considering the coordinates of x', we can deduce that the aforementioned equation can be rewritten
Vy [0,1)", ( G)+ 2 GG) (y, = vy E 1) + 8)) G+
(76)
> و (1+++=+ =
vy E 10 - +2 vy) #T
Equivalently:
Vy {0, 13"h, E5 (1.,),,,) + E 1 (0- u.) + +- (y3 vy) #
(77)
Let us define an input x" E (0, 13, such that the first < < I coordinates are "I", and the remaining ones are" In other words, x" = 1...q Therefore, given Eq. 77 and the specified x" E 1),, it follows that:
Vy E 10 (x
1- (y, v2) #T
(78)
However, this contradicts Eq. 72, and therefore we determine that our initial assumption is erroneous (i.e., such x' E 10, exists), and:
Vx' fo, 17 s.t ||x'|1 k, M (x} uf) + En (y, v')) = T"
(79)
By E 13
Thus, (u',V','T "'"" r")+ & K-GSPP. To conclude, we have proved that: (u, v. T) E GSSP + (d,,VH,TT)) K-SSPP completing our reduction.
Next, we introduce variant of the k-GSSP problem, which we refer to as the k-SSPP problem.
k-GSSP" (Constrained k Generalized Subset Sum):
Input: A set of positive integers (Z), .2,ZZ.....22.. 2,),, subset So, an integer and a positive (target) integer T., Output: Yes, if there exists subset of features (indices) S C Su, such that, |S| = k, and for all subsets S' C $ it holds that Eies(Z)) + Ejes (7,) & T; and No otherwise.
41

---

What makes an Ensemble (Un) Interpretable?
Now, we will establish the hardness of this refined query by demonstrating the following claim:
Claim 9. The query k-GSSP" is Eig -complete-harl
Proof. We will demonstrate 2/ sc-oplltee-arddeeee hardness through a reduction from the k-GSSP problem. Starting with (u (u,, Ug,..... Ur). v = (Vi, Y2...., Vm), k, T") we produce (z = (Z1, .,....,,,................ So = (l,...,,)) K, ,"). The vector
formed by concatenating u and in the following manner:
(u'"v) (==((m)), i... for any 1 i 1: u, and for any (1+ S (1 m1) 2
u' = [2n + 1) u| + i.e. u/j = [22 + 1) un] +1
r (2n + 1) i... v = (2n + 1) va
We also set T = T(2n + 1) + l and k' == k. We then will prove that: (, E k-GSSP So K' K,T") k-GSSP".
First, suppose (u, vk, 7' E k-GSSP. Then, there exists a binary vector x E 0, such that |x|| = k and for any binary vector y E 0, 1m, the following condition is met: Σ (x: u,) + Dn (y, V2) * T. Assuming, without loss of generality, that the first & entries of u align with this particular binary vector x E (0, 1 (note that |x|| = k), we define the subset $ to include all corresponding indices, thus S = {i|x; = 1} = [l....,dd k} S So. We will now establish that for all subsets
S' S 3 = {kk + 1).................... 1, (1+ 1)...., n = (1 + m)} the following holds true for our chosen set
Exe((z) (2)) TT
(80)
We will demonstrate this in two parts: initially by considering subsets of S that include only features from +(1+ 1).... ., (1 + m)). and subsequently by considering subsets of Š that intersect with {(k + 1).....?}. In the first scenario, consider all
. (I + m) n). meaning the features correspond exclusively to those in the original v vector. For this particular E {0, 1Y, it is established that for any E {0, 1)
S' C S where S' C ((l + 1)....:
E/ (x. u:) Mn 2 VJ) HT + (2n + 1) (x: u.) + (2n + 1) (y1 v,) + T(2n + +1) =
(81)
(2n - 1 (x, u;) + (2n + 1ر (y3 vj) + k + (2n + 1) +
Given that |x|[] = k, we proceed under the assumption (w.l.o.g.) that the first k indices of x are set to "1", while the remaining (7 coordinates are 0". Therefore, for any y E (0, 1)m:
(2n + 1) (x; u:) + (2n + 1) 1) u++
(2n + 1) (y, v3) + + =
(82)
2 1) X; u,) + - - (2n +
u,)+
E (2n + 1) yj vj) + +
And, assuming (w.l.o.g.) that the first ie coordinates of x are "1", with the remaining ones set to "0", follows that for any y E 1)m:
k ((2n 11 u:) (2)
(,2n + v.)
(83)
D 2= ((2n + 1) 1 1. + Σm ((2n + v, v -
Ek ([2 + 1) u, 1) 1 (2n+1) vy) T
Given our definitions of u' and v', it follows that for any y E (0, 1)
42

---

What makes an Ensemble (Un) Interpretable?
E + دy= vy) T
(84)
Since S encompasses the first & coordinates of u' (which align with the & "1" coordinates of the specified by design), it results that for any y E 10.
Ezs + (y (+z)) + T
(85)
Therefore, for all S' C where S' S [11 ,1 m)) it established that:
Enes(?)) + Eiesrcs(zi) #
(86)
In the second scenario, we consider any subset S' C S that intersects with {(A 1)...., meaning there is at least one feature i S' such that (k + 1) I i S I. We note that, according to our construction, S contains exactly l indices, each corresponding to a value of [2n + 1) u,] 1. In this second case, 5" C S includes al least one index that corresponds to value (2n + 1) u, + 1 (corresponding to u') and potentially other values of (2n + 1) V, (corresponding to v'). Consequently, when adding the values associated with the indices from and S", we obtain at least (k: + 1) values (and at most, n), with least + values being such that mod (2n 1) 1. Therefore, the total sum will yield value with
modulus of least k + over (2n + 1), implying that:
[les(z])]oode +
[Eiesigs moud((( + 1) S 11 k
(87)
(Eies(z)) + ( + 1) +
Lastly, given that T' = =2n + 1)T + k. it follows that (T") mod (2n + 1) k. therefore:
ExEs(Zi) + Eies's((4) T' (2n + 1)T + k
(88)
Thus, we have demonstrated both scenarios that for our defined $ C So, is true that |S| k and for all subsets S' S = {(k 1).....,, + .,....r. (1+ m)}, holds that:
Eis((z) + E)es)ss(2)) T
(89)
Hence, So, K..T) T') E k-GSSP"
For the other direction, if (u, v, T) & k-GSSP, then for every binary vector x E 1), with |x|] k, there exists a binary vector y' 10m such that: [x, u&) + My (y'j vj) = T. For every k-sized subset S S Sg. we define x' = Lies. Additionally, for each fixed S, we define the set S C S to be:
S' =
[[uu o)ly? 1}
(90)
for the corresponding y' that aligns with the indicator x' associated with S". Next, we observe that:
43

---

What makes an Ensemble (Un) Interpretable?
Eies + Eee (1)
Exes (u/) + E.
Een + 1)u; + 1) + - jes' (12n + 1)v;)
(2n + 1)( + + jessss (v:) + |S| (**)
(91)
(2n + 1) (x) u:) + 1リー (5) vy)] k
(2n [)[ + k
(2n + 1)[ T" k
2n tk=
[T"
k] + +
Where (+) arises because we have selected S' Ç S to exclusively contain indices values pertaining v² (i.e., S'nl. + i), and (#0) is due to considering any subset S S So with size of |S| = k. Therefore, conclude that for all k-sized subsets S C Sg. it is established that there exists subset S' C S such that:
Eie((z)) + Esesrcs(Z,) = =T'
(92)
Thus, (z, So, W,, & k-GSSP", as required.
We will now present the final component of this proof by establishing the following claim:
Claim 10. The MSR query for an ensemble of k-Perceptrons is Ei- -complete-hard for k 5.
Proof. We will outline polynomial-time reduction from k-GSSP' to k-perceptrronMSRR, specifically for k 5. Given Sp, k, T), our polynomial-ting time reduction produces ((fi..... fa), x', k), in the following manner: Initially, the reduction verifies (in polynomial time) whether: Ez=12z;) = T. this condition met, then since z consists solely of strictly positive integers, any strict k-sized subset of these will not sum to T. Consequently, (z, So, k. T") qualifies as belonging to k-GSSP*, As result, the reduction returns, within polynomial time, ((fi == True,... ʃs = True), x', k)) for k- k-Perceptron-MSS as any k-sized set of features sufficiently justifies the condition. Otherwise, if = (z,) & T, the following steps are taken: we initialize x' 1 and k' = k. For each < 5, the perceptron fi is defined follows:
fi = (W1, 61). for = (-Z1, ..... 2,), and 61 == T
f2 (w2, b2). for w2 = =21,,... 2n). and by T 1
fs = (W3, by) ), for W3 =(1s,: Og,) and by - it holds that: fa(x) =1 = Eg (2)) (x)
h + | (1s, A Ax;)+ En
1 (1s, ^x;) 2 k- = Σ - (1s, ^x,) 2 = = E S.) k.
i.e. f3 classifies as "I" if and only if the input has at least "I" values in Sp.
f4 = (W4, 64), for Wa = (O..... 0), and by = 1, i..., =TuTrue
fs = 1 i.e., [x) constructed input x = 1". This setup can be implemented in polynomial time, as demonstrated in (?).)
- x == 1 (i.e., Js acts as a Perceptron serving as an indicator function for the
First, we observe that the ensemble (Jı,..., (s) classifies x' == 1 as "1". This classification results from a majority of at least three (out of five) ensemble members designating the input 1" as "I":
fx() step step(E) Sol (x/ k) step ( k) step([Sol k) =1
(93)
Thus, = =1 Additionally, f1 = 1, as it classifies every input as "1", and fo(1") = as functions as an indicator for this very input. We will prove that: (z, Sp. k. T) E k-GSSP" + fs), x², R*) E MSR for k-ensembles of Perceptrons when k x= 5.
44

---

What makes an Ensemble (Un) Interpretable?
Initially, assuming that (z, So K, T') E k-GSSP" there exists subset S C So with |S| k and for every S S it holds that (z,)(z)) + Ejes+(2 (2z) # T. We then contend that S serves k-sized explanation for input x' = 12 within the S-Perceptron ensemble (f1, f6). When considering S, we conclude that for every S' C S: Exes(z) + Ezes((y)) TT,
or equivalently, for each S":
(Z))(Z)) + PJES:(Z)) 2 T + (E(e(()) + (z)ss
ST-1 -
(94)
We will demonstrate that in both cases, exactly one of fi and fz classifies an input "T", while the other classifies it as "O". In the scenario where (z;) + Ejes' (zz) 2 T 1, for any input {0, 1)"h with Xş 1S, we construct (x): applicable for E {0, 1)"h and for every E {0, 1 1 ensuring that both (2((xs:5s) = 1 and Si (i((xs))s) O. Moreover, fa((xs:ys) = 1s, based on the following:
f2((xs:8s))
step([(Xs:\s) w2] + b2)
slep(((xs:Ns) (zI,..., 2n]] + (-T - [
1
(95)
step(Enes(x: z,) jys(yy; 7z) - T 2
sTep((T + +1 T - - stepl 1
()) =1
In this case, also true that ((xs:tss) = 0, as the following holds:
fi((xs)33) =
step([(xs:ys) wil + b1) =
1
step(((ss:ys) (-z,...., zn)1 (T
2
(96)
step(-Eres(2)) - Ezes(2)) + (T step(-(T+1) + (T }/ = step(
)
2
3
=0
2
With the last transition justified by the assumption that: (zes(z;) + EzE 2 T 1, and we also observe that we have
selected S' = 5 (which is valid since trivially 8 C 5). In the situation where Exes(z,) + Eyes (z,) < T - 1, for any input E 10. with xş- = 1, we construct (xs; suitable for E {0, 1)a and for every y E {0, } ensuring that both fi Vs)) = and (x((x:)s)) = 0. Additionaly, fi ((xs:yss) = 1, based on the following:
fi((xs:85)
step(((xs:Vss wi] + b1)
1
step(((xs:ys) (- 2i...... - 2n)1 + (T
(97)
1
step( ( [xE 2,) + (y; z,)l T
2) )
step((-1)(T 1)) 1) + T } step(1 - T + } stepl ,) =1 )1
In this scenario, also holds that f2((xs: 0. as the following holds:
45

---

What makes an Ensemble (Un) Interpretable?
[2((Xs:8s)) =
step(((xs:\s) W2] b2) =
step(((xs:ss) (Z), ( kn)] + (-T
2) -
1
(98)
1
step(Eies(e) + Sees(()) + (-T
7)1=
1 2 ) = slep(
slep(T +1+
2 =0
The last transition remains valid under the assumption: (i,s(Z,) Ejes (z,) S We further observe that S' := S, which is valid since S S S by definition. Therefore, when (1,s(z,) Eyes' (z,) * T, it follows that exactly one of the Perceptrons in the pair (f1, f2) classifies the input (xs: as "I", while the other classifies it as "0"
Furthermore, /a((Ns; also observed that ((x::))s)) 2 O, implying that it evaluates to True (classifying all inputs as 1"). Therefore, when values of "1" are set in S. one of two outcomes occurs: either the majority (f2, f3, fa) or the majority (f1, fs. fa) classifies every input (s) as "1" for every possible y {0, 11"h. Consequently, serves k-sized sufficient reason for input 1 with respect (f2.-..-
because Ys) contains k "I" values, which is the threshold required by fa to activate. It
thus (ISi....JJa x', k)) MSR for k-ensemble Perceptrons when k: 5.
For the second direction, assume that (z, kg,,, & k-GSSP" We aim to demonstrate that this leads to ((f1.... fs).....f...... xx, k²) & MSR for k-ensemble Perceptrons when k = 5. For the sake of contradiction, suppose the op- posite is true, i.e., are & features in x = 1s which, when fixed, result the ensemble consistently classifying as "I". We will prove this to be impracticable by examining the only two scenarios: (i) that these features are all contained within So; (ii) that at least one of the fixed l features resides in Sg-
"is....,J)s. ,", k²) E MSR for k-ensemble Perceptrons when k = 5. In other words, we posit that there
In the first scenario, assume that all A features are within Sp. Yet, since So, K) & k-GSSP", it follows that for any input Vs) (for any k-sized subset S C So and any E 1)"), there exists corresponding {0, 1)" such that:
(z,)(Z)) + Ejes T
(99)
This suggests that both fi and fo classify the input (xs:y3) as "0", which we will demonstrate below. Additionally, h ((xs:ys)) = 0, as evidenced by the following:
f(((xsiss) step(((xsiVs) wi] + bb)
step(((xs:ys) (-2)....,, -n,) + (T" - 5)
(100)
- (Sssss 4.) + 5. Syjes(y; zy)l + T 5/
step(-T +T } slep( - -/2
Additionally, f2((xs;ys) 0, as the following holds:
[2((xs:3s)
step([(xs:ys) wz] + b2)
step(((XsiNs) (Zz, (Zi,...,,,,, 2,,]] + (-T \/2
1
(101)
step Eie((x) 2.) Mes(s,; 2,) - T 1
)
step(T - T - 2 = stepl
0
2
46

---

What makes an Ensemble (Un) Interpretable?
Therefore, under the assumption that all k fixed features within So, there exists an input y E {0, 13" such that for the input y both fi and fa elassify Si (()()::))) 0 and f2((x);ys) = O. Next, will demonstrate that the input (Is; 05) of 1", i.e., it contains at least one feature with value "0". This is because, for the defined fi and f2, it is not possible that both f1") 0 and f=(1") O, as this would require:
= =(1")= 00 _
(slep(>)= (1 -z:) + (T - =1 = 0] ^ (>lep( (1 . 22) + (-T (-T- = _
1
p= (1 -2i) + (T - <0
2.) + (-T --T-5) 1
<0| -2]00 =
(102)
1
- (1 2,) > T
1=1 (1 (1).4))<++ <T+
1
<T+ 1
T
3 1= (1.2)
2
Given that the z, values are positive integers, this is only true if Σ₁- =;=1 (1 2.) T, which contradicts our assumption. Therefore, for 1 it is not the case that both fi (1") = 0 and f2(1 = 0. Consequently, the existing input y E {0. 1}" such that both fi ((xs::y)) = 0 and f2((xs:ys) = 0 is not i.., (1s:0s) + (1s; 1g) = 1". In this scenario, it also holds that for this input (11s1 s; 0ş)) = 0, since /a is an indicator for the input 1 Therefore, for any k fixed inputs originating solely from So, there always exists an (1s: 0g), such that the perceptron majority (f1. fz, fs), and thus the ensemble overall, classifies this input (1s; 0g) as "0", contrary to the initial classification. Consequently, given our premise that (z, So, k, T & k-GSSP", no features from So qualify as sufficient reason with respect to 1".
In the second scenario, we examine the case where not all k fixed features are in So. which, under our assumption, means the MSR (Minimum Sufficient Reason) consists of at most (k: - 1) fixed values of "1" in Sg- We will show why this is also infeasible. We consider any completion with exactly |S] - k "0" values in the features of S to illustrate this point. Using the same logic as previously, based on the configuration of f1 and f2, it is established that for any input - at least one of fi or f2 classifies it as "0". As demonstrated, exactly one Perceptron of the pair classifies it as "O" when the summation of z,-S does not equal T. and both of them classify it as "0" when the summation equals T.
Furthermore, any input with at most k- 1 "0" values in features corresponding S is classified by fs "O", since fs activates only when it detects at least k of S's features as "1". Additionally, any input that includes more than a single zero value is clearly not equal to 1" and, therefore, will also result in f's classifying it as "O", given that fs serves as an indicator for 1" (classifying any other input as 0*). Thus, in this scenario as well, there is a majority of (f1, fa. ft) or (fz, fa. ft), and consequently the entire ensemble, classifying any such input as "0".
This indicates that any sufficient reason for our ensemble must have a size of at least (k: + 1), and therefore: fo)....,)).. K") & MSR for k-ensembles of Perceptrons when k = 5. In summary, we have demonstrated that (z, So, T) k-GSSP" = ((f1,..., fs),'', x,, k²) E MSR for k-ensembles of Perceptrons when k 5. Thus, solving the MSR query for k-ensemble Perceptrons is Ef -hard.
K. Proof of Proposition 5.3
Proposition K.1. For ensembles of k-decision trees (i) the CSR query is coW[1]-Complete (ii) the MCR query is W[I)-Hard and in W[P], (ii)) the CC query is #W[[)-Complete, and (iv) the SHAP query is W[1] and in XP.
Proof. We begin by demonstrating the initial complexity result stated in the proposition:
Lemma K.2. For ensembles of k-decision trees, the CSR query coW[l] ICCoppltte
Proof. We execute a many-one FPT reduction from the complement of the Multi-Color Clique problem to the corresponding CSR query, and from the CSR query to the complement of the k- t-Clique problem. Both the Multi-Color Clique and the t-Clique problems are known to be W[[]-Complete. We will begin with the first direction to establish membership in coW[1]. We start by defining the k-Clique problem:
47

---

What makes an Ensemble (Un) Interpretable?
k-Clique:
Input: A graph G (V, E).
Parameter: Integer kt.
Output: Yes, if there exists a clique of size larger than 4t in G.
Membership. We initiate the reduction by demonstrating membership in coW[1]. As discussed in Section B, our aim is to establish membership for the weighted voting scenario. However, for clarity, we will initially focus on the simpler case of regular majority voting. Subsequently, we will elaborate on how this proof can be extended to the weighted version.
Membership for standard majority vote. We will specifically demonstrate reduction from CSR k- k-Clique, establishing that CSR resides in coW[1]. Given instance (f, (,,,S) 5), CSR inquires whether S is not sufficient reason with respect or in other words, if S is contrastive. We will begin by establishing the following claim, which concerns the fact that ensembles of decision trees are closed under conditioning (refer to Definition G.2):
Claim 11. Given a model which is an ensemble of k decision frees, some input x, and subset S [n], then is closed under conditioning.
Proof. We first observe that any individual decision tree in the ensemble can be conditioned over Xs. This is accomplished by creating modified model f/ as follows: start by duplicating f., that is, f := f.. We then iterate through the tree from the top downwards, examining all splits. Each split corresponds to an assignment to a feature which can be set to either 0 or 1. j E S, we will retain all paths that extend from the subtree and follow the assignment X,, while deleting all paths that follow the assignment X,. Ultimately, the resulting tree Si adheres to the following condition:
Vz E [[((Ns: 4s) = f((z]
(103)
We observe that following the modifications, any split in the tree f/ concerning the features j E S results in only one viable path, as the subtree associated with the contrary assignment was removed earlier. Consequently, f effectively becomes a tree defined solely over the features in 3. Therefore, the following assertion is valid:
Vz E [f((s: = f. (zs)
(104)
We have thus demonstrated that single decision tree is closed under conditioning. By applying this procedure to each tree within the k-ensemble f, we arrive at the following conclusion:
Vz F [f(xs = f'(zgl
(105)
We will establish a secondary minor claim that will be beneficial for our reduction:
Claim 12. Given model J which is an ensemble of k decision trees, then f' := -f =-==ff
can be constructed in polynomial time.
Proof. We first note that negating single decision tree can be achieved by switching each leaf node's 's assignment from "1" to "0" and vice versa. Applying this modification to any decision tree fi within the ensemble results in negating the entire model f.
Now, employing Claim 11, an ensemble f can be conditioned on a partial assignment features, allowing us to develop a new model f' that is conditioned on Xs. In simpler terms, f' retains only the features from and satisfies the following condition:
Vz I (x(x;77))= (7g))
(106)
Given the ensemble f fe...., fx). the reduction constructs f'= (fl: .,, fl) and uses it to construct a graph G. The final setup of the reduction is (G, W = [+1). We will now detail the construction of the graph G. First, we compute
48

---

What makes an Ensemble (Un) Interpretable?
('(x), which is equivalent to X [xx.. If ((xs) 1, we negate the ensemble f'. This negation is carried out using Lemma 12. Thus, we can generally assume that f"(xx) O.
The graph we construct will be k d--pattite graph, with each part corresponding to each tree in the ensemble f'. The vertices and edges of the graph are constructed as follows: We iterate over the leaf nodes in each tree of f', and every leaf node corresponding to the assignment of -x)(x) is designated as a vertex 0j in the graph (associated with the specific tree this node is part of). We will now proceed to describe the construction of the edges of the graph.
First, it is important to note that any two vertices within the same part of the graph (i.e., associated with the same tree) will not be connected by an edge. We iterate over any two paths in two distinct trees and hence associated with two different parts of the graph. We consider two paths, and a', from different trees in f' to "match" if they do not "collide" on any variable. Specifically, there should be no feature i associated with both and a' where the assignment of i in is X; E {0, } and the assignment in a' is -X The two paths "match" if there is no such collision.
Now, each vertex 02 in the graph is linked to a particular leaf node in one of the trees (and consequently to the path a that leads to this leaf node). The reduction will establish an edge between any two vertices vi and My, which correspond to paths and a' from two separate trees, if and only if the paths a and a' "match" and both paths conclude at a terminating node with True assignment, that is, classified as 1.
We will now prove that S is not a sufficient reason with respect to (f.x) if and only if there exists clique in the graph of size larger than k' : 1 The proof will be divided into several distinct claims. First, we will establish the following claim:
Claim 13. For the uforementioned reduction construction, S is not a sufficient reason concerning (fxx) if and only if there exists a partial assignment za for which f' (z(z))
Proof. By definition, S is not sufficient reason for (f,x) if and only if:
3z F (f(xs;z)) + f(x))
(107)
This equivalently means that S is contrastive with respect to (f)x). Given that S' is conditioned on Xy and includes only the features from S, it equivalently follows that S is not a sufficient reason concerning (f,x) iff:
F (F((z) + (' 0] EE (F(zz) 1]
(108)
This equation holds based assumption about the negation of f' during its construction. Additionally, the condition where f' (((z)) 1 occurs if and only if at least [1] models in the ensemble f', specifically "'....,,'TT have I f'i(z)) 1.
We will begin by establishing a smaller claim.
Claim 14. For the aforementioned reduction construction, the following condition is satisfied: there exists some z E E for which f'(Es) if and only if there exists subset of 2 [ trees: I.....,Jr f in which it is possible to select one path ag in each tree fl such that each path terminates at "True" (classification = 1) node, and each pair of distinct paths "match".
Proof. We first observe that upon proving this lemma, it will be established that the claim (the existence of j 2 [ trees satisfying the aforementioned property) holds if and only if S is not sufficient reason for (f.x). x). This is a direct outcome of the equivalence property mentioned in equation 108.
Let us assume we have a set of j different paths an, Oj within j distinct trees: f", .., J',' where each J is model from the ensemble f with each path chosen within one of the trees. All paths are selected such that they terminate on a "True" node (assignment 1) and every pair of paths from two distinct trees "matches". According to the definition of "matching" paths, this means that there is no feature i for which paths in two different trees disagree on the assignment of that feature. Consequently, we can adopt the partial assignment 7; for each feature i that is assigned value in one of these paths. Let us denote this partial assignment as zg for some S' C S. It therefore, follows that if we fix the features in S' to their values in z, the prediction of each one of the distinct trees: fl ,'....., will be classified as 1. This is equivalent to stating that for any S" C S", the following holds:
49

---

What makes an Ensemble (Un) Interpretable?
Vz' E (1' (2s =... (Zsrr 2gyrg)) =1]
(109)
eeeF (f"( f2 (2s (2) = =... (dgg
If we consider 2 1 then it clearly follows that:
Et' E (f
(110)
Therefore, we can assign yg := (Zgr; Z sy) and it will be established that:
YER (1(ys)= =1
(111)
For the other direction, let us assume that there is no set of 2 [ trees that terminate at a 1 "True" assignment. such that there is viable choice of path og each tree !!" where each pair of distinct paths in this set of trees "matches". From this assumption, follows that there is no group of _ trees for which a partial assignment Zs, with S' C S, can be fixed to ensuring that the prediction of all the trees ft" :...... f3 will remain 1. More specifically, this indicates that there is set of j 2 trees for which an assignment to 3 guarantees that the prediction of all ..... f" trees will remain 1.
Since there are no j 2 [ trees where an assignment to 3 leads to all these trees predicting 1, the value of f" will consistently be 0 for any possible assignment to the features in S. Therefore, it is established that:
E (f'(ys) 0]
(112)
This concludes this segment of the proof. We have now demonstrated that S is not a sufficient reason concerning (f,x) if and only if there exists a subset of j 2 [ trees, each with a different path that finishes at a positive terminal node, and where each pair of paths "match". We will now proceed to prove the following claim, which will conclude our general proof:
Claim 15. In the aforementioned reduction construction, there is a clique of size greater than k' 2 I in G if and onty if there exist k' distinct trees in I' with k' distinct paths (one per tree) that end at a True "1" node, and euch pair of distinct paths "match".
Proof. Assuming that there are k' 2 [k] construction implies that each of these paths corresponds to vertex in G (as they terminate 1 node). Furthermore, given that these paths "match" according our construction, there will be an edge connecting each pair of vertices. Consequently, the set of these k' vertices forms clique in G, establishing the existence of clique of size k' in G.
2 paths k' distinct trees that "match" and end a (True) node, the reduction
For the second direction, suppose there is no subset of k' trees or more. This equivalently means that for any subset of j 2 12 paths chosen from j distinct trees that end on a node, there exists at least one pair of distinct paths that do not match. According to our construction, this implics that the subgraph G" C G. corresponding to these vertices (each representing one of the paths), not a clique. Therefore, it follows that for any subgraph G' C G with [ or more vertices, G' is not clique. This completes the reduction.
Membership for weighted Vote. In our previous proof, conditioned f on the partial assignment xg to derive the model f' We demonstrated that S not being sufficient with respect to (f,x) equates to satisfying assignment in f", We will now extend this proof to the weighted version, where satisfying assignment does not necessarily correspond to a set of [ trees with a "1" classification. In this version, each tree f is associated with a weight Φi. and f' is defined as follows:
f'(x) = step( Σ Φi fx)))
(113)
1545n
Therefore, we can implement the following procedure: Iterate over the power set of all possible trees (representing all potential sets of different trees), which includes iterating over subsets S' C (l..... k). This enumeration bounded by
50

---

What makes an Ensemble (Un) Interpretable?
0 and thus can be performed in FPT time. For each selected combination S", representing choice of |S distinct trees,
check whether:
step LES'
Φ f(())) >
(114)
This corresponds checking whether:
step Σ Φi f((x)) step( Σ 0 f((x) Eo: - step( iES'
Σ d. f((x)) > 0 IsiSn
(115)
EE
NES'
Thus, we only need to "check" subsets S' where equation 116 satisfied (as these alone correspond to positive instance of f'). In our reduction, for each subset, S" satisfying equation 1 116, construct subgraph G' in the same manner as in the previous reduction: each path for each tree associated with S' becomes a vertex in G', and an edge between two vertices is formed between two edges iff two distinct paths "match". Additionally, we add k | extra vertices to each such graph, which are connected to all other vertices in G'. We then construct G as the union of all such sub-graphs G' that were derived from each S", and the reduction results in (G,k),
Previously. in the classic majority- vote scenario, we demonstrated that a positive assignment in f' corresponds to a clique in G, with each vertex in the clique representing its associated path in f" Thus, in current construction, if there is positive assignment to f", then there exists some subset S' such that:
step( Σ Φs f((x)) >0
(116)
IES'
This implies that there a subset of distinct trees within subgraph G" that forms a clique of size |G'| (where each vertex in G" corresponds path in f'). Since these vertices are also connected to an additional k: - |S'| vertices included in our construction, there is also a corresponding clique of size within G², and thus in G as well.
However, if positive assignment for f' does not exist, it indicates that for any subset of trees S' in f', there is no corresponding clique of size |S'| where each vertex corresponds to a path in f". This implies that any clique is of size less than A | + | Since this holds for any subgraph G" within G, it follows that there is no clique of size k in G, thereby concluding the reduction.
Hardness. To demonstrate that CSR for k-ensemble of decision trees is coW[l]-Hard, we will establish many-to-on FPT reduction from the complementary version of the multi-color clique problem, which is known be W[]]-Complete.
Multi Color Clique:
Input: A graph G = E). such that V ;= (V,.... V4) where each Vi denotes a set of distinct vertices of some color, for which any two vertices associated with a color are not neighbors (for all there is no edge (u, v) E E where u, E V2).
Parameter: & (the number of colors).
Output:
Yes, if there exists a clique of size in G.
Let us consider an instance (G. k). where G a multi-colored graph with distinct colors. We can assume that [V] |V/] = ... .
Vv m. This assumption valid because we can take the set with the maximum number of vertices, denoted marV, and "pad" the parts of the graph with fewer than marV vertices by adding extra vertices that are unconnected (thereby not affecting the size of any potential clique). Consequently, the total number of vertices is vn k.
The reduction constructs model f. which is an ensemble of decision trees, in the following manner: Initially, each vertex associated with a unique binary string of length log(m), ensuring that vertices of the same color have different strings. We then iterate over pairs of distinct colors, ranging from S i < j < k. For each pair, we create a tree ft.j. which is a complete binary tree with depth of (m). This tree comprises features xi, x.2. ... =fog(m) (representing all possible assignments for the tree associated with color i) and z/. 2 zq...., "....,,/omm Zlog(m) (representing all possible assignments for the tree
51

---

What makes an Ensemble (Un) Interpretable?
associated with color j). Each of the (l)g(m) nodes in the tree corresponds to an assignment of all features of xt and x>. Each terminal node in the tree, which corresponds some path, represents pair of vertices in colors and j. If there is an edge between these two vertices, this terminal node is marked with 1 (a "True" assignment); if not, it is marked with a 0 (a "False" assignment).
Now, for each constructed tree (totaling (t) trees), we also construct an additional "dummy" tree that consistently returns "False" (assignment 0). Consequently, the total number of trees in the constructed ensemble is (2) 2.
We initially observe that we can assume the existence of at least one pair of vertices (u, v) from different colors i,j that are not adjacent (if all pairs were adjacent, there would trivially exist a clique of size k). Therefore, we select an assignment where fu, reaches a "False" (0) terminal node. Arbitrary assignments can be chosen for all other features. Let us denote this
complete feature assignment by x. Given that there is at least one tree among the first (*) trees that results in a "False" (0) classification, and all the additional (5) "dummy" trees are designed reach a "False" (0) outcome, the majority of trees in
will classify as O. Thus, it is established that f(x) 0. The final structure of the reduction is (f, S :=
0). Notably,
the number of models in I' is 2 (*), setting the parameter for the instance (fxx S =- 0) at k' : 2 (6)) which is within the bounds of computable function gkk), thereby maintaining the FPT reduction.
We first note that this reduction operates in FPT time, as the size of f is capped by log(n) O(A)), which is naturally bounded by (kg(k) - n²*) for some computable function g. We will now demonstrate that a multi-colored clique of size l or greater exists in G if and only if S == is not a sufficient reason with respect to xf.
Assume there exists a multi-colored clique of size k, denoted as G', within G. This implies that for any two vertices u, v in G", (u, u) C E. Given that edges exist between vertices of the same color, selecting two distinct colors i,j ensures that there is at least one edge connecting vertex from color i to vertex from color j. Therefore, for each tree fi.j associated with a pair of two different colors i, we can select the corresponding path that aligns with the edge connecting these two vertices, and which terminates at a "True" (1) leaf node, as per our construction.
We will now prove that when we select these specific paths, any two pairs of distinct paths "match". This occurs due the following reason: Consider two paths chosen from two distinet trees. Initially, assume the first tree fe, is associated with pair of colors j and the second tree fu.1 is associated with pair k I, where * j * l & I. Since the features of the tree füj are not shared with those of the tree fk,1, any two paths from these trees "match" (they do not conflict over any feature assignment). The more complex scenario arises when two distinct trees, fü, and fyu. involve the colors i, and j, k, where i # j * k. In this case, the features corresponding to i, k are different, but those associated with color j are shared. However, because a clique of size in a k-partite graph includes exactly one vertex from each color, the vertex corresponding to color j associated with the paths chosen for both fi, and fμ is the same. Consequently, the binary string representing the path associated with these features is identical, ensuring these two paths do not conflict over any feature assignment. Thus, in any scenario, any pair of distinct paths selected in this manner for these trees "match".
Therefore, we can assign each of the features in these paths to their respective values within the path. This is feasible because all these paths "match" and have no conflicting assignments. Given that all of these trees are complete, all features can be assigned (i.e., this constitutes a full assignment, not a partial one). We will denote this assignment by z E F. As previously noted, and according to our construction, all of these paths terminate at a "True" (1) leaf node. Consequently, the assignment z results in the first (6) trees receiving a (1) assignment. Since exactly half of the trees in the ensemble are assigned a value of 1, the overall classification by f is 1. In summary, there exists an assignment z for which:
3Z F F 1 f(x) = 0]
=
(117)
If no clique of size & exists in G, then any subgraph G' of G containing k vertices is not a clique. Consider such a subgraph G' with k vertices. Since is not a clique, this means there must be at least one pair of vertices (u, within it that are not connected by an edge.
Consider some assignment z E F. When examining the specific path associated with (x)(x) (for 1 < i, S k), it follows a designated path leading to specific terminal node of the tree ftjj- Additionally, any pair of distinct paths from two distinct trees associated with z necessarily "match" (since otherwise, they would not correspond to a non-contradicting assignment). Suppose, for the sake of contradiction, that each of these paths ends at a "True" ("1" classification) node.
For each tree fi.j, we can identify the pair of vertices (u, v) that correspond to the path representing the binary string of that
52

---

What makes an Ensemble (Un) Interpretable?
path. This involves selecting vertices (u, associated with two distinct colors j. Consequently, this specific assignment z gives rise subgraph G", which includes at least one vertex from each color (since every tree Jij is associated with two vertices- one for each color). However, we will now prove that there must be exactly one vertex from each color in G'. Assume, for the sake of contradiction, that there are two vertices v1, 02 of the same color i in G". Since U1 U2 are in G', there exist (without loss of generality) two distinct trees Júj and fL where i * k. and the path associated with fúj includes vertex 01, while the path associated with fi,k includes vertex v/2. This configuration implies that the paths for fi.j and fi, do not "match" (as the vertex chosen for color in these two trees differs and associated with a different binary string).
We have established that G', the graph associated with specific assignment z, contains exactly one vertex from each color in G, and therefore has size of k. From the assumption of this direction in the reduction, this indicates that G' is not clique. Consequently, this also means there must be two vertices (u, v) from two different colors i A j where (u, v) E E. In terms of our reduction construction, this means that examining ft.j, the binary string associated with vertices u, v leads to a "False" (0) terminal node, which contradicts our initial assumption.
Thus, we have demonstrated that if there is no clique G of size k, then for any arbitrary assignment z, not all of the first [()] trees in f receive 1 assignment. In simpler terms, least one tree receives a 0 assignment. Consequently, in the ensemble, any assignment results in at least [(] + 1 trees being assigned 0, ensuring that the ensemble classification is always 0. In other words:
= f(x)] Vz e F [f(z) = 00
(118)
This indicates that S == 0 is a sufficient reason with respect to (f, x), thereby concluding our reduction.
C Lemma K.3. The CC query for k-ensemble of decision trees is #C(lleComplete.
Proof. We note that the CC query is the counting version for the CSR query, for which we already proved coW[ Completness. The proofs of membership and hardness where from the k-Cliqqe, and k-Multicolored-Clinn -Ciiue problems. It is well known that the counting version of k-Clique is #Wmll-Complete (Flum & Grohe, 2004). Moreover, there exist FPT reductions to and from k Multi- Color Clique to t-Clique, which shows us that Multicolored clique is also #W[1l-Complete. Finally, we arrive at that the CC query for a & ensemble of decision trees is #W[l]-Complete.
C
Lemma K.4. The MCR query for a is-ensemlle of decision trees is 3-Had and in W[P].
Proof. Hardness. Specifically, the hardness results are consistent with those presented by (Ordyniak et al., 2024). However, we can also directly prove hardness by presenting a reduction from the previous (complement of) the CSR problem for ensembles of decision trees, which we have shown to be coW(1]-Complete (via FPT reductions from k-Clique and k- Multicolored Clique), which will prove hardness beyond majority-voting ensembles. The complement of the CSR problem equivalent to validating whether, given some ʃ. x, and subset S, it can be checked whether S is not a sufficient reason for (f, x). This is equivalent to checking whether 3 is a contrastive reason for (f.x).
Hence, given instance (f,x, S) can apply Lemma 11, which states that ensembles of decision trees closed under conditioning, We will condition ʃ on Xş to construct f". The resulting model I' will have |S] features, and it holds that:
= Vz F F [f(
(119)
Now, given the instance (J,x,S), S) the reduction will construct: (J", x, k: == (S)). If S is not a sufficient reason for (f,x), this implies that S is contrastive reason for (ff, x), and therefore:
Z (f(xszz)) s(x))
(120)
This further implies that:
3z E (f((z) f(xs:78) f(x) = f'(x))
(121)
53

---

What makes an Ensemble (Un) Interpretable?
which indicates that 3 is a contrastive reason for (f',)). Therefore, there exists contrastive reason of size [ for (f", x). If we assume that S is sufficient reason for (f,x), then it holds that:
E [f(x)= f(xs;zs) 7 Vz F (f'(x) f(x) - f(x::zg)) (((z))
(122)
This indicates that S is not a contrastive reason for (f", xx), and that any subset S' C S is also not a contrastive reason for (f',, x). Hence, it follows that there is no contrastive reason of size [S] or smaller for (f',x). This completes the reduction, thereby proving that the MCR query for an ensemble of decision trees is W[1]-Hard.
Membership. We will prove membership in W[P] by reducing the MCR query for k-ensemble decision trees to the WCS[Ca, 2 problem, deseribed in Section C. Given an instance (f, x, D), where D represents the size of the contrastive reason we are looking for, we construct Boolean circuit C. Although the weft of C is 2 (and could be reduced to I with a more refined construction), its depth will depend on parameter D and will not be bounded by a constant.
Our reduction begins by creating a modified model f' based on the original model f and the input x. Essentially, f and f will maintain the same structure; however, the vector 1, (consisting solely of 1s) in f' will correspond to the vector x in f. and conversely, the vector -x f will correspond the vector O, (consisting solely of Os) in f'.
To carry out this construction, we start by replicating f to create f'. For each decision tree f; in the ensemble f, we examine every node within ft. For each node assignment 8; E {0, 1} where e; + X,, we reverse the 0 and I assignments, with the typical convention that 1 represents the right branch and 0 the left branch. This flipping will be done such that 1 will now correspond to the left branch. If 0 = x,, we retain the original order. This process is repeated across all paths in each decision tree of the ensemble. As a result, we generate a new model f' where each assignment to a value of x; in f corresponds to an assignment to in f'. If f(xx = 1, we can apply the negation principle using Lemma 12 to negate f', and if fx) 0, we can leave as is. Consequently, any vector z F where f(z) * fx) translates a vector z' FF for which fz(z) # 1. Therefore, the problem of determining whether there exists a subset S of size D such that (xg: # fx) equates to finding a vector z' E F with D assignments to 1 (i.e., of Hamming weight D) where (z' o 1.
Now, with f' in place, we will develop a Boolcan circuit C, as outlined carlier. Specifically, we will create Boolean circuit C' with a weft of and arbitrary depth, designed to return True if f' has a positive assignment of Hamming weight D, and False otherwise. The construction will proceed through the following steps:
1. In our ensemble of trees, for each leaf e in every tree f/. we will designate f(r.f() as an input node in the circuit. We will consider two input nodes, V(o.f)) and V(r' .f)), as inconsistent if =j j and v * o'. such cases, we will introduce which is equivalent to ~(B( A ('
a node: [-)( V [-V("",ff)) nodes. This setup essentially encodes the k-Clique problem, except for the final AND encoding involving all input nodes, which we will address in the last step. Recalling our proof for the CSR query, the reduction to the k-Clique problem assists in determining whether a positive assignment exists for f'. We are now tasked with a more challenging problem: determining whether there is positive assignment f' with Hamming weight of d. This necessitates the inclusion of additional constraints.
where both V(v.f!)) and y(or.f) are input
2. To this circuit C, currently encoding the Clique problem, we will introduce more nodes. For each feature i E [n]. we will create new node u, functioning as an OR gate. This node will take inputs from any V(r.fz) where the assignment represented by the leaf' v assigns "True" (i.e., 1 assignment) to feature i.
3. For the final component, we will add another layer to our circuit. For every 1 م S n and for every 0 < d' S D, we define a variable u(j.d'). This variable is configured to be set to True if and only if exactly d' of the features .,. are set to True. Specifically, "(1.0) will take -w1 as its input, and u "(1,1) will take in as its input. All other u ((1dd') variables are set False. For j > we construct u(jad} to take the input:
10--1dd11 A Auj [ u A -4,]
(123)
4. Finally, the output of the circuit is derived from a large AND node that collects inputs from all nodes established in step 2 and those from step 4 of the form un,d', where d' ranges from to D.
54

---

What makes an Ensemble (Un) Interpretable?
Since that circuit C' effectively encodes a scenario where f' receives positive assignment of Hamming weight D, and considering that C' possesses weft of 2 and arbitrary depth, we conclude that the MCR query for ensembles of decision trees is in W[P].
C
The W[1]-W(P) gap for the MCR query. We note that while we have proven the MCR query for ensembles of decision trees is W[I]-Hard and belongs to W[P], the exact complexity class for which this problem is complete remains unknown. Unfortunately, the current definition of the W-hierarchy is not well-suited to capture the complexity of this problem. Specifically, containment in W[t] for a fixed constant t means that the problem instance hand should be encoded using a Boolean circuit of constant depth (as well as weft t), so that the instance at hand is a yes-instance if and only if the circuit has a satisfying assignment having exactly & variables assigned true, where k is the parameter (or k is bounded by a function of the parameter) of the instance at hand. We refer to Chapter 13.3 in (Cygan et al., 2015) for more information. However, our problem involves a "weight measure" d (the Hamming distance) that may be arbitrarily larger than k. In particular, encoding that a potential solution to the instance at hand assigns true to at most d variables cannot be done with a constant-depth circuit, as this requires the implementation of counter.
The problem described above is fundamental one in the definition of the W-hierarehy in the context of weighted problems in general, where the desired total weight of the solution is not bounded by the parameter. Indeed, it is not known how to classify basic W[1]-hard problems in the field such as Weighted k-Clique, where given a vertex- writh--weighted graph, along with integers & and w, we seek a clique of size exactly k and weight at least/at most W, and the parameter is k. The same situation holds for problems where the "weight measure" is implicit similarly to our problem, such as the Partial Vertex Cover problem, where given (non-weighted) graph G and integers k and f, we seek a set of vertices of size exactly & that altogether cover at least edges. From personal communications with other researchers in the field, we have gathered that the definition and study of a "Weighted W- W-Hierarchy" can be a topic of independent interest in parameterized complexity, but this is outside the scope of this paper.
Lemma K.5. The SHAP query for a k-ensemble of decision trees is #W[1] and XP.
proof. Hardness. We begin by proving that this problem is Hlrrd- Our approach follows the proof outlined by (Arenas et al., 2023). which demonstrates a link between the computation of Shapley values and the model counting problem. First, we provide a definition of the model counting problem. Given a model f : {0, 1)" - {0, 1}. we denote # f as the number of assignments where f outputs 1. In other words:
# = =f==KZEB,ffe = 1H|
(124)
Now, the work of (Arenas et al., 2023) demonstrates the following relationship when the feature distribution D, is assumed to be the uniform distribution, which is specific case of the fully factorized distribution considered in this paper. For any f. x, it holds that:
# =xx==((x)- 2n
Σ xc(f,x)
(125)
This provides direct proof that computing the Shapley value under uniform distribution (and consequently for the fully factorized distribution) is as difficult as the model counting problem. It remains to be shown that the model counting problem for an ensemble of kiddccsion trees is #ommleCo when parameterized by k. Since we have already established that the CC query for k-ensemble of decision trees #W[1]-Complets we can demonstrate an FPT many-one reduction from the model counting problem to the computation of the CC query.
Given model we start by selecting an arbitrary vector x E F. f(x) = 1, the reduction calculates the count for (f, x, S : 0). which we denote as #CCCS x, S). If /(x 0, the reduction computes 2n #CC x, S). We note that 2n can be computed in polynomial time, as n (representing the number of input assignments) is provided in unary.
The completion count seeks the number of assignments where the complement of S (which, in this case, includes all possible
assignments) results in a classification of 1. Thus, if fx) = 1, we have #1 f = #CC(f, x, S), and if f(x) = O, we have
# = 2n #CC( x, S), concluding the reduction.
55

---

What makes an Ensemble (Un) Interpretable?
Membership. We will prove membership in XP by presenting an algorithm that computes Shapley values for ensembles of k-decision trees in ((121*)) time. We utilize the following relation, established by (Van den Broeck et al., 2022), concerning Shapley values under conditional expectations and assuming feature independence. The following relation has been proven:
(, =p (f(22
(126)
In other words the computational complexity of obtaining a Shapley value under this formalization is equivalent (under polynomial reductions) to the complexity of computing (z)D)lf(z)] This means can focus on determining the complexity of obtaining Ez ~ (z)s which can sometimes be easier to handle.
We now present the following algorithm for computing [/)D,[((z)] for ensembles of decision trees in (( time. The algorithm iterates over every combination of selecting one path from each tree in the ensemble f. We assume that j of these selected paths correspond to trees that classify as "1", while the remaining k - trees classify as "0". We first check whether this selection of trees fí ......: Sj that classify as "I" can result in positive classification for f. For unweighted
majority voting, this is equivalent to verifying whether j 2 k and for weighted voting, it involves checking whether the weights Ø associated with each tree f'i satisfy Σ S I jø; > O.
We can then verify whether each pair of paths chosen from the set of paths across all trees satisfies that any two paths "match" (i.e., they do not contain any features with conflicting assignments). For each combination of trees, we examine the partial assignment to all features involved in these paths (there must be only one such assignment since the paths "match"), In practice, this is equivalent to iterating over all possible positive assignments of the ensemble f. However, we note that a single iteration over a selection of paths in each tree may yield only a partial assignment to some features, denoted Zg- for some S' C [m]]. As a result, this assignment corresponds to any assignment of the form (Zsr; Z'z.) for any z' E F (all of which are also classified as "1").
We note that this entire process is bounded by Om*)), where m represents the maximum number of leaves in tree and is the number of trees. This is also bounded by O(X ((k)). We now proceed to prove the following claim:
Claim 16. For two distinct partial assignments and z'z. obtained by iterating through the aforementioned procedure of selecting j paths in j distinct trees, it holds that there exists a feature i E S, such that z; F 2
Proof. Since 2ς and S' are selected from iterating over two distinct choices of paths from trees, there must be least one tree where the paths chosen for z5 and z' differ. Any two distinct paths in tree contain at least one feature with differing assignments for some feature i. Therefore, based on the previous construction, it follows that there exists at least one feature i where the partial assignments of zs and zig. differ.
By definition, the following sum holds:
(A-D,((()) = Σ Dz(2)= =
Σ II p(1) zEF =1 [e(n],==1
(
II (1 p(i))
(127)
ZER 1
xE(m],x:=
That is, computing the expectation involves summing each Dp(z) for every positive assignment. Now, assume we have some partial assignment Zy obtained in the previous phase. Since this is only a partial assignment, we need to account for all possible completions of zg. or, in other words, any vector of the form (æs; z' S). Let the set of all partial assignments computed using the aforementioned procedure be denoted by S. Since any partial assignments have a conflicting feature that does not "match", there is no "overlap" in the assignment completions corresponding to two distinct partial assignments. In other words, for two distinct partial assignments zş and S'S' it holds that for all z" E F, (zs; z" S) + (z' S'). This leads to the following equivalence:
END, (f(2) = - Σ
Dp(zs:4z)
(128)
E3
We do note, however, that for a fixed partial assignment zs, the following holds:
56

---

What makes an Ensemble (Un) Interpretable?
E
Dp(zsiz's=
E
II (e
p(i)
II (E(n),(
(1 (1-p(i))) =
4/ E(U,))188
Σ
II
p())
II
(1- (())
II x63,/=1
p(i)
II 1E3,2==0
(1 (1-p(i))
(129)
1 ((0,))
1682=1
165,==0
II 16S2.=1
p())
II
(1 (1-p(i))
=
Overall, obtain that:
E ENDD []<2]]
II p()) E iES2.=1
Σ
II II (1 (1- (1-r(i)) IES
(130)
Hence, after computing S in (())) time, we can iterate over each partial assignment, compute its corresponding weight, and sum all the weights to obtain (z)) This proves that the complexity of computing Ez (p]f(z) is in XP.
As explained earlier, this also establishes that the complexity of computing SHAP for some (f,x, Pp) is likewise in XP.
C
We have demonstrated that solving SHAP when D, represents any fully factorized distribution is #W[1]-Hard and XP. However, we specifically set D, to the uniform distribution (i.e., where for any i [m], p(i) = })). a specific type fully factorized distribution, then this query becomes #W[ll-Complete.
Lemma K.6. Assuming that D, is the uniform distribution, then the SHAP query for ensembles of k-decision trees #W[ll-Complete.
Proof. The hardness is derived directly from our proof concerning fully factorized distributions, assuming a uniform distribution. For membership, we leverage the analysis by (Arenas et al., 2021b), which demonstrates that when D, uniform, computing SHAP can be polynomially reduced the problem of model counting (i.e., computing # ff). As outlined in Proposition K.3, the task of model counting for a k-ensemble of decision trees is W #W[1]-Coompl [1]-Coepleee. Thus, conclude that computing SHAP under the uniform distribution for k-ensembles of decision trees also achieves #W[1)-Complete status.
C
L. Proof of Proposition 5.4
Proposition L.1. The MSR query for k-ensemble of decision trees is para-NP-Hon and is in XNP.
Proof. Hardness. Para-NP hardness is straightforward since the MSR query for a single decision tree is already NP- Hard (Barceló et al., 2020) and hence is obtained for k k= = 1.
Membership. For membership in XNP we need to show that there exists non-deterministic algorithm that solves this problem in (( time. Specifically, we will make use of the minimum- ciiimumm-itting-see (MHS) duality between sufficient and contrastive reasons to prove this claim (Ignatiev et al., 2020b). First, we will define the MHS:
Definition L.2. Given a collection of sets from a universe U, hitting set h for is set such that VS E S, h S S 0. hitting set & is said to be minimum when it has the smallest possible cardinality among hitting sets.
We note that subset minimal contrastive (sufficient) reason of (f.x) is a contrastive (sufficient) reason that ceases to be a contrastive (Sufficient reason) when any feature is removef from it. In other words, for all it holds that $ \ is not sufficient (contrastive). We now are position to use the following MHS duality between sufficient and contrastive reasons (Ignatiev al., 2020b):
57

---

What makes an Ensemble (Un) Interpretable?
Lemma L.3. The MHS of all subset minimal contrastive reasons with respect (J,x) is cardinally minimal sufficient reason of (), Moreover, the MHS of all subset minimal sufficient reasons with respect to (fxx) is cardinally minimal contrastive reason of (f)x).
Now, we describe the following preprocessing stage which runs in time 0(121*)) and computes all of the subset minimal contrastive reasons of (f.x).
Claim 17. Given an ensemble of decision trees f with k decision trees, there exists an algorithm that computes all of the subset minimal contrastive reasons of (f,x) in time O(m*), where denotes the maximal number of leaf nodes in decision tree within f.
Proof. We iterate combinations of choosing leaf (which corresponds one path) from every distinct tree in This process be done in 0(m*) time. We check whether two conditions hold. First, check whether every pair of two distinct paths that belong to two distinct trees "matches" and whether more than [ of these trees terminate over a leaf with a (x( assignment. For any combination of k distinct paths in which any two paths "match", it means that there is some partial assignment z which describes the corresponding assignments in each one of these paths (there is necessarily one such assignment since each two paths "match") and it holds that:
Vy e F ((((s: + s(x)]
(131)
We now will denote by s", the subset of features zg that do not match with x. More specifically:
S" = lit (1.....S) 2, x
(132)
For each combination of k paths, for which the corresponding two conditions hold, we compute S We denote the set of all such subsets as S. will now prove the following claim, which will finish the proof of our lemma:
Claim 18. Any subset minimal contrastive reason of (f.x) is contained in S
Proof. Let us assume towards contradiction that this claim does not hold. In other words, there exists a subset S which is subset minimal contrastive reason of (f, x) and that is not chosen to be in S by our algorithm. Since S is contrastive reason it holds that:
E (f(xg;zs) + [(x)
(133)
However, we will prove a stronger property that holds if S is subset minimal contrastive reason of (f. x). Specifically, it holds that:
[f(xs: xs) + f(x)]
(134)
or in other words the specific vector z for which fixing S to, changes the classification is x. The proof to this claim is straightforward - let us assume towards contradiction that this is not the case, or in other words, it holds that:
[f(xs: = f(x)]
(135)
Since S is a contrastive reason, this means that there exists some other assignment to the features of (which is not -x, which causes the classification to change. In other words, there exists some y * -x for which:
(s(x): # [xx)
(136)
Since y * -x over the features in S, this means that there is at least one feature E S for which y; = X,, Let us now denote
So 5 S (i). We hence get that:
58

---

What makes an Ensemble (Un) Interpretable?
(x(xs: ((5s; xx,) + f(x)
(137)
This implies that So is a contrastive reason of (f, x), hence contradicting the subset minimality of S. This concludes the proof of this claim, and we hence derive in the fact that since S is a subset minimal contrastive reason of (f, x)) it must hold that:
[f(x3: xs) + f(x)
(138)
We hence can take the assignment -X)) and propagate it through f. The assignment f((x:: -xs) will lead to some path, for which there are at least [ which terminate on -x(x) node. These paths, of course "match" (meaning any pair of two distinct paths "match"), because they correspond to one assignment of features, and hence will be chosen as a combination of paths by our algorithm.
We recall that our algorithm chooses the partial assignment which assigns value to each one of the features in each path of each tree (there exists one such assignment). In our case this will be some partial assignment of (Xg:-Ks). The algorithm then chooses the subset S" which is the subset of features whose values (in case of (x3: xx)) that are different than those of x. Hence, it necessarily holds that S" S S.
We note that S" is contrastive reason concerning (f+ x). since by construction, it describes a subset of features such that if we set them to values that are not of x (specifically -x). & or more trees in the ensemble terminate on a -x((x) assignment. Since we have proven that S" C S, then it must hold that S" = S, since otherwise, this will contradict the subset minimality of S. We hence derive in the fact that S is chosen during our algorithm to be in S, contradicting the assumption that not in S. This concludes the proof that any subset minimal contrastive reason of (f, x) is in S.
We will now use the MHS duality to conclude our proof regarding membership in XNP. We recall that if S is the set containing all subset minimal contrastive reasons of (f, x), then the MHS of $ is the cardinally minimal sufficient reason of xf. We note that if we add to S (which contains all subset minimal contrastive reasons of (f, x) other (non-subset- minimal) contrastive reasons of (J, x) the MHS of S will remain the same. This true since the hitting set of any two subsets S and S², when S C S', equal S.
We have proven that the set S that is obtained by algorithm contains all subset minimal contrastive reasons of (f, x). as well as perhaps other contrastive reasons. Hence, the MHS of S is cardinally minimal sufficient reason of x).
Hence, we can simply non-deterministically guess some subset S C {l, n). and check whether S intersects with all subsets in (and hence is the MHS of S, and a cardinally minimal sufficient reason of (f,x). If |S1]] s d, our algorithm can return true, and otherwise, it will return false. Overall, the entire algorithm that we described performs a preprocessing step in Omm²) time (and hence is bounded by O((x1* time), and then performs a non-deterministic step, also bounded by ((xx)*) time. This concludes the proof that solving the MHS query for ensemble of k decision trees is contained in XNP.
C
M. Proof of Proposition 5.5
Proposition M.1. Obtaining a subset-minimal sufficient reason for a k-ensemble of decision trees is in XP.
Proof. The specific result aligns with a result demonstrated by (Ordyniak et al., 2024). However, we can further establish this result as a direct extension of the complexity result for the CSR query (Lemma K.2), which will demonstrate this result not only for majority voting ensembles. To show this, we use common greedy algorithm that computes a subset-minimal sufficient reason by invoking linear number of queries, each checking whether given subset is sufficient reason (Ignatiev et al., 2019a). Intuitively, the algorithm attempts to "free" feature from the subset S at each iteration, until finally converging to subset-minimal sufficient reason.
Lemma K.2 proved that the CSR query for an ensemble of decision trees is in coW[1] (and hence is also in XP). In essesnse, algorithm M implies that linear number of queries to the CSR query produces subset-minimal sufficient reason. It hence,
59

---

What makes an Ensemble (Un) Interpretable?
Algorithm 2 Greedy Subset Minimal Sufficient Reason Search
Input f.x x
1: S {I....,n}
2: for each E (1,..,,] n by some arbitrary ordering do
3: if {i} is sufficient reason w.r.t (ʃ. x) then
4:
(
5: end if
6: end for each
7:
8: return S {S is subset minimal sufficient reason]
directly follows that obtaining some subset minimal sufficient reason for some (f, is also in XP.
60


Reviews:
[{"review_id": "DXvjCC1XiZ", "reviewer": "Reviewer_i9pr", "summary": "This paper studies the interpretability of ensemble of models from the computational complexity theory. Authors show both negative results (e.g., intractability even for constant-size models) and positive results (e.g., tractability for small decision tree ensembles).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and for recognizing the importance of the results provided in our work.\n\n\n**The importance of complexity separations between base-models and ensembles**\n\nWhile 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.\n\nFor 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.\n\nTo 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.\n\n**What structural properties drive the complexity explosion in linear models versus decision trees?**\n\nWe 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.\n\n**Impact of feature independence**\n\nWe 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.\n\nHowever, 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.\n\n**Improving clarity of points**\n\nFollowing 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.\n\n[1] On the Tractability of SHAP Explanations (Van den Broek et al., JAIR 2022)\n\n[2] On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results (Arenas et al., JMLR 2023)\n\n[3] A Unified Approach to Interpreting Model Predictions (Lundberg et al., Neurips 2017)\n\n[4] On the Tractability of SHAP Explanations Under Markovian Distributions (Marzouk et al., ICML 2024)", "claims_and_evidence": "Yes, there are proofs.", "methods_and_evaluation_criteria": "The paper is a pure theoretical work with no experiments.", "theoretical_claims": "Yes, there are proofs.", "experimental_designs_or_analyses": "No, there are no experiments.", "relation_to_broader_scientific_literature": "This paper has an impact over specific claims surrounding the explainability of ensemble models.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strenghts:\n    \nNovelty and Broad Scope:\n\nThe paper provides a formal, complexity-theoretic framework for ensemble interpretability, addressing underexplored (but sometimes) questions. For instance the fact that k-ensemble decision trees are strictly more interpretable than k-ensemble linear models was not proved before. \n The analysis spans multiple explanation types (sufficient reasons, contrastive explanations, Shapley values) and base models. Thus, the paper gives a more broad picture.\n\n\nLimitations:\n\nThe paper is very hard to read, with several notions on complexity that I think are not necessary. Some of the proofs (e.g., Proposition E.1) are dense and could benefit from higher-level intuition in the main text.\n\nThe paper addresses questions with obvious answers. For instance, Section 4 studies the comparison between explainability of base models and their ensemble counterparts. It is obvious that the former is more easily interpretable than the latter. I don't see why we need a study for the purpose. Why is it even important to answer these questions?\n\nThere are no experiments to show the applicability of the theory discussed here.", "other_comments_or_suggestions": "No.", "questions_for_authors": "The analysis assumes feature independence for Shapley value computation. How would feature correlations impact the complexity results? Would relaxing this assumption require new complexity classes or render the problem fundamentally harder?\n\n\nThe paper shows that linear model ensembles become intractable with just two base models, while decision tree ensembles can be tractable for fixed k. What inherent structural property of decision trees (e.g., axis-aligned splits, hierarchical structure) enables this tractability, and why does this property fail for linear models? Is there a formal characterization of model classes that avoid this complexity explosion?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QwtamJsaMh", "reviewer": "Reviewer_7QPs", "summary": "The paper presents complexity results for a variety of explanation\nqueries on different machine learning models with the main aim of\ncomparing the behaviour of single models with ensembles. In\nparticular, the paper considers the following explanation queries:\nMinimum Sufficient Reason (MSR), Minimum Contrastive Reason (or minimum\nchange required) (MCR), Shapley Additive Explanations (SHAP), and\nvariants of MSR such as check sufficient reason (CSR) and count\ncompletions (CC). Moreover, it considers the following models (and\ntheir respective ensembles): decision trees, linear models, and neural\nnetworks.\n\nTheir main results (which are based on various complexity results for\nthe above mention queries on the above mentioned models) are:\n\n- DT are strictly more c-interpretable than ensembles of DTs for CSR,\n  MSR, MCR, CC, and SHAP and the same holds for linear models for CSR,\n  MSR, and MCR. Moreover, assuming unary weights and biases the same\n  applies for linear models w.r.t. CC and SHAP.\n\n- The above does not hold for neural networks, i.e., for any query\n  neural networks and their ensembles behave the same. This is based\n  on the observation that ensembles of neural networks can be\n  transformed into an equivalent single neural network in polytime.\n\n- Parameterized Hardness results for ensembles of all model types with\n  the size of any single model as a parameter for all query types.\n\n- Parameterized complexity results for ensembles of DTs and linear models\n  with the number of models as a parameter showing that while this\n  parameter does not help for linear models it can be helpful for DTs.\n\n\n## Update after rebuttal\n\nI stay with my initial recommendation because the authors did not convince me that the overlapping results are not a problem. In particular, they did not even address all the overlaps in their rebuttal.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback and for acknowledging the significance of many of our results.\n\n**Relation to Ordyniak et al. (KR, November 2024)**\n\nWe 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.\n\nWe 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.\n\n**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.\n\nOur 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.\n\nFor 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.\n\nSimilarly, 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.\n\n**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!", "claims_and_evidence": "The claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked all proofs occuring in the main text as well as some proofs in the appendix and did not find any issues.", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "This is the main problem of the paper, i.e., various results that are\nclaimed to be new have already been shown in\nhttps://arxiv.org/pdf/2407.15780, which is also cited but not\ndiscussed in the paper. In particular, this holds for almost all\nresults shown for DTs and ensembles of DTs for the query types MSR,\nMCR, and CSR. I am not sure why the\nauthors did not see this, I can only imagine that the authors did not\nrealise that MSR equals local abductive explanations, MCR equals local\ncontrastive explanations, and https://arxiv.org/pdf/2407.15780 also\ncontains results on CSR that were used for MSR.\n\nIn particular, I found the following problems:\n\n- Proposition 4.2: The following results have already been shown in\n  https://arxiv.org/pdf/2407.15780 for ensembles of DTs: coNP-hardness\n  with respect to CSR (lemma 42), NP-hardness with respect to MCR (theorem 36), and\n  coNP-hardness w.r.t. MSR (theorem 36)\n\n- Proposition 5.1: The following results have already been shown in\n  https://arxiv.org/pdf/2407.15780 for ensembles of DTs w.r.t. size of\n  any single model: para-coNP-hardness for CSR (theorem 36), paraNP-hardness for\n  MCR (theorem 36), para-coNP-hardness for MSR (theorem 36)\n  \n- Proposition 5.3: The following results have already been shown in\n  https://arxiv.org/pdf/2407.15780 for ensembles of DTs w.r.t. number\n  of ensemble models: coW1-hardness for CSR (lemma 29,30, and 34), W1-hardness\n  (theorem 35)\n  and in XP (theorem 13) for\n  MCR.\n- proposition 5.5: shown in theorem 13 of\n  https://arxiv.org/pdf/2407.15780\n\n- propostion 5.6: shown in theorem 8 of\n  https://arxiv.org/pdf/2407.15780 (in a much more general manner)", "essential_references_not_discussed": "See previous item.", "other_strengths_and_weaknesses": "The problems considered in the paper are well motivated and\nsignificant and the obtained results are insightful and\nplentyful. Unfortunately, many of the obtained results have already\nbeen known previously and shown in https://arxiv.org/pdf/2407.15780\n(see above). This is of course a major problem for the paper that\ncannot easily be repaired since repairing this problem might (and\nprobably) will change the motivation and problem setting of the\npaper. I therefore have to recommend that the paper is rejected. I\nwould also recommend the authors to resolve this issue and resubmit.", "other_comments_or_suggestions": "I do not have additional comments.", "questions_for_authors": "The main question I have is whether the authors agree with my assessment with respect to the results in https://arxiv.org/pdf/2407.15780.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UPkRRjZXhS", "reviewer": "Reviewer_3LNf", "summary": "The paper provides a complexity-theoretic investigation into the interpretability of ensemble models, focusing on three major types of explanation queries (sufficient reasons, contrastive reasons, Shapley values, etc.) and three common base-model classes (decision trees, linear models, neural networks). The main thrust is that ensembles are often far more difficult to interpret, from a computational perspective, than single base models. The authors show that even small ensembles can push explanation queries into NP-complete, #P-complete, or even higher complexity classes, underscoring fundamental limitations on generating certain forms of explanations in a tractable manner. Interestingly, the authors also highlight nuanced differences among models: while even two linear models can already lead to intractability for some explanation queries, an ensemble of a few (small) decision trees may still be analyzed in polynomial or XP time under certain conditions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback, and for recognizing the significance of our work.\n\n**Discussion on more specialized ensemble schemes**\n\nWe 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.\n\n**Practicality aspects and relation to existing explainability schemes**\n\nWe 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.\n\nWe 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.\n\nFor 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.\n\nGiven 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!\n\n[1] VeriX: Towards Verified Explainability of Deep Neural Networks (Wu et al., Neurips 2023)\n\n[2] Using MaxSAT for Efficient Explanations of Tree Ensembles (Izza et al., AAAI 2022)\n\n[3] Efficient Algorithms for Clique Problems (Vassilevska et al., Information Processing Letters)\n\n[4] Efficient Maximum Clique Computation over Large Sparse Graphs (Chang et al., KDD 2019)", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes, I did not find significant issues for this part.", "theoretical_claims": "Yes. For Proposition 4.2 (complexity separations in linear/tree ensembles) and Proposition 5.1 (dealing with constant-size base models), the reductions appear logically consistent. There is no obvious mismatch in how they construct the gadgets or use known NP-complete problems as a basis.", "experimental_designs_or_analyses": "It is not an experimental paper, so there are no empirical tests on real data sets or performance measures.  The analysis is fully theoretical, focusing on polynomial and parameterized complexity arguments.", "relation_to_broader_scientific_literature": "The paper strongly relates to prior research on the computational complexity of interpretability (eg., references to complexity analyses of single decision trees, linear models, and neural networks). It also relates to the broader literature on knowledge compilation and logic-based explanation, as well as standard NP/#P-completeness references. Their parameterized-complexity approach extends prior lines of inquiry that used W[1]-hardness for single-tree explanation tasks.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths\n1. Comprehensive discussion of three explanation types. The paper studies multiple explanation queries (feature-selection based, contrastive, Shapley) which are popular in different XAI branches.\n2. Clear cases on different base-model. By analyzing different base model (linear, tree and neural nets) and structural parameters, the author clarifies precisely how and why ensembles become more difficult to interpret.\n3. Well-structured theoretical results. The complexity classification including membership, hardness, and parameterized analyses.\n\nWeaknesses\n1. Limited discussion on practical methods. While the theoretical results are strong, there is relatively little discussion on approximate or heuristic strategies to circumvent these hardness results. It would be better to state how these hardness barriers affect real-world usage of ensemble interpretability methods. In addition, elaborating how practical interpretability methods (eg., SHAP) align with or contradict the complexity results would be valuable.\n2. Scalability in practice. Although the paper mentions XP- or W[1]-type results, it is still somewhat unclear which of these might be feasible for moderately large ensembles (eg., k=10 or k=20).\n3. Discussion for more specialized ensemble schemes. The paper primarily focuses on major/weighted voting, but some new ensemble methods apply meta-model strategies or dynamic weighting. It is recommended to provide a deep analysis.", "other_comments_or_suggestions": "No", "questions_for_authors": "Some practitioners still use large ensembles (eg., random forests with 100+ trees), do you have suggestions for which subsets of your results are more pressing in practice versus primarily theoretical?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers appreciate the paper's solid technical work.
However, some of them have pointed out that some of the findings seem similar to those in [Ordyniak et al. 2024], which affects the paper's novelty.
The authors should make sure to properly mention and discuss this earlier work, even if their results were found independently.
Comparing their work with existing research will make the paper stronger.
Decision: Accept (poster)