Data-Aware and Scalable Sensitivity Analysis for Decision Tree Ensembles
Authors: Namrita Varshney
Ashutosh Gupta
Arhaan Ahmad
Tanay Vineet Tayal
S. Akshay
Venue: ICLR 2026 Poster (2026)
Keywords: Robustness verification
Sensitivity analysis
SAT solvers
efficient encodings
NP-hardness
fairness
confidence
decision tree ensembles
MultiClass
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Decision tree ensembles are widely used in critical domains, making robustness and sensitivity analysis essential to their trustworthiness. We study the feature sensitivity problem, which asks whether an ensemble is ``sensitive" to a specified subset of features - such as protected attributes- whose manipulation can alter model predictions. Existing approaches often yield examples of sensitivity that lie far from the training distribution, limiting their interpretability and practical value. We propose a data-aware sensitivity framework that constrains the sensitive examples to remain close to the dataset, thereby producing realistic and interpretable evidence of model weaknesses. To this end, we develop novel techniques for data-aware search using a combination of mixed-integer linear programming (MILP) and satisfibility modulo theories (SMT) encodings. Our contributions are fourfold. Firstly, we strengthen the NP-hardness result for sensitivity verification, showing it holds even for trees of depth 1. Secondly, we develop MILP-optimizations that significantly speed up sensitivity verification for single ensembles and for the first time can also handle multiclass tree ensembles. Thirdly we introduce a data-aware framework generating realistic examples near the training distribution. Finally, we conduct an extensive experimental evaluation on large tree ensembles, demonstrating scalability to ensembles with up to 800 trees of depth 8, achieving substantial improvements over the state of the art. This framework provides a practical foundation for analyzing the reliability and fairness of tree-based models in high-stakes applications.

Published as a conference paper at ICLR 2026
DATA-AWARE AND SCALABLE SENSITIVITY ANALY- SIS FOR DECISION TREE ENSEMBLES
Namrita Varshney, Ashutosh Gupta, Arhaan Ahmad, Tanay V. Tayal, & S. Akshay Department of Computer Science and Engineering. Indian Institute of Technology Bombay, Mumbai, India namrita wtt.eiitt.cc...m in, akgêcse litb.ac.ii in, arhaan awwaaammaaaaao 3003@gmal com,
arhaan.ahmad22
senaytayal@cse ii. akshayss@cse. wtwp:/essseeiitbaac.... acc..ac.tiiiiinii
ABSTRACT
Decision tree ensembles are widely used in critical domains, making robustness and sensitivity analysis essential to their trustworthiness. We study the feature sensitivity problem, which asks whether an ensemble is "sensitive" to speci- fied subset of features such as protected attributes- whose manipulation can alter model predictions. Existing approaches often yield examples of sensitivity that lie far from the training distribution, limiting their interpretability and practical value. We propose data-aware sensitivity framework that constrains the sensitive exam- ples to remain close to the dataset, thereby producing realistic and interpretable evidence of model weaknesses. To this end, develop novel techniques for data- aware search using combination of mixed-integer linear programming (MILP) and satisfiability modulo theories (SMT) encodings. Our contributions are four- fold. First, we strengthen the NP-hardness result for sensitivity verification. show- ing holds even for trees of depth 1. Second, we develop All.P-optinizations that significantly speed up sensitivity verification for single ensembles and, for the first time, can also handle multiclass tree ensembles. Third, we introduce a data-aware framework that generates realistic examples close to the training distribution. Fi- nally, we conduct an extensive experimental evaluation on large tree ensembles, demonstrating scalability to ensembles with up 800 trees of depth 8. achiev- ing substantial improvements over the state of the art. This framework provides a practical foundation for analyzing the reliability and fairness of tree-based models in high-stakes applications.
INTRODUCTION
Decision tree ensembles are a popular AI model, known for their simplicity, power, and interpretabil-
ity. They ubiquitous across multiple industries, ranging from banking (Chang al. 2018
Madaan et al. 2021) and healthcare (Ghiasi & Zendehboudi [2021] Kelarev et al. 2012) to wa- ter resources engineering (Niazkar et al. (0244) and telcoommunication (Shrestha & Shakya 2022). Given that this class of models forms a cornerstone for automated decision-making in various in- dustries, it is important be able trust their answers and provide guarantees on their reliability. Towards this goal, there has been significant research in the past decade on formalizing and verifying various safety properties of tree ensembles.
In this paper, we focus on one such problem: understanding the influence that a particular subset of input features can have on the output of decision tree classifier. This notion of sensitivity of the model to feature set has been studied in various contexts in previous works. It has been related to individual fairness and causal discrimination (Dwork al., 2011 Calzavara et al., 2022 Galhotra et al. [017]] Blockeel et al.) 2023). which are central to building responsible Al systems. A model is called sensitive to a specified set of features if the output of the model can changed by keeping every other feature the same and varying only the specified input features. Thus the problem of feature sensitivity verification (or simply sensitivity) is to check whether a given tree ensemble model E is sensitive to specified subset of features F C F. i.. whether there exist two inputs, called a (sensitive) counterexample pair that are identical on F \ F, but on which E gives different outputs. Knowledge of sensitivity specific subsets of input features is important for understanding

---

Published as a conference paper at ICLR 2026
3
3
Figure 1: Two counterexample pairs from a tree ensemble trained on MNIST. (Left) A counterexample pair where the left image is classified as 3 and the right as 8; but both are meaningless blobs. (Right) A pair closer to the training distribution. The left image is classified as 3 and the right as 8; where both resemble a 3, but the second is confidently misclassified, providing a more useful witness of sensitivity.
and mitigating attacks that aim to change model outputs by manipulating a small set of protected input features. This analysis can also help uncover unwanted patterns in the trained models that may arise from social biases in the training data.
Recently, Ahmad et al. (2025) showed that sensitivity verification is NP-hard for ensembles with trees of maximum depth at least 3, and gave a tool utilizing a pseudo-Boolean encoding to tackle the problem for binary classifiers. However, their NP-hardness proof (via 3-SAT reduction) does not extend to ensembles of trees with depth at most 1 or 2, leaving the hardness of the sensitivity problem open for such ensembles. Trees of depth also called decision stumps, have been long studied in the literature Wang et al. (2020); Horváth et al. (2022); Martinez-Muñoz et al. (2007) and are of interest in several applications Chen et al. (2023); Huynh et al. (2018).
A second, major challenge is that sensitive counterexample pairs may priori lie far from actual data points, providing only weak evidence of model's sensitivity. To see an illustrative example of this, consider Figure where a tree ensemble trained on MNIST with 786 features yields two counterexample pairs. In the left pair, the decision flips (3 to 8), but neither image likely appears in the training set, so this does not reveal model weakness. In contrast, the right pair is informative: the first image closely resembles a real training image (3) and is correctly classified, but modifying 20/786 features causes misclassification to 8 while remaining near the data distribution. Do similar cases occur when |F| = 1? They do, even in tabular datasets, as illustrated in Section C in the Appendix. This raises the question: to the real data distribution, enabling meaningful conclusions about model sensitivity? Such coun- terexamples are valuable for downstream tasks, such as retraining hardening the model, but in this work we focus solely on their identification, which is already a challenging problem.
identify sensitive counterexample pairs that are closer
We start by showing that the sensitivity problem is NP-hard even for ensembles of decision tree stumps (trees of depth 1) via a novel reduction from the subset-sum problem. Next, to find coun- terexample pairs closer to the data, we develop two complementary strategies one using a prod- uet of marginal distributions as an objective function and another constraint-soffe based approach where we avoid regions of sparsely populated data during the search. The pseudo-Booless approach of Ahhaa et al. 20025) is difficult to extend with such objective functions and hence we revisit a mixed integer Tinear program (MILP) approach for sensitivity verification. However, a baseline MILP implementation, based on the original encoding of Kantchelian et al. (2016) performs worse than the pscudo-Boolean optimizations to the MILP encoding that result in significant speed up, making it feasible to analyze large ensembles, while guiding the search toward meaningful counterexample pairs (i.e., close to the data distribution). We also show that our new MILP encoding can be extended to obtain to-the-best- of-our-knowledge the first tool for sensitivity verification over multiclass tree ensemble classifiers. Empirically, we demonstrate the effectiveness of our approach on ensembles trained using XGBoost (Chen & Guestrin, 2016), achieving an order of magnitude improvement in runtime compared to earlier methods, as well as higher quality counterexamples. measured by their proximity to the data distribution. Thus, our main contributions are:
Boolean method, highlighting the challenge of this approach. We introduce novel
We show that sensitivity verification is ha-hard even for ensembles of depth-1 trees.
2

---

Published as a conference paper at ICLR 2026
We significantly advance sensitivity verification by enabling discovery of counterexample pairs closer to the training distribution, through two complementary strategies: one using marginll objective, and another a novel constraint-solving based approach to compute clause summaries and prune data-sparse regions in the input space.
We design a MILP-based encoding with key novel optimizations for sensitivity verification, implemented via a combination of MILP and SMT solvers, and to the best of our knowl- edge are the first to extend sensitivity verification to multiclass decision tree ensembles.
We implement our approach in a tool ENSENSE and perform extensive experiments on 18 datasets and 36 tree ensembles for binary and multiclass settings. ENSENSE can verify tree ensembles with up to 800 trees of depth 8, significantly outperforming the state of the art.
Related Work. A closely related problem is local robustness, which involves finding adversarial perturbations that can cause misclassification. In the context of decision trees, this problem was originally defined in Kantchelian et al. (2016) who showed its NP-hardness and used an MILP en- coding to solve it. Since then, a rich line of work has emerged for robustness verification (Devos et all. 202 T, Chen et al. 2219aa Ranzato & Zanella 2020 Törbblom & Medjm-TTerrnnj [2019] Wang ct al. 2020). using different techniques, from suput-outpul mappings in Törnblom & Nadjm-Tehrani Tehrani
(2019) to abstract interpretation in Ranzato & Zanella (2020) to dynamic programming Wang et al.
(020) and clique- based approaches in the state-of-the
tool, VERITAS (Devos et al. (021). Most
recently, Devos et al. (2024) extended the last approach to local robustness verification for multiclass tree-ensembles. While specific ideas from robustness verification are useful for sensitivity verifica- tion (and we do build on some of them), the locality of the robustness problem allows mixture of simplifying optimizations given the knowledge of one input. In contrast, sensitivity verification involves a universal quantification over two inputs, making it more complex problem.
PRELIMINARIES
In a classification problem, we are given an input space X' C Rd defined over a d-dimensional feature space F, and an output space y = {0. L..... C- 1}. where C is the number of classes. We intend to learn the unknown mapping& & X - y. For any x E X', we will denote the value of feature f E F for x as z. A decision tree is recursively defined as either a leaf node or an internal node. Each leaf node n has a leaf value n.val, which is a scalar in R (for binary classification) or vector in RC (for multiclass classification). Each internal node consists of references to child nodes, decision trees n.yes and n.no, and a guard n.guard, which is a linear inequality of the form Xy < T. Here, f is a feature, Xy denotes the variable for feature f. and 7 is constant. An input I E X' is evaluated on the tree T by a top-down traversal. For each encountered internal node n, the guard of n, say n-guard the guard inequality evaluates to true, we move to n.yes; otherwise, we move to n.no. This process continues till we reach a leaf node n, and the output of the tree 7 (xxx) ) is given by n.val.
T is evaluated by substituting X +- x in the inequality. If
To increase the power of a single decision tree, it is common to use ensembling, where multiple decision trees are trained, and the outcomes are aggregated to reach final decision. Formally, a tree ensemble classifier E : X + y consists of a set T of decision trees. The output of the ensemble is found by aggregating the outputs of each decision tree. There are three notions of outputs from a tree ensemble: (i) graw(an (ar), which represents a linear aggregation of the outputs of the ensemble for class c, typically a sum over the outputs of all trees in the ensemble, (ii) (pro((z): the predicted class probability of class and (iii) the output label E(z) arg max, E gorob (I). In the binary classification setting, where y {0, 1}. each leaf node stores n.val E IR and Erao (a) =
ΣTET T(x), Crow (a) = Ero (x)), Eprot(x) = SIGMOID (g (x)). E gprob (a)) = gprob (c). where SIGMOID R + R is the sigmoid function defined as SIGMOID(z) = 1/(1+
For
convenience, glossary of the notation used throughout the paper is provided in Appendix A
FEATURE SENSITIVITY AND HARDNESS
In this section, we define the sensitivity verification problem and provide our improved hardness results. Given decision tree ensemble classifier &, our goal is to find two points (1()) and (2))) in the
3

---

Published as a conference paper at ICLR 2026
imput space X, such that they differ only in specified subset of features F C F and have the same values for all the remaining features, while producing different output labels when passed to the classifier, i.e., ((x(1) * E(x(2)). This problem becomes more significant if, not only are their out- put labels different, but the predicted class probabilities of the outputs are also far apart, indicating a change from a highly confident positive prediction to highly confident negative prediction.
Definition 3.1. Given a tree ensemble for binary classification & X' - {0, 13, a set of features F C F and parameter 9 2 0, & is said be (g. -'--ssiitveee if we can find two inputs 2²(2), x:(2) (called a countercxample pair) such that (a())) = (z())) and eTr (z(1) 2 0.5 + g and Eprob (x(?)) < 0.5 g. The sensitivity verification problem asks if given tree ensemble classifier is (g. (). seensitve.
In what follows, we often fix and refer to F-sensitivity; when F is clear from context, we simply write sensitivity. [Ahmad et al. (2025) showed that sensitivity is NP-Hard for tree ensembles with constant and = F. However, as noted by the authors, their reduction (from 3-SAT) does not work for depth 1 and 2. Our first result is to close this gap by showing NP-hardnesss at depth using novel reduction from the subset sum problem, a well-known
maximum depth 2 3 for [F] = F
NP-complete problem Garey & Johnson 1979).
Theorem 3.2. Sensitivity verification with |F| is NP-Hard for tree ensembles with depth 2 1.
Proof. Consider an instance of the integer subset sum problem, i.e., we are given a set of integers U and an integer k, and we want to find a subset U C M, such that ExeU = k. We call the gth integer u, where i varies from 0 to n na-1 1. For every index i, we create a Boolean feature ft. Then we create a decision tree of depth 1, which splits on fi, giving output 0 if ft is false and u, otherwise. We create another Boolean feature f' and a decision tree of depth 1, which splits on f', giving output k- 0.5 if f' is false and - + 0.5 otherwise. We call the ensemble of all these trees to be E: (0. 1 11=+t + {0,1) } with the trees being T, where é varies from 0 to n 1 and T', We claim that & is I-sesssseeeee iff there exists U C U such that Eiev = k. With this claim, the theorem immediately follows. A formal proof of the claim is given in Appendix B
We remark that when F/F] is bounded, we can solve the depth problem in polynomial time (see Appendix B This completes the complexity-theoret picture for the sensitivity problem.
4 DATA-AWARE SENSITIVITY VERIFICATION
Sensitivity, as defined in Definition 3.1 requires finding a counterexample pair showing sensitivity, but does not specify how close the inputs (.(1) and (2)) in the pair must be to real-world data. Indeed, this is not surprising, as the definition is itself independent of data (including training data), and only depends on the trained model. But, as consequence, counterexample pairs may include inputs that are arbitrarily far from the true data distribution, as illustrated Figure in the Introduction. Addi- tional examples are in Appendix C Our goal, therefore, is to find more meaningful counterexample pairs, towards which we extend Definition 3.1 with a utility function.
Definition 4.1. Given a (binary) tree ensemble classifier & X- f0, 1), set of sensitive features
F C F, gap parameter g 2 0 and a data distribution/utility function u : X' x X' that & is (g, F, -)-seniiive,, if there exist two inputs ,(1),,(0 X' such that 2 "F =ype (E(())) 2 0.5 + g. )) < 0.5 g and (1x("), (x))) is maximal among all such pairs.
+ [0, 1]. we say (1)
We could also add threshold parameter [0, 1] and require u(x (2)) 2 Typically, serves as a proxy for how similar (1)), 22(2) are to the training distribution. Given (possibly training) dataset DD we want the utility function u X' x X - [0. 1] to represent the likelihood of the input pair being drawn from close to D. In this work, we investigate two approaches to achieve this.
Utility Function. For simplicity, we first assume that all input features are independent. This allows us calculate the likelihood of each feature independently and then multiply the results. For a given feature f. consider the guards in the ensemble that involve f. Suppose a feature f appears in K₁ guards, with sorted thresholds Ty1 < ....< < TyK,, We assume that the X, takes value within range (Ty1, )y which ensure by introducing guards X < -00 and X, < xc. This partitions
4

---

Published as a conference paper at ICLR 2026
the space of feature ff into K intervals. We estimate the marginal probability of lying in each interval (T)(K-1): Tyk) ) by calculating the count of points in D for which f lies in [T)(--1): Tyx) and dividing this by the total count of points in D. That is, for any feature and real value we have,
( M E T/(--1 S Say < <
Tf (v(
[D]
And for any input (21, F2, Iy..... Id), assuming independence of features, we define TT T (21) T/a ...2)...TT,, (Id), where : X' + [0, 1] is the product distribution estimated from DD With this the utility function just becomes u(x()) ((2)) = (x(()) x(x(2)).
Intuitively, under the independence assumption, it measures how likely inputs are be drawn from the distribution D, guiding our approach to look for more meaningful counterexamples. In the next section, we show how this can be encoded effectively, and our experiments indicate that in many benchmarks it does give better counterexample pairs (i.e.. closer to data). However, its effectiveness diminishes datasets with high feature dependencies, which motivates an orthogonal approach.
Restricting search space using clause summaries. Our second approach attempts to com- pute summaries of the input space that describe cavities regions where no data points exist.
Our goal is ensure that these cavities are excluded from our sensitivity search. For simplicity, we focus on cavities represented as a bounded boxes in the input space. Given value of (a width parameter), we create the following template for points in D that fall in cavity:
ub
lb
A (X lb, A X,. < ub;)) VE[1,u]
(1)
lbj
ubj
fz
where each 1b, and ub; take values from one of the guards associated with feature fi appearing in the tree ensemble. In Figure we illustrate green cavity in 2-D space, where all the data points are projected in dimensions fi and fz. Therefore, we avoid finding sensitivity pairs in (Xy, 2 lb, X, < ub;) A (X,, 2 lb, A X,, < uby). The difficulty to find such cavities in the data set. For this, we observe that given a box which is conjunction of interval regions, its negation clause, in a form that can be processed by a constraint solver. Hence, our main idea is to find such cavities in the input data-set using a state-of-the-art Satisfiability Modulo Theories (SMT) solver De Moura & Bjørner (2008), as we detail in Section 5.3
Figure 2:
There are no training set data points within the green box.
AN IMPROVED MILP ENCODING
We build on the MILP encoding for decision trees introduced by Kantchelian al. (2016). The encoding, when used directly for sensitivity verification, is less efficient than the pseudo-Boolean approach as shown in Ahmad et al. (2025). However, we develop novel optimizations to the encoding for sensitivity analysis, which allow the MILP encoenng to outperform the pseudo-Booles encoding by a large margin, achieving an order-of of-mannitude runtime reduction compared to SENSPB.
Base Encoding. The encoding represents the decision tree ensemble set of linear inequalities. uses a set of binary variables Pyı to denote the predicates that appear on the internal node's guard true, and a set of continuous variables 0 < L, < 1 denote which leaf node is visited in each tree. The output of the tree ensemble is then computed as linear combination of the leaf values, weighted by the predicate variables. For each input feature ʃ. ensure consistency across the predicate
variables corresponding to the feature, since if T2, then X, < implies X, T2- Let the corresponding predicate variables be Pf1. Pf1.P/2...... PyK,, We require that Pʃ1 PfK, = 1. We encode this in MILP as Eq. (2)
Pr2 1,
Pf2 =1
Pf3 PJ( =
Pf1 P52 S PfK,
(2)
12 +IN=1
Let 4 1,.2.... IN be the leaf variables corresponding to a tree. We require two leaf consistency conditions. First, require that exactly one of these leaf variables is set to I and every other leaf variable is set to 0, which can be enforced as in Eq. (3). Second, we require that a leaf variable is set to 1, then every predicate variable in the path to the leaf node needs to be set such that the path
5

---

Published as a conference paper at ICLR 2026
is followed. For each internal node of rth tree, consider the set TSet of leaf nodes in the subtree rooted at n.yes and set Fet of the leaf nodes of subtree rooted at n.no. Let X < Tyk be the guard of node (recall that Xy refers to variables while z concrete input values). If n is root node, then we add the constraint given in Eq. (4), and for any non-root node, the constraint in Eq. (5)
Σ P1k REFSet
Σ L NETSet
(4)
Σ nEFt
2
Pfk
Σ I
(5)
neT
The constraints in Eq. to (5. are from Kantchelian problem, we create two instances of all the variables to encode the runs of the two differentiating inputs given to the tree ensemble. We will add superscripts indicate the copies. We need to ensure that the two inputs differ only in the specified set of features F S F.. For this, denoting by VE the set of all predicate variables such that their guards contain some f E F, we add the constraint in Eq. (6. Finally, for binary trees, Eprob > 0.5 + 9 + graw (x) > SIGMOID (anoorD~1(....0 (0.5 + g). Let us define = SIGMOID (0.5 + g). Because of the symmetry of SIGMOID about y = 0.5, we have that SIGMOID -1 "0..5 g) = -6. Thus. we introduce the constraint described in Eq. (Gap-bin) Recall that for leaf node n, n.val denotes its value. Let A be the set of all leaves in all trees.
(2166). To model the sensitivity
(1) Pfk V
= Pyk
(6)
Σ REA
n 1nn.vl 2 Sn Σ (2) n.val S - (Gap-bin)
nEA
Any feasible solution to these constraints corresponds two inputs x11) and 22 which differ only in the feature set F and produce outputs such that {(x(1)) 2 0.5 + 9 and ((r(2)) S 0.5
Optimizations the Encoding, We now deseribe the novel optimizations that we develop and prove their corrections. Subsequently, we will also explain how we incorporate data-awareness.
5.1 CONSTRAINTS ON UNAFFECTED AND AFFECTED LEAVES
For each leaf, we call the set of the guards in the path from the root to the leaf as the ancestry of that leaf. A leaf is called unaffected if, for each guard in the ancestry of the leaf, the guard predicate does not contain a feature from the set varying features. Let Ul denote the set of indices of all unaffected leaves. For each such leaf, we add a constraint on the two variables ( ((2) as defined in Eq. (UnAff). Intuitively, if leaf is reached be reached in the second. Adding this constraint explicitly helps the solver reach feasible solution faster, especially in cases where the sensitive feature only affects a small subset of the leaves. This is particularly important for features that are present in guards that are farther away from root nodes. In practice, large fraction of leaves belong to 24
run of the first input, then will also
Next, given that significant fraction of the leaves unaffected in practical scenarios, also add constraints to ensure that Leaf variables that are not in 2 (i.c., they correspond to "affected" leaves) capable of influencing the output. This is done by subtracting the two constraints in Eq. (Gap- bin) and using Eq. (Unff)) to remove any terms corresponding to unaffected leaves, leading to the constraints in Eq. bin This constraint has significantly fewer terms than Eq. (Gap-bin) while capturing its essence, leading to significantly faster running times.
A (12) Leu
(UnAff)
Σ L.
(100 (10) 1...nvaal 13) 22x (Aff-bin)
Crucially, as the following theorem shows (with Proof in Appendix D adding these optimizations does not change the set feasible solutions.
Theorem 5.1. Let C denote the MILP equation obtained as a conjunction of Equations 2 B.
6 and (Gap-bind. The set of feasible solutions of C and the MILP obtained by conjuncting with the constraints induced by Eq. (UnAf]) and Eq. Afff-bin are equal.

---

Published as a conference paper at ICLR 2026
5.2 OBJECTIVE FUNCTION
Modern MILP solvers are built to optimize over an objectíve function and are highly engineered with multiple heuristics traverse the search space while being mindful of the objective function. For our setting, we just need to find a single feasible solution to the set of constraints C as defined in Theorem 5.1 Among these constraints, Eq. (Gap-bin) captures the essence of the two outputs being different and reduces the set of feasible solutions by significant amount. We can utilize the objective function to amplify the importance of this constraint for the solver by adding a constraint in Eq. Obj-bin). capturing the difference between the two equations in Eq. (Gap-bin).
MAX Σ
(1 n. - 11.2
(Obj-bin)
REA
This addition leads to sigmificant improvement in running times, as the objective function can guide the MILP solver in choosing the better edge when faced with multiple candidates during the simplex- solving process instead of arbitrarily choosing between each of the available constraints. In Ap- pendix H. we present the full encoding of an illustrative example.
5.3 MODIFICATION IN MILP FOR AWARE SEARCH
Finally, we modify the MILP encoding solve data-aware sensitivity defined in Def. 4.1
Utility Function. Given the utility function as defined in Section we replace the objective function in Eq. (Obj-bin) by the following objective, which maximizes the value of the utility function:
MAX Σ /EFR=2
(log(T ( (T)(=)))) (og(=((71)))Mf + +
Importantly, we convert the product of marginals to log values, as MILP solvers only handle additive constraints on the objective function. The following lemma establishes the correctness of the data- aware objective function given in equation
Lemma 5.2. The objective function in maximizes ulx((1) 222)).
(1) Proof. Let Pyk be true for smallest k. Due to the consistency constraints, all Pj(tt) ....,,.................. Pyk, are (2)
true. Let Pyk be true for smallest k'. Therefore, the sum will reduce to Σrer ( + (og((z((T/K)) )). We may ignore the last term as it constant and we may replace Tf(k-1) by 25 because x [T TsR) and Tf(K-1) by of because x
(
(2)
(1)("1))>TT>)) Tykr). Therefore, the total sum will be Efer (og( (o))) (ag( (2)) Since the objective function is maximizing the sum, it is maximizing our utility function (1x(1), (2))
Computing clause summaries. Next we define constraints that can identify cavities in data and their negations, i.e., clauses that guide the sensitivity search. In Eq. ( we need to learn the features and their bounds. Let ray be a Boolean variable indicating f, f. and si indicating 1b; Tyk. and bi indicating ub; = Tyk, where Tyk is the k-th guard for feature f. For each & E D. we add:
(A Atw ((z, Tsk V 2 T(K)))
iE(1.a) FEF R.EEKK
To avoid redundancies, we enforce the ordering of features: i < S1 Sz. While solving the constraints to find a clause that satisfies all samples, we also add an objective function to guide towards learning tight clauses as: MIN (Ere(t,a)) (E! sit I!K K' tw)) where K mary (Ky) ). This ensures that select the smallest guard & for the lower bound of some feature and the largest guard K' for the upper bound of the feature. We iteratively compute one clause time and add constraints to exclude solutions corresponding previously computed clauses.

---

Published as a conference paper at ICLR 2026
Binary classifiers
Multi classifiers
SNO
ModelName
#Trees
Dep. #Feat.
SNO
ModelName
#Trees Dep. #Classes
breast_cancer wwwcccanncccrreeeee robust
10
4
5
10
1
covtype_robuss
100
6
10
diabetes robust
20
4
8
2
covtype unrobust
100
6
10
diabetes unrobust
20
5
8
3
fashion robust
100
6
10
ijenn robust
60
8
fashion unrobust
100
uunobbut
60
8
22
ori.mnist_robus.
100
10
adult
4.05
15
6
ori_mmist_unrobus
100
6
10
churn pimadiabetes (200,300,500
200,330,5000
21
7
Iris
100
1
(4.5)
Red-Wine
100
german
{500,800)
(4.5)
20
Table 1: Benchmark details. Binary models 1-6 are taken from Chen et al. (019h):
7-10 are
trained on UCI datasets Dua & Graff (2019) using all combination of #T'ress E [200. 300, 500)
and Depth {5, 6} (six configurations), Multiclass models 1-6 are from Chen al. (2019));
models 7-8 are trained on UCI datasets Dua & Graff (2019). Dep. refers to the average depth in the ensemble across all trees of the model.
Initially, we learn clauses of size one and progressively increase the size up to a user-defined limit. The computed clauses provide summary of D, capturing how the data is distributed across the input space and add the learned clauses to the constraints. Any solution to the query is required to satisfy these clauses, thereby making it more likely align with the data.
EXTENSION TO MULTI-CLASS TREE ENSEMBLES
We extend our formalism and encoding to the multi-class setting. Let y {0, 1...., ......C C- 1} denote the set of C classes in multiclass tree ensemble. The set of trees T is partitioned into C equal partitions, one for each class denoted by To, Ti....... Tc-1- The trees in a partition Te are one-vs- rest classifiers for the class c; that is, they consider class the positive class, and everything else combined as the negative class and train like binary classifier. Formally, graw (x) = ETET_ T(x), the softmax 1-C-1ect e"h, The output is the class with ensemble for multiclass classification & X' + {0, C. 1}, c()) c(?) E 10, 1.1...C--11. 1}. we find ((()),((3 E X such that ((x( c(1) A E(z(2)) c(2), We also extend the parameterized version of Def. 3.1 by requiring that the difference between probability of most and second most probable class is large:
and ggrab (x) SOFTMAX, (ET* (.)),..,, (s),..., E0. (z:), where SOFTMAX, R.C
function defined as SOFTMAX.(TO: ".l....c---,, = e />x=0)
the highest probability, i.e., Exx) Argmoncey&. Thus, given C-1).
F.g 2 0, two classes (1) (P)) V. & is (g. F, c()) ((8))ssensitiee if there exist x:(1) xx(2 such that )FFF = (x(2) de A c(2), (orob (x((1) 2 2g Egrob( and Vo c(2), eprot (z(2))
Definition 6.1. Given tree ensemble & X V
(2rob(2(22)
Now to extend our MILP encoding to the multiclass setting it turns out that we only need mod- ify Eq. Gap-bin), Eq. (Aff-bin) and Eq. (Obj-bin) (and its data-aware variant). We present the modifications and prove their correctness Appendix
EXPERIMENTS
We implement the MILP encoding from Section 5 with all structural optimizations and then add our two data-aware objectives tool called ENSENSE. We trained models with XGBoost v1.7. evaluate sensitivity using single CPU core per run with a per-instance 3600 seconds timeout. We use Gurobi Gurobi Optimization, LLC (2024) as the MILP solver. We focus on single-feature sensitivity; results varying multiple (viz., 2, 3, 4, and 5) features
presented in Appendix 7 We address the following research questions: RQ1: How does our MILP encoding with optimiza- tions fare against the baseline and state-of-the-art for (i) binary and (ii) multi-class classification?
8

---

Published as a conference paper at ICLR 2026
CNOORSE
186.94
time
327
102
221
Instances Salved
Instances Solved
(a) Binary classification
(b) Multiclass classification
Figure 3: Cactus plot comparing runtimes of single feature sensitivity for binary and multiclass.
2.02
None
Clause
Prob Probclause
pribeluse
0.57
0.306
0.26
0.17
Distance
3.25
Method
Win % Draw % Loss %
3.00
Clause None
80.5
3.2
16.1
Prob vs None
76.6
1.15
22.1
Prob vs Clause
56.6
1.1
42.1
Probclause vs None 86.7
1.1
12.1
0.25
Probclause Prob 56.4
15.3
28.1
Probelause vs Clause 72.7
1.7
25.5
200
400 60
800
2000
Instances Solved
Figure 4: In top-left, report the mean & distance of all instances for each method. In the bottom-left table, we report the win, draw, and loss rates for all pairwise method comparisons. On the right side, cactus plot of the distance (from the data to the counterexample found) across binary benchmarks. Instances are sorted by non data-aware baseline (none, orange, solid); for each position, distances Prob (red, dotted), Clause (green, dashed), and Probclause (blue, solid) are evaluated on same instance (no re-sorting). Lower curves indicate better quality.
RQ2: How does data-aware sensitivity perform in giving better quality counterexamples? How do we measure it, what do we compare against and how do each of our strategies help?
Binary Classification. To answer RQ1(i), compare the performance of ENSENSE against SENSPB the tool using secudo-Boolcan encoding from Ahmad et al.] (2025). and KANT, the base- line MILP encoding (adapted from Kantchelian al. (0016)). We mentioned in (left, with number trees ranging from 4 - 800, with depth from - 8. Con- sidering each single-feature variant as a separate instance and with gap (0.5, 1, 1.53 this yields total of 1,290 benchmark instances. Figure aa) reports results for the 1,103 instances whose run- time is 1s; we omit 187 instances solved in 1s for fair comparison, which demonstrates the superior performance of ENSENSE. ENSENSE achieves average speedups of approximately 8x over KANT and 5x over SENSPB, with no timeouts whereas SENSPB times out for 205 and KANT for 153 instances.
wide set of benchmarks
Multiclass Classification. For RQI(ii) we compare ENSENSE against the baseline MILP (still called KANT), as SENSPB does not handle multiclass ensembles. We also repurposed the versatile robustness verification tool VERITAS from Devos al. 2024) that can handle multiclass ensembles. to solve sensitivity. As it timed out on all except two instances, detail these results in Appendix F Table Tright) lists the multiclass benchmarks. For fashion and ori mimimsst, which have 784 features, restricted to single-feature sensitivity for the 100 most frequently used features in the model. For the others, we tested on all features, making a total of 538 benchmark instances. Our results in (b) where again dropped 17 instances which were solved in < sec. The results

---

Published as a conference paper at ICLR 2026
demonstrate that ENSENSE outperforms KANT by roughly 15x average speed up, and does not timeout on any of these benchmarks, whereas KANT times out on 256.
Data-Aware Sensitivity Verification. For RQ2. to evaluate data-aware sensitivity, compare (i) the bascline (no data-awareness) with (ii) the utilitt-based objective that steers solutions toward data-dense regions (called Prob), (iii) the clause-summary strategy that prunes Ma empty-data regions (called Clause), (iv) the combination of both (called Probclause), which ENSENSE uses.
To evaluate the performance of data-awareness sensitivity of each method, we compute the & dis- tance over insensitive features from the data to the nearest counterexample region identified. Given an input 2,, a counterexample region is connected subset of the input space containing x' such that: (i) the tree ensemble's prediction is constant throughout the region (all points fall into the same combination of leaves across all trees), and (ii) every point in the region has a label y with same probability (e.g., is misclassified). Intuitively, tree ensembles partition Rd into axis-aligned polytopes (one per joint leaf pattern); within each polytope, the model's output does not change. A counterexample region is one of these polytopes (or an intersection thereof with additional con- straints) that certifies whole set of violating inputs, not just a single adversarial point. We focus on regions rather than single point because if the nearest data point lies in the same counterexam- plc region, the correct distance is zero, whereas distance to any particular witness point inside that region can be nonzero and misleading.
Experiments are conducted on the same binary classification benchmarks (from Table with gap e 1, 1, 1.5). We used z:De Moura & Bjömer (2008) to synthesize clauses with maximum of 3 literals, with counterexample-guide each clause without reducing coverage. We also discard clauses that enclose an input point, and limit to 1500 synthesized clauses. Our results in Fig show that Utility-based vs. baseline: wins 76.65% of pairs (losses 22.19%. draws 1.15%), with mean distance advantage 0.435 on wins and mean deficit 0. 1 on losses. Clause- summary vs. baseline: wins 80.59% (losses 16.13% draws 3.26%), with mean advantage 0.34 (wins) and mean deficit 0.09 (losses). Combined (Probclause): strongest overall-wing winn 86.04% of pairs versus baseline, with mean advantage 0.47 on wins and mean deficit 0.06 on losses. In summary, our results show significant improvement in quality of counterexample pairs (measured by their E2 distance from data), with best results obtained by probclause used by ENSENSE.
refinement, followed by greedy literal-pruning to minimize
We also performed ablation studies on binary and multiclass ensembles to evaluate the contribution of the MILP optimizations, affected and unaffected constraints that we present in Appendix G.2 More experiments and technical details are given in the ArXiv version Varshney et al. (2026) and code is available at httpss//github..oo/orraaaa wtw.:/ormmmnrtttttt///eeeeeeetet
CONCLUSION
In this work, we defined a data-aware variant of the sensitivity problem on tree ensembles and devel- oped two approaches to solve this. We developed a new MII.P encoding with several improvements, that allows us to improve the quality of the sensitivity witness reported while at the same time pro- viding upto 5x speedup for binary classification over the existing methods and 15x for multiclass classification. One obvious direction for future work is to develop methods for training tree ensem- bles such that sensitivity can be reduced. This is analogous to the development of various tools for training decision trees that are hardened for local robustness. The other direction for future work is to go from identifying sensitive pairs to quantifying sensitive areas across the input space.
ACKNOWLEDGMENTS
We acknowledge the State Bank of India (SBI) Foundation Hub for Data Science & Analytics IIT Bombay for supporting the work done in this project. We thank Shri Shakeel Ahmed Agasimani, Deputy General Manager, Analytics Department, C Ramesh Chander, Assistant General Manager (Statistician), Muthukumaran M S, Chief Manager (Data Scientist), Komaragiri Srinivas Jagannath, Manager (Data Scientist). Neha Maheswari, Manager (Data Scientist), State Bank of India. for multiple wide-ranging discussions and feedback. We are grateful to Sunita Sarawagi for her valuable discussions and guidance throughout this work.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Arhaan Ahmad, Tanay Vineet Tayal, Ashutosh Gupta, and S. Akshay. Sensitivity verification for additive decision tree ensembles. The Thirteenth International Conference on Learning Rep- resentations, 2025. URL http:://ppperreee.e.mmm net hwt.://ooorriiccooooooommmm
Hendrik Blockeel, Laurens Devos, Benoît Frénay, Géraldin Nanfack, and Siegfried Ni- jssen. Decision trees: from efficient prediction to responsible ai. Frontiers in Artifi- cial Intelligence, 6, 2023. ISSN 2624-8212.
doi: 00.3399frrai.223.11245555 URL
https: www. www.::fftottiriinnnno.o.... jorrggjjourrar
a Brticlees/1.3333/ffaaaa....
Stefano Calzavara, Lorenzo Cazzaro, Claudio Lucchese, and Federico Mareuzzi. Explainable global faimess verification of tree-based classifiers. 2023 IEEE Conference on Secure and Trustworthy
Machine Learning (SaTML., pp. 1-17, 2022. URL. https://api.semmntiicc www.eettttcccoolle....
Yung-Chis Chia Chang. Kuci-Hu Chang, and Guan-Jhih Wu. Application of extreme gradient boost- ing trees in the construction of credit risk assessment models for financial institutions. Ap- plied Soft Computing, 73:914-920, 2018. ISSN 1568-4946. doi: http:///bi.org/11.011/////
2018.09.029 URL httpp///wwww.scceneeerrrr...ctt. htt.:/aaeeeeeeeecccococ///ceeeee 01568494618305488
Hongge Chen, Huan Zhang, Duane Boning, and Cho-Jui Hsieh. Robust decision trees against adver- sarial examples. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research. pp. 1122-112 131. PMLR, 09-15 Jun 2019a. URL https: htttps://proceedingg .ml....eeinnnmm................. mmrr.
2ress/v97/cee chem1 9m. html
Hongge Chen, Huan Zhang, Si Si, Yang Li, Duane S. Boning, and Cho-Jui Hsieh. Ro- bustness verification tree-based models. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Burs Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, cc/paper/21111/ htmll
pp. 12317-12328, 2019b. URL https::/
hash/ llsa:/ec5offaassooeeee2322211133
Jing Chen, Lianlian Wu, Kunhong Liu, Yong Xu, Song He, and Xiaochen Bo. EDST: a decision stump based ensemble algorithm for synergistic drug combination prediction. BMC Bioinform. 24(1):325, 2023. doi:
URL https: /ttttp:://cc.oooo http:///...oogo.....
$12859-023-054522
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 11. pp. 785-794, New York, NY, USA, 2016. ACM. ISBN 978 178-1-4500-4232-2 doi: 10.1145/ 9939977. URL URL/nttp://doo 210..
acm. 100 111111..1111221
Leonardo De Moura and Nikolaj Bjømner. 73: efficient smt solver. In Proceedings the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Con- struction and Analysis of Systems. TACAS 08/ETASS/ pp. 337-340, Berlin, Heidelberg, 2008. Springer-Verte ISBN 3540787992.
Laurens Devos, Wannes Meert, and Jesse Davis. Versatile verification of tree ensembles. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 Proceedings of Machine Learning Research, pp. 2654-2664. PMLR, 18-24 Jul 2021. URL http:hhttps:pooceeeeeeooo http://eeeeee..tm.m.o...es/////s
html
Laurens Devos, Lorenzo Cascioli, and Jesse Davis. Robustness verification of multi-class tree en- sembles. Proceedings of the AAAI Conference on Artificial Intelligence, 38(19):1019-21002, Mar. 2024, doi: 10. www96609aaaiii wwi.i..........0.0 330093. UtLhttpss:/ www.oosssaaa....... wwriii.rrg// wwtp/iddd..ioo../oo php/
AAAT att

---

Published as a conference paper at ICLR 2026
Dheeru Dua and Casey Graff. Uci machine learning repository. httpp::/arccive..ee edu//m 2019.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. CoRR, abs/1104.33 104.3913, 2011. URL httep::/arxii..or//bb//////
3913
Sainyam Galhotra, Yuriy Brun, and Alexandra Mcliou. Fairness testing: testing software for dis- crimination. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software En- gineering. ESEC/FSE 2017, Pp. 498 510, New York, NY, USA, 2017. Association for Com- puting Machinery. ISBN 9781450351058
doi: 10.1145/310623::10677777
URL https:
//doi. 1145/3106231 221110000237.311277
M. Garey and David Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7.
Mohammad M. Ghiasi and Sohrab Zendehboudi. Application of decision tree-based ensemble learning in the classification of breast cancer. Computers in Biology and Medicine, 128: 104089, 2021. ISSN 0010-4825, doi: 7/www,
104099 URLhttps
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https: gurobi com
Miklós Z. Horváth, Mark Niklas Müller, Marc Fischer, and Martin T. Vechev. (de- Jrandomized smoothing for decision stump ensembles. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.). Advances in Neural In- formation Processing Systems 35: Annual Conference on Neural Information Process- ing Systems 2022, NewrIPS 2022, New Orleans, IA, USA, November 28- December 9, 2022, 2022. URL http: /
/ttt:://papera wtwppsapppppppaa//paepppaa wttppp.cccppppp.pppppppppppppppp __rffffii___ fww.sflleeaae wttps//aappe//2///aaaaae
(30.3336007955252222 (01.799055555556922222522 7b4924 Abst Absttracccbbr Conference. html
Phuoc-Ha Hai Huynh, Van Hoa Nguyen, and Thanh-Nghi Do. Random ensemble oblique decision stumps for classifying gene expression data. In Proceedings the Ninth International Symposium on Information and Communication Technology. SolCT 2018, Danang City, Vietaa, December 06-07, 2018 pp. 137-144 ACM, 2018. doi: 10.1 (0.1145/3287921.33388 org/10. 11000.145550 328 921 3287987
URL WRR/https://dot
Alex Kantchelian, J. D. Tygar, and Anthony D. Joseph. Evasion and hardening of tree ensemble classifiers. In Maria-Florina Balcan and Kilian Q. Weinnerger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19- 24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 2387-23999 2396. JMLR.org, 2016. URL URL
mlr www.ppess/vvve. kank che iani6 6, html
Andrei V Kelarev, Andrew Stranieri, JL Yearwood, and Herbert F Jelinek. Empirical study of decision trees and ensemble classifiers for monitoring of diabetes patients in pervasive healthcare. In 2012 15th International Conference on Setwork-Based Information Systems, pp. 441-446, IEEE, 2012.
Mehul Madaan, Aniket Kumar, Chirag Keshri, Rachna Jain, and Precti Nagrath. Loan default pre- diction using decision trees and random forest: A comparative study. IOP Conference Series: Materials Science and Engineering, 102 1022(1)001042, jan 2021. doi: 10. 00.1088/17577-899X102222 1/012042. http:///ww//////.....///////////
Gonzalo Martínez-Muñoz Daniel Hermández-Lobato, and Alberto Suárez. Selection of decision stumps in bagging ensembles. In Joaquim Marques de Sá, Luís A. Alexandre, Wlodzislaw Duch, and Danilo P. Mandic (eds.), Artificial Neural Networks ICANN 2007, 17th International Con- ference, Porto, Portugal, September 9-13, 2007, Proceedings. Part I, volume 4668 of Lecture 32w.:311......nnneeee Springer, 2007. doi: 10071007777 000000-77---- 33.
Notes in Computer Science, pp. 319 328.
URL http:hppp//oooooooo//00000/////3
12

---

Published as a conference paper at ICLR 2026
Majid Niazkar, Andrea Menapace, Bruno Brentan, Reza Piraci, David Jimenez, Pranav Dhawan, and Maurizio Righetti. Applications of xgboost in water resources engineering: systematic literature review (dec 2018-mat may 2023). Environmental Modelling and Software, 174:105971, 2024. ISSN 1364-8152 122. doi: https:/ddo..org/lo...od.e..ssss.
URL https:// www. sci snceddiiiiiccccccccc rect. com sci http:///w.aaaaa...e..//////////a
Francesco Ranzato and Marco Zanella. Abstract interpretation of decision tree ensemble clas- sifiers. Proceedings of the AAAI Conference on Artificial Intelligence. 34004)5547--548, Apr. 2020. doi: 10. 5998
URL httph:t/://// /tttpp::/ooj..aa...... www.aaa.......ae...e/eaaaa phpp
Sagar Maan Shrestha and Aman Shakya. A customer churn prediction model using xgboost for the telecommunication industry nepal. Procedia Computer Science, 215:652-661, 2022. ISSN 1877-0509. doi: htts://doi.org/1O..
12.067 URL https: //wp:: sciencedirect. http:///caaaneeaat.a..e/////////
4th Interna- tional Conference on Innovative Data Communication Technology and Application.
John Törnblom and Simin Nadjm-Tehranii. An abstraction-refinement approach to formal verifi-
cation of tree ensembles. In Computer Safety, Reliability, and Security: SAFECOMP 2019 Workshops, ASSURE, DECSoS, SASSUR, STRIVE, and WAISE, Turku, Finland, September 10, 2019, Proceedings. pp. 301-313, Berlin, Heidelberg. 2019. Springer-Verllee ISBN 978-3- 030-26249-5. doi:
24. URL attps:://o. wtt.:ei..rr.1.100010111
978-3-030-26250-122
Namrita Varshney, Ashutosh Gupta, Arhaan Ahmad, Tanay V. Tayal, and S. Akshay. Data-aware and scalable sensitivity analysis for decision tree ensembles, 2026. URL https:
org/aba/ 2602. 07453
Yihan Wang, Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. On Ip-norm robustness of ensemble decision stumps and trees. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 10104-10114, PMLR, 2020. URL http: //procediing ngs. mlr. .press////ee.................e.e v919///// ww/p//ang00...... html
APPENDIX
The appendix is organized into 8 sections, in the order in which they occurred in the paper:
In Section
we provide a table of notation used throughout the paper for easy reference.
In Section
we provide Additional Proofs and theoretical results relevant to Section 3
In Section we provide data-aware sensitivity examples from Tabular Data as promised
in Section
In Section
we prove the correctness of our encoding optimizations from Section
In Section we describe the multi-class ensemble encoding into MILP that was left out of
Section 5 due to lack of space.
In Section F we describe the difficulty with using the VERITAS Devos al. 2024) frame- work for comparison and how we can encode our sensitivity problem in that framework and perform some comparisons.
In Section G we provide additional experimental setup details well additional exper- iments including:
(a) an ablation study for our encoding improvemennt/oppmizzatooos on binary and mul- ticlass tree ensembles
(b) a multi-feature sensitivity analysis.
In section H we provide an illustrative example of our encoding for a small decision tree ensemble.
13

---

Published as a conference paper at ICLR 2026
A
NOTATION TABLE
In this section, we provide a table of notation used throughout the paper for easy reference.
Symbol
Meaning
X
input space of the classifiers
y
output space of the classifiers
F
set of all features feature in F an input in X' value of feature / for input
x
Fy
decision tree node in decision tree leaf value Ieaf node n guard condition of internal node child node internal node n for true guard evaluation child node of internal node for false guard evaluation output of tree T on input x variable for feature
n.val
n.guard X <T
n.yes
T(x)
X5
T
set of decision trees in the ensemble
Te
set of decision trees in the ensemble for class decision tree ensemble
inputs to the ensemble
F
set of features to check sensitivity against minimum probability threshold for data-aware sensitivity utility function to maximize
9
D
training data samples
Tfk
threshold in the kth guard of feature f the number of guards for feature marginal probability function for feature f maximum size of the cavity constraints in Eq. lower bound on feature f, in the cavity constraints in Eq. upper bound feature fi in the cavity constraints in Eq
K
Ts
lb
ub;
Psk
Boolean variable for the truth value of kth guard of feature f Variable denoting leaf is visited.
4
Sigmod (0.5 g)
VF
set of all predicate variables for features in F set of all leaf nodes in the ensemble set of all unaffected leaves
A
4
Tft
Boolean variable to indicate that the feature in ith conjunct cavity is feature f
8ik
Boolean variable indicate that the ith conjunct of cavity uses kth guard of its feature lower bound
1,k
Boolean variable indicate that the ith conjunct of cavity uses kth guard of its feature upper bound
B ADDITIONAL PROOFS AND THEORETICAL RESULTS
Theorem B.1. The feature sensitivity problem with [F| is NP-Hard for tree ensembles with depth 2 1.
Proof. Consider an instance of the integer subset sum problem, i.e., we are given set of integers and an integer k, and we want to find a subset C U, such that EiEU k. We call the 4th integer u, where varies from 0 to 1. For every index we create Boolean feature ft. Then a decision tree of depth which splits on fi giving output if fa is false and u; otherwise. We create another Boolean feature f' and decision tree of depth which splits I' giving output -k 0.5
create
14

---

Published as a conference paper at ICLR 2026
if is false and -k + 0.5 otherwise. These trees are depicted in Figure 5 We call the ensemble of all these trees to be E {0, [0,1]=+1 1 + {0,1) with the trees being T; where varies from to n and T'
Claim. We claim that & is {ʃ" -eesiiivve iff there exists U Cu such that L k.
To see this, consider a function S {0, 1] - P(U) where P(U) denotes the power set of U
defined as S(x) fuz E Uf 1 for some E {0, ,,...,, 1}}. By construction of the trees,
E =0= (a(r)) where
[0,1)*+1 If is sensitive to [f"), then there exist a(1) and x²22) such that graw (z(!) 0 and gram (x(2) 0 and 2 Tif' where z refers to imput
(2)
projected into all features except f'. By construction, z'g' (1) 0 and sij'
(2) 1. Then (ra)(x(()))
2y +TT < 0 = E < = E < k+0.5. Similarly, = M k 0.5 0 = Eies(een > k 15-0. 0.5. Also, by construction of 5, ((x(1) = S(x since ,1(1) and x22) only differ on I' and S is independent of that value. Let ((x())) ) S(x(2) = U. Thus, k- - 0.5 < Eieul < k 0.5. As all
graw (z(2)) TT (z((2))
numbers are integers, Eigul k and thus there exists U l such that EiEUl k.
If there exists U C U such that Dieul = then consider (11) and (2)) such that 2; (1) = z; = 1ff
(2)
My U and si (1) x) (2) 0f uy & U where j, E (0, 1, 1,...,... nn 1} Also, Fy (1) and Tp =1.
(2)
Note (zx(2)) = ((x(²)) = U. Thus, E(x!1)) = Enn) (x)))) = k - k k 0.5 = 005 < <0
and (x) = Eles(nten) + (x())) = k - k + 0.5 = 0.5 > 0. Also L = I Thus, & is sensitive { as the above (1) and (2) are required pair of inputs show sensitivity.
Thus, by proving in both directions, we have shown if we can solve sensitivity for decision tree ensembles of depth- then we can solve integer subset sum problem. Thus, sensitivity is at least as hard as integer subset sum and thus it is NP-Hard for depth 1.
fi < 1
< 1
F
0
+ 0.5
A
0.5
Figure 5: Trees for Proof of Theorem B.I
Finally, we show that when |F/F| is bounded, we can solve the depth problem in polynomial time.
Theorem B.2. The feature sensitivity problem with bounded FF/F| solvable in polynomial time for tree ensembles with depth 1.
Proof. Given sensitivity problem with decision tree ensemble of trees of depth E (To, Ti Ti.... }. feature F, features for checking sensitivity against F and a scalar such that [F/F] < k, we solve the problem in polynomial time. Let [8] ie. there are total m decision trees and | n i. there a total of n features.
As each tree splits only 1 feature, we can create a set of trees corresponding to each feature. Thus, we create a function S(f) from the set of feature space to a subset of all trees. Note, it is a partition of all the trees each tree will split on exactly one feature.
For all f E F, consider the set S(f). We will calculate the minimum and maximum value of sum output of trees in S(f) and their corresponding features values. There total of [S(f) distinct possible values and thus can be found in ((m) time.
We will add the minimums and maximums found above and get global minimum and maximum value say m and M. We need to find whether there exists an assignment to features F/F such that the sum of output corresponding to trees of these features lies between - M and -m.
15

---

Published as a conference paper at ICLR 2026
For each feature f E F,F, the possible number of distinct outputs is [S()) + 1. Therefore, the total possible number of outputs are [[)fF//(S(f) + 1) which is 0(m*), Thus, by checking for all possible outputs, we can find whether such output exists or not. If does, then the ensemble is sensitive otherwise it isn't. Thus we have polynomial time algorithm h is not parameter but bound.
C DATA-AWARE SENSITIVITY EXAMPLES IN TABULAR DOMAINS
This section presents examples that demonstrate the effectiveness of incorporating data-awareness into sensitivity analysis, using models trained on tabular datasets. each case, we compare sensitive input pairs discovered with and without data-aware methods, showing how the inclusion of data distribution knowledge leads to more realistic counterexamples. Please note that the IJCNN model is trained by Chen et al.J (2019b), and the dataset for this model is unfortunately not available with the original feature names. The feature names are simply mentioned as to f22.
Sensitive Example of IJCCN Chen er al. (2079h): In the examples | and example 2 helow, we anal- yse the sensitivity with respect to features and 15 in the model trained on the IJCNN dataset. Both methods detect sensitive pair by varying only these features respectively, resulting in change in the model's prediction. However, the distance from the training data distribution reveals a clear differ- ence: The pair found without data-awareness has distance of 1 1.077 (077(exapple]] [T] and 1.06 (example 2). indicating it is quite far from any possible realistic data point and may not be very helpful in practice. In contrast, the pair identified with data-awareness has a distance of just (x32peex I and 0.34 (example 2), meaning it is much closer to the data distribution and training data.The in- sensitive features the training data points that are far away from the sensitive pair are highlighted with cyan color.
Sensitive Examples of Adult: based on Adult dataset Dua & Graff (2079) ): Here, we present the analysis of the 'adult' dataset in examples and this time examining the sensitivity of the features "age' and 'sex'. The non-data-award aware (baseline) method identifies the sensitive pairs with larger distances of 0.656 and 0.9899 for sensitive features 'age" and 'sex', respectively. The data-aware method, however, identifies pairs that are much closer to the data distances of 0.019 and 108. method reports 'age' value of 86, even though the
In example 4, the baseline(non-data- closest datapoint has an age of '40'. The data-aware method, however, identifies a pair with an age value of '46', very close to the nearest datapoint, which has an age of '45'. A similar pattern appears for capital-gane and capital-loss. The baseline values 10,585 (capital-gain) and 3,142 (capital-loss), while the nearest datapoint has values 0 and 2,258. The data-aware method, by comparison, identifies a pair where both features are 0, matching the nearest datapoint exactly. The insensitive features in the training data points that are far away from the sensitive pair are highlighted with cyan color.
selects a pair with
Sensistive Examples of Pimadiabetes:: (Dua Graff (209)): Finally, we present one more sensitive pair example, the Pima Diabetes dataset (with no categorical features), in example 5 and examine the sensitivity of feature ('BloodPressuree,, ). Again, the non-data-aware method identifies the sensi- tive pairs with larger distances of 0.35, where almost all feature values are far from the data which we show in cyan color). However, the data-aware method again identifies the pairs that are much closer to the data distances of 0.03, where only feature "Glucose" is far and the others are close. The examples clearly show that data-aware search finds sensitive pairs closer to the data.
D PROOF OF THEOREM 5.1 (CORRECTNESS OF OPTIMIZATIONS)
In this section, we prove Theorem 5.1 which says that our encoding optimiziations, that gave rise to significant improvement in performance, are sound.
Proof. We first prove that equation UnAff is already subsumed by equation equution 6 This established using a proof by contradiction. Assume to the contrary and let n E is such that (1) * (2) Since the leaf variables are forced to be either or 1 (by equation 4 assume without loss of generality that ((3) and (!2) 0.
16

---

Published as a conference paper at ICLR 2026
Example I: LICN ROBUST Chen et al. (2019b)
Sensitive Point Found Without Data-Awareness Analysis For Sensitive Feature
Pointl: ('f1'; 0.0, 'f2': 1.0, '33' 0.0, 'f4'; 0.0, f5'; : 1.0, '66;
1.0, 'f7': 0.0, 'f8': C.C, 'f9': 1.0, 'f10': 0.C, "f11': 0, 0,872834,
f12': 1.21062, 'f13': 0.637325, ff14 0.356398,
'f15': 0.482769, 1f19:: 0.607626,
f16': 0.390789, 'f17': 6.609402, 'f18': 0.558829,
f20': 0.696077, rf21': 0.448006,
0.61926)
Point2: : ('11': 0.0, '22': 'E2': '33': 1.0, ' 'E0'' 0.0, 125': 1.0, 'f6': 1.0, "17":000. 'f8': 0.0, 1, 'f1,'' 0.0,
'111": 0.872834, '115': 0.482769, 'f19'; 0.607626,
"12'; 1.210621, 'f13' 0.637325,
'f18': 0.558829, 'f20"; 0.696077, 'f21'; C.448006,
'f16': 0.390789,
'f17' 6.9402.
'f2''; 0.619263)
Distance from data: 1.07757866169
Nearest Training Datapoint: {'El': 0.0, '22': 1.0, 'f3': 0.0, '44' O.C, 'E5': 0.0, '66': 0.C, 'f7': 0.0, '58': 0.0, (e91:
0.0, ff10:: 0.0, 'fll': 0.540556, 'E12': 0.250375, 1513"
0.467001, 'f14"; 0.470297, 'f15': 0.570899, 'f16'; 0.527529, 'E17': 0.517118, 'f18'; 0.51931, '119': 0.51546, '220 : 0.55852, '221' 0.53037, '222" 0.528941
Sensitive Point Found With Data-Awaseness Analysis For Sensitive Feature 3
Pointl: ('fl'; 0.0, '22': 0.0, '33' 0.0, '44' : 0.0, '55': : 1.0, '66': 0.0, 'f7': 0.0, '28'; C.C, '99: 0.0, 'f10'; 0.0, 'f11': 0.678628,
'f15': 0.516459, f20': : 0.502477, "f21": 0.50531, (222"; : 0.5078613
f12': 0.541327, 'f13': 0.512386, 'f14': 0.516051,
f16': 0.497491, 'f17': 0.475932, '118" 0.495826,
'119': 0.459603,
Point2: (ffl': 0.0, 'f2': 0.0, (f3': 1 1.0, 'f4': 0.0, (f5': 1.0, '66':
0.0, (f7'; 0.0,
'f8': 0.C, ".9'; 0.0, 'f10'; 'f1''' 0.0,
'fll': 0.678628, '115": 0.516459, '119" 0.459603, "22"" 0.507861)
f12': 0.541327, 'E13': 0.512386, '214': 0.516051,
f16': 0.497491,
'E17': 0.475932, E20': : 0.502477,
'218" 0.495826,
0050:3.
Distance from data: 0.327039
Nearest Training Datapoint: ('fl'; 0.0, 'f2' 0.0, 'f3'; 0.0, 'f4' O.C,
'f': 1.0, 'f6': 0.0, 'f7': 0.0, '18': 0.0, 'f9' : 0.0, '210' 0.0, 'fll': 0.536865, 'f12':
0.250375, 'f13': 0.51317, 'f14': 0.50743, "f15': 0.526203, 1f16'
0.497706, 'f17': 0.484023, 'f18': 0.524588, (f19': 0.541842, "220": 0.467001, "E21": 0.470298, "E22" : 0.570898)
Example 1: JJCNN ROBUST Chen et 2019b)
17

---

Published as a conference paper at ICLR 2026
Example 2: LICN ROBUST Chen et al. (2019b)
Sensitive Point Found Without Data-Awareness Analysis For Sensitive Feature 15
Pointl: ('f1'; 0.0, 'f2'; 1.0, 'f3'; 1.0, 'f4': 0.0, 'f5': 1.0, 'f6':
1.0, 'f7': 0.0, 'f8': 0.C, 'f9': 0.0, 'f10': 1.0, 'f11': 0.822872,
f12': : 0.276149, 'f13': 0.448491, "f14'; 0.653076, 'f15':
0.64666, (f16'; 0.615426, 'f17': 0.35238, 'f18": 0.561026, ff19': 0.533231, 'f20": 1.199128, 'f21': 0.394238, 'f22': 0.558881)
Point2: ('f1': 0.0, '22': 1.0, '33': 1.0, '44': 0.0, '15': 1.0, '26':
1.0, 0.0, '28': 0.C, 'I9': 0.0, '#10': 1.0, '111': 0.822872, f12': : 0.276149, '513': 0.44849. '214'; 0.653076, '#15':
0.30856, 'f16'; 0.615426, 'f17': 0.35238, 'f18'; 0.561026, '119'; 0.533231, 'f20'; 1.199128, 'f21': 0.394238, '222;: 0.558881)
Distance from data 1.0647264749
Nearest Training Datapoint:: ('fl': 0.0, "22": 1.0, "33': 0.0, 'E4':
0.0, '55': 0.0, 'f6': 0.C, 'f7': 0.0, 'f8': 0.0, "E9': 0.0, rE10': 0.0, "fil'; 0.579145, 'f12": 0.18406, 'f13': 0.456363, 'E14':
0.543959, "f15'; 0.531502, 'f16': 0.449082, 'f17':
0.483391, ff18"; 0.520606, ff19"; 0.511848, #200: 0.527679,
'221'; 0.474918, '222" 0.477095}
Sensitive Point Found With Data-Awareness Analysis For Sensitive Feature 15
Pointl ('fl'; 0.0, '22': 1.0, 'f3': 0.0, '44': 0.0, 'f5': 0.0, '66':
0.0, 'f7: 0.0, '88' 0.C, '9': 0.0, '110'; 0.0, 'f11': 0.797221,
f12': 0.341174, 'f13'; 0.540222, 'f14'; 0.380818,
'f15':
1.168992, 'f16'; 0.457969, 'f17': 0.368609, 'f10'; 0.457974, '119' 0.527069, 1f20" 0.399163, 'f21': 0.367169, 'f22'; 0.501212)
Point2 ('fl': 0.0, 1f2':110 (f3'; 0.0, 'f4': 0.0,
'f5': 0.0, rf6':
0.0, 0.0, f12': 0.341174, 0.412158, 'f16'; 0.457969, '$17': 0.368609, 'f18"; 0.457974, 'E19' 0.527069, 120': 0.399163,
'88'; 0.C, 'f9': 0.0, :f10'; 0.0,
'fll": 0.797221,
'113' 0154:
"214': 0.380818,
'115":
'221': 0.367169, '22': 0.5012121
Distance from data 0.3449
Nearest Training Datapoint:: ('fl'; 0.0, '22': 1.0, 'f3'; 0.0, 'f4': 0.0, 'f5': 0.0, 'f6'; C.C, 'f7'; 0.0, 'f8' 0.0, 'f9'; 0.0, 'f10':
0.0, <fll<; 0.579295, 'f12': 0.16411, 'f13's 0.44351, 'E14': 0.45535, rf15f: 0.542591, (f16': 0.301968, 1117: 0.500353, "f18r: 0.5093, "E19": 0.495474, '220" 0.515701, (f21"; 0.511422, "f22" 0.517442)
Example 2: JJCNN ROBUST Chen et 2019h)
18

---

Published as a conference paper at ICLR 2026
Example 3: Dua & Grafi (201)
Sensitive Point Found Without Data-Awareness Analysis For Sensitive Feature 'age'
Pointl: l'age' :66, 'workelass;;
'Never-worked', 'fnlwgt': 574792.14018, 'education': 'Some=college', 'education-num" 16, 'marital-status' 'Widowed', 'occupation's "Dransport-movingg o ''eeatiooshipp'. Unmarried', 'race': 'White', 'sex 'Male', 'capital-gain'; 10585, capital-loss': 2309, "hours-per-wee''' 92, 'native-countzy'. 'Foland ")
Point2: l'age' :86, 'workclass'; 'Never-worked', "Iniwgt': : 574792. 'education on'; 'Some-college! 'education-nin 'Widowed', 'occupation': "mransport-moving" 'relationship'' Unmarried', 'race': 'White', 'sex'; MMale', 'capital-gain's 10585, capital-loss' 2309, "hours-per-week 92, 'rative-country' 'Poland
16, 'marical-status':
Distance from data 0.6569890
Nearest Training Datapoint: ('age' 32, 'workclass'; 'Pzivate', 'fnlwgt': 226975, 'oducation': "oome-colloge' 'education-num"
10, 'marital-status' "Nover-marridd' 'occupation': 'Sales', 'relationship':
Own-child', 'race' 'Wite'' 'sex' "Male', 'capital-gain' 0, capital-loss': 1876, hours--prr 60, nattive-country'. UnittedSttttes
Sensitive Point Found With Data-Awareness Analysis For Sensitive Feature 'age'
Pointl: ('age': 46, 'workclass'; 'Sclf-omp-ine', 'fniwgt:;
080532.5437,, 'education': 'Doctorate', 'education-num' 13.500002, 'marital-status" "Married-civ-spousee, 'occupation': "Exec- managerial', 'relationship': / 'Huaband', 'race' 'Black', 'sex' Female', 'capital-gain's 0 'capital-loss" 0, 'hours-per-wekk' 40, 'native-countzyy' "Fuerto-Rico',,
Point2: a'age': 33, workclass' 'Selt-emp-inc', 'fnixgt':
180532.54372, 'education': 'Doctorate', 'dducation-num' 13.500002,
'marital-status': "Married-eiv--pouse" 'ocoupation'; 'exec- managerial', 'relationship': Husbandd' 'race': 'Black', 'sex': Female', 'capital-gain's 0, 'capital-loss' 0, 'hours-per-weds 40, 'native-countzy"' : 'Puerto-Rico'!
Distance from data 0.0191765741
Nearest Training DataPoint: ('age'; 44, 'workclsss;; (Frivate', 'fnlwgt': 211759, 'oducation': 'Bachelors', 'dducation-num' 13, marital-status's "Marricd-clv-gpuuee' 'occupation': "Exec- managerial', 'relationship' (Husband', 'race' 'Other', 'sex' (Male', tcapital-gain's C, "alpital-los: 0, "hours-per-weekk 40, 'native-country' P
Example 3: Adult Dua & Graff 2019
19

---

Published as a conference paper at ICLR 2026
Example 4: Dua & Graff (2019)
Sensitive Point Found Without Data-Awareness Analysis For Sensitive Feature 'sex'
Pointl: ('age': 86, 'workclass': 'Without-pay', 'fnlwg''
"education' 'HS-grad', 'education-nun': 16.0, 'marital-status:; Never-married', 'occupation's : "rrangport-movingg, 'rclationship's Unmarricd', 'race'; Amee=-nndaan-sskino 'sex': 'Female', 'capital-gain' 10585, 'capital-loss's 3142, "hours-per- week' 99, 'native-courtry'' (Laos'),
Point2: ('age': 86, 'workclass': "wi Wwithout-pay', 'fnlwgt': 520260. 329277, 'educatí on'; 'HS-grad', 'educationnnum' 16.0, Never-marzied', "occupation': "Transport-movingg, 'relationship' Unmarried', 'race': "Amer-indian 'Male', 'capital-gain': 10585, "capital-loss': 3142, "hours-per-wesk ': 99, 'native-country:: 'Lare' LLaos")
'sex'
Distance from data: 0.98998791099
Nearest Training Datapoint: { 'age'; 40, 'workelass';
'Private', 'fnlwgt': 287983, 'education': BBachelors', 'education-num':
13, 'marital-status': 'Never-married' 'occupation' 'Tech-support', 'relationship': NNo--inffamll', 'race'; 'Asian-Pac-Islande" 'sex' 'Female', 'capital-gain's 0, 'capital-loss' 2258, "houss-per-week" 48, 'native-countzy: "philippines'
Sensitive Point Found With Data-Awareness Analysis For Sensitive Feature 'sex'
Pointl: 46, 'workclass'; 'Self-emp-ine', 'fniwgt': 284508. 95444, 'education': 'Doctorate', 'education-num'' 13, 'maritalsstatus: Married-civ-goouse, 'ocoupation': 'Craft-repair', 'relationship Husband', 'race': 'Black', 'sex':
"Male', 'capital-gain's C, 'capital-loss': 0, /hours-per-weekk, 50, 'native-country'. 'France'),
Point2: ('age": 46, 'workelass' 'Self-emp-ine' fningt':
0845088954445 'education': 'Doctorate', 'education-num's 13, marital-status', "Married-ctv-spouaa', 'occupation': 'Craît-repie 'Crašt-repair', 'relationship's 'Husband', 'race"; 'Black', 'sex': "Female', 'capital-gain': / 'capital-loss'; 0, 'hours-per-week's 50, naativeccoutzyy: 'France')
Distance from data: 0. 0.1081739837784343
Nearest Training Datapoint: ('age' 45, 'workclass';
'Private', 'fnlwgt' 238567, 'education': 'Bachelors', 'education-
num': 13, 'marital-status's Marriied-civ-spossed 'occupation's
"Exec-managezial", 'relationship' 'Husband', 'race': 'White', sex
': 'Male', 'capital-gain's 0, 'capital-Loss' 0, 'hours-per-weed
40, "native-countzy' "England"
Example 4: Adult Dua & Graff 2019
20

---

Published as a conference paper at ICLR 2026
Example 5: Pimadiabetes Dua Graff (2019)
Sensitive Point Found Without Awaa-nwssesess Analysis For Sensitive Feature 2
Pointl: ('Pregnancies': 17, 'Glucose': 188, "BloodPressure',
122, 'skinThickness' 33, 'Insulin's 846, 'BMI'; 67.1,
2.42, 'Age' 81), Point2: I'Pregnancics"; 17.0, 'Glucose's : 188, 'BloodPressure's
tiabetesPaalproctnntttto""
76, "Skinfhickness'' 33, Insulin': 846, 'AMI': 67.1, perbattesPddigeeennntttiitt
2.42, 'Age': 81)
Distance from data: 0.3534358888
Nearest Training Datapoint: l'Pregnancies': 10, 'Glucose'; 148, 'BloodPressure' 84, Skinnhhickness' : 48, 'Insulin' 237, PXI' 37.6, DiabettsseedggeeePaaattonn 1.001, 'Age' 511
Sensitive Point Found With Data-Awareness Analysis For Sensitive Feature 2
Point 1: ['PPregnancies': 2e-06, "Glucose': 139, 'BloodPressure' :70, SkinThickness's : 0, 'Insulin':
"BMI': 32.75,
Diabpteeseddippeenntttii
0.3595, 'Age': 211
Point2: I I'Eregnancies': 2e-06, 'Glucose': 139, 'EloodPressuze' :79, skinthickness': 0, 'Insulin': 0, 'BMI'; 32.75, piabetesPddigreeinnttioo Distance from data: 0.03051399
0.959,, 'Age': 21}
Nearest Training Datapoint: ("Pregnancies': 0, 'Glucose':
132, "BloodPressure' 78, "SkinThickness" 0, 'Insulin': 0, 'BMI': 0.393, 'Age' 21)
32.4, Diabeteeseediggeeeuueete
Example 5: Pimadiabetes Dua & Grafi (2019)
By equation 3. there exists leaf n' such that ((2) 1 and the leaves n and n' belong to the same tree. Let n² be the last common node in the paths from the root leaves and n', respectively. Let n" be labeled with with X, Tk and Pyk be the corresponding predicate. Since n" the ancestry (1) (2) of n' and E U, have that Pfk Pyk (by equation 6).
Without loss of generality, assume that leaf is present the subtree rooted n .no, while leaf n' (1)
present in the one rooted at n" -ees. Since r(() = 1, equation implies that
p
Pjk = 0. At the same time, since (2) 1, equation implies that Pfk 2
pfk = 1 Pjk
leading to a contradiction. Hence, (1) (22 Vi E U is implied by equation 2 eqquation the set of feasible solutions does not change on the addition of equation UnAff
6 and hence
As mentioned earlier, we show that equation UnAff and equation Gap-bin together imply equa- tion
Aff-binn Subtracting the two incqualities in equation Gap-bin we get that when equation Gap-
bin holds, then Σ
((1) n.val - (2) n.val 2 2
However, for the leaves belonging U, the difference terms
by definition, i.e.
Eneu ((") ( n.all = Using these two equations we conclude that if equation Un-
Aff holds and equation Gap-bin holds, then we must have Engu ((1) n.val 1 n.val 2 2 x 6, which completes the proof.
E MILP ENCODING FOR MULTICLASS SENSITIVITY
In the main paper, we had extended the Sensitivity problem from binary to multiclass classification. Here we provide the details regarding how we extend the MILP encoding tackle the multiclass setting. We observe that for the (g. F, -. equation Gin-bin, equation Aff- bin and equation [Obj-bin need to be modified. We now describe these changes. Let L. denote the indices of the leaf variables corresponding to the trees of class
problem for multiclass ensemble, only
21

---

Published as a conference paper at ICLR 2026
The change in equation Gap-bin follows from Definition 6.1
To encode that
Ve o c(4) (00)) g 2 g Egrob (x instead move the space of &Row, i.e. the
values before applying SOFTMAX. Given the definition of SOFTMAX,
Eorob e(t)
(z(1)) 2 g x Eorob (x(1)
EXP (x(1))
Ex Cra (a(11))
Σ Exp(Eram (x)(( (x(11)) 2 29 X
Σ Exxp(E Eroww (s:(1))
(x))))
Eay (x(1) El (x(1)) Ing
We call In g as 77, to get the new gap constraints
A
Σ
n.val
Σ LnELe
n. + +]
(gell) I.E..
(Gap-multi)
Σ
11)) n.val
Σ L.E
of n. +
egfet L.C.
With this new constraint gap constraint, we can arrive at a constraint for the affected leaves, sim- ilar to equation Aff-bin by adding the two constraints in equation Gap-multi and using reasoning analogous to that the binary classification setting.
Σ 100 ngu
( n.vva - 1..nl
Σ
( n.val - 100 n.val) > 2 x n (Aff-multi)
+
1,2, ng 1
An objective function can be formulated as before:
MAX Σ (1 - -.122) +
Σ L.C,,
( - 1111 (.'nnval)
(Obj-multi)
Theorem E.1. The set of feasible solutions of the MILP defined by equation 2
A equation 3 ^
equation A equation 5 equation 6 A equation Gap multi and that of the MILP defined by
adding equation Aff multi are equal.
The only difficult part in the proof is to see how we obtain equation equationAAf--mn Aff-multi Let us choose c c(2)
the first half and = c(1) in the second half in equation Gap-multi
We obtain
Σ
n.val >
Σ
(1) n.vall +
L, 1.
(8)
Σ
(2)) n.vall
Σ
122) n.val +
1. (22)
In En
Add the two equations
Σ (1()) - (2) y. +
Σ (112) - -10 > 2m
L.C
Since for the unaffected leafs ((1) ((2) is zero. We derive the desired equation.
Σ
nn.al 12)
Σ
(2) 1.).v (( n....aa)) x
(Aff-multi)
L.EC (3) ngll
LEE .2))
22

---

if c (2) Published as a conference paper at ICLR 2026
F COMPARISON WITH VERITAS
One of the comments that we left in the main paper was the comparison or lack there-of with the tool VERITAS, versatile tool for robustness verification of decision tree ensembles, for which there a multi-class variant available. this section, we explain why we cannot easily compare with that tool and also how it can be modified that we can compare it. Firstly, VERITAS does not solve the problem directly as it is not designed for sensitivity. So as the first step, we modified the tool enable the multiclass sensitivity analysis. Note that VERITAS is more generalizable tool and we approach the problem differently. To encode the multiclass feature sensitivity problem in VERITAS, we create two instances of given tree ensemble and optimize the following objective:
MAX (Do(x(1)
MMXX.. (e(x(1) ,0())))))
(10)
where D is defined as follows:
c(a) (x) ) g (x(2)),
if 0
Eg Egaw (x))) Eg Egow (2)2).
if (1)
Dc(x()),
Ela (w (1) + graw (x(2)),
e(l)
gxow (x(() (x) + grow (x(22),
otherwise
We define the objective value found by VERITAS being "better than" ENSENSE if the output of VERITAS is greater than 2 x 17.
Here we provide the proof of correctness of this comparison.
From the equation Gap-multi
conclude:
graw (2) MAX C grow (x) (g0))
((0)211 2
(11)
gray (2)) MAX C. Erow
grow (x)22) 2
(12)
(13)
Ideally we would like to maximize the sum of LHS of the above equations. We will prove that objective is an upper bound for the output described above.
Claim. For all (1))) and xx(2) Da(x ,x)))) MAX (D)((( (2(1)) > graw (z
MAX MAX graw (z:11) graw (x(2)) MAX Co graur (z!2)).
As MaX(a, S MAX(a) + MAX(b), MAX (D( (Dc (o(2)) S MAX Erou (z) +
MAX cestet) (xa Thus negating and adding Do (2(1)) to both sides, we arrive at our claim. Hence our claim true.
As our claim is true for all (1) and (2) and Vzf(z) 2 g(z) = MAXx( (()))
our objective is an upper bound over the ideal objective.
Thus, we can safely say if VERITAS outputs a value less than 2 r) or it timeouts, while our tool gives a sat output, our tool is better than VERITAS. If our tool gives sat but VERITAS provides a higher output, we deem VERITAS to be better. our tool gives unsat, then we ignore that instance.
We give VERITAS 1200 seconds to run for each experiment and compare with the best output found till then. For all other tools, we compare time taken for them to find a satisfying pair of examples. The results of the experiments are given in Table The Veritas algorithm finds progressively larger and larger gaps. %V indicates the amount of "gap" found by Veritas during the given time as compared ENSENSE. For instance, consider the Iris where we report 2%, which implies that the gap found by ENSENSEis 50 times bigger than the gap found by Veritas.
G ADDITIONAL EXPERIMENTS AND DETAILS
In this section, we provide more details regarding how we trained the models, how performed our experiments, and also present additional experimental results. We then explain the counterexample region that is used to evaluate the distances from data. Then we do ablation study to understand the impact of each improvement both in binary and multiclass tree ensembles. Finally, we show what happens when the sensitive feature set is larger than 1, say 2-4.
23

---

Published as a conference paper at ICLR 2026
Dataset
#Class
Dep.
#Trees
ENSENSE
KANT
covtype-robuse
10
6
100
139.08
3086.10
covtype untobust
10
6
100
213.78
3087.16
robust
10
6
100
118.76
5667.60
fashion_unrobust uunrobust
10
6
100
67.63
5001.60
ori robust
10
6
100
108.76
3343.97
ori unrtoutt
10
6
100
76
3587.97
Iris
100
0.01
0.01
Red-Wine
3
6
100
3.83
3.89
100
Table 2: Multi-Class comparison experiments with VERITAS and KANT. The table reports PAR2 runtimes for the experiments Fig. counting any timeout as 2 x the timeout.
G.1 TRAINING DETAILS
We trained XGBoost (v1.7.1; binary:logistic) with label encoding for categoricals, rows with miss- ing values removed, and hyperparameters chosen on a 20% validation split (seed = 42) over maxi- mum depthe {5,6) and number of boosting rounds (200,300,500) (benchmarks 7-9) 500,800 (benchmark 10).
G.2 ABLATION STUDY
10
10"
Timels, log scale)
Timels, log scale)
301
dks affeabi unaffe unaffeart
affeeb)
10a
unaff off-
107
unaife infffeaffoohi
1000
402
Instances Solved
Instances Solved
(a) Ablation Binary
(b) Ablation Multielass
Figure 6: Timing performance of single feature sensitivity for (a) binary ensembles. and (b) multiclass ensembles.
To evaluate the contribution of each component in sensitivity analysis, conducted ablation study by systematically removing key optimizations equation UnAff and equation Aff-bin eval- uating the resulting performance. We present these results in Figure 6 for binary ensembles in (left) and multi-class tree ensembles (right). Figur(6(left) reports the results for 1102 benchmarks whose runtime is >Is and omitting 188 instances solved under 1s. right) reports the results for 517 benchmarks whose runtime is > 1s, omitting 21 instances solved under 1s Overall, the added constraints improve solver performance by up an order of magnitude and dramatically reduce the number of timed-out instances. An interesting observation in both these plots is that when equa- tion bfff-i added then equation Unnff do not contribute much in the performance (as can seen by the overlapping lines). Overall, these results confirm that our enhancements significantly improve the practical feasibility of sensitivity verification in binary and multiclass decision tree ensembles.
G.3 MULTIFEATURE SENSITIVITY ANALYSTS
To evaluate the ENSENSE's ability to handle multi-feature sensitivity (i.e., sensitivity wrt change in more than one feature simultaneously FF] 1), conducted experiments binary classifica-
24

---

Published as a conference paper at ICLR 2026
10"
multifeature 1
multifeature 2
multifeature 3
10a
multifeature 4
multifeature
10a
time
10
10
10
50
100
150
200
250
300
350
400
Instances Solved
Figure 7: Timing performance of Multifeature sensitivity for Binary Classification
f7 < c1
fr C1
f4 <
fg <
fo <
fg < C3
valo
val
val2
cals
cals
vals
vale
cal7
Figure 8: A tree ensemble with two trees Ti, Tg having real valued (raw) outputs on leaves
tion models, allowing 1, 2, 3, 4, and 5 features to vary simultaneously. For each benchmark and each m-feature(s) setting, generate many test instances the total number of features. Each instance corresponds to randomly sampled subset of m-feature(s) from the feature set. Across all benchmarks (binary classifier) TableT this results total of 430 instances for the m-feature(s). The results, shown in Figure 7 demonstrate that even the number of varying features increases, our tool remains scalable and even improves in performance. The reason that the search space ex- plored by the tool decreases as we increase number of sensitive features (since we search in the space of F \ F). These results demonstrate the framework's scalability and effectiveness performing multi-feature sensitivity analysis.
H AN ILLUSTRATIVE EXAMPLE
In Figure we show a tree ensemble with two trees Ti and Tz. Each tree has four leaves with real-valued outputs val,, 0, O...., 7. Let us assume that the sensitive feature is {f1). We want verify there exists two inputs (1) and (2) differing only in feature fa such that the output of the ensemble changes from 0.5 gap to 0.5 + gap.
To formulate this MILP, we introduce the following variables:
(1) (1) (1) (1). Pai P71 P91 Pyz binary variables represent the decisions at the internal nodes of the trees for input (1)
25

---

Published as a conference paper at ICLR 2026
Pii:P7 :P1 P91 Pg2 binary variables represent the decisions at the internal nodes of the
(2) (2) (2) (2),
trees for input x (2)
(1) [1) 1 (1) .13
binary variables indicating which leaf of tree T₁ is reached by input x
((,,1 (1) 10
binary variables indicating which leaf of tree T2 is reached by input 2x())
10 10,1 11)) _1 binary variables indicating which leaf of T₃ reached by input ax(2)
1 (2) 1 binary variables indicating which leaf of tree T2 is reached by inputa(()
The objective function in the following is equation Obj-bin for our example.
max vale ((1) + valı 21") + val2 122) + vals 133 vala 14" + vals 1g
+ valo 16') val7 44) valo 1/² - val1 113) vol2 12²)
val3 (2) val. ((2) vals l5 vale ((2) val, (93)
(14)
The above objective is subject to the following constraints. In the guards of fo, we assume C1 < Therefore, the following constraints are due to Equation 2
(1)
P91 < P92
Pbi S P92
(2)
(2)
(15)
The following constraints are due to Equation 3
1 + (1)) ((0) + 1/
(1)
( +1 (2) (2) +1
(16)
4 + (1) + (1) +10
(2) + 15 (0) (
The following constraints due to Equations 4
and
-Pr + 1800 +2 =0
P71 + (2)
+ (2)
P71 +1 +1,1) ((1) =1
(1)
+ (2) (2)
P7
(1) +1 +15
+1
P71
(1) + +/0 +(() =1
(2) +
P71
P71
(1) 11++)55 50 50
-h (2) +
Pn
P4 12++1 S
(2) +1
(17)
P92 +1 0
(1)
(2) +1
Paz
P92 +111 <1
(1)
(2) +11
P9
P92 + +(00 50
(1)
P + +1
Pg2 + +111) <1
(1)
(2) +141
Pgz
(1) +1111 50
(2) +1(0) 10)00
P91
Pa1
P91 (1
(1) (1) <1
(2) 21
P91
The following constraints are due Equation 6
(1)
(2) 0
P91 + P91
(1) (2)
P92 + P92
(18)
(1) (2) 0
P71 P71
26

---

Published as a conference paper at ICLR 2026
The following constraints are due to equation Gap-bin
valo ( + vall 1 + val2 1/2 + val3 (11) + vala ( + vals 1/ + vala 16 + valy 144) 2 gup 0.5
valo (6²) + valı 199) + val2 122) + valy 122) + vala ((2) 14 + vals ((2) + vale (/2) vals 1,2) S 0.5 gap
(19)
The following constraints are due to Equations f4 is sensitive.
UnAff and Aff-bin respectively, since only feature
1 (2)
2
(1) ( (2)
( (
(20)
( 5 (2)
((1) =16 (2)
5 (49)
valo 16' + veal 111) valo 16 (22 - val, 1121 2 2 gap
(21)
The above constraints indicates the key reason of the efficiency of our method. The long sum of Equation [9 reduces much shorter sum Thereby, MILP solver has easier time solving the problem.
27


Reviews:
[{"review_id": "zwTmjKwQVG", "reviewer": "Reviewer_KgVe", "summary": "The paper studies the feature sensitivity problem in decision tree ensembles. The authors proposed a data-aware sensitivity framework that builds on the combination of MILP and SMT encoding to verify whether prediction changes under feature perturbations. They developed a method SVIM and demonstrated the effectiveness of their methods compared to prior work on empirical data sets.", "questions": "1. Could this method be generalized for regression problems?\n2. Will the “data-aware” counterexample be used for model retraining, will there be model improvements observed?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper shows sensitivity verification is NP-hard even for depth-1 trees.\n2. The authors implemented their method SVIM and outperformed prior baselines such as SENSPB and KANT.\n3. They extended the method beyond binary classification to multi-class problems.\n4. The paper is clear in definitions and theoretically well-justified.", "weaknesses": "1. Whether the “data-aware” counterexamples lead to practical improvements in model fairness or robustness is not well explored, and remains an interesting practical direction.\n2. The independence assumption is mitigated through restricting space, yet it still introduces a theoretical gap between the assumed and real data distribution.\n\nMinor formatting: “Figures” vs “Fig”. (Line 456)", "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": "SBdKFM6foT", "reviewer": "Reviewer_6CwP", "summary": "This paper introduces efficient techniques to evaluate the sensitivity of an ensemble of trees to different subsets of features. The authors propose a specialized MILP formulation to construct counterexample pairs, while insuring that the constructed counterexample is realistic with respect to the data distribution. Empirical analysis shows that, across several datasets and models, this tool provides substantial runtime improvements over existing methods.", "questions": "- I would recommend adding the 1 feature case to Figure 7 to support a direct comparison.\n- In the examples in the appendix, it would be nice to know what each of the reported features represents.\n- I would consider this out of scope for the current work, but in the future I would recommend conducting a brief user study to see whether the counterexamples generated by this method are generally considered more realistic.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The empirical results for SVIM are quite compelling. SVIM universally improves upon the runtime of prior methods, while producing counterexamples that are designed to be realistic.\n- The proposed MILP formulation is interesting and involves several novel components.\n- The problem studied here is interesting and well motivated.\n- In general, the paper is well written and figures are clear.", "weaknesses": "- While the paper is generally easy to follow, it is quite notation heavy and suffers from some minor inconsistencies. In addition to the several specific comments listed below, I recommend adding a notation table to the appendix to help readers keep up.\n    - In EQ 4/5, should $p_{kf}$ be $p_{fk}$?\n    - In Eq Gap-Bin and Off-bin, $v_i$ is undefined.\n    - In the data aware objective function defined under Utility Function, it seems like some things may be off. Should solution (2) be considered in some way, rather than just solution (1)? Additionally, I don’t think pi_f without an input value is well defined.\n    - In the constraint introduced under Computing clause summaries, I believe w is undefined. Additionally, the subscript on the “and” is a bit off — should $j \\in |F|$ be either $j \\in F$ or $j \\in [1, |F|]$?\n- The L2 distance may not be an appropriate metric to measure counterexample validity because it may be thrown off if one entry in the original, unperturbed sample is extreme. Maybe an L_infininty distance would be more appropriate? This does depend on how features were pre-processed. Were they normalized in some way?", "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": "uOOiC6CQ9A", "reviewer": "Reviewer_6zFs", "summary": "This paper introduces several improvements, both in runtime and example quality, to the framework of Kantchelian et al. (2016) for finding pairs of sensitive points (or two inputs which are close to the dataset, and have very different probability predictions from a tree ensemble). The closeness to the dataset is one improvement, for which two methods are discussed. The first is an approach that measures a point's closeness to the dataset by the product of its marginals, and the second restricts the search to remove \"cavities\", or boxes in input space with no points. The authors also present several runtime optimizations based on adding additional constraints of consistency across predicate variables and leaf conditions. There are experimental results demonstrating improved performance on several binary and multiclass datasets, and a variety of parameter configurations.", "questions": "1. Are any of the approaches you're comparing against designed for multi-threaded systems? Is your approach suited for multi-threaded systems? I am skeptical of a single-core evaluation of MILP-solver based systems, which to my understanding (not my field, so please pardon the question) are designed to be parallelizable.\n\n2. How do you place a limit on cavity constraint creation so that you don't cover the entire input space?\n\n3. What is the relationship between this topic and the domain of adversarial example search, where the goal is to find an adversarial example very close (within some small $\\varepsilon$) to a specific point in the dataset?\n\n4. Does your approach model binary/categorical and continuous features in the same input space? Does this affect your distance-based methods? Modeling these in the same input space enforces an assumption about the relative \"cost\" of flipping a binary variable and moving around on a continuous feature. \n\n5. Very minor point, but the table headers in table 2 in the appendix are confusing. What is %V?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The papers organization is clear and logical, and the paper is well situated in existing literature. It is clear from the authors' presentation what is novel, how it is novel, and what research problems each component of the paper are trying to address.\n\n2. The new constraints that speed up optimization are well-reasoned and proven to be correct.\n\n3. The ablation study is convincing that the combination of all methods leads to a greater improvement than any subset.\n\n4. I am not an expert in this area, but I appreciate the effort to go above and beyond to compare to VERITAS by modifying this system to suit the sensitivity problem. \n\n5. The experiments seem to demonstrate a runtime improvement over existing methods, as well as finding examples closer to the training distribution.", "weaknesses": "1. The benchmarking results are too aggregated and are lacking statistical significance testing or error bars. The results should have been obtained over repeat trials for each configuration, with a corresponding mean and standard deviation. Moreover, it seems that most problem instances evaluated in Figure 3 are on only 4 datasets -- the ones with a lot of combinations of # trees and depths. I think that this work requires 1) statistical significance testing on the results over repeat trials for all results, and 2) disaggregated versions of the results by dataset (perhaps in the appendix; the aggregated results are fine as long as the disaggregated versions are accessible).\n\n2. Figure 4 is really hard to read, and the definition of distance to the dataset is unclear. I assume that the distance to the dataset is defined by the distance to the nearest training point. I am concerned that, under this definition, a counterexample could be close to only a single point far off in a low-density region of space but still appear \"close\" to the dataset.\n\n3. The use of cavities to restrict the search space is not compelling to me. Even in the provided example, it is odd that we ignore potential counterexample pairs close to the boundary of the green box. Those points are just as \"in distribution\" as any other. Furthermore, at least by inspection, it seems to me that we could form overlapping cavities over the entire search space, and thereby restrict our search only to exactly the points in the training dataset (for which there can obviously be no counterexample pairs). \n\n4. The examples of counterexample pairs in the appendix are not informative -- there is no relative scale to understand what different distance magnitudes mean, and there are no feature names to understand the actual relevance of the features involved. The conclusions in the paragraphs in section B in general (\"quite far from any possible realistic data point and may not be very helpful\", for example) are not well-justified and contextualized in terms of the actual features in the data.\n\n5. The experiment in Figures 6 and 7, which do the ablation and vary the number of features to be searched over, seem to be conducted on different datasets (fewer instances) than the other experiments. These should be described.", "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": "DJKHlimVVa", "reviewer": "Reviewer_XHrk", "summary": "This paper proposes a new method for the sensitivity analysis of decision tree ensembles. \nGiven a tree ensemble classifier, it aims to identify two data points that are close but receive different predictions from the model. \nThe authors also introduce an additional constraint that encourages two data points to be close to the dataset and propose an efficient algorithm based on mixed-integer linear programming (MILP). \nBy experiments with large tree ensemble models, the authors demonstrated that the proposed method achieved significant speedups over baseline methods.", "questions": "1. The proposed method aims to generate pairs of data points $x^{(0)}$ and $x^{(1)}$ that are close to the dataset $\\mathcal{D}$. Why not simply use data points already contained in $\\mathcal{D}$? If one of the points, say $x^{(0)}$, were fixed to a sample from $\\mathcal{D}$, can we formulate the problem as a more tractable one while still achieving the same objective? \n1. Could the authors clarify which part of the analysis in the prior work (Ahmad et al., 2025) makes it impossible to extend or adapt to the cases with depth 1 or 2? A brief explanation would help contextualize the limitation and highlight the novelty of the proposed approach.\n1. In the experiments, both the proposed method and Kant rely on an MILP solver to obtain solutions. Which solver did the authors use?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "1. This paper tackles an important problem of sensitivity analysis for tree ensemble models. The authors provide a theoretical analysis for the case that has not been addressed in prior work (Ahmad et al., 2025).\n1. The experimental results demonstrate the scalability of the proposed method. Figure 3 clearly demonstrates that the proposed method could obtain solutions in a reasonable time compared to the baselines.", "weaknesses": "1. The presentation of Section 5 could be improved entirely. It is difficult to distinguish which terms are decision variables and which are fixed parameters in the proposed MILP formulation, making it hard to implement and reproduce. Adding clear notation definitions and a small illustrative example would help readers understand the formulation more easily and grasp the intuition behind the constraints.\n1. While Figure 4 appears to show the L2 distance of each method for each instance, it is difficult to interpret and extract meaningful insights from it. It might be more precise and informative to summarize the results in a table reporting average values or win rates, rather than presenting all instance-level values in a single figure.\n1. (Minor) The motivation of “data-awareness” has also been discussed in the literature on counterfactual explanations, which aim to generate realistic perturbations to alter prediction outcomes (e.g., Cui et al., 2015; Kanamori et al., 2020; Parmentier and Vidal, 2021). It would be helpful if the authors could clarify how their notion of data-awareness differs from or extends these prior concepts.", "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)