Literati: Towards Anytime Optimal Shape Generalized Trees via AO*

Nakul Upadhya; Eldan Cohen

Source-linked AI summary

Literati: Towards Anytime Optimal Shape Generalized Trees via AO*

Nakul Upadhya, Eldan Cohen

arXiv:2609.09299v1Sep 8, 2026cs.LG

TL;DR

Greedy tree induction can produce unnecessarily complex, suboptimal models, while existing SGT methods lack global optimality guarantees. Literati formulates optimal SGT induction as AND/OR graph search and solves it with an enhanced AO* algorithm. Across 24 benchmark datasets, it achieves superior performance over evaluated optimal-tree and greedy SGT baselines.

Problem
Greedy SGT induction can yield globally suboptimal trees, while existing optimal-tree methods do not provide optimal induction for expressive shape-function splits.
Method
Literati jointly optimizes tree structure and shape-function complexity using an AND/OR graph formulation solved by AO* with secondary OR-node heuristics and round-robin AND-node exploration.
Results
Across 24 benchmark datasets, Literati achieves superior performance over all evaluated optimal-tree and greedy SGT baselines.
Takeaways & Limitations
Literati provides optimality guarantees while retaining strong anytime performance for interpretable SGT induction.
Takeaways & Limitations
Literati is primarily designed for tabular data and may struggle to prove optimality on large-sample datasets within short time budgets.

Abstract

from arXiv · show

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.

1 Introduction

Decision trees combine interpretability with strong tabular-data performance, but greedy induction can produce suboptimal, unnecessarily complex structures. Literati addresses this gap by optimally inducing Shape Generalized Trees through an enhanced AO*-based AND/OR graph search.

1 Introduction: Global optimization methods improve generalization and reduce complexity, but conventional decision-tree approaches remain based on threshold splits.These methods optimize predictive performance and sparsity together.
1 Introduction: SGTs replace threshold comparisons with axis-aligned shape functions, enabling nonlinear node boundaries and more compact trees.Existing SGT methods nevertheless rely on greedy induction and can remain globally suboptimal.
1 Introduction: Literati jointly optimizes SGT structure and shape-function complexity in an AND/OR graph, with globally optimal solutions guaranteed.Its formulation targets both tree structure and the complexity of individual shape functions.
1 Introduction: Literati enhances AO* with an inadmissible secondary heuristic for OR-node selection and round-robin AND-node exploration, preserving optimality while improving anytime performance.The approach is evaluated against state-of-the-art tree induction baselines on real-world datasets.

2 Background

AND/OR graph search represents decomposable optimization problems through states, actions, and subproblems, while Shape Generalized Trees use interpretable univariate functions to capture nonlinear feature effects. Literati builds on these ideas to address the limitations of greedy SGT induction and prior optimal-tree search methods.

2.1 AND/OR Graph Search: AND/OR graphs encode OR choices among actions and AND requirements across each action’s successor subproblems.A state is solved when one action solves all of its successors, or when it is terminal.
2.1 AND/OR Graph Search: AO* searches acyclic AND/OR graphs with admissible heuristics, expanding relevant subproblems while preserving provable optimality.Its iterative process comprises selection, expansion, and bottom-up backpropagation until the root is complete.
2.2 Optimal Tree Induction: Literati differs from earlier AO*-based tree methods through a new SGT-specific graph formulation and selection enhancements for better anytime performance.The formulation jointly supports optimal SGT induction rather than only conventional sparse or cost-sensitive decision trees.
2.3 Shape Generalized Trees: SGTs replace threshold splits with learnable univariate shape functions that capture nonlinear feature-target relations while preserving visual interpretability.This can reduce repeated branching on the same feature and produce more compact trees.
2.3 Shape Generalized Trees: Existing SGT methods such as ShapeCART greedily optimize local impurity, yielding globally suboptimal trees that post-hoc refinement can only improve from its initialization.The increased expressivity of SGTs makes their induction more challenging.

3 Literati

Literati formulates sparse Shape Generalized Tree induction as an AND/OR graph and solves it with an AO*-based algorithm that preserves global optimality while improving anytime search.

3 Literati: Literati minimizes classification error while regularizing both the number of leaves and shape-function discontinuities.Depth and change-point constraints bound tree and branching-rule complexity.
3.1 AND/OR Graph Representation: The AND/OR formulation incrementally constructs shape functions by adding change points, avoiding direct enumeration of every feasible shape function.This decomposition lets AO* identify suboptimal partial shape functions during search.
3.1 AND/OR Graph Representation: Data states choose between leaf and split actions, while shape-function states refine a candidate rule or commit it to two child data states.Split actions incur λ + α, refinements incur α, and committed children must both be solved.
3.2 Anytime AO*: The admissible heuristic and AO* termination guarantee that the induced tree is globally optimal for the formulated sparse SGT problem.The heuristic also permits marking a data state terminal when Err(Ds) ≤ λ + α without affecting optimality.
3.1.2 Candidate Change Points: Adaptive discretization makes solutions optimal only within the discretized candidate space, although it substantially speeds convergence in practice.The authors report objective values close to those from the full candidate set in practice.
3.2 Anytime AO*: Literati improves anytime search with a secondary heuristic for OR-node selection and round-robin exploration of unsolved AND children.The secondary heuristic is more informative but potentially inadmissible; round-robin prevents repeated expansion of one imbalanced subtree.

4 Experimental Evaluation

Across 24 datasets, Literati combines globally optimized SGT induction with competitive anytime performance and stronger out-of-sample accuracy than the evaluated baselines. Experiments also show that richer shape functions and both selection enhancements improve performance.

4.1 Optimization Performance: Literati achieves the highest training accuracy for D ∈4, 5, 6 across evaluated methods and the lowest runtime among optimal methods for D ∈3, 4, 5.Table 1 summarizes training accuracy, runtime, and optimality proof rate across depth budgets.
4.1 Optimization Performance: Increasing shape complexity improves training accuracy: K = 1 to K = 2 yields ≈0.4%, while K = 3 achieves the highest accuracy at every depth.The K = 2 to K = 3 improvement is smaller but consistent, and K = 3 exceeds comparable SGT and optimal-tree methods.
4.1 Optimization Performance: Literati’s training accuracy continues improving with depth at every K, even when proof rates fall, while several baselines degrade or return poor timeout performance.The gap between Literati and STreeD or LDS-DL8.5 widens with increasing depth; DPDT does not return intermediate solutions upon timeout.
4.1.1 Selection Strategy Ablation: The informative inadmissible OR heuristic and round-robin AND selection each improve anytime performance, with their combination performing best overall.The ablation evaluates the selection strategies on five representative datasets.
4.2 Generalization: 1.0% higher average test accuracy than ShapeTAO, with a statistically significantly higher average rank than all evaluated baselines.This evaluates generalization under a 15-minute training budget per fold after validation-based hyperparameter tuning.

5 Conclusion

Literati formulates optimal Shape Generalized Tree induction as an AND/OR graph problem and uses AO*-based search to obtain optimal trees. The formulation is proven equivalent to the sparse SGT objective, while the method remains subject to tabular-data and computational-scaling limitations.

5 Conclusion: Literati provides optimal SGT induction by jointly optimizing tree structure and shape-function complexity through AND/OR graph search.The paper presents this as its central contribution and establishes global optimality for the formulation.
5 Conclusion: AO* retains anytime behavior through an inadmissible secondary OR-node heuristic and round-robin AND-node exploration while preserving optimality at termination.These two selection modifications are the algorithmic enhancements highlighted by the paper.
5 Conclusion: Literati is primarily designed for tabular data and may struggle to prove optimality on large datasets within short time budgets.These are the authors’ stated scope and computational limitations.
5 Conclusion: The AND/OR formulation is equivalent to the sparse SGT objective, so the optimal policy extracts a feasible tree satisfying depth and shape-complexity constraints.The proof identifies identical recurrences and base cases, then shows the extracted tree is optimal.

A.3 Lower Bound on Training Loss

The analysis establishes that Literati’s optimum is lower-bounded by DPDT and CART under matched conditions, while its AND/OR graph can grow rapidly with depth, features, samples, and shape complexity. Adaptive discretization reduces this growth, motivating Literati’s anytime search and implementation optimizations.

Lower bound and dominance: Literati’s optimal objective is at least as good as DPDT’s and is lower-bounded by CART, with equality to DPDT when K = 1.The comparison assumes matched depth budgets, regularization, candidate sets, and discretization schedules.
Lower bound and dominance: When K = 1, Literati’s shape functions reduce to threshold splits, yielding the same discretized feasible set and objective as DPDT.The error terms agree because the induced routing is equivalent up to relabeling, while the complexity penalties match under αDPDT = λ + α.
Graph complexity: The AND/OR graph’s effective branching factor is O(MN^K), and its state space is dominated by shape-function states, producing exponential growth with depth.Here N is the number of training instances, M the number of features, and K the shape-function complexity budget.
Adaptive discretization: Adaptive discretization reduces branching from feature-sample candidate counts to O(B_d^K), and when B_d ≪ M · N it significantly reduces the graph size.The resulting total state-space bound varies across depth levels through the product of depth-specific branching factors.
Implementation: The implementation improves runtime by reusing bin partitions, maintaining policy queues, and eagerly initializing commit successors for backpropagation.These structures avoid repeated partition scans and recomputation of statistics used throughout search.

C Additional Experimental Details

The experiments use specified hardware and established implementations for the evaluated tree methods, with dataset information summarized in Table 3.

Experimental setup: Experiments ran on Intel Granite Forest nodes with Xeon 6972P processors, 12 vCPUs, and 64 GB RAM.Optimization Performance experiments disabled regularization for all approaches.
Baseline implementations: CART, DPDT, STreeD, and ConTree use Scikit-Learn or official author-provided implementations.The implementations are identified by the corresponding software repositories or packages.
Datasets: Table 3 reports dataset statistics and source information for the experimental datasets.

C.1 Generalization Experiment Details

Generalization experiments tune depth and method-specific hyperparameters across the evaluated approaches, including Literati’s regularization, shape complexity, and discretization settings.

Shared tuning: Depth is tuned for every model over D ∈ {2, . . . , 6}.This common search range follows the cited experimental protocol.
Literati hyperparameters: Literati tunes impurity, λ, α, maximum shape-function order, and CART-node schedules, with α ≤ λ.Its λ and α grids range from 1 to 64 and are divided by the number of samples.
Baseline hyperparameters: ShapeCART, CART, AxTAO, and DPDT use method-specific impurity, split, leaf, regularization, and discretization hyperparameter grids.The configurations include candidate CART-node schedules for DPDT and regularization settings for AxTAO.

D Selection Strategy Ablation Continued

The selection-strategy ablation compares Literati configurations by their distance to the optimal solution over time and iterations across five datasets. The informative-heuristic and round-robin configuration consistently provides the best anytime performance.

Selection-strategy ablation: Figure D.5 plots distance to the optimal solution against time and iterations for Literati Full and its ablations on Eye-movements, Avila, Page, Fault, and Rice.
Selection-strategy ablation: The informative OR-node heuristic combined with round-robin AND-node selection consistently achieves the best anytime performance across five datasets.This result holds when performance is evaluated both by elapsed time and by search iterations.

E Other Inadmissible Heuristics

The CART-based inadmissible heuristic reaches near-optimal solutions faster than primal and impurity alternatives, despite minor initial overhead.

CART consistently approaches the optimum in fewer expansions than the primal or impurity heuristics across five datasets.Its advantage is more pronounced when progress is measured by iterations rather than wall-clock time.
The primal and impurity heuristics behave similarly because both score candidate splits using only information local to the node.The impurity heuristic uses weighted Gini or entropy multiplied by dataset size.
The CART heuristic fits a surrogate subtree, providing an implicit lookahead and tighter estimates.This produces substantial runtime improvement on most datasets, while adding only 10^-2–10^-1 seconds initially.

F Impact of Shapes

Increasing shape-function complexity improves training accuracy at comparable tree sizes, with the largest gains appearing when moving from K = 1 to K = 2.

Setup: The experiment sweeps 100 regularization values and compares K ∈ {1, 2, 3} at maximum depth 6 under a one-hour limit.K = 1 yields a threshold tree equivalent to DPDT in this configuration.
Results: K = 2 matches K = 1 accuracy with 35 leaves using 25 on Avila and matches the 40-leaf K = 1 model with 20 leaves on Rice.These comparisons quantify the reduction in tree size associated with more expressive shape functions.
Results: Increasing K consistently raises training accuracy across tree sizes on all five datasets.The effect is most pronounced on Avila and Rice.
Results: The accuracy gain from K = 2 to K = 3 is consistently smaller than the gain from K = 1 to K = 2.This indicates diminishing returns from additional shape complexity in the evaluated range.

G Optimality Experiment Results Continued

The continued optimality experiments show that Literati’s light configurations trade some training accuracy for major runtime savings while retaining anytime and proof-rate advantages.

G.2 Optimization Capability: Above D = 3, all Literati K values achieve statistically significantly higher training accuracy than the other compared approaches.For D ∈ {4, 5}, K = 2 and K = 3 also significantly outperform K = 1.
G.1 Light and Depth-Adaptive Configurations: Switching from heavy to light discretization reduces runtime by orders of magnitude but costs training accuracy.The light configuration still produces optimality proofs on a majority of datasets across all depths.
G.1 Light and Depth-Adaptive Configurations: Literati-L K = 1 achieves lower average runtime than DPDT-L, demonstrating the quality of Literati’s search strategy.Under light discretization, Literati and DPDT have identical training accuracy at all depths except D = 6 on Mini-Boone, where neither converges.
G.3 Per Dataset Results: With quantile pre-discretization, Literati has higher training accuracy than STreeD at every depth except D = 3, where the methods tie.Literati has higher proof rates at D = 3 and D = 5, while STreeD is higher at D = 6.

H Per Dataset Generalization Results

The per-dataset generalization section reports test accuracy and runtime across folds, while emphasizing that SGTs retain decision-tree interpretability through modular, feature-wise shape functions.

Generalization Results: Table 8 reports average test accuracy across folds for each dataset, with the highest average per dataset bolded.
Generalization Results: Table 9 reports selected-model runtime across folds, with the lowest average per dataset bolded.
Interpretability: SGTs preserve modular decision-tree structure because each node’s shape function operates on only one feature.This supports visualizing the shape function and tracing the model’s root-to-leaf decision process by hand.