acceptodds
Under review as a conference paper at ICLR 2027

Local Sensitivity in Decision Tree Ensembles with Applications to Explainability and Monitoring

Abstract

Decision Tree Ensembles (DTE) are a popular model that are widely used in various sectors, such as, finance and health. The popularity of this model is essentially due to their inherent *explainability*. It is much easier to understand how a DTE is making decisions compared to most other ML models. We study the problem of how sensitive the prediction of a DTE is, with respect to a subset of its features. This problem has been studied in a *global* setting, where the objective is to find two data points that agree on a set of features, but have different classifications. In this article, we *local*-ize this problem. *Given a data point*, we check if it is possible to perturb this point to get another point having a different classification. We establish the precise computational hardness of deciding this problem. We then show that two well-studied problems, *explainability* and *monitorability* for DTEs, reduce to checking *local sensitivity*. We propose an algorithm for solving local sensitivity, thereby also solving explainability and monitorability. Our prototype implementation demonstrates our approach is competitive with respect to their dedicated tools.

Primary area:
interpretability and explainable AI
Keywords:
tree ensembles, local sensitivity, contrastive explanations, monitoring, mixed-integer linear programming, robustness verification, NP-completeness

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_8qFMOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies local sensitivity. Previous work defined global sensitivity which searches for sensitive pairs of inputs that differ only in a subset of features SS but receive a different prediction. This paper defines local sensitivity where one of the two inputs of a sensitive pair has its values fixed. The paper proves that this problem is difficult. Local sensitivity algorithms can be used for other tasks: contrastive explanations and robustness checking. The difference between the existing concept of robustness (Chen et al. 2019) is the limitation in the number of features that are modified.

Critical strengths

The paper studies an interesting and relevant problem. The complexity analyses provided in the paper are interesting.

Critical weaknesses

The introduced concepts are different from existing concepts (robustness, counterfactual explanations) only in minor details.

Similarly, the algorithms introduced in this paper (RegEnum and the MILP encoding) are minor adaptations of existing techniques (RegEnum: Martens et al. ICML'26, MILP: Varshney et al ICLR'26 (as cited in paper)).

The monitoring application does not mention the high (or exact) similarity to empirical robustness evaluation (eg. Kantchelian et al. 2016 and others). The link to the monitoring problem studied by Gupta et al. 2025 seems somewhat forced, maybe in an attempt to make the application seem more novel than it is.

Questions for authors
  • Adversarial examples are typically unrestricted in what features can be modified. Does the restriction of the feature set S make the problem easier? That is, could you take any existing adversarial example generator to find sensitive pairs by "fixing" the features not in S by pruning the decision trees?
  • For the contrastive explanations, the focus seems to be on finding the smallest subset of features S that all require a change of value in order to flip the prediction. As far as I understand, Local-Sens takes an S as input and you use an additional routine on top of Local-Sens to find this minimal S. Couldn't you use any other verification tool instead of local sense in that routine, and hence, isn't the subroutine the novelty here?
  • How is the monitoring problem of RQ3 different from robustness checking? And if it isn't different, why do you not compare to other robustness checking approaches?
1 comment

Q1. … could you take any existing adversarial example generator to find sensitive pairs …

We thank the reviewer for this suggestion. Local sensitivity indeed reduces to local robustness: fixing the features outside S to their values in v (equivalently, pruning the DTE with the box $Nbd_{S,\varepsilon}(v) $) yields a robustness query over the remaining features, and local robustness is the special case S = F. Restricting S does not make the problem easier in general: local sensitivity remains NP-complete and is W[1]-hard parameterized by |S| (Section 4), though it is in XP.

We will make it clear that the focus of our article was to establish the problem of local sensitivity and how it can help solve other relevant problems, in particular the problem of explainability.

Q2. … Couldn't you use any other verification tool instead of local sense in that routine …

A CXp is a subset-minimal set of features SS such that changing only the features in SS, can flip the prediction. This condition is exactly the definition of the ensemble being (0,S,∞)(0, S, \infty)-sensitive at vv (Lemma 7). Every query in the routine is therefore a local sensitivity query, and any verifier used as the oracle has to solve local sensitivity. This makes local sensitivity the natural primitive for computing CXps.

Q3. How is the monitoring problem of RQ3 different from robustness checking? …

In RQ3, we run the local sensitivity check on each input with varying all features. Local sensitivity is exactly ε\varepsilon-robustness (Lemma 1). What RQ3 compares is two ways of monitoring a stream of inputs. Any sound and complete robustness checker applied to each input would raise the same alarms as ours. RQ3 is about which violations can be detected, not about how fast a single check runs, so we compare against the monitor rather than against other robustness checkers. We will clarify this in the final version.

Reviewer_dTndOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper study local sensitivity in Decision Tree Ensembles, which ask if changing only small chosen group of features by small amount around one specific input can flip model prediction across decision boundary by given confidence gap. This problem is very important because it connect three verification tasks into one single framework: it generalize standard local robustness (where all features can change together), it directly find contrastive explanations in explainable AI (which look for smallest group of features that flip prediction when changed), and it allow white-box runtime monitoring to catch unstable predictions on one single query immediately, without waiting to see second similar input in data stream. On theory side, authors use graph clique reduction with depth-two trees to prove this problem is NP-complete and W1-hard with respect to number of changeable features, meaning fast scalable algorithm cannot exist when changeable feature group grow. They also prove this hardness boundary is exact, showing problem can be solved in polynomial time if number of changeable features is fixed constant, or if all trees in ensemble have only depth one.

For practical solving in their tool, authors propose two exact methods: region enumeration when few features change, and pruned Mixed-Integer Linear Programming (MILP) when many features change. Region enumeration lock all fixed features and use tree split thresholds to cut search space into small boxes where model prediction never change, so checking just one sample point inside each box give exact answer very fast for small feature groups. For large feature groups, authors adapt existing global sensitivity MILP—which normally need two copies of variables to search over two unknown inputs—into single-copy MILP by fixing reference input as known constant and pruning away all tree splits outside allowed feature subset and perturbation range. To find minimal contrastive explanations, they run this MILP once to find flipping example and then greedily reset features one by one, or ask MILP objective to directly minimize total number of changed features. In my view, theoretical novelty is high because of clean unification and nontrivial hardness proof, while algorithmic novelty is mostly smart engineering of known box-checking and MILP tree encodings; however, single-copy pruning trick is very effective in practice, running thirty to ninety times faster than baseline explainability solver XREASON and catching hundreds of runtime violations missed by black-box monitor CLEMONT.

Critical strengths
  • the paper's novelty is primarily theoretical and conceptual, lying in its unified formulation of local (g,S,ε)(g, \mathcal{S}, \varepsilon)-sensitivity across robustness, explainability, and runtime monitoring, alongside its W[1]\text{W}[1]-hardness proof and sharp complexity split between depth-1 and depth-2 trees.
  • the paper's core techniques are already well-known. However, their main breakthrough is realizing that keeping one input fixed allows them to cut the math in half and prune away unnecessary branches. This shortcut makes the tool extremely fast.
Critical weaknesses
  • the experiments do not evaluate interpretability from a qualitative, human-centric, or semantic standpoint. Instead, they treat interpretability strictly as a computational benchmark
  • In practice, REGENUM works exceptionally well when kk is very small (k=1k = 1 or 22), often outperforming MILP. However, as soon as kk approaches 55 to 1010, the number of interval hyper-rectangles explodes, causing REGENUM to time out on hundreds of instances. Users must abandon region-based checking and rely entirely on the MILP solver for higher-dimensional feature subsets, which is exponential in worst case
Questions for authors

N/A

3 comments

CW1: the experiments do not evaluate interpretability from a human-centric and semantic standpoint …

Thanks for this important question/comment. The idea of interpretability considered in this paper is indeed limited to what the literature calls contrastive explainability; i.e. a minimal set of features that can flip the prediction of a DTE classifier. This definition as well as other related computational definitions have been widely studied in the literature, e.g., [Ignatiev et al., 2020]; [Audemard et al., 2023]; [Izza et al., 2025] and also used by the tool XReason [Izza et al. 2026] that we compare against. In fact, researchers have also compared this computational notion to other statistical notions of explainability (like SHAP, Lime), e.g., [Silva & Huang 2024] and argued that contrastive explanations are a useful notion of interpretability. Our present submission contributes to this line of work, and hence we restricted ourselves to these computational benchmarks for our comparisons. However, evaluating this notion from a human-centric and semantic standpoint is a natural next step and an interesting direction that we would very much like to explore in the immediate future.

[Ignatiev et al., 2020] Alexey Ignatiev, Nina Narodytska, Nicholas Asher, and Joao Marques-Silva. From contrastive to abductive explanations and back again. In International Conference of the Italian Association for Artificial Intelligence, pp. 335–355. Springer, 2020.

[Audemard et al., 2023] Gilles Audemard, Jean-Marie Lagniez, Pierre Marquis, and Nicolas Szczepanski. Computing abductive explanations for boosted trees. In International Conference on Artificial Intelligence and Statistics, pp. 4699–4711. PMLR, 2023.

[Silva & Huang 2024] Joao Marques-Silva and Xuanxiang Huang. 2024. Explainability Is Not a Game. Commun. ACM 67, 7 (July 2024), 66–75. https://doi.org/10.1145/3635301

[Izza et al., 2025] Yacine Izza, Alexey Ignatiev, Sasha Rubin, Jo˜ao Marques-Silva, and Peter J. Stuckey. Most general explanations of tree ensembles. In IJCAI, pp. 5463–5471. ijcai.org, 2025.

[Izza et al., 2026] Yacine Izza, Alexey Ignatiev, Xuanxiang Huang, Peter J Stuckey, and Joao Marques-Silva. Rigorous explanations for tree ensembles. arXiv preprint arXiv:2603.29361, 2026.

Thank you for your response. I will keep my positive score.

Thank you so much for the positive score and for your feedback.

Reviewer_9ipYOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes a local sensitivity framework for decision tree ensembles, studying whether modifying a specified subset of features can change the prediction at a fixed input. The authors establish computational complexity results, develop enumeration- and MILP-based algorithms, and demonstrate the effectiveness to contrastive explanations and robustness monitoring using real world examples.

Critical strengths
  1. The paper studies an interesting problem connecting local sensitivity with robustness verification and contrastive explanations. It also provides theoretical results, including NP-completeness, W[1]-hardness.
  2. The empirical results show substantial runtime improvements over XReason, particularly for cardinality-minimum contrastive explanations, with competitive correctness results.
Critical weaknesses
  1. In Section 6 (Lines 352–357), the authors iteratively restore features of a fixed counterexample without re-optimizing the remaining features. However, the failure to preserve a prediction flip for a particular counterexample does not imply that no alternative counterexample exists using a smaller feature subset. Furthermore, Algorithm 1 (Lines 842–843) terminates after the first unsuccessful feature restoration. These issues raise concerns about the correctness of the subset-minimal explanations and the corresponding runtime comparisons.
  2. The independent algorithmic contribution of the MILP formulation is unclear. Since the proposed method is adapted from Varshney et al. (2026)[1], the authors should better distinguish the new algorithmic contributions.

Varshney, Namrita, et al. "Data-aware and scalable sensitivity analysis for decision tree ensembles." International Conference on Learning Representations. Vol. 2026. 2026.

Questions for authors
  1. Could the authors clarify where the substantial speedup over XReason comes from? Is it mainly due to the MILP formulation, differences in the solvers, the explanation extraction procedure, or other factors?
2 comments

We thank the reviewer for the careful review:

CW1: In Section 6 (Lines 352–357),… concerns about the correctness ...

We thank the reviewer for pointing this out. It seems that there was an oversight on our part in describing how we compute the subset-minimal set of sensitive features (Section 6, lines 352-357, Algorithm 1 in Appendix). While Algorithm 1 written in the appendix was unfortunately erroneous, it does not match our implementation, which was indeed correct. Hence, we did not need to re-run the algorithm and the results reported in the paper are all correct. What we actually implemented is the following: starting from the set FF of features on which vv and xx differ, we remove one feature from FF to obtain F’F’ and check whether the ensemble is (0,F’,∞)(0, F’,\infty)-sensitive at vv. If it is, we replace FF by F’F’. In either case, we process the next feature, so the overall algorithm does not terminate after the first unsuccessful removal. Since each check (after dropping one feature) searches for a new counterexample, rather than reusing xx, when the algorithm terminates without finding a sensitive pair, it is guaranteed that no sensitive pair (v,x’)(v,x’) exists in which x’x’ differs from vv only on the features in F’F’. Therefore, the final FF returned by the algorithm is indeed a subset-minimal CXp. We have attached the logs of our implementation, which show the calls we make to the MILP solver, together with one example annotated with the lines of the algorithm. In this example, the first call finds xx, which differs from vv on 16 features, and calls 2-18 test dropping these features one at a time. Call 9 returns Insensitive, and the procedure continues with calls 10-18, returning a CXp of two features after 18 calls. This shows that our algorithm does not terminate as soon as it cannot drop a feature. We have uploaded a revised version of the paper with the changes marked in blue. In the main text, we have updated the explanation of the algorithm, and in the appendix we have presented a cleaner and corrected pseudocode of the algorithm. As stated in the reproducibility statement, we will share our code upon acceptance.

CW2: independent algorithmic contribution …

The main contribution of the paper is the local sensitivity problem itself: its formulation, its complexity (NP-completeness, W[1]-hardness, an XP algorithm, and a polynomial-time case for stumps), and its use as an oracle for contrastive explanations and robustness monitoring. To solve it in practice, we adapt the encoding of Varshney et al. (2026) from global to local sensitivity. We fix one input to vv and allow the other to change only the features in SS, within distance ϵ\epsilon of vv. We also add an objective function that minimizes the number of changed features, which yields cardinality-minimum CXps in a single call. With only a sensitivity oracle, the obvious algorithm checks subsets of increasing size, which needs exponentially many oracle calls in the worst case, and XReason also needs many oracle calls. However, with our objective, the MILP solver performs this search internally, in one call. We believe this is part of the reason why we perform better.

Q1. …the substantial speedup over XReason comes from?…

We thank the reviewer for this question. The speedup comes mainly from the explanation extraction procedure, which requires far fewer oracle calls. Both tools use an oracle that answers the same question: can the prediction at vv flip when the features outside a given set are fixed? The difference lies in how many times this oracle is called. To illustrate this, we analyzed our previously run logs and we report the results in Table 3 in the uploaded revised version. Table 3 (App. B) reports the number of oracle calls per instance, averaged over the instances solved by both tools (max in parentheses). For subset-minimal CXps, our tool makes 7.6 calls on average (≤20\le 20), while XReason makes 61.6 (up to 1889). For cardinality-minimum CXps, our tool always makes exactly 2 calls, a witness search followed by a single MILP that minimizes the number of changed features, while XReason makes 56.8 on average (up to 705).

Table: Number of oracle calls per instance for computing CXps, averaged over the instances solved by both tools (maximum in parentheses). For cardinality-minimum CXps, the second call of local-sens is a single MILP call that minimises the number of changed features.

DatasetXReason, subset-minimallocal-sens, subset-minimalXReason, cardinality-minimumlocal-sens, cardinality-minimum
Breast-Cancer21.1 (68)6.1 (11)17.5 (67)2.0 (2)
Pima-Diabetes10.0 (18)4.9 (8)10.8 (27)2.0 (2)
Spambase255.7 (1889)13.5 (18)137.7 (705)2.0 (2)
adult71.9 (391)8.1 (18)87.7 (145)2.0 (2)
bank71.7 (368)9.9 (20)64.7 (93)2.0 (2)
churn54.5 (479)7.2 (18)28.5 (99)2.0 (2)

We hope the reviewer found the response adequate, in particularly in addressing the critical weaknesses, and the question regarding the speedup wrt XReason. If there are any further questions/concerns, we would be very happy to address them. Thanks again for the careful review!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.