CS Paper Radar

Adaptive Multi-Branching for Shallow Decision Tree Induction

Hanul Park, Jeonghoon Choi, Juseong Kim, Sanghun Sel, Giltae Song

cs.LG cs.AI ·submitted 2026-08-29 13:35 UTC · v1

Abstract

Decision trees are attractive for tabular prediction tasks because each prediction follows an interpretable sequence of feature-threshold tests. Under a strict maximum-depth budget, however, conventional binary trees can be under-expressive, since each internal node makes only a single threshold decision. We study shallow-depth tree induction, where the goal is to improve accuracy while keeping root-to-leaf paths short. We propose the Multi-Branch Neural Decision Tree with Adaptive Pruning (MBNDT), a single axis-aligned tree trained end-to-end with differentiable multi-way splits. Each internal node learns ordered thresholds over a selected feature and a branch mask that adapts its effective arity, and the trained model is converted to a deterministic single-path tree for inference. Across 21 OpenML binary-classification benchmarks, MBNDT achieves the best average rank and mean balanced accuracy among depth-constrained single-tree baselines; a controlled ablation isolates multi-way splitting as the source of the gain. These gains come with an explicit trade-off: MBNDT realizes more leaves than the other single-tree baselines, making it best suited when accuracy under short, bounded decision paths is prioritized over minimal global tree size.

Comment
9 pages, 1 pages for the appendix

Closest papers

Nearest neighbours by meaning across the whole index.

A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees

cs.LG cs.AImath.OC ·2026-09-18 ·Chenxuanyin Zou, Jiayang Ren, Qiangqiang Mao, Jing Liu, Marcus Lai +1 more
published similarity 0.71
Abstract · J2C Certification

Despite the importance for interpretability, decision trees face severe scalability challenges. Existing global optimal methods are often limited by binary feature selection and shallow tree depths, whereas traditional heuristic approaches frequently sacrifice predictive accuracy. To overcome these limitations, this paper proposes a moving-horizon approximate branch-and-reduce method to train near-optimal deep classification trees on large-scale datasets with continuous features. Built on a hierarchical root-subtree optimization framework, the method solves the root-level problem via branch-and-reduce while approximating the induced subtree problem using greedy heuristics. Although the underlying framework is capable of guaranteeing global optimality, the approximation, which functions as a lookahead rollout in a reinforcement learning context, significantly boosts efficiency for deeper structures. A low-cost moving-horizon strategy is then employed to iteratively refine model accuracy. Extensive numerical results demonstrate that our method exceeds the testing accuracy of existing heuristic baselines while offering significantly greater scalability, in terms of both dataset size and tree depth, than global optimal solvers.

0.22

MotherTree: Meta-learning on synthetic data improves decision tree training

cs.LG ·2026-10-07 ·Ziyuan Wang, Fredrik D. Johansson
hot direction similarity 0.69
Abstract

Conventional decision tree algorithms produce effective, transparent models that can be audited, communicated, and deployed independently of the training data, but require learning every new task from scratch. In contrast, tabular foundation models demonstrate that meta-learning from a synthetic prior distribution enables strong in-context prediction for previously unseen tasks, especially in small-sample regimes. However, this approach does not produce a standalone model that can be inspected in isolation. We introduce MotherTree, a tabular transformer that meta-learns decision tree induction: given a training set for a new task, it outputs a hard, axis-aligned decision tree, equivalent in form to classically trained trees, in a single forward pass. MotherTree is pre-trained on a synthetic prior using stochastic gradient descent without requiring reference trees for supervision. On established benchmarks with controlled sample size, the approach is competitive with size-matched trees from common algorithms: recursive partitioning, gradient-based tree learning, globally optimal trees, and distillation from tabular foundation models. Notably, MotherTree consistently improves over from-scratch gradient-based learning and acts as a strong initializer: task-specific tuning of the generated tree outperforms the corresponding from-scratch learner on all benchmarks and sample sizes. These results show that meta-learning can provide effective inductive biases for learning stand-alone, small decision tree classifiers.

0.27

Partially Interpretable Decision Trees

cs.LG ·2026-11-04 ·Ludovic Schwartz, Federico Berton, Tim van Erven
similarity 0.64
Abstract

Partially interpretable models extend simple interpretable models with the option to defer complicated inputs to an accurate but uninterpretable black-box model. By deferring more inputs, the model gets more accurate; by deferring fewer, it gets more interpretable. Existing procedures to train such partially interpretable models build on linear models or decision rules. We propose three algorithms for decision trees: a partially interpretable extension of the existing Branches algorithm, which performs exact search to optimize the tree; a conversion algorithm that we run on top of standard CART, which is computationally more efficient; and a generalized CART whose splitting criterion takes into account the option to defer while growing the tree. Perhaps surprisingly, the performance of the three algorithms is similar across many realworld datasets. We can explain this through a formal bound on the potential gain of smart tree construction, provided the black box accuracy is sufficiently homogeneous across the domain. We also construct a synthetic dataset where the accuracy of the black box is deliberately inhomogeneous. There, our deferral-aware generalization of CART does outperform regular CART and matches the performance of exact search. Finally, we evaluate an application to concept bottleneck models. Partially interpretable decision trees can replace uninterpretable neural networks after the bottleneck. On undeferred inputs, the model is fully interpretable, and deferring preserves accuracy.

0.28

TreePIN$^{2}$: Tree-Prior Initialized Neural Networks

cs.LG cs.AI ·2026-10-31 ·Yanrong Wang, Qiming Sun, Haoyang Chen
similarity 0.64
Abstract

Fitted decision trees provide predictive knowledge for neural network initialization. We present Tree-Prior Initialized Neural Networks (TreePIN$^{2}$), a method that translates split rules, decision paths and leaf predictions into initial network weights and biases for classification and regression. Sigmoid units encode split responses, hidden units combine them along decision paths, and leaf predictions initialize the output layer. We calibrate split softness using local training margins, sample support and impurity reduction, relating the initial responses to the data at each node. All weights and biases remain trainable, allowing gradient-based optimization to refine the transferred decisions and their combinations. Across six classification and six regression tasks with twenty paired seeds, TreePIN$^{2}$ improves mean initial and early validation performance over initialization baselines on most tasks. After fifty epochs, it achieves the best or tied-best mean validation performance among the six compared methods on ten tasks. Paired ablations show how split calibration and leaf-informed output initialization contribute to the starting predictor and its subsequent learning.

0.28

From Prompts to Trees: Effective LLM-Guided Tree Generation for Few-Shot Tabular Classification

cs.LG cs.AIcs.CL ·2026-10-07 ·Yue Qiu, Zekang Du, Yiqun Diao, Bingsheng He, Qinbin Li
top venuecode/data similarity 0.64
Abstract · Accepted to EMNLP 2026 Main as an oral presentation. Code available: https://github.com/yueqiu0/LLMTree

While Large Language Models (LLMs) possess rich world knowledge and impressive generalization capabilities, their direct application to tabular data classification is hindered by high inference costs and limited interpretability. In contrast, decision trees are fast and transparent but often underperform in low-data regimes. In this work, we propose a novel framework that bridges these paradigms by distilling LLM knowledge into interpretable decision trees under a few-shot learning setting. Instead of directly prompting the LLM to generate full trees, which is often unstable and inefficient, we develop a three-stage paradigm that prompts the LLM to generate rules and organize the rules into a tree. Experiments on multiple real-world tabular datasets demonstrate that our method achieves superior accuracy and interpretability with significantly lower prompting overhead compared to existing baselines.

0.40

Literati: Towards Anytime Optimal Shape Generalized Trees via AO*

cs.LG ·2026-09-08 ·Nakul Upadhya, Eldan Cohen
top venue similarity 0.64
Abstract · Accepted to NeurIPS 2026

Decision trees are prized for their interpretability and strong performance on tabular data, but popular greedy top-down induction algorithms can yield suboptimal and unnecessarily complex structures. Optimal decision tree methods address this through global optimization, yet remain restricted to axis-aligned threshold splits, which limit the expressivity of each node and often force deep, complex trees to capture non-linear feature effects. Shape Generalized Trees (SGTs) generalize threshold splits to learnable univariate shape functions, improving expressivity and enabling more compact trees. However, existing SGT induction algorithms are greedy and offer no optimality guarantees. In this work, we introduce Literati, the first algorithm for optimal SGT induction. We propose a novel AND/OR graph formulation of the problem that jointly optimizes tree structure and shape function complexity. To solve this AND/OR graph, we develop an AO*-based algorithm with two enhancements that improve anytime performance while preserving optimality: a secondary heuristic for OR-node selection and a round-robin policy for AND-node exploration. Across 24 real-world datasets, Literati achieves higher training and test accuracy than state-of-the-art tree approaches.

0.39

Learned Look-Ahead Splitting Rule for CART

cs.LG stat.ML ·2026-09-14 ·Andrew Gao, Tianlin Liu, Ruichen Han, Lu Tian
similarity 0.62
Abstract

Classification and regression trees are typically constructed using a greedy splitting rule that maximizes the immediate reduction in prediction error at each node. Although this strategy is computationally efficient, it can miss splits that yield small short-term gains but create substantial downstream improvements after further partitioning. We propose a look-ahead tree-building method that evaluates each candidate split by the prediction error reduction achieved after growing a conventional CART subtree below that split. Because the full look-ahead procedure can be computationally expensive, we also describe a smart look-ahead algorithm that learns downstream split values using node-level features. The proposed framework preserves the interpretability of recursive partitioning while improving split selection in hierarchical or interaction-driven settings. We conduct a simulation study comparing conventional, full look-ahead, and smart look-ahead methods under several settings and apply the proposed methods to analyze two real data examples demonstrating the merit of the new methods.

0.30

An Exact Junction-Tree Extended Formulation for Optimal Classification Trees

cs.LG ·2026-09-21 ·Jiancheng TU, WenqiFan
similarity 0.61
Abstract

We develop an exact linear programming (LP) formulation for bounded-depth classification trees with binary features, using a junction-tree representation. The formulation is integral and supports recursive subtree optimization. Exact reductions make the model smaller while preserving the optimal value and recovery of an optimal tree. The reduced model supports two solution methods: column generation and message passing. Column generation solves integral restricted LPs and uses bounds over the full feasible domain to certify optimality. Message passing recursively combines optimal subtree costs. Both methods solve common subtree problems that, once the preceding tree decisions are fixed, can be evaluated independently and in parallel. Computational experiments show that the exact reductions substantially reduce the size of the junction-tree formulation. The resulting linear programming formulation certifies instances for which the tested mixed-integer formulation does not establish optimality within the same computational budget, while the column-generation and message-passing methods certify more instances and achieve an order-of-magnitude reduction in geometric-mean runtime relative to an existing state-of-the-art exact method for optimal classification trees.

0.20