← 研踪 PaperTrailarXiv:2507.14492 · v2
Verifying Glitches in Decision Tree Ensembles
首次提交 2025-07-19 13:33
版本更新 2026-10-28 16:33
雷达观测 2026-10-30 10:22
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-10-28 16:33 · 最新观测版本
Verifying Glitches in Decision Tree Ensembles
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.
查看此版本解读 →查看此版本原文 ↗