# Testing Transformer Learnability on the Arithmetic Sequence of Rooted Trees

arXiv: https://arxiv.org/abs/2512.01870 · HTML: https://mlsanity.com/paper/2512.01870/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 1 Dec 2025.

## Builds on (most cited first, 24 of 24)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [Understanding Factual Recall in Transformers via Associative Memories](https://mlsanity.com/paper/2412.06538/) (2024)
- [Disentangling Syntax and Semantics in the Brain with Deep Networks](https://mlsanity.com/paper/2103.01620/) (2021)
- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [Machine-Learning Mathematical Structures](https://mlsanity.com/paper/2101.06317/) (2021)
- [A polar coordinate system represents syntax in large language models](https://mlsanity.com/paper/2412.05571/) (2024)
- [A distributional simplicity bias in the learning dynamics of transformers](https://mlsanity.com/paper/2410.19637/) (2024)
- [Deep-Learning the Landscape](https://mlsanity.com/paper/1706.02714/) (2017)
- [Mapping of attention mechanisms to a generalized Potts model](https://mlsanity.com/paper/2304.07235/) (2023)
- [Sometimes I am a Tree: Data Drives Unstable Hierarchical Generalization](https://mlsanity.com/paper/2412.04619/) (2024)
- [Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures](https://mlsanity.com/paper/2505.07070/) (2025)
- [Classification of integers based on residue classes via modern deep learning algorithms](https://mlsanity.com/paper/2304.01333/) (2023)
- [Integer Factorisation, Fermat & Machine Learning on a Classical Computer](https://mlsanity.com/paper/2308.12290/) (2023)
- [Exploring Prime Number Classification: Achieving High Recall Rate and Rapid Convergence with Sparse Encoding](https://mlsanity.com/paper/2402.03363/) (2024)
- [Discrete Denoising Diffusion Approach to Integer Factorization](https://mlsanity.com/paper/2309.05295/) (2023)
- [Machine Learning of the Prime Distribution](https://mlsanity.com/paper/2403.12588/) (2024)

## Abstract (arXiv)

We study whether a transformer network can learn the deterministic sequence of trees generated by the iterated prime factorization of the natural numbers. Each integer is mapped into a rooted planar tree and the resulting sequence mathbbNmathscrT defines an arithmetic text with measurable statistical structure. A transformer network (the GPT-2 architecture) is trained from scratch on the first 1011 elements and evaluated on Next-Token and masked-word prediction tasks, with a Hidden Markov Model as baseline and a scaling analysis over context window, dataset size, vocabulary size and model size. The model reaches a word accuracy of about 0.4, well above the baseline, and its performance remains stable on test blocks located at 1013--1015, far beyond the training interval. Moreover, the likelihood assigned by the model separates the arithmetic text from two controls: synthetic sequences reproducing its word frequencies exactly but carrying no sequential organization, with a separation that widens as the evaluated context grows; and sequences containing more than three consecutive square-free integers, a configuration that arithmetic forbids. These results indicate that the transformer captures regularities of the arithmetic text that go beyond its frequency profile.