Physics of Language Models: Part 1, Learning Hierarchical Language Structures — part 1/7

Cleaned-text code points [0, 15939). Bibliography omitted here; source.md includes it.

# Physics of Language Models: Part 1, Learning Hierarchical Language Structures Thanks: The title Physics of Language Models was jointly conceived and designed by ZA and Xiaoli Xu. V1 appeared on this date; V2 polishes writing and adds Appendix G ; V3 polishes writing and changes the title; V4 improves writing and adds Appendix H (more uniform attention results, May 18, 2025). The first six papers in the Physics of Language Models series were presented as a two-hour tutorial at ICML 2024 in Austria ( youtu.be/yBL7J0kgldU ). A 100-min deep dive into Part 1 is available at youtu.be/kf_eGgVtOcs . Future updates and code release can be found on SSRN and the project page physics.allen-zhu.com . We would like to thank Lin Xiao, Sida Wang and Hu Xu for many helpful conversations. We would like to extend special thanks to Ian Clark, Gourab De, Anmol Mann, and Max Pfeifer from W&B , as well as Nabib Ahmed, Giri Anantharaman, Lucca Bertoncini, Henry Estela, Liao Hu, Caleb Ho, Will Johnson, Apostolos Kokolis, and Shubho Sengupta from Meta FAIR NextSys; without their invaluable support, the experiments in this paper would not have been possible.

###### Abstract

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 [ 1 ] ); 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.

## 1 Introduction

Transformer-based language models, like GPT [ 25 ] , are powerful but mysterious; many studies attempt to uncover the inner workings of transformers. Perhaps the simplest observation is that attention heads can pair closing brackets with open ones, see the concurrent work and the references therein [ 39 ] . Others also demonstrate that transformer can store key-value knowledge pairs by storing value in the hidden embedding of keys (see [ 3 ] and the references therein).

The seminal work from Anthropic [ 13 , 24 ] focuses on induction heads , which are logic operations on the input level (such as [A][B]…[A] implies the next token should be [B]). This can be used to interpret how language models perform sequence copying, translation, and some easy forms of pattern matching. They “hypothesized” that induction heads may exist to “match and copy more abstract and sophisticated linguistic features, rather than precise tokens”, yet they acknowledge that they “don’t have a strong framework for mechanistically understanding” this.

The interpretability in the wild paper [ 35 ] explored many different types of attention heads, including ‘‘copy head’’, ‘‘name mover head’’, ‘‘inhibition head’’, etc. Most notably, they explained how GPT2 predicts the next token ‘‘Mary’’ given prefix ‘‘When Mary and John went to the store, John gave a drink to [...]’’ This requires some logical reasoning by selecting (not naively copying) what is the right name. While this result is very inspiring, there exists very simple rule-based algorithm to achieve the same. 1 1 1 Yet, they also said “to the best of our knowledge, (this is) the most detailed attempt at reverse-engineering a natural end-to-end behavior in a transformer-based language model.” Our paper appeared six months after [ 35 ] .

In practice, transformers perform much more complex operations and reasoning, yet, achieving a mechanistic understanding of their internal workings remains a significant challenge. To gain such interpretability on how a transformer performs a certain task, it is often beneficial to have a well-defined algorithm for that task; the model’s internal representations and computations can then be compared against this algorithmic benchmark. However, many “impressive skills” of state-of-the-art language models are for tasks lacking such clear algorithmic solutions. Motivated by this, we ask: Is there a setting for us to understand how language models perform hard tasks, involving deep logics / reasoning / computation chains?

To isolate and rigorously study how models tackle tasks demanding deep reasoning over hierarchical structures, we employ a controlled setting using synthetic Context-Free Grammars (CFGs). CFGs, which include terminal (T) and nonterminal (NT) symbols, a root symbol, and production rules, inherently hierarchically produce highly-structured expressions. Crucially for our study, parsing such CFG-defined languages—a form of structured reasoning —often necessitates textbook-level, yet quite difficult, dynamic programming (DP)—a class of algorithms relevant to complex problem-solving. This CFG/DP paradigm provides a framework to probe for DP-like computational mechanisms when language models tackle these structured tasks. 2 2 2 Not to say in the theory community, CFGs are also used to model some rich, recursive structure in languages, including some logics, grammars, formats, expressions, patterns, etc. Generally, • We wish to capture how models reason over long-range dependencies via CFG. The simplest example is bracket matching, in ...Y(...)[[...]{...}]{...}X , the next symbol X could depend on Y that was hundreds of tokens before. Another example is coding, where goto N can only be used if N is a valid line number that could be hundreds of lines ago.

• We wish to capture how models reason through local ambiguity . A coding grammar (like python) can be parsed using greedy without ambiguity, so does bracket matching — once locally seen ...()... we know the two parentheses must be paired together. We focus on hard CFGs that require global planning via dynamic programming to parse.

Most popular choices of CFGs do not satisfy the two above properties. Notably, the English CFG (e.g., derived from Penn TreeBank) has an average length of 28 tokens (too short), and is not very locally ambiguous (e.g., RB JJ or JJ PP imply their parent must be ADJP ). As we show in Appendix G , such CFGs can even be learned using tiny GPT2 models with ∼ \sim 100k parameters. Thus, human languages may be too easy for our interpretability purpose .

For this reason, we design synthetic CFGs. We give one example in Figure 1 and discuss a family of 7 CFGs with varying difficulties in Section 2 (we have 15 more in the appendix). 3 3 3 A benefit of using synthetic data is to control the difficulty of the data, so that we can observe how transformers learn to solve tasks at different difficulty levels. We pre-train GPT-2 [ 28 ] , denoted by GPT, on a language modeling task using a corpus of strings sampled from such CFGs. We test the model’s accuracy and diversity by feeding it prefixes from the CFG (or no prefix, just the starting token) and observing if it can generate completions.

It is perhaps evident from Figure 1 that even if the CFG tree is given, deciding if a string satisfies it may require scratch paper and half an hour for a person, not to mention learning the CFG from scratch. However, we demonstrate that GPT can learn these CFGs, and using rotary or relative attention is crucial, especially for complex CFGs ( Results 1-3 ). More crucially, we examine attention patterns and hidden states to understand the reasoning mechanisms GPT employs to achieve this. Specifically,

• Results 4 - 5 . Develop a multi-head linear probing method to verify that the model’s hidden states linearly encode NT information almost perfectly, a significant finding as pre-training does not expose the CFG structure. (In contrast, encoder models like BERT do not.)

• Results 6- 9 . Introduce methods to visualize and quantify attention patterns, demonstrating that GPT learns position-based and boundary-based attentions, contributing to understanding how it performs hierarchical structure reasoning of CFG regularity and periodicity.

• Corollary. GPT models perform structure reasoning on CFGs by mimicking information flow characteristic of dynamic programming. Boundary-based attention allows a token to attend to its closest NT symbols in CFG tree, even when separated by hundreds of tokens. This resembles DP, in which parsing on a sequence 1 ​ … ​ i 1...i needs to be “concatenated” with another sequence i + 1 ​ … ​ j i+1...j to form a solution to a larger problem on 1 ​ … ​ j 1...j . See Figure 2 + 10 for illustrations.

We also explore implicit CFGs [ 26 ] , where each T symbol is a bag of tokens, and data is generated by randomly selecting tokens from these bags. Implicit CFGs capture additional structures, such as word categories. We demonstrate that GPT models learn implicit CFGs by encoding the T symbol information (i.e., token bags) directly into their token embedding layers ( Result 10 ).

We further examine model robustness [ 21 , 33 ] using CFGs, assessing the model’s ability to auto-correct errors and generate valid CFGs from a corrupted prefix (e.g., randomly flipping 15% of the symbols in the prefix). This capability is crucial as it reflects the model’s ability to process real-world data, including those containing grammatical errors. We find that:

• Result 11 . GPT models, trained on grammatically correct data, exhibit low robustness. However, introducing just a 10% perturbation to the training data significantly improves the model’s robustness. This suggests the benefit of using lower-quality data during pre-training.

• Result 12 - 13 . When trained with perturbed data, GPT models develop a “mode switch” for toggling between making or not making grammar mistakes. This behavior is observable in real-life completion models like Llama or GPT-3 (davinci003).

While previous works explored synthetic grammars and interpretability (e.g., [ 15 , 11 ] ), our contribution lies in isolating and quantifying dynamic programming-like computation in generative models via CFGs that require global parsing decisions — a regime where local heuristics fail.

## 2 Our Synthetic Context-Free Grammars

A probabilistic context-free grammar (CFG) is a formal system defining a string distribution using production rules. It comprises four components: terminal symbols ( 𝐓 \mathbf{T} ), nonterminal symbols ( 𝐍𝐓 \mathbf{NT} ), a root symbol ( r ​ o ​ o ​ t ∈ 𝐍𝐓 root\in\mathbf{NT} ), and production rules ( ℛ \mathcal{R} ). We represent a CFG as 𝒢 = ( 𝐓 , 𝐍𝐓 , ℛ ) \mathcal{G}=\left(\mathbf{T},\mathbf{NT},\mathcal{R}\right) , with L ⁡ ( 𝒢 ) L(\mathcal{G}) denoting the string distribution generated by 𝒢 \mathcal{G} .

### 2.1 Definition and Notations

We focus on L L -level CFGs where each level ℓ ∈ [ L ] \ell\in[L] corresponds to a set of symbols 𝐍𝐓 ℓ \mathbf{NT}_{\ell} with 𝐍𝐓 ℓ ⊆ 𝐍𝐓 \mathbf{NT}_{\ell}\subseteq\mathbf{NT} for ℓ < L \ell<L , 𝐍𝐓 L = 𝐓 \mathbf{NT}_{L}=\mathbf{T} , and 𝐍𝐓 1 = { r ​ o ​ o ​ t } \mathbf{NT}_{1}=\{root\} . Symbols at different levels are disjoint: 𝐍𝐓 i ∩ 𝐍𝐓 j = ∅ \mathbf{NT}_{i}\cap\mathbf{NT}_{j}=\varnothing for i ≠ j i\neq j . We consider rules of length 2 or 3, denoted as ℛ = ( ℛ 1 , … , ℛ L − 1 ) \mathcal{R}=(\mathcal{R}_{1},\dots,\mathcal{R}_{L-1}) , where each ℛ ℓ \mathcal{R}_{\ell} consists of rules in the form: r = ( a ↦ b , c , d ) or r = ( a ↦ b , c ) for a ∈ 𝐍𝐓 ℓ and b , c , d ∈ 𝐍𝐓 ℓ + 1 \displaystyle r=(a\mapsto b,c,d)\hskip 10.00002pt\text{or }\hskip 10.00002ptr=(a\mapsto b,c)\hskip 10.00002pt\text{for }\hskip 10.00002pta\in\mathbf{NT}_{\ell}\hskip 10.00002pt\text{and }\hskip 10.00002ptb,c,d\in\mathbf{NT}_{\ell+1} Given a non-terminal symbol a ∈ 𝐍𝐓 a\in\mathbf{NT} and any rule r = ( a ↦ ⋆ ) r=(a\mapsto\star) , we say a ∈ r a\in r . For each a ∈ 𝐍𝐓 a\in\mathbf{NT} , its associated set of rules is ℛ ⁡ ( a ) = def { r ∣ r ∈ ℛ ℓ ∧ a ∈ r } \mathcal{R}(a)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\big\{r\mid r\in\mathcal{R}_{\ell}\wedge a\in r\big\} , its degree is | ℛ ⁡ ( a ) | |\mathcal{R}(a)| , and the CFG’s size is ( | 𝐍𝐓 1 | , | 𝐍𝐓 2 | , … , | 𝐍𝐓 L | ) (|\mathbf{NT}_{1}|,|\mathbf{NT}_{2}|,\dots,|\mathbf{NT}_{L}|) .

Generating from CFG. To generate samples x x from L ⁡ ( 𝒢 ) L(\mathcal{G}) , follow these steps:

1. Start with the r ​ o ​ o ​ t root symbol 𝐍𝐓 1 \mathbf{NT}_{1} .

2. For each layer ℓ < L \ell<L , keep a sequence of symbols s ℓ = ( s ℓ , 1 , ⋯ , s ℓ , m ℓ ) s_{\ell}=\big(s_{\ell,1},\cdots,s_{\ell,m_{\ell}}\big) .

3. For the next layer, randomly sample a rule r ∈ ℛ ⁡ ( s ℓ , i ) r\in\mathcal{R}(s_{\ell,i}) for each s ℓ , i s_{\ell,i} with uniform probability. 4 4 4 For simplicity, we consider the uniform case, eliminating rules with extremely low probability. Such rules complicate the learning of the CFG and the investigation of a transformer’s inner workings (e.g., require larger networks and longer training time). Our results do extend to non-uniform cases when the distributions are not heavily unbalanced. Replace s ℓ , i s_{\ell,i} with b , c , d b,c,d if r = ( s ℓ , i ↦ b , c , d ) r=(s_{\ell,i}\mapsto b,c,d) , or with b , c b,c if r = ( s ℓ , i ↦ b , c ) r=(s_{\ell,i}\mapsto b,c) . Let the resulting sequence be s ℓ = ( s ℓ + 1 , 1 , ⋯ , s ℓ + 1 , m ℓ + 1 ) s_{\ell}=\big(s_{\ell+1,1},\cdots,s_{\ell+1,m_{\ell+1}}\big) .

4. During generation, when a rule s ℓ , i ↦ s ℓ + 1 , j , s ℓ + 1 , j + 1 s_{\ell,i}\mapsto s_{\ell+1,j},s_{\ell+1,j+1} is applied, define the parent 𝗉𝖺𝗋 ℓ + 1 ​ ( j ) = 𝗉𝖺𝗋 ℓ + 1 ​ ( j + 1 ) = def i \mathsf{par}_{\ell+1}(j)=\mathsf{par}_{\ell+1}(j+1)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}i (and similarly if the rule of s ℓ , i s_{\ell,i} is of length 3).

5. Define NT ancestor indices 𝔭 = ( 𝔭 1 ​ ( i ) , … , 𝔭 L ​ ( i ) ) i ∈ [ m L ] \mathfrak{p}=(\mathfrak{p}_{1}(i),\dots,\mathfrak{p}_{L}(i))_{i\in[m_{L}]} and NT ancestor symbols 𝔰 = ( 𝔰 1 ​ ( i ) , … , 𝔰 L ​ ( i ) ) i ∈ [ m L ] \mathfrak{s}=(\mathfrak{s}_{1}(i),\dots,\mathfrak{s}_{L}(i))_{i\in[m_{L}]} as shown in Figure 2 : 𝔭 L ( j ) = def j , 𝔭 ℓ ( j ) = def 𝗉𝖺𝗋 ℓ + 1 ( 𝔭 ℓ + 1 ( j ) ) and 𝔰 ℓ ( j ) = def s ℓ , 𝔭 ℓ ​ ( j ) \mathfrak{p}_{L}(j)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}j\kern 5.0pt,\hskip 10.00002pt\mathfrak{p}_{\ell}(j)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\mathsf{par}_{\ell+1}(\mathfrak{p}_{\ell+1}(j))\hskip 10.00002pt\text{and }\hskip 10.00002pt\mathfrak{s}_{\ell}(j)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}s_{\ell,\mathfrak{p}_{\ell}(j)}

The final string is x = s L = ( s L , 1 , ⋯ , s L , m L ) x=s_{L}=(s_{L,1},\cdots,s_{L,m_{L}}) with x i = s L , i x_{i}=s_{L,i} and length len ​ ( x ) = m L \textbf{len}(x)=m_{L} . We use ( x , 𝔭 , 𝔰 ) ∼ L ⁡ ( 𝒢 ) (x,\mathfrak{p},\mathfrak{s})\sim L(\mathcal{G}) to represent x x with its associated NT ancestor indices and symbols, sampled according to the generation process. We write x ∼ L ⁡ ( 𝒢 ) x\sim L(\mathcal{G}) when 𝔭 \mathfrak{p} and 𝔰 \mathfrak{s} are evident from the context.

###### Definition 2.1 .