# 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 .

A symbol x i x_{i} in a sample ( x , 𝔭 , 𝔰 ) ∼ L ⁡ ( 𝒢 ) (x,\mathfrak{p},\mathfrak{s})\sim L(\mathcal{G}) is the NT boundary / NT end at level ℓ ∈ [ L − 1 ] \ell\in[L-1] if 𝔭 ℓ ​ ( i ) ≠ 𝔭 ℓ ​ ( i + 1 ) \mathfrak{p}_{\ell}(i)\not=\mathfrak{p}_{\ell}(i+1) or i = len ​ ( x ) i=\textbf{len}(x) . We denote 𝔟 ℓ ​ ( i ) = def 𝟙 x i ​ is the NT boundary at level ​ ℓ \mathfrak{b}_{\ell}(i)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\mathds{1}_{x_{i}\text{ is the NT boundary at level }\ell} as the NT-end boundary indicator function. The deepest NT-end of i i is— see also Figure 2 — 𝔟 ♯ ( i ) = min ℓ ∈ { 2 , 3 , … , L − 1 } { 𝔟 ℓ ( i ) = 1 } or ⊥ if set is empty . \textstyle\mathfrak{b}^{\sharp}(i)=\min_{\ell\in\{2,3,\dots,L-1\}}\{\mathfrak{b}_{\ell}(i)=1\}\hskip 10.00002pt\text{or $\bot$ if set is empty }\kern 5.0pt.

The 𝖼𝖿𝗀𝟥 \mathsf{cfg3} synthetic CFG family. We focus on seven synthetic CFGs of depth L = 7 L=7 detailed in Section A.1 . The hard datasets 𝖼𝖿𝗀𝟥𝖻 , 𝖼𝖿𝗀𝟥𝗂 , 𝖼𝖿𝗀𝟥𝗁 , 𝖼𝖿𝗀𝟥𝗀 , 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3b},\mathsf{cfg3i},\mathsf{cfg3h},\mathsf{cfg3g},\mathsf{cfg3f} have sizes ( 1 , 3 , 3 , 3 , 3 , 3 , 3 ) (1,3,3,3,3,3,3) and increasing difficulties 𝖼𝖿𝗀𝟥𝖻 < 𝖼𝖿𝗀𝟥𝗂 < 𝖼𝖿𝗀𝟥𝗁 < 𝖼𝖿𝗀𝟥𝗀 < 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3b}<\mathsf{cfg3i}<\mathsf{cfg3h}<\mathsf{cfg3g}<\mathsf{cfg3f} . The easy datasets 𝖼𝖿𝗀𝟥𝖾𝟣 \mathsf{cfg3e1} and 𝖼𝖿𝗀𝟥𝖾𝟤 \mathsf{cfg3e2} have sizes ( 1 , 3 , 9 , 27 , 81 , 27 , 9 ) (1,3,9,27,81,27,9) and ( 1 , 3 , 9 , 27 , 27 , 9 , 4 ) (1,3,9,27,27,9,4) respectively. The sequences generated by these CFGs are up to 3 6 = 729 3^{6}=729 in length. Typically, the learning difficulty of CFGs inversely scales with the number of NT/T symbols, assuming other factors remain constant, because having more NT/T symbols makes the language less ambiguous and more easily parsed using greedy (see Figure 4 and we discuss more in Appendix G ). We thus primarily focus on 𝖼𝖿𝗀𝟥𝖻 , 𝖼𝖿𝗀𝟥𝗂 , 𝖼𝖿𝗀𝟥𝗁 , 𝖼𝖿𝗀𝟥𝗀 , 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3b},\mathsf{cfg3i},\mathsf{cfg3h},\mathsf{cfg3g},\mathsf{cfg3f} .

### 2.2 Why Such CFGs

We use CFG as a proxy to study rich, recursive structure reasoning in languages—from logics and grammars to formats and patterns. Those structures are diverse yet strict (e.g., in a CFG describing chapter numbers, Chapter 3.1 can be only followed by Chapter 3.1.1, Chapter 4 or Chapter 3.2, not others). The CFGs we consider are non-trivial, with over 2 270 > 10 80 2^{270}>10^{80} strings in 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} among a total of over 3 300 > 10 140 3^{300}>10^{140} possible strings of length 300 or more (see our entropy estimation later in Figure 4 ). The probability of a random string belonging to this language is nearly zero, and a random completion of a valid prefix is unlikely to satisfy the CFG. In particular, Figure 31 in the appendix shows that 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} cannot be learned by transformers (much) smaller than GPT2-small. In contrast, the English CFG (e.g., derived from Penn TreeBank) can be learned to good accuracy using tiny GPT2 models with ∼ \sim 100k parameters — so it is too easy for our interpretability purpose.

To obtain clean interpretability result and facilitate clearer analysis of learned representations across processing levels, we selected a CFG family with a’canonical representation’ (e.g., layered CFG). This layered structure, while simplified, allows for direct probing of per-level NT symbol encodings and attention patterns at distinct hierarchical depths, aiding our interpretability goals. This controlled design allows us to demonstrate a strong correlation between the CFG representation and the hidden states in the learned transformer. We also create additional CFG families to examine “not-so-canonical” CFG trees, with results deferred to Appendix G (see an example in Figure 3 ). We do not claim our results encompass all CFGs; our chosen CFGs are already challenging for a transformer to learn and can lead to clean hierarchical interpretability results.

## 3 Results 1-3: Transformer Can Learn Such CFGs

Before we analyze how transformers perform structure reasoning on such CFGs, we have to first verify that they at least can learn such CFGs. In this section, we generate a large corpus { x ( i ) } i ∈ [ N ] \{x^{(i)}\}_{i\in[N]} from a synthetic CFG language L ⁡ ( 𝒢 ) L(\mathcal{G}) in Section 2.1 , and pretrain a (decoder-only) transformer model F F on this corpus, treating each terminal symbol as a separate token, using an auto-regressive task (see Appendix A.3 for details). We then evaluate how well the model learns such L ⁡ ( 𝒢 ) L(\mathcal{G}) .

Models. We denote the GPT2 small architecture (12-layer, 12-head, 768-dimensions) as 𝙶𝙿𝚃 \mathtt{GPT} [ 28 ] and implemented its two modern variants. We denote 𝙶𝙿𝚃 \mathtt{GPT} with relative positional attention [ 14 ] as 𝙶𝙿𝚃 𝗋𝖾𝗅 \mathtt{GPT}_{\mathsf{rel}} , and 𝙶𝙿𝚃 \mathtt{GPT} with rotary attention [ 32 , 10 ] as 𝙶𝙿𝚃 𝗋𝗈𝗍 \mathtt{GPT}_{\mathsf{rot}} . For purposes in later sections, we introduce two weaker variants. 𝙶𝙿𝚃 𝗉𝗈𝗌 \mathtt{GPT}_{\mathsf{pos}} replaces the attention matrix with a matrix based solely on tokens’ relative positions, while 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} uses a constant, uniform average of past tokens from various window lengths as the attention matrix. Detailed explanations of these variants are in Section A.2 .

We quickly summarize our findings and then elaborate them in details. Result 1-3 ( Figure 4 ) . The GPT models (except the original absolute embedding variant) can effectively learn our synthetic CFGs. Given any prefix, they can generate completion strings • that can perfectly adhere to the CFG rules most of the time, (accuracy) • that are sufficiently diverse in the CFG language, and (diversity) • that closely follow the probabilistic distribution of the CFG language. (probability) Moreover, one had better use rotary or relative attentions; the original 𝙶𝙿𝚃 \mathtt{GPT} (with absolute positional embedding) performs even worse than 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} (with uniform attention).

Result 1: Completion accuracy. We evaluate F F by letting it generate completions for prefixes x : c = ( x 1 , x 2 , ⋯ , x c ) x_{:c}=(x_{1},x_{2},\cdots,x_{c}) from strings x x freshly sampled from L ⁡ ( 𝒢 ) L(\mathcal{G}) . The generation accuracy is measured as 𝐏𝐫 x ∼ L ⁡ ( G ) + randomness of F [ ( x : c , F ( x : c ) ) ∈ L ( 𝒢 ) ] \operatornamewithlimits{\mathbf{Pr}}_{x\sim L(G)\,+\,\textrm{randomness of $F$}}[(x_{:c},F(x_{:c}))\in L(\mathcal{G})] . We use multinomial sampling without beam search for generation. 5 5 5 The last softmax layer converts the model outputs into a probability distribution over (next) symbols. We follow this distribution to generate the next symbol, reflecting the unaltered distribution learned by the transformer. This is the source of the “randomness of F F ” and is often referred to as using “temperature τ = 1 \tau=1 .”

Figure 4 (left) shows the generation accuracies for cuts c = 0 c=0 and c = 50 c=50 . The c = 0 c=0 result tests the model’s ability to generate a sentence in the CFG, while c = 50 c=50 tests that to complete a sentence. 6 6 6 𝖼𝖿𝗀𝟥 \mathsf{cfg3} family is large enough to ensure a negligible chance of a freshly sampled prefix of length 50 being seen during pretraining. The results show that the pretrained GPT models can often generate strings that perfectly adhere to the CFG rules for the 𝖼𝖿𝗀𝟥 \mathsf{cfg3} data family.

Result 2: Generation diversity. Could it be possible that the pretrained GPT models only memorized a small subset of strings from the CFG? We evaluate this by measuring the diversity of its generated strings. High diversity suggests a better understanding of the CFG rules.

We consider two methods to estimate diversity. One is to estimate the distribution’s entropy, which provides a rough estimate of (the log 2 \log_{2} of) the support size, see the middle of Figure 4 . The other is to use birthday paradox to theoretically lower bound the support size [ 7 ] . This allows us to make precise claims, such as in the 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} dataset, there are at least 4 × 10 8 4\times 10^{8} distinct sentential forms derivable from a symbol at levels 1 to 5 or levels 2 to 6; not to say from the root to level 7. Details are in Appendix B . Our general conclusion is that the pre-trained model does not rely on simply memorizing a small set of patterns to achieve high completion accuracy.

Result 3: Distribution comparison. To fully learn a CFG, it is crucial to also learn the probabilistic distribution. One naive approach is to compare the marginal distributions p ⁡ ( a , i ) p(a,i) , for the probability of symbol a ∈ 𝐍𝐓 ℓ a\in\mathbf{NT}_{\ell} appearing at position i i . We observe a strong alignment between the generation probabilities and the ground-truth, included in Appendix B.2 .

Another approach is to use the standard KL-divergence formula to compare the next-token prediction probability (as predicted by the transformer model) and the ground-truth. Let p ∗ p^{*} denote the distribution over strings in the true CFG and p p that from the transformer model. Let S = { x ( i ) } i ∈ [ M ] S=\big\{x^{(i)}\big\}_{i\in[M]} be samples from the true CFG distribution. Then, the KL-divergence can be estimated as follows: 7 7 7 Similar formula was also used in [ 12 ] . 1 | S | ∑ x ∈ S 1 len ​ ( x ) + 1 ∑ i ∈ [ len ​ ( x ) + 1 ] ∑ t ∈ 𝐓 ∪ { 𝖾𝗈𝗌 } 𝐏𝐫 p ∗ [ t ∣ x 1 , … , x i − 1 ] log 𝐏𝐫 p ∗ [ t ∣ x 1 , … , x i − 1 ] 𝐏𝐫 p [ t ∣ x 1 , … , x i − 1 ] \textstyle\frac{1}{|S|}\sum_{x\in S}\frac{1}{\textbf{len}(x)+1}\sum_{i\in[\textbf{len}(x)+1]}\sum_{t\in\mathbf{T}\cup\{\mathsf{eos}\}}\operatornamewithlimits{\mathbf{Pr}}_{p^{*}}[t\mid x_{1},\dots,x_{i-1}]\log\frac{\operatornamewithlimits{\mathbf{Pr}}_{p^{*}}[t\mid x_{1},\dots,x_{i-1}]}{\operatornamewithlimits{\mathbf{Pr}}_{p}[t\mid x_{1},\dots,x_{i-1}]} (Above, 𝐏𝐫 p [ t ∣ x 1 , … , x i − 1 ] \operatornamewithlimits{\mathbf{Pr}}_{p}[t\mid x_{1},\dots,x_{i-1}] is the next-token distribution predicted by the model, and 𝐏𝐫 p ∗ [ t ∣ x 1 , … , x i − 1 ] \operatornamewithlimits{\mathbf{Pr}}_{p^{*}}[t\mid x_{1},\dots,x_{i-1}] is that from the ground-truth. 8 8 8 There are many dynamic programming methods to compute 𝐏𝐫 p ∗ [ t ∣ x 1 , … , x i − 1 ] \operatornamewithlimits{\mathbf{Pr}}_{p^{*}}[t\mid x_{1},\dots,x_{i-1}] exactly; which one to use is irrelevant. ) In Figure 4 (right) we compute such KL-divergence using M = 20000 M=20000 samples.

Connection to DP. Result 1-3 (e.g., learning the CFG’s next-token distribution) is merely a small step towards showing that the model employs a DP-like approach. Dynamic programming (e.g., the inside-outside algorithm [ 9 ] ) can compute next-token distributions of CFGs, and such algorithms can be implemented using nonlinear neural networks like transformers, achieving a global minimum in the auto-regressive training objective. 9 9 9 This has been carefully explored for masked language modeling case in Zhao et al. [40] . However, the mere existence of a dynamic-programming transformer to obtain the training objective’s global minimum is not satisfactory. Does employing an AdamW stochastic optimizer for 100k iterations on the training objective yield such an algorithm? The remainder of this paper will delve deeper to address this question.

Other Applications of Results 1–3. While not the focus of this paper, our constructed CFGs also serve as a quick testbed for comparing architecture designs. For instance, the strong performance of uniform attention aligns with the effectiveness of ALiBi [ 27 ] and H-Alibi [ 16 ] , and has motivated our follow-up work on designing Transformer architectures that explicitly leverage short-window uniform attention [ 1 ] . Additional robustness experiments for uniform attention—across data complexities and model sizes—are included in Appendix H .

## 4 Results 4-5: How Do Transformers Learn CFGs?

In this section, we delve into the learned representation of the transformer to understand how it encodes CFGs. We employ various measurements to probe the representation and gain insights.

Recall classical way to solve CFGs. Given CFG 𝒢 \mathcal{G} , the classical way to reason about if a sequence x x satisfies L ⁡ ( 𝒢 ) L(\mathcal{G}) is to use dynamic programming (DP) [ 29 , 31 ] . One possible implementation of DP involves using the function 𝖣𝖯 ⁡ ( i , j , a ) \mathsf{DP}(i,j,a) , which determines whether or not x i + 1 , x i + 1 ​ … , x j x_{i+1},x_{i+1}\dots,x_{j} can be generated from symbol a a following the CFG rules. From this DP representation, a DP recurrent formula can be easily derived. 10 10 10 For example, one can compute 𝖣𝖯 ⁡ ( i , j , a ) = 1 \mathsf{DP}(i,j,a)=1 if and only if there exists i = i 1 < i 2 < ⋯ < i k = j i=i_{1}<i_{2}<\cdots<i_{k}=j such that 𝖣𝖯 ⁡ ( i r , i r + 1 , b r ) = 1 \mathsf{DP}(i_{r},i_{r+1},b_{r})=1 for all r ∈ [ k − 1 ] r\in[k-1] and a → b 1 , b 2 , … , b k a\to b_{1},b_{2},\dots,b_{k} is a rule of the CFG. Implementing this naively would result in a O ⁡ ( len 4 ) O(\textbf{len}^{4}) algorithm for CFGs with a maximum rule length of 3 3 . However, it can be implemented more efficiently with O ⁡ ( len 3 ) O(\textbf{len}^{3}) time by introducing auxiliary nodes (e.g., via binarization). In the context of this paper, any sequence x ∼ L ⁡ ( 𝒢 ) x\sim L(\mathcal{G}) that satisfies the CFG must satisfy the following conditions: 𝔟 ℓ ​ ( i ) = 1 , 𝔟 ℓ ​ ( j ) = 1 , ∀ k ∈ ( i , j ) , 𝔟 ℓ ​ ( k ) = 0 ​ and ​ 𝔰 ℓ ​ ( j ) = a ⟹ 𝖣𝖯 ⁡ ( i , j , a ) = 1 \mathfrak{b}_{\ell}(i)=1,\mathfrak{b}_{\ell}(j)=1,\forall k\in(i,j),\mathfrak{b}_{\ell}(k)=0\text{ and }\mathfrak{s}_{\ell}(j)=a\implies\mathsf{DP}(i,j,a)=1 (4.1) (recall the NT-boundary 𝔟 ℓ \mathfrak{b}_{\ell} and the NT-ancestor 𝔰 ℓ \mathfrak{s}_{\ell} notions from Section 2.1 ). Note that ( 4.1 ) is not an “if and only if” condition because there may be a subproblem 𝖣𝖯 ⁡ ( i , j , a ) = 1 \mathsf{DP}(i,j,a)=1 that does not lie on the final CFG parsing tree but is still locally parsable by some valid CFG subtree. However, ( 4.1 ) provides a “backbone” of subproblems, where verifying all 𝖣𝖯 ⁡ ( i , j , a ) = 1 \mathsf{DP}(i,j,a)=1 values in this backbone certifies that the sentence x x is a valid string from L ⁡ ( 𝒢 ) L(\mathcal{G}) . It is worth mentioning that there are exponentially many implementations of the same DP algorithm 11 11 11 Each inner loop of the dynamic programming can proceed in any arbitrary order, not limited to k = i . . j k=i..j or k = j . . i k=j..i , and the algorithm can prune and break early. This gives a safe estimate of at least ( n ! ) Ω ⁡ ( n 2 ) (n!)^{\Omega(n^{2})} possible implementations. Furthermore, there are at least 2 Ω ⁡ ( n ) 2^{\Omega(n)} ways to perform binarization, meaning to break length-3 rules to length-2 ones. This is just to detect if a given string of length n n belongs to the CFG. and not all ( i , j , a ) (i,j,a) tuples need to be computed in 𝖣𝖯 ⁡ ( i , j , a ) \mathsf{DP}(i,j,a) . Only those in the “backbone” are necessary.

Connecting to transformer. In this section, we investigate whether pre-trained transformer F F also implicitly encodes the NT ancestor and boundary information, which forms the basis for its structure reasoning capabilities. If so, it suggests the model contains sufficient information to support all the 𝖣𝖯 ⁡ ( i , j , a ) \mathsf{DP}(i,j,a) values in the backbone. This is a significant finding, considering that transformer F F is trained solely on the auto-regressive task without any exposure to NT information. If the model encodes NT ancestor and boundary information after pretraining (as demonstrated in Results 4-5), this means it internally possesses the structural knowledge necessary not only for generation but also to certify the grammatical correctness of sentences according to the CFG. That is, its internal states effectively represent the parse tree.

### 4.1 Result 4: Transformer’s Last Layer Encodes NT Ancestors/Boundaries

Let l l be the last layer of the transformer (other layers are studied in Appendix C.2 ). Given an input string x x , we denote the hidden state of the transformer at layer l l and position i i as E i ​ ( x ) ∈ ℝ d E_{i}(x)\in\mathbb{R}^{d} . We first investigate whether a linear function can predict ( 𝔟 1 ​ ( i ) , … , 𝔟 L ​ ( i ) ) i ∈ [ len ​ ( x ) ] \big(\mathfrak{b}_{1}(i),\dots,\mathfrak{b}_{L}(i)\big)_{i\in[\textbf{len}(x)]} and ( 𝔰 1 ​ ( i ) , … , 𝔰 L ​ ( i ) ) i ∈ [ len ​ ( x ) ] \big(\mathfrak{s}_{1}(i),\dots,\mathfrak{s}_{L}(i)\big)_{i\in[\textbf{len}(x)]} using the full ( E i ​ ( x ) ) i ∈ [ len ​ ( x ) ] \big(E_{i}(x)\big)_{i\in[\textbf{len}(x)]} . If so, it implies that the last-layer hidden states encode the CFG’s structural information up to a linear transformation .

Multi-head linear probing (full). Due to the high dimensionality of this linear function (e.g., len ​ ( x ) = 300 \textbf{len}(x)=300 and d = 768 d=768 yield 300 × 768 300\times 768 dimensions) and variable string lengths , we propose a multi-head linear function for efficient learning. We consider a set of linear functions f r : ℝ d → ℝ | 𝐍𝐓 | f_{r}\colon\mathbb{R}^{d}\to\mathbb{R}^{|\mathbf{NT}|} , where r ∈ [ H ] r\in[H] and H H is the number of “heads”. To predict any 𝔰 ℓ ​ ( i ) \mathfrak{s}_{\ell}(i) , we apply: G i ​ ( x ) = ∑ r ∈ [ H ] , k ∈ [ len ​ ( x ) ] w r , i → k ⋅ f r ​ ( E k ​ ( x ) ) ∈ ℝ | 𝐍𝐓 | \displaystyle\textstyle G_{i}(x)=\sum_{r\in[H],k\in[\textbf{len}(x)]}w_{r,i\to k}\cdot f_{r}(E_{k}(x))\in\mathbb{R}^{|\mathbf{NT}|} (4.2) where w r , i → k = def exp ⁡ ( ⟨ P i , r , P k , r ⟩ ) ∑ k ′ ∈ [ len ​ ( x ) ] exp ⁡ ( ⟨ P i , r , P k ′ , r ⟩ ) w_{r,i\to k}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\frac{\exp(\langle P_{i,r},P_{k,r}\rangle)}{\sum_{k^{\prime}\in[\textbf{len}(x)]}\exp(\langle P_{i,r},P_{k^{\prime},r}\rangle)} for trainable parameters P i , r ∈ ℝ d ′ P_{i,r}\in\mathbb{R}^{d^{\prime}} . G i G_{i} can be seen as a “multi-head attention” over linear functions. We train G i ​ ( x ) ∈ ℝ | 𝐍𝐓 | G_{i}(x)\in\mathbb{R}^{|\mathbf{NT}|} using the cross-entropy loss to predict ( 𝔰 ℓ ​ ( i ) ) ℓ ∈ [ L ] \big(\mathfrak{s}_{\ell}(i)\big)_{\ell\in[L]} . Despite having multiple heads, G i ​ ( x ) G_{i}(x) is still a linear function over ( E k ​ ( x ) ) k ∈ [ len ​ ( x ) ] (E_{k}(x))_{k\in[\textbf{len}(x)]} as the linear weights w r , i → k w_{r,i\to k} depend only on positions i i and k k , not on x x . Similarly, we train G i ′ ​ ( x ) ∈ ℝ L G^{\prime}_{i}(x)\in\mathbb{R}^{L} using the logistic loss to predict the binary values ( 𝔟 ℓ ​ ( i ) ) ℓ ∈ [ L ] \big(\mathfrak{b}_{\ell}(i)\big)_{\ell\in[L]} . Details are in Section A.4 .

Using such multi-head linear probing, we discover that:

Result 4 ( Figure 5 ) . Pre-training allows GPT models to almost perfectly encode the NT ancestor 𝔰 ℓ ​ ( i ) \mathfrak{s}_{\ell}(i) and NT boundary 𝔟 ℓ ​ ( i ) \mathfrak{b}_{\ell}(i) information in the last transformer layer’s hidden states ( E k ​ ( x ) ) k ∈ [ len ​ ( x ) ] (E_{k}(x))_{k\in[\textbf{len}(x)]} , up to a linear transformation. (See Figure 5 for comparison against randomly-initialized 𝙶𝙿𝚃 𝗋𝖺𝗇𝖽 \mathtt{GPT}_{\mathsf{rand}} or encoder model 𝚍𝚎𝙱𝙴𝚁𝚃𝚊 \mathtt{deBERTa} , which fail to recover deep NT structure.) 11 11 footnotetext: 𝚍𝚎𝙱𝙴𝚁𝚃𝚊 \mathtt{deBERTa} is a modern variant of BERT, equipped with relative attentions. It is expected that encoder models may not learn deep NT information, because in a masked-language modeling (MLM) task, the model only needs to figure out the missing token from its surrounding, say, 20 tokens. This can be done by pattern matching, as opposed to global planning like dynamic programming. But, do we need this full layer for linear probing? We explore next.

### 4.2 Result 5: NT Ancestors are Encoded At NT Boundaries

In Result 4, we used the full hidden layer, ( E i ​ ( x ) ) i ∈ [ len ​ ( x ) ] \big(E_{i}(x)\big)_{i\in[\textbf{len}(x)]} , to predict ( 𝔰 ℓ ​ ( i ) ) ℓ ∈ [ L ] \big(\mathfrak{s}_{\ell}(i)\big)_{\ell\in[L]} for each position i i . This is essential since it’s information-theoretically impossible to extract all of i i ’s NT ancestors by only reading E i ​ ( x ) E_{i}(x) or even all hidden states to its left , especially if x i x_{i} is the start of a string or a subtree in the CFG. But, how about those ones information-theoretically possible? In particular, how about predicting 𝔰 ℓ ​ ( i ) \mathfrak{s}_{\ell}(i) at locations i i with 𝔟 ℓ ​ ( i ) = 1 \mathfrak{b}_{\ell}(i)=1 — i.e., at the end of the CFG subtrees.

Multi-head linear probing (diagonal). We consider a neighborhood of position i i in the hidden states, say E i ± 1 ​ ( x ) E_{i\pm 1}(x) , and use that for linear probing. In symbols, we replace w r , i → k w_{r,i\to k} in ( 4.2 ) with zeros for | i − k | > 1 |i-k|>1 (tridiagonal masking), or with zeros for i ≠ k i\neq k (diagonal masking). G i ​ ( x ) = ∑ r ∈ [ H ] , k ∈ [ len ​ ( x ) ] , | i − k | ≤ δ w r , i → k ⋅ f r ​ ( E k ​ ( x ) ) ∈ ℝ | 𝐍𝐓 | where δ = 0 or 1 \displaystyle\textstyle G_{i}(x)=\sum_{r\in[H],k\in[\textbf{len}(x)],|i-k|\leq\delta}w_{r,i\to k}\cdot f_{r}(E_{k}(x))\in\mathbb{R}^{|\mathbf{NT}|}\hskip 20.00003pt\text{where $\delta=0$ or $1$ } (4.3)

Result 5 ( Figure 6 + 7 ) . For GPT models, the information of position i i ’s NT ancestor/boundary is locally encoded around position i ± 1 i\pm 1 when i i is on the NT boundary. This is because: • At NT boundaries (i.e., 𝔟 ℓ ​ ( x ) = 1 \mathfrak{b}_{\ell}(x)=1 ), we discover that diagonal or tridiagonal multi-head linear probing ( 4.3 ) is adequate for accurately predicting the NT ancestors 𝔰 ℓ ​ ( x ) \mathfrak{s}_{\ell}(x) (see Figure 7 ). • Such masking is also sufficient for accurately predicting NT boundaries 𝔟 ℓ ​ ( i ) \mathfrak{b}_{\ell}(i) (deferred to Figure 19 in Appendix C.1 ). In contrast, encoder models like 𝚍𝚎𝙱𝙴𝚁𝚃𝚊 \mathtt{deBERTa} do not store deep NT information at the NT boundaries.

Related work. Linear probing at least traces back to Hewitt and Manning [15] , who examines the correlation between BERT’s hidden states and the parse tree distance metric (similar to NT-distance in our language). Subsequent studies [ 30 , 40 , 20 , 18 , 34 , 36 , 8 ] also explored probing techniques to suggest that BERT-like transformers can approximate CFGs from natural languages .

Our approach differs not only in the multi-head probing formula that we proposed; also that we use synthetic data to demonstrate that linear probing can almost perfectly recover NT ancestors and boundaries, even for complex and ambiguous CFG strings exceeding hundreds of tokens (c.f. English CFG has an average length of 28, see Appendix G ). We focus on training generative decoder-only models; an encoder-based model like BERT [ 17 ] or its modern variant 𝚍𝚎𝙱𝙴𝚁𝚃𝚊 \mathtt{deBERTa} [ 14 ] may not learn deep (i.e., close to the CFG root) NT information very well, as shown in Result 4 - 5 .

Our results, along with Section 5 next, shall provide evidence that generative language models like GPT-2 employ a DP-like approach to generate CFGs, while encoder-based models trained via MLM struggle to learn more complex/deeper CFGs.

## 5 Results 6-9: How Do Transformers Learn NTs?

We now delve into the attention patterns, which reveal the model’s reasoning mechanisms. We demonstrate that these patterns mirror the CFG’s syntactic structure and rules, with the transformer employing different attention heads to reason with NTs at different CFG levels.

### 5.1 Result 6: Position-Based Attention

We first note that the transformer’s attention weights are primarily influenced by the tokens’ relative distance. This holds true even when trained on the CFG data with absolute positional embedding. This implies that the transformer learns the CFG’s regularity and periodicity through positional information, which it then uses for generation.

Formally, let A l , h , j → i ​ ( x ) A_{l,h,j\to i}(x) for j ≥ i j\geq i represent the attention weight for positions j → i j\to i at layer l l and head h h of the transformer, on input sequence x x . For each layer l l , head h h , and distance p ≥ 0 p\geq 0 , we compute the average of the partial sum ∑ 1 ≤ i ′ ≤ i A l , h , j → i ′ ​ ( x ) \sum_{1\leq i^{\prime}\leq i}A_{l,h,j\to i^{\prime}}(x) over all data x x and pairs i , j i,j with j − i = p j-i=p . We plot this cumulative sum for l , h , p l,h,p in Figure 8 . We observe a strong correlation between the attention pattern and the relative distance p = j − i p=j-i . The attention pattern is also multi-scale , with some attention heads focusing on shorter distances and others on longer ones.

Motivated by this, we explore whether using position-based attention is sufficient to learn CFGs. In Figure 4 , we find that 𝙶𝙿𝚃 𝗉𝗈𝗌 \mathtt{GPT}_{\mathsf{pos}} (or even 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} ) performs well, surpassing the vanilla 𝙶𝙿𝚃 \mathtt{GPT} , but not reaching the full potential of 𝙶𝙿𝚃 𝗋𝖾𝗅 \mathtt{GPT}_{\mathsf{rel}} . This supports the superior practical performance of relative-position based transformer variants (such as 𝙶𝙿𝚃 𝗋𝖾𝗅 , 𝙶𝙿𝚃 𝗋𝗈𝗍 \mathtt{GPT}_{\mathsf{rel}},\mathtt{GPT}_{\mathsf{rot}} , 𝚍𝚎𝙱𝙴𝚁𝚃𝚊 \mathtt{deBERTa} ) over their base models ( 𝙶𝙿𝚃 \mathtt{GPT} or BERT). On this other hand, this also indicates that position-based attention alone is not enough for transformers to learn CFGs.

### 5.2 Result 7-9: Boundary-Based Attention

Next, our idea is to remove the position-bias from the attention to examine the remainder. We discover that the transformer also learns a strong boundary-based attention pattern, where tokens on the NT-end boundaries typically attend to the “most adjacent” NT-end boundaries , see Figure 2 for an illustration. This pattern enables the transformer to effectively learn the hierarchical and recursive structure of the CFG, and generate output tokens based on the NT symbols and rules.

Formally, let A l , h , j → i ​ ( x ) A_{l,h,j\to i}(x) for j ≥ i j\geq i denote the attention weight for positions j → i j\to i at layer l l and head h h of the transformer, on input sequence x x . Given a sample pool { x ( n ) } n ∈ [ N ] ∈ L ⁡ ( 𝒢 ) \{x^{(n)}\}_{n\in[N]}\in L(\mathcal{G}) , we compute for each layer l l , head h h , 12 12 12 Throughout this paper, we use ⟦ ⋅ ⟧ \llbracket\cdot\rrbracket to denote multi-sets that allow multiplicity, such as ⟦ 1 , 2 , 2 , 3 ⟧ \llbracket 1,2,2,3\rrbracket . This allows us to conveniently talk about its set average. A ¯ l , h , p = A v e r a g e ⟦ A l , h , j → i ( x ( n ) ) ∣ n ∈ N , 1 ≤ i ≤ j ≤ len ( x ( n ) ) s.t. j − i = p ⟧ , \overline{A}_{l,h,p}=Average\llbracket A_{l,h,j\to i}(x^{(n)})\mid n\in{N},1\leq i\leq j\leq\textbf{len}(x^{(n)})\text{ s.t. }j-i=p\rrbracket\kern 5.0pt, which represents the average attention between any token pairs of distance p p over the sample pool. To remove position-bias, we focus on B l , h , j → i ​ ( x ) = def A l , h , j → i ​ ( x ) − A ¯ l , h , j − i B_{l,h,j\to i}(x)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}A_{l,h,j\to i}(x)-\overline{A}_{l,h,j-i} in this subsection. Our observation can be broken down into three steps.

Result 7 ( Figure 9(a) ) . B l , h , j → i ​ ( x ) B_{l,h,j\to i}(x) exhibits a strong bias towards tokens i i at NT ends . This can be seen in Figure 9(a) , where we present the average value of B l , h , j → i ​ ( x ) B_{l,h,j\to i}(x) over data x x and pairs i , j i,j where i + δ i+\delta is the deepest NT-end at level ℓ \ell (symbolically, 𝔟 ♯ ​ ( i + δ ) = ℓ \mathfrak{b}^{\sharp}(i+\delta)=\ell ). The attention weights are highest when δ = 0 \delta=0 and decrease rapidly for surrounding tokens.

Result 8 ( Figure 9(b) ) . B l , h , j → i ​ ( x ) B_{l,h,j\to i}(x) favors pairs i , j i,j both at NT ends at some level ℓ \ell . This can be seen in Figure 9(b) , where we show the average value of B l , h , j → i ​ ( x ) B_{l,h,j\to i}(x) over data x x and pairs i , j i,j where 𝔟 ℓ ​ ( i + δ 1 ) = 𝔟 ℓ ​ ( j + δ 2 ) = 1 \mathfrak{b}_{\ell}(i+\delta_{1})=\mathfrak{b}_{\ell}(j+\delta_{2})=1 for δ 1 , δ 2 ∈ { − 1 , 0 , 1 } \delta_{1},\delta_{2}\in\{-1,0,1\} . It is maximized when δ 1 = δ 2 = 0 \delta_{1}=\delta_{2}=0 .

Result 9 ( Figure 9(c) ) . B l , h , j → i ​ ( x ) B_{l,h,j\to i}(x) favors “adjacent” NT-end token pairs i , j i,j . Above, we define “adjacency” as follows. We introduce B l , h , ℓ ′ → ℓ , r end → end B^{\text{end }\to\text{end }}_{l,h,\ell^{\prime}\to\ell,r} to represent the average value of B l , h , j → i ​ ( x ) B_{l,h,j\to i}(x) over samples x x and token pairs i , j i,j that are at the deepest NT-ends on levels ℓ , ℓ ′ \ell,\ell^{\prime} respectively (symbolically, 𝔟 ♯ ​ ( i ) = ℓ ∧ 𝔟 ♯ ​ ( j ) = ℓ ′ \mathfrak{b}^{\sharp}(i)=\ell\wedge\mathfrak{b}^{\sharp}(j)=\ell^{\prime} ), and are at a distance r r based on the ancestor indices at level ℓ \ell (symbolically, 𝔭 ℓ ​ ( j ) − 𝔭 ℓ ​ ( i ) = r \mathfrak{p}_{\ell}(j)-\mathfrak{p}_{\ell}(i)=r ). We observe that B l , h , ℓ ′ → ℓ , r end → end B^{\text{end }\to\text{end }}_{l,h,\ell^{\prime}\to\ell,r} decreases as r r increases, and is highest when r = 0 r=0 (or r = 1 r=1 for pairs ℓ ′ → ℓ \ell^{\prime}\to\ell without an r = 0 r=0 entry). 13 13 13 For any token pair j → i j\to i with ℓ = 𝔟 ♯ ​ ( i ) ≥ 𝔟 ♯ ​ ( j ) = ℓ ′ \ell=\mathfrak{b}^{\sharp}(i)\geq\mathfrak{b}^{\sharp}(j)=\ell^{\prime} — meaning i i is at an NT-end closer to the root than j j — it satisfies 𝔭 ℓ ​ ( j ) − 𝔭 ℓ ​ ( i ) ≥ 1 \mathfrak{p}_{\ell}(j)-\mathfrak{p}_{\ell}(i)\geq 1 so their distance r r is strictly positive.

In conclusion, tokens corresponding to NT-ends at level ℓ ′ \ell^{\prime} statistically have higher attention weights to their most adjacent NT-ends at every level ℓ \ell , even after removing position-bias . 14 14 14 Without removing position-bias, such a statement might be meaningless as the position-bias may favor “adjacent” anything, including NT-end pairs.

### 5.3 Connection to Dynamic Programming (DP)

Dynamic programming involves storage of intermediate results and a recurrent formula to combine them. While identifying a specific DP implementation within transformers is infeasible due to numerous possibilities ( Footnote 11 ), we can probe for crucial commonalities. Section 4 demonstrated that transformers encode the DP’s storage backbone—all necessary 𝖣𝖯 ⁡ ( i , j , a ) \mathsf{DP}(i,j,a) values on the correct CFG parse tree—independent of any specific DP implementation. Regarding the recurrent formula (e.g., 𝖣𝖯 ⁡ ( k , j , a ) \mathsf{DP}(k,j,a) derived from 𝖣𝖯 ⁡ ( k , i , b ) ∧ 𝖣𝖯 ⁡ ( i , j , c ) \mathsf{DP}(k,i,b)\wedge\mathsf{DP}(i,j,c) for rule a ↦ b , c a\mapsto b,c ), 𝖣𝖯 ⁡ ( k , i , b ) \mathsf{DP}(k,i,b) is stored near i i , while 𝖣𝖯 ⁡ ( k , j , a ) \mathsf{DP}(k,j,a) and 𝖣𝖯 ⁡ ( i , j , c ) \mathsf{DP}(i,j,c) are near j j ( Result 5 ). This necessitates a memory read from i i at j j ( j → i j\to i ). Indeed, for adjacent NT-ends i , j i,j at the same level, GPT models exhibit such j → i j\to i attention ( Result 8 ), suggesting an information flow consistent with DP. See Figure 10 (top).

Further reading for DP/CFG experts. Transformers are both parsing and generative algorithms. CFG experts (or participants in competitions like IOI/USACO/ACM-ICPC) may recognize that the generative process requires a second DP: let 𝖣𝖯 2 ​ ( j , a ) \mathsf{DP}_{2}(j,a) denote if prefix x 1 , … , x j x_{1},\dots,x_{j} can be followed by symbol a ∈ 𝐍𝐓 ∪ 𝐓 a\in\mathbf{NT}\cup\mathbf{T} . If a rule b ↦ c , a b\mapsto c,a holds and 𝖣𝖯 ⁡ ( i , j , c ) ∧ 𝖣𝖯 2 ​ ( i , b ) \mathsf{DP}(i,j,c)\wedge\mathsf{DP}_{2}(i,b) are true, then 𝖣𝖯 2 ​ ( j , a ) \mathsf{DP}_{2}(j,a) is also true. This is similar to the inside-outside algorithm [ 9 ] . The model must perform a memory read from position j j to i i , where i i is the nearest NT-end to j j at a different level. Unlike parsing 𝖣𝖯 \mathsf{DP} ; the generative 𝖣𝖯 2 \mathsf{DP}_{2} uses information about the end of a prior constituent (at i i ) to inform the valid start (at j j ) for symbol a a . The attention patterns ( Result 9 and Figure 10 bottom), indicative of the model’s reasoning process, support this directional information flow.

To generate following the CFG distribution, the model learns 𝖣𝖯 2 ′ ​ ( j , a ) \mathsf{DP}_{2}^{\prime}(j,a) , the probability that symbol a a can follow prefix x 1 , … , x j x_{1},\dots,x_{j} . The recurrent formula involves similar memory read patterns. We omit this detail for brevity.

In sum, while pinpointing a specific DP implementation is difficult, the DP backbone, including storage states and recurrent formulas, is evident in pretrained models’ hidden states and attention patterns. This suggests that pretrained (decoder-only) transformers largely mimic dynamic programming, regardless of the specific DP implementation.

## 6 Results 10-13: Extensions of CFGs

### 6.1 Result 10: Implicit CFGs

In an implicit CFG , terminal symbols represent bags of tokens with shared properties. For example, a terminal symbol like n ​ o ​ u ​ n noun corresponds to a distribution over a bag of nouns, while v ​ e ​ r ​ b verb corresponds to a distribution over a bag of verbs. These distributions can be non-uniform and overlapping, allowing tokens to be shared between different terminal symbols. During pre-training, the model learns to associate tokens with their respective syntactic or semantic categories, without prior knowledge of their specific roles in the CFG.

Formally, we consider a set of observable tokens 𝐎𝐓 \mathbf{OT} , and each terminal symbol t ∈ 𝐓 t\in\mathbf{T} in 𝒢 \mathcal{G} is associated with a subset 𝐎𝐓 t ⊆ 𝐎𝐓 \mathbf{OT}_{t}\subseteq\mathbf{OT} and a probability distribution 𝒟 t \mathcal{D}_{t} over 𝐎𝐓 t \mathbf{OT}_{t} . The sets ( 𝐎𝐓 t ) t (\mathbf{OT}_{t})_{t} can be overlapping. To generate a string from this implicit CFG, after generating x = ( x 1 , x 2 , … , x m ) ∼ L ⁡ ( 𝒢 ) x=(x_{1},x_{2},\dots,x_{m})\sim L(\mathcal{G}) , for each terminal symbol x i x_{i} , we independently sample one element y i ∼ 𝒟 x i y_{i}\sim\mathcal{D}_{x_{i}} . After that, we observe the new string y = ( y 1 , y 2 , ⋯ , y m ) y=(y_{1},y_{2},\cdots,y_{m}) , and let this new distribution be called y ∼ L O ​ ( 𝒢 ) y\sim L_{O}(\mathcal{G})

We pre-train language models using samples from the distribution y ∼ L O ​ ( 𝒢 ) y\sim L_{O}(\mathcal{G}) . During testing, we evaluate the success probability of the model generating a string that belongs to L O ​ ( 𝒢 ) L_{O}(\mathcal{G}) , given an input prefix y : c y_{:c} . Or, in symbols, 𝐏𝐫 y ∼ L O ​ ( 𝒢 ) + randomness of F [ ( y : c , F ( y : c ) ) ∈ L O ( 𝒢 ) ] , \textstyle\operatornamewithlimits{\mathbf{Pr}}_{y\sim L_{O}(\mathcal{G})+\text{randomness of $F$ }}\big[(y_{:c},F(y_{:c}))\in L_{O}(\mathcal{G})\big]\kern 5.0pt, where F ( y : c ) F(y_{:c}) represents the model’s generated completion given prefix y : c y_{:c} . (We again use dynamic programming to determine whether the output string is in L O ​ ( 𝒢 ) L_{O}(\mathcal{G}) .)

We summarize our finding below and deferring details to Appendix E . Result 10 ( Figure 11 ) . Generative language models can learn implicit CFGs very well. In particular, after pretraining, the token embeddings from the same subset 𝐎𝐓 t \mathbf{OT}_{t} are grouped together, indicating they use token embedding layer to encode the hidden terminal symbol information.

### 6.2 Results 11-13: Robustness on Corrupted CFG

One may also wish to pre-train a transformer to be robust against errors and inconsistencies in the input. For example, if the input data is a prefix with some tokens being corrupted or missing, then one may hope the transformer to correct the errors and still complete the sentence following the correct CFG rules. Robustness is an important property, as it reflects the generalization and adaptation ability of the transformer to reason effectively with real-world training data, which may not always follow the CFG perfectly (such as having grammar errors).

To test robustness, for each input prefix x : c x_{:c} of length c c that belongs to the CFG, we randomly select a set of positions i ∈ [ c ] i\in[c] in this prefix — each with probability ρ \rho — and flip them i.i.d. with a random symbol in 𝐓 \mathbf{T} . Call the resulting prefix x ~ : c \widetilde{x}_{:c} . Next, we feed the corrupted prefix x ~ : c \widetilde{x}_{:c} to the transformer F F and compute its generation accuracy in the uncorrupted CFG: 𝐏𝐫 x ∼ L ⁡ ( 𝒢 ) , F [ ( x : c , F ( x ~ : c ) ) ∈ L ( 𝒢 ) ] \operatornamewithlimits{\mathbf{Pr}}_{x\sim L(\mathcal{G}),\,F}[(x_{:c},F(\widetilde{x}_{:c}))\in L(\mathcal{G})] .

We not only consider clean pre-training, but also some versions of robust pre-training . That is, we randomly select γ ∈ [ 0 , 1 ] \gamma\in[0,1] fraction of the training data and perturb them before feeding into the pre-training process. We compare three types of data perturbations. 15 15 15 One can easily extend our experiments by considering other types of data corruption (for evaluation), and other types of data perturbations (for training). We refrain from doing so because it is beyond the scope of this paper. • (T-level random perturbation). Each x i x_{i} w.p. 0.15 0.15 we replace it with a random symbol in 𝐓 \mathbf{T} .

• (NT-level random perturbation). Let ℓ = L − 1 \ell=L-1 and recall s ℓ = ( s ℓ , 1 , s ℓ , 2 , … , s ℓ , m L − 1 ) s_{\ell}=\big(s_{\ell,1},s_{\ell,2},\dots,s_{\ell,m_{L-1}}\big) is the sequence of symbols at NT-level ℓ \ell . For each s ℓ , i s_{\ell,i} , w.p. 0.10 0.10 we perturb it to a random symbol in 𝐍𝐓 ℓ \mathbf{NT}_{\ell} ; and then generate x = s L x=s_{L} according to this perturbed sequence.

• (NT-level deterministic perturbation). Let ℓ = L − 1 \ell=L-1 and fix a permutation π \pi over symbols in 𝐍𝐓 ℓ \mathbf{NT}_{\ell} . For each s ℓ , i s_{\ell,i} , w.p. 0.05 0.05 we perturb it to its next symbol in 𝐍𝐓 L − 1 \mathbf{NT}_{L-1} according to π \pi ; and then generate x = s L x=s_{L} according to this perturbed sequence.

We focus on ρ = 0.15 \rho=0.15 with a wide range of perturbation rate τ = 0.0 , 0.1 , … , 0.9 , 1.0 \tau=0.0,0.1,\dots,0.9,1.0 . We present our findings in Figure 12 . The main message is:

Result 11 ( Figure 12 , rows 4/5) . When pretrained over clean data, GPT models are not so robust to “grammar mistakes.” It is beneficial to include corrupted or low-quality pretrain data. Specifically, GPT models achieve only ∼ 30 % \sim 30\% accuracy when pretrained over clean data x ∼ L ⁡ ( 𝒢 ) x\sim L(\mathcal{G}) . If we pretrain from perturbed data — both when γ = 1.0 \gamma=1.0 so all data are perturbed, and when γ = 0.1 \gamma=0.1 so we have a small fraction of perturbed data — GPT can achieve ∼ 79 % , 82 % \sim 79\%,82\% and 60 % 60\% robust accuracies respectively using the three types of data perturbations (rows 4/5 of Figure 12 ).

Next, we take a closer look. If we use temperature τ = 1 \tau=1 for generation: Result 12 ( Figure 12 , rows 3/6/9) . Pre-training on corrupted data teaches model a mode switch . • Given a correct prefix, it mostly completes with a correct string in the CFG (Row 9); • Given a corrupted prefix, it always completes sentences with grammar mistakes (Row 6); • When given no prefix, it generates corrupted strings with probability close to γ \gamma (Row 3).

By comparing the generation accuracies across different τ \tau and γ \gamma , we observe:

Result 13 ( Figure 12 , rows 4/5/6) . High robust accuracy is achieved when generating using low temperatures τ \tau , 16 16 16 Recall, when temperature τ = 0 \tau=0 the generation is greedy and deterministic; when τ = 1 \tau=1 it reflects the unaltered distribution learned by the transformer; when τ > 0 \tau>0 s small it encourages the transformer to output “more probable” tokens. and is not sensitive to γ \gamma – the fraction of pretrain data that is perturbed. This should not be surprising given that the language model learned a “mode switch.” Using low temperature encourages the model to, for each next token, pick a more probable solution. This allows it to achieve good robust accuracy even when the model is trained totally on corrupted data ( γ = 1.0 \gamma=1.0 ). Note this is consistent with practice: when feeding a pre-trained completion model (such as Llama or GPT-3-davinci003) with prompts of grammar mistakes, it tends to produce texts also with (even new!) grammar mistakes when using a large temperature.

Our experiments suggest that, additional instruct fine-tuning may be necessary, if one wants the model to always stay in the “correct mode” even for high temperatures. This is beyond the scope of this paper.

## 7 Related Work and Conclusion

Related Works. Transformers can encode some CFGs, particularly those related to human languages [ 15 , 30 , 40 , 20 , 18 , 34 , 36 , 8 ] . Deletang et al. [11] explored transformers’ learnability on languages within the Chomsky hierarchy, including CFGs. However, the inner mechanisms of how transformers solve these tasks remain unclear.

Some works can precisely interpret each neuron’s function but focus on simpler tasks and architectures. For example, Nanda et al. [23] studied 1- or 2-layer transformers with context length 3 for arithmetic addition. We focus on the 100M-sized GPT-2 model with a context length over 300. While we cannot determine each neuron’s function, we have identified roles of some heads and hidden states that correlate with DP.

Murty et al. [22] explored methods beyond linear probing to deduce tree structures learned by transformers. They designed a score to quantify a transformer’s “tree-like” nature, showing it becomes more tree-like during training. Our Figure 21 in Appendix C.3 supports these findings.

Conclusion. In this paper, we analyzed how transformers like GPT-2 perform hierarchical structure reasoning on challenging synthetic CFGs, showing that their internal states correlate strongly with the dynamic ‐programming computations underpinning such reasoning (i.e., for parsing and generation). This work provides a controlled interpretability setting and offers insights into how language models can effectively reason over complex, hierarchical structures and generate valid continuations. We also introduced multi ‐head linear probing—a tool that may enable deeper analyses of larger models on similarly complex tasks.

We further derived several corollary findings: 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.

While synthetic CFGs offer well ‐defined benchmarks for compositional and hierarchical behavior, they do not capture the full diversity of language or intelligence—much like sorting or ListOps tasks. For this reason, we explore grade-school math and reasoning in Parts 2.1+2.2 [ 37 , 38 ] , knowledge storage, extraction, and manipulation in Parts 3.1+3.2+3.3 [ 3 , 4 , 5 ] , and integrate these into a unified synthetic-data architecture playground in Part 4 [ 1 ] .

Appendix

## References

[1] Zeyuan Allen-Zhu. Physics of Language Models: Part 4.1, Architecture Design and the Magic of Canon Layers. SSRN Electronic Journal , May 2025. https://ssrn.com/abstract=5240330 .

[2] Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. In COLT , 2023. Full version available at http://arxiv.org/abs/2001.04413 .

[3] Zeyuan Allen-Zhu and Yuanzhi Li. Physics of Language Models: Part 3.1, Knowledge Storage and Extraction. In Proceedings of the 41st International Conference on Machine Learning , ICML 2024, 2024. Full version available at https://ssrn.com/abstract=5250633 .

[4] Zeyuan Allen-Zhu and Yuanzhi Li. Physics of Language Models: Part 3.2, Knowledge Manipulation. In Proceedings of the 13th International Conference on Learning Representations , ICLR 2025, 2025a. Full version available at https://ssrn.com/abstract=5250621 .

[5] Zeyuan Allen-Zhu and Yuanzhi Li. Physics of Language Models: Part 3.3, Knowledge Capacity Scaling Laws. In Proceedings of the 13th International Conference on Learning Representations , ICLR 2025, 2025b. Full version available at https://ssrn.com/abstract=5250617 .

[6] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In ICML , 2019. Full version available at http://arxiv.org/abs/1811.03962 .

[7] Sanjeev Arora and Yi Zhang. Do gans actually learn the distribution? an empirical study. arXiv preprint arXiv:1706.08224 , 2017.

[8] David Arps, Younes Samih, Laura Kallmeyer, and Hassan Sajjad. Probing for constituency structure in neural language models. arXiv preprint arXiv:2204.06201 , 2022.

[9] James K Baker. Trainable grammars for speech recognition. The Journal of the Acoustical Society of America , 65(S1):S132–S132, 1979.

[10] Sid Black, Stella Biderman, Eric Hallahan, Quentin Anthony, Leo Gao, Laurence Golding, Horace He, Connor Leahy, Kyle McDonell, Jason Phang, Michael Pieler, USVSN Sai Prashanth, Shivanshu Purohit, Laria Reynolds, Jonathan Tow, Ben Wang, and Samuel Weinbach. GPT-NeoX-20B: An open-source autoregressive language model. In Proceedings of the ACL Workshop on Challenges & Perspectives in Creating Large Language Models , 2022. URL https://arxiv.org/abs/2204.06745 .

[11] Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, et al. Neural networks and the chomsky hierarchy. In ICLR , 2023.

[12] Brian DuSell and David Chiang. Learning hierarchical structures with differentiable nondeterministic stacks. In ICLR , 2022.

[13] Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. A mathematical framework for transformer circuits. Transformer Circuits Thread , 1, 2021.

[14] Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention. arXiv preprint arXiv:2006.03654 , 2020.

[15] John Hewitt and Christopher D. Manning. A structural probe for finding syntax in word representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) , pages 4129–4138, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1/N19-1419 . URL https://aclanthology.org/N19-1419 .

[16] Samy Jelassi, David Brandfonbrener, Sham M Kakade, and Eran Malach. Repeat after me: Transformers are better than state space models at copying. arXiv preprint arXiv:2402.01032 , 2024.

[17] Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT , pages 4171–4186, 2019.

[18] Christopher D Manning, Kevin Clark, John Hewitt, Urvashi Khandelwal, and Omer Levy. Emergent linguistic structure in artificial neural networks trained by self-supervision. Proceedings of the National Academy of Sciences , 117(48):30046–30054, 2020.

[19] Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics , 19(2):313–330, 1993. URL https://aclanthology.org/J93-2004 .

[20] Rowan Hall Maudslay and Ryan Cotterell. Do syntactic probes probe syntax? experiments with jabberwocky probing. arXiv preprint arXiv:2106.02559 , 2021.

[21] Milad Moradi and Matthias Samwald. Evaluating the robustness of neural language models to input perturbations. arXiv preprint arXiv:2108.12237 , 2021.

[22] Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher D Manning. Characterizing intrinsic compositionality in transformers with tree projections. In ICLR , 2023.

[23] Neel Nanda, Lawrence Chan, Tom Liberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. arXiv preprint arXiv:2301.05217 , 2023.

[24] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209.11895 , 2022.

[25] OpenAI. Gpt-4 technical report, 2023.

[26] Matt Post and Shane Bergsma. Explicit and implicit syntactic features for text classification. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) , pages 866–872, 2013.

[27] Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108.12409 , 2021.

[28] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.

[29] Itiroo Sakai. Syntax in universal translation. In Proceedings of the International Conference on Machine Translation and Applied Language Analysis , 1961.

[30] Hui Shi, Sicun Gao, Yuandong Tian, Xinyun Chen, and Jishen Zhao. Learning bounded context-free-grammar via lstm and the transformer: Difference and the explanations. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 36, pages 8267–8276, 2022.

[31] Michael Sipser. Introduction to the Theory of Computation . Cengage Learning, 2012.

[32] Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, 2021.

[33] Lifu Tu, Garima Lalwani, Spandana Gella, and He He. An empirical study on robustness to spurious correlations using pre-trained language models. Transactions of the Association for Computational Linguistics , 8:621–633, 2020.

[34] David Vilares, Michalina Strzyz, Anders Søgaard, and Carlos Gómez-Rodríguez. Parsing as pretraining. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 34, pages 9114–9121, 2020.

[35] Kevin Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. Interpretability in the wild: a circuit for indirect object identification in gpt-2 small. arXiv preprint arXiv:2211.00593 , 2022.

[36] Zhiyong Wu, Yun Chen, Ben Kao, and Qun Liu. Perturbed masking: Parameter-free probing for analyzing and interpreting bert. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics , pages 4166–4176, 2020.

[37] Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process. In Proceedings of the 13th International Conference on Learning Representations , ICLR 2025, 2025a. Full version available at https://ssrn.com/abstract=5250629 .

[38] Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of Language Models: Part 2.2, How to Learn From Mistakes on Grade-School Math Problems. In Proceedings of the 13th International Conference on Learning Representations , ICLR 2025, 2025b. Full version available at https://ssrn.com/abstract=5250631 .

[39] Shizhuo Dylan Zhang, Curt Tigges, Stella Biderman, Maxim Raginsky, and Talia Ringer. Can transformers learn to solve problems recursively? arXiv preprint arXiv:2305.14699 , 2023.

[40] Haoyu Zhao, Abhishek Panigrahi, Rong Ge, and Sanjeev Arora. Do transformers parse while predicting the masked word? arXiv preprint arXiv:2303.08117 , 2023.

## Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" ( ) button, located in the page header.

Tip: You can select the relevant text first, to include it in your report.

Our team has already identified the following issues . We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion , and welcome developer contributions .

## Appendix A Experiment Setups

### A.1 Dataset Details

We construct seven synthetic CFGs of depth L = 7 L=7 with varying levels of learning difficulty. It can be inferred that the greater the number of T/NT symbols, the more challenging it is to learn the CFG. For this reason, to push the capabilities of language models to their limits, we primarily focus on 𝖼𝖿𝗀𝟥𝖻 , 𝖼𝖿𝗀𝟥𝗂 , 𝖼𝖿𝗀𝟥𝗁 , 𝖼𝖿𝗀𝟥𝗀 , 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3b},\mathsf{cfg3i},\mathsf{cfg3h},\mathsf{cfg3g},\mathsf{cfg3f} , which are of sizes ( 1 , 3 , 3 , 3 , 3 , 3 , 3 ) (1,3,3,3,3,3,3) and present increasing levels of difficulty. Detailed information about these CFGs is provided in Figure 13 : • In 𝖼𝖿𝗀𝟥𝖻 \mathsf{cfg3b} , we construct the CFG such that the degree | ℛ ⁡ ( a ) | = 2 |\mathcal{R}(a)|=2 for every NT a a . We also ensure that in any generation rule, consecutive pairs of T/NT symbols are distinct.

The 25%, 50%, 75%, and 95% percentile string lengths are 251,278,308,342 251,278,308,342 respectively.

• In 𝖼𝖿𝗀𝟥𝗂 \mathsf{cfg3i} , we set | ℛ ⁡ ( a ) | = 2 |\mathcal{R}(a)|=2 for every NT a a . We remove the requirement for distinctness to make the data more challenging than 𝖼𝖿𝗀𝟥𝖻 \mathsf{cfg3b} . The 25%, 50%, 75%, and 95% percentile string lengths are 276,307,340,386 276,307,340,386 respectively.

• In 𝖼𝖿𝗀𝟥𝗁 \mathsf{cfg3h} , we set | ℛ ⁡ ( a ) | ∈ { 2 , 3 } |\mathcal{R}(a)|\in\{2,3\} for every NT a a to make the data more challenging than 𝖼𝖿𝗀𝟥𝗂 \mathsf{cfg3i} . The 25%, 50%, 75%, and 95% percentile string lengths are 202,238,270,300 202,238,270,300 respectively.

• In 𝖼𝖿𝗀𝟥𝗀 \mathsf{cfg3g} , we set | ℛ ⁡ ( a ) | = 3 |\mathcal{R}(a)|=3 for every NT a a to make the data more challenging than 𝖼𝖿𝗀𝟥𝗁 \mathsf{cfg3h} . The 25%, 50%, 75%, and 95% percentile string lengths are 212,258,294,341 212,258,294,341 respectively.

• In 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} , we set | ℛ ⁡ ( a ) | ∈ { 3 , 4 } |\mathcal{R}(a)|\in\{3,4\} for every NT a a to make the data more challenging than 𝖼𝖿𝗀𝟥𝗀 \mathsf{cfg3g} . The 25%, 50%, 75%, and 95% percentile string lengths are 191,247,302,364 191,247,302,364 respectively.

###### Remark A.1 .

From the examples in Figure 13 , it becomes evident that for grammars 𝒢 \mathcal{G} of depth 7 7 , proving that a string x x belongs to L ⁡ ( 𝒢 ) L(\mathcal{G}) is highly non-trivial, even for a human being, and even when the CFG rules are known. The standard method of demonstrating x ∈ L ⁡ ( 𝒢 ) x\in L(\mathcal{G}) is through dynamic programming. We further discuss what we mean by a CFG’s “difficulty” in Appendix G , and provide additional experiments beyond the 𝖼𝖿𝗀𝟥 \mathsf{cfg3} data family.

###### Remark A.2 .

The dataset 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} lies at the difficulty threshold that GPT2-small can master under our pretraining setup (see Figure 31 ; training details in later sections). Although deeper, more complex CFGs are possible (as we explore in [ 1 ] ), they would require a larger model and extended training. We focus on 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} because it already provides compelling evidence for our findings.

Simultaneously, to illustrate that transformers can learn CFGs with larger | 𝐍𝐓 | |\mathbf{NT}| or | 𝐓 | |\mathbf{T}| , we construct datasets 𝖼𝖿𝗀𝟥𝖾𝟣 \mathsf{cfg3e1} and 𝖼𝖿𝗀𝟥𝖾𝟤 \mathsf{cfg3e2} respectively of sizes ( 1 , 3 , 9 , 27 , 81 , 27 , 9 ) (1,3,9,27,81,27,9) and ( 1 , 3 , 9 , 27 , 27 , 9 , 4 ) (1,3,9,27,27,9,4) . They are too lengthy to describe so we include them in an attached txt file in Appendix G.2 .

### A.2 Model Architecture Details

We define 𝙶𝙿𝚃 \mathtt{GPT} as the standard GPT2-small architecture [ 28 ] , which consists of 12 layers, 12 attention heads per layer, and 768 (= 12 × 64 12\times 64 ) hidden dimensions. We pre-train 𝙶𝙿𝚃 \mathtt{GPT} on the aforementioned datasets, starting from random initialization. For a baseline comparison, we also implement DeBERTa [ 14 ] , resizing it to match the dimensions of GPT2 — thus also comprising 12 layers, 12 attention heads, and 768 dimensions.

Architecture size. We have experimented with models of varying sizes and observed that their learning capabilities scale with the complexity of the CFGs. To ensure a fair comparison and enhance reproducibility, we primarily focus on models with 12 layers, 12 attention heads, and 768 dimensions. The transformers constructed in this manner consist of 86M parameters.

Modern GPTs with relative attention. Recent research [ 14 , 32 , 10 ] has demonstrated that transformers can significantly improve performance by using attention mechanisms based on the relative position differences of tokens, as opposed to the absolute positions used in the original GPT2 [ 28 ] or BERT [ 17 ] . There are two main approaches to achieve this. The first is to use a “relative positional embedding layer” on | j − i | |j-i| when calculating the attention from j j to i i (or a bucket embedding to save space). This approach is the most effective but tends to train slower. The second approach is to apply a rotary positional embedding (RoPE) transformation [ 32 ] on the hidden states; this is known to be slightly less effective than the relative approach, but it can be trained much faster.

We have implemented both approaches. We adopted the RoPE implementation from the GPT-NeoX-20B project (along with the default parameters), but downsized it to fit the GPT2 small model. We refer to this architecture as 𝙶𝙿𝚃 𝗋𝗈𝗍 \mathtt{GPT}_{\mathsf{rot}} . Since we could not find a standard implementation of GPT using relative attention, we re-implemented GPT2 using the relative attention framework from DeBERTa [ 14 ] . (Recall, DeBERTa is a variant of BERT that effectively utilizes relative positional embeddings.) We refer to this architecture as 𝙶𝙿𝚃 𝗋𝖾𝗅 \mathtt{GPT}_{\mathsf{rel}} .

Weaker GPTs utilizing only position-based attention. For the purpose of analysis, we also consider two significantly weaker variants of GPT, where the attention matrix exclusively depends on the token positions, and not on the input sequences or hidden embeddings. In other words, the attention pattern remains constant for all input sequences.

We implement 𝙶𝙿𝚃 𝗉𝗈𝗌 \mathtt{GPT}_{\mathsf{pos}} , a variant of 𝙶𝙿𝚃 𝗋𝖾𝗅 \mathtt{GPT}_{\mathsf{rel}} that restricts the attention matrix to be computed solely using the (trainable) relative positional embedding. This can be perceived as a GPT variant that maximizes the use of position-based attention . We still choose the 12-layer, 12-head, 768-dim structure.

We also implement 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} , a 12-layer, 8-head, 1024-dimensional Transformer where the attention matrices are fixed . Specifically, for each h ∈ [ 8 ] h\in[8] , the h h -th head consistently applies a uniform average over the previous 2 h − 1 2^{h}-1 tokens. This can be viewed as a GPT variant that uses the simplest form of position-based attention . Since 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} lacks key and value matrices, its parameter count differs from standard GPT variants. A GPT2-small-sized 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} —i.e., one with 12 layers and 840 hidden dimensions—matches its parameter count. As we show in Appendix H , this smaller version performs similarly to the 1024-dimensional 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} .

###### Remark A.3 .

It should not be surprising that 𝙶𝙿𝚃 𝗉𝗈𝗌 \mathtt{GPT}_{\mathsf{pos}} or 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} perform much worse than other GPT models on real-life wikibook pre-training. However, once again, we use them only for analysis purpose in this paper, as we wish to demonstrate what is the maximum power of GPT when only using position-based attention to learn CFGs, and what is the marginal effect when one goes beyond position-based attention.

Features from random transformer. Finally we also consider a randomly-initialized 𝙶𝙿𝚃 𝗋𝖾𝗅 \mathtt{GPT}_{\mathsf{rel}} , and use those random features for the purpose of predicting NT ancestors and NT ends. This serves as a baseline, and can be viewed as the power of the so-called (finite-width) neural tangent kernel [ 6 ] . We call this 𝙶𝙿𝚃 𝗋𝖺𝗇𝖽 \mathtt{GPT}_{\mathsf{rand}} .

### A.3 Pre-Training Details

For each sample x ∼ L ⁡ ( 𝒢 ) x\sim L(\mathcal{G}) we append it to the left with a BOS token and to the right with an EOS token. Then, following the tradition of language modeling (LM) pre-training, we concatenate consecutive samples and randomly cut the data to form sequences of a fixed window length 512.

As a baseline comparison, we also applied DeBERTa on a masked language modeling (MLM) task for our datasets. We use standard MLM parameters: 15 % 15\% masked probability, in which 80 % 80\% chance of using a masked token, 10% chance using the original token, and 10% chance using a random token.

We use standard initializations from the huggingface library. For GPT pre-training, we use AdamW with β = ( 0.9 , 0.98 ) \beta=(0.9,0.98) , weight decay 0.1 0.1 , learning rate 0.0003 0.0003 , and batch size 96 96 . We pre-train the model for 100k iterations, with a linear learning rate decay. 17 17 17 We have slightly tuned the parameters to make pre-training go best. We noticed for training GPTs over our CFG data, a warmup learning rate schedule is not needed. For DeBERTa, we use learning rate 0.0001 0.0001 which is better and 2000 2000 steps of learning rate linear warmup.

Throughout the experiments, for both pre-training and testing, we only use fresh samples from the CFG datasets (thus using 4.9 4.9 billion tokens = 96 × 512 × 100 ​ k 96\times 512\times 100k ). We have also tested pre-training with a finite training set of 100 ​ m 100m tokens; and the conclusions of this paper stay similar. To make this paper clean, we choose to stick to the infinite-data regime in this version of the paper, because it enables us to make negative statements (for instance about the vanilla GPT or DeBERTa, or about the learnability of NT ancestors / NT boundaries) without worrying about the sample size. Please note, given that our CFG language is very large (e.g., length 300 tree of length-2/3 rules and degree 4 would have at least 4 300 / 3 4^{300/3} possibility), there is almost no chance that training/testing hit the same sentence .

As for the reproducibility of our result, we did not run each pre-train experiment more than once (or plot any confidence interval). This is because, rather than repeating our experiments identically, it is obviously more interesting to use the resources to run it against different datasets and against different parameters. We pick the best model using the perplexity score from each pre-training task. When evaluating the generation accuracy in Figure 4 , we have generated more than 20000 samples for each case, and present the diversity pattern accordingly in Figure 14 .

We test our results using a mixture of V100 and A100 GPUs (on A100, pretraining a model takes less than a day using 4GPUs), even when using float32.

### A.4 Predict NT ancestor and NT boundary

Recall from Section 4.1 that we have proposed to use a multi-head linear function to probe whether or not the hidden states of a transformer, implicitly encodes the NT ancestor and NT boundary information for each token position. Since this linear function can be of dimension 512 × 768 512\times 768 — when having a context length 512 and hidden dimension 768 — recall in ( 4.2 ) , we have proposed to use a multi-head attention to construct such linear function for efficient learning purpose. This significantly reduces sample complexity and makes it much easier to find the linear function.

In our implementation, we choose H = 16 H=16 heads and hidden dimension d ′ = 1024 d^{\prime}=1024 when constructing this position-based attention in ( 4.2 ) . We have also tried other parameters but the NT ancestor/boundary prediction accuracies are not very sensitive to such architecture change. We again use AdamW with β = ( 0.9 , 0.98 ) \beta=(0.9,0.98) but this time with learning rate 0.003 0.003 , weight decay 0.001 0.001 , batch size 60 60 and train for 30k iterations.

Once again we use fresh new samples when training such linear functions. When evaluating the accuracies on predicting the NT ancester / boundary information, we also use fresh new samples. Recall our CFG language is sufficiently large so there is negligible chance that the model has seen such a string during training.

## Appendix B More Experiments on Results 2-3 (Generation)

Diversity can be estimated through entropy. Given a distribution p p over strings and a sampled subset S = { x ( i ) } i ∈ [ M ] S=\big\{x^{(i)}\big\}_{i\in[M]} from p p , for any string x ∈ S x\in S , denote by len ​ ( x ) \textbf{len}(x) its length so x = ( x 1 , … , x len ​ ( x ) ) x=(x_{1},\dots,x_{\textbf{len}(x)}) , and denote by x len ​ ( x ) + 1 = 𝖾𝗈𝗌 x_{\textbf{len}(x)+1}=\mathsf{eos} . The entropy in bits for p p can be estimated by − 1 | S | ∑ x ∈ S ∑ i ∈ [ len ​ ( x ) + 1 ] log 2 𝐏𝐫 p [ x i ∣ x 1 , … , x i − 1 ] \textstyle-\frac{1}{|S|}\sum_{x\in S}\sum_{i\in[\textbf{len}(x)+1]}\log_{2}\operatornamewithlimits{\mathbf{Pr}}_{p}\big[x_{i}\mid x_{1},\dots,x_{i-1}\big] We compare the entropy of the true CFG distribution and the transformer’s output distribution using M = 20000 M=20000 samples in Figure 4 (middle).

Diversity can also be estimated using the birthday paradox to lower bound the support size of a distribution [ 7 ] . Given a distribution p p over strings and a sampled subset S = { x ( i ) } i ∈ [ M ] S=\big\{x^{(i)}\big\}_{i\in[M]} from p p , if every pair of samples in S S are distinct, then with good probability the support of p p is of size at least Ω ⁡ ( M 2 ) \Omega(M^{2}) . In Appendix B.1 , we conducted an experiment with M = 20000 M=20000 . We performed a birthday paradox experiment from every symbol a ∈ 𝐍𝐓 ℓ 1 a\in\mathbf{NT}_{\ell_{1}} to some other level ℓ 2 > ℓ 1 \ell_{2}>\ell_{1} , comparing that with the ground truth. For instance, we confirmed for the 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} dataset, there are at least Ω ⁡ ( M 2 ) \Omega(M^{2}) distinct sentential forms that can be derived from a symbol in level 1 to level 5, or from level 2 to level 6, etc. — not to mention from the root in 𝐍𝐓 1 \mathbf{NT}_{1} to the leaf at level 7 7 . In particular, M 2 M^{2} is already more than the number of parameters in the model.

From both experiments, we conclude that the pre-trained model does not rely on simply memorizing a small set of patterns to learn the CFGs.

### B.1 Generation Diversity via Birthday Paradox

Since “diversity” is influenced by the length of the input prefix, the length of the output, and the CFG rules, we want to carefully define what we measure.

Given a sample pool x ( 1 ) , … , x ( M ) ∈ L ⁡ ( 𝒢 ) x^{(1)},...,x^{(M)}\in L(\mathcal{G}) , for every symbol a ∈ 𝐍𝐓 ℓ 1 a\in\mathbf{NT}_{\ell_{1}} and some later level ℓ 2 ≥ ℓ 1 \ell_{2}\geq\ell_{1} that is closer to the leaves, we wish to define a multi-set 𝒮 a → ℓ 2 \mathcal{S}_{a\to\ell_{2}} that describes all possible generations from a ∈ 𝐍𝐓 ℓ 1 a\in\mathbf{NT}_{\ell_{1}} to 𝐍𝐓 ℓ 2 \mathbf{NT}_{\ell_{2}} in this sample pool. Formally,

###### Definition B.1 .

For x ∈ L ⁡ ( 𝒢 ) x\in L(\mathcal{G}) and ℓ ∈ [ L ] \ell\in[L] , we use 𝔰 ℓ ( i . . j ) \mathfrak{s}_{\ell}(i..j) to denote the sequence of NT ancestor symbols at level ℓ ∈ [ L ] \ell\in[L] from position i i to j j with distinct ancestor indices: 18 18 18 With the understanding that 𝔭 ℓ ​ ( 0 ) = 𝔭 ℓ ​ ( len ​ ( x ) + 1 ) = ∞ \mathfrak{p}_{\ell}(0)=\mathfrak{p}_{\ell}(\textbf{len}(x)+1)=\infty . 𝔰 ℓ ( i . . j ) = ( 𝔰 ℓ ( k ) ) k ∈ { i , i + 1 , … , j } ​ s.t. ​ 𝔭 ℓ ​ ( k ) ≠ 𝔭 ℓ ​ ( k + 1 ) \mathfrak{s}_{\ell}(i..j)=\left(\mathfrak{s}_{\ell}(k)\right)_{k\in\{i,i+1,\dots,j\}\text{ s.t. }\mathfrak{p}_{\ell}(k)\neq\mathfrak{p}_{\ell}(k+1)}

###### Definition B.2 .

For symbol a ∈ 𝐍𝐓 ℓ 1 a\in\mathbf{NT}_{\ell_{1}} and some layer ℓ 2 ∈ { ℓ 1 , ℓ 1 + 1 , … , L } \ell_{2}\in\{\ell_{1},\ell_{1}+1,\dots,L\} , define multi-set 19 19 19 Throughout this paper, we use ⟦ ⋅ ⟧ \llbracket\cdot\rrbracket to denote multi-sets that allow multiplicity, such as ⟦ 1 , 2 , 2 , 3 ⟧ \llbracket 1,2,2,3\rrbracket . This allows us to conveniently talk about its collision count, number of distinct elements, and set average. 𝒮 a → ℓ 2 ( x ) = ⟦ 𝔰 ℓ 2 ( i . . j ) | ∀ i , j , i ≤ j such that 𝔭 ℓ 1 ( i − 1 ) ≠ 𝔭 ℓ 1 ( i ) = 𝔭 ℓ 1 ( j ) ≠ 𝔭 ℓ 1 ( j + 1 ) ∧ a = 𝔰 ℓ 1 ( i ) ⟧ \displaystyle\mathcal{S}_{a\to\ell_{2}}(x)=\bigg\llbracket\mathfrak{s}_{\ell_{2}}(i..j)\,\Big|\,\forall i,j,i\leq j\text{ such that }\mathfrak{p}_{\ell_{1}}(i-1)\neq\mathfrak{p}_{\ell_{1}}(i)=\mathfrak{p}_{\ell_{1}}(j)\neq\mathfrak{p}_{\ell_{1}}(j+1)\wedge a=\mathfrak{s}_{\ell_{1}}(i)\bigg\rrbracket and we define the multi-set union 𝒮 a → ℓ 2 = ⋃ i ∈ [ M ] 𝒮 a → ℓ 2 ​ ( x ( i ) ) \mathcal{S}_{a\to\ell_{2}}=\bigcup_{i\in[M]}\mathcal{S}_{a\to\ell_{2}}\big(x^{(i)}\big) , which is the multiset of all sentential forms that can be derived from NT symbol a a to depth ℓ 2 \ell_{2} .

(Above, when x ∼ L ⁡ ( 𝒢 ) x\sim L(\mathcal{G}) is generated from the ground-truth CFG, then the ancestor indices and symbols 𝔭 , 𝔰 \mathfrak{p},\mathfrak{s} are defined in Section 2.1 . If x ∈ L ⁡ ( 𝒢 ) x\in L(\mathcal{G}) is an output from the transformer F F , then we let 𝔭 , 𝔰 \mathfrak{p},\mathfrak{s} be computed using dynamic programming, breaking ties lexicographically.)

We use 𝒮 a → ℓ 2 𝗍𝗋𝗎𝗍𝗁 \mathcal{S}_{a\to\ell_{2}}^{{\mathsf{truth}}} to denote the ground truth 𝒮 a → ℓ 2 \mathcal{S}_{a\to\ell_{2}} when x ( 1 ) , … , x ( M ) x^{(1)},\dots,x^{(M)} are i.i.d. sampled from the real distribution L ⁡ ( 𝒢 ) L(\mathcal{G}) , and denote by 𝒮 a → ℓ 2 F = ⋃ i ∈ [ M ′ ] and x ( i ) : c , F ( x ( i ) : c ) ∈ L ( 𝒢 ) 𝒮 a → ℓ 2 ( x : c ( i ) , F ( x : c ( i ) ) ) \displaystyle\textstyle\mathcal{S}^{F}_{a\to\ell_{2}}=\bigcup_{i\in[M^{\prime}]\text{ and }x^{(i)}_{:c},F(x^{(i)}_{:c})\in L(\mathcal{G})}\mathcal{S}_{a\to\ell_{2}}\big(x^{(i)}_{:c},F(x^{(i)}_{:c})\big) that from the transformer F F . For a fair comparison, for each F F and p p , we pick an M ′ ≥ M M^{\prime}\geq M such that M = | { i ∈ [ M ′ ] ∣ x : p ( i ) , F ( x : p ( i ) ) ∈ L ( 𝒢 ) } | M=\big|\big\{i\in[M^{\prime}]\mid x_{:p}^{(i)},F(x^{(i)}_{:p})\in L(\mathcal{G})\big\}\big| so that F F is capable of generating exactly M M sentences that nearly-perfectly satisfy the CFG rules. 20 20 20 Please note M M and M ′ M^{\prime} are roughly the same, given

Intuitively, for x x ’s generated by the transformer model, the larger the number of distinct sequences in 𝒮 a → ℓ 2 F \mathcal{S}^{F}_{a\to\ell_{2}} is, the more diverse the set of NTs at level ℓ 2 \ell_{2} (or Ts if ℓ 2 = L \ell_{2}=L ) the model can generate starting from NT a a . Moreover, in the event that 𝒮 a → ℓ 2 F \mathcal{S}^{F}_{a\to\ell_{2}} has only distinct sequences (so collision count = 0), then we know that the generation from a → ℓ 2 a\to\ell_{2} , with good probability, should include at least Ω ⁡ ( M 2 ) \Omega(M^{2}) possibilities using a birthday paradox argument. 21 21 21 A CFG of depth L L , even with constant degree and constant size, can generate 2 2 Ω ⁡ ( L ) 2^{2^{\Omega(L)}} distinct sequences.

For such reason, it can be beneficial if we compare the number of distinct sequences and the collision counts between 𝒮 a → ℓ 2 F \mathcal{S}^{F}_{a\to\ell_{2}} and 𝒮 a → ℓ 2 𝗍𝗋𝗎𝗍𝗁 \mathcal{S}^{\mathsf{truth}}_{a\to\ell_{2}} . Note we consider all ℓ 2 ≥ ℓ 1 \ell_{2}\geq\ell_{1} instead of only ℓ 2 = L \ell_{2}=L , because we want to better capture model’s diversity at all CFG levels. 22 22 22 A model might generate a same NT symbol sequence s L − 1 s_{L-1} , and then generate different Ts randomly from each NT. In this way, the model still generates strings x x ’s with large diversity, but 𝒮 a → L − 1 F ​ ( x ) \mathcal{S}^{F}_{a\to L-1}(x) is small. If 𝒮 a → ℓ 2 F \mathcal{S}^{F}_{a\to\ell_{2}} is large for every ℓ 2 \ell_{2} and a a , then the generation from the model is truely diverse at any level of the CFG. We present our findings in Figure 14 with M = 20000 M=20000 samples for the 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} dataset.

In Figure 15 we present that for 𝖼𝖿𝗀𝟥𝖻 , 𝖼𝖿𝗀𝟥𝗂 , 𝖼𝖿𝗀𝟥𝗁 , 𝖼𝖿𝗀𝟥𝗀 \mathsf{cfg3b},\mathsf{cfg3i},\mathsf{cfg3h},\mathsf{cfg3g} , in Figure 16 for 𝖼𝖿𝗀𝟥𝖾𝟣 \mathsf{cfg3e1} , and in Figure 17 for 𝖼𝖿𝗀𝟥𝖾𝟤 \mathsf{cfg3e2} . We note that not only for hard, ambiguous datasets, also for those less ambiguous ( 𝖼𝖿𝗀𝟥𝖾𝟣 , 𝖼𝖿𝗀𝟥𝖾𝟤 \mathsf{cfg3e1},\mathsf{cfg3e2} ) datasets, language models are capable of generating very diverse outputs.

### B.2 Marginal Distribution Comparison

In order to effectively learn a CFG, it is also important to match the distribution of generating probabilities. While measuring this can be challenging, we have conducted at least a simple test on the marginal distributions p ⁡ ( a , i ) p(a,i) , which represent the probability of symbol a ∈ 𝐍𝐓 ℓ a\in\mathbf{NT}_{\ell} appearing at position i i (i.e., the probability that 𝔰 ℓ ​ ( i ) = a \mathfrak{s}_{\ell}(i)=a ). We observe a strong alignment between the generated probabilities and the ground-truth distribution. See Figure 18 .

## Appendix C More Experiments on Results 4-5 (NT Ancestor and Boundary Probing)

### C.1 NT Ancestor and NT Boundary Probing

Earlier, as confirmed in Figure 5 , we established that the hidden states (of the final transformer layer) have implicitly encoded the NT ancestor symbols 𝔰 ℓ ​ ( i ) \mathfrak{s}_{\ell}(i) for each CFG level ℓ \ell and token position i i using a linear transformation. In Figure 19(a) in this section, we also demonstrate that the same conclusion applies to the NT-end boundary 𝔟 ℓ ​ ( i ) \mathfrak{b}_{\ell}(i) . This completes Result 4 .

More importantly, for 𝔟 ℓ ​ ( i ) \mathfrak{b}_{\ell}(i) , we also show that this information is stored locally , very close to position i i (such as at i ± 1 i\pm 1 ). Details can be found in Figure 19 . In particular, note as shown in Figure 7 , we confirmed that at any NT boundary position i i where 𝔟 ℓ ​ ( i ) = 1 \mathfrak{b}_{\ell}(i)=1 , the transformer has also locally encoded clear information about the NT ancestor symbol 𝔰 ℓ ​ ( i ) \mathfrak{s}_{\ell}(i) , either exactly at i i or at i ± 1 i\pm 1 . To be precise, this is a conditional statement — given that it is an NT boundary, NT ancestors can be predicted. Therefore, in principle, one must also verify that the prediction task for the NT boundary is successful to begin with. Such missing experiments are, in fact, included in Figure 19(b) and Figure 19(c) .

### C.2 NT Probing Across Transformer’s Layers

As one may image, the NT ancestor and boundary information for smaller CFG levels ℓ \ell (i.e., closer to CFG root) are only learned at those deeper transformer layers l l . In Figure 20 , we present this finding by calculating the linear encoding accuracies with respect to all the 12 transformer layers in 𝙶𝙿𝚃 \mathtt{GPT} and 𝙶𝙿𝚃 𝗋𝖾𝗅 \mathtt{GPT}_{\mathsf{rel}} . We confirm that generative models discover such information hierarchically .

### C.3 NT Predictions Across Training Epochs

Moreover, one may conjecture that the NT ancestor and NT boundary information is learned gradually as the number of training steps increase. We have confirmed this in Figure 21 . We emphasize that this does not imply layer-wise training is applicable in learning deep CFGs. It is crucial to train all the layers together, as the training process of deeper transformer layers may help backward correct the features learned in the lower layers, through a process called “backward feature correction” [ 2 ] .

## Appendix D More Experiments on Results 6-9 (Attention Patterns)

### D.1 Result 6: Position-Based Attention Pattern

Recall from Figure 8 we have shown that the attention weights between any two positions j → i j\to i have a strong bias in the relative difference p = | j − i | p=|j-i| . Different heads or layers have different dependencies on p p . Below in Figure 22 , we give experiments for this phenomenon in more datasets and for both 𝙶𝙿𝚃 / 𝙶𝙿𝚃 𝗋𝖾𝗅 \mathtt{GPT}/\mathtt{GPT}_{\mathsf{rel}} .

### D.2 Result 7: From Anywhere to NT-ends

Recall from Figure 9(a) , we showed that after removing the position-bias B l , h , j → i ​ ( x ) = def A l , h , j → i ​ ( x ) − A ¯ l , h , j − i B_{l,h,j\to i}(x)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}A_{l,h,j\to i}(x)-\overline{A}_{l,h,j-i} , the attention weights have a very strong bias towards tokens i i that are at NT ends . In Figure 23 we complement this experiment with more datasets.

### D.3 Result 8: From NT-ends to NT-ends

As mentioned in Section 5.2 and Figure 9(b) , not only do tokens generally attend more to NT-ends, but among those attentions, NT-ends are also more likely to attend to NT-ends. We include this full experiment in Figure 24 for every different level ℓ = 2 , 3 , 4 , 5 \ell=2,3,4,5 , between any two pairs j → i j\to i that are both at NT-ends for level ℓ \ell , for the 𝖼𝖿𝗀𝟥 \mathsf{cfg3} datasets.

### D.4 Result 9: From NT-ends to Adjacent NT-ends

In Figure 9(c) we have showcased that B l , h , j → i ​ ( x ) B_{l,h,j\to i}(x) has a strong bias towards token pairs i , j i,j that are “adjacent” NT-ends . We have defined what “adjacency” means in Section 5.2 and introduced a notion B l , h , ℓ ′ → ℓ , r end → end B^{\text{end }\to\text{end }}_{l,h,\ell^{\prime}\to\ell,r} , to capture B l , h , j → i ​ ( x ) B_{l,h,j\to i}(x) averaged over samples x x and all token pairs i , j i,j such that, they are at deepest NT-ends on levels ℓ , ℓ ′ \ell,\ell^{\prime} respectively (in symbols, 𝔟 ♯ ​ ( i ) = ℓ ∧ 𝔟 ♯ ​ ( j ) = ℓ ′ \mathfrak{b}^{\sharp}(i)=\ell\wedge\mathfrak{b}^{\sharp}(j)=\ell^{\prime} ), and of distance r r based on the ancestor indices at level ℓ \ell (in symbols, 𝔭 ℓ ​ ( j ) − 𝔭 ℓ ​ ( i ) = r \mathfrak{p}_{\ell}(j)-\mathfrak{p}_{\ell}(i)=r ).

Previously, we have only presented by Figure 9(c) for a single dataset, and averaged over all the transformer layers. In the full experiment Figure 25 we show that for more datasets, and Figure 26 we show that for individual layers.

## Appendix E More Experiments on Result 10 (Implicit CFGs)

We study implicit CFGs where each terminal symbol t ∈ 𝐓 t\in\mathbf{T} is is associated a bag of observable tokens 𝐎𝐓 t \mathbf{OT}_{t} . For this task, we study eight different variants of implicit CFGs, all converted from the exact same 𝖼𝖿𝗀𝟥𝗂 \mathsf{cfg3i} dataset (see Section A.1 ). Recall 𝖼𝖿𝗀𝟥𝗂 \mathsf{cfg3i} has three terminal symbols | 𝐓 | = 3 |\mathbf{T}|=3 : • we consider a vocabulary size | 𝐎𝐓 | = 90 |\mathbf{OT}|=90 or | 𝐎𝐓 | = 300 |\mathbf{OT}|=300 ;

• we let { 𝐎𝐓 t } t ∈ 𝐓 \{\mathbf{OT}_{t}\}_{t\in\mathbf{T}} be either disjoint or overlapping; and

• we let the distribution over 𝐎𝐓 t \mathbf{OT}_{t} be either uniform or non-uniform.

We present the generation accuracies of learning such implicit CFGs with respect to different model architectures in Figure 27 , where in each cell we evaluate accuracy using 2000 generation samples. We also present the correlation matrix of the word embedding layer in Figure 11 for the 𝙶𝙿𝚃 𝗋𝖾𝗅 \mathtt{GPT}_{\mathsf{rel}} model (the correlation will be similar if we use other models).

## Appendix F More Experiments on Results 11-13 (Robustness)

Recall that in Figure 12 , we have compared clean training vs training over three types of perturbed data, for their generation accuracies given both clean prefixes and corrupted prefixes. We now include more experiments with respect to more datasets in Figure 28 . For each entry of the figure, we have generated 2000 samples to evaluate the generation accuracy.

## Appendix G Beyond the CFG3 Data Family

The primary focus of this paper is on the 𝖼𝖿𝗀𝟥 \mathsf{cfg3} data family, introduced in Section A.1 . This paper does not delve into how GPTs parse English or other natural languages. In fact, our CFGs are more “difficult” than, for instance, the English CFGs derived from the Penn TreeBank (PTB) [ 19 ] . By “difficult”, we refer to the ease with which a human can parse them. For example, in the PTB CFG, if one encounters RB JJ or JJ PP consecutively, their parent must be ADJP . In contrast, given a string 3322131233121131232113223123121112132113223113113223331231211121311331121321213333312322121312322211112133221311311311 3111111323123313313331133133333223121131112122111121123331233112111331333333112333313111133331211321131212113333321211 1121213223223322133221113221132323313111213223223221211133331121322221332211212133121331332212213221211213331232233312 that is in 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} , even with all the CFG rules provided, one would likely need a large piece of scratch paper to perform dynamic programming by hand to determine the CFG tree used to generate it.

Generally, the difficulty of CFGs scales with the average length of the strings. For instance, the average length of a CFG in our 𝖼𝖿𝗀𝟥 \mathsf{cfg3} family is over 200, whereas in the English Penn Treebank (PTB), it is only 28. However, the difficulty of CFGs may inversely scale with the number of Non-Terminal/Terminal (NT/T) symbols. Having an excess of NT/T symbols can simplify the parsing of the string using a greedy approach (recall the RB JJ or JJ PP examples mentioned earlier). This is why we minimized the number of NT/T symbols per level in our 𝖼𝖿𝗀𝟥𝖻 , 𝖼𝖿𝗀𝟥𝗂 , 𝖼𝖿𝗀𝟥𝗁 , 𝖼𝖿𝗀𝟥𝗀 , 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3b},\mathsf{cfg3i},\mathsf{cfg3h},\mathsf{cfg3g},\mathsf{cfg3f} construction. For comparison, we also considered 𝖼𝖿𝗀𝟥𝖾𝟣 , 𝖼𝖿𝗀𝟥𝖾𝟤 \mathsf{cfg3e1},\mathsf{cfg3e2} , which have many NT/T symbols per level. Figure 4 shows that such CFGs are extremely easy to learn.

To broaden the scope of this paper, we also briefly present results for some other CFGs. We include the real-life CFG derived from the Penn Treebank, and three new families of synthetic CFGs ( 𝖼𝖿𝗀𝟪 , 𝖼𝖿𝗀𝟫 , 𝖼𝖿𝗀𝟢 \mathsf{cfg8},\mathsf{cfg9},\mathsf{cfg0} ). Examples from these are provided in Figure 29 to allow readers to quickly compare their difficulty levels.

### G.1 The Penn TreeBank CFG

We derive the English CFG from the Penn TreeBank (PTB) dataset [ 19 ] . To make our experiment run faster, we have removed all the CFG rules that have appeared fewer than 50 times in the data. 23 23 23 These are a large set of rare rules, each appearing with a probability ≤ 0.2 % \leq 0.2\% . We are evaluating whether the generated sentence belongs to the CFG, a process that requires CPU-intensive dynamic programming. To make the computation time tractable, we remove the set of rare rules. Note that 𝖼𝖿𝗀𝟥 \mathsf{cfg3} does not contain rare rules either. Including such rules complicates the CFG learning process, necessitating a larger transformer and extended training time. It also complicates the investigation of a transformer’s inner workings if these rare rules are not perfectly learned. This results in 44 T+NT symbols and 156 CFG rules. The maximum node degree is 65 (for the non-terminal NP ) and the maximum CFG rule length is 7 (for S -> ‘‘ S , ’’ NP VP . ). If one performs binarization (to ensure all the CFG rules have a maximum length of 2), this results in 132 T+NT symbols and 288 rules.

###### Remark G.1 .

Following the notion of this paper, we treat those symbols such as NNS (common noun, plural), NN (common noun, singular) as terminal symbols . If one wishes to also take into consideration the bag of words (such as the word vocabulary of plural nouns), we have called it implicit CFG and studied it in Section 6.1 . In short, adding bag of words does not increase the learning difficult of a CFG; the (possibly overlapping) vocabulary words will be simply encoded in the embedding layer of a transformer.

For this PTB CFG, we also consider transformers of sizes smaller than GPT2-small. Recall GPT2-small has 12 layers, 12 heads, and 64 dimensions for each head. More generally, we let GPT- ℓ \ell - h h - d d denote an ℓ \ell -layer, h h -head, d d -dim-per-head 𝙶𝙿𝚃 𝗋𝗈𝗍 \mathtt{GPT}_{\mathsf{rot}} (so GPT2-small can be written as GPT-12-12-64).

We use transformers of different sizes to pretrain on this PTB CFG. We repeat the experiments in Figure 4 (with the same pretrain parameters described in Appendix A.3 ), that is, we compute the generation accuracy, completion accuracy (with cut c = 10 c=10 ), the output entropy and the KL-divergence. We report the findings in Figure 30 . In particular:

• Even a 135K-sized GPT2 (GPT-2-4-16) can achieve generation accuracy ∼ \sim 95% and have a KL divergence less than 0.01. (Note the PTB CFG has 30 terminal symbols so its KL divergence may appear larger than that of 𝖼𝖿𝗀𝟥 \mathsf{cfg3} in Figure 4 .)

• Even a 1.3M-sized GPT2 (GPT-6-4-32) can achieve generation accuracy 99% and have a KL divergence on the order of 0.001.

• Using M = 10000 M=10000 samples, we estimate the entropy of the ground truth PTB CFG is around 60 60 bits, and the output entropy of those learned transformer models are also on this magnitude.

• By contrast, those small model sizes cannot learn the 𝖼𝖿𝗀𝟥𝖿 \mathsf{cfg3f} data, see Figure 31 .

### G.2 More Synthetic CFGs

Remember that the 𝖼𝖿𝗀𝟥 \mathsf{cfg3} family appears “balanced” because all leaves are at the same depth and the non-terminal (NT) symbols at different levels are disjoint. This characteristic aids our investigation into the inner workings of a transformer learning such a language. We introduce three new synthetic data families, which we refer to as 𝖼𝖿𝗀𝟪 / 𝟫 / 𝟢 \mathsf{cfg8/9/0} (each with five datasets, totaling 15 datasets). These are all ‘‘unbalanced’’ CFGs, which support length-1 rules. 24 24 24 When a length-1 CFG rule is applied, we can merge the two nodes at different levels, resulting in an “unbalanced” CFG. Specifically, the 𝖼𝖿𝗀𝟢 \mathsf{cfg0} family has a depth of 11 with rules of length 1 or 2, while the 𝖼𝖿𝗀𝟪 / 𝟫 \mathsf{cfg8/9} family has depth 7 7 with rules of length 1/2/3. In all of these families, we demonstrate in Figure 32 that GPT can learn them with a satisfactory level of accuracy.

We have included all the CFG trees used in this paper to this embedded file: cfgs.txt . It can be opened using Adobe Reader. Below, we provide descriptions of how we selected them.

CFG8 family. The 𝖼𝖿𝗀𝟪 \mathsf{cfg8} family consists of five CFGs, namely 𝖼𝖿𝗀𝟪𝖺 / 𝖻 / 𝖼 / 𝖽 / 𝖾 \mathsf{cfg8a/b/c/d/e} . They are constructed similarly to 𝖼𝖿𝗀𝟥𝖻 / 𝗂 / 𝗁 / 𝗀 / 𝖿 \mathsf{cfg3b/i/h/g/f} , with the primary difference being that we sample rule lengths uniformly from { 1 , 2 , 3 } \{1,2,3\} instead of { 2 , 3 } \{2,3\} . Additionally, • In 𝖼𝖿𝗀𝟪𝖺 \mathsf{cfg8a} , we set the degree | ℛ ⁡ ( a ) | = 2 |\mathcal{R}(a)|=2 for every NT a a ; we also ensure that in any generation rule, consecutive pairs of terminal/non-terminal symbols are distinct. The size is ( 1 , 3 , 3 , 3 , 3 , 3 , 3 ) (1,3,3,3,3,3,3) .

• In 𝖼𝖿𝗀𝟪𝖻 \mathsf{cfg8b} , we set | ℛ ⁡ ( a ) | = 2 |\mathcal{R}(a)|=2 for every NT a a ; we remove the distinctness requirement to make the data more challenging than 𝖼𝖿𝗀𝟪𝖺 \mathsf{cfg8a} . The size is ( 1 , 3 , 3 , 3 , 3 , 3 , 3 ) (1,3,3,3,3,3,3) .

• In 𝖼𝖿𝗀𝟪𝖼 \mathsf{cfg8c} , we set | ℛ ⁡ ( a ) | ∈ { 2 , 3 } |\mathcal{R}(a)|\in\{2,3\} for every NT a a to make the data more challenging than 𝖼𝖿𝗀𝟪𝖻 \mathsf{cfg8b} . The size is ( 1 , 3 , 3 , 3 , 3 , 3 , 3 ) (1,3,3,3,3,3,3) .

• In 𝖼𝖿𝗀𝟪𝖽 \mathsf{cfg8d} , we set | ℛ ⁡ ( a ) | = 3 |\mathcal{R}(a)|=3 for every NT a a . We change the size to ( 1 , 3 , 3 , 3 , 3 , 3 , 4 ) (1,3,3,3,3,3,4) because otherwise a random string would be too close (in editing distance) to this language.

• In 𝖼𝖿𝗀𝟪𝖾 \mathsf{cfg8e} , we set | ℛ ⁡ ( a ) | ∈ { 3 , 4 } |\mathcal{R}(a)|\in\{3,4\} for every NT a a . We change the size to ( 1 , 3 , 3 , 3 , 3 , 3 , 4 ) (1,3,3,3,3,3,4) because otherwise a random string would be too close to this language.

A notable feature of this data family is that, due to the introduction of length-1 rules, a string in this language L ⁡ ( 𝒢 ) L(\mathcal{G}) may be globally ambiguous . This means that there can be multiple ways to parse it by the same CFG, resulting in multiple solutions for its NT ancestor/boundary information for most symbols . Therefore, it is not meaningful to perform linear probing on this dataset, as the per-symbol NT information is mostly non-unique. 25 25 25 In contrast, the 𝖼𝖿𝗀𝟥 \mathsf{cfg3} data family is only locally ambiguous, meaning that it is difficult to determine its hidden NT information by locally examining a substring; however, when looking at the entire string as a whole, the NT information per symbol can be uniquely determined with a high probability (if using for instance dynamic programming).

CFG9 family. Given the ambiguity issues arising from the 𝖼𝖿𝗀𝟪 \mathsf{cfg8} data construction, our goal is to construct an unbalanced and yet challenging CFG data family where the non-terminal (NT) information is mostly unique, thereby enabling linear probing.

To accomplish this, we first adjust the size to ( 1 , 4 , 4 , 4 , 4 , 4 , 4 ) (1,4,4,4,4,4,4) , then we permit only one NT per layer to have a rule of length 1. We construct five CFGs, denoted as 𝖼𝖿𝗀𝟫𝖺 / 𝖻 / 𝖼 / 𝖽 / 𝖾 \mathsf{cfg9a/b/c/d/e} , and their degree configurations (i.e., ℛ ⁡ ( a ) \mathcal{R}(a) ) are identical to those of the 𝖼𝖿𝗀𝟪 \mathsf{cfg8} family. We then employ rejection sampling by generating a few strings from these CFGs and checking if the dynamic programming (DP) solution is unique. If it is not, we continue to generate a new CFG until this condition is met.

Examples from 𝖼𝖿𝗀𝟫𝖾 \mathsf{cfg9e} are illustrated in Figure 29 . We will conduct linear probing experiments on this data family.

CFG0 family. Since all the CFGs above support rules of length 3, we have focused on L = 7 L=7 to prevent the string length from becoming excessively long. 26 26 26 Naturally, a larger transformer would be capable of solving such CFG learning tasks when the string length exceeds 1000 1000 ; we have briefly tested this and found it to be true. However, conducting comprehensive experiments of this length would be prohibitively expensive, so we have not included them in this paper. In the 𝖼𝖿𝗀𝟢 \mathsf{cfg0} family, we construct five CFGs, denoted as 𝖼𝖿𝗀𝟢𝖺 / 𝖻 / 𝖼 / 𝖽 / 𝖾 \mathsf{cfg0a/b/c/d/e} . All of them have a depth of L = 11 L=11 . Their rule lengths are randomly selected from { 1 , 2 } \{1,2\} (compared to { 2 , 3 } \{2,3\} for 𝖼𝖿𝗀𝟥 \mathsf{cfg3} or { 1 , 2 , 3 } \{1,2,3\} for 𝖼𝖿𝗀𝟪 / 𝟫 \mathsf{cfg8/9} ). Their degree configurations (i.e., ℛ ⁡ ( a ) \mathcal{R}(a) ) are identical to those of the 𝖼𝖿𝗀𝟪 \mathsf{cfg8} family. We have chosen their sizes as follows, noting that we have enlarged the sizes as otherwise a random string would be too close to this language: • We use size [ 1 , 2 , 3 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 ] [1,2,3,4,4,4,4,4,4,4,4] for 𝖼𝖿𝗀𝟢𝖺 / 𝖻 \mathsf{cfg0a/b} .

• We use size [ 1 , 2 , 3 , 4 , 5 , 6 , 6 , 6 , 6 , 6 , 6 ] [1,2,3,4,5,6,6,6,6,6,6] for 𝖼𝖿𝗀𝟢𝖼 \mathsf{cfg0c} .

• We use size [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 ] [1,2,3,4,5,6,7,8,9,10,11] for 𝖼𝖿𝗀𝟢𝖽 / 𝖾 \mathsf{cfg0d/e} .

Once again, the CFGs generated in this manner are globally ambiguous like the 𝖼𝖿𝗀𝟪 \mathsf{cfg8} family, so we cannot perform linear probing on them. However, it would be interesting to demonstrate the ability of transformers to learn such CFGs.

Additional experiments. We present the generation accuracies (or the complete accuracies for cut c = 20 c=20 ) for the three new data families in Figure 32 . It is evident that the 𝖼𝖿𝗀𝟪 / 𝟫 / 𝟢 \mathsf{cfg8/9/0} families can be learned almost perfectly by GPT2-small, especially the relative/rotary embedding ones.

As previously mentioned, the 𝖼𝖿𝗀𝟫 \mathsf{cfg9} data family is not globally ambiguous, making it an excellent synthetic data set for testing the encoding of the NT ancestor/boundary information, similar to what we did in Section 4 . Indeed, we replicated our probing experiments in Figure 33 and Figure 34 for the 𝖼𝖿𝗀𝟫 \mathsf{cfg9} data family. This suggests that our probing technique has broader applicability.

## Appendix H More on Uniform Attention

In Result 1, we observed that 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} (uniform attention) performs surprisingly well—significantly outperforming the original 𝙶𝙿𝚃 \mathtt{GPT} with absolute positional embeddings. Although interpretability is the primary focus of this paper, we briefly highlight the robustness and implications of this result.

Since 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} lacks query and key matrices, its per-layer parameter count is approximately 10 ​ d 2 10d^{2} (for hidden size d d ), compared to 12 ​ d 2 12d^{2} for vanilla 𝙶𝙿𝚃 \mathtt{GPT} . Thus, a parameter-matched comparison would be 𝙶𝙿𝚃 ⁡ ( 12,768 ) \mathtt{GPT}(12,768) (12 heads, 768 dimensions) versus 𝙶𝙿𝚃 𝗎𝗇𝗂 ​ ( 8,840 ) \mathtt{GPT}_{\mathsf{uni}}(8,840) (8 heads, 840 dimensions). For completeness, we also compare with other natural baselines such as 𝙶𝙿𝚃 ⁡ ( 8 , 1024 ) \mathtt{GPT}(8,1024) and 𝙶𝙿𝚃 ⁡ ( 12,936 ) \mathtt{GPT}(12,936) . All experiments are summarized in Figure 35 .

At a high level, we group six 12-layer models by parameter scale: 𝙶𝙿𝚃 ⁡ ( 12,768 ) ≈ 𝙶𝙿𝚃 𝗎𝗇𝗂 ​ ( 8,840 ) ≪ 𝙶𝙿𝚃 𝗎𝗇𝗂 ​ ( 8 , 1024 ) ≈ 𝙶𝙿𝚃 ⁡ ( 12,936 ) ≈ 𝙶𝙿𝚃 ⁡ ( 8,936 ) ≪ 𝙶𝙿𝚃 ⁡ ( 8 , 1024 ) . \mathtt{GPT}(12,768)\approx\mathtt{GPT}_{\mathsf{uni}}(8,840)\ll\mathtt{GPT}_{\mathsf{uni}}(8,1024)\approx\mathtt{GPT}(12,936)\approx\mathtt{GPT}(8,936)\ll\mathtt{GPT}(8,1024)\kern 5.0pt. Yet, across all settings, Figure 35 consistently shows that uniform attention 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} outperforms vanilla 𝙶𝙿𝚃 \mathtt{GPT} — even when the latter has more trainable parameters.

While we do not claim this constitutes a comprehensive architecture benchmark (CFG tasks do not reflect the full spectrum of language abilities), these results reinforce the strength of uniform attention. This connects to prior work such as ALiBi [ 27 ] and especially H-Alibi [ 16 ] , which apply hard attention cutoffs—where each attention head attends only to a fixed-size window. This is structurally similar to our 𝙶𝙿𝚃 𝗎𝗇𝗂 \mathtt{GPT}_{\mathsf{uni}} , where the window size varies per head.

These findings also motivate our follow-up work [ 1 ] , where we incorporate short-window uniform attention as a lightweight architectural component to further improve Transformer performance without increasing parameter count significantly.