Physics of Language Models: Part 1, Learning Hierarchical Language Structures โ€” part 6/7

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

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