Learning Elementary Cellular Automata with Transformers
Mikhail Burtsev · 2024
Read Learning Elementary Cellular Automata with Transformers by Mikhail Burtsev (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01417.txt.
Introduction
Mikhail Burtsev presents a machine learning paper, published in 2024, testing whether transformer models can truly learn simple rules rather than memorize patterns. The test bed is elementary cellular automata, tiny grids where each cell updates by a fixed local rule. Transformers trained on state sequences from random starts learned to predict the next state across many different rules.
Accuracy stayed high for one step ahead but fell sharply when the model had to plan many steps without fresh input. Training that also asked for future states or the rule itself built stronger inner representations and improved long runs. Deeper models also did better, a hint for how language models might gain reasoning skill.
Catalog record
| CREATOR | Mikhail Burtsev |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-01417
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning Elementary Cellular Automata with Transformers Mikhail Burtsev Abstract Large Language Models demonstrate remarkable mathematical capabilities but at the same time struggle with abstract reasoning and planning. In this study, we explore whether Transformers can learn to abstract and generalize the rules governing Elementary Cellular Automata. By training Transformers on state sequences generated with random initial conditions and local rules, we show that they can generalize across different Boolean functions of fixed arity, effectively abstracting the underlying rules. While the models achieve high accuracy in next-state prediction, their performance declines sharply in multi-step planning tasks without intermediate context. Our analysis reveals that including future states or rule prediction in the training loss enhances the models’ ability to form internal representations of the rules, leading to improved performance in longer planning horizons and autoregressive generation. Furthermore, we confirm that increasing the model’s depth plays a crucial role in extended sequential computations required for complex reasoning tasks. This highlights the potential to improve LLM with inclusion of longer horizons in loss function, as well as incorporating recurrence and adaptive computation time for dynamic control of model depth. 1 Introduction Large Language Models (LLMs) have become valuable tools in mathematics, demonstrating impressive capabilities in problem-solving and reasoning tasks. Notably, OpenAI’s o1 model achieved a ranking among the top 500 students in the US in a qualifier for the USA Math Olympiad (AIME) [ 1 ] . Despite these successes, LLMs still face challenges in reasoning [ 2 , 3 , 4 , 5 , 6 ] and planning [ 7 ] , particularly when required to infer and apply underlying rules from data. These observations raise a question: Do the limitations of LLMs in reasoning stem from the nature of their training data, the procedures employed during training, or inherent architectural constraints? Transformers [ 8 ] , which form the backbone of many modern LLMs, are universal approximators [ 9 , 10 , 11 , 12 ] and theoretically capable of simulating Turing machines using intermediate computational steps, making them Turing complete and, by extension, capable of formal reasoning [ 13 , 14 , 15 , 16 ] . Earlier studies found that transformers can be trained to perform symbolic integration and solving differential equations [ 17 ] , as well as symbolic regression [ 18 , 19 ] . In our study, we continue the line of research exploring the trainability of Transformers for mathematical reasoning tasks by focusing on Elementary Cellular Automata (ECAs). The simplicity and clarity of this "toy" problem make it an ideal testbed for assessing the ability of Transformers to abstract and apply logical rules. By demonstrating that Transformers can learn and generalize Boolean functions of fixed arity inherent in ECAs, we aim to evaluate their ability to infer, generalize, and apply logical rules solely from observed data, without relying on memorization. 2 Methods A B Figure 1 : Learning Elementary Cellular Automata (ECA) with Transformers. A. Examples of training samples. Orbit of ECA is a sequence of binary strings of size W=20 . First k=10 states marked by red rectangle encode Transformer input. B. Given a part of the orbit Transformer with full attention learns to predict the next state (O-S), the next few steps (O-O), the next state and a rule (O-SR), or predict the next state given a rule and an orbit (RO-S). An Elementary Cellular Automaton (ECA) is a one-dimensional, dynamical system in which space and time are discrete. Let r\in\mathbb{N}:r\geq 1 be the neighbourhood radius in space represented by a regular lattice of W\in\mathbb{N}:W\geq 2r+1 identical, locally-interconnected cells with a binary state space, \mathbb{S}=\{0,1\} . The ECA’s global state , x\in\mathbb{S}^{W} , is a lattice configuration specified by the values of all the states of all cells in the lattice at a given time. This state evolves deterministically in synchronous, discrete time steps according to a global map g_{\rho}:\mathbb{S}^{W}\rightarrow\mathbb{S}^{W} defined by a local rule \rho:\mathbb{S}^{2r+1}\rightarrow\mathbb{S} , so [g_{\rho}(x)]_{w}=\rho(x_{w-r},\ldots,x_{w},\ldots,x_{w+r} ). The sequence of states an ECA passes through during its space–time evolution , \mathcal{O}^{T}(x)=[x,g_{\rho}(x),g_{\rho}(g_{\rho}(x)),\ldots,g_{\rho}^{oT-1}(x)] , defines its trajectory or orbit from an initial condition (configuration) x for T\in\mathbb{N}:T\geq 1 . Examples of ECA orbits are visualized on the figure 1 A. Let consider four modifications of learning tasks designed to evaluate different aspects of predictive modeling and rule inference in ECAs (see Fig. 1 B). Orbit-State (O-S), given an orbit \mathcal{O}^{T}(x)=[x^{(0)},x^{(1)},\ldots,x^{(T-1)}] where x^{(0)}\in\mathbb{S}^{W} , the objective is to predict the state x^{(T)} at time T . Orbit-Orbit (O-O), given an orbit \mathcal{O}^{k}(x) for some k<T predict the subsequent states up to time T , generating \mathcal{O}_{k}^{T}(x)=[x^{(k)},\ldots,x^{(T)}] . Orbit-State and Rule (O-SR), given an orbit \mathcal{O}^{T}(x) the objective is to predict the state x^{(T)} at time T and the local rule \rho . Rule and Orbit-State (RO-S), given an orbit \mathcal{O}^{T}(x) and the local rule \rho the objective is to predict the state x^{(T)} at time T . Our base model is Transformer encoder with full self-attention. It has 4 layers and 8 heads with d_{model}=512 . The input vocabulary of the model consists of tokens: [0], [1], [SEP], and [M].The states and the local rule \rho are encoded as binary strings. The model receives the orbit as a sequence of bits representing consecutive states separated by the [SEP] tokens. For the prediction of future states or the inference of the local rule, the end section of the input sequence is filled with mask tokens [M] corresponding to the positions of the unknown elements. We generated a dataset with the CellPyLib [ 20 ] 1 1 1 Dataset and a source code for experiments are available at https://github.com/burtsev/TransformerECA . for fixed lattice size W=20 and neighborhood radius r=2 . This configuration results in a total of 2^{2^{2r+1}}\approx 4.3\times 10^{9} possible boolean functions defining local rules. For each sample in the dataset, both the initial state and the local rule \rho were generated randomly. We then computed the orbit for T=20 time steps using these parameters. The training dataset consists of 9.5\times 10^{5} and the test of 10^{5} samples. Importantly, the local rules included in the test set are exclusive and not present in the training set. This separation ensures that the model’s performance reflects its ability to generalize to unseen rules, rather than simply memorizing the training data. To measure the quality of the model’s predictions, we use per-bit accuracy averaged over free runs, which calculates the proportion of bits correctly predicted in the output sequences. 3 Results and Discussion A B C D Figure 2 : Transformer learns to predict the next state of ECA but struggles to plan ahead. A. Accuracy of the next state prediction for ECA orbit with size 20 generated by Boolean function of 5 arguments for different input state lengths. B. Planning accuracy for different training settings (see the main text for details). C. Accuracy for autoregressive generation of ECA orbit. D. Comparison of autoregressive (AR) and look ahead (LA) predictions. We first assess whether the samples in our dataset provide sufficient information for the model to learn the underlying dynamics successfully. The minimal number of time steps T_{\text{min}} needed to recover the local rule \rho from the observed orbit can be estimated analogous to the coupon collector’s problem