Unifying Formal Explanations: A Complexity-Theoretic Perspective
Authors: Shahaf Bassan
Xuanxiang Huang
Guy Katz
Venue: ICLR 2026 Poster (2026)
Keywords: explainability
interpretability
combinatorial optimization
submodular optimization
sufficient reasons
abductive explanations
formal XAI
contrastive explanations
counterfactual explanations
semifactual explanations
algorithmic recourse
computational complexity
Primary area: interpretability and explainable AI

Abstract: Previous work has explored the computational complexity of deriving two fundamental types of explanations for ML model predictions: (1) *sufficient reasons*, which are subsets of input features that, when fixed, determine a prediction, and (2) *contrastive reasons*, which are subsets of input features that, when modified, alter a prediction. Prior studies have examined these explanations in different contexts, such as non-probabilistic versus probabilistic frameworks and local versus global settings. In this study, we introduce a unified framework for analyzing these explanations, demonstrating that they can all be characterized through the minimization of a unified probabilistic value function. We then prove that the complexity of these computations is influenced by three key properties of the value function: (1) *monotonicity*, (2) *submodularity*, and (3) *supermodularity* - which are three fundamental properties in *combinatorial optimization*. Our findings uncover some counterintuitive results regarding the nature of these properties within the explanation settings examined. For instance, although the *local* value functions do not exhibit monotonicity or submodularity/supermodularity whatsoever, we demonstrate that the *global* value functions do possess these properties. This distinction enables us to prove a series of novel polynomial-time results for computing various explanations with provable guarantees in the global explainability setting, across a range of ML models that span the interpretability spectrum, such as neural networks, decision trees, and tree ensembles. In contrast, we show that even highly simplified versions of these explanations become NP-hard to compute in the corresponding local explainability setting.

Published as a conference paper at ICLR 2026
UNIFYING FORMAL EXPLANATIONS: A COMPLEXITY-THEORETE PERSPECTIVE
Shahaf Bassan's Xuanxiang Huang Guy Katz' The Hebrew University of Jerusalem', Nanyang Technological University?
shahaf. bass aasssan@mail huji. ac ac.il, xuanxiang baanxiang.huanggntuus. edu sg,
g zat www.iuu........
ABSTRACT
Previous work has explored the computational complexity of deriving two fun- damental types of explanations for MI. model predictions: (i) sufficient reasons, which are subsets of input features that, when fixed, determine prediction, and (ii) contrastive reasons, which are subsets of input features that, when modified, alter prediction. Prior studies have examined these explanations in different texts, such as non-probabilistic versus probabilistic frameworks and local versus global settings. In this study, we introduce unified framework for analyzing these explanations, demonstrating that they can all be characterized through the minimization of unified probabilistic value function. We then prove that the complexity of these computations is influenced by three key properties of the value which are three fundamental properties in combinatorial optimization. Our findings un- cover some counterintuitive results regarding the nature of these properties within the explanation settings examined. For instance, although the local value functions do not exhibit monotonicity or aabbooduaartyysuuermotlarr demonstrate that the global value functions do possess these properties. This distinction enables us to prove a series of novel polynomial-tinn results for com- puting various explanations with provable guarantees in the global explainability setting, across a range of MI. models that span the interpretability spectrum, such neural networks, decision trees, and tree ensembles. In contrast, show that even highly simplified versions of these explanations become NP-hard to compute in the corresponding local explainability setting.
function: (i) monotonicity. (ii) submodularity, and (iii) supermodularity
whatsoever, we
INTRODUCTION
Despite substantial progress in methods for explaining ML model decisions, the literature has consistently unfortunately found that many desirable explanation types with different provable guarantees are computationally hard to obtain (Barceló et al. 2020 Van den Broeck et al. 2022), with difficulty typically worsening in complex or highly non-linear models (Barceló et al. 2020 Adolfi al.) 22255] 2024). As result, the computational complexity of obtaining explanations has become central theoretical focus, with many recent works aiming to chart which types of explanations can
be efficiently obtained for different kinds of models, and which remain out of reach (Barceló et al.
2020: Wäldchen et al. 2021 AArena et al.) 2022 2023 Marzouk & De La Higueral 2024 Ordyniak
al.
2023
Laber 2024 Bhattacharjee & Luxburg 2024 Blane et al. 2021 2022
From sufficient to contrastive reasons. Among studies on the computational complexity of generat-
ing explanations, fundamental types of explanations for MI models
extensively examined:
(i) sufficient reasons and (ii) contrastive reasons (Barceló et al. 2020 Arenas et al. [0022 Audemard
al. 2022al Arenas et al.) 202I; Barceló et al.) 2025 Marques- Silva & Ignatiev [2022] Ignatiey
et al. 2020b Darwiche & Hirth 2020). A sufficiett reason is subset of input features S such that
when these features are fixed to specific values, the model's prediction remains unchanged, regardless
of the values assigned to the complementary set S. A contrastive reason is subset of input features
such that modifying these features leads to a change the model's prediction.
" Eqqual contribution.

---

Published as a conference paper at ICLR 2026
Unlike additive attribution methods, which allocate importance scores across features but are often hard for humans to interpret (Kumar et al. all (020) or lack actionability (Bilodeau et al.) (024). sufficient and contrastive reasons provide discrete, condition-lik explanations that directly answer "what is enough to justify this prediction?" or "what must change to flip it?". Their intuitive nature has
given them central role in many classic XAI methods (Ribeiro et al., 2018 Carter et al. 2019
Ignatiev et al. 2019; Dhurandhar et al., (2018). shown greater effectiveness in improving human prediction over additive models (Ribeiro et al. 2018 Yin & Neubig [022] DDurrnnhar et al. 2018 and proved useful for downstream tasks such as bias detection (Balkir et 2022 Carter et al. 2021] La Malfa et 200T Muthukumar et al. 2018), model debugging (Jacovi et all.]2201) and anomaly detection (Davidson et al. 2025). A well-established principle further holds that smaller sufficient and contrastive explanations enhance interpretability, making minimality central guarantee of interest (Ribeiro et al.
2018
Lopardo et al. 2023] Carter et al. 2019 Barceló et al. 2020
Arenas
ctt al. 2022 Blanc et al.
2021 Wäldchen et al. (0221).
Barceló et al. (2020) conducted one of the earliest studies on the complexity of deriving sufficient and contrastive reasons. Their work established that finding the minimal-sized sufficient reason for a decision tree is NP-hard, with the complexity further increasing Σg -hard for neural networks. In the case of contrastive reasons, they demonstrated that computing the smallest possible explanation is solvable in polynomial time for decision trees but becomes NP-Hard for neural networks. Similar
hardness results were later shown to hold for tree ensembles as well (Izza & Marques-Silva 2021
Ordyniak al. 2024 Audemard et al., 2022b).
From non-probabilistic to probabilistic explanations. A common criticism of the classic definition of sufficient and contrastive reasons is their rigidity and lack of flexibility, as they hold in absolute sense over entire domains and can thus lead to excessively large or uninformative explanations (g
natiev et al., 2019 2020a] Arenas et al., [022 Wäldchen et al., 2021]. To address these limitations, the literature has shifted towards more general definition that incorporates a probabilistic perspective
on sufficient and contrastive reasons (Wäldchen et al. 2021; Arenas et al. 2022 Blanc et al., [002T]
Izza et al.) 2023 Xue et al. 2023). Under this framework, the goal is to identify subsets of input features that influence a prediction with a probability exceeding a given threshold 6.
Wäldchen et al. (2221) were the first to study the complexity of probabilistic sufficient reasons, showing that for CNF classifiers the problem is Np -hard. This hardness extends to tree ensembles
and neural networks (Barceló et al. 2020: Ordyniak et al.) (023)). ) A central theoretical insight in the
probabilistic setting is the lack of monotonicity in the probability function (Arenas et al. 2022 Izza
et ) which makes even subset minimal ex explanations computationally hard. Strikingly, (Arenas itt al. 2022) show that finding a subset minimal probabilistic sufficient reason is NP-hard even for decision trees- unlike in the non-probabilistic case, where such explanations are computable in polynomial time (Huang et al. 2021 Barceló et al. 2020).
From local to global explanations. In more recent study, Bassan et al. (2024) extend the complexity analysis from the local (non -ooo-obbbbbllitcc setting where explanations are tied to individual predictions- - to the glohal (non-prot noon-probabilistc) setting, which seeks sufficient or contrastive reasons over entire domains. However, as with other con-probabilistic methods (Ignatiev et al. 2019 Barceló ett al. 2020 Arenas et al. 2021 Darwiche & Hirth 2020)) the criteria are extremely strict arguably even more so in the global setting than in the local one. For instance, any feature excluded from a global sufficient reason is deemed strictly redundant (Bassan et al., 2024), often making the explanation span nearly all input features and thus less informative.
OUR CONTRIBUTIONS
1. We unify previous explanation computation problems including sufficient, contrastive, probabilistic, probaabbaiilistic, as well as local and global - into one framework, described as a minimization task over a unified value function. We then identify three fundamen- tal properties of the value function that significantly impact the complexity of this task: (a) monotonicity, (b) supermodularity. and (c) submodularity.
2. Interestingly, we show that these properties behave in strikingly different manners depending the structure of the value function. In particular, we demonstrate the surprising result that while the local value functions for both sufficient and contrastive reasons are non- non-monotonic, their global counterparts are monotonic non-decreasing. Moreover, we identify additional
2

---

Published as a conference paper at ICLR 2026
intriguing properties unique to the global setting: the global sufficient value function is supermodular, whereas the global contrastive value function is submodular in contrast to the local setting, where neither property holds.
3. We leverage these properties to derive new complexity results for explanation computation, revealing the intriguing finding that global explanations with guarantees can be computed efficiently, even though computing their local counterparts remains computationally hard. We demonstrate these findings across three widely used model types that span the inter- pretability spectrum: (i) neural networks, (ii) decision trees, and (iii) tree ensembles. First, we prove that while computing a subset-minimal local sufficient/contrastiin explanation is NP-hard even for decision trees (Arenas et al.] (022). its global counter- part can be computed in polynomial time. We further extend this result to any black-box model (including complex models such neural networks and tree ensembles) when using empirical distributions. Specifically, we show that obtaining a monsett global suffi- cient/contrastive explanation is achievable in polynomial time, whereas the local version remains NP-hard for these models.
probabilistic
4. Finally, we present an even stronger complexity result by exploiting the submodular and supermodular properties of the value functions in the global setting properties that do not hold in the local case. Specifically, we show that it is possible to achieve provable constant- factor approximation guarantees for computing cardinally minimal global explanations even for complex models like neural networks or tree ensembles when the empirical distribution is fixed. In sharp contrast, we establish strong inapproximability results for the local setting, demonstrating that no bounded approximation is possible, even under very simple assumptions.
Owing to space constraints, we provide an overview of our main theorems and corollaries in the main text, with full proofs deferred to the appendix.
2 PRELIMINARIES
Setting. We consider input space of dimension N. with input vectors := (X1, X2.... Xx)) Each coordinate x, may take values from its corresponding domain X, which can be either discrete continuous. The full input feature space is therefore F == X2 x X2 x ... x Xn We consider classification models f F + [c] where c E N is the number of classes. Moreover, we consider generic distribution D F - [0, over the input space. In many settings, however, accurately approximating D is computationally infeasible. A natural alternative is to instead work with a fixed empirical dataset D := {z], 22...... DDI), which serves as a practical proxy for the "true" distribution, for instance, by taking D sampled subset from the available training data.
The explanations that we study are either local or global. In the local case, the explanations target a specific prediction E F, providing form of reasoning for why the model predicted f(x) for that instance. In the global case, explanations aim to reflect the general reasoning behind the behavior of f across wider region of the input space, independent of any specific x, and characterize its overall decision mrakiign-making logic.
Models. While many results presented in this work are general (e.g., inherent properties of value functions), we also provide some model-specific complexity results for widely-used ML models. To broadly address the interpretability spectrum, we chose to analyze models ranging from those typically considered "black-box to those commonly regarded as "interpretable". Specifically, we focus on: (i) decision trees, (ii) neural networks (all urchitectures at least as expressive as feed- -orwardd ReI.U networks), and (iii) tree ensembles, including majority-voting ensembles (e.g., random forests) and weighted-voting ensembles (e.g., XGBoost). Formal definitions are provided in the Appendix.
Distributions. We emphasize that in probabilistic explanation settings, the complexity can vary sig- nificantly with the input distribution D. Particularly, we focus on three distribution types: (i) general distributions, which make specific assumptions over D and thus encompass all possible distribu- tions. We use these distributions mainly in proofs of properties that hold universally; (ii) empirical distributions, which include all distributions derived from the finite dataset D approach com- monly employed in XAI (Lundberg & Lee| [017] Van den Broeck et al., 2022); and (iii) independent distributions, which assume that features in DD are mutually independent another widely adopted
3

---

Published as a conference paper at ICLR 2026
assumption in XAI literature (Arenas al. 2022 2023
Lundberg & Lee 2017 Ribeiro et al. 2018)
We note that empirical distributions do not necessarlly imply feature independence: rather, they can represent complex dependencies extracted from finite datasets (Van den Broeck et al., 2022)) The complete formal definitions of these distributions are provided in the Appendix.
3 FORMS OF REASONS
In this section, we introduce the explanation types studied in this work, starting with the strict con-pobbabilistic definitions of (local/global) sufficient and contrastive reasons, and then extending their more flexible and generalizable probabilistic counterparts.
3.1 Non-Probabilistic SUFFICIENT AND CONTRASTIVE REASONS
Sufficient reasons, In the context of feature selection, users often select the top k features that contribute to model's decision. We examine the well-established sufficiency criterion for this selection, which aligns with commonly used explainability methods (Ribeiro et al. 2018 Carter et al. 2019 Ignatiev al. 2019 Dasgupta et al. 2022). This feature selection can be carried out either locally - focusing on a single prediction
or globally across the entire input domain. Following standard conventions, we define a local sufficient reason as a subset of features such that when the features in S are fixed to their corresponding values in the model's prediction remains (x) regardless of the values assigned to the remaining features S. Formally, is local sufficient reason for (J. iff the following condition holds:
C {1.....
Vz E F, f(xs:2s) f()).
Here, (Xs; (g) denotes a vector where features in S take their values from x, and those in S from Local sufficient reasons are closely related to semi-factual explanations (Kenny & Keane [021]] Alfano et al. 2025). which search for alternative inputs z' that keep the prediction unchanged (i.c.,
[ = ((x) while being as "close" as possible the original point. When we instantiate z' as (xs;75) and measure proximity via Hamming distance, the two notions coincide.
global sufficient reason (Bassan et al. 2024) is a subset of input features S [I.....m] that serves local sufficient reason for every possible input E FF:
V f(xs: = f(x).
(2)
Contrastive reasons. Another prevalent approach to providing explanations is by pinpointing subsets of input features that modify a prediction (Dhurandhar et al. [2088) Mothilal et al., 2020 Guidotti 2024). This type explanation aims to determine the minimal changes necessary to alter a prediction. Formally, subset S S (1....,m) is defined as local contrastive reason concerning (f, x) iff:
3E E F, f(zs:xs) + fxx).
(3)
Contrastive reasons are also closely connected counterfactual explanations (Guidotti 2024
Mothilal et al. 2020), which seek nearby assignment x' for which the prediction flips, i.e., f(x)= f(x). When the distance metric is taken to the Hamming weight, the two notions coincide.
Similarly to sufficient reasons, one can determine subset of input features that, when altered, changes the prediction for all inputs within the domain of interest. This form of explanation is also closely connected to approaches for identifying bias (Arenas et al.) [021] Bassan et al. [0224] Darwiche & Hirth 2020), as well as group counterfactual explanation methods that search for counterfactuals over multiple data instances (Carrizosa et al. 2024 Warren et al. 2024). Formally, we define a subset as global contrastive reason with respect to iff:
Vx E F,
EERR,
f(zs:x)) # f(x).
4

---

Published as a conference paper at ICLR 2026
3.2 Probabilistic SUFFICIENT AND CONTRASTIVE REASONS
As discussed in the introduction, non-probabilistic sufficient and contrastive reasons are often criticized for imposing significantly overly strict conditions, motivating a shift probabilistic definitions (Arenas et al. [022 Ribeiro et al. 2018:) Izza et al. 2023] Wäldchen et al. [021] [Bonnia
& Koriche, |023] Subercaseaux al. [025] Wang et al. 2022a a Blanc et al. (2021), which generalize
these requirements by demanding that the guarantees hold with probability at least å E [0, 1]. The
special case recovers the original propaabbaiilistic definitions.
Probabilistic sufficient reasons. We define S S (1..... n as local 8-sufficient reason with respect to (f.x) if, when the features in S are fixed to their corresponding values in and the remaining features are sampled from a distribution D, the classification remains unchanged with probability least In other words:
PRaDD (f(z)= fxx ny =x) (5)26 8.
(5)
where Σş denotes that the features in S of vector are fixed to their corresponding values in We adopt the standard notion of global explanations - by averaging over all inputs the global domain and define a subset S S {1..... n global 5 ö-sufficient reason with respect to (f) if, when taking the expectation of the local sufficiency probability over samples drawn from the distribution D, the expectation remains with value at least ò. In other words:
EXWD Przz = f(x) 2s = xs)]
(6)
Probabilistic contrastive reasons. Similar to the non-probabilistic case, define local 8- contrastive reason as subset of input features that changes prediction with some probability. Here, unlike sufficient reasons, we set the features of the complementary set S to their respective values in and when allowing the features in S to vary, we require the prediction to differ from the original prediction f (x) with probability exceeding 8. Formally:
PRaDD (f(2) f(x) Z3 xg)
For the global setting, we define subset S to be global ô-contrastive reason, analogous to global sufficient reasons, by computing the expectation over all local contrastive reasons sampled from the distribution D, and requiring that this expected value exceeds ò:
E Pr.- (f(z) # f(x) zg xx)] 1120
(8)
FORMS OF MINIMALITY
As discussed the introduction, across all the explanation forms discussed so far whether sufficient or contrastive, local or global common assumption in the literature is that explanations of smaller size are more meaningful, thereby making their minimality a particularly important provable guarantee. In this study, we explore two central notions of minimality across all our explanation types:
Definition 1. Assuming a subset S S (1,...n) is an explanation, then:
1. S is pardinally-minine explanation (Barceló et al. 2020 Bassan et al. 2024) iff S has the smallest explanation cardinality |S] (i.e., there is explanation S such that S < SS)).
2. S C (1....,n))
n) is subset-minimal explanation (Arenas et al. iff S is an explanation, and any S' C S is not an explanation.
2022 Ignatiev al. 2019)
We note that cardinal- minnmality is strictly stronger than subset-mining minimmllti: every cardinally minimal S is subset-minimal, but not vice versa (see Appendix B.3 for an example). We use the terms subset and cardinally minimal, rather than local and global minima, to avoid confusion with local vs. global explanations (input- domain-level reasoning). Both notions apply all explanation forms analyze. For instance, a cardinally minimal local probabilistic sufficient reason is the one with the smallest (S), while subset-minimal one is any S where no proper subset S' C S also qualifies.
5

---

Published as a conference paper at ICLR 2026
5 A UNIFIED COMBINATORIAL OPTIMIZATION TASK
Interestingly, all previously discussed computational problems - local or global, sufficient or contrastive, probabilistic not can be cast finding minimal-size subset S such that v(S) 2 6, where in non-probabilistic settings we set := 1. We now introduce notation for the value functions: let " denote the local sufficiency probability from equation i.e., it. = f(z) xs zs), and define the global variant Uuuft (equation 6 Similarly, let u/co and voea denote the local and global contrastive probabilities (equations 7 and [3] respectively). Using this notation, we now formally define the unified task of finding cardinally minimal 5-local/global sufficien/ccontrastive reason:
Cardinally Minimal 6-Explanation:
Input: Model f. distribution D. (possibly. an input x), general value function v 2" + [0, (defined using f. D, and possibly x), and some E [0. 1]. Output: A subset S S [n] such that v(S) 2 5 and [S] is minimal.
Similarly, for the relaxed condition where the goal is to obtain subset-minimal rather than cardinally-minimal local or global sufficient/contrastive reason, we define the following relaxed optimization objective:
Subset Minimal t-Explanation:
Input: Model f. distribution D. (possibly, input x), general value function 2" [0, 1] (defined using f. D, and possibly x), and some E [0, 1]. Output: A subset C [n] such that v(S) 2 5 and for any 5' S it holds that e(S') < 6.
Properties of that affect the complexity. We now outline several key properties of the value function, which we later show play crucial role in determining the complexity of generating explanations. The first property is non-decreasing monotonicity, which ensures that the marginal contribution vSS U {f]) v(5) is consistently non-negative. Formally:
Definition We say that a value function v maintains non-decreasing monotonicity if for any S S (1, .L, n and any E n1} it holds that: U U
2 v(S).
The other key properties of supermodularity and submodularity pertain to the behavior of the marginal contribution v0S u (i}) - uSS). Specifically, in the supermodular case, this contribution forms monotone non-decreasing function. In contrast, under the dual definition of the submodular case, the marginal contribution vSS U {i}) v(S) is monotone non-increasing function. Formally:
Definition 3. Let there be some value function v, some S S {1, ........,))
, n., and & S'. Then:
1. v maintains supermodularity iff it holds that: vSS (1)) - v(S) S (S (1)) - v(S").
2. v maintains submodularity iff it holds that: vSSu (1)) - v(S) 2 o(' U (1)) x(S)).
UNRAVELING NEW PROPERTIES OF THE GLOBAL VALUE FUNCTIONS
Prior work shows that in the local setting non-probabilistic explanations, subset-minimal sufficient or contrastive reasons can be computed thanks to monotonicity, which holds only in the restricted case 8 1. This assumption, however, is highly limiting and lacks practical flexibility. While one might hope generalize to probabilistic guarantees for arbitrary ò, prior results demonstrate that monotonicity breaks down in this setting, rendering the computation of explanations computationally
harder (Arenas et al. 2022 Kozachinskiy 2023
1zza et al. 2023 Subercaseaux et al. 2025 17a
et al. 2024b).
At the even more extreme case of the global and non-probabilistic setting, Bassan et al. (2024) demon- strated the stringent uniqueness property - i.e., there exactly one subset-minimal explanation. However, requiring 8 = 1 makes this setting highly restrictive, especially in the global case, where the explanation conditions must hold for all inputs. In fact, Bassan et al. (0024) proves that this unique minimal subset is equivalent to the subset of all features that are not strictly redundant (which may, in practice, all of them). We prove that in the general global probabilistic setting for any this uniqueness property actually does not hold, and the number of subsets even be exponential.

---

Published as a conference paper at ICLR 2026
Proposition 1. While the ponoroobaii case (Ó 1) admits unique subset-minimal global sufficient reason (Bassan et al. (024), in the general probabilistic setting (for arbitrary 6). there exist functions f that have O -
subset-minimal global sufficient reasons.
Vn
Interestingly, although the uniqueness property fails to hold in the general case for arbitrary 5 (and is restricted to the special case of ò 1), we show that the crucial monotonicity property holds for the global value function across all values of ò. This applies to both the sufficient (taa)) and contrastive (veon) value functions. This finding is surprising it stands in sharp contrast to the local setting, where the corresponding value functions (u and v(nn) do not satisfy this property:
Proposition 2. While the local probabilistic setting (for any 5) lacks monotonicity - iee, the value functions y'mm and "'ug are non-monoen non-monotonic (Arenas et al. 2022 Izza et al. 2023 Subercaseaux et al. 2025: Izza et al. 2024b) in the global probabilistic setting (also for any d), both value functions
con and by are monotonic non- non-decreasing.
Beyond the surprising insight that monotonicity holds for the global value functions but fails to hold in the local one we identify additional structural properties unique to the global setting, including submodularity or supermodularity. In particular, we show that under the common assumption of feature independence, the global sufficient value function e exhibits supermodularity. In contrast, its local counterpart vf fails to exhibit this property even under the much more restrictive assumption of a uniform (and hence independent) input distribution. Specifically:
Proposition 3. While the local probabilistic sufficient setting (for any 8) lacks supermodularity even when D is uniform, i.e., the value function V'uf is not supermodular in the global probabilistic setting (also for any 8), when 'D exhibits feature independence, the vulue function vaug is supermodular.
Interestingly, for the second family of explanation settings specifically, that of obtaining global probabilistic contrastive reason - we show that the corresponding value function is not supermodular, but rather submodular. This result is particularly surprising when contrasted with the local setting, where the value function is neither submodular nor supermodular.
Proposition 4. While the local probabilistic contrastive setting (for any 5) lacks submodularity even when D is uniform, i..., the value function of is not submodular - in the global probubilistic setting (also for any 8), when D exhibits feature independence, the value function vg is submodular.
7
COMPUTATIONAL COMPLEXITY RESULTS
7.1 SUBSET MINIMAL EXPLANATIONS
In this section, examine the complexity of obtaining subset minimal explanations (local/global, sufficient/contrastivve) across the different model types analyzed. The key property at play here is the monotonicity of the value function. The previous section established that monotonicity holds for both global value functions, v.gm and vaur but does not hold for the local value functions, v and u This distinction is crucial in showing that a greedy algorithm converges to a subset minimal explanation in the global setting but fails the local setting. As a result, we will showcase the surprising finding that computing various local computing subset-minimal global explanation forms tractable (polynomial-tee solvable). We will begin by introducing the following generalized greedy algorithm:
explanation forms is hard, whereas
Algorithm 1 Subset Minimal Explanation Search
Input Value function v, and some 5 [0, 1]
1: S + [1....,n.} n
2: while minies e(S \ {i)) > 8 do
3: f- arggaxxss u(S {i})
4: S S
5: end while
6: return
D a (subset minimal?) 8-explanation
Algorithm| aaims to obtain a mubbet-minimal 6-explanation. We begin the algorithm with the subset S initialized as the entire input space (1....,n). Iteratively, we check whether the minimal value that
7

---

Published as a conference paper at ICLR 2026
v(S) \. {i}) can attain exceeds 5. In each iteration, we remove a feature j from S that minimizes the decrease in the value function, selecting the feature j that maximizes v(S \ {i}). Once this iterative process concludes, we return S.
The key determinant of whether Algorithm yiceds a subset-miningt minimal explanation is the monotonicity property of the value function v. The algorithm concludes with phase in which removing any individual feature from S results in v(5 \ {i)) being smaller than 6. However, monotonicity ensures that this holds for any v(S \ S"), providing a significantly stronger guarantee. Given the monotonicity property of the value functions established in the previous sections, we derive the following proposition:
Proposition 5. Computing Algorithm 7 with the local value functions V'm and ving does not always converge to a subset minimal 6-sufficien//comuussiee reason. However, computing with the global value functions t.oo or "mug necessarity produces subset minimal suufficeen/cconrrsstiv reasons.
Building on this result, we proceed to establish new complexity findings for deriving various forms of subset-minimal explanations within our framework, considering the different analyzed model types.
Decision trees. We hegin by examining a highly simplified and ostensibly "interpretable" scenario.
Specifically, we assume that the model is a decision tree and that the distribution D is independent. Within this simplified setting, we demonstrate strict separation: [Arenas et al. (022)) established the surprising intractability result that, unless PTIME-NP, no polynomial-tine for computing a mubset-miningg local d-sufficient reason for decision trees under independent distributions (even under the uniform distribution). In contrast, we demonstrate the unexpected result that this exact problem can be solved efficiently in the global setting, meaning that subset-minimal global 8-sufficient reason for decision trees can indeed be computed in polynomial time. Formally:
algorithm exists
Theorem 1. If f is decision tree and the probability term vnng can be computed in polynomial time given the distribution DD (which holds for independent distributions, among others). then obtaining a subset-minimal global S-sufficient reason can be obtained in polynomial time. However, unless PTIME=NP, no polynomial -imemial-time algorithm exists for computing a local 8-sufficient reason for decision trees even under independent distributions.
Extension to other tractable models. We additionally note that a similar tractability guarantee for computing global explanations also holds for orthogonal DNF's (Crama & Hammer 2011), which briefly recall are Disjunctive Normal Form formulas whose terms are pairwise mutually exclusive. Establishing the result for this class useful because orthogonal DNFs generalize decision trees while preserving their clean structural properties, allowing our guarantees to extend beyond tree-structured models. For completeness, we provide the full argument in Appendix
Neural networks, tree ensembles, and other complex models. We now extend our previous results to more complex models beyond decision trees. Specifically, we will demonstrate that when the distribution 2 is derived from empirical distributions, and under the fundamental assumption that the model f allows polynomial-
inference, it follows that computing subset-minimal global 5-sufficient and contrastive reason can be done in polynomial time.
Proposition 6. For any model f. and empirical distribution D D computing a subset-mininal global 8-sufficient or 8-contrastive reason for f can be done in polynomial time.
This strong complexity outcome, which holds for any model under an empirical data distribution assumption, allows us to further differentiate the complexity of local and global explanation settings. Specifically, for certain complex models, computing subset-minimal local explanations remains intractable even when restricted to empirical distributions. We establish this fact for both neural networks and tree ensembles, leading to the following theorem strict complexity separation:
Theorem 2. Assuming f is a neural network or a tree ensemble, and D is an empirical distribution there exist polynomial -ime algorithms for obtaining subset minimal global 6- 6-sufficient and con- trastive reasons. However, unless PTIME-NP, there is no polynomial time algorithm for computing subset minimal local 5-sufficien reason or a subset minimal local 5-contrastive reason.
7.2 APPROXIMATE CARDINALLY MINIMAL EXPLANATIONS
In this subsection, we shift our focus from subset-minimal sufficient/contrastivee reasons to the even more challenging task of finding cardinally minimal E-sufficient/coonrastive reason. We
8

---

Published as a conference paper at ICLR 2026
will demonstrate that in the global setting, the interplay between supermodilaity/summddlarr and monotonicity of the value function enables us to establish novel provable approximations for will show that computing these explanations in the local setting remains intractable. This result further strengthens the surprising distinction between the tractability of computing global explanations versus local ones.
computing explanations. In contrast,
unified greedy approximation algorithm. When working with a non-decreasing monotonic submodular function, the problem of identifying a cardinally minimal explanation closely aligns with the submodular set cover problem (Wolsey] 1982). In contrast, employing a supermodular function leads to a non-sunnmen submodular variation of this problem (Shi et al.) 2021). These problems have garnered significant interest due to their strong approximation guarantees (Wolsey) 1982, Iyer & Bilmes] 2013) Chen Crawford 2023). In the context of submodular set cover optimization, standard approach involves using classic greedy algorithm, which we will first outline (Algorithm 2). This algorithm serves as the foundation for approximating a cardinally minimal sufficient or contrastive d-reason, and we will later examine its specific guarantees in both cases.
Algorithm 2 Cardinally Minimal Explanation Approximation Search
Input Value function v, and some 8 [0, 1]
1: S 5 0
2: while maxtes v(S U (i)) < 8 do
3: j - argmaxxes uSS USSUPI (i))
4: S S
5: end while
6: return S
D |8| a (provable approximation?) of cardinally minimal 8-explanation
Algorithm closely resembles Algorithm | but works bottom-up rather than top-down. starts with an empty subset and incrementally adds features, each time selecting the one that minimizes the increase in v(5 U i), stopping when adding any feature would push the value over 8.
Cardinally minimal contrastive reasons. We begin with global contrastive reasons, where mono- tonicity and submodularity hold, reducing the task the classic submodular ser cover problem and allowing us to apply Wolsey (1982)'s 's classic guarantee via Algorithm 2 For integer-valued objec-
tives, the algorithm achieves a Harmonicc-asse factor, and more generally an O In e(ln)
minselal u(()
approximation. Under an empirical distribution D with fixed sample size, this becomes constant approximation, only logarithmic in the sample size, yielding a substantially strong guarantee. By contrast, the local setting even for single sample point - no bounded approximation exists. marking a sharp gap between global and local cases.
Theorem 3. Given neural network or tree ensemble J and an empirical distribution 'D over a fixed datasel D, Algorithm yields constant O (In mincefe) Poon ((13)) -approximation, bounded by OIn( for computing a global cardinally minimal 8-contrastive reason for assuming feature independence. In contrast, unless PTIME=NP, no bounded approximation exists for computing
e (In))
local cardinally minimal d-contrastive reason for any xf,x), even when [ 1.
We also provide matching lower bound for the bound in Theorem 3 in the specific of an empirical distribution without any independence assumption (see Appendix M.
Cardinally minimal sufficient reasons. Unlike the submodular set cover problem linked cardi- nally minimal global contrastive reasons and admitting strong approximations - the supermodular variant, tied to global sufficient reasons, is harder approximate. Still, it offers guarantees when the function has bounded curvature (Shi et al. 2021). The total curvature of function v 2" + IR
is defined as k = min:e(m)
"[[n] [[n])=m([ ())
Shi et al. (2021), we show Leveraging results Shi
=(0)-((0)
that Algorithm achieves an 1-
+ In
v((n))
-aprrxxmmation
[minse e(s)
Notably, under fixed empirical distribution, the approximation becomes constant. While contrastive reasons admit a tighter O[I((D)) bound, sufficient reasons incur an extra T- factor - yet still yield a constant-facte approximation. In sharp contrast, the local variant remains inapproximable, lacking any bounded approximation when |D|

---

Published as a conference paper at ICLR 2026
Theorem 4. Given neural network or tree ensemble f and an empirical distribution 'D over fixed dataset D, Algorithm 2 yields constant O (1-kkr + In minnggi)) & (ggtt )) approximation for computing global cardinally minimal d-sufficient reason for f. assuming feature independence. In contrast, unless PTIME-NP, there is bounded approximation for computing a local cardinally minimal ò-sufficient reason for any xx),, even when [D]
(1n))
Overall, these findings strengthen Subsection 7.1 which showed the tractability of computing subset- minimal global explanations in stark contrast to local ones. Here, we further show that approximating cardinally minimal global explanations is tractable, unlike their inapproximable local counterparts.
LIMITATIONS AND FUTURE WORK
While many of our most important findings - particularyy those concerning fundamental properties of value functions - hold generally, we also instantiate them to yield concrete complexity results for specific model classes (c.g.. neural networks). distributional assumptions (c.g., empirical distribu- tions), and explanation definitions within framework. Naturally, other potential settings remain open for analysis. Nonetheless, we believe our findings offer compelling insights into foundational aspects of explanations, along with new tractability and intractability results, which together lay strong foundation for investigating a broader range of explainability scenarios in future work.
More specifically, study brings forward several important open theoretical questions:
1. Firstly, would be interesting to investigate whether some of the tractable complexity results we obtained for global explainability can be tightened for simpler model classes, such as decision trees, linear models, or other models with inherently tractable structure. Although local explanations for such models are often intractable compute (Arenas et al., [022] SSueeraaseaxx et al. (2025). the global explanation forms we study in this work exhibit strong structural properties, enabling significantly improved complexity guarantees that may be tightened even further. Furthermore, tightening the approximation guarantees when working with empirical distributions represents a key open direction.
2. Secondly, when exact computation of expectations is infcasible, is natural to ask whether alternative techniques such as Fully Polynomial Randomized Approximation Schemes (FPRAS) for model classes like DNF formulas (Meel et al., 2019) (and thus for tree ensembles), Monte parlo-based approximations as the ones used in (Subercaseaux et al., 2025) can be employed to approximate these expectations. A key open challenge is determining how maintain minimality guarantees under approximation error, and what tolerance levels still allow the guarantees to hold.
3. Finally, we believe that studying alternative notions of feature importance - e.g., other loss measures such as KI. divergence (Conmy et al. (023) - may reveal similar patterns of monotonicity, submodularity, supermodularity when transitioning from local to global explanations. Such properties could enable efficient feature selection under these alternative metrics well.
CONCLUSION
We present a unified framework for evaluating diverse explanations and reveal a stark contrast between local and global sufficient and contrastive reasons. Notably. while the local explanation variants lack any structural form common in combinatorial optimization such as monotonicity, submodularity, or supermodularity, we prove that their global counterparts exhibit precisely these crucial properties: (i) monotonicity, (ii) submodularity in the case of contrastive reasons, and (iii) supermodularity for sufficient reasons. These proofs form the basis for proving a series surprising complexity results, showing that global explanations with provable guarantees can be computed efficiently, even for complex model classes such as neural networks. In sharp contrast, we prove that computing the corresponding local explanations remains NP- even in highly simplified scenarios. Altogether, our results uncover foundational properties explanations and chart both tractable and intractable frontiers, opening new avenues for future research.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was partially funded by the European Union (ERC, VeriDeL, 101112713). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This research was additionally supported by a grant from the Israeli Science Foundation (grant number 558/24).
REFERENCES
Federico Adolfi, Martina G Vilas, and Todd Wareham. ConplexityTheeoreicc Limits on the Promises of Artificial Neural Network Reverse-Enginecring. In Proc. 46th Annual Meeting of the Cognitive Science Society (CogSci), 2024.
Federico Adolfi, Martina Vilas, and Todd Wareham. The Computational Complexity of Circuit Discovery for Inner Interpretability. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
Gianvincenzo Alfano, Sergio Greco, Domenico Mandaglio, Francesco Parisi, Reza Shahbazian, and Irina Trubitsyna. Even-If Explanations: Formal Foundations, Priorities and Complexity. In Proc. 39th AAAI Conf. on Artificial Intelligence, pp. 15347-15355, 2025.
Ibrahim M Almanjahie, Zouaoui Chikr Elmezouar, Ali Laksaci, and Mustapha Rachdi. KNN Local Linear Estimation the Conditional Cumulative Distribution Function: Dependent Functional Data Case. Comples Rendus. Muthématique, (56((0):0036-1)))
2018.
David Alvarez Melis and Tommi Jaakkola. Towards Robust Interpretability with Self- Seff-Explaining Neural Networks. In Proc. 32nd Conf. on Neural Information Processing Systems (NeurIPS), 2018.
Leila Amgoud and Martin Cooper. Axiomatic Foundations of Counterfactual Explanations. 2026. Technical Report, htttps://arxiv. http://xww....aaa////2//222222
Guy Amir, Shahaf Bassan, and Guy Katz. Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation. In Proc. 27th European Conf. on Artifical Intelligence (ECAI), 2024.
Alaa Anani, Tobias Lorenz, Mario Fritz, and Bernt Schiele. Pixel-level Certified Explanations via Randomized Smoothing. In Proc. 42nd Int, Conf. on Machine Learning (ICML), 2025.
Marcelo Arenas, D. Baez, P. Barceló, J. Pérez, and B. Subercaseaux. Foundations of Symbolic Languages for Model Interpretability. In Proc. 34th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 11690-11701, 2021.
Marcelo Arenas, P. Barceló, M. Romero, and B. Subercaseaux. On Computing Probabilistic Explana- tions for Decision Trees. In Proc. 35th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 28695-28707, 2022.
Marcelo Arenas, Pablo Barceló, Leopoldo Bertossi, and Mikaël Monet. On the Complexity of SHAP- Score-Based Explanations: Tractability via Knowledge Compilation and Non Approxximmaiby Results. Journal of Machine Learning Research (JMLR), 24(63); 2023.
Gilles Audemard, S. Bellart, L. Bounia. F. Koriche, J. Lagniez, and P. Marquis. On the Computa- tional Intelligibility of Boolean Classifiers. In Proc. 18th Int. Conf. Principles of Knowledge Representation and Reasoning (KR), pp. 74-86, 2021.
Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis. On Preferred Abductive Explanations for Decision Trees and Random Forests. In Proc. 3 Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 643-650, 2022a.
Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Mean-Marie Lagniez, and Pierre Marquis. Trading Complexity for Sparsity in Random Forest Explanations. In Proc. 36th AAA! Conf. on Artificial Intelligence, number 5, pp. 5461-5469, 2022b.
11

---

Published as a conference paper at ICLR 2026
Gilles Audemard, Jean-Marie Lagniez, Pierre Marquis, and Nicolas Szezepanski. Computing Abductive Explanations for Boosted Trees. In Proc. 26th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 4699-4711, 2023.
Steve Azzolin, Sagar Malhorta, Andrea Passerini, and Stefano Teso. Beyond Topological Self- Explainable GNNs: A Formal Explainability Perspective. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
Esma Balkir, Isar Nejadgholi, Kathleen C Fraser, and Svetlana Kiritchenko. Necessity and Sufficiency for Explaining Text Classifiers: A Case Study in Hate Speech Detection. In Proc. Conf. of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), pp. 2672-200220 2626, 2022.
Pablo Barceló, M. Monet, J. Pérez, and B. Subercaseaux. Model Interpretability through the Lens of Computational Complexity. In Proc. 33rd Int. Conf. on Advances Neural Information Processing Systems (NeurIPS), pp. 15487-15498, 2020.
Pablo Barceló, Alexander Kozachinskiy, Miguel Romero, Bernardo Subsercascaux, and José Verschae. Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. In Proc. 3rd ACM on Management of Data, pp. 1-26, 2025.
Shahaf Bassan and G. Katz. Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks. In Proc. 29th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 187-207, 2023.
Shahaf Bassan, Guy Amir, Davide Corsi, Idan Refaeli, and Guy Katz. Formally Explaining Neural Networks Within Reactive Systems. In Proc. 23rd Ini. Conf. on Formal Methods in Computer-Aided Design (FMCAD). pp. 1-13, 2023.
Shahaf Bassan, Guy Amir, and Guy Katz. Local vs. Global Interpretability: A Computational Complexity Perspective. In Proc. 41st Int. Conf. on Machine Learning (ICML), 2024.
Shahaf Bassan, Guy Amir, Meirav Zehavi, and Guy Katz. What makes an Ensemble (Un) Inter- pretable? In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025a.
Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Matthias Althoff, and Guy Katz. Explaining. Fast and Slow: Abstraction and Refinement of Provable Explanations. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025b.
Shahaf Bassan, Ron Eliav, and Shlomit Gur. Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025c.
Shahaf Bassan, Shlomit Gur, Sergey Zeltyn, Konstantinos Mavrogiorgos, Ron Eliav, and Dimosthenis Kyriazis. Self-nxpla Neural Networks for Business Process Monitoring. 2025d. Technical /tttpss//arrtiv.orr//bb/////////
18067
Shahaf Bassan, Michal Moshkovitz, and Guy Katz. Additive Models Explained: A Computational Complexity Approach. In Proc. 39th Conf. on Neural Information Processing Systems (NeurIPS), 2025e.
Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Volkan Sahin, Jan Kretinsky, Matthias Althoff, and Guy Katz. Provably Explaining Neural Additive Models. In Proc. 14th Int. Conf. on Learning Representutions (ICLR), 2026.
Robi Bhattacharjec and Ulrike Luxburg. Auditing Local Explanations is Hard. In Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), pp. 18593-18632, 2024.
Blair Bilodcau, Natasha Jaques, Pang Wei Koh, and Been Kim. Impossibility Theorems for Feature Attribution. Proc. of the National Academy of Sciences (PNAS), 121(2):c2304006100 2024.
Guy Blanc, Jane Lange, and Li- Yang Tan. Provably Efficient, Succinet, and Precise Explanations. In Proc. 35th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 0129-6144, 2021.
12

---

Published as a conference paper at ICLR 2026
Guy Blanc, Caleb Koch, Jane Lange, and Li- Yang Tan. A Query-Optimal Algorithm for Finding Counterfactuals. In Proc. 39th Int. Conf. on Machine Learning (ICML), pp- 2075-2090, 2022.
Ryma Boumazouza, Fahima Cheikh-Alili, Bertrand Mazure, and Karim Tabia. ASTERYX: A model- Agnostic SaT-basEd appRoach for SYmbolic and Score-Based EXplanations. In Proc. 30th ACM Int. Conf. on Information & Knowledge Management (CIKM), pp. 120-129, 2021.
Ryma Boumazouza, Raya Elsaleh, Melanie Ducoffe, Shahaf Bassan, and Guy Katz. FAME: For- mal Abstract Minimal Explanation for Neural Networks. In Proc. 14th Int. Conf. on Learning Representations (ICLR), 2026.
Louenas Bounia. Enhancing the Intelligibility of Boolean Decision Trees with Concise and Reliable Probabilistic Explanations. In Proc. 20th Inf. Conf. Information Processing and Management of Uncertainty in Knowledge-Bass Systems (IPMU), pp. 205-218, 2024.
Louenas Bounia. Using Submodular Optimization to Approximate Minimum-Siie Size Abductive Path Explanations for Tree-Based Models. In Proc. 41st Conf. on Uncertainty in Artificial Intelligence (UAI), 2025.
Louenas Bounia and Frederic Koriche. Approximating Probabilistic Explanations via Supermodular Minimization. In Proc. 39th Conf. on Uncertainty in Artificial Intelligence (UAI), pp. 216-225, 2023.
Marco Calautti, Enrico Malizia, and Cristian Molinaro. On the Complexity of Global Necessary Reasons to Explain Classification. 2025. Technical Report.
2501. 06766
Emilio Carrizosa, Jasone Ramírez-Ayerbe, and Dolores Romero Morales. Mathematical Optimization Modelling for Group Counterfactual Explanations. European Journal of Operational Research (EJOR). 319(2):399-412, 2024.
Brandon Carter, Jonas Mueller, Siddhartha Jain, and David Gifford. What Made You Do This? Understanding Black-Box Decisions with Sufficient Input Subsets. In Proc. 22nd Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 567-576, 2019.
Brandon Carter, Siddhartha Jain, Jonas W Mueller, and David Gifford. Overinterpretation Reveals Image Classification Model Pathologies. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), pp. 15395-15407, 2021.
Wenjing Chen and Victoria Crawford. Bicriteria Approximation Algorithms for the Submodular Cover Problem. In Proc. 37th Conf. on Neural Information Procesing Systems (NeurIPS), pp.
72705-72716, 2023.
Arthur Conmy, Augustine Mavor-Parker Aengus Lynch. Stefan Heimersheim, and Adrià Garriga- Alonso. Towards Automated Circuit Discovery for Mechanistic Interpretability. Proc. 37th Conf. Neural Information Processing Systems (NeurIPS), pp. (6318-16352) 2023.
Yves Crama and Peter L Hammer. Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press, 2011.
Adnan Darwiche. Logic for Explainable AI. Proc. 38th ACM/IEEE Symposium on Logic in
Computer Science (LICS), pp. 1-11, 2023.
Adnan Darwiche and Auguste Hirth. On the Reasons Behind Decisions. In Proc. 24th European Conf. on Artificial Intelligence (ECAI), pp. 712-720, 2020.
Adnan Darwiche and Chunxi Ji. On the Computation of Necessary and Sufficient Explanations. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 5582-5591, 2022.
Sanjoy Dasgupta, Nave Frost, and Michal Moshkovitz. Framework for Evaluating Faithfulness of
Local Explanations. In Proc. 39th Int. Conf. Machine Learning (ICML), pp. 4794 4815, 2022.
Ian Davidson, Nicolás Kennedy, and SS Ravi. CXAD: Contrastive Explanations for Anomaly Detection: Algorithms, Complexity Results and Experiments. Transactions on Machine Learning Research (TML.R), 2025.
13

---

Published as a conference paper at ICLR 2026
Alessandro De Palma, Greta Dolcetti, and Caterina Urban. Faster Verified Explanations for Neural Networks. 2025. Technical Report. https:: haapss://axxvvv. org/ abs///b////// 2ttp:/512.000 00164
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations Based on the Missing: Towards Contrastive Explanations with Pertinent Negatives. Proc. 32nd Conf. on Neural Information Processing Systems (NewrIPS), 2018.
Hidde Fokkema, Rianne De Heide, and Tim Van Erven. Attribution Explanations that Provide Recourse Cannot be Robust. Journal of Machine Learning Research (JMLR), 24(360):1-37 2023.
Hidde Fokkema, Damien Garreau, and Tim van Erven. The Risks of Recourse in Binary Classification. In Proc. 27th Int. Conf. on Artificial Intelligence and Statisties (AISTATS), pp. 550-558, 2024.
Tobias Geibinger, Reijo Jaakkola, Antti Kuusisto, Xinghan Liu, and Miikka Vilander. Why This and Not That? A Logic-based Framework for Contrastive Explanations. In Proc. 19th European Conf. on Logics in Artificial Intelligence (JELIA). pp. 45 60. Springer, 2025.
Joshua Größer and Ostap Okhrin. Copulae: An Overview and Recent Developments. Wiley Interdis- ciplinary Reviews: Computational Statistics, 14(3):e1557, 2022.
Riccardo Guidotti. Counterfactual Explanations and How to Find Them: Literature Review and Benchmarking. Data Mining and Knowledge Discovery (DMKD), 3865):2770-2824, 2024.
Hyukjun Gweon, Matthias Schonlau, and Stefan H Steiner. The K Conditional Nearest Neighbor Algorithm for Classification and Class Probability Estimation. PeerJ Computer Science, 5te 194, 2019.
Itamar Hadad, Shahaf Bassan, and Guy Katz. Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees. In Proc. 14th Int. Conf. on Learning Representations (ICLR), 2026.
Ouns El Harzli, Bernardo Cuenca Grau, and Ian Horrocks. Cardinality-Mnnimal Explanations for Monotonic Neural Networks. In Proc. 32nd Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 3677-3685, 2023.
W Keith Hastings. Monte Carlo Sampling Methods using Markov Chains and their Applications. Biometrika, 57:97-109, 1970.
Rongjie Huang, Max W. Y. Lam, Jun Wang. Dan Su, Dong Yu, Yi Ren, and Zhou Zhao. FastDiff: Fast Conditional Diffusion Model for High- Brig-Quulity Speech Synthesis. In Proc. 31st Int. Joint Conf. on Artificial Intelligence (IJCAI), pp- 4157-4163. 2022.
Xuanxiang Huang, Yacine Izza, Alexey Ignatiev, and Joao Marques-Silva. On Efficiently Explaining Graph-Based Classifiers. In Proc. 18th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), 2021.
Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva Abduction-Based Explanations for Machine Learning Models. In Proc. 33rd AAAI Conference on Artificial Intelligence, pp. 1511- 1519, 2019.
Alexey Ignatiev, Martin Cooper, Mohamed Siala, Emmanuel Hebrard, and Joao Marques-Sin Silva. Towards Formal Faimness in Machine Learning. In Proc. 26th Int. Conf. on Principles and Practice of Constraint Programming (CP), pp. 846-867, 2020a.
Alexey Ignatiey, Nina Narodytska, Nicholas Asher, and Joao Marques-Silva. From Contrastive to Abductive Explanations and Back Again. In Proc. Int. Conf. of the Italian Association for Artificial Intelligence (AIxAI), pp. 335-355, 2020b.
Alexey Ignatiev, Yacine Izza, Peter Stuckey, and Joao Marques-Silva Using MaxSAT for Efficient Explanations of Tree Ensembles. In Proc. 36th AAAI Conference on Artificial Intelligence, pp. 3776-3785, 2022.
Rishabh K Iyer and Jeff A Bilmes. Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints. Proc. 27th Conf. on Neural Information Processing Systems (NeurIPS), 2013.
14

---

Published as a conference paper at ICLR 2026
Yacine Izza and Joao Marques-Silva. On Explaining Random Forests with SAT. In Proc. 30th Int. Joint Conf. on Artificial Intelligence (IJCAI), 2021.
Yacine Izza, Xuanxiang Huang. Alexey Ignatiev, Nina Narodytska, Martin Cooper, and Joao Marques- Silva. On Computing Probabilistic Abductive Explanations. Int. Journal of Approximate Reasoning (IJAR), 159:108939, 2023.
Yacine Izza, Xuanxiang Huang, Antonio Morgado, Jordi Planes, Alexey Ignatiev, and Joao Marques- Silva. Distance-Restricted Explanations: Theoretical Underpinnings & Efficient implementation. In Proc. s/ Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp- 475 486, 2024a.
Yacine Izza, Kuldeep S Meel, and Joao Marques-Silva. Locally-Minimal Probabilistic Explanations. In Proc. 27th European Conf. on Artificial Intelligence (ECAI), 2024b.
Reijo Jaakkola, Tomi Janhunen, Antti Kuusisto, Masood Feyzbakhsh Rankooh, and Mikkka Vilander. Explainability via Short Formulas: the Case of Propositional Logic with Implementation. Journal of Artificial Intelligence Research (JAIR), 83, 2025.
Alon Jacovi, Swabha Swayamdipta. Shauli Ravfogel, Yanai Elazar, Yejin Choi, and Yoav Goldberg. Contrastive Explanations for Model Interpretability. In Proc. Conf. Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1597-1611, 2021.
Helen Jin, Anton Xue, Weiqiu You, Surbhi Goel, and Eric Wong, Probabilistic Stability Guarantees for Feature Attributions. In Proc. 39th Conf. on Neural Information Processing Systems (NeurIPS), 2025.
Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counter- factual explanations to interventions. In Proc. 4th ACM Conf. on Fairness, Accountability, and Transparency (FAceT), pp. 353-362 2021.
Eoin M Kenny and Mark T Keane. On Generating Plausible Counterfactual and Semi-Factual Explanations for Deep Learning. Proc. 35th AAAI Conf. on Artificial Intelligence, number 13, pp. 11575-11585, 2021.
Alexander Kozachinskiy. Inapproximability of Sufficient Reasons for Decision Trees. 2023. Technical Report. httpp:://arxxv..rrr////aaa 02781
Elizabeth Kumar, Suresh Venkatasuubramanian, Carlos Scheidegger, and Sorelle Friedler. Problems with Shapley- Saapleey-Valu-Baassee Explanations as Feature Importance Measures. In Proc. 37th Int. Conf. on Machine Learning (ICML), pp. 5491-5500, 2020.
Emanuele La Malfa, Agnieszka Zbrzezny, Rhiannon Michelmore, Nicola Paoletti, and Marta Kwiatkowska. On Guaranteed Optimal Robust Explanations for NLP Models. In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 2658-26655 2021.
Eduardo Sany Laber. The Computational Complexity of some Explainable Clustering Problems. Information Processing Letters, 184: 184:106437, 2024.
Shuai Li, Yingjie Zhang, Hongtu Zhu, Christina Wang, Hai Shu, Ziqi Chen, Zhuoran Sun, and Yanfeng Yang. X-Nearest-Neighber Local Sampling Based Conditional Independence Testing. Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pp. 23321-23344, 2023.
Gianluigi Lopardo, Frédéric Precioso, and Damien Garreau. A Sea of Words: An In In-Depth Analysis of Anchors for Text Data. In Proc. 26th Int. Conf. on Artificial Intelligence and Statistics (AISTATS) 2023, 2023.
Scott M Lundberg and Su-In Lee. Unified Approach to Interpreting Model Predictions. Proc. 31st Conf. on Neural Information Processing Systems (NeurIPS), 2017.
Joao Marques-Sine SSllees--Ssaaaaaaa and Alexey Ignatiev. Delivering Trustworthy Al through formal XAL. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 12342-12350, 2022.
15

---

Published as a conference paper at ICLR 2026
Joao Marques-Silva and Alexey Ignatiev. No Silver Bullet: Interpretable ML Models Must be Explained. Frontiers in Artificial Intelligence, 6: 6:1128212, 2023.
Joao Marques-Silva, Silva, Thomas Gerspacher, Martin Cooper, Alexey Ignatiev, and Nina Narodytska. Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay. In Proc. 33rd Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp. 20590- 20600, 2020.
Joao Marques-Silva, Thomas Gerspacher, Martin Cooper, Alexey Ignatiev, and Nina Narodytska. Explanations for Monotonic Classifiers. In Proc. Int. Conf. on Machine Learning (ICML), pp. 7469-7479, 2021.
Reda Marzouk and Colin De La Higuera. On the Tractability of SHAP Explanatto under Markovian Distributions. In Proc. 41st Int. Conf. on Machine Learning (ICML), pp. 34961-34986, 2024.
Reda Marzouk, Shahaf Bassan, and Guy Katz. SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism. In Proc. 39th Conf. on Neural Information Processing Systems (NeurIPS), 2025a.
Reda Marzouk, Shahaf Bassan, Guy Katz, and De Higuera. On the Computational Tractability of the (Many) Shapley Values. In Proc. 28th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), 2025b.
Kuldeep S Meel, Aditya A Shrotri, and Moshe Y Vardi. Not all FPRASs are Equal: Demystifying FPRASs for DNF-Counting. Constraints, 24(3):21 1-233, 2019.
Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining Machine Learning Classifiers Through Diverse Counterfactual Explanations. In Proc. 3rd Conf. on Fairness, Accountability, and Transparency (FAccT), pp. 607-617, 2020.
Vidya Muthukumar, Tejaswini Pedapati, Nalini Ratha, Prasanna Sattigeri, Chai-Was Wu, Brian Kingsbury, Abhishek Kumar, Samuel Thomas, Aleksandra Mojsilovie, and Kush R Varshney. Understanding Unequal Gender Classification Accuracy from Face Images. 2018. Technical Report. httpp:::/aa.....rrp///p////
00099
Sebastian Ordyniak, Giacomo Paesani, and Stefan Szeider. The Parameterized Complexity of Finding Concise Local Explanations. In Proc. 32nd Int. Joint Conf. on Artificial Intelligence (IJCAI). 2023.
Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki, and Stefan Szeider. Explaining Decisions in ML Models: A Parameterized Complexity Analysis. In Proc. 21st Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp. 563-573, 2024.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-Precisioe Model-Agnostic Explanations. In Proc. 32nd AAAI Conf. on Artificial Intelligence, 2018.
Majun Shi, Zishen Yang, and Wei Wang. Minimum Non-Submodular Cover Problem with Applica- tions. Applied Mathematics and Computation, 410:126442, 2021.
Andy Shih, Arthur Choi, and Adnan Darwiche. Symbolic Approach to Explaining Bayesian Network Classifiers. In Proc. 27th Int. Joint Conf. Artificial Intelligence (IJCAI), pp. 5103- 5111, 2018.
Bernardo Subercaseaux, Marcelo Arenas, and Kuldeep S Meel. Probabilistic Explanations for Linear Models. In Proc. 39th AAAI Conf. on Artificial Intelligence, pp. 20655-20662, 2025.
Guy Van den Broeck, Anton Lykov, Maximilian Schleich, and Dan Suciu. On the Tractability of SHAP Explanations. Journal of Artificial Intelligence Research (JAIR), 74:851-886, 2022.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the Optimal Memorization Power of ReLU Neural Networks. Proc. 10th Int. Conf. on Learning Representations, ( (ICLR), 2022.
Vijay V Vazirani. Approximation Algorithms. Springer, 2001.
16

---

Published as a conference paper at ICLR 2026
Sahil Verma, Varich Boonsanong, Minh Hoang. Keegan Hines, John Dickerson, and Chirag Shah. Counterfactual Explanations and Algorithmic Recourses for Machine Learning: A Review. ACM Computing Surveys, 56(1)):31)))))))))))) (111:11-422, 2024.
Stephan Wäldchen, Jan Macdonald, Sascha Hauch, and Gitta Kutyniok. The Computational Com- plexity of Understanding Binary Classifier Decisions. Journal of Artificial Intelligence Research (JAIR), 70:351-388 2021.
E. Wang, P. Khosravi, and G. Van den Broeck. Probabilistic Sufficient Explanations. In Proc. 30th Int. Joint Conf. on Artificial Intelligence (ICCAI) 2021a.
S. Wang, H. Zhang. K. Xu, X. Lin, S. Jana, C. Hsieh, and Z. Kolter. Beta-Crown: Efficient Bound Propagation with Per-Neuron Split Constraints for Neural Network Robustness Verification. In Proc. 35th Int. Conf. Advances in Neural Information Processing Systems (NeurlPS), pp- 29909-29921, 2021
Greta Warren, Eoin Delaney, Christophe Guéret, and Mark T Keane, Explaining Multiple Instances Counterfactually: User Tests of Group-Countert Counterfactuals for XAI. In Proc. 32nd Int. Conf. on Case-Based Reasoning (ICCBR), pp. 206 222, 2024.
Ingo Wegener. The Complexity of Symmetric Boolean Functions. Computation Theory and Logic, pp. 433 442, 2005.
Laurence A Wolsey, An Analysis of the Greedy Algorithm for the Submodular Set Covering Problem. Combinatorica, 2(4):385-393, 1982.
Haoze Wu, Omri Isac, Aleksandar Zeljié, Teruhiro Tagomori, Matthew Daggitt, Wen Kokke, Idan Refaeli, Guy Amir, Kyle Julian, Shahaf Bassan, et 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.
Min Wu, Haoze Wu, and Clark Barrett. Verix: Towards Verified Explainability of Deep Neural Networks. In Proc. 36th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2024b.
Lei Xu, Maria Skoularidou, Alfredo Cuesta-Infante, and Kalyan Veeramachaneni. Modeling Tabular Data Using Conditional GAN. Proc. 33rd Cond. on Neural Information Processing Systems (NeurIPS), 2019.
Anton Xue, Rajeev Alur, and Eric Wong. Stability Guarantees for Feature Attributions with Multi- plicative Smoothing. Proc. 37th Conf. Neural Information Processing Systems (NeurIPS), pp. 22388-62411 2023.
Kayo Yin and Graham Neubig. Interpreting Language Models with Contrastive Explanations. In Proc. Conf. on Empirical Methods in Natural Language Processing (EMNLP), pp. 184-198, 2022.
Jinqiang Yu, Alexey Ignatiev, Peter Stuckey, Nina Narodytska, and Joao Marques-Silva Eliminating the Impossible, Whatever Remains Must Be True: On Extracting and Applying Background Knowledge in the Context of Formal Explanations. In Proc. 37th AAAI Conf. on Artificial Intelligence, pp. 4123-4131, 2023.
17

---

Published as a conference paper at ICLR 2026
Appendix
The appendix contains formalizations and proof's that were mentioned throughout the paper:
Appendix
contains extended related work on Formal XAI.
Appendix
contains the formalizations of the models and distributions used in this work.
Appendix
contains the proof of Proposition
Appendix contains the proof of Proposition
Appendix contains the proof of Proposition
Appendix contains the proof of Proposition
Appendix contains the proof of Proposition
Appendix contains the proof of Theorem
Appendix contains the proof of Proposition
Appendix contains the proof of Theorem
Appendix contains the proof of Theorem
Appendix contains the proof of Theorem
Appendix contains an LLM usage disclosure.
A EXTENDED RELATED WORK ON FORMAL XAI
Our work falls within the line of research on on formal explainable Al (formal XAI) Marqqees-Sin Silva
& Ignatiev 2022), which studies explanations equipped with provable guarantees Yu al. 2023
Darwiche & Ji, 2022; Darwiche 2023 Shih et al. 2018 Azzolin et al. 2025 Audemard et al.
C et al. 2025). A central theme in this area concerns the computational complexity of
generating such guaranteed explanations (Barceló et al.) 2020; ?: Marzouk et al. 20255 b Marzouk
De La Higuera| 2024 Bassan et al. 2025e] Amir al. 20224] Blanc et al. 2021: 2022 Jaakkola
ct al. [025 | Amgoud & Cooper| [026 Geibinger et al. 2025). Since obtaining formal explanations is
often computationally intractable for expressive models such as neural networks (Adolí et al.) [0024]
Barceló et al. 2020) and tree ensembles (Ordyniak et al. 2024 Bassan et al. 2025a), much of the
literature has focused on more tractable model classes (Marques-Sin -Siqua & Ignatiev (023), including
decision trees (Bounia 2025 Arenas et al., 2022 Bounia, 2024] Bounia & Koriche 2023). monotonic
models (Marques-Sile Silva et al. 2021 Harzli et al. 2003). linear models (Marques-Siie et al. 2020
Subercaseaux et al. 2025). and additive models (Bassan et al. 2026).
Beyond complexity-theoree investigations, substantial effort has also been devoted to computing formal explanations in practice using automated reasoning tools, such MaxSAT and MILP solvers
for tree ensembles (Audemard et al. 2023 2022a: Ignaticv et al.] [022]
Boumazouza et al. 2021)
and neural network verification frameworks (Wang al. [022b] Wu et al. (022aa) derive certified
explanations for neural networks (Wu et al.] 2024b) Bassan & Katz 2023 Bassan et al.) 2023 Izza
al. 22024a] Hadad al.) 2026)] [gnatiev al. 2019). Additional approaches seek alleviate the
inherent computational burden through abstractions (De Palma et al. [2025]
Bassan et al. 2025b
Boumazouza al. 2026), relaxations such as smoothing (Xue al. 2023] Anani al. 2025 Uin
et al. 2025), or training-time time interventions (Alvarez Melis & Jaakkola 2018
Bassan et al. 2025c d)
Finally, within formal XAI. a related line of work studies methods that leverage combinatorial and submodular optimization techniques to improve the computation of local probabilistic sufficient reasons (Bounia 2025 Bounia Koriche 2023), particularly for decision tree classifiers. As
noted in that literature, well as in this work, the value-function objective underlying these local explanation variants is not submodular practice. Nevertheless, greedy algorithms inspired by submodular optimization often serve as effective heuristics and can yield high-quality explanations empirically. In contrast, our work establishes rigorous theoretical connection between combinatorial and submodular optimization objectives and the global variants of sufficient and contrastive reasons. This connection provides formal guarantees and opens the door to a broader range of principled algorithmic implementations.
18

---

Published as a conference paper at ICLR 2026
B MODEL AND DISTRIBUTION FORMALIZATIONS
In this section, we formalize the models and distributions referenced throughout the paper. Specifically, Subsection [. defines the model families, while Subsection B.2 formalizes the distributions.
B.1 MODEL FORMALIZATIONS
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 define a decision tree (DT) as a directed acyclic graph that represents a function f: - [c]. where E N denotes the number of classes. The graph encodes the function follows: (i) Each internal node v is assigned a distinct binary input feature from the set {1...., }: (ii) Every internal node has at most k outgoing edges, each corresponding to value in [k] assigned to u; (iii) Along any path a in the decision tree, each variable appears at most once; (iv) Each leaf node labeled with class from [c]. Thus, assigning values to the inputs
uniquely determines a path a from the root to leaf in the DT. where the function output fx) corresponds to class label i [c]. The size of the DT, denoted [f]. defined as the total number of edges in the graph. To allow
for flexible modeling, the ordering of input variables (1....; n may differ across distinct paths and o', ensuring that no variable is repeated along single path.
Neural Networks. We present our hardness proofs for neural networks with ReLU activations, though our tractability results (i.e., polynomial-tine algorithms) apply to any architecture that allows for polynomial-time inference
standard assumption. Thus, all separation results between tractable and intractable cases we prove carry over to any neural architecture at least as expressive as standard feed-forward ReLU network, encompassing many widely used models such as ResNets, CNNs, Transformers, Diffusion models, and more. Moreover, note that any Rel. U network can be represented as fully connected network by assigning zero weights and biases missing connections. Following standard conventions (Barceló et al. [020 [assan et al., (2024] Adolf et al.) (025). we thus assume the network is fully connected. Specifically, our analysis applies to multi-layer perceptrons (MLPs). Formally, an MLP f consists of 1 hidden layers (g(3) for j = l.....t 1) and one output layer (()), where each layer is defined recursively
g0و = (g + (0))
where Wi) denotes the weight matrix, b63) the bias vector, and gهو the activation function of the j-th layer. Accordingly, the model comprises weight matrices (W(),.... W()), t bias vectors (b(1) b()),, and activation functions (o(1), (o()))....,,())
The input layer is defined as (0) of the network are governed by a sequence positive integers do..... ; de, with weight matrices and bias vectors given by WOO) E Qdi-1xd; xdd and ((0) E Q respectively. These parameters are learned during training. Since the model functions
{0, 1]"h representing the binary input vector. The dimensions
binary classifier over features, we set do and d, = 1. The hidden layers use the ReLU activation function, defined by ReLU(xr) = max(0, .). Although sigmoid activation is typically used during training, for interpretability purposes, assume the output layer applies a threshold-basee step function, defined as step(z) = if 2 0 and step(z) 0 otherwise.
Tree Ensembles. Many popular ensemble methods exist, but since our goal is to provide post-hoc explanations, we focus on the inference phase rather than the training process. Our analysis centers on ensemble families that rely on either majority voting (c.g., Random Forests) or weighted voting (e.g., XGBoost) during inference. However, as with our treatment of neural networks, our tractability results namely, polynomial-tima algorithms extend to any possible ensemble configuration with polynomial-time inference, encompassing an even broader range of ensemble configurations.
Majority Voting Inference. In majority voting inference, the final prediction f(x) is assigned to the class j E [c] that receives the majority of votes among the individual predictions fx(x from all i [k:] (i.e., from each tree in the ensemble).
19

---

Published as a conference paper at ICLR 2026
f(x) (ajority((f(()) | [k]]]
(10)
where majority(S) denotes the most frequent label in the multiset S. If there is tie, it is resolved by a fixed tie-breaking rule (e.g., lexicographic order or predefined priority).
Weighted Voting Inference. In weighted voling inference, each model in the ensemble is assigned a weight dy E Q representing its relative importance. The predicted class is the one with the highest total weight across all models. Formally, for any E F, we define f as:
((x)
arg max jE
Φ5 [[]((x)
(11)
where Il denotes the identity function.
B.2 DISTRIBUTION FORMAIIZATIONS
This subsection formalizes the distribution definitions discussed in the main paper.
Empirical Distributions. The distribution 2> over the input features will be defined based dataset D comprising various inputs z' ,z?....z!!! Here, the distribution of any given input E F defined by the frequency occurrence of x within D, specifically by:
D
Pr(x)
1
Σ
I(z'
=x)
(12)
D
Independent Distributions. Formally, given probability value p(x.) E [0, defined for each individual input feature, we say that the distribution D is independent if the joint probability over inputs is given by Pr(x): = [[s p(x:).
We observe that when p(x:)= p(x,) holds for all i,j [n]. the distribution reduces to the uniform distribution, a special case of independent distributions.
General Distributions. We note that many of the proofs in this work - particularly those concerning
fundamental properties of value functions - apply broadly over general distribution assumptions. While empirical distributions (using the training dataset as proxy) are common in XAI, alterna- tive frameworks for approxin imttion distributions include k-NN resampling from nearby points (Li) al.] [2033] Almanjahie et al.) 2018 (weon al., 2019), copulas for modeling tabular dependen- Grööeer & Okhrin (022), or more advanced conditional generative models such CTGAN (Xu)
cies
cct al. 2019) and conditional diffusion models (Huang et al. 2022). Such choices are common in the
counterfactual explanation and algorithmic recourse literature (Karimi et al.) 2021 Fokkema et al.
2024
2023 Verma et al., 2024), which are related to contrastive explanations. Furthermore, when the value function is not computed directly from a structural property of the model (e.g.. leaf enumeration in decision trees) or from empirical distributions, one may instead approximate it using methods such Monte Carlo sampling (Hastings 1970), following approaches similar to (Subercaseaux al.
2025
Lopardo et al. 2023
B.3 SUBSET VS. CARDINAL MINIMALITY
In this subsection, we provide a more detailed discussion of the distinction between cardinal and subset minimality. Cardinal minimality offers substantially stronger guarantee, as it corresponds to a globally minimal explanation size, whereas subset minimality only ensures a local form of minimality.
To see why cardinal minimality is stronger, note that if S C [n] is a cardinally minimal explanation, then smaller set S' with [S'| < |S] can qualify explanation. Hence, strict subset 5 Ç S is an explanation, which means S is also subset minimal.
However, the reverse does not hold. Consider the function:
20

---

Published as a conference paper at ICLR 2026
x1 x (x2
(13)
and the assignment := (1, 1,,1,1), which gives f(1, 1. Fixing feature X1 1 yields cardinally minimal (and subset minimal) sufficient reason, since the prediction remains regardless of X2, x3- But fixing both X2 and X; = also gives subset minimal explanation yet not cardinally minimal one. Thus, while every cardinally minimal explanation subset minimal, not every subset minimal explanation cardinally minimal.
C PROOF PROPOSITION
Proposition 1. While the non-probabillstic case (ò = 1) admits unique subset-minimal global sufficient reason (Bassan et al. (2024), the general probabilistic setting (for arbitrary 8), there exist functions J that have O vn) subset-minimal global sufficient reasons.
Proof. It known that certain Boolean functions admit an exponential number of subset-minimal local conn-bbbabllistcc sufficient reasons for some input x Bassan al. (2024). particular, this phenomenon was shown to occur in functions of the following form. We demonstrate that the same function admits an exponential number of global and probabilistic sufficient reasons. Notably, the mentioned function is a special case of a broader class of threshold Boolean functions described in Wegener (2005). Specifically, for n = 2k + with & E N, this function defined as:
f(x) = { 0
Σ 2
(14)
otherwise
where is drawn from uniform distribution D. Notably, the function f is symmetric, in the sense of symmetric threshold Boolean functions Wegener (2005): its output depends solely on the number of I's (or, equivalently, 0's) in the input and is invariant under any permutation of input bits. Furthermore, the two extreme inputs the all-zeros vector (O...., 0) and the all-ones vector (I,..., 1) each admit an exponential number of subset-minimal local (non-probabilistic) sufficient reasons.
Since the function f is symmetric, the condition (St) ugg (S2) holds for any two subsets S1. S2 S [n]. Moreover, can be verified that for any subset C n of size
have:
(Vi E S).
(S)(())=
{t))
(15)
We also deliberately set to satisfy:
Sut S (i}) < & 2 (
(16)
and also set : 1 Each these subsets is subset-minimal because any subset of size at most [ fails be sufficient reason for (f.x) (with respect to the 5 threshold). Therefore, directly apply the same analysis as in (Bassan al. 2024). particular, there are exactly (1)) subset-minimal local sufficient reasons for (J.x). Using Stirlnn''s approximation, we obtain:
2v2T 2 e²
n
2
lim -000
<
(17)
Vn
Vn
This yields the corresponding bound on the number of subset-minimal global d-sufficient reasons.
D PROOF OF PROPOSITION
setting Proposition 2. While the local probabilistic setting (for any 8) lacks monotonicity i.e., the value
functions o and of are non-monotonic (Arenas et al. 2022 Izza et al. 2023 Subercaseaux et al, 2025; Izza et al. 2024b)- in the global probabilistic setting (also for any 8), both value functions vgon and v2 are monotonic non-decreasing.
21

---

Published as a conference paper at ICLR 2026
Proof. In this section, prove the monotonicity property for both types of global explanations sufficient and contrastive. We begin by establishing the property for global sufficiency. To build intuition, first focus the simpler functions with discrete multi-valued input domains and multiple output classes. We further extend the result continuous input domains and show that the monotonicity property holds for any well-defined classification function. Finally, we demonstrate how the same monotonicity guarantees apply to global contrastive explanations. Importantly, none of our proofs rely on the assumption of feature independence the monotonicity property holds strongly for any underlying distribution.
of Boolean functions, then generalize the result to
Lastly, we present a simple example showing that the monotonicity property does not hold for the local probabilistic sufficient or contrastive value functions.
The global sufficient value function va is monotonic non-decreasing for Boolean functions, under any data distribution.
Lemma 1.
Proof. Given an arbitrary set S E [n]. and feature $ S, we have that:
Pr(x) = Pr(xs, xs) = Pr(x3 xs) Pr(xs)
(18)
Consequently, this implies that:
Pr(x) Pr((sutj Xsu(() Pr(xsu(i))
= Pr((supi Xsu(()) 2r(xs,2;)
(19)
Xsu(()) Pr(x; xs) Pr(xs)
Moreover, for any two points x, x' 'D such that x5 = xx's and f(x) = 1 - f(('), it holds that:
PFz=D(f(Z) = fxx 2g = xs) = PreDD (f(z) = f(x') zs = X's
(20)
To simplify notation, we occasionally omit the distribution notation D in the local probability expression (f)) = f(x) Zs = xs), and use ft and f to denote the events f(z) = 1 and
fz) 0, respectively.
We begin with technical simplification of the probability term to facilitate the proof, and then proceed establish monotonicity.
Simplifying the probability term. Let Ds denote the distribution restricted to the set S. Given a point x ~ D and a set S, consider all points z ~ D such that ny = Xg and f(z) b, where b E {0, 1} - they all share the same local probability Prz=D(f(z) = b zs xs). For every x ~ D that shares the same 25 and the same output b, we marginalize over Øz. This yields Pr(s(x)= = b,xx) Pr(f(x) = xs) Pr(xs), from which we can infer:
PFaND(f(z) = zs = xs) = Pr(f(x)= = b xs).
(21)
Thus, for ExDD (P f(x) zg = xs)]. we get that:
EXDD PIND(f(Z) f(x) 2g xx)]
Σ Pr(f PrwDD + Iz = xs) + E Pr(f ,s)) PrawD(f xx)
xgnDs.ft
xgnDa.f
Σ Pr(xs): [PrwDD(f + 1zs xs))² + (PrzwD(f 2s =
x ===xs))²
xg>Ds
Σ Pr(xs) [PrnDD(s+ 2s xs))² + (1 - Pr | =
xs)
zs
(22)
From which it follows that:
22

---

Published as a conference paper at ICLR 2026
Ex Ex-D(Prz-D((e)) f(x) 2suin = xsL(())]
Σ (r()) [(Pr((f [su(() =xSU(t))) - P1 [s xsu(t)) (}
Σ Pr(z: 1,xs) [Prr(ff 2s = x = 1))² 2 + +(11 (11-PM +f Zs xS, 1))
===l
Σ Ny
Pr(x, = 0,xs) ( Zg Xs. = 0))² + -Prr(f 2g = 0))
2,=0
(23)
Proving monotonicity. We now proceed prove the monotonicity claim, building on the previous
simplification. We begin by introducing few additional notations. Let of := Pr (f (z) =
Zs Xs, 2 = 1) and 9o + == Prz-D (z) 1 z5 = xs, = 0). Similarly, define P1 = Pr(
1 xs) and Po = Pr(a
x5). Then, the following expectations Bx-D(PreNDi (f f(x)
Z. Xs)] and E (Pzz) = [(x) Zsu(() xsu(et)] can be simplified accordingly 1
E ExDD PreND(f(L) f(x) Is = xs)
Σ Pr(xs) [P1 gt + Po Po + (1 - (P1. g + Po o)1))
Xg
(24)
Σ Pr(xs) [2(P) of + Po 9t, - 2(P, g6 + Po go + 1].
xs>Ds
As result, obtain the following:
E PrenD(J(Z) s(x) (sutt = xsu(et)]
Σ Pr(xs): P1 ((gt)² + +(1 - +1- (1= +
Σ Pr(xs) Po -(gt)) + (1 - (²)
xy>Ds
Ds
Σ Pr(xs): Pi (2((()))) 1 20 + +1) + Σ
Pr(xs) Po (2(g(())))) - -290 + 1)
xg>Ds
xe>Da 2,=0
2,=
(25)
Σ Pr(xs): [P1 (2(g)) 2g +1) + Po (2(g) ) 290 + 1)]
xs>
Σ Pr(xs): (2P: - ((gT)² g + 2P. ((x) 2- 90 +1]
Xg~Da
Σ Pr(xs): [2( (gt)² + Po (g 2(P g6 + Po gb) + +1].
=
Ny~Dz
Let AS, f) denote Ex-D (F f(x) Zsutt xsu(t))] - (P- f(x) Zs = x.) Without loss of generality, we assume that both P1 and Pa are positive. Otherwise, it can be verified that (, f) = Then, we get:
Note that the notations Pt. Po. g and -6 as well as all others used throughout the paper are not fixed constants, but rather depend on the specific input xg. Formally, they should be written as (xs),, Po(xs), and so However, for readability, omit the explicit dependence Xs.
23

---

Published as a conference paper at ICLR 2026
f.(S.))
Σ Pr(xs) [2( (gt)²+ Po (06))) Po- 2(pp 5/ + Po g0
xsnDs
Σ Xg>Da
2. Pr(xs) [(P: (g) + (Po )0) 2. Pı Po gf 95l (26)
Σ xg~Da
2. Pr(xs) P1 Po (g) )
2 0.
Note that identities along with the previous result, we conclude that E.DD (x-D(Prz-D(((2) f(x) zs =xs] is monotone, thereby concluding our proof.
PiPo and similarly: Po Po-Po Po(1 (o) Po-P)=P((1-Pa))
PgP.). Using these
Lemma 2. The global sufficient value function vaug is monotonic non-decreasing for functions with discrete mulli-valued inpul domains and multiple outpul classes, under any data distribution.
Proof. Extending the proof from the simplified Boolean case, we now generalize the result to functions whose input domains and output ranges each consist of finite set of values. Let K. represent the set output classes.
We can generalize equation 22 as follows:
EXW CorD(PrND(f()) f(x) 2s =xs]] (f (f =j Z5 xs))
Σ Pr(xs) XanDD
Pr
(27)
jEK
Given the condition 2s Xg, suppose feature can take possible values fui,...,,,, 2r}. Then, equation 23 can be generalized as follows:
E (Pren(((()) f(x) Zsu(t) = xsu(())]
Σ k=
Σ Ng
Pr(xs)- Pr(a = uk xs). 12
(PrnD(((()) = |zs = xs. 2 = =1a))
jeK
(28)
Let Pk denote Pr(z, = Uk xs). Let de denote PræDD(((z) = j zs xs. Ux)) that is. 24
takes the value Up and the output class is j. Then, we have
BADD Pr f(x) zs = xs)] Σ Pr(xs)
Σ
Pk 9h)
(29)
Xa
JEK #=1
and
(rr f(x) Zsssg xs
Σ Pr(xs)
Σ
P "iot)
Xy
jeK
Combining these implications, can conclude that:
24

---

Published as a conference paper at ICLR 2026
f)
Σ Pr(xs)
Σ PR
Σ
(1k)
Σ
Pk: 9
Xg
k=1
JEK
JEK k=1
Σ Pr(xs)
Pk. (oh)))
Σ
(Px. (.)2 2 Pk. Pi gh sf)
Ng
JEN k=1
JEK k=1
kel
(30)
Σ Pr(xs)
Σ
Ph Pt (9-())))-
ΣΣ
2- Pt 9e
Ng
JEK Kil
JEK Ke!
Σ Pr(xs)
Σ1
Pk Pt -96 -1) Σ
JEK k<!
2 0.
Hence, ENDD PraD(PraND(fa f(x) zs =x9)] is monotone, which completes the proof for this setting.
Lemma 3.
The global sufficient value function o is monotonic non-decreasing for functions with continuous input domains and multiple output classes, under any data distribution.
Proof. We extend the monotonicity results to functions where features are defined over continuous domains. One approach is to partition the domain of the continuous features into two disjoint subdomains and then adapt the proofs lemma reasoning remains unchanged when transitioning from the discrete to the continuous case-only the notation differs.
2 by revising the notation accordingly. The core
Alternatively, we provide direct proof below. Assume all features lie in continuous domains, and let p(xs.X3 xs) denote the corresponding joint probability density function. Moreover, let p(x;) denote the marginal probability density function of Tú, and X; denote the domain of feature i.
We define marginal density as
p(xs) = f
p(xs,xs)dxg
(31)
xxgEXs
where X's represents the domain of features in S. And the conditional density is defined as:
x(x)
p(re
X5) p(xs)
(32)
The local probability of S given x is defined
Pry-D(j(z)) = zs = xs) SLgEXs I(f(xs, =) p(xs: 7g 7g)
(33)
p(xs)
This term can also be decomposed into:
Piz-D(((2) = j us =xs) / J p(ze/ (s)) Prrp = 1zs = Xs, = =z)dzz (34)
via an additional feature t &f S.
We then modify equation 27 to ExND Pr Pr.D(f(E)) f(x) zs = =x]]
[ XeEXs
p(xs) 1
(Pr zs xs)) dxs,
(35)
jEK
25

---

Published as a conference paper at ICLR 2026
while equation 28 is changed to
ExDD PræwD(f(2) = f(x) [su(e) = =Xsu(t)]]
= ASEXs
1/ ZIE
p(xs)
p(zel (s)
( JEK
(PrzD = zsu(() xsu(t))) ())(t))))) dz) dxs.
(36)
For simplicity, let (t) denote Pra=D(f(z) = 2s Xs, 2t vz), and Pul denote p(zr xs).
Note that both (t) and Pais associated with fixed Xs We prove monotonicity follows:
f)
= LxDD PrzD(((()) = f(x) 2Suf() = xss(tt)] - ExnD PrzwD (f(z) = f((x zs = xs)] [Σ
= - p(xs)
1f
(PraD = = (su(t) xsU(())) dec dxs
.XSEXS
s
ZeE
jEK
[ p(xs)
LASEXS
Σ
Pris
PrawD(f(z)=
xs, = 2z)dze) daxs
jEK
- p(xs).
Σ
Pis Yj(1)ddx - 1 Pils (ss((Y)())))) Juks
JXEEX'
X,
JEK
-J p(xs).
(o pas pels (Y,(1)² - (())))(()) Jakes
Σ
JEK
- p(xs).
Σ
Ve Pns Peis (V,() - vy(1)) 2 dzzdzz Jass
JASEXS
JEK
2 0.
(37)
Proposition 2. While the local probabilistic setling (for any 8) lacks monotonicity iee, the value functions of and sug are non-monotonic (Arenas al. 2022 Izza al. 2023 Subercaseaux et al. 2025 Izza et al.) 2024b) in the global probabilistic setting (also any 0), both value functions con and b are monotonic non-decreasing.
Proof. As a consequence of lemmas to 3 we conclude that the global sufficient value function e monotonic non-decreasing for any deffnnef classification function - whether its features are Boolean, discrete, continuous, combination under any data distribution.
con S
u (S)
(38)
This implies that vgan monotonic non-increasing with respect to adding features to S. Equivalently, vam is monotonic non-decreasing as features are removed from S and added to S, thus completing the proof.
E PROOF OF PROPOSITION 3
3. While the local probabilistic sufficient setting (for any 8) lacks supermodulariry even when uniform, i.e., the value function v'ng not supermodular in the global probabilistic setting (also for any 8), when D exhibits feature independence, the value function vilg is supermodular.
Proposition
Proof. This section establishes the supermodularity property for both global sufficient and contrastive explanations. As with monotonicity, we begin with Boolean functions and progressively generalize
Changing X alters their values, we omit X5 the notation for brevity.
26

---

Published as a conference paper at ICLR 2026
discrete and continuous input domains, and finally consider the case of well-defined classification functions. Unlike the monotonicity property, however, these proofs require the assump- tion of feature independence. We also provide counterexample to show that supermodularity may fail when this assumption is relaxed.
to
Lemma 4. The global sufficient value function "a is supermodular for Boolean conattanfunciio functions, under the assumption of feature independence.
Proof. Particularly, we will prove that:
A,S,,) S A,S
(39)
where S S' and & S That is, f) is monotone.
Clearly, if S' S. then A, f) S A,(S", f) holds. S' S u {i}, where i & and + t. For the local probability Præ~D(f(z) = fxx
xs), under the assumption of feature independence,
we have that the following holds:
Pr,(/(z) = [xx) Es = xs)
Pr(z; = 1) Pr(a 1). Pr,(f(z) = fxx Xs, 4 = 1, = 1) +
Pr(4 = 1) Pr(2: = 0) Prz(f(z) = f(x) Zş = Xs, 2 = 1, = 0) +
(40)
Pr(4 = 0) Pr(z: = 1) (rz([(z) = =[(x) Zg Xs: 0, 1) +
Pr(z- = 0) Pr(z: = 0) Prx(f(z) - =f(x) Zg = Xs; 2 = 0, 2t = 0).
Let P1, Po. Q1, and Qo denote Pr(z; = 1), Pr(zt = 0), Pr(2, = 1). and Pr(z: = =0), respec-
tively. Moreover, let 9 91o- go1. and g0o denote Prz-D(f(z) = zg = Xs, 2 = 1, 21 = 1). PrzzD(f(z)
Zs Xs, 24 1, 0). PreWD = zs X5, 0, 2t 1). and
Pr,-D(((z) = 1 z. = Xs, = 0, 21 0), respectively.
We further decompose equation 26 into:
A(S)f)= Σ 2 Pr(xs) PiPo [[Q1 gi + Qo gol) (Q1 gio + Qo -db))
Ng
(41)
= Σ 2. Pr(xs) P.Po [Q (gft gio) + Qo (0ti - sttol
Xg
Similarly, the following also holds:
AS U (t).))
Σ 2. Pr(s())) P.Po (Q1 (gft -ito) + Qu -90t 91
(42)
xg~Ds
Thus, we get
A = Σ 2. P-Pr(x)) PiPo Q100 (at gtt 9/1 +
+
xs>D2
(43)
0.
This implies that f) is monotone, that is, c(SU((),)) < (SUU)),))-SS))
Lemma 5.
The global sufficient value function ung is supermodular for functions with discrete multi- valued input domains and multiple output classes, under the assumption of feature independence.
Proof. We extend the results of the previous section to multi-valued discrete functions, again with the assumption of feature independence. We use Ps. to denote Pr(*t v2). and Qx to denote
Pr(z: v.)). Moreover, use d denote (r z5 xs, 24 1 2t vg). We
27

---

Published as a conference paper at ICLR 2026
decompose equation to
= E Pr(xs)
EE
PEP P
Qu
P.. -E
Qu sker)
xg~Ds
JEK kEl
#==1
k'=1
(44)
Σ
Pr(xs)
Σ
P.P Σ
Qu
w -shil)
Kg Dg
JEK
Likewise, have
A ff).))
Σ
Σ Pr(xs) Pr(z v//) Σ
Σ
PRP (ok - skrr)
k= Xg
jEK R<1
Σ Pr(xs)
EQe. Qui Σ
PeP: (Pee - s22))2
(45)
X
K=11
jEK kcl
Σ Pr(xs)
Σ
Σ
PEP:
Σ
Qk (oW -2.))
xg
JEK kct
k==
Therefore, we get
((SS A.(S.))
Σ Pr(xs) ΣΣΣ
PEPIOUQ (o -khi Ryr + gh))
(46)
Xe~Ds JEK kC Wey!
2 0.
Proposition 3. While the local probabilistic sufficient setting (for any 5) lacks supermodularity- even when uniform, i.e,, the value function v'ngg is not supermodular- in the global probabilistic setting (also for any 8), when D exhibits feature independence, the value function v sug is supermodular.
Proof. We can generalize the supermodularity results established in Lemma 5 to the continuous case, assuming that D, satisfies feature independence. One approach is partition the domain of the continuous features into two disjoint subdomains and then adapt the proofs in Lemma 5 by revising the notation accordingly.
Altematively, we provide direct proof below. Under this assumption, the marginal and conditional densities simplify as follows:
p(xs) = II p(æx), and p(z, xs) = p(x)).
(47)
X
Consequently, the local probability of S conditioned becomes:
Pra-D(((2)=)) = =xx) /
I([(xs;z)==)) = j) II p(2))
(48)
egEXS
iES
We let (t, denote Prz) =j 25 = xs, = Ri, = =xt), where E S, g S and i + t.
Evidently,
and (t(t) / pi (i,,tt))
28

---

Published as a conference paper at ICLR 2026
We have:
f)
=f
p(xs)
Σ
1 2
/
PEP (Yg(t) - (Xx(())))) dz ) dxs
exeed's
JEK
=f p(xs)
Σ
(o
Xx, PiPU S Ps (,,(((,t)) - / Po Yj t' t') dzzdzr) )
dos
'sgEX'
JEK
=f
p(xs)
Σ
(Vr. xx
( ( Ps. (X,(tt) - Yj(i, dz;) dzzdzz) ( Jdss: DIPee
XeEX's
JEK
(49)
where
J..Ja. P.D SS ps (Y,((,)1,))) Yy(i,("))dz) d 'zddzr
-Sre / Xx.
Pipepipe (Yg(i,t) Y,(i,t) (Y)(1,))) (od,t)-Yyal -Yş(i', ( dzddy.
xx. Let S" =SU then we have:
ff)
=f
Exg Egg
p(xs:)
2 (1. /
PaPe
(Yg(i,t) - Yy(i,t)) "2zdze)) )] dxxs
JEK
JASEXS p(xs).
Σ5
1
( Pi: Veenee PaPe (Yg(1.)) (i)), dzidey) dzi dxs (50)
JEK
= -/ p(xs)
Σ 2
Ja PEPAPE (Ys(1,)) - (5((,1')) ( dxs.
ASEXS
JEK
where
J J.
P&PEPe (Y,(i,t) - Y,(i,t) ( dzddzedz
N. Jx+
-Ja. Xx [ Jxx P.PuPiPe (Y,(i,t) Yii,it)) d2dz
Let aci,tt) denote ti, - ti,)") and tt"', denote (i(, (i,,,, we can infer that A. f) - f.(
W Jay Jal J - (() dxs
p(xs)
Σ
4
jeK
0.
(51)
Consequently, the global sufficient value function v retains the supermodularity property for any valid classification function, regardless of whether its features Boolean, discrete, continuous, mix thereof.
We now demonstrate that the local probabilistic sufficient value function is neither submodular supermodular. As simple illustration, fix the uniform distribution on the three variables (2,, and define Boolean function as follows:
((1,, (x1 V 422) T3-
(52)
Consider the input x = (1, 1, 1) which is classified as 1. For the local probabilistic sufficient value function y have that the following holds:
29

---

2' Published as a conference paper at ICLR 2026
3 8' (0)
2 (133) 3
1
u ((1)) 2' (12))
4"
(f 2, 1. suurr {1,2}) = 2' ( (1,33) = 1, (1,, = 1, (
Since ( (1, - -
u < (M (1, - ((3)) the function
sun neither supermodular nor submodular.
F PROOF OF PROPOSITION 4
Proposition 4. While the local probabilistic contrastive setting (for any 5) lacks submodularity even when D is uniform, i.e., the value function v is not submodular in the global probabilistic setting (alsofor any ö), when 'D exhibits feature independence, the value function vg is submodular.
Proof. Once we establish that the global sufficient setting supermodular, it directly follows that the global contrastive setting is submodular. Let S S [n] be the set of features allowed to change, and suppose S C S" with & S". To compare the marginal contributions vgon (S {i} voon (5) and omm (S' (it)) "S")(S"), we equivalently compare (1 (1- u (S (S) {i))) - (1 snn (S) and (1
2 suff
( {i))) - (1 - ( Since S S S", it follows that S S S, and therefore we obtain:
(o (S) - Laufr( {i})) 2 (u - u (S') {+)))
(53)
Which is equivalent to:
(v (i)) - 2 (S)) 2 (v (S' U (i}) - vooa (S")).
(54)
Thus, the global contrastive value function vo.n is submodular, hence concluding this proof.
We will now demonstrate that the local probabilistic contrastive value function is neither submodular nor supermodular. As simple illustration, fix the uniform distribution on the three variables 433 and define a Boolean function as follows:
f x2) = (x1 V x2) A T3-
(55)
Consider the input (1, 1) which classified 1. For the local probabilistic contrastive value function u we have:
vo ((1)) 1, v ((2)) 1, v/con ((3)) 1 U ((2.
con (0)
3
1
1 Voen (11,2,3))
3
c (1,2})
o ((1,3))
4'
2'
2'
Since (v'on((11 (1, v'on ((2)) < ((1, (12,3)) (Vo ({1)) "000 (0)), the
function in is neither submodular nor supermodular.
In the rest of this section, we show that the feature independence assumption is not just sufficient but also necessary for supermodularity. We illustrate this with the following counterexample.
Define Boolean function:
f(1 x22) = 21
(56)
For this boolean function, it holds that f(00) = 0, f(11) = o, f(10) = 1, and f(11) = Moreover, define distribution D on 21 and æ2. Recall that the global sufficient value function is:
30

---

Published as a conference paper at ICLR 2026
Ex Ex (..-D(PrrD((()) [xx Zs xs)]
Σ Pr(x) Pra-D(S(Z) [(x) xx)
In addition, if we show that
() & ff
where S' S S" and t & S", then the global sufficient value function is supermodular. When S = 0, we have that the following holds:
Ex-D (r-D(Prr-D((()) = =((x) xx]]
= -rr(#1 = 0,32 - 0) Przwz(((z)) = 0) Pr(21= 0, =) Pra~D((()) = 0)
Pr(x1 = 1,22 =0 Prz))(((()) = + Pr((1 = 1,22 1) Præw((((2) =)
Which is also equivalent to:
Pr(x1 = 0, 22 = 0) (Pr(z1 = 0,32 = 0) Pr(x1=110111110 0,22 = 1)) +
Pr(z: 0,32 = 1) (Pr(z) 0,32 0) + Pr(m = 0,72 -1)) +
Pr(m: 1, 0) (Pr(x) 1,02 0) Pr(m 1,22 =1))
Pr(1: 1, = 1) (Pr(z) 1,42 0) + Pr(z1 =, 1))
=(P((11 = 22 0) Pr(21 0, 1))² (Pr(21 1,22 0) Pr(21 = 1,22 1))²
When 8 {2), have that the following condition holds:
Ex Ex-p(Pr,-D((E))) f(x 4s = xs)]
Pr(æ1 = 0,22 = 0) Przwz(((z) = n2 = 0) +
Pr(æ1 0, 1) PraDD(f( =0 I2 1) +
Pr(z1 1, = 0) Pr (f((z) = 1 = 0) +
Pr(z1 1, 1) Pra (f(() IΣ =
This can also be rearranged as follows:
Pr(o: = 0,
Pr(r: = 0, = 0) Pr(zi = = -
Pr(x = 0, 72
Pr(z1 = 02 = 1) Pr(x1 0,æ2 = 1) Pr(x) = 1, 1)
+
Pr(æ1 1,
Pr(x1 1, = 0) Pr(x1 0,æ2 = 0) + Pr(z) = 1, 0)
+
Pr(z: 1,32 1)
Pr(x1 1,02 = 1): Pr(x1 0,22 = 1) Pr(#1 1 = 1, 1)
Pr(z1 0, F2 0)2 + Pr 1, 0)2
+ Pr(m1 0, 1)2 Pr(z1 1, 1)²
Pr(æ1 = 0,42 = 0) + Pr(x: = 1,02 = -0)
Pr = 0, = 1) + Pr(x) = 1,22 1)
contrast, when = {1}. 1 we have the the following holds:
BwwD(Pr,-D(fe f(x) 4s = xs)
Pr(m 0, = 0) PræwD(f(z) = 0 = 0) +
Pr(æ1 0,42 = 1) Pr (f(()) =0 ||x1 = 0) +
Pr(z1 1, = 0) Pr (f((z) = =1 1| = =1) +
Pr(z1 1,42 = 1) PrwDD(f( | =1=1)
This can similarly be rearranged as follows:
31

---

Published as a conference paper at ICLR 2026
Pr(z1 0, = Pr(z1 0, 0) Pr(x) 0, 2222222222 = 1)
Pr(z) = 0, = 0) + Pr(z)= = 0,2g =1)
Pr(01 0,1² 0) Pr(11 0,02 1)
Pr(21 0, 1)
Pr(æ1 = 0,32 = 0) + Pr(21 = 0,32 =
Pr(z1 1, 0) Pr(21 1,
Pr(m1 1,32 0)
Pr(æ1 1,32 0) Pr(11 1,32
Pr(m1 = 1,32 0) Pr(m = 11
Pr(21 1, 1) Pr(z1 22 0) Pr(21 1,32=1
=1
Finally, when 8 = 21, we have the following condition:
Exwp(Pr-D(((P) = f(x)
xs)]]
Pr(æ1 0,32 = 0) PrawD (f 0 0| 0,22 0)
Pr(x1 = 0, = 1) PraD (f(z) = 0 | = 0, = =1] +
Pr(x1 1, 0) PreeD (f(z) 21 1, 0) +
Pr(m1 = 1, = 1) PreDD (f(z) = ||
21 =
1,42 =
This can likewise be reordered as follows:
Pr(x1 = 02 00 Pr(#1 = 22 0)
+ Pr(x1 = 0,02 Pr(z1 0, = +
Pr(z1 = 0, =0)
Pr(z1 0,12 = 1)
Pr(#1 1,32 0)
Pr(m1 1,22 1)
Pr(x1 = 1,22 = 0) Pr(#1 = 1,02 = 0)
+ -r(( = 1, = 1) Pr(æ1 = 1,32
=1
Let 2. Evidently, we have (.((1), f) = assume feature independence, we observe that:
Next, let us analyse (, f). We note that if
(Pr(2) 0, 22 = Pr(z1 0, 1))² + (Pr(21 1, 0) Pr(z1 =1,02 = 1))² = -Pr(#1 = + = 1)
Additionally, another condition that holds is:
Pr(z1 0, 0)2 Pr [1 = 1. 0)2
Pr(z1 0, 1)2 Pr(z1 1, 1)2 Pr(m: = 0,22 = 1) [z) 1,32 =
Pr(x: = 0,22 = 0) + Pr(zi [ = 1, 0)
Pr(x1 = =0 Pr(z -1)2.
This implies (0. f) 0, that is. (., f) < (f1)), However, without the assumption of feature independence, we cannot guarantee (0, f) = 0. For example, let:
Pr(x1 = 0, = 0) = Pou, Pr(#1 = 0, x2 = 1) = Po1
and
Pr(æ1 1,22 = 0) = Piu. Pr(z1 = 1,12 = 1) = Pu1
Then, by simplifying (0, f) we get that the following holds:
P + p2
pa + PR
[(Pbo + Poi)² (Pio + P.))
A, f)
(57)
Poo + Pio
Poi Pni
We then let Poo = 0.4, Poi 0.2, Piu = 0.1, and P11 = 0.3, and get that the following holds:
(0, (0.4)² + (0.1)
(0.2)² 2 (0.3) (0.4 [(0.4+0.2] 0.2) + (0.1 + 0.3)* = 0.08. (58)
0.5
0.5
This implies that A, (1, f). indicating that - unlike in the monotonicity setting where not required feature independence is necessary condition for supermodularity.
32

---

Published as a conference paper at ICLR 2026
G PROOF OF PROPOSITION 5
Proposition S. Computing Algorithm with the local value functions V'on and of does not always converge to a subset minimal b-sufficien//contratiii reason. However, computing with the global value functions v.oo or sugg necessarity produces subset minimal b-suffcceen//onnraative reasons.
Proof. We note that this proposition follows directly from our proof that both u and vgon are monotone non non-decreasing (as established in Proposition 2 along with other relevant conclusions drawn in prior work. the remainder of this section, we elaborate on how this monotonicity property leads to the stated corollary.
The convergence of Algorithm|]] to to a subset-minimal 5 global sufficient or contrastive reason with respect to the value functions Ugan and suff follows directly from the monotonicity property, for which prior work (Ignatiev et al. 2019 Wu et al., 2024b) Arenas al. 2022) showed that this type of greedy algorithm yields subset-minimal explanation when the underlying value function is monotone non-decreasing. The algorithm halts when, for all i S, the value v(S \ {i}) drops below 8, ensuring that although u(S) 2 5 (a maintained invariant), removing any element causes the condition to fail. Due to monotonicity, this implies that no proper subset of satisfies the condition, guaranteeing that S subset-minimal.
We now turn to explain why Algorithm [ does not converge to a subset-minimal solution in the local setting. We note that it well known that the local probabilistic sufficient value function (and likewise the local probabilistic contrastive value function) is not monotone Arenas et al. (2022): Izza
al. (2023); Suberccsaax et al. (2025): Izza al. (2024b). As a simple illustration, fix the uniform distribution on the two binary variables 11 22
and define Boolcan function as follows:
(x11 21 V T-2-
(59)
Consider the input x = (0, 1) which classified as 1, then:
( (0) 4" ((1)) ouun = 1, (f,,((,,))) =
(60)
Because ((ur(()) (0) > sunl ({1}) < u (f1, 2),, the function o is not monotone. Likewise, can be
computed that:
L.co (0) 1, v (f1)) 1, o (12) r.om ((1,2)) 3
(61)
(For vfoo the S denotes the set of features that allowed vary.) Because veca (0) v ((2)) of (f1, 2)), the function of is also non-monotone.
H PROOF OF THEOREM
Theorem If f is decision tree and the probability term vight can be computed in polynomial time given the distribution D (which holds for independent distributions, among others), then obtaining subset-minimal global 8 5-uufficient reason can be obtained in polynomial time. However, unless PTIME-NP, no polynomial time algorithm exists for computing a local 8-sufficient reason for decision trees even under independent distributions.
Proof. We begin by noting that for decision trees, assuming that D represents independent distribu- tions, the computation of the value function:
Sun (S) P (F(x) = fz) | zs)
(62)
Can be carried out in polynomial time using the following procedure. Thanks to the tractability of decision trees, iterate over all pairs of leaf nodes, each corresponding partial assignments
33

---

Published as a conference paper at ICLR 2026
Xş and Zzr. For each such pair, if both leaf nodes yield the same prediction under f. compute the corresponding term in the expected value Ex~pl BxwppPrrzpp (Prz=p(f(x = f(z) Xg = zg) by multiplying the respective feature-wist probabilities over the shared features of the two vectors. Under the feature independence assumption, these probabilities decompose, allowing the full expectation to be computed by summing the contributions of all such matching leaf pairs.
Since all probabilities involved are provided as part of the input and each step involves only polynomial-time operations, the entire procedure runs in polynomial time. This establishes that every step in Algorithm|| iss efficient, and thus the algorithm as a whole runs in polynomial time. Finally, combining this with Lemma 2 which proves that * is monotone non-decreasing, we conclude that Algorithm T converges to a subset-minims explanation. This is because the algorithm halts when, for all E S, the value v(S {i)) falls below while v(S) 2 8 preserved throughout. By monotonicity, this guarantees that no strict subset of S satisfies the condition, ensuring S is indeed subset-minimal.
For the remaining part of the claim, the result follows from (Arenas al. 2022 which showed that, assuming PANP, there is no polynomial-tmme algorithm for computing a subset-minimal 8-sufficient reason for decision trees. While this was proven specifically under the uniform distribution, the hardness clearly extends to independent distributions, which include this case. Combined, these results establish the complexity separation between the local and global variants, thus concluding proof.
I PROOF OF PROPOSITION 6
Proposition 6. For any model f. and empirical distribution D D computing subset-mininal global 5-sufficient or 5-contrastive reason for f can be done in polynomial time.
Proof. The computation of the global sufficient probability function:
Suff (S) Ex-D
f(z) xs = zs)
(63)
or the computation of the global contrastive probability function
Con (S) EX-D Pr + f(z) x5 = =z)]
(64)
Can be performed in polynomial time when D is selected from the class of empirical distributions. This is achieved by iterating over pairs instances x, z within the dataset and running an inference through fx) and f(z) to compute the expected values at each step. Consequently, determining whether the probability function exceeds or falls below a given threshold 8 can also be accomplished in polynomial time. Furthermore, leveraging the proof of non-decreasing monotonicity (Proposition () of the global probability function, we can utilize algorithm [ for contrastive reason search or for sufficient reason search. By executing linear number of polynomial queries, subset-minimal explanation (whether a subset minimal contrastive reason or a subset minimal sufficient reason) can thus be obtained in polynomial time.
J PROOF OF THEOREM 2
Theorem 2. Assuming f is neural network or tree ensemble, and D is an empirical distribution there exist polynomial-time algorithms for obtaining subset minimal global ô-sufficient and con- trastive reasons. However, unless PTIME-NP, there is no polynomial time algorithm for computing a subset minimal local 8- 8-sufficient reason or a subset minimal local 8-contrastive reason.
Proof. The first part of the proof follows directly from Proposition 6 which established that
this holds for any model, since both (S) Ex-D Pr (x) f(z) X3. = zs)] and vg (S) EEaD Pr (x() # f(z) x5
z3)] can be computed in polynomial time from
34

---

Published as a conference paper at ICLR 2026
the empirical distribution. For the second part, we proceed by proving two lemmas: one establishing the intractability of computing the sufficient case, and the other addressing the contrastive case.
Lemma 6. Unless PTIME- NP, then there is no polynomial time algorithm for computing a subset minimal local ö-sufficient reason for either tree ensemble or a neural network, under empirical distributions.
Proof. We will first prove this claim for neural networks and then extend the result to tree ensembles. We will establish this claim by demonstrating that if polynomial-time algorithm exists for computing subset-minima. local o sufficient reason for neural networks, then it would enable us to solve the classic comclete CNF-SAT problem in polynomial time. The CNF-SAT problem is defined as follows:
CNF-SAT:
Input: A formula in conjunetive normal form (CNF): é.
Output: Yes, if there exists an assignment to the literals of db such that de is evaluated to True, and
No otherwise
Our proof will also utilize the following lemma (with its proof provided in Barceló et al. (022 )
Lemma 7. Any boolean circuit & can be encoded into equivalent MLP over the binary domain {0, + {0, }} in polynomial time.
Proof. We will actually establish hardness for a simpler, more specific case, which will consequently imply hardness for the more general setting. In this case, we assume that the empirical distribution D consists of single element, which, for simplicity, we take be the zero vector O₂, Since the sufficiency of S in this scenario depends only on the local instance x and the single instance O, in our empirical distribution, the nature of the input format (whether discrete, continuous, etc.) does not affect the result. Therefore, the hardness results hold universally across all these settings.
Similarly to O,, we define 1n as an n-dimensional vector consisting entirely of ones. Given an input 6, we initially assign 1, to o, effectively setting all variables to True. If ø evaluates to True under this assignment, then a satisfying truth assignment exists. Therefore, we assume that (b(1,.) = 0. We now introduce the following definitions:
22 = (II A 22 A A...
(65)
o' ===0 x 62
6', while no longer a CNF, can still be transformed into an MLP f using Lemma g ensuring that behaves equivalently
o' over the domain {0, 1)". Given assumption that computing subset-minimal local d-sufficient reason is feasible in polynomial time, we can determine one for the instance (f,x x := 1n), 8 1, noting that the empirical distribution D is simply defined over the single data point O,,.
We now assert that the subset-minimal 8-sufficient reason generated for (f,x) encompasses the entire input space. i.c., S = {1, n). if and only if (Ø) &CNF-SAT.
Let us assume that S = [1, ... n). Since S is a 8-sufficient reason for (f,x), this simply means that setting the complementary set to any value maintains the prediction. Since the complementary set is @ in this case, this trivially holds. The fact that S is subset-minimal means that any other subset S' C S satisfies v(S") < 5 = 1. Since the probability function (rz= = f() Xs zs) is determined by a single point (the distribution contains only the point 0,,), the probability function can only take values of 1 or O. Hence, we also know that v(5") 0. This tells us that, aside from the subset (1, (1,...,,7) n). for any subset S' C S, fixing the features in S' result in classification outcome of 1. Since the d2 component within ø' is True only if all features are assigned 1, this directly implics that ø is assigned False for any of these inputs. Since we already know that á does not return True answer for the vector assignment 1, (as verified at the beginning), and now we have established that the same holds for all other input vectors, we conclude that á g CNF-SAT.
and the rest to does not
Now, suppose that S is a subset that is strictly contained within (1...., n). Given that S is sufficient under our definitions of the distribution D with 8 = can apply the same reasoning as before to
35

---

Published as a conference paper at ICLR 2026
conclude that v(S) 1. This implies that setting the features in S to 1 while setting the remaining features to O ensures that the function f evaluates to 1. Since this assigmment is necessarily not vector consisting entirely of ones, it follows that the Φ2 component within o' must be False. Consequently, the Φ component must be True, which implies that (Ø) ECNF-SAT: This completes the proof.
We have established that the following claim holds for neural networks. However, extending the proof tree ensembles requires minor and straightforward adaptation. To do so, will utilize the following lemma, which has been noted in several previous works (Ordyniak et al. 2024
Audemard
al. 2022by:
Lemma 8. Any CNF or DNF can be encoded into equivalent random forest classifier over the binary domain 10 - {0, 1} in polynomial time.
Proof. We observe that can apply the same process used in our proof for neural networks, where we encoded ø' into an equivalent neural network. However, o' is no longer valid CNF due to our construction (though encoding into an MLP was not an issue, as any Boolean eircuit can be transformed into an MLP). Nevertheless, since ø' consists of conjunction of only two terms, we can easily represent as an equivalent CNF:
ø' = (o2) (Cm V Φ22
(66)
Where each G; is a disjunction of a few terms. Consequently, o' is a valid CNF, allowing us to transform it into equivalent random forest classifier. The reduction we outlined for MLPs applies directly to these models as well, thereby completing the proof for both model families.
C
Lemma 9, Unless PTIME= NP, then there is no polynomial time algorithm for computing a subset minimal local 6-contrastive reason for either a tree ensemble or a neural network, under empirical distributions.
Proof. We will present a proof analogous to the one in Lemma 6 Specifically, we will once again utilize the classical NP-hard CNF-SAT problem defined in Lemma 6 In particular, given a Boolean formula o, we will demonstrate that determining a subset- minimal contrastive reason - whether for neural network a tree ensemble allows to decide the satisfiability of
First, we check whether assigning all variables in & to evaluates á to True. If so, the formula is satisfiable, and we have determined its satisfiability. Otherwise, we use Lemma X to encode the CNF formula as a neural network f. Next, we compute a subset-minimal 5-sufficient reason by setting D as the empirical distribution containing only single data point O,, following a similar procedure Lemma Additionally, we set 5 = 1 and compute subset-minimal 8-contrastive reason concerning xf.x). We will now demonstrate that if any subsct-minimal å contrastive reason obtained for Φ is satisfiable. then ó itself is satisfiable. Conversely, no subset-minimal 8 contrastive reason obtained. then is unsatisfiable. The validity of this claim follows a reasoning similar to that provided in Lemma 6 Specifically, the term Pr (f (x) # fz) xg zz), where the distribution D considers sampling from a single datapoint, can set the probability to either 0 or 1. Furthermore, since we are searching for a 8 = 1 contrastive reason, this is equivalent to asking whether there exists an assignment that changes the classification of f. which corresponds to modifying the assignment of from False to True. such an assignment exists, then ø is satisfiable. However, no subset-minima contrastive reason exists, then no subset of features fixed to evaluates to true. This is equivalent to stating that no assignment evaluates f (and consequently Φ) to True, implying that Φ is unsatisfiable.
when the complementary set is set ones
To extend the proof from neural networks to tree ensembles, we can follow the same procedure outlined in Lemma encoding the CNF formula into equivalent random forest classifier. Conse- quently, the proof remains valid for tree ensembles, thereby concluding the proof.
36

---

Published as a conference paper at ICLR 2026
K PROOF OF THEOREM 3
Theorem 3. Given a neural network or tree ensemble f and an empirical distribution 'D over a fixed dataset D. Algorithm 2 yields constant O IIn
minsete] 2on ((i))) caproximmaiin, bounded by
ve vaun(())) ([n))
(In(P))) for computing a global cardinally minimal 6-confrastive reason for assuming feature independence. In contrast, unless PTIME=NP, no bounded approximation exists for computing a local cardinally minimal 6-contrastive reason for any (J,x), even when [D] =1.
Proof. We divide the proof of the theorem into two lemmas, covering both the approximation guarantee and the result on the absence of a bounded approximation.
Lemma 10. Given neural network tree ensemble f and empirical distribution D over fixed dataset D, Algorithm yields constant O (In mincets) vean ((3}) approximation, bounded by
([a))
(In( fo for computing a global cardinally minimal 6-contrastive reason for f. assuming feature independence.
Proof. We will in fact prove stronger claim, showing that this holds for any model, provided the trivial condition that its inference time is computable polynomial time, along with one additional mild condition that we will detail later - both of which apply to both our neural network and tree ensemble formalizations.
We begin by noting that, since we are working with empirical distributions, the computation of the global contrastive probability value function:
con (S) = EX PT # f(z) x5- = zg)
(67)
Can be computed in polynomial time by iterating over all pairs x, in the dataset D, previously established in Proposition 2 Since Algorithm 2 performs only a linear number of these polynomial- time queries, its total runtime is therefore polynomial.
Regarding the approximation, the classical work by Wolsey et al. (Wolsey 1982) established harmonic-serien besee--baeeddeeee approximation guarantee for monotone non-decreasing submodular func- tions v with integer values. More generally, their result yields an approximation factor of e([ns)
O (In minsel-) m({i]) ) We showed in Proposition that the value function vgon is monotone
its submodularity. Com- bined with the fact that Algorithm runs in polynomial time, this directly yields an approximation
non-decreasing, and under feature independence,
2
guarantee of O In
((x)
[In
Menn (1n)
is both finite and bounded by (In()))) implying that it is effectively constant, due the assumption To ensure this, we begin by confirming that the expression is well-defined and finite. We then proceed to establish the desired bounds. To do so, we introduce a preprocessing step in which we eliminate "redundant" elements-thos that could theoretically cause the denominator minsejn] venn(()) ({i)) to be zero. We begin by formally defining what we mean by redundancy:
However, we must also show that the expression
min.eln! (2.
fixed dataset DD
Definition 1. Let D denote some empirical distribution over a dataset D. Then we say that some feature i E [n]] is redundant with respect to 'D for any pair x, 7 E D it holds that (((1)))11)2(()))))) = fxx).
Here, the notation (x ( indicates that all features in [n]] \ {i} are fixed to their values in x, while feature i is set to its value in z. Notably, this is equivalent to defining:
AS I Zg) / ((5s))))
(68)
As before, the notation (Xs; zg) indicates that the features in S are fixed to their values in x, while the features in 5 are fixed to their values in Thus, in this sense, if we "remove" feature i from the input space and define a new function $f'$ over the reduced space [n'] := [n] {d). then for any input of size n', the output of f' will exactly match the output of when applied to the same features [m] (i).
37

---

Published as a conference paper at ICLR 2026
This removal can be done in polynomial time for both tree ensembles and neural networks: for neural networks, involves detaching the corresponding input neuron from the network; for tree ensembles, it involves removing any splits that feature from all decision trees. Given the empirical nature of the contrastive value function c2m (5) as previously discussed in this proof and in Proposition 2 we can compute each rian ({)) for all E [n] by iterating all pairs x, 'D and checking whether:
(( # f(x)
(69)
If this condition holds, it indicates that feature i is not redundant. Conversely, if the condition fails for all pairs considered during iteration, then is deemed redundant. Once all redundant features have been identified with respect to the empirical distribution D, can remove them and construct equivalent model f'. As discussed above, this transformation can be performed in polynomial time for both neural networks and decision trees.
To conclude our proof, we observe that ({i)) equals 0 for some empirical distribution D and only if feature i is redundant with respect D. Therefore, once the preprocessing step re- moves all redundant features from and we construct the resulting function f', we ensure that min 2 ({t}) >
We now present the more precise bounds referenced in our proof. Specifically, we demonstrate that the approximation factor is (In (D))). Given that the empirical distribution D is fixed, this yields constant approximation. While tighter bounds may be achievable, our goal here is solely to establish that the bound is constant property that will later sharply contrast with the local explainability setting, where no bounded approximation exists.
More specifically, we know that the probability function Pry-D(J(x)) * f(z) x5 = 75) is, by the definition of empirical distributions, at least [D] Therefore, the definition of E PPrz- + In particular, this also implies that:
f(z) x5 zs)] (i.e., the value function vggn) is at least 1
min u.on (f+)) 2
(70)
sE|n]
D
Consequently, we obtain that:
0 non
(mz)
In
I In([D O[n((D))
(71)
min
2
({i})
Which concludes our proof.
C
Lemma 11. Unless PTIME=NP, there is no bounded approximation for computing a cardinally minimal local 8-contrastive reason for any (f.x) where f is either a neural network or tree ensemble, even when DD 1.
Proof. Assume, for contradiction, that there exists a bounded approximation algorithm for computing a cardinally minimal local 8-contrastive reason for some (J,x), where f is a neural network or However, Lemma establishes that even with a single baseline z = O, (i.c., when the entire dataset is just one instance), deciding whether a contrastive reason exists algorithm could yield bounded approximation for a cardinally minimal contrastive reason, it would contradict this result, such an approximation would implicitly decide the existence of a contrastive explanation.
tree ensemble- even when D
NP-hard unless PTIME = NP. Therefore, if polynomial-tin
L PROOF OF THEOREM 4
Theorem 4. Given a neural network or tree ensemble
I and an empirical distribution 'D over of
fixed dataset D. Algorithm yields a constant (T' + min 2n ((F))) aaproxximation for
38

---

Published as a conference paper at ICLR 2026
computing global cardinally minimal 6-sufficient reason for f. assuming feature independence. In contrast, unless PTIME-NP. there is no bounded approximation for computing a local cardinally minimal 6-sufficient reason for any (f,x), even when [D] =
Proof. We divide the proof into two lemmas: one establishing the approximation guarantee for the global case, and the other demonstrating the intractability of the local case.
Lemma 12. Given a neural network or Iree ensemble J and an empirical distribution 'D over
fixed dataset D, Algorithm 2 vields a constant O (T-Rr + minueets) (ig((i))) ) upproximation for computing global cardinally minimal ö-sufficient reason for f, assuming feature independence.
o eag([n))
Proof. The proof will follow a similar approach to that of Lemma 10
where we showed that for both neural networks and tree ensembles. Algorithm 2 achieves an approximation factor of
([n]
In min.e(ss) (()) After applying the preprocessing step, this ratio is guaranteed to be finite and bounded by (In()
Similar to Lemma I0 we will again prove a stronger claim namely, that the result holds for any model, assuming the trivial condition that its inference time is polynomially computable, and the additional condition concerning the removal of redundant features, as described in Lemma TO As discussed there, both conditions are satisfied by our neural network and tree ensemble formalizations.
Here as well, since we are working with empirical distributions, the computation of the global sufficient probability value function:
(S) EADD EnD((PreD(((x) = f(z) xs zs)]
(72)
can be computed in polynomial time by iterating over all pairs x, in the dataset D, previously makes only a linear number of such polynomial timeiill--mmeeeeeeeee queries, its overall runtime is polynomial.
shown in both Lemma and Proposition 2
Since Algorithm 2
Unlike Lemma 10 where the approximation relied on the result by Wolsey et al. (Wolsey 1982) for monotone non-decreasing submodular functions, the setting here requires different condition due to the supermodular nature of the function. Specifically, Shi et al. et al. 2021) provided an approx- =((]))=((w]())
imation guarantee of O RT
In minceto) yaar (4)5) where kf == minjejo]
vi (be)
(()-)(())
We established in Proposition] 2 that the value function og is monotone non-decreasing, and under the assumption of feature independence, Proposition further shows that it is supermodular. Given that Algorithm runs in polynomial time, this leads directly to an approximation guarantee of ((x((
In miniete" "a (4))
where kf ;= minie[ni
ee ( ((x)(()
oi ((t) 2 (0)
To show that this expression is both bounded and constant, we follow the same preprocessing step
as in Lemma 10 where we remove all redundant features from T- a process that, as previously explained, can be carried out in polynomial time for both neural networks and tree ensembles. As before, a feature is strictly redundant if and only if v(fi)) =(0) = 0. This preprocessing yields new function I' that behaves identically to f over the remaining features and ensures that, for every i, both uur ((i)) > O and ((t)) (0) > hold.
In order for to show that this expression is both bounded and constant, similarly to Lemma T0 we will perform the exact same preprocessing phase (which, as wel explained there, can be performed in polynomial time both for neural networks as well as tree ensembles) before where we remove all redundant features from f- We note that here too, it holds that a feature is strictly redundant if and only if o(fi)) v(0) = O. Hence, this preprocessing phase will give new function f' for which it both holds that it is equivalent to the behaviour of for all remaining feautres and also satisfies that for any i it holds that both ((t)) > 0 and aa ((1)) (0) 0 hold.
Now, following the same reasoning as in Lemma 10 where the probability term is lower bounded by I and its expected value by D we obtain that min (i) D and v ( (0) 2 D
This implies, as in Lemma 10 that the first term is lower bounded by O(I((D()) and for the second term we derive the following:
39

---

Published as a conference paper at ICLR 2026
Since "uutt is supermodular (Proposition Bp. have that oaur ([n) - 2 suff ((1z) {t}). It follows that
1 1 I Suut (mn)) U ([x] \\ {i)) - [D/2. This implies: 1 S minxe(m]
Van ((a)) (m])
san (())
<D] and
Sur ( - (0)
therefore, 1- 2 < V < O. This yields 1-k I [D|2, demonstrating that the overall approximation
1
bound based on the one established by Shi et al. is constant. While this bound may be significantly
smaller in practice, our goal here is simply to show that remains constant unlike in the local setting, where no bounded approximation is achievable.
Lemma 13. Unless PTIME=NP, there is no bounded approximation for computing a local cardinally minimal ò-sufficient reason for any x), even when [D]
Proof. The proof follows similar approach to Lemma 11 Suppose, for contradiction, that there exists a polynomial-tinn time algorithm that provides a bounded approximation a cardinally minimal local 8-sufficient reason for some (f, x). where f is either neural network tree ensemble- even when DJ = 1. Yet, Lemma 6 shows that even in the extreme case where the dataset consists of a single baseline Hence, the existence of such an approximation algorithm would contradict this hardness result, as would entail the ability to decide the existence of a sufficient reason.
O,, deciding whether sufficient reason exists is NP-hard unless PTIME NP.
M HARDNESS OF APPROXIMATING GLOBAL CONTRASTIVE REASONS FOR NEURAL NETWORKS USING EMPIRICAL DISTRIBUTIONS
Proposition 1. Assume neural network f F - [c] with ReLU activations, some dataset D,
such that is the empirical distribution defined over D, and some threshold 5 E Q. Then unless NP DTIME( (itoplooot) ), there does not exist a polynomial-tine O[n([D]) - c) approximation algorithu for computing a cardinally minimal global contrastive reason for f concerning for any fixed 0.
Proof. The proof proceeds via a polynomial-ting approximation-Poi prreiorvnnneeeiinggggg reduction from a specific variant Set Cover that is, similarly to regular Set Cover, provably hard approximate within the factor given in the proposition (Vazirani 2001).
Partial Set Cover:
Input: A universe U := fui..... Un ), a collection of sets := {Si,..... Sm such that for all j Sj C U, and coverage threshold 8 {0, 1,..,,.... n). Output:
minimum-sio subset C C S such that S 2
We reduce this problem to that of computing a global, ceddinallymmnnima contrastive reason for neural network f with respect to a distribution D defined over dataset D, and some threshold 8'. We begin by recalling the definition of global contrastive reason and then extend to the setting where the explanation is evaluated over an empirical dataset D. The definition is as follows:
E EADD Pr Pr + f(x) zg =xx]] 5.
(73)
More specifically, when we assume an empirical distribution over D, this implies that:
E Pr (f()) # (x) 7g =xg)]
Pr Pr (f(z) # f(x) zs xs)
D
XED
(74)
Σ ExeDg(ax) ((()))(())
D
(z(z,))
XED
where we denote (z(z,x) = : :3 Before doing so, specify the functional form that intend the constructed neural network f to
}3) We now construct a ReLU neural network f.
40

---

Published as a conference paper at ICLR 2026
implement. For each set S,, we introduce two vectors x and y², both belonging to Z" and drawn from the dataset D, such that they agree on all coordinates outside Sy; that is, they share identical feature values on the complement Sy. Formally:
(75)
and assign strictly different values the features in Sy by selecting them from two distinct vectors z and z' such that:
x = (X Eg
(x 233)
(y's, 25,,) =
(76)
We aim to construct f such that it satisfies the following:
f(x) = f sss
f(x's x25)) (1's;:z33)) f(y')
(77)
Let us now assume that both x and yd occur uniquely in the dataset D across all [n] coordinates that is, other vector in D matches either of them on any coordinate. Under this assumption, obtain the following relation:
Ex-D(PreNDfee f(x) 25, -xs,)
EvED,, (2.x) [((0))(0))
(78)
Sgj (z,x)
2D
D
XED
Here, the factor of 2 appearing in both the numerator and denominator arises from the fact that only two vector pairs (x))²) and (z², x²) contribute the respective sums.
We repeat this construction for each S; in the set-cover instance, each time choosing two distinct vectors x² and y that differ on every coordinate in [n]. In total, this yields 2m vectors that form the dataset D from which we construct f.
We then construct neural network that simulates this function. This is achieved using a known result on neural network memorization (Vardi et al. (2022), which guarantees that ReLU network capable of representing any finite set of onput-output pairs can be built in polynomial time. Using this result, construct f accordingly, and set 8' := [D]
We now argue that subset S, is global contrastive reason for f under tolerance 8' and only C' is partial set cover for U under tolerance 5. By Equation 78 each constructed pair of vectors (x', yd) contributes exactly [D] to the value term. Moreover, because each S, uses its own distinet pair of vectors in Z", there is no overlap between these pairs. Consequently, the coverage achieved by any cover C corresponds exactly the accumulated contribution of the selected subsets in the input domain of f. This completes the reduction.
N TRACTABILITY RESULTS FOR ORTHOGONAL DNFS
Lemma 14. If f is an orthogonal DNFs and the probability term vag can be computed in polynomial time given the distribution 'D (which holds for independent distributions, among others), then obtaining mubsee-mminmal global 8-sufficient reason can be obtained in polynomial time.
Proof. We begin by defining orthogonal DNFs (Crama & Hammer 2011 before presenting the full proof.
Definition 2 (Orthogonal DNFs). A Boolean function is in orthogonal disjunctive normal form (orthogonal DNF) (Crama & Hammer 201T) it a disjunction of terms T₁ T2 ... V Ty.. such that for every pair of distinct terms T, and T; 4 j):
TAT, 1
This means that no single variable assignment can satisfy more than simultaneously.
41

---

Published as a conference paper at ICLR 2026
The proof mirrors the argument used in Theorem | relying on the fact that Vaunt be computed in polynomial time for any set S.
For given set S, let C be the constraints that the term T. imposes on the variables in S. We enumerate all pairs of terms (T;, Any pair whose constraints on S are inconsistent (i.c.. Cr; Cr + I) is ignored, since it contributes zero to suff.
For each consistent pair of terms (Ti, Tj), we evaluate Pr(xs E C7 C,,T,) where CF,,T; C+, n n The contribution of this pair " is then
Pr(xs E CI,TT)) Pr(xg E Cf,)) Pr(xg E City.
Under feature independence, these probabilities factor as Pr(xs) = Ilies p(x:). Since there are at most m² such term pairs, the value u can be computed in polynomial time under an independent distribution D.
O DISCLOSURE: USAGE OF LLMS
An LLM was used exclusively a writing assistant refine grammar and typos and improve clarity. did not contribute to the generation of research ideas, study design, data analysis, or interpretation of results, all of which were carried out solely by the authors.
42


Reviews:
[{"review_id": "8iGw6plVkW", "reviewer": "Reviewer_qstK", "summary": "This paper proposes a unified framework for explanation complexity. Global value functions are monotone; under feature independence, sufficient variants are supermodular and contrastive variants submodular. This yeilds polynomial-time algorithms for subset-minimal global explanations and approximations for cardinality-minimal ones. Local explanations remain NP-hard.", "questions": "Could you clarify the candidate set specification in Algorithm 2?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The global versus local structural distinction appears to be new. Monotonicity holds without independence. Proofs are rigorous with counterexamples showing the necessity of assumptions.", "weaknesses": "Feature independence is required for approximation results. This limits practical applicability where features correlate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "g78DzolaTI", "reviewer": "Reviewer_uoPW", "summary": "The paper proposes a framework for unifying two types of explanations: contrastive and sufficient reason explanations. The framework models both explanations as minimisations of a value function.", "questions": "None", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Clear research question and contribution\n- A lot of novel (formal) insights are generated, which I consider to be valuable for the XAI community.", "weaknesses": "- Readability and accessibility can be improved. Most importantly, it looks to me that sufficient reasons are the same as semi-factual explanation, and global contrastive reasoning seems to describe goup/multi-instance counterfactuals. Since semi and counterfactuals are popular and widely used terms in the XAI community, I suggest clearly relating them to the concepts introduced and discussed in this paper. By this, the paper and its contribution will become accessible to a wider audience.\n\nMinor:\n- Line 232 \"smaller\" in XAI people often talk about \"simpler explanation\". I suggest clarifying the meaning of \"smaller\" and also including \"simpler\" to make the paper more accessible to other researchers", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "FK4gPZPLcV", "reviewer": "Reviewer_cPWT", "summary": "This paper presents new findings in the field of formal explainable artificial intelligence (XAI), focusing on the complexity of sufficient and contrastive explanations, including their probabilistic variants. The authors introduce a unified framework that covers both local and global explanations, providing insights into the complexity and approximability of subset-minimal and cardinality-minimal explanations.\n\nThe key takeaway from this study is that global probabilistic explanation problems differ significantly from local ones in terms of computational complexity and approximability. Specifically, the objective function for both sufficient and contrastive global probabilistic explanations is monotone increasing (Proposition 2). Additionally, when dealing with joint distributions, the objective function exhibits supermodularity for sufficient global probabilistic explanations (Proposition 3) and submodularity for contrastive global probabilistic explanations (Proposition 4). In contrast, local probabilistic explanations lack these properties.\n\nThe authors also focus on empirical distributions, where the objective function can be evaluated in polynomial time for various classifiers. They combine the aforementioned properties with standard greedy algorithms to reveal new results. Notably, subset-minimal global explanations can be computed efficiently for empirical distributions (Theorem 2), and cardinality-minimal global explanations are approximable (up to curvature and a logarithmic term) for empirical joint distributions (Theorems 3 and 4).", "questions": "------------------------------\n### Major Comments:\n------------------------------\n\n**C1**. As mentioned earlier, I found Algorithm 2 to be confusing. Typically, a greedy algorithm aims to maximize the marginal gain at each step, which is especially true for the greedy set-cover method. Therefore, unless I missed something, I believe that in Line 3, the `argmin` function should be replaced with an `argmax` function. Consequently, the comment in Line 428 should also be revised accordingly.\n\n**C2**. Essentially, the approximation factor for Theorem 3 consists of a logarithmic term (related to the number of data instances), while the approximation factor for Theorem 4 includes both a logarithmic term and a curvature term. Can we bound the curvature term? If not, the fourth contribution mentioned in the introduction (Lines 120-126) should be rephrased to reflect this.\n\n**C3**. In light of the previous comment, could the authors provide tight lower bounds for Theorems 3 and 4? Specifically, for large datasets, a bound of the form $\\log |D|$ in Theorem 3 seems quite loose. However, if the authors demonstrate that approximating the problem within a factor of $(1 - \\epsilon) \\ln |D|$ is NP-hard, this would strengthen the result. A similar observation applies to Theorem 4, given that the curvature can be significant.\n\n**C4**. In Theorems 2-4, the assumption regarding “empirical” distributions is reasonable; otherwise, the problem could be PP-hard. However, combining this assumption with the condition that $\\mathcal D$ is also a “joint” distribution appears unrealistic in practice. Do the authors envision practical scenarios where we need to globally explain a model trained on a dataset with samples drawn from a joint distribution? At present, I find this result to be primarily of theoretical interest, as I have not identified concrete applications for it.\n\n-----------------\n### Minor Comments:\n------------------\n\n**C5**. In Section 2 (Setting), I suggest introducing the main notation, including the input dimension ($n$), the number of classes ($c$), the underlying distribution ($\\mathcal D$), and the training set ($\\mathbf D$ or $\\mathbf Z$). Additionally, I would like to ask why you are using the subscript $p$ in $\\mathcal D_p$; I would recommend simply using $\\mathcal D$. Throughout the rest of the paper, I suggest maintaining consistent notation (for example, choose either P or PTIME, but not both).\n\n**C6**. Based on the proof provided, I believe that Theorem 1 applies not only to decision trees but also to orthogonal DNF formulas (i.e., \"1-satisfy\" DNF formulas). Given that there exists a Fully Polynomial Randomized Approximation Scheme for counting models of arbitrary DNF formulas, I am also curious whether we could find an approximation result for identifying minimal subset global explanations under the uniform distribution.\n\n**C7**. Section 8 is acceptable, but it could be more informative. I recommend including some key open questions that arise from this theoretical study. For instance, can we establish better approximation bounds for minimal-size global explanations when the classifier is a simple function, such as a decision tree or a linear threshold function?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "**S1.** Despite the paper's dense and technical nature, it is well-articulated: the notation is clear, and the results are easy to understand.\n \n**S2.** The related work is well-detailed, including most relevant references. \n\n**S3.** The unified framework that encompasses both local and global explanations, including probabilistic approaches, is intuitive. \n\n**S4.** To my knowledge, Propositions 2, 3, and 4 appear to be novel contributions. In most cases, the negative results are not straightforward.", "weaknesses": "**W1.** I find Algorithm 2 confusing, as it seems incorrect; the marginal gain should be maximized. \n\n**W2.** I think that the positive results presented in the main theorems (1-4) are primarily applications of existing findings. \n\n**W3.** Theorem 4 does not truly deliver a constant-factor approximation, as the curvature could be unbounded. \n\n**W4.** The upper bounds for Theorems 3 and 4 appear somewhat loose, and these approximation results lack lower bounds necessary to establish tightness. \n\n**W5.** Finally, the practicality of Theorems 3 and 4 is questionable, given that empirical “joint” distributions are rarely available in real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)