REVIEW 3 major objections 6 minor 300 references
Search order alone can decide whether optimal decision trees finish fast or stall, and two simple priorities beat prior solvers.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.5
2026-07-31 15:44 UTC pith:UTEXHPUR
load-bearing objection Solid subfield engineering paper: a real unification of ODT search plus a useful 18-way bake-off; SOTA margins are real inside their stack but partly confounded by terminal solvers and continuous-feature handling. the 3 major comments →
Search Strategies for Optimal Classification and Regression Trees
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Inside a single AND-OR framework for continuous-feature optimal trees, search strategy is a decisive performance factor: among eighteen strategies, best-first search that prioritizes low-support nodes with low lower bounds proves optimality fastest, and balanced depth-first search (expanding the less-explored child of each AND node) yields the strongest anytime performance; together they surpass prior state-of-the-art solvers on anytime classification quality and cut regression runtime by more than ten times.
What carries the argument
An incremental AND-OR search tree whose three hooks—Select (which unexpanded threshold interval and split to open next), Expand (replace an interval with an AND node and residual intervals), and BackPropagate (push bounds and prune)—instantiate DFS, BFS, LDS, and pure AND-OR as different priority and left/right rules while preserving completeness and optimality.
Load-bearing premise
That earlier solvers can be replayed inside this shared framework with only small, practically negligible differences, so measured gaps really come from search order rather than missing engineering.
What would settle it
Re-implement the same two winning priority rules on top of an independent continuous-feature ODT codebase (or re-run the paper’s framework with each baseline’s original cache, terminal solver, and binarization exactly restored) and check whether the anytime and regression-runtime gaps versus the published baselines shrink below an order of magnitude or lose statistical significance on the same UCI suite.
If this is right
- ODT implementers should default to small-support + low-lower-bound best-first search when the goal is to prove optimality, and to balanced left/right depth-first search when the goal is good trees under a time budget.
- Anytime performance for deeper trees depends more on balancing left and right expansions than on discrepancy neighborhoods around the greedy tree.
- The same Select/Expand/BackPropagate skeleton can host new heuristics without rewriting the whole solver, making strategy ablation routine rather than a full redesign.
- Regression ODT search, previously much slower, becomes practical on the tested continuous datasets once the better strategy is used.
- Future AND-OR solvers outside trees can test whether “small support first” and “balance AND children” transfer as generic control rules.
Where Pith is reading between the lines
- If small-support-first works because it quickly produces tight bounds that prune large siblings, similar “solve cheap subproblems first” priorities may help other branch-and-bound ML models (rules, sparse linear models) with additive structure.
- The weak gains from pure lower-bound AND-OR and from GOSDT-style large-support heuristics suggest that bound quality alone is not enough when the continuous split space is huge; hybrid DFS/BFS switching under memory pressure may become standard.
- Because the framework deliberately omits caching and still wins on numeric data, the field may have over-weighted DP memoization relative to split-interval pruning and terminal depth-two solvers for continuous features.
- A natural next measurement is whether the same two strategies keep their ranking when λ > 0, multi-objective losses, or categorical features are required.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes CODT, a unified AND-OR search framework for optimal classification and regression trees that incrementally expands UnExp threshold-interval nodes via Select/Expand/BackPropagate (Defs. 1–8, Algs. 1–2). Within this framework the authors instantiate and compare 18 search strategies spanning DFS, BFS, LDS, and AND-OR (Table 2; App. B), prove completeness and optimality preservation of the generic loop (Theorems 1–2, App. C), and add a generalized depth-two terminal solver and similarity/interval pruning for continuous features (App. A). Empirically, BFS-Small-LB is best for proving optimality and DFS-Blossom is best for anytime objective integral (OI); against external baselines, CODT reports better classification anytime performance (Figs. 5–6) and more than an order-of-magnitude regression runtime gains (Fig. 7).
Significance. If the results hold under fair attribution, this is a valuable consolidation paper for the ODT community: it replaces scattered, hard-to-compare solver papers with a common algorithmic lens and the largest head-to-head evaluation of search orders to date (18 strategies). The finding that small-support + low-LB BFS beats the large-support heuristic used by GOSDT, and that balanced left/right DFS (Blossom-style) dominates anytime performance at d≥5, are concrete, transferable design lessons. Strengths include stated completeness/optimality theorems with proofs, a clear OI metric with CDFs and Friedman–Nemenyi testing, multi-class and regression coverage, and a continuous-feature depth-2 subroutine. These make the work more than an incremental solver release.
major comments (3)
- [Introduction / Search Framework; App. A–E] Introduction / Search Framework: the central attribution claim—that prior methods are instantiated “exactly or up to small and practically negligible differences”—is load-bearing for both the internal ranking and the SOTA claims (abstract; Figs. 5–7), but is not validated. CODT’s depth-2 terminal solver (App. A.1, Alg. 4), delayed similarity/interval pruning schedule (App. A.2), absence of a cache, root-split multi-threading, and native continuous-feature handling differ from the original ConTree, Quant-BnB, GOSDT, and Branches codebases. Please either (i) ablate these engineering components while holding Select fixed, or (ii) explicitly qualify which gains are attributable to search order versus the shared continuous-feature machinery, and restrict “search strategy” language accordingly.
- [Comparison with the Baselines; App. D–E.3; Figs. 5–7, 15] §Comparison with the Baselines and App. E.3: GOSDT and Branches OOM on the full continuous instances and are only compared on 100-sample subsamples (Fig. 15); Quant-BnB is limited to d≤3; CA-ConTree solves no instance to optimality. The abstract’s “compared to the state of the art … order of magnitude for regression” therefore mixes full-scale runs against ConTree/STreeD/Quant-BnB with handicapped or re-hosted baselines. Strengthen the claim by reporting, for each baseline, the exact problem encoding (binarized vs continuous, λ, depth, threads) side-by-side with CODT-ST, and move OOM baselines out of the main SOTA sentence or into a clearly labeled “binarized/subsample” subsection.
- [Experiment Setup; App. D.2] Experiments / App. D.2: all runs fix λ=0. With zero complexity penalty the search landscape and the value of lower-bound-guided strategies (AOS, BFS-LB variants) can differ materially from the sparse-ODT regime that motivated GOSDT/OSRT/Blossom. At least a small λ-sweep (e.g., λ∈{0,0.01,0.1}·n or per-dataset defaults from prior work) on a subset of datasets is needed to show that BFS-Small-LB / DFS-Blossom remain preferred when sparsity is enforced; otherwise the strategy recommendations are conditional on λ=0.
minor comments (6)
- [Experiments] Code is promised “after acceptance” but is not available for review; a review artifact or anonymous repo would strengthen reproducibility claims.
- [Table 1] Table 1 lists “This paper CODT … Many” under search strategy; a pointer to Table 2 / App. B would help readers map the 18 concrete Select definitions.
- [Metrics; Fig. 2] Fig. 2 and the OI definition use s̄ from CART and s* as best-found-by-any; state explicitly whether s* is pooled across all strategies/baselines (which can slightly favor methods run in the same bake-off).
- [Throughout] Typographical issues: “Brit,a” / “Brit,a” throughout; “andand” / missing spaces in several places; arXiv date “30 Jul 2026” looks like a placeholder.
- [App. B.2; Fig. 10] App. B.2: the dynamic BFS→DFS-Prio memory fallback is important for fairness of BFS memory/runtime CDFs (Fig. 10); report how often it triggered.
- [App. A.3] Clarify whether multi-threaded CODT shares only root incumbents or also lower bounds across feature threads; this affects reproducibility of the multi-thread curves in Figs. 5–7.
Circularity Check
No circularity: empirical runtime/anytime claims measured against external baselines, not quantities forced by construction from fitted inputs or self-citation chains.
full rationale
This is a systems/algorithms paper whose load-bearing claims are empirical CDFs of runtime and objective integral for named search strategies (DFS-Blossom, BFS-Small-LB, etc.) versus external and reimplemented baselines (Quant-BnB, ConTree, CA-ConTree, STreeD, GOSDT, Branches). The AND-OR framework (Defs. 1–8, Alg. 1–2) and the completeness/optimality theorems are ordinary inductive arguments from the stated definitions; they do not define the measured OI or wall-clock times in terms of themselves. Self-citations (MurTree, STreeD, ConTree, Blossom, regression DP) appear as related work and comparison targets, not as uniqueness theorems or ansätze that force the ranking. There is no fitted parameter renamed as a prediction, no self-definitional loop, and no renaming of a known empirical law. Residual concerns about whether prior methods are instantiated only up to negligible engineering differences affect attribution fairness, not circularity under the stated criteria. Score 0 with empty steps is therefore the correct outcome.
Axiom & Free-Parameter Ledger
free parameters (4)
- regularization λ =
0
- time-out t̄ =
15 min
- BFS tie-break ε =
1e-6
- LDS large/small constants M, m =
unspecified large/small
axioms (4)
- domain assumption ODT learning is an AND-OR search over feature tests (OR) and left/right subproblems (AND) with leaf label assignment.
- standard math Valid lower/upper bounds never cut an improving root incumbent (optimality preservation).
- domain assumption Loss is additive over samples (0-1 or SSE) plus λ per branch node; D2 terminal requires element-wise additive cost tuples.
- ad hoc to paper Prior solvers differ from framework instantiations only by negligible implementation details for comparison purposes.
invented entities (2)
-
CODT AND-OR search framework (UnExp threshold intervals + Select/Expand/BackPropagate)
no independent evidence
-
BFS-Small-LB and related support/LB hybrid heuristics
no independent evidence
read the original abstract
Optimal decision trees (ODTs) are compact, interpretable machine learning models that globally optimize a given objective, but their scalability remains challenging. While recent work has proposed a variety of search strategies to improve scalability, the precise contribution of each strategy remains unclear. To address this gap, we introduce a general algorithmic framework for ODTs that instantiates previously used search strategies and enables the definition of new ones. This provides a common lens through which to understand and compare different strategies, which we use to empirically investigate the effect of 18 search strategies. Compared to the state of the art, the best strategy in our evaluation achieves significantly better anytime performance for classification, and improves runtime by more than an order of magnitude for regression.
Figures
Reference graph
Works this paper leans on
-
[1]
Van der Linden, Jacobus G. M. and De Weerdt, Mathijs M. and Demirovi. 2023 , booktitle =
2023
-
[2]
Van den Bos, Mim and Van der Linden, Jacobus G. M. and Demirovi. 2024 , booktitle =
2024
-
[3]
and Van der Linden, Jacobus G
Brița, Cătălin E. and Van der Linden, Jacobus G. M. and Demirovi. 2025 , booktitle =
2025
-
[4]
Van der Linden, Jacobus G. M. and Vos, Daniël and De Weerdt, Mathijs M. and Verwer, Sicco and Demirovi. 2024 , journal =
2024
-
[5]
Denison, David G. T. and Mallick, Bani K. and Smith, Adrian F. M. , number =. 1998 , journal =
1998
-
[6]
1997 , journal =
Esposito, Floriana and Malerba, Donato and Semeraro, Giovanni , number =. 1997 , journal =
1997
-
[7]
2000 , booktitle =
Benbrahim, Houda and Bensaid, Amine , pages =. 2000 , booktitle =
2000
-
[8]
2012 , booktitle =
Min, Fan and Zhu, William , pages =. 2012 , booktitle =
2012
-
[9]
2017 , journal =
Lomax, Susan and Vadera, Sunil , number =. 2017 , journal =
2017
-
[10]
2019 , journal =
Karabadji, Nour El Islem and Khelf, Ilyes and Seridi, Hassina and Aridhi, Sabeur and Remond, Didier and Dhifli, Wajdi , pages =. 2019 , journal =
2019
-
[11]
2014 , journal =
Moro, Sérgio and Cortez, Paulo and Rita, Paulo , pages =. 2014 , journal =
2014
-
[12]
2001 , journal =
Li, Xiao-Bai and Sweigart, James and Teng, James and Donohue, Joan and Thombs, Lori , number =. 2001 , journal =
2001
-
[13]
1992 , journal =
Buntine, Wray and Niblett, Tim , pages =. 1992 , journal =
1992
-
[14]
2026 , booktitle =
Kiossou, Harold and Schaus, Pierre , pages =. 2026 , booktitle =
2026
-
[15]
and Lauwaert, Lode and Reijers, Wessel and Depeursinge, Adrien and Andrearczyk, Vincent and M
Graziani, Mara and Dutkiewicz, Lidia and Calvaresi, Davide and Amorim, José Pereira and Yordanova, Katerina and Vered, Mor and Nair, Rahul and Abreu, Pedro Henriques and Blanke, Tobias and Pulignano, Valeria and Prior, John O. and Lauwaert, Lode and Reijers, Wessel and Depeursinge, Adrien and Andrearczyk, Vincent and M. 2023 , journal =
2023
-
[16]
2024 , journal =
Eng. 2024 , journal =
2024
-
[17]
2014 , journal =
Romei, Andrea and Ruggieri, Salvatore , number =. 2014 , journal =
2014
-
[18]
1984 , booktitle =
Karmarkar, Narendra , pages =. 1984 , booktitle =
1984
-
[19]
2019 , journal =
Leiva, Rafael García and Anta, Antonio Fernández and Mancuso, Vincenzo and. 2019 , journal =
2019
-
[20]
2023 , booktitle =
Semenova, Lesia and Chen, Harry and Parr, Ronald and Rudin, Cynthia , journal=. 2023 , booktitle =
2023
-
[21]
2016 , journal =
Biau, Gérard and Scornet, Erwan , number =. 2016 , journal =
2016
-
[22]
2018 , booktitle =
Agarwal, Alekh and Beygelzimer, Alina and Dud. 2018 , booktitle =
2018
-
[23]
, pages =
Yang, Lingjian and Liu, Songsong and Tsoka, Sophia and Papageorgiou, Lazaros G. , pages =. 2017 , journal =
2017
-
[24]
2022 , booktitle =
Hua, Kaixun and Ren, Jiayang and Cao, Yankai , pages =. 2022 , booktitle =
2022
-
[25]
and Nguyen, Lam M
Zhu, Haoran and Murali, Pavankumar and Phan, Dzung T. and Nguyen, Lam M. and Kalagnanam, Jayant R. , pages =. 2020 , booktitle =
2020
-
[26]
2013 , journal =
Lomax, Susan and Vadera, Sunil , number =. 2013 , journal =
2013
-
[27]
Rasoul and Landgrebe, David , number =
Safavian, S. Rasoul and Landgrebe, David , number =. 1991 , journal =
1991
-
[28]
Barros, Rodrigo Coelho and Basgalupp, Márcio Porto and De Carvalho, Andre C. P. L. F. and Freitas, Alex A. , number =. 2011 , journal =
2011
-
[29]
2021 , journal =
Mehrabi, Ninareh and Morstatter, Fred and Saxena, Nripsuta and Lerman, Kristina and Galstyan, Aram , number =. 2021 , journal =
2021
-
[30]
2022 , journal =
Le Quy, Tai and Roy, Arjun and Iosifidis, Vasileios and Zhang, Wenbin and Ntoutsi, Eirini , pages =. 2022 , journal =
2022
-
[31]
2020 , journal =
Grari, Vincent and Ruf, Boris and Lamprier, Sylvain and Detyniecki, Marcin , number =. 2020 , journal =
2020
-
[32]
1973 , booktitle =
Martelli, Alberto and Montanari, Ugo , pages =. 1973 , booktitle =
1973
-
[33]
2020 , journal =
Miron, Marius and Tolan, Songül and G. 2020 , journal =
2020
-
[34]
2018 , booktitle =
Carreira-Perpin. 2018 , booktitle =
2018
-
[35]
and Meisel, William S
Payne, Harold J. and Meisel, William S. , number =. 1977 , journal =
1977
-
[36]
2012 , journal =
Kirsch, Adam and Mitzenmacher, Michael and Pietracaprina, Andrea and Pucci, Geppino and Upfal, Eli and Upfal, Eli , number =. 2012 , journal =
2012
-
[37]
1989 , journal =
Mingers, John , pages =. 1989 , journal =
1989
-
[38]
2016 , journal =
Mabu, Shingo and Obayashi, Masanao and Kuremoto, Takashi , pages =. 2016 , journal =
2016
-
[39]
, number =
Kass, Gordon V. , number =. 1980 , journal =
1980
-
[40]
2005 , booktitle =
Sun, Juan and Wang, Xi-Zhao , pages =. 2005 , booktitle =
2005
-
[41]
and Hobeika, Antoine G
Sherali, Hanif D. and Hobeika, Antoine G. and Jeenanunta, Chawalit , number =. 2009 , journal =
2009
-
[42]
2017 , journal =
Gupta, Bhumika and Rawat, Aditya and Jain, Akshay and Arora, Arpit and Dhami, Naresh , number =. 2017 , journal =
2017
-
[43]
Nick and Wolberg, William H
Chi, Chih-Lin and Street, W. Nick and Wolberg, William H. , pages =. 2007 , booktitle =
2007
-
[44]
1998 , journal =
Dietterich, Thomas G , pages =. 1998 , journal =
1998
-
[45]
2021 , booktitle =
Aglin, Gaël and Nijssen, Siegfried and Schaus, Pierre , pages =. 2021 , booktitle =
2021
-
[46]
1999 , journal =
Graf, Erika and Schmoor, Claudia and Sauerbrei, Willi and Schumacher, Martin , number =. 1999 , journal =
1999
-
[47]
and George, Edward I
Chipman, Hugh A. and George, Edward I. and McCulloch, Robert E. , number =. 1998 , journal =
1998
-
[48]
2024 , journal =
Gomes Mantovani, Rafael and Horv. 2024 , journal =
2024
-
[49]
2018 , journal =
Chikalov, Igor and Hussain, Shahid and Moshkov, Mikhail , number =. 2018 , journal =
2018
-
[50]
2016 , journal =
Barocas, Solon and Selbst, Andrew D , pages =. 2016 , journal =
2016
-
[51]
and Silverman, Bernard W
Taylor, Paul C. and Silverman, Bernard W. , pages =. 1993 , journal =
1993
-
[52]
2023 , booktitle =
Demirovi. 2023 , booktitle =
2023
-
[53]
1994 , booktitle =
Kohavi, Ron , pages =. 1994 , booktitle =
1994
-
[54]
and Soklic, M
Zwitter, M. and Soklic, M. , url =
-
[55]
2022 , journal =
Liu, Yanchao , number =. 2022 , journal =
2022
-
[56]
2011 , journal =
Hemmateenejad, Bahram and Shamsipur, Mojtaba and Zare-Shahabadi, Vali and Akhond, Morteza , pages =. 2011 , journal =
2011
-
[57]
Mangasarian, O. L. and Wolberg, W. H. , number =. 1990 , journal =
1990
-
[58]
2011 , journal =
Wang, Haizhou and Song, Mingzhou , number =. 2011 , journal =
2011
-
[59]
, number =
De'ath, Glenn and Fabricius, Katharina E. , number =. 2000 , journal =
2000
-
[60]
2002 , journal =
Potharst, Rob and Feelders, Adrianus Johannes , number =. 2002 , journal =
2002
-
[61]
2009 , booktitle =
Kamiran, Faisal and Calders, Toon , pages =. 2009 , booktitle =
2009
-
[62]
2007 , booktitle =
Struyf, Jan and D. 2007 , booktitle =
2007
-
[63]
and Rathee, Anju and Srivastava, Saurabh , number =
Priyam, Anuja and Abhijeeta, Gupta R. and Rathee, Anju and Srivastava, Saurabh , number =. 2013 , journal =
2013
-
[64]
2008 , booktitle =
Maszczyk, Tomasz and Duch, Włodzisław , pages =. 2008 , booktitle =
2008
-
[65]
1998 , journal =
Zhang, Weixiong , pages =. 1998 , journal =
1998
-
[66]
2019 , journal =
Ruggieri, Salvatore , number =. 2019 , journal =
2019
-
[67]
, number =
Freitas, Alex A. , number =. 2014 , journal =
2014
-
[68]
2022 , booktitle =
Subramanian, Shivaram and Sun, Wei and Drissi, Youssef and Ettl, Markus , pages =. 2022 , booktitle =
2022
-
[69]
2005 , booktitle =
Struyf, Jan and D. 2005 , booktitle =
2005
-
[70]
2022 , journal =
Nanfack, Géraldin and Temple, Paul and Fr. 2022 , journal =
2022
-
[71]
1987 , booktitle =
Niblett, Tim , pages =. 1987 , booktitle =
1987
-
[72]
, number =
Hyafil, Laurent and Rivest, Ronald L. , number =. 1976 , journal =
1976
-
[73]
, pages =
Turney, Peter D. , pages =. 1995 , journal =
1995
-
[74]
and Ha, Jungwoo and Rossbach, Christopher J
Davis, Jason V. and Ha, Jungwoo and Rossbach, Christopher J. and Ramadan, Hany E. and Witchel, Emmett , pages =. 2006 , booktitle =
2006
-
[75]
2007 , booktitle =
Freitas, Alberto and Costa-Pereira, Altamiro and Brazdil, Pavel , pages =. 2007 , booktitle =
2007
-
[76]
1993 , journal =
Tan, Ming , number =. 1993 , journal =
1993
-
[77]
and Resick, Patricia A
King, Matthew W. and Resick, Patricia A. , number =. 2014 , journal =
2014
-
[78]
1993 , booktitle =
Oliver, Jonathan , pages =. 1993 , booktitle =
1993
-
[79]
and Smyth, Padhraic , number =
Goodman, Rodney M. and Smyth, Padhraic , number =. 1988 , journal =
1988
-
[80]
and Salzberg, Steven , pages =
Murthy, Sreerama K. and Salzberg, Steven , pages =. 1995 , booktitle =
1995
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.