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. 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.
Introduction
Transformers are the undisputed standard for modern Large Language Models (LLMs). However, they are computationally expensive, resource-intensive, and notoriously difficult to interpret—often referred to as "black boxes." Meanwhile, tree-based models like Random Forests and XGBoost remain the gold standard for tabular data due to their efficiency and interpretability, but they are rarely used for language generation.
This paper explores the untapped potential of Auto-Regressive Decision Trees (ARDTs) for language modeling, challenging the assumption that only neural networks can generate coherent text. The authors ask a provocative question: can we adapt decision trees to predict text auto-regressively? And if so, do they possess the computational capacity to handle the complexities of human language and logical reasoning?
The ARDT Architecture
To make decision trees work with sequential text, the authors designed a novel pipeline that adapts traditional tree ensembles for auto-regressive next-token prediction.
- Input Representation: Words are converted into Word2Vec embeddings. The model computes an exponentially decaying weighted average of recent tokens, creating a single vector that prioritizes recent context while maintaining a fixed-size input for the trees.
- Prediction: An XGBoost ensemble takes this aggregated context vector and predicts the embedding of the next word, rather than outputting a direct classification logit over the entire vocabulary.
- Decoding: During inference, the model compares the predicted vector against the vocabulary using similarity ranking. It finds the word whose embedding is closest to the predicted vector and outputs it as the next token.
Key Insights and Interpretability
The theoretical and practical exploration of ARDTs yields several surprising insights into the capabilities of non-neural architectures.
Chain-of-Thought Unlocks Exponential Power: A standard decision tree would need to be exponentially large to compute certain complex functions. However, by allowing the tree to output intermediate tokens auto-regressively, ARDTs can efficiently simulate finite state automata, Turing machines, and sparse circuits. This mathematical formalization of "chain-of-thought" prompting shows that compositional sparsity defeats the curse of dimensionality.
Transparent Decision-Making: Unlike neural networks where activations are abstract and dense, an ARDT's routing can be explicitly visualized. By clustering word embeddings into a lower-dimensional space, individual features (splits) in the decision tree correspond to specific semantic concepts.
You can literally trace a generated word back through the tree to see exactly which previous words or semantic concepts triggered the split (e.g., testing for the presence of the word "Lily").
Empirical Results
It is highly unintuitive that a decision tree ensemble can generate fluent text, yet the empirical results demonstrate genuine potential. The authors evaluated ARDTs across two primary domains:
- Language Generation (TinyStories): On a synthetic dataset of short stories restricted to a 3-to-4-year-old's vocabulary, a tiny ARDT ensemble with only ~0.3 million parameters successfully learned grammar, consistency, and plot progression. It outperformed a 1-million parameter Transformer (TinyStories-1M) across grammar, creativity, consistency, and plot metrics when graded by GPT-4.
- Logical Reasoning (BIG-Bench Hard): The authors tested ARDTs on challenging reasoning tasks (Boolean Expressions, Navigate, Web-of-Lies, Sports Understanding). When trained on top of pre-trained GPT-2 embeddings, ARDTs achieved highly competitive reasoning accuracy. For instance, on the Boolean Expressions task, the ARDT hit 85.3% accuracy, edging out PaLM-540B (83.2%) under the specific conditions of that test.
- Efficiency: Tree inference scales logarithmically with size. The model generated 20 words in about 1 second on a single A100 GPU, highlighting the lightweight nature of the architecture.
Limitations and Future Directions
The authors readily acknowledge that ARDTs do not yet match the performance of modern, large-scale LLMs on broad, unconstrained tasks. Additionally, there is a slight gap between their theoretical proofs (which assume a single tree outputting discrete tokens) and their experimental setup (which uses tree ensembles outputting continuous vectors).
However, the goal is not to replace Transformers entirely. Instead, the authors propose integrating tree-based models into current LLM pipelines. Creating hybrid architectures that combine the advanced language understanding of Transformers with the efficient, interpretable, and logical routing of decision trees represents a highly promising frontier for future NLP research.
Summary updated