On the Power of Decision Trees in Auto-Regressive Language Modeling

Yulu Gan, Tomer Galanti, Tomaso A. Poggio, Eran Malach

Abstract

Originally proposed for handling time series data, Auto-regressive Decision Trees (ARDTs) have not yet been explored for language modeling. This paper delves into both the theoretical and practical applications of ARDTs in this new context. We theoretically demonstrate that ARDTs can compute complex functions, such as simulating automata, Turing machines, and sparse circuits, by leveraging "chain-of-thought" computations. Our analysis provides bounds on the size, depth, and computational efficiency of ARDTs, highlighting their surprising computational power. Empirically, we train ARDTs on simple language generation tasks, showing that they can learn to generate coherent and grammatically correct text on par with a smaller Transformer model. Additionally, we show that ARDTs can be used on top of transformer representations to solve complex reasoning tasks. This research reveals the unique computational abilities of ARDTs, aiming to broaden the architectural diversity in language model development.

Introduction

While Transformers currently dominate the landscape of Large Language Models (LLMs), their "black box" nature and high computational demands have prompted a search for more interpretable and efficient alternatives. This research explores a classic machine learning structure—the Decision Tree—reimagined for auto-regressive next-token prediction. By framing decision trees as Auto-Regressive Decision Trees (ARDTs), we demonstrate that these simple structures are theoretically as powerful as Turing machines and empirically competitive with small Transformers in specific linguistic tasks.

Methodology: The ARDT Framework

The core innovation is the application of decision trees in an auto-regressive loop. Instead of a single classification pass, the model predicts the next token in a sequence, which is then appended to the input for the subsequent iteration.

The training and inference pipeline involves several key steps:

  1. Token Embedding: Tokens are converted into 100-dimensional vectors using Word2Vec.
  2. Context Aggregation: To handle variable sequence lengths, the model uses a weighted average of past token embeddings with exponential decay, ensuring recent context is prioritized.
  3. Model Training: An ensemble of trees is trained using XGBoost to predict the embedding of the target next token.
  4. Inference and Decoding: During inference, the predicted vector is mapped back to the nearest actual word in the vocabulary via similarity ranking.
The training and inference pipeline for Auto-Regressive Decision Trees (ARDTs).

Theoretical Power and "Chain-of-Thought"

A significant contribution of this work is the theoretical proof that ARDTs can simulate Finite State Automata, Turing Machines, and Sparse Circuits. The mechanism enabling this complexity is the "chain-of-thought" process. By allowing the tree to generate intermediate tokens, it can perform multi-step logic that a single decision tree could not achieve in one pass. For example, computing parity (checking if the number of 1s in a string is even) requires an exponentially large standard tree, but a tiny ARDT can solve it by maintaining state across tokens.

Empirical Results

The performance of ARDTs was evaluated on the TinyStories dataset and a subset of Big-Bench-Hard (BBH) reasoning tasks.

Story Generation

On the TinyStories benchmark, an ARDT ensemble with only 0.3 million parameters outperformed a 1 million parameter GPT-Neo (Transformer) model. Evaluation by GPT-4 on a 10-point scale showed that ARDTs achieved a score of 7.85 for Grammar and 5.39 for Plot, compared to the Transformer's 4.42 and 3.65, respectively.

Interpretability

One of the primary advantages of ARDTs is their inherent transparency. Unlike the opaque attention mechanisms of Transformers, the decision-making process of an ARDT can be visualized as a series of logical splits based on semantic clusters.

An example of text generation and the corresponding interpretable decision tree structure.

Complex Reasoning

When integrated with pre-trained GPT-2 embeddings, ARDTs achieved an average accuracy of 77.4% across selected BBH tasks. This performance is remarkably competitive with much larger models like InstructGPT (70.3%) and PaLM 540B (69.3%) on these specific benchmarks.

Conclusion and Future Work

This research highlights the surprising computational capacity of Auto-Regressive Decision Trees. While they offer significant gains in interpretability and efficiency for small-scale tasks, challenges remain in scaling these models to the massive datasets used for state-of-the-art LLMs. Future work may explore hybrid architectures that combine the linguistic strengths of Transformers with the logical, interpretable branching of Decision Trees.

Summary updated

Abstract

Originally proposed for handling time series data, Auto-regressive Decision Trees (ARDTs) have not yet been explored for language modeling. This paper delves into both the theoretical and practical applications of ARDTs in this new context. We theoretically demonstrate that ARDTs can compute complex functions, such as simulating automata, Turing machines, and sparse circuits, by leveraging "chain-of-thought" computations. Our analysis provides bounds on the size, depth, and computational efficiency of ARDTs, highlighting their surprising computational power. Empirically, we train ARDTs on simple language generation tasks, showing that they can learn to generate coherent and grammatically correct text on par with a smaller Transformer model. Additionally, we show that ARDTs can be used on top of transformer representations to solve complex reasoning tasks. This research reveals the unique computational abilities of ARDTs, aiming to broaden the architectural diversity in language model development.
BibTeX
@inproceedings{gan2024power,
  author = {Yulu Gan and Tomer Galanti and Tomaso A. Poggio and Eran Malach},
  title = {{On the Power of Decision Trees in Auto-Regressive Language Modeling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=nge5deRsEH},
}
Figure