# Deep networks learn to parse uniform-depth context-free languages from local statistics

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 50 references that are in the map.
- First posted on arXiv 31 Jan 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT Rediscovers the Classical NLP Pipeline](https://mlsanity.com/paper/1905.05950/) (2019)
- [Dissecting Contextual Word Embeddings: Architecture and Representation](https://mlsanity.com/paper/1808.08949/) (2018)
- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [When Models Manipulate Manifolds: The Geometry of a Counting Task](https://mlsanity.com/paper/2601.04480/) (2026)
- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [A polar coordinate system represents syntax in large language models](https://mlsanity.com/paper/2412.05571/) (2024)
- [How Compositional Generalization and Creativity Improve as Diffusion Models are Trained](https://mlsanity.com/paper/2502.12089/) (2025)
- [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)
- [Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures](https://mlsanity.com/paper/2505.07070/) (2025)
- [Unraveling Syntax: Language Modeling and the Substructure of Grammars](https://mlsanity.com/paper/2510.02524/) (2025)
- [Sneaking Syntax into Transformer Language Models with Tree Regularization](https://mlsanity.com/paper/2411.18885/) (2024)

## Built on by (most cited first, 5 of 5)

- [Jailbreak Scaling Laws for Large Language Models: Polynomial-Exponential Crossover](https://mlsanity.com/paper/2603.11331/) (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)
- [A Solvable Theory of Pre-training Data Poisoning: Regime-Dependent Scaling Exponents](https://mlsanity.com/paper/2609.32288/) (2026)

## Abstract (arXiv)

Understanding how the structure of language can be learned from sentences alone is a central question in both cognitive science and machine learning. Studies of the internal representations of Large Language Models (LLMs) support their ability to parse text when predicting the next word, while representing semantic notions independently of surface form. Yet, which data statistics make these feats possible, and how much data is required, remain largely unknown. Probabilistic context-free grammars (PCFGs) provide a tractable testbed for studying these questions. However, prior work has focused either on the post-hoc characterization of the parsing-like algorithms used by trained networks; or on the learnability of PCFGs with fixed syntax, where parsing is unnecessary. Here, we (i) introduce a tunable class of PCFGs in which both the degree of ambiguity and the correlation structure across scales can be controlled; (ii) provide a learning mechanism -- an inference algorithm inspired by the structure of deep convolutional networks -- that links learnability and sample complexity to specific language statistics; and (iii) validate our predictions empirically across deep convolutional and transformer-based architectures. Overall, we propose a unifying framework where correlations at different scales lift local ambiguities, enabling the emergence of hierarchical representations of the data.