Verifying Glitches in Decision Tree Ensembles

Satyankar Chandra; Harsh Chaurasia; Ashutosh Gupta; Kaushik Mallik; Krishna Shankaranarayanan; Namrita Varshney

cs.LGJul 19, 2025

Verifying Glitches in Decision Tree Ensembles

Authors: Satyankar Chandra, Harsh Chaurasia, Ashutosh Gupta, Kaushik Mallik, Krishna Shankaranarayanan, Namrita Varshney

Organizations: Indian Institute of Technology Bombay, Mumbai · IMDEA Software Institute Madrid, Spain

Abstract

Decision tree ensembles are widely used for tabular prediction tasks in judiciary, healthcare, banking, etc. We show that the piecewise-constant structure of these models can create narrow local oscillations, leading the ensemble score to sharply drop and then rise (a downward spike), or sharply rise and then drop (an upward spike), over a small change in a single feature. We call such patterns glitches. A glitch is not, by definition, an error. Rather, it is a formally checkable audit target requiring inspection. Formally, glitches are witnessed by ordered input triples in which a small monotonic change in a single input feature causes the output to first change in one direction and then revert in the opposite direction. Through a substantial experimental study, we show that glitches have widespread existence in even the state-of-the-art models performing various critical tasks. Our findings also indicate that glitches enrich and extend existing notions like robustness and monotonicity, providing us a more refined tool to isolate anomalies for inspection. On the theoretical side, we prove that deciding whether a decision tree ensemble contains a glitch is NP-complete, even for bounded-depth trees. We then present a mixed-integer linear programming encoding for the global and local glitch verification problems, and implement our algorithm in a verifier for gradient-boosted decision trees. Experiments show our verifier can scale to realistic model sizes from the literature.

Figures & tables

Panel of Figure 1 — Figure 1: Glitch illustration: The plot illustrates the output score of a binary classifier as one input feature varies monotonically. The output score threshold at which the prediction flips is indicated by the dashed line. The blue circles mark threshold crossings, each of which witnesses a local robustness violation. The set of three red crosses marks a glitch: a short input interval in which the score jumps from one prediction to another and then jumps back.

Panel of Figure 2 — Figure 2: Comparing robustness and glitch events in a pre-trained binary classifier [ 12 ] . The X-axes vary feature f18 while all other features are fixed. The Y-axes show the model output. Values above $0.5$ are predicted as label $1$ , and values below $0.5$ as label $0$ . Red dots are nearby training points. Panel (a) shows an anticipated local robustness violation caused by nearby training points with different labels. Panel (b) shows a glitch: as f18 increases, the three marked points satisfy $p^{-}=(0.4703,0.757)$ , $p=(0.4708,0.4875)$ , and $p^{+}=(0.4722,0.567)$ . Thus $p^{-}$ and $p^{+}$ are predicted as label $1$ , while the intermediate point $p$ is predicted as label $0$ . The glitch event therefore contains two opposite threshold crossings in a short interval, not just a single pairwise output change.

Panel of Figure 4 — Figure 4: Illustration: reducing the toy 3-CNF-SAT instance $(\lnot a\lor b\lor\lnot c)$ to a tree ensemble for $\mathrm{TE\_GLITCH(\alpha,i)}$ . Denoting the (only) clause as $c_{1}$ , LEFT: $T_{1}$ , RIGHT: $T_{1}^{\prime}$ . For each node, the child connected to it via a solid or dashed edge is its “true” or “false” child, respectively.

SNO	ModelName	#Trees	Dep.	#Feat.
Benchmarks
1	breastCancerR	4	4	10
2	breastCancerU	4	5	10
3	diabetesR	20	4	8
4	diabetesU	20	5	8
5	ijcnnR	60	8	22

Table 1: Benchmarks for our experiments. R and U stand for robust and unrobust versions of the models, respectively.

Config	Adult	Churn	Pima	German	Breast	Spambase
			Diabetes	Credit	Cancer
t200_d4	85.71	42.86	100.00	38.89	33.33	92.00
t200_d5	78.57	26.67	100.00	29.41	41.38	91.49
t500_d4	57.14	26.67	100.00	33.33	31.03	92.00
t500_d5	57.14	26.67	100.00	23.53	41.38	93.75
t800_d4	78.57	26.67	100.00	22.22	31.03	90.00

Table 2: Features exhibiting glitches under TE_GLITCH(

\alpha

,i) with

\alpha=1

. Percentage of features with glitches across six tabular datasets and six tree configurations (t = number of trees, d = maximum depth).

Figure 5: Robust vs. unrobust models. Robust training reduces but does not eliminate glitch-exhibiting features.

Panel of Figure 6 — Figure 6: Cactus plot reports the runtime (a) for $\mathrm{TE\_GLITCH(\alpha,i)}$ , (b) for $\mathrm{TE\_GLITCH(\alpha)}$ and (c) $\mathrm{TE\_GLITCH}$ .

Config	Adult	Churn	Pima Diabetes	German Credit	Breast Cancer	Spambase
t200_d5	533.70	134.52	33.80	67.31	5.37	6399.41
t200_d6	474.30	151.22	68.24	26.36	17.85	2013.30
t500_d5	337.26	32.96	138.80	124.87	10.72	TO
t500_d6	343.34	24.43	14.10	84.86	16.40	0.27
t800_d5	129.40	10.72	109.95	7.22	10.72	TO
t800_d6	0.84	TO	48.08	33.82	16.40	TO

Table 3: Glitch magnitudes reported for

\mathrm{TE\_GLITCH}

Panel of Figure 7 — Figure 7: Local robustness violations and glitches. (a) Counts in $\epsilon$ -neighborhoods of randomly sampled test points, where A and U denote anticipated and unanticipated robustness violations. (b)–(c) A churn-model glitch before and after monotonic training on $TotalCharges$ .

Ensemble Learning

Ensemble learning combines multiple predictors to improve accuracy, robustness, calibration, or uncertainty estimates.

See all 278 papers

Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach
May 13, 2026Ajinkya Naik, Chaitanya Garg, S. Akshay +2Ensemble Learning Formal Verification
Indian Institute of Technology Bombay, India · University of Toronto, Canada
Leaf Values as Coordinates: Exact Contrastive Explanation for Gradient-Boosted Ensembles
Aug 19, 2026Emanuele LuzioCounterfactual Explanations Algorithmic Recourse
Independent Researcher
Learning Auditable Classifier Models: Source-Disjoint Tree Ensembles
Aug 16, 2026Srikumar KrishnamoorthyRule-Based Classification Interpretable ML
Information Systems Area, Indian Institute of Management Ahmedabad, India

May 13, 2026J/K move · Enter open · S save

Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach

Ajinkya Naik, Chaitanya Garg, S. Akshay, Ashutosh Gupta+1

Indian Institute of Technology Bombay, India · University of Toronto, Canada

Ensemble Learning Formal Verification Sensitivity Analysis

Open paper AskPDF arXiv

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 XCount achieves significant speedup over other approaches and can scale well with the increasing sizes of the ensembles.

Abstract

Ensemble Learning

Explore similar work

Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach

Leaf Values as Coordinates: Exact Contrastive Explanation for Gradient-Boosted Ensembles

Learning Auditable Classifier Models: Source-Disjoint Tree Ensembles