CLARITree: Cholesky and Lookahead Accelerations for Regression with Interpretable Piecewise Linear Trees

Regression trees are among the most interpretable yet expressive model classes in machine learning. Historically, greedy induction has been the dominant approach for constructing well-performing regression trees. While optimal methods based on dynamic programming and branch-and-bound exist, they are computationally prohibitive for general linear regression trees, despite often achieving substantially better performance than greedy approaches. Recent work has shown that specialized lookahead strategies can dramatically improve runtime while maintaining near-optimal performance, primarily in classification settings. In this work, we develop a novel algorithm for near-optimal, sparse, piecewise linear regression trees that combines a lookahead-style search strategy with efficient rank-one Cholesky updates of the Gram matrix. We demonstrate, both theoretically and empirically, that our method achieves a favorable trade-off between computational efficiency, predictive accuracy, and sparsity, and scales significantly better than the current state of the art.

Decision trees are widely used because people can easily understand how they make predictions. Linear regression trees further improve this idea by combining simple decision rules with local linear models, allowing them to capture more complex relationships while remaining interpretable. However, there is often a trade-off between accuracy and efficiency. Fast methods usually rely on greedy decisions that can miss much better solutions, while more accurate optimization-based methods are often too slow to run on large datasets. In this work, we develop a new algorithm, CLARITree, that builds accurate and interpretable linear regression trees much more efficiently. Our method looks ahead before making splitting decisions, allowing it to avoid many poor local choices made by standard greedy approaches. At the same time, we introduce efficient mathematical updates that greatly reduce the computational cost of evaluating candidate tree structures. Across many benchmark datasets, CLARITree achieves prediction performance close to state-of-the-art optimal methods while being dramatically faster and more scalable. This helps make highly accurate, interpretable machine learning models more practical for real-world applications where both transparency and efficiency are important.