# Robustness Verification of Tree-based Models

arXiv: https://arxiv.org/abs/1906.03849 · HTML: https://mlsanity.com/paper/1906.03849/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2019.

## Built on by (most cited first, 30 of 33)

- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [A Review of Formal Methods applied to Machine Learning](https://mlsanity.com/paper/2104.02466/) (2021)
- [A Review of Adversarial Attack and Defense for Classification Methods](https://mlsanity.com/paper/2111.09961/) (2021)
- [Learning Interpretable, High-Performing Policies for Autonomous Driving](https://mlsanity.com/paper/2202.02352/) (2022)
- [Statistical Perspectives on Reliability of Artificial Intelligence Systems](https://mlsanity.com/paper/2111.05391/) (2021)
- [On the Safety of Interpretable Machine Learning: A Maximum Deviation Approach](https://mlsanity.com/paper/2211.01498/) (2022)
- [Neural-to-Tree Policy Distillation with Policy Improvement Criterion](https://mlsanity.com/paper/2108.06898/) (2021)
- [(De-)Randomized Smoothing for Decision Stump Ensembles](https://mlsanity.com/paper/2205.13909/) (2022)
- [Beyond Robustness: Resilience Verification of Tree-Based Classifiers](https://mlsanity.com/paper/2112.02705/) (2021)
- [Enhancing Robustness of Gradient-Boosted Decision Trees through One-Hot Encoding and Regularization](https://mlsanity.com/paper/2304.13761/) (2023)
- [Trust Regions for Explanations via Black-Box Probabilistic Certification](https://mlsanity.com/paper/2402.11168/) (2024)
- [Verifiable Learning for Robust Tree Ensembles](https://mlsanity.com/paper/2305.03626/) (2023)
- [Robustness Verification for Knowledge-Based Logic of Risky Driving Scenes](https://mlsanity.com/paper/2312.16364/) (2023)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [Naive Bayes Classifiers over Missing Data: Decision and Poisoning](https://mlsanity.com/paper/2303.04811/) (2023)
- [Ensuring Topological Data-Structure Preservation under Autoencoder Compression due to Latent Space Regularization in Gauss--Legendre nodes](https://mlsanity.com/paper/2309.08228/) (2023)
- [Data-Aware and Scalable Sensitivity Analysis for Decision Tree Ensembles](https://mlsanity.com/paper/2602.07453/) (2026)
- [MUC-driven Feature Importance Measurement and Adversarial Analysis for Random Forest](https://mlsanity.com/paper/2202.12512/) (2022)
- [Finding Minimum-Cost Explanations for Predictions made by Tree Ensembles](https://mlsanity.com/paper/2303.09271/) (2023)
- [Faster Repeated Evasion Attacks in Tree Ensembles](https://mlsanity.com/paper/2402.08586/) (2024)
- [Generating Global and Local Explanations for Tree-Ensemble Learning Methods by Answer Set Programming](https://mlsanity.com/paper/2410.11000/) (2024)
- [PACE: Prune-And-Compress Ensemble Models](https://mlsanity.com/paper/2605.06278/) (2026)
- [Adversarial Example Detection in Deployed Tree Ensembles](https://mlsanity.com/paper/2206.13083/) (2022)
- [Quantifying probabilistic robustness of tree-based classifiers against natural distortions](https://mlsanity.com/paper/2208.10354/) (2022)
- [Robust Boosting Forests with Richer Deep Feature Hierarchy](https://mlsanity.com/paper/2210.16451/) (2022)
- [Symmetry Defense Against XGBoost Adversarial Perturbation Attacks](https://mlsanity.com/paper/2308.05575/) (2023)
- [Inverse classification with logistic and softmax classifiers: efficient optimization](https://mlsanity.com/paper/2309.08945/) (2023)
- [Probabilistic ML Verification via Weighted Model Integration](https://mlsanity.com/paper/2402.04892/) (2024)
- [Verifiable Boosted Tree Ensembles](https://mlsanity.com/paper/2402.14988/) (2024)
- [On the Efficiency of Training Robust Decision Trees](https://mlsanity.com/paper/2507.10048/) (2025)

## Abstract (arXiv)

We study the robustness verification problem for tree-based models, including decision trees, random forests (RFs) and gradient boosted decision trees (GBDTs). Formal robustness verification of decision tree ensembles involves finding the exact minimal adversarial perturbation or a guaranteed lower bound of it. Existing approaches find the minimal adversarial perturbation by a mixed integer linear programming (MILP) problem, which takes exponential time so is impractical for large ensembles. Although this verification problem is NP-complete in general, we give a more precise complexity characterization. We show that there is a simple linear time algorithm for verifying a single tree, and for tree ensembles, the verification problem can be cast as a max-clique problem on a multi-partite graph with bounded boxicity. For low dimensional problems when boxicity can be viewed as constant, this reformulation leads to a polynomial time algorithm. For general problems, by exploiting the boxicity of the graph, we develop an efficient multi-level verification algorithm that can give tight lower bounds on the robustness of decision tree ensembles, while allowing iterative improvement and any-time termination. OnRF/GBDT models trained on 10 datasets, our algorithm is hundreds of times faster than the previous approach that requires solving MILPs, and is able to give tight robustness verification bounds on large GBDTs with hundreds of deep trees.