Physics of Language Models: Part 1, Learning Hierarchical Language Structures β part 4/7
Cleaned-text code points [46911, 62630). Bibliography omitted here; source.md includes it.
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
## 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