# Towards a theory of how the structure of language is acquired by deep neural networks

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 57 references that are in the map.
- First posted on arXiv 28 May 2024.

## Builds on (most cited first, 30 of 32)

- [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)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [BERT Rediscovers the Classical NLP Pipeline](https://mlsanity.com/paper/1905.05950/) (2019)
- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Are Emergent Abilities of Large Language Models a Mirage?](https://mlsanity.com/paper/2304.15004/) (2023)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [Predictability and Surprise in Large Generative Models](https://mlsanity.com/paper/2202.07785/) (2022)
- [Feature Learning in Infinite-Width Neural Networks](https://mlsanity.com/paper/2011.14522/) (2020)
- [Dissecting Contextual Word Embeddings: Architecture and Representation](https://mlsanity.com/paper/1808.08949/) (2018)
- [A Theory for Emergence of Complex Skills in Language Models](https://mlsanity.com/paper/2307.15936/) (2023)
- [A Dynamical Model of Neural Scaling Laws](https://mlsanity.com/paper/2402.01092/) (2024)
- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [Does syntax need to grow on trees? Sources of hierarchical inductive bias in sequence-to-sequence networks](https://mlsanity.com/paper/2001.03632/) (2020)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [Criticality in Formal Languages and Statistical Physics](https://mlsanity.com/paper/1606.06737/) (2016)
- [Deep Learning and Hierarchal Generative Models](https://mlsanity.com/paper/1612.09057/) (2016)
- [Learning Syntax Without Planting Trees: Understanding Hierarchical Generalization in Transformers](https://mlsanity.com/paper/2404.16367/) (2024)
- [A Provably Correct Algorithm for Deep Learning that Actually Works](https://mlsanity.com/paper/1803.09522/) (2018)
- [U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Models](https://mlsanity.com/paper/2404.18444/) (2024)
- [What Can Be Learnt With Wide Convolutional Neural Networks?](https://mlsanity.com/paper/2208.01003/) (2022)
- [LSTMs Compose (and Learn) Bottom-Up](https://mlsanity.com/paper/2010.04650/) (2020)
- [Autocorrelations Decay in Texts and Applicability Limits of Language Models](https://mlsanity.com/paper/2305.06615/) (2023)

## Built on by (most cited first, 30 of 39)

- [How Linguistics Learned to Stop Worrying and Love the Language Models](https://mlsanity.com/paper/2501.17047/) (2025)
- [A Percolation Model of Emergence: Analyzing Transformers Trained on a Formal Language](https://mlsanity.com/paper/2408.12578/) (2024)
- [Probing the Latent Hierarchical Structure of Data via Diffusion Models](https://mlsanity.com/paper/2410.13770/) (2024)
- [How Compositional Generalization and Creativity Improve as Diffusion Models are Trained](https://mlsanity.com/paper/2502.12089/) (2025)
- [Bigger Isn't Always Memorizing: Early Stopping Overparameterized Diffusion Models](https://mlsanity.com/paper/2505.16959/) (2025)
- [A distributional simplicity bias in the learning dynamics of transformers](https://mlsanity.com/paper/2410.19637/) (2024)
- [Deriving Neural Scaling Laws from the statistics of natural language](https://mlsanity.com/paper/2602.07488/) (2026)
- [How transformers learn structured data: insights from hierarchical filtering](https://mlsanity.com/paper/2408.15138/) (2024)
- [Learning curves theory for hierarchically compositional data with power-law distributed features](https://mlsanity.com/paper/2505.07067/) (2025)
- [Analyzing Neural Scaling Laws in Two-Layer Networks with Power-Law Data Spectra](https://mlsanity.com/paper/2410.09005/) (2024)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures](https://mlsanity.com/paper/2505.07070/) (2025)
- [Deep networks learn to parse uniform-depth context-free languages from local statistics](https://mlsanity.com/paper/2602.06065/) (2026)
- [Deep Learning of Compositional Targets with Hierarchical Spectral Methods](https://mlsanity.com/paper/2602.10867/) (2026)
- [Unraveling Syntax: Language Modeling and the Substructure of Grammars](https://mlsanity.com/paper/2510.02524/) (2025)
- [Scale Dependent Data Duplication](https://mlsanity.com/paper/2603.06603/) (2026)
- [Jailbreak Scaling Laws for Large Language Models: Polynomial-Exponential Crossover](https://mlsanity.com/paper/2603.11331/) (2026)
- [Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens](https://mlsanity.com/paper/2410.18858/) (2024)
- [Towards Worst-Case Guarantees with Scale-Aware Interpretability](https://mlsanity.com/paper/2602.05184/) (2026)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Incremental Learning of Sparse Attention Patterns in Transformers](https://mlsanity.com/paper/2602.19143/) (2026)
- [Sampling Data with Chains of Forward-Backward Diffusion Steps](https://mlsanity.com/paper/2605.27006/) (2026)
- [Learn from your own latents and not from tokens: A sample-complexity theory](https://mlsanity.com/paper/2605.27734/) (2026)
- [Statistical Properties of Training & Generalization](https://mlsanity.com/paper/2606.20299/) (2026)
- [Structure Before Collapse: Transient semantic geometry in next-token prediction](https://mlsanity.com/paper/2606.26749/) (2026)
- [Rethinking the Relationship between the Power Law and Hierarchical Structures](https://mlsanity.com/paper/2505.04984/) (2025)
- [Learning with Shallow Neural Networks on Cluster-Structured Features](https://mlsanity.com/paper/2605.14927/) (2026)
- [Self-supervised local learning rules learn the hidden hierarchical structure of high-dimensional data](https://mlsanity.com/paper/2605.18557/) (2026)
- [Testing Transformer Learnability on the Arithmetic Sequence of Rooted Trees](https://mlsanity.com/paper/2512.01870/) (2025)
- [Language models as tools for investigating the distinction between possible and impossible natural languages](https://mlsanity.com/paper/2512.09394/) (2025)

## Abstract (arXiv)

How much data is required to learn the structure of a language via next-token prediction? We study this question for synthetic datasets generated via a Probabilistic Context-Free Grammar (PCFG) -- a tree-like generative model that captures many of the hierarchical structures found in natural languages. We determine token-token correlations analytically in our model and show that they can be used to build a representation of the grammar's hidden variables, the longer the range the deeper the variable. In addition, a finite training set limits the resolution of correlations to an effective range, whose size grows with that of the training set. As a result, a Language Model trained with increasingly many examples can build a deeper representation of the grammar's structure, thus reaching good performance despite the high dimensionality of the problem. We conjecture that the relationship between training set size and effective range of correlations holds beyond our synthetic datasets. In particular, our conjecture predicts how the scaling law for the test loss behaviour with training set size depends on the length of the context window, which we confirm empirically in Shakespeare's plays and Wikipedia articles.