Intelligence at the Edge of Chaos
Authors: Shiyang Zhang
Aakash Patel
Syed A Rizvi
Nianchen Liu
Sizhuang He
Amin Karbasi
Emanuele Zappala
David van Dijk
Venue: ICLR 2025 Poster (2025)
Keywords: Large Language Models (LLMs)
Elementary Cellular Automata (ECA)
Emergent Intelligence
Complex Systems
Complexity Theory
Primary area: learning on time series and dynamical systems
TL;DR: Training Large Language Models (LLMs) on elementary cellular automata (ECA) rules shows that models exposed to more complex rule behaviors perform better on downstream tasks.

Abstract: We explore the emergence of intelligent behavior in artificial systems by investigating how the complexity of rule-based systems influences the capabilities of models trained to predict these rules. Our study focuses on elementary cellular automata (ECA), simple yet powerful one-dimensional systems that generate behaviors ranging from trivial to highly complex. By training distinct Large Language Models (LLMs) on different ECAs, we evaluated the relationship between the complexity of the rules' behavior and the intelligence exhibited by the LLMs, as reflected in their performance on downstream tasks. Our findings reveal that rules with higher complexity lead to models exhibiting greater intelligence, as demonstrated by their performance on reasoning and chess move prediction tasks. Both uniform and periodic systems, and often also highly chaotic systems, resulted in poorer downstream performance, highlighting a sweet spot of complexity conducive to intelligence. We conjecture that intelligence arises from the ability to predict complexity and that creating intelligence may require only exposure to complexity.

Published as a conference paper at ICLR 2025
INTELLIGENCE AT THE EDGE OF CHAOS
Shiyang Zhang
Aakash Patel*:
Syed Rizvi* Nianchen Liu Sizhuang He!
Amin Karbasi
Emanuele Zappala*
David van Dijk
Yale University, "Columbia University, Northwestern University, "Idaho State University
ABSTRACT
We explore the emergence of intelligent behavior in artificial systems by inves- tigating how the complexity of rule-based systems influences the capabilities models trained to predict these rules. Our study focuses on elementary cellu- lar automata (ECA), simple yet powerful one-dimensional systems that generate behaviors ranging from trivial highly complex. By training distinct Large Lan- guage Models (LLMs) on different ECAs, we evaluated the relationship between the complexity of the data generated by the rules and the models' ability to learn effective general representations, reflected in their performance on downstream tasks. Our findings reveal that models trained on more complex data exhibit greater predictive ability, demonstrated by their performance reasoning and chess move prediction tasks. Both uniform and periodic systems, and often also highly chaotic systems, resulted in poorer downstream performance, highlighting a sweet spot of complexity conducive to intelligence. We conjecture that intelli- gence arises from the ability predict complexity and that creating intelligence may require only exposure to complexity.
INTRODUCTION
The emergence and nature of intelligence within computational systems have long been subjects of fascination and rigorous study in the fields of artificial intelligence (AT) and theoretical computation. Traditional AI methodologies predominantly involve training models on high-quality datasets inher- ently imbued with human intelligence- suchh as natural language corpora, expert-annotated datasets, or data reflecting human cognitive processes (Coleman et al., 2019). This approach operates under the assumption that creating intelligent behavior necessitates exposure intelligent data sources. In contrast, this paper explores an alternative hypothesis: that intelligence can emerge from modeling simple systems as long as they exhibit complex behaviors, even when the process that generates the data lacks inherent intelligence.
To investigate this hypothesis, we utilize Stephen Wolfram's elementary cellular automata (ECA) experimental framework. ECAs are one-dimensional, binary-state, discrete computational systems defined by 256 possible 8-bit rules. They generate a diverse spectrum of behaviors ranging from simple, repetitive patterns to highly complex and chaotic structures (Wolfram 1983). Despite their simple rule-based definitions, certain ECAs produce significantly complex patterns, making them ideal for examining the relationship between complexity and intelligence.
Our methodology involves training separate instances of the GPT-2 language model (Radford et al. 2019) data generated by individual ECAs. The models are tasked with predicting future states of the automata. Following this pretraining phase, we evaluate the transformer models' ability to learn useful representations by quantifying their performance on downstream logical reasoning and chess move prediction tasks.
This paper presents an extensive study exploring the relationship between system complexity and the emergence of intelligence in large language models (LLMs), quantified by the effectiveness of
'Equal contribution
"Coresponndence david vandii jkkya 1 e.edu

---

Published as a conference paper at ICLR 2025
learned representations for downstream tasks. We discover positive correlation between the com- plexity of the ECA data and the downstream performance of models trained on that data, highlighting the role of complexity in learning effective representations. Surprisingly, we find that models can learn complex solutions even when trained on rules that generate simple data. Our results suggest an optimal complexity level, "edge of chaos", conducive to learning. where the system is structured yet challenging to predict. These findings enhance our understanding of intelligence in artificial systems and provide a framework for future research focused on the importance of complexity in developing these systems.
BACKGROUND
2.1 ELEMENTARY CELLULAR AUTOMATA
Cellular automata (CAs) are computational models of complex systems, consisting of grid of cells that evolve over time based on simple rules. First introduced by John von Neumann (von Neumann, 1966), CAs have since been widely used to simulate various physical, biological, and computational systems due to their simplicity and ability produce complex behavior.
Elementary Cellular Automata (ECAs) (Wolfram Mallinckrodt, 1994) are a type of one- dimensional cellular automaton where each cell has binary state, and its next state is determined by a simple rule that depends only on the current state of the cell and its two immediate neighbors. There are 256 possible ECA rules, 88 of which are unique after accounting for symmetries (Castillo-) Ramirez & Magaña-Chaver
2003). Notable examples include Rule 110, which has been proven to be Turing complete (Cook) 2009), and Rule 90, which generates the fractal-like Sierpinski triangle. These rules are categorized into four classes based on their behavior when initialized with random conditions: Class I, which evolves homogeneous state; Class II, which forms simple periodic structures; Class III, which produces chaotic and aperiodic patterns; and Class IV, which exhibits complex structures (Castillo-Ramire,
Tagaña-Chavee 2023).
ECAs are valuable computational models used to explore complex systems and emergent behav- iors arising from simple rules. Their usefulness lies in their simplicity and the variety of patterns they can produce. making them ideal for studying pattern formation in computation (Meunier) 2016), physics (Banerjee & Dalui 2024), and mathematical biology (Rasolonjanahary & Vasiev 2020). Additionally, ECAs have been utilized in cryptography
basis of certain security frame- works (Corona-BB Bermúdez et al. 2022) and in computer science education (Staubitz et al., (016)) to illustrate concepts in algorithms and computational theory. Their ability to model intricate systems with minimal computational resources has made ECAs a popular tool across scientific disciplines.
2.2 LARGE LANGUAGE MODELS
Large language models (LLMs) are advanced artificial intelligence systems designed to understand and generate human-like text based on vast datasets (Brown et al. 2020). By leveraging deep learn- ing techniques, these models analyze patterns in language perform tasks such translation, sum- marization, and conversational dialogue (Devlin et al. 2018). Notable examples like OpenAl's GPT-4 have demonstrated remarkable capabilities in producing coherent and contextually relevant responses across a wide range of topics (Achiam et al. 2023). The development of LLMs repre- sents a significant advancement natural language processing, opening up new possibilities for applications in education, research, and industry (Katz et al. 2023
2.3 COMPLEXITY MEASURES
Various complexity measures have been proposed assess the behavior of dynamical systems. In this work, we employ the following measures:
1. Lempel-Ziv Complexity assesses the compressibility of sequence by counting the num- ber of unique substrings in the sequence (Lempel Ziv 1976).
2. Compression Complexity quantifies how effectively a sequence can be compressed using data compression algorithm such as Zlib (Zli).
2

---

Published as a conference paper at ICLR 2025
Elementary Cellular Automata
Pre-training
Downstream Tasks
Abstraction Ressoning
Chess Move Prediction
Space
206
Q LLM
Q LLM
O LLM
O LLM
Next token prediction
Time
04 14664446 d5
Perfoman
Complexity Meesures
Pertormnns
Unioomm
Pertadic
Chastic
Complex
Compresdonn complisiity
Wathram decoiftction
kyspunoy
Lempel-Zyy complanity
exponine
8100210
Complesity
Complesity
Figure 1: Our framework for investigating the link between complexity and intelligence. We pretrain Large Language Models (LLMs) on Elementary Cellular Automata (ECAs) from different complex- ity classes using next-token prediction, then evaluate them downstream reasoning and chess move prediction tasks. We use various measures to analyze the complexity of ECA- -eA-generated data, and quantify the relationship between complexity and downstream performance.
3. Lyapunov Exponent gauges system's 's sensitivity to initial conditions. Higher Lyapunov exponents indicate that small variations in initial states result in rapidly diverging outcomes. We adopt the method proposed by Wolf 1986) for computing this metric.
4. Krylov Complexity evaluates how information propagates in system's Hilbert space, measuring how quickly an operator spans larger regions of the state space over time (Parker
ct al. 2019).
5. Wolfram Classification categorizes ECA rules into four categories based on behavior and complexity (see Section 2.1
While these measures correlated with another, each measures different aspects of complex- ity. For most analyses, we focus on Lempel-Ziv Complexity and the Wolfram Classification. Perfor- mance downstream tasks function of other complexity measures is shown in Appendix
3 METHODOLOGY
In this study, we systematically investigate the relationship between system complexity and the generalization of learned representations of models trained on these systems. This section outlines our methodology, including the steps for data generation and model pretraining. An overview the training process and task evaluations is provided in Figure]
3.1 DATA GENERATION
To train our models, we simulate selection of ECA rules. Each simulation generates a sequence of binary vectors, where each vector represents the system's spatial state specific time step. For each sample, begin with randomly initialized vector as the automaton's initial state. The system then evolved over 1000 time steps by repeatedly applying the chosen ECA rule. This process produces sequence of binary vectors that capture the evolving dynamics of the ECA over time.
To increase the diversity of the training data, extract random spatiotemporal windows from the full sequences. Specifically, we sample subsequences by selecting random windows 60 time steps and 100 spatial dimensions from the binary vectors. This method exposes the model variety of contexts and state configurations, enhancing its ability to learn the dynamics of the ECA rules and generalize to new sequences. Each training sequence represents randomly selected segment in
3

---

Published as a conference paper at ICLR 2025
space and time of the automaton's evolution. To vary the difficulty of the task, we train models to predict either 1 or 5 steps in the future.
3.2 TRAINING PROCEDURE FOR GPT-2 MODELS
We utilized modified GPT-2 architecture (Radford et al., 2019) adapted for binary input and output data, enabling it to perform next-token prediction on sequences binary vectors. Instead of using traditional token embedding layer followed by softmax over vocabulary, we replaced the token embeddings with a linear projection layer that directly maps binary vectors into the model's embed- ding space. The GPT-2 model processes these embeddings to capture temporal dependencies and patterns within the sequences. At the output, we apply a linear projection layer to map the model's hidden states back the data dimensionality, generating the prediction for the next state of binary variables at each time step. This adaptation allows the GPT-2 model to handle binary data directly and perform next-token prediction without relying on predefined vocabulary. Additionally, this also makes the model deterministic, in line with the deterministic nature of ECAs
3.3 PRETRAINING SETUP
Each model was pretrained on next-token prediction tasks using data generated from single ECA rule for up to 10,000 epochs. In each epoch, a new dataset was generated from a random initial state. Not only does this setup effectively provide infinite data, but it also makes the volume of data seen by the model directly proportional to the number of epochs the model has been trained for. To prevent overfitting, early stopping based validation loss employed. The training data were organized into batches of 64 sequences, each comprising 60 time steps and 100 spatial dimensions.
We employed the Adam optimizer with an initial learning rate 7 of 0.01. A learning rate scheduler with linear warm-up over the first 10% of the total steps was implemented to stabilize the initial stages of training and improve convergence rates. After the warm-up phase, we applied cosine annealing to gradually decay the learning rate over the remaining training steps. Gradient accumulation was used handle larger effective batch sizes within the constraints of GPU memory, allowing to simulate larger batch sizes by accumulating gradients over multiple mini-batches. To prevent exploding gradients, we applied gradient clipping with maximum norm of 1.0.
10-6 and weight decay
EXPERIMENTS
To evaluate the emergent intelligence of models trained on cellular automata, we conducted experi- ments on three downstream tasks: one easy and one hard reasoning task inspired by the Abstraction and Reasoning Corpus (ARC) (Chollet) (00o)l,t]001),.....) and a challenging chess move prediction task (Ruoss) jet al. 2024). These tasks were designed to quantify the transformer models' abilities in reasoning. abstraction, and long-term prediction, thereby assessing the level of intelligence encoded during pretraining on -eseeeeee data of varying complexities. We freeze the layers of the pretrained GPT-2 models and train only the imput and output projection layers for downstream tasks to ensure that performance differences reflect the inherent capabilities of the models.
Our central hypothesis is that models pretrained rules that generate complex data will exhibit superior performance on downstream tasks compared to those pretrained on simple rules. The in- clusion of both easy and hard tasks allows to observe different performance trends and better understand the relationship between pretraining complexity, task difficulty, and emergent intelli- gence. The chess move prediction task, in particular, serves as excellent system test reasoning due to its inherent complexity and requirement for strategic thinking.
4.1 DOWNSTREAM TASK: REASONING
We developed a downstream task inspired by the ARC (Chollet 2019) to evaluate models' problem- solving and reasoning abilities. Our approach utilizes sequence completion problems that require the model to infer transformation rules from provided examples and apply them novel scenarios.
4

---

Published as a conference paper at ICLR 2025
The data consists of fixed number of shapes grid. At each time step, any of the following transformations can be applied to each shape: changing the color. rotating the shape by 90º, or shifting the shapes by one position. We designed two versions of the reasoning task, differing in complexity based on the number and type of transformations applied.
Easy: In the easy task, only 3 3 squares that fixed in position and orientation. The only possible transformation a color change, which we perform a predetermined order.
Hard: The hard task involves more complex patterns where all transformations are applied simul- taneously. We used four distinct base shapes, each represented by a 5 x 5 matrix. This results in complex sequences where shapes change color, orientation, and position tion of these transformations requires the model to reason over multiple simultancous changes to accurately predict the next pattern in the sequence.
time. The combina-
For the easy reasoning task, models were post-trained for 1,000 epochs with a learning rate of 1 x 10-4. Due the increased complexity and difficulty of the hard reasoning task, we post-train for 10,000 epochs with a learning rate of x 10 10=5, We use early stopping based on validation loss to prevent overfitting.
4.2 DOWNSTREAM TASK: CHESS MOVE PREDICTION
For the chess experiment, we evaluated the capability of the different ECA-pretrained models to predict next moves in chess games represented using Standard Algebraic Notation (SAN) (Alg). We use chess games from the Lichess Elite database (Lic), focusing on games played between January and April 2016 by Grandmasters with ratings of 2200 and above. Each game was represented as a sequence of SAN moves. We split this collection into training, validation, and test sets using an 80-10- 10-100 10 split to facilitate model training and evaluation. Each game sequence segmented into subsequences of 60 moves each, and any subsequence shorter than this length was padded sequences to length 60.
We added an embedding layer to convert the SAN tokens into vector representations, which were then processed using the frozen ECA-ppetraiie model. A linear output layer was used to transform the outputs to the vocabulary size corresponding to the SAN tokens. These input and output layers trained while the rest of the model was frozen. The model was trained using cross-entropy loss, the Adam optimizer (Kingmal 2014), and learning rate scheduler with warm-up. Early stopping was again used.
4.3 HARDWARE AND SOFTWARE
The experiments were conducted using PyTorch version 2.1 and the Transformers library (version 4.41.0), with CUDA version 12.4 for GPU acceleration. The models were trained on 12 NVIDIA H100 GPUs, each with 80 GB of memory, running on Red Hat Enterprise Linux 8.8.
RESULTS
In this section, we present our results exploring the relationship between system complexity and emergent intelligence in LLMs. The following sections detail our analyses of task performance and attention patterns across models trained on data with varying complexities.
5.1 RELATIONSHIP BETWEEN INTELLIGENCE AND COMPLEXITY
Figure presents the model performance across three downstream tasks (easy reasoning, hard rea- soning, and chess move prediction)
function of the complexity of the ECA rules the models were pretrained on. The top row highlights the relationship between performance and the Lempel- Ziv complexity data, while the bottom row categorizes the performance by Wolfram's complexity classes. For clarity, two representative rules from each complexity class are displayed on the left, with their corresponding performance annotated in the top plots.
For the reasoning tasks, models generally achieve near near- perfect accuracy when trained for a sufficient number of epochs. Therefore, instead of reporting absolute accuracy, we focus model efficiency,
5

---

Published as a conference paper at ICLR 2025
Rule 66
Rele
Rrsceiing (ATC Fagy)
Beserrite [ABI Blod)
Chess Moer Prrfictes
Unalocn
0.005
F. 30
AT
r-0.4
DU000G
0.200
0L00G
Fuiil 700
Ralle
M0004
0.004
0:55
Rale Cheeplanit (Lenpel-lc))
Rale Compplenit (Eenaps kiles)
Rale Complexiy (Eags kile)
6:2.
1L10%
0.000
0.0044
0.0000
0.88
LL1E2
6:87
0.000
Tnnfeen Peraddi: Chandic Uberplen
Tirffen
Peraeda:
Chaendo Creepee
Beifern
Pottddo: Clantto Crappee
(VV]
10
(III)
(VV)
30
(II) (IV)
Figure 2: Relationship between downstream task performance and data complexity. (a) Eight repre- sentative ECA rules, two from each of Wolfram's 's four complexity classes. Performance of models trained on these rules is highlighted in the top row of (b). (b) Top row: Model performance in rela- tion to the Lempel-Ziv complexity of data generated by each rule. The left and center panels show efficiency (1 divided by number of epochs to reach 80% validation accuracy) for the easy and hard reasoning tasks, respectively. The right panel shows move prediction accuracy for the chess task. The rules depicted on the left are highlighted in the plot with triangles and annotated with the rule number. The correlation coefficient is shown the top-left corner of each plot. An asterisk next to the value indicates significant relationship (p 0.05). Bottom row: Downstream task performance based on Wolfram classification of each rule. Models trained on Class III and Class IV (chaotic and complex) rules perform better than models trained uniform and simple rules. Baseline results for a randomly initialized transformer model are shown with a dashed black line on all plots.
defined as the inverse of the number of epochs required to reach 80% accuracy. The chess task is sufficiently difficult that models do not achieve perfect performance, and so we report the final accuracy. As data complexity increases, we observe a clear positive correlation in all tasks, with more complex data leading greater efficiency. This correlation significant for each of the tasks. The p-values, along with the distance correlation coefficient, are given in Appendix D
In terms of Wolfram's classification, rules from Classes and (uniform and periodic) show lower average efficiency in the reasoning tasks compared to those from Classes III and IV (chaotic and complex). Class IV rules especially outperform the other classes on the chess move prediction task. This pattern suggests that models trained on more complex data tend to perform better harder downstream tasks. Results with respect to other complexity measures are shown Appendix E
We observe that models trained on certain Class III (Chaotic) rules, such as Rules 105, 146, and 150, have poorer performance on the hard reasoning and chess move prediction tasks. This behavior expected due to chaotic systems lacking the structured patterns necessary for effective learning. In other words, they may be too random to predict, leading to weaker downstream performance. Though provide the correlation coefficient quantify the relationship. the key takeaway is the qualitative insight: performance peaks at intermediate complexity and deteriorates with excessive complexity. These results highlight the existence of "sweet spot" of complexity conducive to intelligence, where the system is still predictable yet hard to predict.
5.2 MODELS LEARN COMPLEX SOLUTIONS FOR SIMPLE RULES
The elementary cellular automata (ECA) are inherently memoryless, meaning the state at the next time point is determined only by the current time point, without any consideration of past states. For each model, a straightforward solution exists: simply learning the 8-bit ECA rule and applying it to the current state to predict the next state. However, alternative solutions may also be possible, where the model leverages historical states for its predictions. The key question is whether the model is merely learning the trivial solution or if it is integrating information from the state history.

---

Published as a conference paper at ICLR 2025
(Uniloonn)
Rule 105
Avergg Atsemion Or) Last States
0.08
P=0.66
Rule 170 (Porkodic)
Tuil 110
0100
Role (Chaotic)
0:01
10-4
0.03
(Complex)
0.12
6-40
64
6-5
6-4)
1-3
6-1
40
60
100
State
Complesiit (Lempel-2s)
Figure 3: Attention scores for the final 10 states prior to the target state, showing that models trained on more complex data rely more heavily on past states for prediction. Left: Visualization of the last 10 states and the target state for representative rules from each of Wolfram's 's complexity classes. Center:
Attention scores for each of the last 10 states, highlighting that models trained on chaotic and complex (Class III and Class IV) rules focus more on recent states, while models trained on uniform rules exhibit consistently low attention. Periodic rules demonstrate a repeating attention pattern, suggesting that the model is learning to attend to earlier cycles of the same state rather than general state history. Right: Average attention across the final 10 states for all rules, plotted against Lempel-Ziv complexity. A strong positive correlation (r 0.66) indicates that models trained on higher complexity data attend more highly to historical states during prediction.
To explore this, we analyze the self-attention scores with respect the last state in the input quence, which the model uses to predict the next state (see Section [.2). Specifically, we examine the attention values corresponding to the final ten states before the target state. Figure iillustrases the average attention across all layers and heads for the different ECA rules, as well as the attention each of the last 10 states for one rule from each complexity class.
Our findings reveal that models trained on rules that produce more complex dynamics tend to al- locate higher attention to the last ten states, with strong positive correlation (r 0.66) between data complexity and average attention. This suggests that models trained on complex data integrate information from past states to make their predictions. contrast, models trained on simpler rules display lower attention across the last ten states. For example, Rule 168 (uniform) shows consis- tently low attention, indicating that previous states are not being utilized in the prediction process. Rule 179 (periodic) demonstrates recurring pattern in its attention scores, where the model focuses on every other state. This behavior is explained by the nature of Rule 179, which produces an alter- nating pattern that repeats every two time steps (Figure 3). Thus, the model appears to be learning only this alternating cycle, rather than general state history. The simpler attention structure sug- gests that these models learn trivial solution, which is in accordance with their poorer downstream performance.
We emphasize that for both rules that generate simple data and those that generate complex data, trivial solution exists: learning the instantaneous 8-bit rule and applying it to only the current state. Such model would have no attention on previous states, as it only needs the current state make its prediction. The fact that the complex models are attending to previous states indicate that they are learning a more complex solution to this simple problem, and we conjecture that this complexity is what makes the model "intelligent" and capable of repurposing learned reasoning to downstream tasks.
We had initially expected that predicting one step in the future would be too easy, and would result in every model learning the trivial (8-bit rule) solution. As such, we trained models to predict steps ahead. Surprisingly, we found that models predicting only the next step not only learned non-trivial solutions, but even outperformed models predicting five steps ahead (Figure 4 This result suggests that even when predicting the immediate next state, the models are learning nontrivial solutions (provided that the underlying data is complex), capable of capturing complex patterns beyond the trivial nle-based approach.
7

---

Published as a conference paper at ICLR 2025
0.010
Peffrrmanc of Model Trained on Longtern Prodictio
ECA Rules
Equal performance
100
0,008
90
Rallo Compp Compleoste codoy (Lmmpe) (00
0.006
-70
000
50
0.002
30
0.000
0.000
0.002
0,004
0.006
0.008
0.010
Performance of Model Trainod on Short-term Prediction
Figure 4: Comparison of model performance short-term (1-step) and long-term (5-step) pre- diction tasks for ECA rules. Points are colored by Lempel-Ziv complexity, with the dashed line indicating equal performance. Points below the line show better short-term performance.
In this section, we explored the relationship between system complexity and emergent intelligence. Our results show that downstream model performance improves with pretraining on more complex data, but can deteriorate with excessive complexity or chaotic behavior, signifying sweet spot of complexity conducive to intelligence. Attention patterns further reveal that models trained on complex data integrate historical information into their predictions, suggesting that they are learning more sophisticated solutions to relatively simple problems. hypothesize that this complexity in the learned representations is key factor enabling models to generalize and perform well downstream tasks.
RELATED WORK
Elementary Cellular Automata and Complexity Elementary Cellular Automata (ECA) serve as foundational models for exploring complexity arising from simple rules. Early research demon- strated that even minimalistic CA systems, governed by basic and local interaction rules, could generate intricate patterns time (Wolfram) 1983). Wolfram's extensive investigations into dimensional CA revealed that certain rules produce behaviors ranging from stable and periodic to chaotic and complex (Wolfram/ 1984). In his work Cellular Automata and Complexity, Wolfram classified one-dimenn mie-dimensional CA into four classes based on their dynamic behaviors, highlighting the rich complexity that simple systems can exhibit (Wolfram Mallinekrodii 1994). Wolfram's 's Prin- ciple of Computational Equivalence posits that systems with sufficiently complex behavior can ex- hibit computational capabilities equivalent to universal computation (Wolfram & Gad-el Hak 2003). ECA Rule 110, which has been proven to be Turing complete (Cook et al. 2004), demonstrates that even simple, rule-based systems can perform any computation given the right initial conditions. Re- cent works have explored the use of transformers to predict cellular automata states (Berkovich & Buchler 2024).
Computation at the Edge of Chaos The concept of computation at the "edge of chaos" sug- gests that systems poised between order and disorder exhibit maximal computational capabilities and complex behavior. [Langton] (1990) introduced this idea, demonstrating that cellular automata operating at this critical transition can perform complex computations. Packardd (1988) explored how systems adapt toward the edge of chaos, suggesting that evolution may favor systems that bal- ance between stability and chaos. Mitchell et al. (1993) investigated evolving cellular automata to perform computations, finding that rules near the edge of chaos are more capable of complex tasks. These studies provide theoretical foundation for our work, as we observe that models trained on rules with higher complexity exhibit greater intelligence in downstream tasks.
8

---

Published as a conference paper at ICLR 2025
Emergence of Intelligence Through Complexity Exposure The hypothesis that intelligence can arise from exposure to complexity is supported by studies in artificial life and complexity science. Bedau (2003) discusses how complex behaviors and adaptation emerge from simple rules in arti- ficial life systems. Langton (1990) introduced the concept of "computation at the edge of chaos," proposing that systems poised between order and disorder exhibit maximal computational capabil- ities and complex behavior. Our conjecture that creating intelligence may require only exposure to complexity aligns with these perspectives. (Crutchfield & Mitchell (1995) explored how evolution- ary processes can lead to emergent computation in cellular automata, demonstrating that complexity in the euvironment can drive the evolution of computational abilities. Kauffman (1992) discussed self-organization and complexity in biological systems, suggesting that complex interactions can lead to emergent properties like intelligence.
Emergent Abilities in Large Language Models Recent advancements in large language models (LLMs) have shown that not only increasing model size but also exposing models to more complex and diverse data can lead to the emergence of new capabilities not present in smaller models mod- els trained on simpler data. WWi et al. (2022) discuss emergent abilities in LLMs, highlighting that certain reasoning tasks become solvable only when models reach certain scale and trained on sufficiently complex data. [Brown (020) demonstrate that L.MSs like GPT-3 can perform few-shot learning, indicating that exposure to wide range of linguistic contexts and complexities enhances the models' adaptability and understanding, [Hoffmann et al. (2022) emphasize the importance of data scaling laws, showing that increasing the amount and complexity of training data can lead to better performance than merely increasing model size, suggesting trade-off between model capac- ity and data complexity. Kaplan et al. (2020) introduce scaling laws for neural language models, illustrating how performance improves predictably with model size, dataset size, and computational resources, but also noting that the nature of the data plays a crucial role.
Reservoir Computing and Chaotic Systems Reservoir Computing (RC) leverages fixed, high- dimensional dynamical systems-ofter randomly initialized recurrent neural networks-to model nonlinear and chaotic systems (Maass et al. 2002). It projects input signals into high-dimensional space, capturing temporal patterns through inherent dynamics while only training the output weights (Lukoševičius & Jaeger 2009). This simplifies training and allows the system handle chaotic behavior without adjusting internal weights. RC has been successfully applied to tasks like time series prediction and system identification (Pathak et al. 2018), effectively harnessing chaotic system dynamics for computation.
7 DISCUSSION
In this work, we utilize LLMs trained on elementary cellular automata (ECA) to study how intelli- gent behavior may emerge in large language models (LLMs) when trained on increasingly complex systems. Our findings reveal several important trends that contribute to understanding the relation- ship between complexity and model behavior.
Optimal complexity: the "edge of chaos" We observe that the best model performance occurs in systems operating at high but not excessive complexity, previously referred to the "edge of chaos" (Langton 1990). Models trained on Class IV ECA rules, which exhibit structured yet com- plex behaviors, perform optimally, suggesting that intelligence may emerge in systems that balance predictability and complexity. On the one hand, if a system is too simple and predictable, like those governed by Class and II rules, the model quickly learns a trivial solution and fails to develop more sophisticated reasoning. On the other hand, highly chaotic rules from Class III provide too much randomness, akin to training on noise, where the lack of meaningful patterns prevents the model from finding useful structure. The sweet spot arises when complexity is high enough to challenge the model but still retains underlying patterns that the model can exploit. This balance between order and randomness seems particularly conducive to fostering intelligent behavior, as it forces the model to develop more effective reasoning and processing strategics.
Complex solutions for irreducible systems pable of learning complex, non-trin trivial solutions even when simpler, more trivial ones are available, likely because they are overparametrized. For ECA nules generating lower-complexity data, the
Our findings demonstrate that large models

---

Published as a conference paper at ICLR 2025
models often adopt trivial solution, focusing only the current state since no history is needed. However, when exposed to more complex data, models tend to leverage prior states, as indicated by the attention patterns in Figure Despite the memoryless nature of ECA systems, overparam- eterized models explore a broader search space, and solutions that integrate historical information may be more robust. We hypothesize that by learning incorporate past states, the model develops generalizable logic that can be reused across tasks. In contrast, a model relying solely on a triv- ial, state-specific rule would struggle transfer its knowledge to more complex downstream tasks. Thus, the ability to learn from past states may be key to the model's success in adapting to diverse problems.
Certain ECA rules, such as Rule 110, are known to be computationally irreducible, meaning their behavior cannot be predicted without directly computing each step (Wolfram) 1997). However, some studies suggest that even in these systems, partial predictability can be achieved under certain conditions (Israeli Goldenfeld 2004). This implies that models learning more complex, non- trivial solutions actually outperform simpler, irreducible approaches by leveraging approximate but efficient predictions. Rather than directly calculating each state, models can explore patterns and generalize from past states, potentially leading to solutions that are not only more robust across tasks but also more efficient than the irreducible solution.
Broader Impact Our findings connect to a larger body of work on the emergence of intelligence in large language models (LLMs). Understanding how LLMs develop sophisticated reasoning capa- bilities when trained on relatively simple data could offer new insights into why and how intelligence emerges in these models. This research may help shed light some of the open questions surround- ing LLMs, particularly how their internal representations evolve and how certain training conditions lead to more transferrable reasoning abilities.
In future work, this framework can be further explored by training larger LLMS on synthetic data generated by simple rule-based systems. Incorporating measures of complexity, such those used in this study, could provide a valuable tool for prioritizing and curating data, ensuring that models are exposed to information with the right balance of structure and randomness. This aligns with recent advances in data curation, where data quality and complexity, rather than quantity, is increasingly
emphasized in improving model performance (Zhao al. 2023 Cao al. 2023
Liu et al. 2023).
Additionally, this work may have implications for our understanding of human intelligence, which is proposed have evolved
mechanism for interacting with complex and hard-to- hard-to-predict world (uler 2018). The idea that intelligence arises in systems operating at the "edge of chaos" parallels cognitive science theories suggesting that human brains function a critical state between different dynamics (Cocchi et al., 2017] Hesse & Gross 2014; O O'Byrne & Jerbi 2022). By exploring the conditions under which LLMs develop intelligence, we may gain new insights into the fundamental processes that underlie both artificial and human cognition.
8 REPRODUCIBILITY STATEMENT
To facilitate the reproduction of our results, we have provided detailed descriptions of our data pro- cessing methods and experimental procedures in Sections and Jndd We utilized the GPT-2 model ob- tained from Hugging Face for our experiments. The complete code for our paper is now available in at the adde__of_chaoe
the following GitHub repository: http::/ggihuh..co//vanjiiikllll
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Algebraic chess notation chessprogramming wiki. httpss//ww..chesppppppaammmi
org/Algebraic htt.aleeerraiccChes__ttttttaaaaa Accessed: 2024-09-30.
Lichess elite database.
hiw.oooee...ikoooe.......... Accessed: 2024-09-30.
Zlib: A massively spiffy yet delicately unobtrusive compression library. htttp::/ww..2..
net/ Accessed: 2024-09-30.
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
Som Banerjee and Mamata Dalui. Identification of ECA rules forming MACA in periodic boundary condition. International Journal of Modern Physics C, pp. 2450173, July 2024. ISSN 0129-1831, 1793-6586. doi: 10.1142/0012118312450000 com/doi/10 11/2/ 01144////00111111444000
URL
Mark Bedau. Artificial life: organization, adaptation and complexity from the bottom up. Trends in cognitive sciences, 7(1 ((11):505-512 2003. 2003..
Jaime A Berkovich and Markus J Buehler. Lifegpt: Topology-agnoste generative pretrained trans- former model for cellular automata. arXiv preprint arXiv:2409. /2/82, 2024.
Charles L Bouton. Nim, game with complete mathematical theory. Annals of mathematics, (1/4):35-39, 1901.
Tom B Brown. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess. Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. CoRR, 2020. URL htt.h: htt.:ps://aaxiv.oeee www.org//abs//oooo 2005. 14165
Yihan Cao, Yanbin Kang, and Lichao Sun. Instruction mining: High-quality instruction data selec- tion for large language models. arXiv preprint arXiv:2307.06299, 2023.
Alonso Castillo-Ramirez and Maria G. Magaña-Chavez. A study on the composition of elementary cellular automata, 2023. URL ttltstttt:::: wttp://gggabbb.....oooo 02947
François Chollet. On the measure of intelligence, 2019. URL
1911.01547
Luca Cocchi, Leonardo L Gollo, Andrew Zalesky, and Michael Breakspear. Criticality in the brain:
A synthesis of neurobiology, models and cognition. Progress in neurobiology, 158:132-152. 2017.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. arXiv preprint 1906. 18299, 2019.
Matthew Cook. A concrete view of rule 110 computation. arXiv preprint arXiv:0906.32243 2009.
Matthew Cook et al. Universality in elementary cellular automata. Complex systems, 15(1):1-40, 2004.
Erendira Corona- Besona--ermúezz... Juan Carlos -himal-Eguía, and Germán Téllez-Castillo, Cryptographic Services Based Elementary and Chaotic Cellular Automata. Electronics, 11(4))613, February 2022. ISSN 229929292 doi: 10.3390/electromics 1040613. URL wwww mdpi. com/ 2079 0111999999/111////
11

---

Published as a conference paper at ICLR 2025
James P Crutchfield and Melanie Mitchell. The evolution of emergent computation. Proceedings of the National Academy of Sciences, 92(23):10742-10777 1995.
Jacob Devlin, Ming-Waiee Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1810.04805, 2018. URL
http::/arxtt V org/ abs 1811 1080 04805
Dominic Edelmann, Tamás F Móri, and Gábor J Székely. On relationships between the pearson and the distance correlation coefficients. Statistics & probability letters, 169:108960, 2021.
Matthew J Euler. Intelligence and uncertainty: Implications of hierarchical predictive processing for the neuroscience of cognitive ability. Neuroscience & Biobehavioral Reviews, 94:93-112, 2018.
Janina Hesse and Thilo Gross. Self-organized criticality as a fundamental property of neural sys- tems. Frontiers in systems neuroscience, 8: 8:166, 2014.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Train- ing compute-optimal large language models. arXiv preprint arXiv:2203.15556 2022.
Navot Israeli and Nigel Goldenfeld. Computational irreuciibility and the predictability of complex physical systems. Physical review letters, 92(7):074105, 2004.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836) 2020.
Daniel Martin Katz, Michael James Bommarito, Shang Gao, and Pablo Aredondo. GPT-4 Passes the Bar Exam, March 2023. URL PRLpsttps::/pppeess sarn. com/ abs
Stuart A Kauffman. Origins of order in evolution: self-organization and selection. In Understanding origins: Contemporary views on the origin of life, mind and society, pp. 153-181. Springer, 1992.
Diederik Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.698., 2014.
Chris G. Langton. Computation at the edge of chaos: Phase transitions and emergent computation. Physica D: Nonlinear Phenomena, 42( 42(1):12-37 1990. ISSN 0167-2789. doi: https:/doi..og org/
10.00160066--2779900999996-666 URL httpt:ttt///.m htt.:pp:://ww... sci encedi rect. com/ sci ence/
axticiee/.1101177779990000
A. Lempel and J. Ziv. On the complexity of finite sequences. IEEE Transactions Information Theory, 22(1):75-81, 1976. doi: 10. 10.1109//T..197.1 1055501.
Wei Liu, Weihao Zeng, Keqing He, Yong Jiang, and Junxian He. What makes good data for align- ment? a comprehensive study of automatic data selection in instruction tuning. arXiv preprint wrXiv:2312.15685, 2023.
Mantas Lukoševičius and Herbert Jaeger. Reservoir computing approaches to recurrent neural net- work training. Computer science review, 3(3):127-149, 2009.
Wolfgang Maass, Thomas Natschläger, and Henry Markram. Real-time computing without stable states: A new framework for neural computation based perturbations. Neural computation, 14 (11):2531-255 25660, 2002.
Pierre-Étienne Meunier. Unraveling simplicity in elementary cellular automata. Theoretical Com- puter Science, 641:2-10, August 2016. ISSN 03043975. doi: 10.10166f.ces22016.1..0000 URL
https: http:::///iiiigghhbb www.weeseeee..... com htt.a//www....eeeeeeeeeeee/////.
Melanie Mitchell, Peter Hraber, and James P Crutchfield. Revisiting the edge of chaos: Evolving cellular automata to perform computations. arXiv preprint adap-org/930300. 1993.
Jordan O' Byrne and Karim Jerbi. How critical is brain criticality? Trends in Neurosciences, 45(11); 820-837, 2022.
12

---

Published as a conference paper at ICLR 2025
N.H. Packard. Adaptation Toward the Edge of Chaos. University of Illinois at Urbana- Champaign, Center for Complex Systems Research, 1988. URL https://bookks google.
Daniel E Parker, Xiangyu Cao, Alexander Avdoshkin, Thomas Scaffidi, and Ehud Altman. A uni- versal operator growth hypothesis. Physical Review X, (4):041017, 2019.
Jaideep Pathak, Brian Hunt, Michelle Girvan, Zhixin Lu, and Edward Ott. Model-free prediction of large spatiotemporally chaotic systems from data: A reservoir computing approach. Physical review letters, 120(2):024102, 2018.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Manan Larivo Rasolonjanahary and Bakhtier Vasiev. Formation of Morphogenetic Patterns in Cel- lular Automata. In Valeria V. Krzhizhanovskaya, Gábor Zävodszky, Michael H. Lees, Jack J. Dongarra, Peter M. A. Sloot, Sérgio Brissos, and João Teixeira (eds.), Computational Sci- ence ICCS 2020, volume 12142, pp. 359-373. Springer International Publishing, Cham, 2020. ISBN 9783030504328 9783030504335. doi: htttps://iink.spt
URL
5_28
Anian Ruoss, Grégoire Delétang, Sourabh Medapati, Jordi Grau-Moya, Li Kevin Wenliang, Elliot Catt, John Reid, and Tim Genewein. Grandmaster-level chess without search. arXiv preprint arXiv:2402.044994 2024.
Thomas Staubitz, Ralf Teusner, Christoph Meinel, and Nishanth Prakash. Cellular automata as basis for programming exercises in a mooc driven development. 2016 IEEE International Conference on Teaching, Assessment, and Learning for Engineering (TALE), pp. 374-380, 2016. doi: 10.1109/TALE.200 201...01667555 78584. 2..7858444..
J. von Neumann. Theory of Celf-Reproducing Automata. University of Illionois Press, Champain, IL, 1966.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yo- gatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint MXXi::22060066.1 2022.
A. Wolf. 13. Quantifying chaos with Lyapunov exponents. Arun Holden (ed.). Chaos, pp. 273-290. Princeton University Press, December 1986. ISBN 9781 400858156 doi: 10. 1515/9781 4007788140088816.66..6. URL /tttts://///// http://www.gg..r.rrrrreme com/ htt http://ccmmeeto////o//e// /htll
Stephen Wolfram. Statistical mechanies of cellular automata. Rev. Mod. Phys., 55:601-644, Jul
1983. doi: 10.1 1011///eMoodyyyy555.000 RevModPhys 55. 601
//isk////nkkk.////////// aps wttpp///rg///////o.o.. https/////..a.pp..orr////////.11
Stephen Wolfram. Universality and complexity in cellular automata.
Physica D: Non-
linear Phenomena, 10(1):1335, 1984. ISSN 0167-2789. doi: https//doo.orr/10.
101600167-2799(88904445- URL lattps://ww/ http///wwwwwinncceeeetttte/ htt.aa/cccieecc.cccccccceeeeeeee
att.icle/p11101177779883333
Stephen Wolfram. New kind of science, 1997.
Stephen Wolfram and M Gad-el Hak. new kind of science. Appl. Mech. Rev. 56(2):B18-BI B19, 2003.
Stephen Wolfram and Alexander Mallinckrodt. Cellular automata and complexity. 1994. URL https://api. cesaanicccchllae org./oorpuIID:22777777 62571078
Yingxiu Zhao, Bowen Yu, Binyuan Hui, Haiyang Yu, Fei Huang, Yongbin Li, and Nevin 7hang A preliminary study of the intrinsic relationship between complexity and alignment. arXiv preprint arXiv:2308.05660 2023.
13

---

Published as a conference paper at ICLR 2025
A SCALING EXPERIMENTS
In this section, we explore the interplay between data complexity, model capacity, and data volume in the learning process. We conducted scaling experiments using three transformer-based models:
1. A 67k-parameter custom single-layer transformer with one attention head and 64- dimensional embeddings ("Tiny"),
2. An 35M-parameter GPT-2 small model with 12 layers, 12 attention heads, and 768- dimensional embeddings ("Small"), and
3. A r08M-parameter GPT-2 large model with 36 layers, 20 attention heads, and 1280- dimensional embeddings ("Large").
Each model is pretrained on various quantities of ECA -eeeereeetteed data with varying complexities.
Thy
Small (85M)
Data Elliiieney (Rale
0.771
r-
Tikken Chasamppke
1.
10
Tolon Conoomppin
Validalion
214
Tiay (b7b)
(S5M]
022
Loge (7164))
Complsaty
Langel-Zii Cumplesily
Tokom consumption
Figure 5: Scaling experiments with varying quantities of data and different model sizes. Left: Number of tokens seen before convergence during pre-training for the Tiny model. Center: Number of tokens seen before convergence during pretraining for the Small model. Right: Validation loss as a function of token consumption for models trained on data from ECA Rule 110. Larger models achieve lower validation loss with fewer tokens, highlighting the improved data efficiency for larger models.
Figure 5 illustrates the results of these experiments. The left and middle panels show that as the complexity of the data increases, both models require more tokens to reach convergence. This trend indicates that higher data complexity demands more data for effective learning. Notably, the right panel demonstrates that the Small model achieves lower validation loss faster than the Tiny model when trained on complex data (and similarly for Large vs. Small), suggesting that larger models can learn more efficiently from complex patterns.
These findings highlight trade-off between data complexity, model capacity, and data volume. While complex training data can enhance model capabilities, it necessitates more data for smaller models to learn effectively. However, increasing model capacity can mitigate this requirement by enabling faster convergence, thereby reducing the amount of data needed.
B THE ROLE OF TEMPORAL STRUCTURE IN LEARNING REPRESENTATIONS
To discern whether temporal structure is necessary or if spatial complexity alone sufficient for better feature learning, we performed an ablation study by disrupting the sequential nature of the ECA data. Specifically, we randomly shuffled the temporal order the states generated by the ECAs while preserving their spatial configurations. This manipulation retains the spatial complexity but removes the inherent temporal structure, effectively isolating the spatial component.
We trained models on this temporally shuffled data following the same procedures as detailed in Section 3 The performance these models on the easy reasoning task showed a significant drop compared to models trained on the original, temporally ordered data. As shown in Figure 6 models trained on temporally structured data reached 80% accuracy in significantly fewer epochs than those trained temporally shuffled data.
14

---

Published as a conference paper at ICLR 2025
(ABC.
0.63
0002
0001
0000
Tea
Figure 6: Impact of temporal shuffling on downstream task performance. Models trained on tempo- rally shuffled ECA data exhibit decreased efficiency on the easy reasoning task compared to models trained on ordered data, highlighting the importance of temporal structure in learning effective rep- resentations. The average efficiency for each Wolfram class on ordered data is shown with dashed lines for reference. (*) indicates models that did not reach the 80% accuracy threshold.
These results underscore the critical role of temporal information in ECA data in enabling models to learn representations that generalize effectively. While spatial complexity provides rich patterns, is the structured temporal evolution that allows models to capture dynamic relationships and develop more sophisticated reasoning abilities. This experiment confirms that both spatial and temporal complexities are necessary components for training models capable of generalizing and performing complex reasoning tasks.
C DOWNSTREAM TASK: NIM GAME
To further evaluate the models' ability to generalize and perform strategic reasoning, we tested their performance on predicting optimal moves in the game of Nim, a classic mathematical strategy game (Bouton 1901). In Nim, players take turns removing objects from distinct heaps, aiming to be the one who removes the last object. Optimal play involves computing the binary addition of heap sizes, making this game ideal test for logical reasoning and pattern recognition.
We constructed a dataset comprising sequences of Nim game states and their corresponding opti- mal moves. To produce diverse scenarios for challenging task, we simulate games starting with between 5 and 15 heaps and 1 to 10 items in each heap. Each game state is represented as a string starting with the initial configuration of the heaps, followed by a sequence of moves until the game terminates when all the heaps are empty. Each move is encoded as the player number, followed by the heap identifier, followed by the number of items removed. For example, "1B3" signifies "Player I removed 3 items from heap B". Each possible move and heap state corresponds to a unique token for the embedding layer of the model. The dataset was split into training and validation sets using 90-10 ratio.
Using the same approach in previous downstream tasks, we trained models with the ECA- pretrained weights frozen, allowing only the input embedding and output layers to be updated. Figure the relationship between model efficiency and the complexity of the ECA rule used during pretraining- We found that the Nim game is considerably harder than the ARC reasoning tasks, and most models are unable to get accuracies greater than 20%. We adjust our definition of "efficiency"" accordingly to divided by number of epochs to reach 20% accuracy. We observed a significant (p- < 0.05) positive correlation between data complexity and model performance on the Nim task, consistent with our earlier findings on reasoning and chess benchmarks. Models pre- trained on more complex data required fewer epochs to reach a given level of accuracy. indicating that complex pretraining data facilitates the acquisition of strategic reasoning abilities.
These results reinforce the idea that pretraining on complex data structures enables models to de- velop more sophisticated representations, which can be effectively leveraged in downstream tasks.
15

---

Published as a conference paper at ICLR 2025
J00
110
244
Lempel Zir Complexity
Figure 7: The relationship between performance in the Nim game task and data complexity. Higher data complexity is correlated with increased efficiency, measured as 1 divided by the time to reach 20% accuracy. The data has a statistically significant correlation coefficient of r = 0.63, consistent with the trends we observed with the other downstream tasks.
D CORRELATION COEFFICIENTS AND HYPOTHESIS TESTING
We computed the Pearson correlation and the distance correlation coefficients (Edelmann et al. 2021 between the rule complexity and the performance on all downstream tasks. Whereas the Pearson correlation coefficient measures the linear dependence between variables, the distance cor- relation is capable of measuring non-linear association as well. The correlation coefficients and their respective p-values for the Lempel-Ziv complexity are given in Table T
Table 1: Summary of Correlation Analysis Results for Downstream Tasks
Task
Pearson Correlation
Distance Correlation
ARC-Easy
0.7322 (p = 4.93 x 10 10-18 18)
0.7163 (p = 4.97 10
ARC-Hard
0.3896 (p 5.04 x 10-4)
0.4444 (p 4.97 x 10-3)
Chess
0.4371 (p 9.73 x 10-3)
0.4329 (p 2.99 10 10-2)
NIM
0.6314 (p 3.31 10-6)
0.7108 (p 4.97 10-3)
E RESULTS FOR OTHER COMPLEXITY MEASURES
The downstream results for the ARC Easy, ARC Hard, and Chess tasks as a function the com- pression complexity. Lyapunov exponent, and Krylov complexity measures are shown in Figure g We observe the same general patterns that we see with the Lempel-Ziv complexity Figure 2
16

---

Published as a conference paper at ICLR 2025
Comproosio Complesity
Lynpunov Exponent
Kryler Complesity
0.008
0,008
I=00.54 6."
0.008
0.74
Reconing (AII Eany)
0.004
0.004
0.004
0.002
0.000
0.002
1001
150
01.11
50
100
0.0007
0.0007
6P
Betoching (ABC llno)
0.0000
0.00006
0.0000
Eltelene
1000000
0.0000
0.0004
0,0004
0.0004
0.0003
0,0003
0.0005
0.0002
0.0002
0.0002
0.0001
0.0001
0.0000
0.205
r=0.43
0.200
F=0
0.905
0-5.4
Closs Moae Prefictka
0,200
Acouracy
0.195
0.180
0.180
0.180
150
200
0.2
50 Complexity
100
Complexity
Complestng
Figure 8: Relationship between downstream task performance and data complexity for other com- plexity measures. Rows depict easy reasoning, hard reasoning, and chess move prediction tasks, while columns show compression complexity, Lyapunov exponent, and Krylov complexity, respec- tively. Baseline results for randomly initialized transformers are shown with a dashed black line.
17


Reviews:
[{"review_id": "uyjGD84y4j", "reviewer": "Reviewer_rE2s", "summary": "The paper explores whether LLMs can develop generalisable reasoning abilities by pretraining on structured but simple datasets, specifically sequences generated by cellular automata. The authors hypothesise that exposing models to complex patterns, even if the underlying system is deterministic and rule-based, could improve the models’ performance on reasoning tasks. By pretraining LLMs on cellular automata generated data, they test whether this training improves performance on abstract reasoning benchmarks, such as tasks from the Abstraction and Reasoning Corpus and chess move prediction (after finetuning).\n\nThe results show that models exposed to complex patterns, those generated by \"edge-of-chaos\" traces, perform better on these reasoning tasks compared to models pretrained on simpler or more chaotic traces. This suggests that pretraining on richer, more complex patterns helps LLMs develop broader generalisation abilities, even when the training data lacks semantic content.", "questions": "In my view the paper is quite interesting and a good fit for ICLR, and would like see it accepted if some of its weaknesses are addressed. Some questions:\n\n- (see above) What role does the temporal structure of CA sequences play in learning generalisable representations?\n- Is the amount of data required from CA pretraining comparable to the amount of data required using natural langage (or similar complex data), to reach similar generalisation effects?\n- what's the trade-off between complexity and volume of data", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I like about this paper that it uses a relatively simple approach to create data with varying (and quantifyiable) degrees of complexity. The approach could help in exposing LLMs to large amounts of data, potentially leading to smaller requireemtns of corpora during pretraining. The \"edge-of-chaos\" idea has been investigated in neural networks before, but not as a result of pretraining with data from CAs.\n\nThe approach of pretraining on CAs and finetuning the outputs later seems like a great fit to learning representations / ICLR - an interesting way to derive good features for training models.", "weaknesses": "While I like the idea and the approach of the paper, the choice of words could be improved and language be more precise. The choice of \"Intelligence\" in the title and throughout the paper is awkward, the work doesn’t necessarily show \"intelligence\" in the sense of true reasoning or understanding: it demonstrates however that structured complexity in data can lead to the development of generalisable features or representations, that is a better choice would be to describe the approach as learning useful features or representations for predictions or other complex tasks.\n\nThe language around the CA rules is also imprecise - all CA rules are similarly simple, but some of the rules lead to complex (or chaotic, or simple...) outputs / traces. It is the generated data that exhibits the complex patterns in case of the class iv CAs. \n\nAs an ablation, it might also be interesting to explore if it is the *structured* complexity that leads to better features, or if complex patterns are sufficient. This could be achieved by using surrogate outputs from CAs (ie scramble the temporal order), to allow the distinction between the complex (spatial) pattern or the structured, sequential nature of the data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "a9gb880z2Y", "reviewer": "Reviewer_YCfn", "summary": "The authors explore how the complexity of the rule of the data generative system influences the model capabilities on the downstream tasks. They use elementary cellular automata (ECA) as a rule-based dynamic system to control complexity of the training data trained GPT-2 derived transformer architecture and evaluated the trained model on reasoning/chess move prediction tasks. They found that higher but not too chaotic complex system leads to higher downstream task performance. Also, they found that the model trained with more complex system tends to obtain more complex solution rather than a simple rule, which the authors hypothesized as a reason for better downstream task performance.", "questions": "- Could you comment on the differences between \"complexity\" and \"diversity\" in ECA model? Is any of the complexity measures you incorporate captures diversity of the data as well? Are complex data always more diverse and vice-versa? \n\n-  In figure 2 violin plot, it seems like it's not only mean values but also variances that are correlated to the complexity measure and downstream tasks which I found interesting.  Could the authors provide comment?\n\n- Related to the weaknesses I wrote above, I am curious about baseline performance of the models before pre-trained on ECA data. \n\n- I see different tendency on Krylov complexity compare to the other on fig 3 i.e. high variance on both very low and very high complexity measure. Is there any reason that you could think of?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- I really enjoyed reading the paper. The authors explore the impact of rule complexity of the training data on the model's downstream task performance. I believe it is important and timely subject as there are already many literatures suggesting the importance of data property on acquired intelligence of the neural network models. \n- The paper is well motivated and the authors made good connection to the related previous works on complexity and computational capabilities.\n- Particularly, I liked the ECA data model that the authors use, which provides a good control of complexity of the rule-based dynamical system. Also, the authors used multiple measures of complexity rather than single definition. \n- The paper is well-written, it was easy to follow and understand the key claims that the authors make.", "weaknesses": "- While I am fairly convinced with the motivation and general results, but the presented quantitative result is rather weak in the results and figures they provide. Is the difference between accuracy across complexity, for example, in figure 2, shows fairly low r value.  \nFor wolfram's complexity class categorization, does the p-test shows significance? The absolute accuracy difference between the categories look fairly low. And the baseline performance without the ECA pretraining is not provided. \n\n- Did the authors run experiments with multiple seeds?\n\n- The claimed 'emergent' intelligence is only evaluated on the downstream tasks after post-tuning, and in limited kinds. Also, the baseline performance without the pre-training on ECA is not given. \n\n- While authors found that the model trained with complex system tends to obtain more complex solution than the actual rule and made a interesting conjecture that this might be the reason for better downstream performance, no rigorous experiment to further investigate this point is provided. \n\nFurther questions and comments are given in the next section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "f4B8LzE4zx", "reviewer": "Reviewer_8JtY", "summary": "The authors of this paper utilize a large language model (GPT-2) to demonstrate \"Intelligence at the Edge of Chaos,\" showing that models achieve optimal performance in moderately complex, but not overly chaotic, systems. They train on tasks based on elementary cellular automata (ECA) and evaluate on various downstream tasks to explore the link between system complexity and emergent intelligence. The results align well with their hypothesis, though additional experiments could further strengthen these findings.", "questions": "1. Could you include more downstream tasks, like nim games or cylinder chess, to expand the evaluation?\n\n2. Could you test on smaller models, such as ResNet-50, BERT, or Mamba-170m, to validate the results?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper’s topic is innovative, as I believe the emergence of intelligence is fostered by increasingly large architectures capable of handling complex data. The authors devote significant attention to explaining the concept of the \"Edge of Chaos,\" ensuring a thorough understanding of this idea. Their explanation of the results is also convincing, and the paper’s visual illustrations are highly effective.", "weaknesses": "The experiments are somewhat limited. Adding more downstream tasks, such as nim games or toroidal chess, could enhance the findings. Additionally, testing the hypothesis on smaller models could provide further support, rather than relying solely on results from larger models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "3tKRt79L73", "reviewer": "Reviewer_JMh7", "summary": "This paper explores a potential connection between complexity and intelligence using data from elementary cellular automata (ECA) — a class of discrete dynamical systems that exhibit simple, complex, and chaotic dynamics. The authors find that transformers trained on complex and chaotic dynamics perform better on downstream tasks. They first train transformers on these dynamical systems, then adapt the pre-trained transformer to other tasks while freezing the transformer weights and only training the encoder/decoder layers.", "questions": "1. How does this relate to Reservoir Computing (RC)? A randomly initialized RC can also perform well on nonlinear and chaotic tasks. How do you distinguish between the sources of good performance—complexity versus reservoir effects?\n2. Beyond the trivial explanation mentioned above, what other reasons might explain why the transformer learns to use attention? Have you experimented with varying model sizes? It's possible that more powerful models might not require attention, while smaller models (or those trained with high L2 regularization) might need attention to allocate more computational resources.\n3. Does this relate to the principle of computational equivalence?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper proposes a novel approach to studying connections between complexity and intelligence. By pre-training transformers on complex patterns, it aligns with large language model (LLM) studies, which have demonstrated that high-quality training data leads to better performance on testing tasks. This study conducts thorough experiments across various tasks, examining the topic from different perspectives. It reveals significant performance differences in transformers trained on different cellular automata.", "weaknesses": "The most critical issue in this paper is the method of generating training data. As mentioned in lines 146-152, you first generate a large spatiotemporal evolution, then extract only a small spatiotemporal window from it. This approach inadvertently introduces randomness into the evolution because information outside the spatial window is lost, yet its effects continue to diffuse into the observed space. The authors appear to overlook this randomness, claiming the system is deterministic. They then use a linear encoder/decoder to map states into hidden representations and predict the next state from these hidden states.\n\nThis mismatch may lead to several problems, potentially explaining some of the results observed in your paper:\n\n1. Your deterministic model may not be strong enough to learn highly random patterns;\n2. The attention pattern discovered in Figure 4 might be caused by this mismatch: For simple tasks, external unknown information may not diffuse into the space, so the cut windows contain truly deterministic dynamics, hence the transformer doesn't need to have attention on previous states. However, for complex patterns, information from states outside the window is necessary for prediction. Consequently, the transformers use previous states for better prediction, resulting in the observed attention patterns;\n3. This could lead to a trivial, yet unfalsified explanation of your discovery: the reason transformers trained on complex patterns perform well on downstream tasks might be because they have more attention. And the reason they have more attention might be caused by the unknown information outside the spatial window.\n\nTo address this issue, you could predict only part of the next state. For example, given state indices 1-60 as input, you could predict only states 2-59, thereby mitigating the problem. I’m wondering if you still observing the results when removing such randomness.\n\nSome other minor issues:\n\n1. The models should not been named as large language model (LLM) — they are not large, and not natural language. I would suggest using transformer instead;\n2. Around line 158, please define “binary vector”. Is it a vector of spatial pattern at given time?\n3. In line 232, why there isn’t rule 110 in ARC Easy / Chess Move? It is Turning complete, may need more attention on it.\n4. It will be good to compare to a randomly initialized transformer. Would complex ECAs beat random transformer?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)