On the Power of Decision Trees in Auto-Regressive Language Modeling
Authors: Yulu Gan
Tomer Galanti
Tomaso A Poggio
eran malach
Venue: NeurIPS 2024 poster (2024)
Keywords: Decision Trees
Auto-Regressive
Language Models
Primary area: learning_theory
TL;DR: This paper explores Auto-regressive Decision Trees for language modeling through theoretical and empirical analysis, showing their ability for complex computations and coherent text generation.

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.

On the Power of Decision Trees in Auto-Regressive Language Modeling
Yulu Gan
Tomer Galanti Texas A&M University galanti ttamt.. edu
Massachusetts Institute of Technology yulu@csail mit. edu
Tomaso Poggio
Eran Malach
Massachusetts Institute of Technology tp@csail.m mmt. edu
Harvard University eran www.mmallggaiil.comm com
Abstract
Originally proposed for handling time series data, Auto-regressive Decision Trees (ARDTs) have not yet been explored for language modeling. This paper explores 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 computationall efficiency of ARDTs, highlighting their surprising computational power. Empirically, we train ARDTs on simple language generation tasks, showing that they can learn generate coherent and grammatically correct text par with smaller Transformer model. Additionally, we show that ARDT' can be used top of transformer representations solve complex reasoning tasks. This research reveals the unique computational abilities ARDTs, aiming to broaden the architectural diversity in language model development.
Introduction
In recent years, Large Language Models (LLMs) have achieved outstanding results in tasks such as natural language understanding, coding, and mathematical reasoning. LLMs predominantly utilize the Transformer architecture Vaswani et al. (2023), establishing it as the standard in this field. However, recent initiatives (Gu Dao 2023 Sun et al. 2023 Ma et al. 2023 De et al. 2024) have begun to challenge the dominance of Transformers. These alternatives, while not yet matching Transformer performance, offer advantages in terms of inference time efficiency. Moreover, some works are revisiting traditional non-neural network models for language modeling, such elassical symbolic models (Wong et al.) 2023). These developments indicate a shift towards diverse, efficient, and interpretable language modeling methodologies.
Tree-based models, particularly favored for handling tabular data (Grinsztajn et al. 2022), continue to hold significant importance. While tree-based methods mostly used for classification and regression tasks, Auto-regressive Decision Trees (ARDTs) (Meek et al. 2002) have been studied for time-series prediction, offering simpler and more interpretable alternative to complex nonlinear approaches. Although the ARDT approach was not originally designed for language tasks, it has demonstrated considerable promise in various time-series datasets, outperforming traditional auto- regressive models while maintaining ease of interpretation. Motivated by these results, our study seeks explore the potential of ARDTs for language prediction tasks, assessing whether they could serve as a viable, interpretable alternative to complex, resource-intensive language models.
Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.

---

Input Prompt:
together
Once upon a time,
f19>-0.992
N
Outputs:
lily
there was little girl named Lily. She loved play outside in sunshine. One day. she saw a big tree in the garden. She was so excited about it.
F2> 2.084
19 23117
belt
kids
lily
calorful
F5>-2:17
F18B-0.644
F2-1277
f7=2.148
ever
because
loved
Fily
(a)
(b)
Figure 1: (a) An example of story continuation generated by our Auto- cuto-Reeressive Decision Trees. We decision trees and, remarkably, attain results comparable Transformer-basee models in terms of linguistic fluency. (b) The decision process of the decision trees. We visualize part of the tree ensemble, and can observe which word most relevant for the splitting rule at each node.
To understand the power of ARDTs, first conduct theoretical studies demonstrating that ARDTs, using decision trees as next-token predictors, can compute more complex functions than traditional decision trees. We explore the classes of functions ARDTs simulate functions computed by automata, Turing machines, or sparse circuits through intermediate "chain-of-thought" computations. We provide bounds on the size, depth, and run-time (measured by the number of intermediate tokens) required for ARDTs to simulate these function classes. Our findings highlight the surprising computational capabilities of ARDTs, underscoring their potential as powerful and interpretable alternative for language prediction tasks requiring complex function computations.
compute, showing their ability to
Our experimental results further demonstrate the practical utility of ARDT' in language generation tasks. Utilizing standard auto-regressive inference methods, these models generate output sequences token-by-token, appending each new token to the input of the subsequent iteration. When trained on the TinyStories dataset[Eldan & Li (003), ARDTs produce coherent and grammatically accurate text (see in Fig D Notably, decision tree ensembles with approximately 0.3 million parameters outperform Transformer model with around 1 million parameters on the same Tinystories dataset, highlighting their efficiency despite a smaller size. We discuss our approach to training interpretable decision trees, which enhances the transparency of the decision -making process language generation. Furthermore, we assess the ability of tree-based models to execute various logical reasoning tasks. Notably, ensembles built on top of transformer embeddings and trained on specific downstream tasks perform comparably to larger general models like InstructGPT Ouyang et al.) (2022) and PaLM-540B Chowdhery et al. (2022), under the conditions of these particular tasks.
Our contribution can summarized as follows:
We extend the application of ARDTs to language prediction tasks, adopting a novel approach that capitalizes on their inherent simplicity and interpretability. This aims to broaden the architectural diversity in language model development.
Through theoretical analysis, we demonstrate that ARDTs can compute a broader array of complex functions than previously recognized, including the simulation of automata, Turing machines, and sparse circuits. These theoretical findings deepen our understanding of ARDT'' computational capabilities.
Our experimental results offer empirical evidence that ARDT' are capable of generating coherent and grammatically correct text, perform well compared more complex models like small Transformers, and demonstrate solid reasoning abilities.

---

2 Related Work
Decision Trees. Tree based models have been widely used for solving different classification and regression tasks machine learning (Navada et al., 2011). The ID3 algorithm was introduced by Quinlan (1986), and has been widely used for decision tree learning, along with the CART (Breiman ct al. 1984; Lewis 2000) algorithm. Decision tree ensembles, such as random forests (Breiman 2001 and gradient boosted trees (Friedman 2002), also very popular. Despite continuous advancements in deep learning, decision tree ensembles still outperform neural network based models on tabular datasets (Shwartz-Ziv & Armon, 2022). Different from traditional decision trees, auto-regressive decision trees to perform language prediction tasks more efficiently.
Learning Theory for Decision Trees. There are a few theoretical works studying the power of decision trees in solving machine learning problems. The work of Brutzkus et al. (2020) shows that the ID3 algorithm can learn sparse functions in some setting. Kearns & Mansour (1996) show that decision trees are equivalent to boosting methods for amplifying the performance of weak learners on the distribution. Other works focus on other aspects of decision tree learnability (Rivest [987] Blum 1992 Ehrenfcucht & Haussler 1989 Bshouty & Burroughs 2003). We note that from the approximation point of view, decision trees can be regarded as splines with free knots. For instance, piecewise constant hierarchical splines functions, similar to neural networks with threshold activation also be seen as decision trees. Note that ReLU networks can be viewed as piecewise hierarchical linear splines (Anselmi et al., [2055] Yarotsky (016)). and so decision trees can represent ReLU networks (see AAytekin (2022)) ) though possibly with an exponential number of parameters. We note that none of the works mentioned above studies the theory of auto-regressive decision trees, which is novel contribution of our paper.
Decision Trees for Language. Despite gaining popularity in several fields of machine learning, tree based models are not widely used for language generation. Past works have utilized auto-regressive decision trees for time-series analysis (Meek et allaal22000 (2002). or use trees for basic language modeling (Potamianos & Jelinek 1998). Decision trees were also used in parsing (Magerman 1995 Heeman 1999; Nallapati & Allan 2002). modeling syntax (Filimonov) 2011) and language identification
(Hakkinen & Tian 2001)
3 Theory
To explore the capabilities of ARDTs, we initially undertake theoretical studies demonstrating that using decision trees as next-token predictors enables ARDTs to process significantly more complex functions than "standard" decision trees. Firstly, we define the theoretical setting of our analysis in Section 3.1 We then examine the various classes of functions that ARDT can compute, as discussed in Sections 3.2 3.3 and 3.4 Here, the computation involves the ARDT receiving an input sequence, such as question, generating series of intermediate tokens that describe the thought process, and finally producing the output token. Specifically, we demonstrate that functions computed by Automata, Turing machines, sparse circuits can be emulated by an ARDT using these intermediate "chain-of-thouu -houuhhhhh" computations. Additionally, we provide bounds on the size, depth, and runtime (measured by the number of intermediate tokens) required for ARDTs to simulate these classes of interest. Our findings affirm that ARDTs, by leveraging decision trees for next-token prediction, can handle far more complex functions than "standard" decision trees.
Comment 1. The results this section are representation results. That is, we study which functions can, in theory, be represented by auto-regressive decision trees. We do not provide any formal results on whether such functions can be learned from data. The question of how decision trees can be trained to produce "chain-of-thowe responses to input questions is beyond the scope of this work.
3.1 Setting
We adapt the standard definition of decision tree, as described by Quinlan (186)). to include modifications that allow for the processing of vector sequences of arbitrary lengths. Firstly, we establish vocabulary ID. which serves as our token dictionary. Next, we define an input embedding V ID + Rdd For any sequence of tokens E TD>,, V(()) E Rexd represents the embedding applied individually to each token. The space comprising sequences of d-dimensional vectors is denoted by
3

---

X' R'xd, Subsequently, we define a decision tree T that receives an input æ E X' and outputs token y E D..
In our experiments, detailed Section we apply a weighted-average operator to the word vectors of the sequence, where the average vectors are used analysis we study different approach for using decision trees over vector sequences, where instead of averaging word vectors we "concatenate" them. That is, the decision tree is applied to the L most recent words, in a "sliding window" fashion. We note that experimentally we observed that both the "sliding-window" window" and the weighted-average approach produced similar results, and use the Seighted-averagee technique in our experiments for computational reasons.
input to the decision trees. For the theoretical
We start by defining decision tree T that gets inputs of fixed length L, namely T R..dd ID. We refer to the value J. as the context length of 'T, and this value will correspond to the maximal length of a sequence that affects the computation of the tree. In this case, we treat the input x E TR Lxd as a vector, and let T be a standard decision tree operating on vectors of size L d. Namely, T is defined by a binary tree, where each node corresponds to an input feature Fi and some threshold E R. Each leaf corresponds to some output token y E DB The output of the tree T is computed by starting the root, and for each internal node with feature Ii,j and threshold т, moving to the right node if Ti 2 and otherwise moving to the left node. When reaching leaf, we output the value y E D' corresponding to the leaf. The size of the tree T is the number of leaves in the tree, and its depth is the maximum length of a path from root to leaf. Note that the runtime of computing the output of T corresponds to the depth of the tree.
Now, given some tree over length-T. inputs T Lxd + D. we apply T to an input of arbitrary length X' using the following simple rule: if x: has length shorter than I., we pad it to length L by prepending the input, adding additional padding ((PAD)) tokens at the beginning; if æ is longer than L, we apply T only to the last tokens œ. This induces decision tree with arbitrary length inputs T X D.
the tree T as next-token predictor function, applied over some input using auto- regressive computation. That is, we define a sequencc-to-sequeeee predictor T D + D' induced from the tree T as follows: for every input D". recursively define Sn+i+1 and let TTA(()) (s....... decision tree (ARDTT).
Finally,
((
(8n-1, 8nt.. We call AR an auto-regressive
In the rest of this section, we will analyze the capacity of ARDTs to simulate some function classes. Following Malach (2023), we give the following definition:
Definition For some class F of functions f D - D, we say F can be simulated by auto-regressive decision-trees in length complexity T, if for every f E F there exists TAR s.t. for all E Id",, we have T.AR f(s) (where A.R indicates the output of o ARR at iteration T).
In other words, we say that the tree AR can compute the function f, if given some input sequence 8, it generates 7 tokens followed by the correct output f fs). That is, allow the tree use T intermediate tokens as "chain-of-thoughr" before outputting the correct answer.
3.2 Simulating Automata
An automaton A is defined over an alphabet Σ, using set of states Q, an initial state go E Q and transition function ó: Q x Σ - Q. We always assume that | 2 2 and [Q] 2 2. The automaton A gets an input string
>n, and computes an output state A(x) Q by starting at state qo and at each iteration i transitioning to the next state based on the i-th token 24, namely qi = 8()) The automaton then returns the state reached at the final iteration.
Let Auut is the class of all functions computed by automata over strings of length n. Namely, JAur is the class of functions " Q s.t. for all f FAut there exists automaton A s.t.
A(x) = f(x) for all æ E E".
The class of functions computed by Automata has been well-studied from the early days computer science theory (Hopcroft et al.) 200T), and has various important connections to language problems. This class of functions is also interesting in the context of reasoning tasks for language modeling. For

---

example, the Web-of-Lies and Navigate problems in the Big- Big-Bench Hard dataset (Srivastava et al. 2023] can be solved by finite state Automata.
We show that ARDTs can simulate Automata:
Theorem 3. Let ID E LUQU ((PA))) Then, F can be simulated by ARDTs of size o (Df) depth Ollog Di) and context length L 2 n, in length complexity ((n).
Note that ARDTs simulate Automata very efficiently: the total run-time of the ARDT guaranteed by Theorem 3 is (n log [[), which corresponds the time it takes read all the input bits. In this sense, no a gorithh can simulate Automata significantly faster than ARDT.
In the proof, we construct ARDT that, at every iteration i, outputs the state of the Automaton at step i (denoted qi). The state at step i is only a function of the i-th state, given by the most recent token generated by the model; and the i-th input, which is always given by looking back n + 1 tokens. over the input, can compute the transition matrix
Therefore, a simple tree, applied as a sliding- to find the next state. The full proof is given in Appendix A
Next, we show that the above result implies a separation between ARDTs and standard decision trees. Specifically, we show that if we use decision-tree over the input to directly predict the final output of the Automata, without outputting intermediate states, then the size of the decision tree must be exponential in the length of the input:
Theorem 4. There exists some FAut s.t. any decision tree that computes f has size 2 .(22)..
This shows that the fact that ARDTs can perform intermediate computations auto-regressively (e.g., perform thain-of-thoughs significantly improves their efficiency To prove the result, we show that computing the parity of a sequence of bits (i.e., whether the number of bits is even odd) requires tree of exponential size, but can be easily computed by simple 2-state Automaton.
Proof of Theorem 4 with Σ 2 and
Consider the binary alphabet Σ = (0.1) and the state set Q = {even, odd}, 2. We define function Σd - as follows:
evven if Σ 2, mod 2 0,
f(x)
odd otherwise.
The function f describes the parity of the sum of bits in x can efficiently computed by an automaton that toggles between states even and odd upon encountering 1.
Suppose a decision tree T computes f. We claim that the size of must be least 2", Assume for contradiction that T has fewer than 2n leaves. Since T is a decision tree, we assume that all its leaves are reachable by some input
13
Consider leaf of T reached by some input x, at depth less than n. This implies that there exists at least one bit index [n] such that no decision node in T queries x, the path to l. Define x' E [0,1]" by flipping zÿ in x, while keeping all other bits unchanged:
if if
x =
if
Since x' alters x only the unqueried index j. follows the same path in and reaches the same leaf I. Therefore, T(x) Txx'). However, the definition of f guarantees f f(x) # f(x') as their parities different, leading a contradiction. Thus T cannot compute with fewer than 2 leaves.
'This is an example of how compositional sparsity can defeat the curse of dimensionality (Poggio 2022). function may not be approximated by decision tree without an exponential number of parameters but may be represented efficiently by composing intermediate sparse functions, ARDTs do.
5

---

3.3 Simulating Turing Machines
Turing machine M is defined over an alphabet Σ, using a space set Q. initial state go E Q and transition function 8 Q x E - Q x Σ x (LEFT), (RIGHT)). The Turing machine has a tape, where each cell contains a symbol from Σ. The head of the Turing machine is initialized at the leftmost cell on the tape in state do E Q. At each iteration of the machine, it reads the symbol E E and given the head state E Q uses ó(g. s) to determined the new state of the head, the symbol to write under the head, and whether to move the head left or right on the tape.
In our setting, we consider Turing machines with fixed memory M, i.e. Turing machines with access to tape with M cells. In particular, this means that the Turing machine . operate inputs with < M tokens. At the initial step, the input is written on the tape. If the imput size is shorter than M, we add empty tokens {0} E Σ after the input sequence. We consider Turing machines with fixed runtime T, namely we let the machine run for T iterations and then halt it. The output of the machine is the rightmost symbol the tape after T iterations. So, we define M EM + E to be the function computed by the machine after I' steps. We denote by F Turrnng the class of functions computed by M,T Turing machines with memory of size M and runtime T.
Comment 5. Turing machines are typically defined with infinite number of tape cells, and are allowed run arbitrarily long before halting. However, for every given input length, any computable function always uses fixed memory and run-time (which depend on the input length).
We now show any Turing machine with fixed memory and run- run-time time can be simulated by an ARDT:
Then, F Fariis can be simulated by ARDTs Theorem 6. Ler = EUQU (SEP) P
size size O (ID*)) depth Ollog DI) and context length M 3, with length complexity O(MT).
To prove the result, we show that an ARDT can compute the state of the Turing machine at each iteration. Specifically, we encode the state of the machine as sequence of tokens from D, where put a token g E Q C D indicating the state of the head before the token that the head reads. This way, the transition between states is function that only depends locally the tokens surrounding the position of the head, where all other (non-state) tokens can be copied as-is from one state to the next. Similarly to the proof in the previous section, this operation can be realized by small sliding-window tree. The full proof is given in Appendix A
3.4 Simulating Sparse Circuits
circuit over some alphabet defined as a direeted-acccelie-gaapl (DAG), with input nodes and one output node. Each internal (non-input) node with l incoming edges corresponds to some function g * + Σ computed by the node over its incoming inputs. For some input æ E l", the output of the circuit C is the value of the output node, when setting the input nodes of C to Z1...., In. The size of the circuit is the number nodes in the computational graph. We say that k-sparse, if the maximal in-degree of every node in the graph is k. Denote by F the class of functions computed by k-sparse circuits of size N.
N.k
We note that sparse circuits are an extension of sparse Boolean circuits, and so can represent Turing machines with bounded memory (Arora & Barak 2009). In this sense, this class is "equivalent" to the class of functions computed by Turing machines. However, some functions may be more efficient to compute using sparse circuits, and so it is interesting to understand how ARDTs can directly simulate sparse circuits, as demonstrated in the following theorem:
Theorem 7. Let Eu ((PA))) Then, Circuit can be simulated by ARDTs of size o N DD log ml)) and context length 2 N, in length complexity ONN).
We introduce new separator token (SEP), that is used during the generation of the ARDT, but is not part of the alphabet state set of the Turing machine.

---

Proof of Theorem Z Consider s-spar circuit C with N total nodes, where N - are internal nodes. Let -n Σ be the functions computed at the internal nodes, ordered topologically so that each function depends only on the inputs or the results of preceding nodes. Let 9N-n denote the function computed by the output node.
Define fi - - Σ as the output of the i-th node in this ordering, considering all inputs and outputs from previous nodes. Each f; effectively k-Junta. By Lemma 10, there exists a decision tree Ti of size O (D) such that (x)() fi()) for all æ E gn+i-1
To accommodate inputs æ E Y.,, we modify each tree Ti to ignore the first N - n i+ inputs. This adaptation does not affect the size of the tree.
Let z = ((PAD)) E {0, 1j, Construct a tree as follows: begin with the rightmost branch of the tree, using functions h1,1,... hi.d: ,,N -n..n........................... NN- For each node i E [N n1] and each
bit j E [d]. define:
(1)ss 2 1} h (1)((z); <1}
z = 1,
if = 0.
Attach tree TN-n-i+1 at each left node (i,
Observe that during the i-th iteration, the string begins with N - n i(AD) tokens, allowing T to process the pertinent part of the input. After N n iterations, the constructed tree calculates the output token as specified by C.
4 Experiments
In this section, we experimentally validate the capabilities of ARDTs as demonstrated in the previous section and prove their language modeling potential. In Section 4.2 we first train a model based on ARDT' and test its ability to continue stories on Tinystories Eldan & Li (2033), which involves extending narratives similar to finite state automaton. ARDTs generate coherent text that builds on existing stories, also requiring the interpretation of complex contexts and emotions. This showcases the effectiveness of sparse circuits managing significant yet limited inputs.
we assess the model's 's reasoning abilities on the Big- hig-BBech-HHee Heach Suzgun et al. (2022) dataset, where tasks often involve evaluating the truthfulness of propositions, effectively emulating a Turing machine as it processes inputs to determine a definitive outcome (true or false).
Additionally, in Section 4.3
4.1 Setting
To align with the theory section, we designed our experiments to closely mirror the theoretical settings as closely as possible. We here provide a detailed description of our implementation of Auto-regressive Decision Trees (ARDTss for next-token prediction tasks. Our objective is to utilize ARDTs as a language model that receives a sequence of input tokens Zi,... In and predicts the subsequent token Ix+1- Initially, we employ a Word2 embedding Mikolov et al. (2013). denoted by V. to convert the sequence tokens into word embeddings (x1),..... V(r,), ), V ( E IR 200
We then compute weighted average of these embeddings with exponential decay. prioritizing the most recent tokens: 전 = Σm= a" -++1 (x:), where a E (0. 1). Using XGBoost Chen & Guestrin (2016), we train an ensemble of decision trees, T. which takes the input vector V and predicts the embedding of the next token (I aiming to minimize the mean squared error (MSE) loss. We train this model using sequences of varying lengths sampled from our dataset. During inference, the model generates text regressggessyvell. At each step. it receives the current sequence U, outputs the predicted embedding of the next token u TT()), and identifies the token whose embedding is closest to this prediction, i.e., & = arg min, || [xr) úill- This token is then used as the next token in the sequence. The input vector is updated with the new token using 4- aT + (&)) and the process repeats for the next iteration. Figure 2 illustrates the training and inference pipeline.
Comment 8. We note that the setting described above deviates from the theory setting. 1) While the theoretical analysis focuses on the representational power of single auto ruto-regressive decision tree, the experiments utilize ensembles of decision trees. Notably, tree ensembles are more expressive, which suggests that our positive findings should also extend to these ensembles. 2) For simplicity, our theoretical study examines trees that generate a single output token in each iteration, rather than producing word vector, which is the approach used in the experiments. 3) The decision trees
7

---

Train
Inference
Step generate's 'V'
Stop
Stop
Model
Decision Trees
Once upon a time,
girl
Xiboout
Similarity Ranking
Gir
She
Weightid Yawaage
Topt
Build Dataset
Model
Decision
Weighti Beaage
XGboo
Next Tokan
Wiighted Average
Sliling Window
Word2Ves
Embeddingg-
Word2Vee
Vectors
Original Data
Input
colors
playing
Once upon time,
Prompt:
Figure 2: The Pipeline of Our Method. (a) Training. First, we employ a Word2 model to convert words into embeddings. Next, utilize sliding window approach construct dataset for training decision trees. Within this window, we performed a weighted average calculation, and the following token after the window was used as the label. (b) Inference. We our trained Decision Trees for the purpose of next-token prediction.
discussed theoretically operate on concatenated token vectors within a sliding window, in contrast to the use of vector averages in the experimental setting.
4.2 The Ability Generate Coherent Stories
We ARDTs' ability to generate stories with the TinyStories Eldan Li (2023) dataset, which is widely-used high-quality synthetic dataset of short stories that contain words that 3 to 4-year-old child can understand, generated by GPT-3.5 and GPT-4. Details can be found in Appendix B.2
For experiments conducted on TinyStories, we strictly follow Eldan & Li 2023 and employ the multidimensional score provided by GPT-4, as detailed in Appendix B.5
For baselines to compare with ARDTs, we selected several Transformer-basee models. These include two small Transformers trained on the TinyStories dataset (TinyStories- 1M and TinyStories- 33M Eldan & Li (2023)), as well as GPT-4 OpenAl et al. (2023), to illustrate the performance differences between non-neural network methods and the Transformer architecture.
For our evaluation, we provide the models with 100 story beginnings (refer examples in Ap- pendix B.4). each consisting of fewer than 6 words, generated by GPT-4. We use these beginnings as inputs to the model, allowing the perform next token prediction, ultimately generating outputs of 20 words. For the ground truth row in Table we grade complete stories from the dataset.
As shown in Table [ ARDTs achieved performance comparable GPT-4 and TinyStories-33M on four metrics: grammar, creativity, consistency, and plot. Our model outperforms Stories 1M, Transformer-based model with 1M parameters, despite being smaller in size. These results demonstrate that although tree-based models are generally considered inferior to large neural networks, surprisingly, they can compete with small Transformers when trained on the TinyStories dataset.
4.3 Evaluating ARDT' in Language Reasoning Tasks
now explore the potential of using decision trees for logical reasoning tasks using the Big- Big-Bench- Hard dataset. The Big-Bench-BBR dataset, detailed in Appendix B.2 contains 23 challenging

---

Table Experiment Results on TinyStories: The results show that an auto-regressive tree can achieve better performance as the GPT-Neo architecture and exhibit competitive performance compared to both GPT-4 and TinyStories-33M.
Model Architccture
Parameters"
Grammart
Creativity
Consistency
Plotf
TinyStories-IM M
GPT-Neo
IM
4.42
2.70
6.32
3.65
TinyStories-33M
GPT-Nco
33M
7.80
6.87
9.10
7.65
GPT-4
GPT-4
1800B
9.93
8.51
9.32
8.24
Ground Truth
8.21
6.32
7.87
7.56
ARDTs (Ours)
Decision Tree 0.3M
7.85
4.10
7.36
5.39
For our decision trees, we report the total number of nodes the ensemble as parameter count. To minimize the impact of inconsistency on our results and enhance the robustness of our evaluation metrics, we calculated the average scores from ten assessments for each of the 100 stories. Each story was evaluated ten times using the same prompt provided to GPT-4.
reasoning tasks from the BIG-Bench benchmark. We selected four representative reasoning tasks for evaluation, with examples provided in Appendix B.2
Each task involves training a separate decision tree ensemble. These ensembles utilize a weighted average of input word embeddings, described in Section 4.1, using the word embedding layer from pre-trained GPT-2 model trained on WebText. Each model is trained with 200 examples and tested on 50 examples. We also experiment with decision trees trained top of pre-trained GPT-2 Transformer model, where the output vectors from GPT-2 serve as input features for the decision trees, combining GPT-2's advanced language understanding with the analytical capabilities of decision trees.
For establishing baselines, we follow the methodology of Suzgun et al. (2022) and use accuracy as the metric. InstructGPT, Codex, and PaLM 540B are used as baselines.
As presented in Table 2 our model demonstrates substantial effectiveness in reasoning tasks, with performance comparable state-of-the-ar methods. For instance, we observe improvements of 7.4% in Boolean Expression tasks, 2% in Navigate tasks, and 7.8% in Sports Understanding tasks. Moreover, we find that further enhancements are possible by integrating decision trees with the GPT-2 Transformer, underscoring the significant impact of word embeddings on performance. However, his paper focuses on highlighting the potential of the ARDTs architecture, not word embeddings. Our results show that the ARDT's model has strong reasoning abilities.
Table 2: Experimental Results on BIG-Bench-Hard. Lin: Linear Embedding: GPT: GPT-2 Embedding. The results demonstrate that ARDTs possess good reasoning capabilities.
Srivastava et al. 2023)
Ours
BIG-Bench Hard
Human-Rater InstructGPT Codex PaLM 540B
Random
SOTA
Lin
GPT
Boolean Expressions
50
68.5
79.4
90
88.4
83.2
72.0
85.3
Navigate
50
81.9
62.4
55.4
69.2
Web-of-Lies
50
59.6
81.3
51.6
51.6
51.2
53.2
71.1
Sports Understanding
50
68.1
70.8
71.6
72.8
80.4
72.3
83.9
All Tasks (avg)
50
63.1
78.4
70.3
65.8
69.3
63.2 77.4
5
Discussion
The findings in this paper demonstrate that tree- based models have potential in language generation. Although they do not yet match the performance of large language models, they possess certain advantages that make them valuable for studying the emergence of intelligence Decision trees are easier to interpret (see Appendix for more on interpretability using ARDTs), simpler to understand and analyze mathematically, and fast to train. Moreover, unlike standard neural
smaller scale.

---

networks, the inference time for decision trees typically increases logarithnically with their size: tree with depth can have 2d nodes but only requires traversing O(d) nodes per input.
This paper serves as a preliminary exploration into using ARDT's for language modeling tasks. We aim to inspire further research that integrates tree-based models into current language model pipelines, leveraging their unique strengths to enhance language generation capabilities. We believe incorporating tree-structured models into hybrid models with Transformers could be promising direction for future research.
References
Anselmi, F., Rosasco, L., Tan, C., and Poggio, Deep convolutional networks are hierarchical kernel machines. Center for Brains, Minds and Machines (CBMM) Memo No. 035, 2015.
Arora, S. and Barak, B. Computational complexity: a modern approach. Cambridge University Press, 2009.
Aytekin, C. Neural networks are decision trees, 2022.
Bird, S., Klein, E., and Loper, E. Natural language processing with Python: analyzing text with the natural language toolkit. O' Reilly Media, Inc.", 2009.
Blum, A. Rank-r decision trees subclass of r-decision lists. Information Processing Letters, 42 (4):183-185, 1992.
Breiman, Random forests. Machine learning, 45:5-32, 2001.
Breiman, L., Friedman, J., Olshen, R., and Stone, C. Classification and Regression Trees. Wadsworth Publishing, 1984.
Brutzkus, A., Daniely, A., and Malach, E. Id3 learns juntas for smoothed product distributions. In Conference on Learning Theory, pp. 902-915. PMLR, 2020.
Bshouty, N. H. and Burroughs, L. On the proper learning of axis dii--prrllll concepts. The Journal of Machine Learning Research, 4:157-176, 2003.
Chen, and Guestrin, C. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16 pp. 785- 794, New York, NY, USA, 2016. ACM. ISBN 978-1 4503--223--2 doi: 10.1 10.1145/99997722233755. URL http://doi. acm. org/10..///0 11w.11139///9222.1 2939785
Chowdhery, A., Narang. S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., Schuh, P., Shi, K., Tsvyashchenko, S., Maynez, J., Rao, A., Barnes, P., Tay, Y., Shazeer, N., Prabhakaran, V., Reif, E., Du, N., Hutchinson, B., Pope. R., Bradbury, J. Austin, J., Isard, M., Gur-Ari, G., Yin. P., Duke, T., Levskaya, A., Ghemawat, S., Dev, S., Michalewski, H., Garcia, X., Misra, V., Robinson, K., Fedus, L., Zhou, D., Ippolito, D., Luan, D., Lim. H., Zoph, B., Spiridonov, A., Sepassi, R., Dohan, D.. Agrawal, S., Omernick, M., Dai, A. M.. Pillai, T. S., Pellat, M., Lewkowycz, A., Moreira, E., Child, R., Polozov, O., Lee, K., Zhou, Z., Wang, X., Sacta, B.. Diaz, M., Firat, O., Catasta. M., Wei, Meier-Hellstern K., Eck, D., Dean,
J., Petrov, S., and Fiedel, N. Palm: Scaling language modeling with pathways, 2022.
De, S., Smith, S. L., Fernando, A., Botev, A., Cristian-Murary G., Gu, A., Haroun, R., Berrada, L., Chen, Y. Srinivasan, S.. Desjardins, G., Doucet, A., Budden, D., Teh, Y. W., Pascanu, R., Freitas, N. D., and Gulcehre, C. Griffin: Mixing gated linear recurrences with local attention for efficient language models, 2024.
Ehrenfeucht, A. and Haussler, D. Learning decision trees from random examples. Information and Computation, 82(3):231-246 1989.
Eldan, R. and Li, Y. Tinystories: How small can language models be and still speak coherent english?, 2023.
Filimonov, D. Decision tree-based syntactic language modeling. University of Maryland, College Park, 2011.
10

---

Friedman, J. H. Stochastic gradient boosting. Computational statistics & data analysis, 38(4): 367-378, 2002.
Grinsztajn, L., Oyallon, E., and Varoquaux, G. Why do tree-based models still outperform deep learning typical tabular data? Advances in Neural Information Processing Systems, 35:507-520, 2022.
Gu, A. and Dao, Mamba: Linear-time sequence modeling with selective state spaces, 2023.
Hakkinen, and Tian, J. N-gram and decision tree based language identification for written words. In IEEE Workshop Automatic Speech Recognition and Understanding. 2001. ASRU'OI., pp- 335-338. IEEE, 2001.
Heeman, P. A. Pos tags and decision trees for language modeling. In 1999 Joint SIGDAT Conference on Empirical Methods Natural Language Processing and Very Large Corpora. 1999.
Hopcroft, J. E., Motwani, R., and Ullman, D. Introduction automata theory. languages, and computation. Acm Sigact News, 32(1):60-65, 2001.
Kearns, M. and Mansour, Y. On the boosting ability of top-down decision tree learning algorithms. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 459-468, 1996.
Lewis, R. J. An introduction classification and regression tree (cart) analysis. In Annual meeting of the society for academic emergency medicine in San Francisco, California, volume 14. Citeseer, 2000.
Ma, X., Zhou, C., Kong, X., He, J., Gui, L., Neubig, G., May, J., and Zettlemoyer, L. Mega: Moving average equipped gated attention, 2023.
Magerman, D. M. Statistical decision-tres models for parsing. arXiv preprint cmp-lg/9504030, 1995.
Malach, E. Auto-regressive next-token predictors are universal learners. arXiv preprint arXiv:2309.0699 06999, 2023.
Meek, C., Chickering. D. M., and Heckerman, D. Autoregressive tree models for time-series analysis. In Proceedings of the 2002 SIAM International Conference on Data Mining, pp. 229-244. SIAM, 2002.
Mikolov, T. Chen, K., Corrado, G., and Dean, J. Efficient estimation of word representations in vector space, 2013.
Nallapati, R. and Allan, Capturing term dependencies using a sentence tree based language model. In Proceedings of CIKM, volume 2, pp. 383-390. Citeseer, 2002.
Navada, A., Ansari, A. N., Patil, S., and Sonkamble, B. A. Overview of use of decision tree algorithms in machine learning. 20/1 IEEE control and system graduate research colloquium, pp. 37 42. IEEE, 2011.
OpenAl, Achiam, J., and Steven Adler, e. Gpt-4 technical report, 2023.
Ouyang, L.. Wu, J., Jiang. X., Almeida, D.. Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F,, Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback, 2022.
Poggio, T. Compositional sparsity: a framework for ml. Center for Brains, Minds and Machines (CBMM) Memo No. 138, 2022.
Potamianos, G. and Jelinek, study n- n-gram and decision tree letter language modeling methods. Speech Communication, 24(3):171-192, 1998.
Quinlan, J. R. Induction of decision trees. Machine learning, 1:81-106 1986.
Rivest, R. L. Learning decision lists. Machine learning, 2:229-246. 1987.
11

---

Shwartz-Ziv, R. and Armon, A. Tabular data: Deep learning is not all you need. Information Fusion, 81:84-90, 2022.
Srivastava, A., Rastogi, A., and Abhishek Rao, e, a. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models, 2023.
Sun, Y., Dong, L.,, Huang. S., Ma, S., Xia, Y., Xue, J., Wang, J., and Wei, F. Retentive network: A successor to transformer for large language models, 2023.
Suzgun, M., Scales, N., Schärli, N., Gehrmann, S., Tay, Y., Chung, H. W. Chowdhery, A., Le, Q- V., Chi, E. H., Zhou, D., and Wei, Challenging big-bench tasks and whether chain-of-thougee can solve them, 2022.
van der Maaten, L. Barnes-hut-sne, 2013.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, Attention is all you need, 2023.
Wong, L., Grand, G., Lew, A. K., Goodman, N. D., Mansinghka, V. K., Andreas, J., and Tenenbaum, J. B. From word models to world models: Translating from natural language to the probabilistic language of thought, 2023.
Yarotsky, D. Error bounds for approximations with deep relu networks. CoRR, abs/ / 660000 145, 2016. URL http:://axxiv..rgg//b/////1
12

---

A Additional Proofs
For any D. let [[og([D)) and let v D - {0, 1]d be one-to-one mapping of tokens to Boolean vectors, s.t. v (s) for all E D.
Definition 9. A function D > D is called k-Junta if there exists set of separate indexes i,....,ik
ig E [L] and function g D - ID s.t. f(x) g(.
Lemma 10. For every k-Junta f Tt - D, there exists a tree T of size O (ID)*) and depth Okk log [DI s.t. T(V(2))= f( for all a ED.
Proof. Let T the perfect binary tree of depth dk, where each level of the tree corresponds to a pair (i1) [k] x [d], and all the nodes at the level implement the condition (x;,;,) 1. Observe that in this construction, each leaf correspond specific choice of values for v// (zig),... y...: (Ze.) and can set its output to be g(r....... Diy..
Proof of Theorem 3 Let A be some automaton, defined by transition function d xxE - Q. and we can arbitrarily extend it to 8 D2 + D s.t. 8(x, (PAD)) qu for all x E ID. Then, from Theorem 10 there exists some tree T of size O(DI)) s.t. for all æ D holds that T( (x)) = 8 [ TL-n).
We prove by induction that for all i E [n]] it holds that (x) automaton A iteration i.
where is the state of the
Let Z
LLd be the padded output of (xx), i.e. ((((AD)) ..... ((PA))) (Z1). (xx))- Note that since zL-n (PAD)
we have TAR(()) = T(z) = 8(FL, (PAD)) = Q1.
Assume that 7 (x) = (41 1) Therefore,
T (xx) ((VD(()D), ,..., (PAD), $1...., Fnz 91.. -----11))))) 9--1))
= -8(9)-1, qi
Therefore, the required follows.
Proof of Theorem 6 We encode the state of the Turing machine by a string E DD as follows: if the head is in state q E Q and at position E [M], and the memory is mı..... ma E Σ, we set That is, we add token indicating the state of the head before the cell where the head is located. Let 8 Q x Σ function of the Turing machine. We define the following function
s = (m1,.... m4-1, q, m,..... mas).
Ex (LEFT) (RIGHT) } be the transition + D4:
22
if Ø 22,
Q
q
if Æ1 E Q and ((x, (g, a, (RIGHT))
a
=f E Q and 8(x1, 22) = (g, a, (LEFT))
g(s)
a
if T2 E Q and 8( 4z) = (g, a, (RIGHT))
21
if
E Q and 8(12,
(g,a, a, (LEFT))
32 if rg and 8(13,, n.a) (q, o, (RIGHT))
9 if Øz E Q and 8(13, x44) (g, a, (LEFT))
Observe that the function f M+1 + M+ s.t. f((s) g(; 1, 1 8,42) exactly defines the transition between the encoded states of the Turing machine. Namely, if the state the machine at iteration is 8, then the state at iteration + 1 is ((s). We slightly modify g to handle the generation of the first iteration, as follows:
(SEP)
21 = (PAD) and x2 = (PAD) and I3 = (PAD)
(PAD) and D2 (PAD) and 33 * (PAD) (SEP) 22 (SEP)
(())
g(s)
otherwise
13

---

Now, from Lemma 10 there exists tree T of size O(DI)) s.t. T(V(x)) = [(z1 22, 23. T.a).
Let $1...., 8T MD the encodings of the state of the Turing machine iterations 1...., ...,..,, T. Let a E IT2 be the encoding of the input, staring with (PAD) tokens, followed by one (BOS) token and the input string. Denote the output of the ARDT TAR after T (M 2) given the input æ, where split the output into chunks of size M + 2 by:
T AR (z)
(Zi...., 2T) E DF-(++2) 2; E D
Claim: For all i E [2], it holds that 2; = ((SEP), 8t).
Prove: We prove by induction on
For i 1, notice that the input begins with (PAD) tokens, followed by the input tokens 21...... TMM and therefore by definition of 9 we get = ((SEP) .i,..., AMM = ((SEP). s1).
Assume the required holds for First, observe that
Zi+1,1 = (VV (SEP) si, 8t,M+1) = (SEP)
Now, assume that 2,+1,1:j (SEP) 5:41,1 ................................ $1+11-1). Therefore
2+1.-1 7 s st.++1......... M4, (SEP) ; .1........... $41.-11)
= / 11, 8i+l.j
and by induction we get 1 (SEP)) 81+1)
Therefore, T outputs the final token iteration after T(M + 2) steps of auto-regression, which proves the theorem.
B
Additional Implementation Details
B.1 Hardware & Computational Cost
Our experiments conducted single NVIDIA A GPU. For the Tiny Stories experiments, the training process took approximately hour, and required about second to generate 20 words during the inference phase.
B.2 Dataset Details
Tiny Stories. shown in Tab. 3 the training and validation datasets of Tiny Stories contain 147,273 and 21,990 stories, respectively. We use NL.TK Bird et al. (2009) as the tokenizer to obtain 420,351,665 and 4.329,96, tokens from the training dataset. In the training dataset and validation dataset, the number of words in the vocabulary is 27,455 and 11,273, respectively.
BIG-Bench-HRad is dataset contains the selection of difficult tasks from the BIG-Bench. These tasks are identified by their resistance to being outperformed by prior language model evaluations when compared the average human evaluator. The BIG-Bench- Bench-Hard Hard tasks often demand complex, multi-step reasoning, and the use of few-shot prompting without CoT, as previously utilized in SaaluatiosSSSivassaaaa
BIG-Bench evaluations Srivastava et al. (0023), significantly underrepresents the true potential and performance of language models.
Four representative reasoning tasks select for evaluate ARDTs:
(1) Boolean Expressions. Example: not (True) and (Truc). Answer: False
(2) Navigate. Example: If you follow these instructions, will you return to the starting point? Instructions: Turn left. Take steps. Turn right. Answer: No.
(3) Web-of-Lies. Example: Delbert tells the truth. Delfina says Delbert lies. Antwan says Delfina tells the truth. Does Delfina tell the truth? Answer: No.
(4) Sports Understanding. Example: Is the following sentence plausible? "Elias Lindholm beat the buzzer." Answer: No.
14

---

Table Basic Information about the Tinystories Dataset.
Training dataset
Validation dataset
The number of stories
147.273
21,990
The number of tokens
420,351,665
4,329,963
The word count of each story. Vocabulary
54 5,498
63 4,254
27455
11274
B.3 Details about the Visualization of the Decision Trees
To enable visualization that treats words as features, as shown in Algorithm [ we map word embeddings into lower-dimensional space. This process utilizes three primary inputs: word embeddings W in an N x 100 matrix, where N represents the number of words and 100 the dimensionality of each embedding; cluster centers C in x 100 matrix, indicating 20 clusters within the 100-dimensional embedding space; and a mapping matrix M sized 100 x 20, designed to reduce the embeddings' dimensionality to 20. The algorithm begins with an orthogonalization procedure, applying QR decomposition to the transpose of C' (C*) and returning the first 20 columns of QT, thereby establishing an orthogonal basis for the cluster space. then projects the word embeddings W into this diver-dimensional space by multiplying them with the mapping matrix M. By iterating over each word embedding in W, the algorithm applics this projection and ultimately returns set of transformed embeddings {E,...., EN ). where each E; provides lower-dimensional representation of the corresponding word embedding. This approach allows us to treat each vector value individual words, facilitating more intuitive understanding of the data.
Algorithm 1 Map Word Embeddings Lower Dimensional Space
input
Word Embeddings W C IR 10000
Cluster Centers C C I 100
Mapping Matrix M C IR 100
procedure ORTIIOGONALIZE()
Q, R + QR Decomposition C*) return Q[:,: 20).T end procedure
procedure MAPEMBEDDINGS(WV, M) return W.M M end procedure
M ORTHOGGNAALIZE(C) for each word embedding w; in W do
E, t MAPEMBEDDINGS((U,, end for Return [E,...,EN] En}
B.4
The Story Beginnings Used Our Evaluation
In Table we provide 10 examples over 100 story beginnings used for experiments Tiny Stories.
B.5 An Example on Multidimensional Scores
As an example, we took the story that appears in the example above and it after the word "loud". We generated a completion of stories using our ARDTs and baselines, then we prompted GPT-4 to first provide a verbal assessment and then grade the completion. The transcript of interaction is as follows, with the parts produced by GPT-4 in italic font:
15

---

Table 4: Generated Chain-of-Thought data for boolean expression.
Input Prompt
not not not False )) is
True and False and True and True is
Let's think step by step.
Let's think step by step. Remember that (i) pressions inside brackets are always evaluated first and that (ii) the order of operations from highest priority to lowest priority is "not", "and", "or", respectively. We first simplify this expression "Z" follows: "7 True and False and not True and True A B" where "A = True and False" and "B = not True and True". Let's evaluate A: A = True and False = False. Let's evaluate B: B not True and Truc not (True and True) = not (True) False. Plugging in A and B, we get: Z = A and B False and False = False. So the answer is False
Remember that expressions inside brackets are always evaluated first and that (ii) the order of operations from highest priority to lowest priority is "not", "and", "or", respectively. We first simplity this expression "Z" as follows: "Z= not not not (False) ))= not not ( (A) )" where "A = not False
Generated Prompt
)". Let's evaluate A: A not (False)
False True. Plugging in we get: Z= not not A = not not (True) not not False = True. So the answer is True.
Table 5: Generated Chain-of- -houught data for navigation.
you follow these instructions, you return to the starting point? Al- ways face forward. Take 2 steps right. Take steps Take 7 steps right.
If you follow these instructions, do you return to the starting point? Turn around. Take step. Take 6 steps. Turn around. Take 6 steps. Take 9 steps. Take 1 step.
Input Prompt
Let's think step by step. We start at the origin (0, 0), facing the posi-
Let's think step by step. We start the origin (0.
0), facing the positive y-axis. (1) Turn around: (0,
tive y-axis.(1) Always face forward:
0), facing the negative y-axis. (2) Take step: (0,
(0, 0). facing the positive (2)
1)), facing the negative y-axis, (3) Take 6 steps: (0,
Take 2 steps right: (0, 2), facing the
-7), facing the negative y-axis. (4) Turn around:
positive y3axis.(3) Take 9 steps left: (0, -7), facing the positive (4)
(0, -7), facing the positive y-axis. (5) Take 6 steps:
Generated Prompt
(0, 1), facing the positive y-axis. (6) Take 9 steps:
Take 7 steps right: (0, 7). facing the
(0, 8), facing the positive y-axis. (7) Take step:
positive y-axis. Since (0. 0) is (0, 0). we are indeed where started.
(0, 9), facing the positive y-axis. Since (0, 9) is
not (0, 0).
where started. So the
So the answer Yes.
answer No.
Table Examples of the story beginnings generated by GPT-4. In the inference phase, we fed these story beginnings generated by GPT-4 into the ARDTs to continue writting the stories.
The beginning of the stories (GPT-4 generated)
1
Kitty found bright, lost treasure.
2
Thirsty, they sought hidden pond.
3
Roxy climbed, seeking icy hill's peak. Billy's idea sparked an unlikely friendship.
4
5
Leaves underfoot, Roxy ascended triumphantly.
6
Daisy, small yet happy, met Max.
7
Max's 's playful antics delighted tiny Daisy. Suc's thoughtful gesture warmed her mother. A candle's 's flame united mother, daughter. The sad cow wished for companionship.
8
9
10
16

---

the following exercise, the student is given a beginning of story. The student needs to complete it into full story. The exercise tests the student's language abilities and marks the separator between the prescribed beginning and the student's completion:
creativity. The symbol
Once upon a time, *** there was a little girl named I Lily. She loved to play outside in the sunshine. One day, she a big tree in the garden. She so excited about it.
Please provide your general assessment about the part written by the student (the one after the se* symbol). Is it grammatically correct? it consistent with the beginning of the story? Pay special attention to whether the student manages to complete the sentence which is split in the middle by the separator ses,
This is a charming and whimsical story about little girl named Lily who feels excited upon discovering big tree in the garden.
The grommar is generally correct.
Overall, the student's 's completion of the story demonstrates adequate language abilities and creativiry. However, adding more details about Lily's 's exploration, as well as her thoughts and actions after discovering the tree, could make the story more engaging and vivid.
Now, grade the student's completion terms of grammar, creativity, consistency with the story's 's beginning and whether the plot makes sense. Moreover, please provide your best guess of what the age of the student might be, as reflected from the completion. Choose from possible age groups: A: 3 under. B: 4-5. C: 6-7. D: 8-9. E: 10-12. F: 13-16. Grammar: 9/10, Creativity: 4/10, Consistency: 7/10, Age group: E (10-12)
C Interpretability
One advantage of using decision trees over complex neural networks is the Interpretability of the computational process. Unlike neural networks, which rely on abstract vector operations in high- dimensional space, decision trees implement relatively simple logic, computing their output based on splitting criteria that may be easily displayed to, and interpreted by, humans. That said, recall that decision trees operate on aggregations of word vector embeddings, which make interpretabiliity harder to achieve. Specifically, each splitting rule of the decision tree is based on the value of single coordinate, which does not necessarily have an interpretable semantic value when using rotation-invariant word embedding methods such as Word2Vec.
150
forest
park
colorful
phope
50
they
loved
found
shared
lifestyle
belt
-50
llly
equally
ever because
listen n
climb
-150
-100
-50
300
Figure 3: t-SNE van der Maaten (2013) visualization of 20 cluster centers. We selected 20 cluster centers and display 4 words closest to the cluster centers.
In order to generate decision trees with meaningful splitting rules, we modify the word embedding such that single coordinates have specific semantic values. To achieve this, we begin by clustering all the word vectors from the dataset (over 16K words) into 20 clusters using K-means. We then
17

---

Input Prompt:
kids
11x-3
"Ully Tom to play together,
1b-2517
and they found"
loved
f10-2-70
knOW
B-1.057
112-6.700
SONE
colorial
together
190-0.991
Iogetner
PVTT
Po-0.330
shared
Mz-0.50 S19
logether
(39-1-00
1332.003
10x00.86
thored
Mp-9.320
belt
15
[6-0463
SBOW
177-2207
Figure 4: Track the decision-making process within the decision trees. We use 'Lily and Tom loved play together, and they found' the input prompt and generate the next word using ARDTs. We visualize part of the process within the decision tree. Specifically, we visualized 31 nodes of the first decision tree.
Top Feature Importances in XGBoost Model
together
bel
colorful
ever
loved
because
Features
lifestyle
forest
climb
park
listen
shared
they
equally
worth
0.0025
0.0050
0.0075
0.0100 Importance
Figure 5: Feature Importance. We present the feature importance of the top 20 words most closely associated with each cluster, based their average gain.
choose one representative word for each cluster, by taking the word that is closest to the center of the cluster in the embedding space (see Figure 3 an illustration of the clusters and representative words). Now, these words (represented as vectors) form basis for new 20-dimensional embedding space, which is linear subspace of the original 100-dimensional space Werd2Vec. We use these basis words to compute the new word embedding, by projecting each vector from the original space into this subspace, Mathematically, if #1...... F' are the basis words, we define our new embedding & into R& by: (xx) = arg minzer= ||E; 2, (xx;) - (zr))l,, Observe that each basis word æ; mapped by + to unit vector eq. Intuitively, the i-th coordinate of the embedding & now represents words that are
representating the projection a linear combination of basis words.
18

---

semantically similar to the word 2;, Now, splitting rules based on the coordinate can be interpreted as "testing" whether a word similar to z, appears the sentence.
We visualize one of the decision trees trained on the Tiny Stories Dataset using the new "interpretable" emhedding + in Figure [] Note that, unlike complex neural network architectures, which carry opaque computations, the decision process of the ARDT with the new embedding appears to be semantically meaningful. For example, observe that the word Lily appears for three times as the most relevant word during node splits. Considering Lily is frequently occurring name in the Tiny Stories dataset, it's frequent appearance the tree can be deemed reasonable. We further analyze the importance of different features by plotting their importance score. We plot the importance of each cluster, represented by single word, in Figure [5] We assess the importance of each cluster by calculating its average gain during every split within the model.
In Figure M example to visualize part of the decision-man maaion process of the first decision tree in the ensemble. We note that each feature corresponds
the input sentence "Lily and Tom loved to play together and they found" as
single cluster, represented by a single word, e.g. the feature f2 corresponds to the word "Lily". That is, the word "Lily" will be mapped to the unit vector 62 (0, 1, ...,, 0). Note that most words (besides the 20 words used basis for the embedding). will be mapped to linear combination of the basis words, and so can also affect (positively or negatively) the value of the feature f2. Since the input vector is weighted- average of the embedding of all words, the decision when splitting on the feature f2 may be affected by multiple words in the sentence.
19

---

NeurIPS Paper Checklist
596
1.
Claims
598
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
598
600
Answer: [Yes]
Justification: The abstract and introduction clearly state the main theoretical and empirical contributions in this paper.
602
603
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
605
606
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
607
608
NA answer to this question will not be perceived well by the reviewers.
609
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
610
611
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
613
2.
Limitations
614
Question: Does the paper discuss the limitations of the work performed by the authors?
615
Answer: [Yes]
616
Justification: See the Discussion section.
Guidelines:
618
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
619
620
The authors are encouraged to create a separate "Limitations" section in their paper.
821
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
623
625
628
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
627
628
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
630
832
634
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
635
636
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
637
638
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
840
642
644
3. Theory Assumptions and Proofs
645
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
20

---

648
The theoretical results and their assumptions are explicitly stated in The proofs are provided in the main text and the supplementary material.
Justification:
649
650
Guidelines:
651
The answer NA means that the paper does not include theoretical results.
652
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
653
654
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
656
658
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
659
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
682
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
683
664
685
Answer: [Yes]
666
Justification: The experimental results and how to reproduce them are fully disclosed the experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
670
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
672
673
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
674
675
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
676
677
679
680
681
682
683
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
685
687
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
689
680
891
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
882
683
684
685
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
696
697
688
5. Open access to data and code
21

---

701
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
702
704
Answer: [Yes]
705
Justification: The paper provides all the information about the data, models, and implemen- tation. Code will be available upon publication.
708
Guidelines:
The answer NA means that paper does not include experiments requiring code.
709
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
710
httiii/gguidess//deubbbbbla wwwplmmmiiiioooooiiioooooo Policy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
712
714
715
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips.
716
717
hudii///uuidessoeeSuubbii hat////ooSSuSiisseeeeeee wetaaubbiiiiiiiii httpauuiiisisoooooooioooooo onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
719
720
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
721
722
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
724
725
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
726
727
6. Experimental Setting/Details
728
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
729
730
Answer: [Yes]
Justification: The paper provides detailed explanations of the implementation and settings.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
736
The full details can be provided either with the code, in appendix, as supplemental material.
738
739
7. Experiment Statistical Significance
740
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
742
Answer: [Yes]
743
Justification:
The experiments examine all the configurations.
744
Guidelines:
745
The answer NA means that the paper does not include experiments.
746
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
748
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
750
22

---

752
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
753
754
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
756
757
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
758
780
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
781
763
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
788
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
767
788
789
Answer: [Yes]
770
Justification: We disclose all of the information about the computational resources in the section about the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
774
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
776
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
777
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
779
780
781
9.
Code Of Ethics
782
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research follow the NeurIPS Code of Ethies.
786
Guidelines:
787
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
788
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
789
790
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
793
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
795
Answer: [Yes]
796
Justification: Please refer to the Discussion section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
799
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
23

---

801
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairesss considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
802
804
805
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
807
809
811
812
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
814
815
816
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
817
818
819
820
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
822
823
824
Answer: [NA]
825
Justification:
No new data or models are released.
826
Guidelines:
827
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
829
831
832
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
835
837
12. Licenses for existing assets
838
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
840
Answer: [Yes]
842
Justification: The authors are the creators.
843
Guidelines:
844
The answer NA means that the paper does not use existing assets. The authors should cite the original paper that produced the code package dataset.
845
846
The authors should state which version of the asset used and, possible, include URL.
847
848
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
849
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
850
851
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, thcoe com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
853
24

---

856
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is available online, the authors are encouraged to reach out to the asset's s creators.
856
857
858
859
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
861
Answer: [Yes]
863
Justification: The paper describes in detail the implementation of the new methods and the code used for the experiments.
865
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
868
The paper should discuss whether and how consent was obtained from people whose asset is used.
871
872
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
874
14.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
876
878
Answer: [NA]
879
Justification: The paper does not involve crowdsoureing nor research with human subjects.
880
Guidelines:
881
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
882
883
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
884
885
886
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
888
889
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
890
891
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
893
895
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
887
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
889
900
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
902
903
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
905
906
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
25


Reviews:
[{"review_id": "BSJaAz0Qxe", "reviewer": "Reviewer_o5To", "summary": "* This work studies theoretical and practical applications of auto-regressive decision trees (ARDT) in language generation and reasoning tasks.\n* Through theoretical analysis, the authors show that ARDTs can learn more sophisticated functions than previously known, such as automata, Turing machines, and sparse circuits.\n* Using ARDT with a transformer (GPT-2), they achieved performance comparable to SoTA models (InstructGPT, Codex, and PaLM 540B).", "questions": "1. How does the depth of trees affect performance and inference speed?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The problem definition, theoretical analysis, model description, and experimental setup are presented clearly, making the paper accessible and informative.\n* With the interpretability of decision trees, we can better understand the language generation process.", "weaknesses": "1. No mention of the limitations of ARDT for language modeling.\n2. Performance changes with the text length. What will the performance be in generating long texts?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and very positive assessment of our paper. Specifically, we appreciate your acknowledgment of the paper's clarity, informativeness, and its contribution to model interpretability.\n\nQ1: Performance changes with the text length. What will the performance be in generating long texts?\n\nA1: In our paper, we reported the performance of extending a story by 20 words. We have expanded this to 50 words and compared the trend in performance changes, as shown in the **Rebuttal Table 1**.\nAlthough Auto-Regressive Decision Trees (ARDTs) were not specifically designed to handle lengthy texts—a task left for future work—their performance remains robust even when expanded to 50 words. Both the transformer-based model and our method exhibit a decreasing trend as the word count increases, with ARDTs experiencing a slightly greater decline (see **Rebuttal Table 1**).\n\nQ2: How does the depth of trees affect performance and inference speed?\n\nA2: In **Rebuttal Table 2**, we show the impact of tree depth on performance and inference speed. Inference speed is measured during testing by recording the start and end times of the prediction using the time.time()function and then calculating the difference to determine the inference time. As **Rebuttal Table 2** shows, the depth of the tree is positively correlated with performance and inference speed.\n\nWe hope that this clarifies any misunderstandings and we encourage the reviewer to increase their score if we have resolved their concerns or to let us know otherwise so we may try to clear up any remaining confusion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4RpMH8zn49", "reviewer": "Reviewer_97Y1", "summary": "This paper explores the idea to use AutoRegressive Decision Trees for language modelling. From a theoretical perspective, ARDTs are shown to model systems such as finite automata and more generally Turing machines. From an experimental point of view, ARDTs are shown to be able to generate grammatically correct sentences, with performance similar to small transformers.", "questions": "* The difference between the theoretical framework and the experimental setting described in Comment 8, page 7, is due to the complexity of implementing the theoretical solution, or to other issues?", "limitations": "* While the paper introduces ARDTs by stressing the point that they are an interpretable model, then in the experimental evaluation suddenly only tree ensembles are used. Is it because performance are otherwise much lower? Tree ensemble clearly do not have the same degree of interpretability of single decision trees.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ Novelty in the idea of using ARDTs for language modelling\n+ Nice compromise between performance and interpretability\n+ Interesting theoretical analysis of modeling different systems with ARDTs", "weaknesses": "- Experimental evaluation not aligned with the theoretical framework, as it uses tree ensembles \n- Interpretability is reduced when switching from single decision trees to ensembles", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first want to thank the reviewer for their thorough review and positive assessment of our paper. Specifically, we appreciate your acknowledgment of the paper's novel ideas, good balance between performance and interpretability, and interesting theoretical analysis.\n\nQ1: The difference between the theoretical framework and the experimental setting described in Comment 8, page 7, is due to the complexity of implementing the theoretical solution, or to other issues?\n\nA1: The setting we study in the theory section is not efficient to implement in practice, as it requires maintaining a decision tree with a large input size (the sliding window) and potentially generating many output tokens. As with many theoretical works, we study a simplified setting that is simpler to analyze mathematically, and while this setting is not efficient to implement in practice, it still captures the key properties of the experimental setting.\n\n\nQ2: While the paper introduces ARDTs by stressing the point that they are an interpretable model, then in the experimental evaluation suddenly only tree ensembles are used. Is it because performance is otherwise much lower? Tree ensembles clearly do not have the same degree of interpretability of single decision trees.\n\nA2: Although the focus of our paper is to demonstrate the computational capabilities of ARDTs through theoretical and empirical evidence, interpretability (as detailed in **Appendix C** in our paper) is not our main emphasis. As shown in **Rebuttal Table 3**, the performance of a single tree is indeed lower than that of tree ensembles. However, it can still be utilized for interpretability analysis.\n\n\nWe hope that this clarifies any misunderstandings and we encourage the reviewer to increase their score if we have resolved their concerns or to let us know otherwise so we may try to clear up any remaining confusion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O9ev9eMAQY", "reviewer": "Reviewer_qHp8", "summary": "This paper contributes both theoretical and empirical evidence that autoregressive decision trees (ARDTs) are an expressive machine learning model. On the theoretical side, the authors show that a family of ARDTs with concatenated inputs can, in theory, efficiently (usually polynomial in size of input sequence) simulate automata, Turing machines with fixed memory and runtime, and $k$-sparse circuits. The appendix additionally proves a result of simulating $k$-Juntas. Moreover, they do provide a simple example where traditional decision trees would require exponentially more decision nodes compared to ARDTs, showing the improved expressivity of ARDTs. On the empirical side, the authors apply ARDTs on two tasks: learning to generate short stories and learning to solve a set of reasoning tasks, illustrating ARDTs can work in these settings with only limited training data and a small number of parameters.", "questions": "I listed my questions together with their corresponding weaknesses above. Given the questions concern both theory and experiments, any change in score from my side does require a constructive answer or explanation on all above questions.\n\nIf any of my questions are unclear, please let me know and I will gladly try to make them clearer.", "limitations": "The authors do mention that the paper is only the beginning of a larger analysis of tree-shaped models added on top of language models/neural networks. Additionally, they do not claim ARDTs are the solution to anything, rather that they can be an interesting class of models that can work rather well. In that sense, I believe the authors address the limitations of their work to a sufficient degree.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. While autoregressive decision trees are not new, the proven theoretical results are both novel and enlightening. I am also not aware of any such results holding for regular decision trees, increasing the potential impact of the provided results, if correct.\n\n2. Most of the paper is well-written and easy to follow. The necessary preliminaries are explained without being too verbose, with only a couple of exceptions. In general, presentation is good.\n\n3. Applying ARDTs to language modelling might make sense, but is non-trivial. Hence, I do acknowledge that getting ARDTs to work properly with language input might not have been easy. The results on the Big-Bench-Hard are particularly noteworthy, showing the power of neurosymbolic AI methods [1, 2]. \n\n[1] Garcez, A. D. A., & Lamb, L. C. (2023). Neurosymbolic AI: The 3 rd wave. Artificial Intelligence Review, 56(11), 12387-12406.\n\n[2] Marra, G., Dumančić, S., Manhaeve, R., & De Raedt, L. (2024). From statistical relational to neurosymbolic artificial intelligence: A survey. Artificial Intelligence, 104062.", "weaknesses": "1. While the proof sketch of Theorems 3 and the full proof of Theorem 4 are very clear and well written, the remainder of the proofs are not as clear and can be hard to follow. Moreover, I have doubts about their correctness:\n     + In the proof of Theorem 3 (Appendix A), I fail to see how Lemma 10 correctly applies. The assumption being that $\\delta$ is a 2-Junta and a function from $\\mathbb{D}^L \\rightarrow \\mathbb{D}$. However, how is $\\delta$ a function from $\\mathbb{D}^L \\rightarrow \\mathbb{D}$? $L$ is not equal to 2 it seems since $n$ can be larger than 2. Additionally, the function $\\Psi: \\mathbb{D} \\rightarrow \\{0, 1\\}^d$ takes $\\boldsymbol{x} \\in \\mathbb{D}^L$ as input. How is that possible? Do you apply $\\Psi$ componentwise? And how does that lead to $(x_L, x_{L - n})$ in line 461?\n     + In the same proof, the proof by induction starts from the base case at iteration 1 and says that \n     $$\n     \\mathcal{T}_1^{AR}(\\boldsymbol{x}) = \\delta(x_L, PAD) = q_1\n     $$\n     but from the definition of the extended $\\delta$ transitions, we have that $ \\delta(x_L, PAD) = q_0$ and not $q_1$. Hence this would not prove the induction basis. I guess this can be easily solved by correctly defining $ \\delta(x_L, PAD) = q_1$?\n     + Proof of Theorem 6: First it is defined how a state of the TM is encoded as a string $\\boldsymbol{s} \\in \\mathbb{D}^{M + 1}$, but then the function $g$, which takes those strings as input, is a function from $\\mathbb{D}^4 \\rightarrow \\mathbb{D}^4$. What is supposed to be the input to $g$? Should it just be any sequence $\\boldsymbol{x}$ of length 4?\n     + Same proof of Theorem 6: The definition of $f$ also seems flawed. Look for example at $f_{M + 1}(\\boldsymbol{s}) = g(s_{M}, s_{M + 1}, s_{M + 2}, s_{M + 3})$. The vector $\\boldsymbol{s}$ only has $M + 1$ components, do you pad the non-existent ones?\n\n2. The experiment described in Section 4.2 about generating stories seems to have some flaws:\n     + It is mentioned that Table 1 contains average scores across 100 stories, yet this does not seem to be the case. How can every average be an exact integer? Is the variance of the scores over all stories equal to 0? The general lack of variability metrics such as standard deviation or quantiles should also be addressed. Moreover, if the variability is indeed 0, can you elaborate on why this can be the case? Does this mean the GPT-4 scores are not good metrics?\n     + I do have severe concerns with using GPT-4 as an evaluator. It is well-known that LLMs are **not** consistent in their predictions, not only because of the inherent uncertainty (due to sampling) of the inference process, but also due to changing inputs. Did you do a control test to see if GPT-4 indeed scored the same texts consistently? Do you use sampling during inference? The fact that a previously published work used a similar evaluation protocol does not guarantee it is a good protocol.\n\n     + Separate from the utilised evaluation protocol, I do not agree ARDTs perform on par with GPT-4 or even bigger transformers (line 306), seeing how especially their creativity and plot scores are quite a bit lower.\n\n3. I like the experiment in Section 4.3, yet some of the choices made do not instil confidence and seem doubtful. In particular, \n     + why did you only select 4 of the 23 reasoning tasks? Did you try any of the other tasks? Do the chosen tasks work particularly well with decision trees?\n\n     + Why is SOTA lower than the provided baselines? Shouldn't the baselines be lower or equal than SOTA by definition?\n\n     + Apart from chain-of-thought prompting of the LLM baselines, did you also provide a few examples to facilitate few-shot inference? Given that your models (GPT2 + ARDTs) are specifically trained on a small dataset, shouldn't the LLM baselines be given equal playing terms by giving them at least part of the training data as examples in their prompts? Not doing so does give an unfair advantage to your method.\n\n\n\nThe paper has promise, but there are too many uncertainties right now for me to be able to recommend any form of acceptance. However, I am open to significantly change my score if the authors can address my concerns and questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first want to thank the reviewer for their thorough and constructive review of our paper. We appreciate your acknowledgment of the novel and enlightening theoretical analysis, clear writing, and the non-trivial application of ARDTs to language modeling.\n\nQ1: Confusions regarding the proof\n\nA1: Thank you for pointing out the clarifications required in our proofs. While we assure you that the proofs are correct, indeed, as you pointed out, they can definitely be better explained and clarified.\n- As you note, $\\delta$ is not a 2-Junta but rather the function that we use to define the Junta. To be more accurate, let $f : D^L \\to D$ s.t. $f(x) = \\delta(x_L, X_{L-n})$. Then, $f$ is a 2-Junta, and from Lemma 10 there exists a tree satisfying $T(\\Psi(x)) = f(x)$. Indeed, $\\Psi$ is applied componentwise.\n- There is some abuse of notations in our definitions, where the state $q_i$ defines the state of the Automaton at iteration $i$, while we also use $q_0$ to define the initial state of the Automaton, so in fact it is always the case that the first state is $q_0$, i.e. $q_1 = q_0$. We realize that these notations are confusing, and will fix this by using a different notation to indicate the initial state.\n- You are correct, there is a typo and the input to $g$ should be $x$ (of length 4), and not $s$. Thanks for the catch.\n- Yes, values that “overflow” can be considered as <PAD> tokens. These do not affect the output of the function. We will clarify this in the paper.\n\nQ2.1 Why is every average of the 100 different stories an exact integer? Is the variance of the scores over all stories equal to 0?\n\nA2.1: The variance of the score is not zero. Following the Tiny-stories [1] paper, we rounded the results to integers. In the revision, we adjusted the results to two decimal places. The results are shown in the **Rebuttal Table 4**.\n\nQ2.2: Did you do a control test to see if GPT-4 indeed scored the same texts consistently?\n\nA2.2: We found that GPT-4's evaluation scores are not entirely consistent; however, the variance (less than 0.5) is considered acceptable (see **Rebuttal Table 5**). Actually, to enhance the consistency of GPT-4's scores, we followed [1] to setting up more precise and informative prompts (see **Lines 534-554 in Appendix**).\n\nAs shown in **Rebuttal Table 4**, we have updated the scores in **Table 1** by averaging the results of ten evaluations for each of the 100 stories. Each story was scored using the same prompt provided to GPT-4 ten times. Blue means higher than TinyStories-1M (transformer-based model)\n\nQ2.3:  Do you use sampling during inference? \n\nA2.3:  No.\n\nQ2.4:  I do not agree ARDTs perform on par with GPT-4 or even bigger transformers (line 306)\n\nA2.4: Good point, we will make line 306 more accurate: ARDTs (\\~0.3M parameters) trained on the TinyStories dataset are on par with GPT-4 (\\~1800B) or even bigger transformers trained on huge internet dataset regarding the creativity and plot, but remain inferior in terms of grammar and consistency. \n\nQ3.1: Why did you only select 4 of the 23 reasoning tasks? Did you try any of the other tasks? Do the chosen tasks work particularly well with decision trees?\n\nA3.1: We just chose 4 representative tasks. The results of all 23 reasoning tasks are shown in **Rebuttal Table 6**. The results demonstrate that ARDTs possess good reasoning capabilities.\n\nQ3.2: Why is SOTA lower than the provided baselines? Shouldn't the baselines be lower or equal than SOTA by definition?\n\nA3.2: We apologize for any confusion caused. The term ‘SOTA’ here refers to the performance benchmarks borrowed from **Table 3 in the BIG-Bench-Hard [2] paper**, which represent the state-of-the-art performance in the BIG-Bench paper [3]. We will change 'SOTA' to 'SOTA Methods in BIG-Bench' in the revision.\n\nQ3.3: Apart from chain-of-thought prompting of the LLM baselines, did you also provide a few examples to facilitate few-shot inference? Given that your models (GPT2 + ARDTs) are specifically trained on a small dataset, shouldn't the LLM baselines be given equal playing terms by giving them at least part of the training data as examples in their prompts? Not doing so does give an unfair advantage to your method.\n\nA3.3: We will run this experiment with a few-shot examples and report the results in the final version.\n\nWe hope that this clarifies any misunderstandings and we encourage the reviewer to increase their score if we have resolved their concerns or to let us know otherwise so we may try to clear up any remaining confusion.\n\n[1] Eldan, Ronen, and Yuanzhi Li. \"Tinystories: How small can language models be and still speak coherent english?.\" arXiv preprint arXiv:2305.07759 (2023).\n\n[2] Suzgun, Mirac, et al. \"Challenging big-bench tasks and whether chain-of-thought can solve them.\" arXiv preprint arXiv:2210.09261 (2022).\n\n[3] Srivastava, Aarohi, et al. \"Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.\" arXiv preprint arXiv:2206.04615 (2022).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their comprehensive and constructive feedback on our submission. We are pleased that our work is recognized for its novelty (Reviewers o5To, 97Y1, and qHp8), its novel and enlightening theoretical analysis (Reviewers o5To and 97Y1), and a nice balance between performance and interpretability (Reviewers o5To and 97Y1). 

We have prepared an extensive, point-by-point response for each reviewer, outlining our plans to address their concerns and suggestions for additional analyses to enhance the manuscript. **All new tables can be found in the attached one-page PDF file**. We believe that our response will address the reviewers' concerns and allow us to promptly resolve any remaining minor issues.

Once again, we would like to thank all reviewers for their comments and we are looking forward to the discussion period.

Meta-review: This paper is a solid mix of interesting theoretical and empirical results.  The paper stands in contrast to most DNN/transformer based language modeling, and as such, broadens the conversation about the space of useful models.  The paper is well-written, and the authors have improved the presentation based on a good dialogue with the reviewers. I believe this paper will be of interest to a wide variety of researchers and industry practitioners.
Decision: Accept (poster)