Literati: Towards Anytime Optimal Shape Generalized Trees via AO*
cs.LG
Quick verdict
First optimal shape-generalized-tree induction via AO*, with proofs and strong 24-dataset results; optimality holds only within adaptive discretization.
Summary
The paper introduces Literati, the first algorithm for globally optimal induction of Shape Generalized Trees (SGTs), which replace threshold splits with piecewise-constant univariate shape functions whose change points are bounded. Literati formulates sparse SGT induction as AND/OR graph search that jointly optimizes tree structure (regularizer lambda) and shape complexity (regularizer alpha) under depth and per-node complexity budgets; with an admissible heuristic, AO* yields provable optimality (Propositions 1-2), while DPDT-style adaptive discretization of candidate change points keeps the action space tractable, so guarantees hold only relative to the discretized space. Two anytime enhancements preserve optimality: an inadmissible CART-based secondary heuristic for OR-node selection and round-robin AND-node exploration. On 24 OpenML/UCI datasets, Literati attains the best training accuracy at depths 4-6 and the lowest runtimes among optimal methods at depths 3-5, outperforming DPDT, STreeD, Branches, ConTree and DL8.5 variants; ablations confirm both enhancements help. In generalization tests (15-minute per-fold budget, 200-trial random search), Literati averages 90.6% test accuracy versus 89.6% for runner-up ShapeTAO, with a statistically significant rank advantage (Wilcoxon). Limitations: proof rates collapse at depths 5-6, frequent timeouts on large datasets, optimality is discretization-relative, and the test margin is about one point.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Literati is the first algorithm with global optimality guarantees for Shape Generalized Tree induction, via an AND/OR graph formulation proven equivalent to the regularized objective (Proposition 1, Lemmas 1-2).
- An inadmissible CART-based secondary heuristic for OR-node selection and round-robin AND-node exploration substantially improve anytime performance while provably preserving the optimality of the returned policy.
- Across 24 datasets, Literati achieves the highest training accuracy at depths 4-6 among all evaluated methods and the lowest runtimes among optimal methods at depths 3-5.
- Under a 15-minute per-fold budget with 200-trial random search, Literati averages 90.6% test accuracy, 1.0 point above runner-up ShapeTAO, with a statistically significant rank advantage over all baselines.
- All optimality guarantees hold relative to the adaptively discretized candidate space, not the original continuous feature space.
Strengths
First optimal SGT induction with a complete proof chain
Lemma 1/2 and Proposition 1 (Appendix A.1) show the AND/OR recurrences (Eqs. 3-4) compute exactly the optimum of the regularized objective (Eq. 1), handling edge cases (symmetric f^k convention, exclusion of constant functions, canonical u > max(k) ordering); Proposition 2 proves heuristic admissibility and Corollary 1 gives a valid terminality inequality, and both anytime enhancements are argued not to break guarantees.
Comprehensive, well-instrumented evaluation
24 datasets with OpenML/UCI IDs (Table 3), 10 baselines, 1-hour optimization runs over D in {3..6} and K in {1..3}, plus three discretization configurations (heavy Bd=16, light depth-adaptive, and a PreQuant control vs STreeD in Appendix G.2); per-dataset tables (6-7) with mean +/- std, proof rates, and runtimes.
Anytime design is ablated, not asserted
Honest reporting of failure modes
Unusually strong reproducibility material
Weaknesses
Headline optimality is discretization-relative
Modest, budget-sensitive generalization margin
Practical optimality often unproven at depth
Preprocessing asymmetry only partially controlled
Interpretability claims lack user evidence
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper targets a real gap: Shape Generalized Trees (SGTs; Upadhya and Cohen, NeurIPS 2025) replace threshold splits with piecewise-constant univariate shape functions, but were previously learned only greedily (ShapeCART) or refined post-hoc (ShapeTAO). Literati claims three contributions: (1) an AND/OR graph formulation of sparse SGT induction proven equivalent to the regularized objective (Eq. 1), (2) an AO* solver with two anytime enhancements that provably preserve optimality, and (3) experiments on 24 datasets showing accuracy and runtime superiority. The headline *Optimal* must be read carefully: guarantees hold relative to an adaptively discretized candidate set (Section 3.1.2), not the continuous feature space - the authors state this, but never quantify the resulting objective gap.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is a Shape Generalized Tree (SGT)?
A decision-tree variant where each node's split is not a single threshold (x <= theta) but a learnable piecewise-constant function of one feature that can route multiple value intervals left or right. This captures non-linear feature effects within one node, yielding more compact trees; a bound K on the number of discontinuities (change points) keeps each rule inspectable.
Is Literati's learned tree truly optimal?
It is provably globally optimal - via AO* search with an admissible heuristic - with respect to the discretized set of candidate change points generated adaptively at each node from CART thresholds. Against the original continuous features the solution may not be optimal; the paper acknowledges this and provides upper-bound comparisons to DPDT and CART.
How much better is Literati than standard methods?
On 24 OpenML/UCI datasets it achieves the highest training accuracy at depths 4-6 among tested optimal-tree and greedy methods, the lowest runtimes among optimal methods at depths 3-5, and an average test accuracy of 90.6% versus 89.6% for the runner-up ShapeTAO under a 15-minute per-fold budget, with a statistically significant better average rank (Wilcoxon).
Is code and data available for Literati?
The NeurIPS checklist states that code to replicate the experiments is provided, and all datasets are public (OpenML/UCI identifiers are listed in Table 3). The paper also gives detailed pseudocode (Algorithms 2-6), implementation notes, and full hyperparameter grids for every baseline in Appendix C.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a sampled excerpt: [...sampling gap...] markers skip middle content; the full body of Table 1, the detailed round-robin description (Section 3.2.2), part of the Appendix A.2 proof, and the per-dataset generalization tables (Appendix H) fell inside gaps and were judged only from surrounding prose.
- Figure contents (e.g., Figure 3 anytime curves, CDD bar positions) were not extractable; figure-related assessments rest on captions and the surrounding text.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.