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

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

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.