Near-Optimal Decision Trees in a SPLIT Second
Varun Babbar, Hayden McTavish, Cynthia Rudin, Margo Seltzer · 2025
Read Near-Optimal Decision Trees in a SPLIT Second by Varun Babbar, Hayden McTavish, Cynthia Rudin, Margo Seltzer (2025) 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-2502-15988.txt.
Description
Varun Babbar and co-authors chase decision trees that are nearly optimal yet built at greedy speed. Their 2025 paper addresses a standing trade-off in interpretable machine learning: greedy tree growing is fast but provably suboptimal, while exact search finds the best small trees at crushing cost. Their SPLIT family of algorithms looks ahead where it matters.
The key insight is that the deep parts of the tree need not be solved exactly, since greediness suffices near the leaves. Skipping exactness there prunes an exponential blowup, buying orders of magnitude in speed. The authors pitch the method as a step toward trees that regulators can read and engineers can still afford.
Catalog record
| CREATOR | Varun Babbar, Hayden McTavish, Cynthia Rudin, Margo Seltzer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 139 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-15988