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