Learned feature ordering for exact optimal decision tree search: a lightweight neural scoring approach

Abstract

Exact optimal decision tree solvers provide transparent models but face combinatorial search growth, making the order in which candidate features are explored consequential whenever a sound early-stopping bound is reached. Existing solvers largely rely on handcrafted orderings, while the reliability of learned ordering for exact decision tree induction remains insufficiently characterized. We study a lightweight node-only neural scorer that predicts a dataset-specific feature order and inserts it into a dynamic-programming (DP) solver without changing the returned optimum. Across eight capped datasets and 10 paired seeds, per-dataset aggregate state reductions average 8.3% (median 3.6%), but seed-level outcomes comprise 60 wins, 9 ties, and 11 losses with a median reduction of 2.1%; information gain and mRMR remain competitive, and the learned policy regresses in a 60-feature stress test, delimiting the current method’s reliability.