Expected-depth selection for interpretable decision trees

Interpretable decision trees are usually selected by worst-case structural measures such as maximum depth or node count, although many deployments incur cost along the particular root-to-leaf path followed by each case. We study expected depth, the test-sample average number of internal decision tests, as a direct measure of average inference burden. The proposed soft-depth (Soft-D) selector chooses, from a cost-complexity pruning candidate path, the tree with minimum validation expected depth among candidates whose validation accuracy remains within a user-specified tolerance of the best candidate. Across eleven benchmark datasets and 25 outer test folds per dataset, Soft-D reduces expected depth by 47.4% relative to unpruned CART and by 12.1% relative to accuracy-first CCP at [Formula: see text]; a new depth-limited CART baseline confirms that the gain is strongest when a practitioner-selected maximum depth still leaves many samples on long paths. The analysis also shows that ε is a real accuracy-complexity hyperparameter, that refitting after selection can change expected depth in a measurable minority of folds, and that expected-depth selection coincides with node minimization in equal-cost CART paths but separates naturally under heterogeneous query costs. These results position expected-depth selection as a lightweight deployment-time model-selection layer rather than a replacement for globally optimal tree induction.