REVIEW 3 major objections 6 minor 36 references
Learning Elementary Cellular Automata with Transformers
T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper claims that a Transformer trained on random Elementary Cellular Automaton orbits abstracts the underlying Boolean rule and that the ability to plan multiple steps ahead is controlled by the number of layers.
desk verdict Clean toy-domain task comparison, but the depth-scaling result is not supported by the reported single-run experiments. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the Elementary Cellular Automaton (ECA), a one-dimensional lattice of binary cells updated synchronously by a local rule $\rho: \{0,1\}^{2r+1}\to\{0,1\}$; with $W=20$ and $r=2$ there are $2^{32}\approx4.3\times10^9$ possible rules. The machinery is a Transformer encoder with masked tokens standing for unknown future bits or the unknown rule, trained under four task variants: O-S (orbit to next state), O-O (orbit to several future states), O-SR (orbit to next state plus rule), and RO-S (given orbit and rule, predict state). The rule-recovery estimate $T_{\min}=2^{2r+1}(\ln 2^{2r+1}+\gamma)/W\approx6.47$ from the coupon collector's problem tells how many orbit steps are needed, and the depth sweep on the O-O task is what carries the claim that each planning step needs more layers.
What would settle it
Repeat the O-O depth experiment with multiple random seeds and learning-rate schedules at layer counts 2, 4, 7, and 10, and record accuracy distributions. If the apparent thresholds shift by more than a layer or disappear when seeds vary, the claim that each planning step requires additional layers would not be supported; alternatively, a wider 4-layer model that predicts step 3 as well as the 7-layer model would falsify the depth-specific conclusion.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that a Transformer encoder with full self-attention can learn to predict the next state of an Elementary Cellular Automaton from a ten-step orbit and, more strongly, can do so for local rules never seen in training, meaning it has abstracted the underlying Boolean function rather than memorized a specific rule. When asked to jump several steps ahead without intermediate context, accuracy falls sharply, from about 0.96 for next-state prediction to below 0.75 for two or three steps ahead. Training with an orbit-to-orbit objective or with simultaneous rule prediction both improve planning, with the rule-prediction variant (O-SR) generalizing better at longer horizons, while explicitly supplying the rule (RO-S) does not rescue multi-step jumps. A depth experiment shows that four-step planning requires about ten layers, leading the author to conclude that sequential computation in Transformers is bounded by depth and that recurrence or adaptive computation time are promising remedies.
Load-bearing premise
The depth-scaling conclusion assumes that the exact layer counts at which accuracy first rises are real signals rather than random variation between training runs; no repeated runs or error bars are reported.
Editorial extensions
If this is right
- Transformers trained on random ECA orbits can predict the next state of unseen local rules with high per-bit accuracy, so rule abstraction from data alone is possible for Boolean functions of fixed arity.
- Adding future-state or rule prediction to the loss improves both next-state accuracy and autoregressive rollout quality; the rule-prediction variant generalizes best at look-ahead steps.
- Explicitly giving the rule (RO-S) does not fix multi-step planning beyond one or two steps, indicating the difficulty is in propagating intermediate state information, not in knowing the rule.
- Autoregressive generation outperforms direct multi-step look-ahead, so models are better at short state-by-state prediction than at jumping ahead without intermediate context.
- The number of layers required for accurate O-O prediction grows with planning horizon (2 layers for step 1, 4 for step 2, 7 for step 3, 10 for step 4), suggesting depth is the key architectural resource for sequential computation.
Reading between the lines
- If the depth-to-horizon scaling holds beyond this toy setup, fixed-depth models should systematically fail on planning problems whose solution requires more sequential rule applications than the network has layers; that is a testable prediction for arithmetic or multi-hop reasoning benchmarks.
- The O-SR result suggests rule-identification losses could act as a regularizer that compresses the hidden state into a causal rule; one could test this by probing the model's hidden vectors for the rule and correlating probe accuracy with planning accuracy.
- The coupon-collector estimate implies that the number of orbit steps needed to identify a rule grows exponentially in neighborhood radius; scaling ECAs to larger $r$ should make rule abstraction and planning degrade in a predictable way.
- Because RO-S fails at multi-step jumps despite having the rule, the bottleneck is not rule knowledge but the propagation of intermediate states; architectures with explicit memory or recurrent state updates should be tested on the same task.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies whether Transformer encoders can learn the local rules of Elementary Cellular Automata (ECA) from observed orbits and use them for multi-step planning. Four training objectives are compared: next-state prediction (O-S), multi-step prediction (O-O), joint state and rule prediction (O-SR), and state prediction given the rule (RO-S). The authors report that the model reaches about 0.96 per-bit accuracy for next-state prediction on held-out rules, that look-ahead accuracy drops for k≥2, that O-SR improves longer look-ahead over O-O, that autoregressive rollouts are more accurate than direct look-ahead, and that deeper models are needed to predict more steps ahead, with step 1 needing 2 layers, step 2 needing 4, step 3 needing 7, and step 4 needing 10 layers.
Significance. If the claims hold, the paper offers a clean testbed for studying how Transformers abstract discrete rules and a concrete demonstration that multi-step planning scales with depth, with implications for training objectives (longer horizons, rule prediction) and architecture (recurrence, adaptive computation) in LLMs. The setup is well chosen: test rules are disjoint from training rules, so next-state accuracy is evidence of generalization rather than memorization, and the authors provide code and data (GitHub link). The main limitation is that the experimental evidence is currently too thin—single runs, no error bars, and an undefined accuracy threshold for the depth scaling—so the central claims are plausible but not yet established.
major comments (3)
- [3 Results and Discussion (Figure 3)] The depth-scaling conclusion that "each additional planning step requires more computational layers" is not supported as presented. The thresholds (step 2 at 4 layers, step 3 at 7, step 4 at 10 layers) are read from single runs with no stated accuracy criterion for "predicting a step," and no error bars or seeds are reported. Additionally, because d_model=512 and 8 heads are held fixed while the layer count changes from 1 to 11, the experiment conflates depth with parameter count and training dynamics; a shallow-wide control is not reported. This point is load-bearing because the abstract and conclusions use this result to motivate recurrence and adaptive computation time.
- [3 Results and Discussion (Figures 2 and 3)] All accuracy figures appear to come from a single training run per condition; no random seeds, error bars, or significance tests are reported. Consequently, comparative statements such as "the O-SR model outperformed the O-O model" (0.85 vs 0.75 for k=2,3) and the "near-perfect accuracy" of RO-S for k=0,1 are not quantitatively supported. Please report at least a small number of seeds with mean and standard deviation, or otherwise justify the stability of the observed differences.
- [2 Methods] The training configuration is underspecified: the paper does not state the optimizer, learning rate and schedule, batch size, number of training steps, or compute budget, and for the O-SR objective it does not specify how the state and rule losses are weighted. Without these details the experiments are not reproducible, and the claim that rule prediction in the loss "enhances the ability to form internal representations" cannot be separated from arbitrary training choices. Please add full training details and, ideally, a sensitivity check on the loss weight.
minor comments (6)
- [3 Results and Discussion] The text refers to "Figure 3A," but the figure has no panel A; the caption reads "Figure 3: Adding layers improves prediction of ECA orbit." Please correct the cross-reference.
- [2 Methods] The coupon-collector estimate Tmin treats each cell-time observation as an independent draw, but adjacent cells in the same time step have overlapping neighborhoods, so the draws are correlated. The agreement with Figure 2A is therefore heuristic; please state this caveat or provide a more careful estimate.
- [2 Methods / Figure 1] The definition of "look-ahead steps" could be clearer: Figure 2B includes k=0 while the text defines k∈{1,2,3}; please state explicitly what k=0 denotes (presumably next-state prediction) and how "per-bit accuracy averaged over free runs" is computed.
- [3 Results and Discussion] The O-SR model's rule prediction accuracy is never reported, so the claim that it forms an internal representation of the rule is only indirectly evidenced. Reporting the rule-prediction accuracy (and how rule outputs are decoded) would strengthen the mechanistic interpretation.
- [3 Results and Discussion] In Figure 2D, the comparison between autoregressive (AR) and look-ahead (LA) predictions needs a precise definition of both modes; in particular, for AR, specify whether the model consumes its own previous output tokens as context and whether teacher forcing is used at any stage.
- [4 Conclusions] The phrase "we also confirmed that the model's depth plays a crucial role" overstates the evidence given the single-run, threshold-free analysis in Figure 3; please soften the wording to match the strength of the results.
Circularity Check
No significant circularity: the paper is an empirical training and evaluation study whose results are measured on held-out ECA rules, with no fitted input renamed as a prediction.
full rationale
The paper's central claims are empirical measurements, not derivations from fitted constants. The test set uses rules 'exclusive and not present in the training set', so the reported generalization across Boolean functions is measured on held-out data rather than forced by construction. The auxiliary rule-prediction loss in O-SR is an additional training objective, and its effect on planning accuracy is measured, not assumed. The Tmin coupon-collector estimate is an external calculation that is subsequently compared with the observed accuracy plateau in Fig. 2A; no parameter is fitted to the plateau and then reused to produce the plateau. The depth-scaling conclusion in Fig. 3 is an observed accuracy-versus-layers relationship; while the absence of error bars and an explicit accuracy threshold is a legitimate correctness concern, that is a statistical inference issue, not circularity. The paper contains no load-bearing self-citation: the only author-linked artifact is a public repository for dataset and code, and the cited prior work on cellular automata, transformers, and reasoning is external. No step in the derivation reduces, by the paper's own equations or by citation, to a restatement of its inputs. Therefore the appropriate finding is no significant circularity.
Assumptions & free parameters
free parameters (2)
- Input orbit length k =
10 time steps
- Minimum layer count thresholds for planning steps =
2, 4, 7, 10 layers for steps 1, 2, 3, 4
assumptions (3)
- domain assumption Training and test sets use disjoint random local rules, so good test performance indicates generalization to unseen rules.
- standard math The coupon-collector estimate Tmin = 2^5 (ln 2^5 + gamma) / 20 approximates the orbit length needed to identify a rule.
- domain assumption Per-bit accuracy computed on free runs is a valid proxy for rule learning and planning ability.
Cite this review
Pith. "Pith review of Learning Elementary Cellular Automata with Transformers." pith.science (2026). https://pith.science/paper/K5W2QN33
@misc{pith2026241201417,
author = {Pith},
title = {Pith review of: Learning Elementary Cellular Automata with Transformers},
year = {2026},
howpublished = {\url{https://pith.science/paper/K5W2QN33}},
note = {Machine review of arXiv:2412.01417}
}
read the original 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.
Figures
Reference graph
Works this paper leans on
-
[1]
Learning to reason with llms
OpenAI. Learning to reason with llms. https://openai.com/index/ learning-to-reason-with-llms/ , 2024. Accessed: 2024-09-23
2024
-
[2]
Faith and fate: Limits of transformers on compositionality
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al. Faith and fate: Limits of transformers on compositionality. Advances in Neural Information Processing Systems, 36, 2024
2024
-
[3]
A & b== b & a: Triggering logical reasoning failures in large language models
Yuxuan Wan, Wenxuan Wang, Yiliu Yang, Youliang Yuan, Jen-tse Huang, Pinjia He, Wenxiang Jiao, and Michael R Lyu. A & b== b & a: Triggering logical reasoning failures in large language models. arXiv preprint arXiv:2401.00757, 2024
arXiv 2024
-
[4]
Conditional and modal reasoning in large language models
Wesley H Holliday and Matthew Mandelkern. Conditional and modal reasoning in large language models. arXiv preprint arXiv:2401.17169, 2024
arXiv 2024
-
[5]
Inductive learning of logical theories with llms: A complexity-graded analysis
João Pedro Gandarela, Danilo S Carvalho, and André Freitas. Inductive learning of logical theories with llms: A complexity-graded analysis. arXiv preprint arXiv:2408.16779, 2024
arXiv 2024
-
[6]
Liar, liar, logical mire: A benchmark for suppositional reasoning in large language models
Philipp Mondorf and Barbara Plank. Liar, liar, logical mire: A benchmark for suppositional reasoning in large language models. arXiv preprint arXiv:2406.12546, 2024
arXiv 2024
-
[7]
Llms still can’t plan; can lrms? a preliminary evaluation of openai’s o1 on planbench, 2024
Karthik Valmeekam, Kaya Stechly, and Subbarao Kambhampati. Llms still can’t plan; can lrms? a preliminary evaluation of openai’s o1 on planbench, 2024
work page 2024
-
[8]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in neural information processing systems, pages 5998–6008, 2017. URL http://papers.nips.cc/ paper/7181-attention-is-all-you-need . 5
work page 2017
Show all 36 references
-
[9]
Approximations by superpositions of a sigmoidal function
George Cybenko. Approximations by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2:183–192, 1989
1989
-
[10]
Multilayer feedforward networks are universal approximators
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359–366, 1989
1989
-
[11]
Are transformers universal approximators of sequence-to-sequence functions? arXiv preprint arXiv:1912.10077, 2019
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? arXiv preprint arXiv:1912.10077, 2019
1912 arXiv
-
[12]
Representational strengths and limitations of transformers
Clayton Sanford, Daniel J Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. Advances in Neural Information Processing Systems, 36, 2024
2024
-
[13]
Uni- versal transformers
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=HyzdRiR9Y7
2019
-
[14]
On the computational power of transformers and its implications in sequence modeling
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006.09286, 2020
2006 arXiv
-
[15]
Attention is turing-complete
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1–35, 2021
2021
-
[16]
Transformers as recognizers of formal languages: A survey on expressivity
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. Transformers as recognizers of formal languages: A survey on expressivity. arXiv preprint arXiv:2311.00208, 2023
2023 arXiv
-
[17]
Deep learning for symbolic mathematics
Guillaume Lample and François Charton. Deep learning for symbolic mathematics. arXiv preprint arXiv:1912.01412, 2019
1912 arXiv
-
[18]
End-to-end symbolic regression with transformers
Pierre-Alexandre Kamienny, Stéphane d’Ascoli, Guillaume Lample, and François Charton. End-to-end symbolic regression with transformers. Advances in Neural Information Processing Systems, 35:10269–10281, 2022
2022
-
[19]
Deep symbolic regression for recurrent sequences
Stéphane d’Ascoli, Pierre-Alexandre Kamienny, Guillaume Lample, and François Charton. Deep symbolic regression for recurrent sequences. arXiv preprint arXiv:2201.04600, 2022
2022 arXiv
-
[20]
Luis M. Antunes. Cellpylib: A python library for working with cellular automata. Journal of Open Source Software, 6(67):3608, 2021. doi: 10.21105/joss.03608. URL https://doi.org/ 10.21105/joss.03608
2021 doi
-
[21]
Learning cellular automaton dynamics with neural networks
N Wulff and J A Hertz. Learning cellular automaton dynamics with neural networks. Advances in Neural Information Processing Systems, 5, 1992
1992
-
[22]
Cellular automata as convolutional neural networks
William Gilpin. Cellular automata as convolutional neural networks. Physical Review E, 100 (3):032402, 2019
2019
-
[23]
Generalization over different cellular automata rules learned by a deep feed-forward neural network, 2021
Marcel Aach, Jens Henrik Goebbert, and Jenia Jitsev. Generalization over different cellular automata rules learned by a deep feed-forward neural network, 2021
2021
-
[24]
Growing neural cellular automata
Alexander Mordvintsev, Ettore Randazzo, Eyvind Niklasson, and Michael Levin. Growing neural cellular automata. Distill, 5(2):e23, 2020
2020
-
[25]
Hierarchical neural cellular automata
Ritu Pande and Daniele Grattarola. Hierarchical neural cellular automata. In Artificial Life Conference Proceedings 35, volume 2023, page 20. MIT Press One Rogers Street, Cambridge, MA 02142-1209, USA journals-info . . . , 2023
2023
-
[26]
Cellular automata, many-valued logic, and deep neural networks
Yani Zhang and Helmut Bölcskei. Cellular automata, many-valued logic, and deep neural networks. arXiv preprint arXiv:2404.05259, 2024
2024 arXiv
-
[27]
E (n)-equivariant graph neural cellular automata
Gennaro Gala, Daniele Grattarola, and Erik Quaeghebeur. E (n)-equivariant graph neural cellular automata. arXiv preprint arXiv:2301.10497, 2023
2023 arXiv
-
[28]
Attention-based neural cellular au- tomata
Mattie Tesfaldet, Derek Nowrouzezahrai, and Chris Pal. Attention-based neural cellular au- tomata. Advances in Neural Information Processing Systems, 35:8174–8186, 2022. 6
2022
-
[29]
Learning graph cellular automata
Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Learning graph cellular automata. Ad- vances in Neural Information Processing Systems, 34:20983–20994, 2021
2021
-
[30]
Learning spatio- temporal patterns with neural cellular automata
Alex D Richardson, Tibor Antal, Richard A Blythe, and Linus J Schumacher. Learning spatio- temporal patterns with neural cellular automata. PLOS Computational Biology, 20(4):e1011589, 2024
2024
-
[31]
Learning locally interacting discrete dynamical systems: Towards data-efficient and scalable prediction
Beomseok Kang, Harshit Kumar, Minah Lee, Biswadeep Chakraborty, and Saibal Mukhopad- hyay. Learning locally interacting discrete dynamical systems: Towards data-efficient and scalable prediction. In Alessandro Abate, Mark Cannon, Kostas Margellos, and Antonis Pa- pachristodoul...
2024
-
[32]
It’s hard for neural networks to learn the game of life
Jacob M Springer and Garrett T Kenyon. It’s hard for neural networks to learn the game of life. In 2021 International Joint Conference on Neural Networks (IJCNN), pages 1–8. IEEE, 2021
2021
-
[33]
Data-centric approach to constrained machine learning: A case study on conway’s game of life
Anton Bibin and Anton Dereventsov. Data-centric approach to constrained machine learning: A case study on conway’s game of life. arXiv preprint arXiv:2408.12778, 2024
2024 arXiv
-
[34]
Reconstructing cellular automata rules from observations at nonconsecutive times
Veit Elser. Reconstructing cellular automata rules from observations at nonconsecutive times. Physical Review E, 104(3):034301, 2021
2021
-
[35]
Lifegpt: Topology-agnostic generative pretrained transformer model for cellular automata
Jaime A Berkovich and Markus J Buehler. Lifegpt: Topology-agnostic generative pretrained transformer model for cellular automata. arXiv preprint arXiv:2409.12182, 2024
2024 arXiv
-
[36]
Chain-of-thought prompting elicits reasoning in large language models
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837, 2022. 7
2022
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.