Research map / Learning theory and algorithms / Prediction and decision losses

Literati: Towards Anytime Optimal Shape Generalized Trees via AO*

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Optimal decision tree learning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Literati, the first optimal induction algorithm for Shape Generalized Trees, formulating it as AND/OR graph search solved with an anytime-enhanced AO* (secondary informative heuristic at OR nodes and round-robin AND exploration).

Problem

Greedy top-down induction of Shape Generalized Trees (SGTs) yields suboptimal trees with no optimality guarantees, while optimal tree methods are restricted to axis-aligned threshold splits.

Approach

Cast sparse SGT induction as an AND/OR graph where shape functions are built one changepoint at a time, solved by AO* with an inadmissible CART-lookahead heuristic guiding OR selection and round-robin exploration of AND children to improve anytime performance while keeping optimality.

Key results

• At depth 6 with K=3, Literati reaches 92.69% average training accuracy versus 90.50% for LDS-DL8.5 and 89.49% for ShapeTAO (table, averaged over datasets).
• Literati achieves average test accuracy 1.0% higher than the second-place approach, ShapeTAO, with statistically significantly higher average rank than all baselines.
• With K=1 (threshold trees), Literati has lower runtime than DPDT at D=3 (18.22s vs 46.57s) while matching its training accuracy (83.56%).

Surprising findings

• Branches, another AO*-based optimal method, frequently exhausts the 64GB memory limit and degrades in training accuracy with depth.
• Several optimal methods (ConTree, CADL8.5, Branches) show training accuracy decreasing as depth increases under the time limit, due to unfinished searches.

Limitations

• Like other optimal tree methods, struggles to prove optimality on large datasets within short time budgets.
• Adaptive discretization yields optimality only with respect to the discretized candidate space, not the full original space.
• Designed primarily for tabular data, inheriting decision tree constraints.

Experimental setup

Datasets: 24 small-to-medium tabular datasets (QuantBnB benchmark and others)

Benchmarks: 24 real-world tabular datasets (QuantBnB benchmark)

Metrics: training accuracy test accuracy runtime optimality proof rate distance to optimal over time average rank (critical difference)

Baselines: CART AxTAO ShapeCART ShapeTAO Branches STreeD LDS-DL8.5 CADL8.5 ConTree DPDT

Builds on: AO* DPDT Branches ShapeCART TAO

Closest papers by meaning

• Empowering Decision Trees via Shape Function Branching (NeurIPS 2025 · similarity 0.93)
• Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.85)
• Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound (AAAI 2025 · similarity 0.85)
• Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.85)
• TREE-G: Decision Trees Contesting Graph Neural Networks (AAAI 2024 · similarity 0.84)
• Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.84)