mlsanityData to 14 Oct 2026

Leveraging Predictive Equivalence in Decision Trees

arXiv 2506.14143 ↗First posted 17 Jun 2025cs.LGcited by 4

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

Decision trees are widely used for interpretable machine learning due to their clearly structured reasoning process. However, this structure belies a challenge we refer to as predictive equivalence: a given tree's decision boundary can be represented by many different decision trees. The presence of models with identical decision boundaries but different evaluation processes makes model selection challenging. The models will have different variable importance and behave differently in the presence of missing values, but most optimization procedures will arbitrarily choose one such model to return. We present a boolean logical representation of decision trees that does not exhibit predictive equivalence and is faithful to the underlying decision boundary. We apply our representation to several downstream machine learning tasks. Using our representation, we show that decision trees are surprisingly robust to test-time missingness of feature values; we address predictive equivalence's impact on quantifying variable importance; and we present an algorithm to optimize the cost of reaching predictions.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 28 of its 75 references that are in the map. First posted on arXiv 17 Jun 2025.

Builds on

28 of 75 references.

References · 28

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,555
  2. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,166
  3. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,070
  4. 2016Distribution-Free Predictive Inference For Regressioncited by 668
  5. 2018All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneouslycited by 373
  6. 2021Interpretable Machine Learning: Fundamental Principles and 10 Grand Challengescited by 367
  7. 2019Predictive Multiplicity in Classificationcited by 166
  8. 2020Generalized and Scalable Optimal Sparse Decision Treescited by 100
  9. 2019On the Existence of Simpler Machine Learning Modelscited by 89
  10. 2022Exploring the Whole Rashomon Set of Sparse Decision Treescited by 81
  11. 2020MurTree: Optimal Classification Trees via Dynamic Programming and Searchcited by 63
  12. 2021What's a good imputation to predict with missing values?cited by 62
16 more
  1. 2021A Theory of PAC Learnability of Partial Concept Classescited by 60
  2. 2024Amazing Things Come From Having Many Good Modelscited by 55
  3. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  4. 2022Predictive Multiplicity in Probabilistic Classificationcited by 44
  5. 2020In Pursuit of Interpretable, Fair and Accurate Machine Learning for Criminal Recidivism Predictioncited by 42
  6. 2020Born-Again Tree Ensemblescited by 38
  7. 2021Fast Sparse Decision Tree Optimization via Reference Ensemblescited by 38
  8. 2023A Path to Simpler Models Starts With Noisecited by 33
  9. 2023The Rashomon Importance Distribution: Getting RID of Unstable, Single Model-based Variable Importancecited by 29
  10. 2022Classification of datasets with imputed missing values: does imputation quality matter?cited by 22
  11. 2022The Missing Indicator Method: From Low to High Dimensionscited by 19
  12. 2013Prediction with Missing Data via Bayesian Additive Regression Treescited by 10
  13. 2022Sharing pattern submodels for prediction with missing valuescited by 7
  14. 2024Interpretable Generalized Additive Models for Datasets with Missing Valuescited by 7
  15. 2018BEST : A decision tree algorithm that handles missing valuescited by 3
  16. 2023MINTY: Rule-based Models that Minimize the Need for Imputing Features with Missing Valuescited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2026REALITrees: Rashomon Ensemble Active Learning for Interpretable Treescited by 1
  2. 2025Efficient & Correct Predictive Equivalence for Decision Treescited by 0
  3. 2026From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMscited by 0
  4. 2026Adaptive Multi-Branching for Shallow Decision Tree Inductioncited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2021Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent
  2. 2025Learning Decision Trees as Amortized Structure Inference
  3. 2026Approximation-Free Differentiable Oblique Decision Trees
  4. 2024GPTree: Towards Explainable Decision-Making via LLM-powered Decision Trees
  5. 2026Learning Tree-Based Models with Gradient Descent
  6. 2023Fair Feature Importance Scores for Interpreting Tree-Based Methods and Surrogates
  7. 2022Mixture of Decision Trees for Interpretable Machine Learning
  8. 2025Talking Trees: Reasoning-Assisted Induction of Decision Trees for Tabular Data