Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach
Ajinkya Naik, Chaitanya Garg, S. Akshay, Ashutosh Gupta, Kuldeep S. Meel · 2026
Read Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach by Ajinkya Naik, Chaitanya Garg, S. Akshay, Ashutosh Gupta, Kuldeep S. Meel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13830.txt.
Introduction
Ajinkya Naik and four colleagues measure tweak-risk for choice tree sets, asking whether a small change in a subset of inputs can misread an input. Their method writes the problem as an algebra choice diagram, splitting it into sub-tasks solved fast to make math modular and large. Over tests of varying size in tree count and depth, XCount achieves big speedup over model counters on the same problem code. It scales well with growing sets.
Catalog record
| CREATOR | Ajinkya Naik, Chaitanya Garg, S. Akshay, Ashutosh Gupta, Kuldeep S. Meel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81050 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13830
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach Ajinkya Naik, Chaitanya Garg, S. Akshay, Ashutosh Gupta, Kuldeep S. Meel Abstract Decision tree ensembles (DTE) are a popular model for a wide range of AI classification tasks, used in multiple safety critical domains, and hence verifying properties on these models has been an active topic of study over the last decade. One such verification question is the problem of sensitivity, which asks, given a DTE, whether a small change in subset of features can lead to misclassification of the input. In this work, our focus is to build a quantitative notion of sensitivity, tailored to DTEs, by discretizing the input space of the model and enumerating the regions which are susceptible to sensitivity. We propose a novel algorithmic technique that can perform this computation efficiently, within a certified error and confidence bound. Our approach is based on encoding the problem as an algebraic decision diagram (ADD), and further splitting it into subproblems that can be solved efficiently and make the computation compositional and scalable. We evaluate the performance of our technique over benchmarks of varying size in terms of number of trees and depth, comparing it against the performance of model counters over the same problem encoding. Experimental results show that our tool 𝖷𝖢𝗈𝗎𝗇𝗍 \mathsf{XCount} achieves significant speedup over other approaches and can scale well with the increasing sizes of the ensembles. 1 Introduction Artificial Intelligence (AI) models are now ubiquitous in their use in almost all walks of life. While complex models such as transformers, variants of neural networks, and the like, now scale to millions of variables, a major concern has been the difficulty in interpretability and verifiability of such models. At the other end of the spectrum, decision trees are classical models which are known to be interpretable, but are not really scalable. A middle path that has proven to be effective is to train collections of decision trees, called Decision Tree Ensembles (DTEs), that tread the fine line between expressivity and scalability. Since the seminal paper of [ 12 ] , introduced the XGBOOST training algorithm that has since been used, adapted, analyzed and improved over the last decade in different applications and settings [ 5 ] . Today different training algorithms for DTEs including XGBOOST, random forests [ 35 ] , LGBMs [ 28 ] etc are routinely used in many applications [ 38 , 34 , 21 ] , especially in the financial sector [ 31 , 9 ] due to the ease of modeling tabular data using DTEs. Given its many applications, a rich line of work has considered formal verfication of different properties over DTEs [ 27 , 8 , 16 , 10 , 11 , 15 , 43 , 24 , 25 ] . These properties include, evasion, local robustness, sensitivity, fairness, explainability and more. A recent work in [ 1 ] considered the problem of sensitivity, which asks if a given DTE is sensitive to a set of features, i.e., does there exist a pair of inputs (called a sensitive pair) such that they differ only on sensitive features (by potentially a small margin), but their outputs are classified differently (with a high confidence). Sensitivity is closely related to individual fairness or causal discrimination [ 20 , 19 , 23 ] , since any such sensitive pair is a witness to unfairness, when sensitive features are seen as protected features. This problem is quite different from the well-studied local robustness problem, which asks if a model is robust around a given instance. The main difference is that while local robustness can be solved by searching around the neighborhood of a given input, sensitivity (much like the harder global robustness problem), requires searching across the entire input space (of a dimension that is related to the number of non-sensitive features). In [ 1 ] , the authors show NP-hardness of the problem and use a pseudo-Boolean encoding showing that their resulting tool could check and produce sensitive pairs for reasonably large DTE benchmarks. In [ 42 ] , an optimized MILP encoding was proposed for solving this problem, that not only extends to larger and multi-class tree ensembles, but also finds sensitive pairs that are close to the data-distribution. However, a shortcoming in both these works, was that they only check presence of a single sensitive pair, which does not necessarily capture sensitivity of the model. Indeed, what is needed is to quantify the sensitivity of a DTE, ie., to count the number of the sensitive pairs (or estimate the volume of the sensitive region) in a DTE. In fact, it would be even more useful to count the number of input regions for which we witness sensitivity of the model, i.e., existence of sensitive pairs, one inside this region and another outside, as this captures a quantitative measure of sensitivity of the model. This is the problem that we address in this paper. Quantitative verification problems are evidently harder to tackle than plain checking existence or satisfiability. Even for the simple setting of Boolean formulae, this is complexity-theoretically captured by the difference between \#P -hardness vs NP-hardness, with real difference being seen in tools; SAT-solvers routinely scale to millions of variables, while model counters (that count the number of satisfying assignments) are much more conservative. Most exact model counters, including the state-of-the-art d4 [ 30 ] and Ganak [ 41 , 37 ] work by knowledge compilation, i.e., compiling the formula into a form in which counting is easy. Approximate model counters such as ApproxMC [ 44 , 40 ] often scale better at the cost of providing PAC-guarantees rather than exact guarantees. Recent work has considered quantitative notions of robustness for neural networks [ 17 , 29 ] , but to the best of our knowledge, we do not know any work that deals with quantitative versions of sensitivity or fairness in decision tree ensembles. While moving from counting models in Boolean formulae to counting sensitive pairs or regions in DTEs, there are three questions that immediately present themselves. First, what should be the quantitative notion of sensitivity in DTEs? Second, what could be a knowledge representation form for such a quantitative version of sensitivity? Third, can we obtain algorithms at scale at the cost of getting an approximate count with formal guarantees? In this paper, we address these three questions and develop a new compositional algorithm that combines ideas from exact and approximate model counting, knowledge compilation and sensitivity verification tailored for decision tree ensembles. We implement the resulting algorithm and present experimental results to show the effectiveness of our solution. Our contributions are as follows: 1. We exploit the inherent structure of DTEs to formulate a discretized quantitative version of the problem of counting sensitive regions. We can then use Algebraic decision diagrams (ADDs) [ 3 ] , a quantitative extension of Binary decision diagrams (BDDs) [ 7 ] as a natural model to obtain the exact count. However, compiling a DTE to ADD is rather cumbersome and does not lead to efficient algorithms. 2. As our main algorithmic contribution, we develop a novel compositional technique, that subdivides the problem into subproblems for each of which