On the Power of Decision Trees in Auto-Regressive Language Modeling
This work introduces a novel architectural approach for language modeling, potentially broadening diversity in model development, but it is incremental as it adapts an existing method to a new domain.
The paper tackled the problem of applying Auto-regressive Decision Trees (ARDTs) to language modeling, demonstrating theoretically that ARDTs can compute complex functions like simulating automata and Turing machines, and empirically showing they generate coherent text comparable to a smaller Transformer model.
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.