analiza aiqbench
The paper formalizes "glitches," sharp local spikes in decision tree ensemble outputs caused by small changes to one input feature, and frames them as auditable targets rather than errors. It reports that they are common even in state-of-the-art models, proves that detecting them is NP-complete, and offers a MILP-based verifier that scales to realistic gradient-boosted models. For ML practitioners working on tabular models in high-stakes domains, the practical takeaway is that robustness and monotonicity checks may miss these behaviors, so formal verification tools may be needed for auditing.
Verifying Glitches in Decision Tree Ensembles
arXiv:2507.14492v2 Announce Type: replace 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.
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.
Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2507.14492 [cs.LG]
(or arXiv:2507.14492v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2507.14492 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 321 cuvinte
Subiecte conexe
Shrinking the Generation-Verification Gap with Weak Verifiers
arXiv · 7 aug. 2026
Do Quantum AIs Dream in Paths? Path-Integral Slow Thinking through Grover Interference
arXiv · 9 sept. 2026
MedRAGChecker: Claim-Level Verification for Biomedical Retrieval-Augmented Generation
arXiv · 24 aug. 2026
Combinatorial Lock for Trojan-Resilient AI Engines via Hash-Assisted Spectral Filtering
arXiv · 28 oct. 2026