# Physics of Language Models: Part 1, Learning Hierarchical Language Structures

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

## Key facts

- Cited by 83 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 46 references that are in the map.
- First posted on arXiv 23 May 2023.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small](https://mlsanity.com/paper/2211.00593/) (2022)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [GPT-NeoX-20B: An Open-Source Autoregressive Language Model](https://mlsanity.com/paper/2204.06745/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [An Empirical Study on Robustness to Spurious Correlations using Pre-trained Language Models](https://mlsanity.com/paper/2007.06778/) (2020)
- [Perturbed Masking: Parameter-free Probing for Analyzing and Interpreting BERT](https://mlsanity.com/paper/2004.14786/) (2020)
- [Evaluating the Robustness of Neural Language Models to Input Perturbations](https://mlsanity.com/paper/2108.12237/) (2021)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [Characterizing Intrinsic Compositionality in Transformers with Tree Projections](https://mlsanity.com/paper/2211.01288/) (2022)
- [Do Syntactic Probes Probe Syntax? Experiments with Jabberwocky Probing](https://mlsanity.com/paper/2106.02559/) (2021)
- [Do GANs actually learn the distribution? An empirical study](https://mlsanity.com/paper/1706.08224/) (2017)
- [Parsing as Pretraining](https://mlsanity.com/paper/2002.01685/) (2020)
- [Learning Hierarchical Structures with Differentiable Nondeterministic Stacks](https://mlsanity.com/paper/2109.01982/) (2021)
- [Probing for Constituency Structure in Neural Language Models](https://mlsanity.com/paper/2204.06201/) (2022)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)

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

- [Physics of Language Models: Part 3.1, Knowledge Storage and Extraction](https://mlsanity.com/paper/2309.14316/) (2023)
- [Physics of Language Models: Part 3.3, Knowledge Capacity Scaling Laws](https://mlsanity.com/paper/2404.05405/) (2024)
- [Physics of Language Models: Part 3.2, Knowledge Manipulation](https://mlsanity.com/paper/2309.14402/) (2023)
- [Mechanistically analyzing the effects of fine-tuning on procedurally defined tasks](https://mlsanity.com/paper/2311.12786/) (2023)
- [Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process](https://mlsanity.com/paper/2407.20311/) (2024)
- [Projecting Assumptions: The Duality Between Sparse Autoencoders and Concept Geometry](https://mlsanity.com/paper/2503.01822/) (2025)
- [What Makes and Breaks Safety Fine-tuning? A Mechanistic Study](https://mlsanity.com/paper/2407.10264/) (2024)
- [How Linguistics Learned to Stop Worrying and Love the Language Models](https://mlsanity.com/paper/2501.17047/) (2025)
- [Physics of Language Models: Part 2.2, How to Learn From Mistakes on Grade-School Math Problems](https://mlsanity.com/paper/2408.16293/) (2024)
- [ICLR: In-Context Learning of Representations](https://mlsanity.com/paper/2501.00070/) (2024)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles](https://mlsanity.com/paper/2409.10502/) (2024)
- [Physics of Language Models: Part 4.1, Architecture Design and the Magic of Canon Layers](https://mlsanity.com/paper/2512.17351/) (2025)
- [How Is LLM Reasoning Distracted by Irrelevant Context? An Analysis Using a Controlled Benchmark](https://mlsanity.com/paper/2505.18761/) (2025)
- [Locate, Steer, and Improve: A Practical Survey of Actionable Mechanistic Interpretability in Large Language Models](https://mlsanity.com/paper/2601.14004/) (2026)
- [A Percolation Model of Emergence: Analyzing Transformers Trained on a Formal Language](https://mlsanity.com/paper/2408.12578/) (2024)
- [Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling](https://mlsanity.com/paper/2402.00522/) (2024)
- [Learning Syntax Without Planting Trees: Understanding Hierarchical Generalization in Transformers](https://mlsanity.com/paper/2404.16367/) (2024)
- [Language Models as Models of Language](https://mlsanity.com/paper/2408.07144/) (2024)
- [Deriving Neural Scaling Laws from the statistics of natural language](https://mlsanity.com/paper/2602.07488/) (2026)
- [ModernVBERT: Towards Smaller Visual Document Retrievers](https://mlsanity.com/paper/2510.01149/) (2025)
- [Analyzing (In)Abilities of SAEs via Formal Languages](https://mlsanity.com/paper/2410.11767/) (2024)
- [Learning curves theory for hierarchically compositional data with power-law distributed features](https://mlsanity.com/paper/2505.07067/) (2025)
- [Progressive distillation induces an implicit curriculum](https://mlsanity.com/paper/2410.05464/) (2024)
- [Mechanistic Interpretability as Statistical Estimation: A Variance Analysis](https://mlsanity.com/paper/2510.00845/) (2025)
- [Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations](https://mlsanity.com/paper/2511.05295/) (2025)
- [The Dead Salmons of AI Interpretability](https://mlsanity.com/paper/2512.18792/) (2025)
- [On the Role of Depth and Looping for In-Context Learning with Task Diversity](https://mlsanity.com/paper/2410.21698/) (2024)
- [The Strawberry Problem: Emergence of Character-level Understanding in Tokenized Language Models](https://mlsanity.com/paper/2505.14172/) (2025)
- [Mechanistic evaluation of Transformers and state space models](https://mlsanity.com/paper/2505.15105/) (2025)

## Abstract (arXiv)

Transformer-based language models are effective but complex, and understanding their inner workings and reasoning mechanisms is a significant challenge. Previous research has primarily explored how these models handle simple tasks like name copying or selection, and we extend this by investigating how these models perform recursive language structure reasoning defined by context-free grammars (CFGs). We introduce a family of synthetic CFGs that produce hierarchical rules, capable of generating lengthy sentences (e.g., hundreds of tokens) that are locally ambiguous and require dynamic programming to parse. Despite this complexity, we demonstrate that generative models like GPT can accurately learn and reason over CFG-defined hierarchies and generate sentences based on it. We explore the model's internals, revealing that its hidden states precisely capture the structure of CFGs, and its attention patterns resemble the information passing in a dynamic programming algorithm. This paper also presents several corollaries, including showing why absolute positional embeddings is inferior to relative and rotary embeddings; uniform attention alone is surprisingly effective (motivating our follow-up work on Canon layers); encoder-only models (e.g., BERT, DeBERTa) struggle with deep structure reasoning on CFGs compared to autoregressive models (e.g., GPT); and injecting structural or syntactic noise into pretraining data markedly improves robustness to corrupted language prompts.