Research map / Large language models / Reasoning and chain of thought
On the Power of Decision Trees in Auto-Regressive Language Modeling
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.
Proves auto-regressive decision trees (ARDTs) can simulate automata, Turing machines and sparse circuits via chain-of-thought, and trains XGBoost-based ARDTs on TinyStories and Big-Bench-Hard reasoning tasks.
Problem
Decision trees are not used for language modeling, and it is unclear what functions they can compute when used auto-regressively with intermediate chain-of-thought tokens.
Approach
Use a decision tree as next-token predictor applied auto-regressively over a sliding window, proving that this yields much greater expressive power (automata, Turing machines, sparse circuits) than standard decision trees, and training tree ensembles on Word2Vec weighted-average embeddings for language generation.
Key results
- On TinyStories, ARDTs (0.3M tree nodes) score 7.85 grammar and 7.36 consistency, beating TinyStories-1M (4.42 and 6.32) and approaching TinyStories-33M (7.80 and 9.10).
- On BIG-Bench Hard, GPT-2-embedding ARDTs reach 85.3 on Boolean Expressions and 83.9 on Sports Understanding, versus PaLM 540B's 83.2 and 80.4.
- Theory shows parity needs a decision tree with at least 2^n leaves, while a 2-state automaton computes it with auto-regressive steps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GPT-2 Transformer embeddings instead of GPT-2 word embeddings | ARDTs · Boolean Expressions | accuracy: 72.0 -> 85.3 | Helped |
| Use GPT-2 Transformer embeddings instead of GPT-2 word embeddings | ARDTs · Navigate | accuracy: 55.4 -> 69.2 | Helped |
| Use GPT-2 Transformer embeddings instead of GPT-2 word embeddings | ARDTs · Web-of-Lies | accuracy: 53.2 -> 71.1 | Helped |
| Use GPT-2 Transformer embeddings instead of GPT-2 word embeddings | ARDTs · Sports Understanding | accuracy: 72.3 -> 83.9 | Helped |
| Use GPT-2 Transformer embeddings instead of GPT-2 word embeddings | ARDTs · All Tasks (avg) | accuracy: 63.2 -> 77.4 | Helped |
| Use ARDTs instead of TinyStories-1M | TinyStories · TinyStories | Grammar: 4.42 -> 7.85 | Helped |
| Use ARDTs instead of TinyStories-1M | TinyStories · TinyStories | Consistency: 6.32 -> 7.36 | Hurt |
Surprising findings
- Decision tree ensembles with about 0.3M nodes match or beat a 1M-parameter Transformer on some TinyStories metrics.
- The GPT-2-embedding ARDT beats PaLM 540B on Boolean Expressions and Sports Understanding in the reported table.
Limitations
- Theory is representational only; no learnability guarantees for training ARDTs with chain-of-thought.
- Experiments use tree ensembles on averaged embeddings, deviating from the sliding-window theory setting.
- Reasoning results use only 200 training and 50 test examples per task, and scoring relies on GPT-4 judging for story generation.
Experimental setup
Datasets: TinyStories BIG-Bench Hard
Benchmarks: TinyStories BIG-Bench Hard
Metrics: grammar score creativity score consistency score plot score accuracy
Baselines: TinyStories-1M TinyStories-33M GPT-4 InstructGPT Codex PaLM 540B
Builds on: ARDT time-series work XGBoost Word2Vec TinyStories BIG-Bench Hard
Closest papers by meaning
- Auto-Regressive Next-Token Predictors are Universal Learners (ICML 2024 · similarity 0.85)
- Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models (ICML 2024 · similarity 0.85)
- Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regression (ICML 2026 · similarity 0.84)
- Beyond Autoregression: Fast LLMs via Self-Distillation Through Time (ICLR 2025 · similarity 0.84)
- The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models (NeurIPS 2026 · similarity 0.84)
- Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search (NeurIPS 2025 · similarity 0.84)
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.