Research map / Large language models / Agents, code and math
Decision Tree Induction Through LLMs via Semantically-Aware Evolution
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LLEGO, a genetic programming framework that uses an LLM (gpt-3.5-turbo) as semantically-aware crossover and mutation operators for decision tree induction, outperforming greedy, optimal, and GP baselines on 12 OpenML tabular datasets.
Problem
Decision tree induction is NP-complete; greedy methods are suboptimal, exact methods scale poorly and are limited to specific objectives, and conventional GP operators are structural and semantically unaware.
Approach
Use LLMs as variation operators in GP by framing trees as natural-language nested dictionaries: fitness-guided crossover conditions offspring on a target fitness derived from parent fitness, and diversity-guided mutation reweights LLM candidate offspring by their negative log-probabilities via a temperature parameter.
Key results
- At depth 4, LLEGO achieves the best average rank (1.0) across 7 classification datasets, with balanced accuracy e.g. 0.736 on Heart vs 0.669 for GATree-level baselines... (Heart 0.751 vs CART 0.713)
- At depth 3, LLEGO attains average rank 1.6 versus 2.9 for CART, with best results on Diabetes, Heart, Liver and Vehicle subsets among the compared methods (Liver 0.672 vs GOSDT 0.656)
- LLEGO produces superior trees than a GATree configuration with substantially larger search budgets while requiring fewer evaluations
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LLEGO instead of conventional GP operators (GATree) | Decision tree induction · Classification benchmarks, depth 3 | search efficiency | Helped |
| Increase crossover target-fitness parameter α from -0.25 to 0.1 | LLEGO crossover · Offspring generation | offspring fitness | Helped |
| Increase crossover target-fitness parameter α beyond 0.1 | LLEGO crossover · Offspring generation | offspring fitness | Hurt |
| Lower mutation sampling temperature τ | LLEGO mutation · Population search | population diversity | Helped |
| Remove semantic information from prompts (ablation) | LLEGO · Decision tree search | optimization performance | Hurt |
| Remove fitness-guided crossover and use mutation only (ablation) | LLEGO · Decision tree search | optimization performance | Hurt |
| Remove diversity-guided mutation and use crossover only (ablation) | LLEGO · Decision tree search | optimization performance | Hurt |
| Restrict genetic operations to 2 parents (ablation) | LLEGO · Decision tree search | optimization performance | Hurt |
Surprising findings
- LLEGO without semantic information (features renamed to X_i) still performs very competitively, highlighting few-shot ICL strength of LLMs
- Sparse optimal methods DL8.5 and GOSDT remain competitive at depth 3, with the LLEGO advantage concentrated at depth 4
Limitations
- LLM inference adds substantial computational cost relative to conventional GP
- Diversity decreases over generations due to semantic focus, risking premature convergence
- Potential propagation of negative biases from black-box LLMs; fairness addressed only via objective design
Experimental setup
Datasets: credit diabetes compas heart liver breast vehicle cholesterol wine wage abalone cars
Benchmarks: OpenML-CC18 subsets (7 classification datasets) OpenML-CTR23 subsets (5 regression datasets)
Metrics: balanced accuracy mean squared error generalization gap median population fitness diversity
Baselines: CART C4.5 GOSDT DL8.5 GATree
Builds on: genetic programming CART GATree
Closest papers by meaning
- Generative Model for Decision Trees (AAAI 2024 · similarity 0.89)
- AlphaZero-Like Tree-Search can Guide Large Language Model Decoding and Training (ICML 2024 · similarity 0.88)
- Tree-Structured Synergy of Large Language Models and Bayesian Optimization for Efficient CASH (NeurIPS 2026 · similarity 0.87)
- Advancing Tool-Augmented Large Language Models: Integrating Insights from Errors in Inference Trees (NeurIPS 2024 · similarity 0.87)
- OptiTree: Hierarchical Thoughts Generation with Tree Search for LLM Optimization Modeling (NeurIPS 2025 · similarity 0.87)
- Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.