Towards Scalable Meta-Learning of near-optimal Interpretable Models via Synthetic Model Generations

Kyaw Hpone Myint, Zhe Wu, Alexandre G. R. Day, Giridharan IyengararXiv 2025 · DOI · arXiv

TL;DR

Researchers have developed a way to bypass the "NP-hard" bottleneck of creating optimal decision trees by using synthetic data generation. By training a Transformer (MetaTree) on millions of synthetically constructed datasets where the "ground truth" tree is known by design, they achieved performance comparable to state-of-the-art methods at a fraction of the computational cost.

What Problem Does This Paper Address?

In high-stakes fields like finance and medicine, "black-box" AI is often a non-starter. We need interpretable models, and decision trees are the gold standard. However, finding the mathematically optimal decision tree for a given dataset is an NP-hard problem. While greedy algorithms like CART are fast, they often miss the "big picture" (global optimality).

Recently, "meta-learning" has emerged as a solution: instead of training a tree from scratch, we train a large neural network (like a Transformer) to look at a dataset and immediately "predict" the best decision tree. The catch? To train such a meta-learner, you need millions of examples of (Dataset $\rightarrow$ Optimal Tree) pairs. Generating these pairs using traditional optimal solvers is so slow that it makes large-scale pre-training impossible.

Methods

The authors propose a "constructive" synthetic data pipeline that flips the problem on its head. Instead of finding the best tree for a random dataset, they build datasets that are designed to be solved by specific trees.

  1. SCM Generation: They use Structural Causal Models (SCMs) to generate synthetic features and labels, ensuring realistic relationships between variables.
  2. The "Alignment" Trick: They fit a standard CART tree to this synthetic data. Then—and this is the key innovation—they relabel the original data using the CART tree’s predictions and add 5% noise. This ensures the dataset is "intrinsically aligned" with a tree structure.
  3. Quality Filtering: They discard datasets that are too easy (perfectly separable) or too messy (extreme class imbalance), ensuring the meta-learner sees high-quality, challenging examples.
  4. Meta-Learning: They feed these millions of synthetic datasets into MetaTree, a Transformer architecture. The model learns to map a set of data points directly to a near-optimal, look-ahead decision tree.

Datasets

  • Pre-training: A massive synthetic dataset of 20 million examples generated via their SCM pipeline. This is double the size of previous efforts in this niche.
  • Evaluation: To prove it works in the real world, they tested the model on 91 diverse, hand-curated real-world datasets (the same benchmark used in the original MetaTree paper).

Key Insights and Ideas

  • Synthetic Data as a Shortcut: You don't need a "perfect" solver to generate training data. By relabeling data to match a tree's output, you create a "ground truth" that is near-optimal by construction.
  • Constant-Time Scaling: Traditional optimal solvers (like GOSDT) explode in computation time as you add features or depth. The synthetic pipeline’s complexity remains constant, taking under 1 second regardless of tree depth.
  • The "Noise" Sweet Spot: Interestingly, adding a moderate amount of label noise (around 10-30%) during pre-training actually improves the model's final inference accuracy. It likely acts as a form of regularization, helping the Transformer generalize to messy real-world data.
  • Model Complexity "Sweet Spot": For a fixed amount of data (100k samples), a 2-layer Transformer outperformed deeper 12-layer versions, suggesting that "bigger is better" only holds if you scale the data and model in lockstep (consistent with the Chinchilla scaling laws).

Key Results

  • Performance Parity: The MetaTree trained purely on synthetic data achieved an average accuracy of 0.6956, nearly matching the 0.7047 achieved by a model trained on expensive, hand-curated real-world data.
  • Speedup: While optimal solvers like GOSDT took nearly 200 seconds to find a tree of depth 6, the synthetic generation method stayed under 1 second.
  • Ensemble Strength: When used in ensembles (30 trees), the synthetic MetaTree outperformed GOSDT and stayed competitive with the heavily optimized CART algorithm.

Limitations and Future Work

While the paper demonstrates excellent scalability, a few areas remain open for exploration:

  • Tree Depth: The experiments primarily focused on relatively shallow trees (depth 2-6). Scaling this to very deep trees while maintaining interpretability is a challenge.
  • Feature Types: The current work leans heavily on binary and tabular features; extending the SCM pipeline to handle more complex, high-dimensional data types would be a logical next step.
  • Architectural Iteration: The authors note that because synthetic data is "cheap," they can now iterate on Transformer architectures much faster than before, potentially leading to even more specialized "tree-predicting" models.

Summary updated

Abstract

Decision trees are widely used in high-stakes fields like finance and healthcare due to their interpretability. This work introduces an efficient, scalable method for generating synthetic pre-training data to enable meta-learning of decision trees. Our approach samples near-optimal decision trees synthetically, creating large-scale, realistic datasets. Using the MetaTree transformer architecture, we demonstrate that this method achieves performance comparable to pre-training on real-world data or with computationally expensive optimal decision trees. This strategy significantly reduces computational costs, enhances data generation flexibility, and paves the way for scalable and efficient meta-learning of interpretable decision tree models.
BibTeX
@misc{myint2025towards,
  author = {Kyaw Hpone Myint and Zhe Wu and Alexandre G. R. Day and Giridharan Iyengar},
  title = {{Towards Scalable Meta-Learning of near-optimal Interpretable Models via Synthetic Model Generations}},
  year = {2025},
  eprint = {2511.04000},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.04000},
  howpublished = {arXiv},
}

Loading related content...

Figure