{"id":"cad6b801-99a5-407c-b143-c98f69f79ac8","arxiv_id":"2506.08216","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A complexity-theoretic analysis showing that the number, size, and type of base models determine whether ensemble explanations are tractable, with linear-model ensembles intractable even for two models.","lead":"This paper uses computational complexity theory to show when explaining an ensemble model is mathematically hard: even ensembles of a few linear models or of very small decision trees can be intractable to explain, while ensembles with a fixed number of decision trees become solvable in polynomial time. It gives practitioners a formal map of which ensemble configurations can be explained efficiently.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix F's φ'' gadget is false: it can turn a Shortest-Implicant-Core no-instance into a yes-instance, so the MSR ΣP2-hardness reductions for tree and perceptron ensembles are unsupported as written.","rationale":"The reader's weakest_assumption focuses on Claim 1, the unproved constant-DNF restriction of Shortest-Implicant-Core cited from Umans (2001). My check identifies an even more basic blocker in the immediately following Claim 2: even granting Claim 1, the φ'' construction used to convert an SIC instance into an MSR instance over an ensemble is not a faithful reduction. The counterexample above lies in the constant-DNF regime (d = 2, three terms), so it directly exercises the lemma as stated. The source of the error is the proof's assumption that an implicant of a DNF is certified by one fixed subset of terms covering all completions; in a disjunction the witnessing term may vary with the completion. Because the SIC-to-MSR reduction is the route by which the paper obtains ΣP2-hardness for MSR over ensembles of decision trees and perceptrons, the table entries 'ΣP2-C' for MSR and the para-ΣP2 entry for k = 5 linear models are not supported by the written argument. This is a correctness risk in the paper's headline separation between tree and linear ensembles, not merely a missing citation. Other parts of the paper, such as the CSR/MCR/CC/SHAP results and the tree-ensemble XP/W results, appear to rest on different reductions and are not affected by this specific flaw. I therefore recommend rejecting the current version while leaving open that a corrected construction could restore the results.","tokens_in":59780,"tokens_out":15677,"duration_ms":195406,"concrete_test":"Run the Appendix F construction on φ = (x1 x3) ∨ (x2 ¬x3) ∨ (x1 x2), tn = x1 x2, k = 1. First, enumerate all completions to verify that neither C = {x1} nor C = {x2} is an implicant of φ. Second, apply the stated rule to obtain φ'' = (x1 x2) ∨ x3 ∨ ¬x3. Third, verify that C = {x1} is an implicant of φ'' because φ'' is a tautology. This directly refutes Claim 2 and shows the SIC-to-MSR reduction is not many-one correct. If a modified 'covering' rule is intended, the same test on the modified gadget would check whether the implicant-core decision problem is preserved.","verdict_should_be":"REJECT","load_bearing_attack":"The weakest point is not only the unproved constant-DNF restriction (Claim 1) but Claim 2, the φ''-elimination lemma, which is false as stated. The proof assumes that an implicant C of a DNF is witnessed by one fixed set S of terms satisfied by every completion of C. For a disjunction this is not valid: the term that witnesses a completion may depend on the completion. Concrete counterexample in the claimed constant-DNF regime. Let φ = (x1 x3) ∨ (x2 ¬x3) ∨ tn with tn = x1 x2, where all non-tn terms have size 2. For k = 1, no C ⊆ tn of size 1 is an implicant: fixing x1 = 1 fails on (x2 = 0, x3 = 0), and fixing x2 = 1 fails on (x1 = 0, x3 = 1). Running the paper's construction, for t1 = x1 x3 the set r1 = {x3}; t2 = x2 ¬x3 mutually covers x3 = 1 and x3 = 0, so the gadget adds the term ¬x3, and symmetrically adds x3. Thus φ'' = x1 x2 ∨ x3 ∨ ¬x3, which is a tautology. Any singleton of tn, e.g. {x1}, is now an implicant of φ''. Hence Claim 2's 'if and only if' fails, and the reduction from Shortest-Implicant-Core to MSR returns 'yes' on an SIC 'no' instance. Since the MSR hardness results in Proposition 4.2(iii), Proposition 5.1(iii), and Proposition 5.2(iii) all use this reduction, those ΣP2 and para-ΣP2 classifications are unsupported. This is a correctness failure, not merely a missing reference.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational interpretability of ensemble classifiers through complexity theory. It analyzes five explanation queries (CSR, MCR, MSR, CC, and SHAP) over ensembles whose base models are decision trees, perceptrons/linear models, or ReLU networks, under majority and weighted voting, and in both classical and parameterized settings. The headline claims are that ensembles remain intractable even with constant-size base models; that the number of base models matters sharply, with fixed-k tree ensembles being XP/W-hierarchy tractable while constant-size linear-model ensembles are para-intractable; and that neural networks are closed under ensemble construction. The technical centerpiece is a claimed corrected proof that MSR on tree/linear ensembles is ΣP2-hard, together with several para-ΣP2 and para-#P classifications. Full proofs are relegated to the appendices.","tokens_in":60168,"tokens_out":10398,"duration_ms":132947,"significance":"If the results were correct, the paper would provide the first complete parameterized complexity map for these five explanation queries across three base-model families, with direct practical implications for random forests, XGBoost, and linear-model ensembles. The manuscript is commendably explicit about reductions and honestly identifies a technical gap in prior work on MSR hardness. However, the central MSR-hardness proof contains a false lemma, and the affected classifications are unsupported as written. The five-perceptron MSR reduction via generalized subset sum appears independent and may be salvageable, but the tree-ensemble and constant-size-base-model MSR results require either a new correct reduction or a weakening of the claims.","major_comments":[{"comment":"Claim 2 is false as stated. Take φ = (x1x3) ∨ (x2¬x3) ∨ (x1x2), with tn = x1x2 and all non-target terms of size 2. For t1 = x1x3 we have r1 = {x3}; the subset S = {t2} covers both assignments of x3 (x3 = 1 via t1 and x3 = 0 via t2), so the construction adds the term ¬x3. Symmetrically, for t2 = x2¬x3 the subset S = {t1} adds the term x3. Hence φ'' = x1x2 ∨ x3 ∨ ¬x3, which is a tautology. The singleton C = {x1} ⊆ tn is then an implicant of φ'', but C is not an implicant of φ because the assignment x1 = 1, x2 = 0, x3 = 0 falsifies φ. This directly contradicts the 'if and only if' in Claim 2, and the counterexample lies exactly in the constant-size term regime (d = 2), so the constant-DNF restriction does not repair the lemma.","section":"Appendix F, Claim 2 (Eq. (23))"},{"comment":"The ΣP2-hardness of MSR for DNF-representable ensembles rests on the false Claim 2. The concluding step of Appendix F asserts that an implicant C ⊆ tn of φ'' of size k exists iff a sufficient reason of size k exists for ⟨f, x⟩, and that assertion is precisely where the faulty elimination of non-tn variables is used. Consequently, Proposition 4.2(iii), the corresponding entries in Tables 1 and 2, and the MSR separations in Theorems 4.3 and 5.7 are unsupported as written. The paper must either supply a correct reduction from Shortest-Implicant-Core to MSR for these ensemble classes or explicitly weaken these claims.","section":"Appendix F, concluding reduction; Propositions 4.2(iii), 5.1(iii)"},{"comment":"The proof of Proposition 5.1 is incomplete: the text breaks off at 'For the CC query.' before giving the CC-hardness reduction, and the MSR paragraph cites Dick et al. (2009) without showing how a constant-term SIC instance is encoded into an ensemble of constant-size base models while preventing variables outside tn from appearing in sufficient reasons. Since the only mechanism offered for that prevention is the false Claim 2, Proposition 5.1(iii) is not established by the current text. In addition, Claim 1 (Shortest-Implicant-Core for constant-size DNF terms is ΣP2-hard) is only asserted to follow from Umans (2001); a precise derivation or a precise pointer is needed because the constant-size restriction is essential to the reduction.","section":"Appendix I (proof of Proposition 5.1)"}],"minor_comments":[{"comment":"The appendix references are inconsistent: the proof sketch for Proposition 5.1 says 'The proof appears in Appendix J', then a later sentence says 'The proof of Proposition 5.1 appears in Appendix I'. Please correct the cross-references.","section":"Section 5.1 and Appendix I/J"},{"comment":"The five-perceptron MSR proof contains variable slips and an unresolved placeholder: f5 is defined as the indicator of the input 1n, but later text says 'f3 is an indicator for the input 1n'; the construction of f5 is deferred with 'as demonstrated in (?)' and no reference or proof is supplied. These issues should be fixed so the reduction can be checked.","section":"Appendix J, Claim 10"},{"comment":"There are numerous typographical errors, e.g., 'paramaterized', 'hirerchy', 'seperattley', 'furmula', and 'tbe'. They do not affect the mathematics but should be cleaned up in revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The decisive issue is the false Claim 2 in Appendix F: the proposed repair of the known MSR-hardness gap is itself invalid, and the counterexample is in the intended constant-size regime. The five-perceptron reduction for linear-model ensembles appears to be independent and potentially correct, but the tree-ensemble and constant-size-base-model MSR classifications must be re-proven or withdrawn before the paper can be considered further. I would not recommend acceptance in the current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the most complete parameterized complexity map of ensemble explainability queries I know, and the tractability/intractability split between tree and linear ensembles is a genuinely useful organizing result. But one load-bearing lemma in Appendix F is false, so the headline SigmaP2-hardness for MSR over tree and linear ensembles is not supported as written.\n\nWhat is new and good: the paper extends Ordyniak et al.'s tree-ensemble results to linear models, weighted/soft voting, and CC/SHAP; the neural-network \"no gap\" result via closure under ensemble construction is clean; the para-#P and W-hierarchy results for k-tree ensembles give a tractability map that should survive independent of the MSR issue; and the pseudo-polynomial SHAP DP for perceptrons is real work. The authors also openly flag the earlier gap in Audemard et al. and Huang et al., which is the right instinct.\n\nThe soft spot is not a typo. In Appendix F, Claim 2 says any C subset of tn is an implicant of phi iff it is an implicant of the refined phi''. That is false. Take phi = (x1 and x3) or (x2 and not x3) or (x1 and x2), with tn = x1 and x2. For k=1 no singleton subset of tn is an implicant: fixing x1=1 fails on x2=0,x3=0; fixing x2=1 fails on x1=0,x3=1. The construction adds not x3 to cover the x3=0 case for t1, and x3 to cover the x3=1 case for t2. So phi'' = (x1 and x2) or x3 or not x3, a tautology, and {x1} becomes an implicant. The if-and-only-if collapses. This gadget is what carries Proposition 4.2(iii) and Proposition 5.1(iii); those MSR classifications need a different argument. Proposition 5.2(iii) uses the separate GSSP reduction and is not directly affected by this counterexample, but it has its own unresolved citation and f3/f5 slips, so it needs a careful pass too. Claim 1, the constant-DNF SIC hardness, is also not proved in the paper; it is asserted to follow from Umans, with a different reference (Dick et al.) appearing in Appendix I.\n\nThe paper deserves a serious referee, but the referee should treat the MSR rows of Tables 1 and 2 as unproven until Appendix F is repaired. If I were handling it, I would ask for a revision that either fixes the gadget or drops/re-scopes the affected claims.","headline":"A useful complexity map for ensemble interpretability, but the load-bearing MSR gadget in Appendix F is false, so the headline SigmaP2-hardness results need repair.","tokens_in":60695,"tokens_out":5926,"would_cite":false,"duration_ms":68441,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Ensemble interpretability is governed by the number and type of base models, not their size: fixed-count tree ensembles are explainable in polynomial time, while two linear models already make explanation queries intractable.","keywords":["ensemble interpretability","computational complexity","parameterized complexity","sufficient reason","contrastive explanation","Shapley values","decision tree ensembles","linear model ensembles"],"falsifier":"Examine the reducibility of Shortest-Implicant-Core with constant-size DNF terms: if that restricted problem is shown not to be $\\Sigma^P_2$-hard (for example, by a polynomial-time algorithm or by a reduction that only proves NP-hardness), then the paper's MSR classifications for ensembles of decision trees and linear models collapse.","tokens_in":59601,"feed_emoji":"🧩","tokens_out":8182,"duration_ms":91538,"temperature":0.7,"pith_summary":"The paper tries to establish that the folklore switch from “a single model is interpretable” to “an ensemble is a black box” has a precise complexity-theoretic signature. It claims that under standard assumptions ($\\mathrm{P} \\neq \\mathrm{NP}$ and $\\mathrm{FPT} \\neq W[1]$), the number of base models and their type matter more than their size: ensembles of even constant-size linear models, decision trees, or neural networks remain intractable to explain, while an ensemble of a fixed number of decision trees becomes polynomial-time explainable for four of the five queries studied. The paper additionally claims strict computational gaps: decision-tree ensembles are strictly more c-interpretable than linear-model ensembles for all five explanation forms, and ensembles of linear models are hard already at two members. If correct, this provides the first complete parameterized complexity map for these five explanation queries, and it gives practitioners a concrete architectural rule: fewer but deeper trees beat many shallow ones, whereas adding even a couple of linear models destroys tractable explainability.","feed_headline":"Two linear models already break ensemble explainability","feed_subtitle":"While small tree ensembles stay explainable in polynomial time, linear-model ensembles fail with just two members.","key_machinery":"The load-bearing construction is the reduction of Boolean formulas to ensembles whose base models are “poly-subset-constructable”: a family where, given any partial assignment $x_S$, one can build in polynomial time a base model that returns 1 exactly on inputs agreeing with $x_S$. The paper shows decision trees and perceptrons are such families, so every DNF becomes an equivalent majority-voting ensemble of $O(n)$ small base models, and this conversion preserves the difficulty of sufficient-reason, contrastive-reason, counting, and Shapley queries. The hardest MSR results reduce from Shortest-Implicant-Core (for general ensembles) and from a constrained Generalized Subset-Sum problem (for five perceptrons). FPT reductions to and from $k$-Clique and counting $k$-Clique carry the tree-ensemble tractability results, and the property “closed under ensemble construction” explains why neural networks show no complexity gap.","core_discovery":"The central discovery is that explainability of ensembles is not governed by base-model size but by base-model count and type. The paper proves that for ensembles of decision trees and of linear classifiers, checking a sufficient reason is $\\mathrm{coNP}$-complete, finding a minimum contrastive reason is $\\mathrm{NP}$-complete, finding a minimum sufficient reason is $\\Sigma^P_2$-complete, counting completions is $\\#\\mathrm{P}$-complete, and computing Shapley values is $\\#\\mathrm{P}$-hard, while the corresponding single-model queries are mostly polynomial-time. Parameterized by the largest base model, all five queries are para-$\\mathrm{coNP}$, para-$\\mathrm{NP}$, para-$\\Sigma^P_2$, or para-$\\#\\mathrm{P}$ complete or hard already at constant size. Parameterized by number of base models, the contrast is sharp: $k$-ensembles of linear models are para-$\\mathrm{coNP}$, para-$\\mathrm{NP}$, para-$\\Sigma^P_2$, or para-$\\#\\mathrm{P}$ complete or hard (CSR and MCR already for $k=2$, MSR for $k=5$), whereas $k$-ensembles of decision trees are $\\mathrm{co}W[1]$-complete, $W[1]$-hard, $\\#W[1]$-complete, or in XP/XNP, hence polynomial-time for fixed $k$. For neural networks the ensemble construction adds no complexity, because any ReLU network ensemble can be collapsed into a single network in polynomial time.","pith_inferences":["The same complexity map suggests that practical explanation tools for tree ensembles should fix the tree count and bound leaf counts, since the paper's FPT bounds grow as $O(m^k)$; this is an editorial extrapolation of its runtime statement.","Because the reductions use only majority and weighted voting, the para-hardness for two linear models likely transfers to stacking ensembles whose meta-learner can implement a threshold vote, a consequence the paper only notes in passing.","A testable extension is to parameterize by the total number of leaves or the ensemble's global size instead of per-tree leaf count; the paper's XP algorithms suggest those parameters may be smaller than $k$, but this is not established.","The query-dependent complexity gaps imply that “interpretable ensemble” should be qualified by explanation type: a model can be tractable for sufficient reasons yet intractable for Shapley values, so empirical benchmarks should report query-specific behavior."],"forward_implications":["For a fixed number of decision trees, CSR, MCR, CC, and SHAP become polynomial-time solvable; with constant leaf count per tree, they become fixed-parameter tractable even for arbitrarily large trees.","Any ensemble containing two linear models is already intractable to explain for all five query forms, so mixing a few linear models into a heterogeneous ensemble destroys tractable explainability.","Shrinking base models to constant size does not restore interpretability: all five queries remain intractable under maximal-base-model-size parameterization.","Neural-network ensembles gain no extra hardness from aggregation, because an ensemble of ReLU networks is reducible to a single ReLU network.","Tree ensembles are strictly more c-interpretable than linear-model ensembles with respect to CSR, MSR, MCR, CC, and SHAP."],"supporting_citations":[{"why":"Supplies the Shortest-Implicant-Core problem used as the reduction source for $\\Sigma^P_2$-hardness of MSR.","marker":"(Umans, 2001)"},{"why":"Extends Shortest-Implicant-Core hardness to DNFs with constant-size terms, which the paper's Claim 1 relies on.","marker":"(Dick et al., 2009)"},{"why":"Provides the $\\Sigma^P_2$-complete Generalized Subset-Sum problem from which the five-perceptron MSR hardness reduction starts.","marker":"(Schaefer & Umans, 2002)"},{"why":"Establishes W[1]-hardness and coW[1]-completeness results for tree-ensemble CSR and MCR that this paper extends to other queries.","marker":"(Ordyniak et al., 2024)"},{"why":"Defines computational interpretability and supplies baseline complexity results for single decision trees and perceptrons.","marker":"(Barceló et al., 2020)"},{"why":"Underlies the $\\#\\mathrm{P}$-hardness of DNF model counting used for the CC and SHAP query hardness.","marker":"(Valiant, 1979)"},{"why":"Connects Shapley-value computation to model counting, a link used to prove $\\#\\mathrm{P}$-hardness of SHAP.","marker":"(Arenas et al., 2023)"},{"why":"Gives the random-forest MSR reduction whose technical gap the paper identifies and repairs.","marker":"(Audemard et al., 2022b)"},{"why":"Shows that DNFs can be encoded as random forests, the construction generalized to poly-subset-constructable ensembles.","marker":"(Izza & Marques-Silva, 2021)"}],"fun_headline_variants":["Ensemble explainability: two linear models tip the complexity scale","Small tree ensembles stay explainable; two linear models don't","Ensemble interpretability: it's the count and type, not the size","Why two linear models are worse than many trees for explanations","Explainability threshold: k=2 linear models, but any tree count works"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The strongest new hardness results for Minimum Sufficient Reason rest on a lemma, imported from earlier work, that Shortest-Implicant-Core stays $\\Sigma^P_2$-hard even when DNF terms have constant size, plus a sketched refinement of the DNF; if either step fails, the MSR classifications weaken.","fun_headline_variants_meta":{"raw":{"variants":["Ensemble explainability: two linear models tip the complexity scale","Small tree ensembles stay explainable; two linear models don't","Ensemble interpretability: it's the count and type, not the size","Why two linear models are worse than many trees for explanations","Explainability threshold: k=2 linear models, but any tree count works"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000344,"raw_usage":{"total_tokens":1958,"prompt_tokens":1081,"completion_tokens":877,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":697,"completion_tokens_details":{"reasoning_tokens":786}},"tokens_in":697,"tokens_out":877,"duration_ms":9837,"temperature":1.0,"reasoning_tokens":786,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:18:20.594476+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Examine the reducibility of Shortest-Implicant-Core with constant-size DNF terms: if that restricted problem is shown not to be $\\Sigma^P_2$-hard (for example, by a polynomial-time algorithm or by a reduction that only proves NP-hardness), then the paper's MSR classifications for ensembles of decision trees and linear models collapse.","supporting_citations":[{"cited_title":"The Minimum Equivalent DNF Problem and Shortest Implicants","cited_arxiv_id":null,"evidence_quote":"Supplies the Shortest-Implicant-Core problem used as the reduction source for $\\Sigma^P_2$-hardness of MSR."},{"cited_title":"Improved Inapproximability Factors for Some p , 2009","cited_arxiv_id":null,"evidence_quote":"Extends Shortest-Implicant-Core hardness to DNFs with constant-size terms, which the paper's Claim 1 relies on."},{"cited_title":"and Umans, C","cited_arxiv_id":null,"evidence_quote":"Provides the $\\Sigma^P_2$-complete Generalized Subset-Sum problem from which the five-perceptron MSR hardness reduction starts."},{"cited_title":"Explaining Decisions in ML Models: A Parameterized Complexity Analysis","cited_arxiv_id":null,"evidence_quote":"Establishes W[1]-hardness and coW[1]-completeness results for tree-ensemble CSR and MCR that this paper extends to other queries."},{"cited_title":"The Complexity of Enumeration and Reliability Problems","cited_arxiv_id":null,"evidence_quote":"Underlies the $\\#\\mathrm{P}$-hardness of DNF model counting used for the CC and SHAP query hardness."}],"review_version":1}