Physics of Language Models: Part 1, Learning Hierarchical Language Structures
Authors: Zeyuan Allen-Zhu
Yuanzhi Li
Venue: Accepted by TMLR ()

Abstract: Transformer-based language models are effective but complex, and understanding their inner workings and reasoning mechanisms remains a significant challenge. Previous research has primarily explored how these models handle simple tasks such as name copying or selection; we extend this line of work by investigating how they 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 long (e.g., hundreds of tokens), locally ambiguous sentences that require dynamic programming to parse. Despite this complexity, we demonstrate that autoregressive language models such as GPT can accurately learn and reason over these CFG-defined hierarchical languages and generate valid continuations. Analyzing model internals in this controlled setting, we reveal that hidden states linearly encode CFG parse structure, and that attention patterns align closely with the information flow of dynamic-programming parsing algorithms.

This paper also presents several corollary findings, including: why absolute positional embeddings are inferior to relative and rotary embeddings; why uniform attention alone is surprisingly effective (motivating our follow-up work on Canon layers); why encoder-only models (e.g., BERT, DeBERTa) struggle with *deep* structural reasoning on CFGs compared to autoregressive models (e.g., GPT); and why injecting structural or syntactic noise into pretraining data markedly improves robustness to corrupted language prompts.

Published in Transactions on Machine Learning Research (12/2025)
Physics of Language Models: Part 1, Learning Hierarchical
Language Structures* *
Zeyuan Allen-Zhu FAIR at Meta
seyxanallenhhu@@mett..cm
Yuanzhi Li
Yuanzhi, Lödkmbruui
Mohamed bin Zayed University of AT
Reviewed on OpenReview: https: // openreview. net/ met/foruue forum? id= mPQKyzkA
Abstract
Transformer-based language models effective but complex, and understanding their in- ner workings and reasoning mechanisms remains significant challenge. Previous research has primarily explored how these models handle simple tasks such as name copying or se- lection; we extend this line of work by investigating how they perform recursive language structure reasoning defined by context-free grammars (CFGs). We introduce family of synthetic CFGs that produce hierarchical rules, capable of generating long (e.g., hundreds of tokens), locally ambiguous sentences that require dynamic programming parse. De- spite this complexity, demonstrate that autoregressive language models such GPT accurately learn and reason over these CFG-defined hicrarchical languages and generate valid continuations. Analyzing model internals in this controlled setting, reveal that hidden states linearly encode CFG parse structure, and that attention patterns align closely with the information flow of dynamic-programming parsing algorithms.
This paper also presents corollary findings, including; why absolute positional embeddings are inferior to relative and rotary embeddings; why uniform attention alone is surprisingly fective (motivating our follow-up work on Canon layers (Allen-Zhu 2025a b)); why encoder- only models (c.g., BERT, DeBERTa) struggle with deep structural reasoning on CFGs com- pared to auloregressive models (e-g., GPT); and why injecting structural syntactic noise into pretraining data markedly improves robustness to corrupted language prompts.
1 Introduction
Transformer-basse language models, like GPT (OpenAI, 2023), are powerful but mysterious: many studies atlempt. 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 (Zhang et al. 2023). Others also demonstrate that transformer store key-value knowledge pairs by storing value in the hidden embedding of keys (see Allen-Zin Zhu and Li (2024) and the references therein).
The seminal work from Anthropic (Elhage et al. 2021 Olsson et al. 2022) focuses on induction heads, which are logic operations on the impul level (such as [ 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 't have a
'The first six papers in the Physics of Lenguage Models series were presented two-hour tutorial at ICML 2024 in Austria (youtu.be/yBL77 be/yBL7.0kgla A 100-min deep dive into Part is available youtu. be/kf. wtw.://ekkkkeeeeee//ee eGgVtDcs Future updates and code releases available via version corresponds V5 of the paper: VI (May 24, 2023); V2 added Appendix G (additional data familics); V3 polished the writing and revised the title; V4 added Appendix H (more unlform-attention results); and V5 added pseudocode and further clarified the connection dynamic programming.
commabatract=625068 and the project page physics allen-zhu.
This TMLR-accepted

---

Published in Transactions on Machine Learning Research (12/2025)
root |-520 21
191-1886113
16|-11515
13
10)-8899
71-221
root 10:00 19 21
19)->1718
181-1131513
13/2221112
10]-0779
7]-322
an example sentence
root 1-22 19
19/->1811
16]->1613
13/-1012211
10|-2799
7|-311
20
20)
141-2012
71-32
53221312332213322222 22221221211111 1222311311
20)-x36-7
171-1151413
14]
8j-3111
$22253122121112211
18
17]-
14|
111-977
B]-12
2211112133222
21/-01812
171-31514
14]-2101213
12|-2707
8--111
SS889223221131112222222
21) 92232
181-1115515
151--2011 11
121
91-121
53112833333111139332222
21/-22617:6
181-1151315
15| 10
12]-889
9/-33
2152222332213222211222
13555222111222212233333335113333 12222222311112222222222 322323221
23)->3638
18/-51315
15|-21030
9/-11
211133331 12113331111322222228 12111111222333311188222222
151-1221211
2121133125723312
Figure 1: An example CFG used in our experiments. It generates long (e-g., length 354 in this example) and amhiguous strings. Determining if string belongs to the CPG language E ((()) typically requires dynamic programming, even when the CFG rules are known.
strong framework for mechanistically understanding" this.
The interpretability in the wild paper (Wang et al., 2022) 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 [
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 / compulation chains?
To isolate and rigorously study how models tackle tasks demanding deep reasoning over hierarchical struc- tures, 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 expressions. Crucially for our study, parsing such CFG-defined languages a form of structured reasoning-ooe ooten necessitates textbook-level, yet quite difficult, dynamic programming (DP)- class of algorithms relevant to complex problen-solving This CFG/DP paradigm provides a framework to probe for DP-like computational mechanisms when language models tackle these structured tasks." ? Gener- ally,
produce highly-strueture
We wish to capture how models reason over long rangrange dependencies via CFG. The simplest example is bracket matching, in ... H.......... ....,,,,, the next symbol X could depend on Y that was hundreds of tokens before. Another example is coding, where goto 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 a greedy algorithm without ambiguity, docs bracket matching once locally seen O... we know the two parentheses must be paired logether. We focus hard CFGs that require global planning via dynamic programming to parse.
Most popular choices of CFGs do not satisfy the two above propertics. Notably, the English CFG (c.g.. derived from Penn TreeBank) has an average length of 28 lokens (too short), and is not very locally ambiguous (e.g., RB or JJ PP imply their parent must be ADJP). As we show in Appendix GJ such CFGs can even be learned using tiny GPT2 models with 100k parameters. Thus, CFG grammars based on 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 We pre-train GPT-
1 Yet, they also said "to the best of our knowledge, (this is) the most detailed attempt at reverse-engineering natural end-to-end behavior in transformer-baseed language model."
"Not say in the theory community, CFGs are also used to model some rich, recursive structure languages, including some logics, grammars, formats, expressions, pattcrus, etc, A benefit of using synthetic data is control the difficulty of the data, so that we can observe how transformers learn to solve tasks different difficulty levels.
2

---

Published in Transactions on Machine Learning Research (12/2025)
transformer CFG/DP parsing
18
18
18
18
18
18
18
18
18
18
18
13
(sampli mi from dipf
13
13
13
13
13
13
13
13
13
13
15
15
15
18 -40 85
12
12
12
1
12
10
10
10
10
-43
+855
2
12 .807
learns boundary-based attention to most adjacent NT boundaries at all levels
6i-011
parsing
B1:12
boundary
Mio121
learns ancestor/boundary info linearly encoded in the hidden states
51-53
NT boundary by =h
NT boundary by dyyb1
NT boundary by byy the =
NT aTancstorrs syel,, 2,+12, 2,413
NT ancestors Sgn0, sy530
NT anccestors A 5,+10, 6,+15, 2
10
10
14
Figure 2: An example string x from G = cfg3f. Though formally defined in SSection 2.T.
hold symhols in color represent NT boundaries which mark the ending positions of the parsed CFG subtrees at various levels f: we denote by bą(1) if is at the NT boundary for level f. The NT ancestor or({) represents the tree node's label level E for symbol 24- The NT ancestor index Pe(3) represents that 2; on the "pe(i)-th" subtree for level E counting from the left.
2 (Radford et al. 2019), 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 perhaps evident from Figure I that even if the CFG tree given, deciding if a string satisfics it may require scratch paper and half an hour for person, not to mention learning the CFG from scratch. However, we demonstrate that GPT can learn these CFGs, and using rotary 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 5, Develop 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 charac- teristic 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 needs to be "concatenated" with another sequence i + 1...j to form a solution to a larger problem on 1...j. See Figure 20 for illustrations.
We also explore implicit CFGs (Post and Bergsma, 2013), 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 (Moradi and Samwald, 2021 Tu et al., 2020) using CFGs, assessing the model's ability to auto-correct errors and generate valid CFGs from 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 riae-life completion models like Llama GPT-3 (davinci003).
While previous works explored synthetic grammars and interpretability (e.g, (Hewitt and Manning, 2019:
3

---

Published in Transactions on Machine Learning Research (12/2025)
Deletang al., 2023)); contribution lies in isolating and quantifying dynamic programming- like compu- tation in generative models via CFGs that require global parsing decisions 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 (T), nonterminal symbols (NT), root symbol (rool E NT), and production rules (R). We represent a CFG as G (T, R), with L(g) denoting the string distribution generated by G.
2.1 Definition and Notations
We focus on L-level CFGs where each level é E [L] corresponds set of symbols NT, with NT, S NT for f < L, NT2 T, and NT; (root). Symbols at different levels are disjoint: NT, Ø for i # j. We consider rules of length 2 or 3, denoted as R = (R1,... RL-1), where each R2 consists of rules in the form:
r= (a or r= (a b, for a NT, and b, AcdeNT+H1
Given non-terminal symbol E NT and any rule r (a + *), we say a For each E NT, its associated set of rules is R(a) Ra r], its degree is [R(a)), and the CFG's size is (NT,), [NT2),|NT2]...... [NT.]...,,NTTT
Generating from CFG. To generate samples x from L()), follow these steps:
Start with the root symbol NT,,
2. For each layer & < L, keep a sequence of symbols 8, = (st,1,".. 8t,me)
3. For the next layer, randomly sample rule E R(sE,s) for each se, with uniform probability! 4 Replace
Sr, with b, c, if r = (st.s + b,c, or with b if (st.a + b, c). Let the resulting sequence be
Se = ($1+1.1. , ..t+1m
4. During generation, when a rule 8t,i + s:+1.;; 81+1,4+1 1 is applied, define the parent par (j) = par (i
def (and similarly if the rule of 81, is of length 3).
5. Define NT ancestor indices p =
and NT ancestor symbols s =
as shown Figure! 2
(J( der
= j pe()) par e+1 (pe+1()) and 5e(1) del
St.pe(i)
The final string is x = 8L = (SL,1, mL. with x; = SL,; and length len(x) = mL- We use (I. p,s) ~ L(g) to represent x with its associated NT ancestor indices and symbols, sampled according to the generation process. We write x ~ Ig()) when p and s are evident from the context.
Definition 2.1. symboo x, in a sample (x. p, ~ I(g) the NT boundary / NT end on level E [T--1] if pe(l) # 1)) or mri= len(x). We denote be(i) del Le, is the NT boundary on level & as the NT-end boundary indicator function. The deepest NT-end of i is see also Figure 2
b² bi) 1i = or 1 if set is empty
The cfg3 synthetic CFG family. We focus seven synthetic CFGs of depth I. 7 detailed in Section A.1 The hard datasets cfg3b, cfg3i, cfg3h, cfg3g, cfg3f have sizes 3, and increasing difficulties cfg3b < cfg3i < cfg3h < cfg3g < cfg3f. The easy datasets cfg3el and cfg3e2 have sizes (1,3,9. 81, 27,27.9) and (1,3, 9, 27, 27, 9, 9,4) respectively. The sequences generated by these CFGs are up to 36 = 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 indeed cfg3el and cfg3e2 are much easier
For simplicity, consider the uniform case, climinating rules with extremely low probability. Such rules complicate the learning the CFG and the investigation of transformer's inner workings (e-g., require larger networks and longer training time). Our results da extend non-uniform cases when the distributions are heavily unbalanced.
4

---

Published in Transactions on Machine Learning Research (12/2025)
(a) real-life English CFG derived from Penn Treebank, short and simple
Ma Malld
(b) a family max-depth CFGs where rules have length or 2 that GPT can learn, see cfg0 Appendix C
Figure 3: CFG visual comparisons: left a medium-length sample, and right is a 80%--percentilllleenghh sample
learn and we discuss more in Appendix GJ. We thus primarily focus on cfg3b, cfg3i, cfg3h, cfg3g, 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 2270 > 1080 strings in cfg3f among total of over 3300 > 10 possible strings of length 300 or more (see our entropy estimation later in Figure 4). The probability of 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 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 100k parameters it too easy for our interpretability purpose.
To obtain clean interpretability result and facilitate clearer analysis of learned representations across pro- cossing levels, we selected a CFG family with '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 demon- strate a strong correlation between the CFG representation and the hidden states in the learned transformer. We also create additional CFG familics to examine 'not-so-canonical" CFG trees, with results deferred Appendix G (an example in Figure 3). We do not claim our results encompass all CFGs; our chosen CPGs 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 (z(1) JEIN from a synthetic CFG language L(g) in Secciin 2.1 and pretrain a (docoder-only) transformer model 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(g).
Models. We denote the GPT2 small architecture (12-layer, 12-head, 768-dimensions) as GPT (Radford et al.) 2019) and implemented its two modern variants. We denote GPT with relative positional attention (He et al., 2020) as GPT,el, and GPT with rotary attention (Su et al., 2021 Black et al., 2022) as GPT,at- For purposes in later sections, we introduce two weaker variants. GPTpos replaces the attention matrix with a matrix based solely on tokens' relative positions, while GPTuni uses a constant, uniform average of past tokens from various window lengths as the attention matrix. Detailed explanations of these variants are Section A.2
We quickly summarize our findings and then elaborate them in details.
5

---

Published in Transactions on Machine Learning Research (12/2025)
GPT,
69.5
16.3
00.0
66.9
44.9 100.0
generation acc (%3
22.5 20.3
28.
20.0
20.4
59.
20.0
92.7
truth
GPT
GPI
GPT
CIPT,
GPP,
0.00000
0.00011
0.00009
0.00039
0.00004
15-4
16.3
157
565
15.6
98.2
986
08.6
90.4
5955
99.0
07.0
99.0
96.9
96.7
58.9
99.8
92.9
entropy (b
169
185
169
190
169
139
169
189
169
190
169
12V
dive gengeccc
0.00024
0.00078
0.00014
0.00023
0.00028
0.00023
0.00015
0.00027
0.00222
0.009
dbpr
17. 572
18.
18.0
97.6 57.
55.9 23.0
02.
929
204
203
203
252
203
14.3
16.5
16.1 15.0
46
275
272
259
00005
0.00043
0.00050
0.00033
0.00332
02.3
19.2
18.5
92.6
214
413
214
413
0:00025
0.00014
0.00026
0.00013
0.00011
256
252
255
253
252
0.00021
0.00025
0.00015
0.00011
0.00031
Figure Generation accuracy (left), entropy (middle), KL-divergence (right) across multiple CTG datasets.
Observations: Less ambiguous CFGs (cfg3el, cfg3e2, as they have more NT/T symbols) are casier to learn. Trans- formers using relative positional embodding (GPTrel or CPTros) are better for learning harder CFGs. The vanilla CPT is worse than even GPTani which is GPT with fixed, uniform attentions.
Result 1-3 (Figure 4). The GPT models (ezcept the original absolute embedding variant) can effectively learn our synthetic CFGs. Given any prefix, they can generate completion strings
that con perfeclly 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 GPT (with absolute positional embedding) performs even worse than GPTuni (with uniform attention).
Result 1: Completion accuracy. We evaluate F by letting it generate completions for prefixes The (g (e) from strings x freshly sampled from L(g). The generalion accuracy is measured as Pry-L() + randomness of F((x:e; F(x:c)) E L(G)). We use multinomial sampling without beam scarch for generation.
Figure 4 (left) shows the generation accuracies for cuts 0 and = 50. The c= 0 result tests the model's ability to generate a sentence in the CFG, while c= 50 tests that to complete a sentence." 0 The results show that the pretrained GPT models can often generate strings that perfectly adhere to the CFG rules for the cfg3 data family.
Result 2: Generation diversity. Could it be possible that the protrained GPT models only memorizod 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 's entropy, which provides a rough estimate of (the log, of) the support size, see the middle of Figure 4, The ot is to use birthday paradox to theoretically lower bound the support size (Arora and Zhang, (017)) This allows us to make precise claims, such as in the cfg3f dataset, there are at least 4 x 10s distinct sentential forms derivable from a symbol on 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 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, for the probability of symbol a E NT, appearing at position 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 prob- ability (as predicted by the transformer model) and the ground-truth. Let p" denote the distribution over strings in the true CFG and p that from the transformer model. Let S = {x((0) [e[[M] be samples from the
Thhe 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 learued by the transformer. This is the source of the "randomness of F" and often referred as using "temperature 6efg3 family large enough ensure negligible chance of freshly sampled prefix of length 50 being seen during pretraining.
6

---

Published in Transactions on Machine Learning Research (12/2025)
04.6
66.7
662
45.7
94.7 64.6
442 66.
64.7
99.6
66.2
64.6 66.6 99.7
19.6 46.7
59.5
06.3 06.4
96.7
96.7
66.2 09
14.6
66.4
98.3
292
100
921
07.
92.0 300
50.4
98.2
00.3
120
10.7
58.5
200
10.7
90.0
58.5
92A 200
90.0
90.8
50.7
102
07.5
50.6
05.3
22.0
99.2
96.6
91.3
220 99.3
96. 912 99.
29.3 95.6
99.0
100 99.3 36.
95.3
16.0
105 99.6 912
9/2 18.3
102
10.5
05.0 90. 10.8
57.0
NY
100
91.8
34.5
054 833
915 96.8 929 553
97.7
53.3
97.3
15.0
05.2 91.
105 95.2
15.5
95.3
102 99.3
84.0 F7.5 13.3 60.
44.8
50.
100
120
100
150 100
100 130
100 130 100 1:00 100
135
100 130
100 135 100
105 100 105 100
105
100 100
105 100 105 700 99. 4 15. 22 17.6272 16.3
20.9
120
100
120 100
09.0 120 100 120 100 00.0 200 135
100 130
10.0 130 100 100 200 10.3 200
100
100
200
105 200 101 200 09. 36.0 10.5
23.5
14.0 04.578.3
NT6 MTS
NTX MB N72 MT5 NTS MM MT3 M2 NTC MTS MT K7 K7 MBG KTS N74 hT) M72 KTG
KT M73 KT2 NTC hTS MT4 KT N72 KTG MT
KTa M72
Figure 5: After pre-training, hidden states of generative models implicitly encode NT-ancestor information. The NTy column represents the accuracy of predicting sg, the NT ancestors on level E, via linear probing (4.2)
It. also encodes NT boundaries (Appendix C. I; and such information is discovered gradually and héerorchically across layers and training epochs (Appendix C.2 and C.3). As control, we apply the same probing method to randomly- initialized GPT (an) and BERT-style encoder (DeBERIa). Both fail to recover deep NT' structure, confirming the probe does not trivially succeed. In particular, BERT-like models are less effective at learning NT' information lovels close to the CFG root.
true CFG distribution. Then, the KI-divergence can be estimated as follows
Pr. 1tls.... 1] 1 Eves len Eie(len(s)+]] EreTu( Pry-It [I,..., log Pr... [S]
11 is the next-token distribution predicted by the model, and Prp- (1 xi,,............ 11-1] (Above, Pry[(] In, ;i,...,;;;11 is that from the ground-truth (8 In Figure 4 (right) we compute KL-divergence using 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 Baker (1979)) be implemented using nonlinear neural networks like transformers, achieving a global minimum in the auto- regressive training objective 9 However, the mere existence of a dynamic- programming transformer to obtain the training objective's '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 address this question.
compute next-token distributions of CFGs, and such algorithms can
Other Applications of Results 1-3. While not the focus of this paper, our constructed CFGs also serve quick testbed for archilecture designs. For instance, the strong performance of uniform attention aligns with the effectiveness of ALiBi (Press et al., 2021) and H-Alibi (Jelassi et al., 2024), and has motivated our follow- up work on modifying Transformer architectures to explicitly leverage short window uniform attention (Allen- Zhu 2025a Additional robustness experiments for uniform attention-ann caatiioonacross accoss data complexities and model sizes are included in Appendix H.
Open source. Our data generators and evaluation tools, including accuracy evaluation and ground-truth distribution computation, are open-sourced as part of the package (Allen-Zhu, 2025b).
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 g. the classical way to reason about if a sequence x satisfies L(g) is to use dynamic programming (DP) (Sakai, 1961 Sipser 2012). One possible implementation of DP involves using the function DP(i, a), which determines whether or not 24+1, ...,.y can be generated from symbol following the CFG rules. From this DP representation, DP recurrent formula can be easily derived 10 In the context of this paper, any sequence x L(G) that satisfies the CFG must satisfy
Similar formula was also used in DuSell and Chiang (2022).
8'heree are many dynamic programming methods to compute Prp- [t] 21.... -1-1 exactly; which one to use is irrelevant. 9This has been carefully explored for masked language modeling case in Zhao al. (2023). can compute DP(,, a) 1 if and only if there exists bi, b2.b2....,b
10For example, for all r C Ik 1] and &P((,,)441.6))
is = such that rulc of the CFG. Implementing this naively would re- sult in a O(len*) algorithm for CFGs with maximum rule length of 3. However, it can be implemented more efficiently with Olenn) time by introducing auxiliary nodes (e.g., via binarization).
31
7

---

Published in Transactions on Machine Learning Research (12/2025)
18 18
13
1 3 3
3
1 1 2
2
linearly encode
linearly encode
0
1
0
1
Figure 6: Illustration of Result 5) GPT's last layer hidden states at the blue positions linearly encode the NT ancestor ancestor/bound- any in the red boxes. (They may not encode NT ancestors for smaller levels because that may not be information- theoretically possible that is, reading only prefix may not be enough to tell what such NIs are.)
the following conditions:
be(i) = -0,(()),))-
(i.j), = and 5y( = a = DP(i, =
(4.1)
(rocall the NT-boundary be and the NT-anccstor 5e notions from Section 2.1 and Figure 2). Note that (4.1) is not an "if and only if" condition because there may be a subproblem DP(i, = 1 that does not li on the final CFG parsing tree but is still locally parsable by some valid CFG subtree. However, (4.1) provides "backbone" of subproblems, where verifying all DP(i,j.a) 1 values in this backbone certifies that the sentence x is valid string from L(g). It is worth mentioning that there are exponentially many implementations of the same DP algorithm 11 and not all j,,) tuples need to be computed in (. Only those in the "backbone' are necessary.
Connecting to transformer. In this section, we investigate whether pre-trained transformer F also implicitly encodes the NT ancestor and boundary information, which forms the basis for its structure rea- soning capabilities. If so, it suggests the model contains sufficient information to support all the DP(i, a) values in the backbone. This is a significant finding, considering that transformer F is trained solely on the regressgee 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 Prtestorr/Boundariie
Let / be the last layer of the transformer (other layers are studied in Appendix C.2). Given an input string x, we denote the hidden state of the transformer at layer and position i as Ex(x) E Rd. We first iigae (e) :E(len(x)] using the full (E((s))) If so, it implies that the last-layer hidden states encode the CFG's structural information up to a linear transformation, and the linear transformation does not depend on x (a.k.. linear probing).
whether a linear function can predict (b1 bz (b se[len(=)] (i))se((emm( and (si (i))
linear probing (full). Due to the high dimensionality of this linear function (e.g., len(x) 300 and 768 yield 300 768 dimensions) and variable string lengths, we propose multi-head lincar function for efficient learning. We consider a set of linear functions fr: Rd RlNT), where r E [H] and H is the number of "heads". To predict any se(i), we apply:
G.(x) = Ere(() Wriii fx(E((T)) E E INT
(4.2)
where Wr def exp( (Pen.Par))
for trainable parameters Pa,, Rd In words, G, is "multi-
Exeelaa(e)) Pxp..P....Pv....))
head attention" over linear functions: fr is the linear probing function mapping each hidden state (of dimension d) to NT-symbol logits; Pt. is the feature vector for position i under head r, defining position- dependent weights Wris (independent of the input r), and they form matrices Wr.i that specify how much the hidden feature at position contributes to linearly predicting the NT symbol at position i.
Each inner loop of the dynamic programming can proceed in any arbitrary order, not limited to == i.j or k = j.d, and the algorithm can prune and break carly. This gives safe estimate of least (nl))((²) possible implementations. Furthermore, there are least. 200mm ways to perform binarization, meaning break length-3 rules length-2 ones. This is just detect. if a given string of length n belongs the CFG.
8

---

Published in Transactions on Machine Learning Research (12/2025)
predict NT NT -n-eend
(diagonal macking)
57.2
28.4
100
109
21.2 98A
58.4
102
07.296
183
100
000
530
1,0
300
99.8 90
76.
2 48
$9.6
99.5999
99
200
129
20.5
00-7
93.
300
102
56.7
92
100
300
92.0
93.4
300
100
90.7
90-3
300
59. 07.4
13.
525 55
300
99.6
18.2
99-
100
100
100
99.7
89.
100
100
99.6
99
96.
100
99.5
29
99
59.2
59.1
100 100
10.5 99.9
183
09.3
102
183 100 100
130 300
150
06.5
23 30.4
V76 WTS
MT4
M73 K73
MTG NTS
MTS
M72 MTS
MT
KT1
MT N72
MTC
MTS
NF4 H73 M7 KT6
K73 M72 MT6
NTS
NT3 MT3 MIG KT5 MTA
GFT.M
GFT.m
CLECIT
bend (0F7./un))
predict NT NT-end (tridiagonal maskingi
19,6
23
200
109
29. 90.7
100
102
07.00..77 22.5
23.0
93.3
300
100
120 300
19.5
30:8081
19.
300 102
99.6
99.5
100 326
93
99.5
15.0
100 100 90.7 03.5 06.
100
100
00.7 00 56.
503 100
19.7
92.4 50
120 00
50.2
02.
92.6
160 99.3
100 66.3
100 60.3
00.
VTG KTS MT4 M7 K7) MTs NTS MTs MTA N72 NTS MTS K74 MT K7 NTG MTS M74 N73 M7 KTs MTS KT4 K7a M72 NT NTS MN KTa M72
Mn6 K75
M7s
km
N72
Figure Generative models encode NT ancestors almost exactly at NT boundaries. The NT, column represents the accuracy to predict si) at locations with by(1) 1, via diagonal multi-head linear probing (4.3)
Observation. When applying same probe random GPT or DeBERTa (a BERT-style encoder trained with MLM), we find NT ancestor recovery fails at doeper levels especially at boundaries highlighting that our results reflect meaningful learned structure, not probing artifacts.
We train Gz(z) e RNT using the cross-entropy loss to predict (se(i) (e(4)) Despite having multiple heads,
(z)z) is still a linear function over (Es(z))
as the lincar weights Wriiik depend only on positions i and k, not on x (except it depends on len())). Similarly, we train (x)x)) E R- using the logistic loss to predict the binary values (bx(1)) (E():" In this process, the transformer is fixed after pretraining, only the lincar weights are newly trained; and evaluations are performed using fresh new samples never seen in pretraining or linear-weight, training. Details are in Section A.4
Using such multi-head linear probing, we discover that:
Result (Figure 5). Pre-truining allows GPT models to almost perfectly encode the NT ancestor se(i) and NT boundary be(i) information in the last transformer layer's hidden states (Ex(z)) (e(ee(())) up a linear transformation.
(See Figure 5 for comparison against rundomly- GPT or encoder model deBERTa, which fail to recover deep NT structure.)
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(( to prodict (se(i) (e()) essential since it's information-theerrttiaallll impossible to extract all of i's NT ancestors by only reading (x) or even all hidden states to its left, especially if x; is the start of a string or a subtrce in the CFG. But, how about those ones information--heerrlioee
setr] for each position i. This is
possible? In particular, how about predicting se(1) at locations i with (1( = i.e., at the end of the CFG subtrees.
Multi-head lincar probing (diagonal). We consider a neighborhood of position i in the hidden states, say (x), and use that for linear probing. In symbols, we replace Wri in (4.2) with zeros for | kl > (tridiagonal masking), or with zeros for i + & (diagonal masking).
G²(z)= = Eee u/ga Wriiis f((E((T)) E R NT
where ò - -00 or
(4.3)
daBeBE is modern variant of BERT, equipped with relative attentious. It is expected that encoder models may not learn deep NT information, because in a maskod-langange modcling (MLM) task, the model only needs to figure out the missing token from its surrounding, say, 20 tokens. This can done by pattern matching, as opposed global planning like dynamic programming.
9

---

Published in Transactions on Machine Learning Research (12/2025)
Result 5 (Figure 6/7).. For GPT models, the information of position i's NT ancestor/boundary is locally encoded around position i when i is on the NT boundary. This is because:
At NT boundaries (t.e., be(x) 1), we discover that diagonal or tridiagonal multi-head linear probing (4.3) is adequate for accurately predicting the NT oncestors se(x)) (see) Figure 7).
Such masking is also sufficient for accurately predicting NT boundaries be(i) (deferred to Figure 19 in Appendir C.1).
In contrast, encoder models like deBERTa do not store deep NT information at the NT boundaries.
Related work. Linear probing at least traces back to Hewitt and Manning (2019), who examines the correlation between BERT's hidden states and the parse tree distance metric (similar to NT-distance in our language). Subsequent studies (Shi et al., 2022 Zhao et al., 2023; Maudslay and Cotterell, 2021; Manning et al.) 2020; Vilares et al., 2020; Wu al., 2020; Arps et al. 2022) also explored probing techniques suggest that BERT-like transformers can approximate CFGs from natural languages.
Our approach differs not only in the multi-head probing formula that proposed; also that data to demonstrate that linear probing can almost perfeclly 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 Gj. We focus on training generative decoder-only models; an encoder-based model like BERT (Kenton and Toutanova, 2019) or its modern variant deBERTa (He et al., 2020) may not learn deep (i.e., close to the CFG root) NT information very well, as shown in Result 4
synthetic
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 complex/deepee 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: Sesttonn-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 embodding. This implics that the transformer learns the CFG's regularity and periodicity through positional information, which then uses for generation.
Formally, let A1,,)-((z) for 2 i represent the attention weight for positions j + i at layer I and head h of the transformer, on input sequence x. For each layer I, head h, and distance 2 O, we compute the average of the partial sum Eisrs (1) over all data æ and pairs i.j with j - i- p. We plot this cumulative sum for I, h, p in Figure 8. We observe strong correlation between the attention pattern and the relative distance p = jj The attention pattern is also multi-scale, with some attention heads focusing on shorter distances and others on longer ones.
distance pa [iI
pantinaaeed stwretn pattem
04
Figure 8: When trained on efg3h using absolute positional embedding, GPT shows a position-based atten- tion pattern. The 12 rows in each block rep- resent attention heads. See Appendix D.1 for more experiments.
Motivated by this, we explore whether using position- based attention is sufficient learn CFGs. In Figure 4 find that GPTpos (or even GPTun) performs well, sur- passing the vanilla GPT, but not reaching the full potential of GPT This supports the superior practical performance of relative-position based transformer variants (such as GPT,a,, GPT,ot, deBERTa) over their base
10

---

Published in Transactions on Machine Learning Research (12/2025)
any -ir--l = attantion
for GPtral over cfg3h data
Food hoof Fest ses ieveeriiieen wosl
(NTond a 3)-(NTondd 2 attention
iTenn HiTend attention pattern
over cit data
GPTrel over cfg31 data
(a) B for NT-end CFG level Rows represent 2, and columns Result 7
(b) B...,j- 5 NT-ends
for NT-ends between CFG (c) -1,,e'-
in CFG level
columns rep-
levels f. - Rows represent r and
represent -2,-1,0,1, 1,
resent 6,, 62 -1,0, +1.
Result
columns E. "x" means n/a entries.
Reault
Figure After pretrained adjacent NT-end at 8" across different f, E. For definitions Section 5.2, experiments see Appendix D.2 D.3 and D.4 This provides evidence for DP-like approach to learn such hard, synthetic CFGs (discussions in Section 5.3).
CFG data, GPT model's attention has strong blas towards NT-end level El to the most
models (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 bound- arics typically attend This pallern enables the transformer to elfectively learn the hierarchical and recursive structure of the CFG, and generate output tokens based the NT symbols and rules.
the "most adjacent" NT-end boundarics, see Figure 2 for an illustration.
Formally, let AL,,)-s(x)) for j 2 denote the attention weight for positions j + at layer and head h of the transformer, on imput sequence æ. Given a sample pool (2 {2!"))nE(N) E L(g), we compute for each layer 1, head 12
AL,.pp Average[[AAnnj--(" n N, N, len(x!")) s.t. - i--i--
which represents the average attention between any token pairs of distance over the sample pool. To remove position-bias, focus (L,,)-(((z)) AL,j-((z)) Ath.jj in this subsection. Our observation can be broken down into three steps.
Result 7 (Figure 9()). (1 exhibils strong bius lowards tokens i at NT ends.
This can be seen in Figure (a)) where present the average value of Bi, over data æ and pairs i, where + 8 is the deepest NT-end on level l (symbolically, 65 + t). The attention weights are highest when 5 = 0 and decrease rapidly for surrounding tokens.
While Result 7aarrady suggests that the transformer performs precise parsing relative to an unseen parse tree (since NT symbols were never revealed to the model), we go further below, showing stronger attention- pattern results that connect this behavior more dircctly to dynamic programming.
Result 8 (Figure 9(b)). (1,))-i()) favors pairs j, both at NT ends on the same level é.
This can be seen in Figure 9(b). where we show the average value of BL,5--(Z)) over data x and pairs i, where by(i + 61) br(j + 82) = for 61,52 (-1,0,1), 1}. maximized when 8, 82
The connection between Result and DP will be detailed in Section 5.3 and illustrated in L Figure 10, Briefly, to cortify (i a) = using rule b,c, the model must locate midpoint i such that i...k k is generated by b and & - 1...j by This entails reading token k from position meaning the model must attend NT-ends at the same level precisely what Result certifies.
12Thronghout this paper, conveniently talk about average.
[|] denote multi-sets that allow multiplicity, such 2,,2,,,3]. This allows us
11

---

Published in Transactions on Machine Learning Research (12/2025)
DP(L, 18)
DP a) = whether symbol a can generate x ...
DPG, 1.,,
DPG, 1,),00
(stored here, see Results 4-S)
learns parse CFG
after pretraining, model's attention - has strong bias from any position j to its most adjacent node positions
positions
position
Corollary: GPT mimics dynamic programming (DP)
learns generate
positions
position
from CFG
1.6,10)
DP20, a) whether symbol follow sequence X; X..Xj
DPytt. 10)
Figure 10: Illustration how GPTs mimic dynamic programming. See discussions Section
We did not stop here either. To further demonstrate DP-like behavior, the attention should favor adjacent rather than arbitrary NT-ends. In the example above, positions k and are adjacent NT-ends for b and e the same level; more generally (see Section 5.3), it should also favor connections from i + i - 1,, representing adjacent NT-ends across levels. This is exactly what Result 9 demonstrates next.
Result 9 (Figure 9()).. (Ln))n(z)) favors "adjacent" NT-end token pairs j. across possibly different layers.
We define "adjacency" as follows. We introduce -1, to represent the average value of (L over samples and token pairs j that are at the deepest NT-ends on levels e, respectively (symbolically, b²(i) = l A 6F()) f',, and are at a distance r 2 0 based on the ancestor indices on level & (symbolically, pr()) (t( = r). We observe that gend +,, minimized at the smallest possible r:
when e' > is minimized at 0; when 8' < it is minimized at
because
undefined
In both cases, this shows NT-ends on level l' attend to their closest NT-ends every level / to their left. We emphasize that this is so even after removing position bias 14
In the next subsection, we explain why these results are strong supportive evidence that the GPT models have learned to mimic a DP algorithm.
5.3 Connecting Results 4,5,7,8,9 to Dynamic Programming (DP)
Dynamic programming involves storage of intermediate results and a recurrent formula to combine them. While identifying specífic DP implementation within transformers infeasible due numerous possibilities (Footnote 11), we can probe for crucial commonalitios.
Section 4 demonstrated that transformers encode the DP's storage backbone- all necessary (P(i,j, values the correct CFG parse tree independent of any specific DP implementation.
For the recurrent formula (e.g., DP(k, j. j. derived from DP b, A DP(i. j...j... c) for rule + b, c), DP(k, i, b) is stored near i, while DP,k, and DP(i,j. j.c. e) are near j (Result. 5). This necessitates a memory read
at (j + i), and i are adjacent NT-ends at the same level. Result & shows that GPT models exhibit exactly such - attention pattern, suggesting an information flow consistent with DP. See Figure 10 (top).
Further reading for DP/CFG experts: two-step DP. Transformers both parsing and generative
1oror any token pair with b²(1) 2 b*()) l' meaning is at NT-end closer to the root than it satisfics Pe()) pe(() I their distance is strictly positive.
Withhoot removing position- blas, such statement may meaningless as the position bias may favor "adjacent" anything, including NT- pairs.
12

---

Published in Transactions on Machine Learning Research (12/2025)
algorithms. While the above DP is rather naive, it only allows parsing. CFG experts (or participants in competitions like T01/USACO/ACMAICPG may recognize that the generative process requires second DP:
let DP2(j,a) denote if prefix 21, ,,...., Ii can be followed by symbol a E NTUT.
If a rule + c,a holds and DP(i. c) (i) are true, then DP2(j. a) is also true. This is similar to the inside-outside algorithm (Baker, 1979). The model must perform memory read from position j to i, where is the nearest NT-end to j at a different level. Unlike parsing DP; the generative DP2 uses information about the end of prior constituent (at t) to inform the valid start (at j) for symbol a. The attention patterns (Result 9 and Figure 10 bottom), indicative of the model's reasoning process, also consistent with this directional information flow.
Finally, to generate according to the CFG distribution, j,( and (P2 a) must be converted into probabilities to compute the final conditional probability of the next token. The full pseudocode is provided in Algorithm 1 for reference, and it involves precisely the memory reads described above.
In sum, while pinpointing a specific DP implementation is impractical (recall Footnote 11), the DP backbone, including storage states and recurrent formulas, 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.
Algorithm the two-step DP compute the next-token conditional probability
For cleanness, shown for CFG vules of length general case uses binarization (e-g., a + b, c, needs be split into length-2 rules) keep O(n²) complexity; code to be released on Citllub upon acceptance.
Input: (probabilistic) CFG and (valid) prefix 21,22, Zn. initialize DP a) < 0 for all i,j,a except DP(i,i,);) x- for 1,2.....
2: for l 2 to n do
3: for i= to - f ++1+ do
4:
j j+i+8-1
for i= to j j- do
for all CFG rules a - b, with prob. p do DP(i,j,a) - DP(i, +p DP(i, b) DP(k-1,j,c)
see Pigure 10(top)
o now DP(i. the probability that symbol E NT UT can generate Ri:j 9: initialize (P2(k, a) + 0 for all k, except 2P (0, rool) 1.
8:
10: for A: == to n do
11:
for all rules a + b, c with prob. p (from top to bottom levels in order) do (P b) + DP (k. b) + - pPDP2(k,a)
12:
13:
for m
do
14:
DP2 c) + DP2(m, c) + DP2(k, DP(K + m,
Figure 10fbottom)
now ()) = the probability that CFG gemerates (from root) a prefūr 1i.k followed by symbol a E NT U DP(1.i.root) and Pr[æ41 = [|a]]] Output: for all E [n]: Pr|zi41 eos x DP2(1-1,2.)
15:
DP,(1.))
DP
6
Results 10-13: Extensions of CFGs
6.1 Result 10: Implicit CFGs
In an implicil CFG, terminal symbols represent bags of tokens with shared properties. For example, terminal symbol like noun corresponds to distribution over bag of nouns, while verb corresponds to distribution over 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 set of observable tokens OT, and each terminal symbol in associated with subset OT, C OT and probability distribution D2 over OT, The sets (OT,), be overlapping. To
13

---

Published in Transactions on Machine Learning Research (12/2025)
carvi cerviaio of ankkzding
0.35
6.75
0.50
0.00
0.5
0.0
0.00
0.00
425
0.75
-.5
4.89
772
-10
-3.00
Figure 11: Language models learn implicit CFGs by using word embeddings to encode the (hidden) terminal symbol.
We present word embodding correlations for GPT pre-trained implicit CFG with [T] 3 and vocabulary size OT 300. 300 rows/columns represent observable tokens OT. Label ijk (0, 1)a the figure indicates Details in Section 6.1
whether is in OT, for the three choices
generate string from this implicit CFG, after generating x (21, T2,....Tmm L(9), for each terminal symbol Fi, we independently sample one element Dr,- After that, we observe the new string y (y1, "2,"", 7m)), and let this new distribution be called Lo(g)
We pre-train language models using samples from the distribution ~ Lo(g). During testing, we evaluate the success probability of the model generating string that belongs to Lo(g), given an input prefix yie- Or, in symbols,
Pry~Lo (9) trandommess of F [(yer F(y:)) E Lo(g)
where F(y:e) represents the model's generated completion given prefix yse- (We again dynamic program- ming to determine whether the output string is in Lo(g).
We summarize our finding below and deferring details to Appendix E
Result 10 (Figure 11). Generalive language models can learn implicil CFGs very well. In porticular, after pretraining, the token embeddings from the same subset OT, 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 wish to pre-train a transformer robust against errors and inconsistencies in the input. For example, if input a prefix with some tokens being corrupted missing, then one may hope the transformer to correct the errors and still complete the sentence following the correct CFG rules. Robustness an important property, as it reflects the generalization and adaptation ability of the transformer reason effectively with real-world training data, which may not always follow the CFG perfectly (such as having grammar errors).
To lest robustness, for each input prefix I.e of length e that belongs to the CFG, we randomly select a set of positions e [c] in this prefix - each with probability p- and flip them i.id. with a random symbol in Call the resulting prefix T. Next, we feed the corrupted prefi T.o to the transformer F' and compute generation accuracy in the uncorrupted CFG: Prą-ı(0), f (I:c, F(x:c)) E L(g)).
We not only consider clean pre-training, but also select [0, 1] fraction of the training data and perturb them before feeding into the pre-training process. We compare three types of data perturbations!" 13
versions of robust pre-training. That is, we randomly
(T-level random perturbation). Each &; w.p. 0.15 we replace with a random symbol in T.
(NT-level random perturbation). Let L and recall st (se,1 (E,,,, se,2.... .(,m....) is the sequence of symbols at NT--lvel f. For each 8e,s, w.p. 0.10 we perturb it to random symbol in NT; and then generate Sy according to this perturbed sequence.
(NT-level deterministic perturbation). Let f - L - and fix a permutation x over symbols in NT,, For each St,i, w.p. 0.05 we perturb it to its next symbol in NT according to n. and then generate x = sL according this perturbed sequence.
1ne can easily extend our experiments by considering other types of data corruption (for evaluation), and other types of data perturbations training). We refrain from doing because beyond the scope of this paper.
14

---

Published in Transactions on Machine Learning Research (12/2025)
pre-training method T-level 0:15 random perturbation
generation ace (%) for ctg3b
NT-level 0.1 random perturbation
NT-level 0:05 determiristic permutation
cut0 s-0.1
100
cuto rw0.2
-98.7
100
100
100
100
100
100
100
100
100
59.2
99.9
100
100
100
99.9
100 100
100
100
58.5
100
100
100
100
100
1000
100
100
100
1000
cut0 t-2
14.3
26.7
66.5
73.5
82.6
91.8
0.0
14.1
22.8
63.8
9.0
16.7
26.9
16.5
56.8
65.5
61.5
comuptedd
78.6
79.5
70.6
76.4
77.9
02.4
80.4
00.6
80.
02.6
00.8
58.
60.4
59.1
60.6
57.5
50.9
56.3
comupted cue50 t-0.2-0
-774
78.7 69.0
16.6
77.6
78.2
76.3
77.5
74.9
77.9
91.1
81.1
89.5
79.6
61.2
82.0
$1.4
60.7
86.0
86.4
59.5
57.7
55.9
57.6
592
58.5
59.7
572
57.
571
10.3
corrupted out50 r=2
cut50 -.000-100
100
100
100
100
100
109
100
100
100
1.0
100
100
100
100
100
150
100
100
100
93.4
100
100
150
100
100
100
100
100
100
1.00
cut50 t-0.2
59.2
100
100
100
1.0
100
100
100
99.8
100
100
100
100
100
RRA
100
100
1.00
100
100
100
1.00
100
1.0
99.0
99.5
99.4
96.2
90.2
99.1
99.3
99
03.4
90.6
54.0
962
97.2
98.1
98.7
0.7 0.6 0.5 04
0.3
0.2
0.1
1.
6.9
08
07
0.5
0.5
0.3
62
0.1
1.
0.9
0.8
0.7 0.6
0.5
0.4
0.3
0.2 0.1 clean
training data perturbation ratio clean
Figure 12: Generation accuracies for models pre-trained cleanly VS pro-trained over perturbed data, on clean or corrupted prefixes with cuts c = 0 or c = 50, using generation temperatures T =
0.2, 1.0.
Observation. In Rows 4/5, by comparing against the last column, we see it is beneficial to include low-quality data (e.g- grammar mistakes) during pre-training. The amount of low-quality data could be little (7 = 0.1 fraction) or large (every troining sentence vay have granonrr mistake). The transformer also learns a "mode switch" between the "correct mode" or not; details in Section 6.2 (More datasets, see Figure 28)
We focus on = 0.15 with a wide range of perturbation rate = in Figure 12, The main message is:
1.0. We present our findings
Result 11 (Figure 12, rows 4/5). When pretrained over cleon dala, 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% accuracy when pretrained over clean data x ~ L(g). If we pretrain from perturbed data both when 7 1.0 so all data are perturbed, and when y 0.1 so we have small fraction of perturbed data GPT can achieve 79%, 82% and 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 T = 1 for generation:
Result 12 (Figure 12, rows 3/6/9). Pre-training on corrupted data teaches model mode switch.
Given correct preser, it mostly completes with correct string in the CFG (Row 9);
Given corrupted prefiz, it always completes sentences with grammar mistakes (Row 6);
When given prefiz, il generales corrupted strings with probabilily close to (Row 3).
By comparing the generation accuracies across different т and 7, we observe:
Result 13 (Figure 12, rows 4/5/6). High robust accuracy is achieved when generating using low temperatures and is not sensitive to even when model is trained totally on corrupted data (7 1.0).
16
This should not be surprising given that the language model learned "mode switch." Using low temperature encourages the model to, for each next token, pick more probable solution. This allows it to achieve good robust accuracy even when the model is trained totally on corrupted data (> = 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, 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 (He- 2019 Shi et al., 2022; Zhao et al., 2023; Maudslay and Cotterell, 2021 Manning et al.,
witt and Manning
2020: Vilares et al., 2020; Wu et al. 2020; Arps et al. 2022). Deletang et al. (2023) explored transformers'
Recall, when temperature r 0 the generation is greedy and deterministic; when 1 reflects the unaltered distribution learned by the transformer; when > small it encourages the transformer output "mare probable" tokens.
15

---

Published in Transactions on Machine Learning Research (12/2025)
learnability 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. (2023) 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. (0023) explored methods beyond linear probing to deduce tree structures learned by transformers. They designed score to quantify transformer's "tree-like" nature, showing it becomes more tree-like during training. Our Figure 21 in Appendix C.3 supports these findings. (This paper first appeared in May 2023, s0 we focus on related works before that.)
Conclusion. This paper demonstrates how transformers learn to reason over challenging synthetic context- free grammars (CFGs), revealing a close alignment between their internal representations and the information flow characteristic of dynamic programming computations underlying parsing and generation. Our primary aim was to provide a controlled interpretability setting that enables mechanistic insights into attention, hicrarchical reprosentations, and algorithmic reasoning in transformer models.
Our approach differs from prior interpretability work (e.g,, (Elhage et al. 2021: Olsson et al. 2022 Wang et al. 2022)), which primarily analyzes large models trained on real-world corpora where noise and uncon- trolled correlations can obscure underlying algorithmic structure. In contrast, we adopt a complementary methodology: leveraging clean, synthetic data to expose and mechanistically analyze how transformers im- plement well-defined, computationally deep reasoning processes.
Beyond the core analysis, we rntuude multi-head linear probing diagnostic tool for analyzing complex internal computations, potentially enabling deeper studies of larger models on similarly structured tasks. We also derived several corollary findings, including: (i) absolute positional embeddings are inferior to relative and rotary embeddings for deep hierarchical reasoning; (ii) uniform attention alone is surprisingly effective, motivating our follow-up work on Canon layers (Allen-Zhu, 2025a b); (iii) encoder-only models (e.g., BERT, DeBERIa) struggle with deep structural reasoning on CFGs compared autoregressive models (e.g., GPT); and (iv) injecting structural or syntactic noise into protraining data substantially improves robustness to corrupted language prompts.
While synthetic CFGs provide well-defined benchmarks for isolating compositional and hierarchical behav- ior and exposing fundamental computational mochanisms, they do not capture the full diversity of natural language or intelligence much like other synthetic algorithmic tasks such as sorting or ListOps. Accord- ingly, we view CFGs as an abstraction rather than a substitute for real-world evaluation. In complementary work, we extend this synthetic-data approach to grade-school math and reasoning (Parts 2.1+2.2 ( (Ye et al., 2025a b)), knowledge storage, extraction, and manipulation (Parts 3.1+3.2+3.3 (Allen-Zhu and Li 2024; 2025a b)), and leverage these insights for architecture design within a unified synthetic pretraining play- ground (Parts 4.1+4.2 (AllenZZhu, 2025a b)).
Acknowledgements
The title Physics of Language Models was jointly conceived and designed by ZA and Xiaoli Xu. 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.
16

---

Published in Transactions on Machine Learning Research (12/2025)
APPENDIX
A Experiment Setups
A.1 Dataset Details
We construct seven synthetic CFGs of depth 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 cfg3b, cfg3i, cfg3h, cfg3g, cfg3f, which are of sizes (1,3,3 3,3,,, 3,33) and present increasing levels of difficulty. Detailed information about these CFGs is provided in Figure 13:
In cfg3b, we construct the CFG such that the degree RR(a) = 2 for every NT 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 respectively.
In cfg3i, we set [R(a)] 2 for every NT a. We remove the requirement for distinctness to make the data more challenging than cfg3b.
The 25%, 50%, 75%; and 95% percentile string lengths are 276, 307, 340, 386 respectively.
In cfg3h, we set [R(a)] E (2,3] for every NT a make the data more challenging than cfg3i.
The 25%, 50%, 75%, and 95% percentile string lengths are 202, 238, 270, 300 respectively.
In cfg3g, we set [R(a)] for every NT a make the data more challenging than cfg3h. The 25%, 50%, 75%, and 95% percentile string lengths are 212, 258, 294, 341 respectively.
In cfg3f, we set [R(a) E {3, 4} for every NT a to make the data more challenging than cfg3g.
The 25%, 50%, 75%, and 95% percentile string lengths are 191, 302, 302,364 respectively.
Remark A.1. From the examples in Figure 13, becomes evident that for grammars G of depth 7, proving that string x belongs to L(g) highly non-trivial, even for a human being, and even when the CFG rules are known. The standard method of demonstrating x E L(g) is through dynamic programming. We further discuss what mean by CFG's "difficulty" in Appendix G, and provide additional experiments beyond the cfg3 data family.
Remark A.2. The dataset 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 (Allen-Zhu, 2225a)),, they would require a larger model and extended training. We focus on cfg3f because it already provides compelling evidence for findings.
Simultaneously, to illustrate that transformers can learn CFGs with larger [NT] or (T), we construct datasets cfg3el and cfg3e2 respectively of sizes (1, 9, 27, 81, 27,9) and (1,3, 9, 27, 27, 9, 4). They are too lengthy to describe so we include them an attached txt file Appendix G.2 and our repo Allen-Zhu (2025b).
A.2 Model Architecture Details
We define GPT as the standard GPT2-small architecture (Radford et al., 2019), which consists of 12 layers, 12 attention heads per layer, and 768 (=12 x 64) hidden dimensions. We pre-train GPT on the aforementioned datasets, starting from random initialization. For baseline comparison, we also implement DeBERTa (He et al.) 2020), 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 reprodueibility, we primarily focus on models with 12 layers, 12 attention heads, and 768 dimensions. The transformers constructed this manner consist of 86M parameters.
Modern GPTs with relative attention.
Recent research (He et al., 2020 Su et. al. 2021 Black et al.
17

---

Published in Transactions on Machine Learning Research (12/2025)
22)->22
22] 29:20
22)-2202021 21
221-332:0
223-12021
221-020198
19]-016 18
22)=2)
19/-11818 16 18
22]-19:2
19]-11617
221-20155 19
222-2215
a sample from cfg3b:
<22 28:18
10| 101-2282 28
22) 121-7
-273777777 28
221-1201
201-117 16:11
20j-11730 17
700-21810 15
14|-038 16:18
9123121321
1521 3222222
1222111159
20] -25-27
101 x18 12
201 117
23: +2535 27
191 >12 35
31/321 12322 31
1252 1252 12333
121
21]
21jp 18
311:33119 1B
20--23117
14
9513312522 21133112212228 2253232222 112 1223222 121 15225 1252221 125822
21]
21] +18 17
301 122
132 12 13 201311221 223322
12 12 132 1223 1:1 12
132312135
12221 812211 5252 1921 322 B.2322 1922 1223 1922
16) 11..-1...5 14
1-15
201 0:17
31812231 229122182212213386 1S0 101 12h3 122 1SP 1o/122 ISP
11235 151
17/-034 23 15
371 111
17: 23
22 112 37
17|-115 13 1-
151-1514
17: 10155 13.15
211-0133 16
19) x13 14:15
281 14.15 15
28 112 23
14) -12 35
22 125 37 10
a sample from cfg3i:
18/01A11
-0.55
16
71
11
-54455
161 15
11811 1181181212222312 121111111111 3115 131212222 1223 11 12811122 1212112
M41-11.00 10
54 140-3001001
131-0:300 30
1G1-1433 33
222312211 11319111 1511 Sa iaa 12511
14 141-1011:31 12
14 -1010
14] +0002222
17) 1.55 34
161 +1.4 14
1233 22321
15 10
151 11:20
14|->2300
1-1--233 33
171-11 34:33
122
151-1112210 10
221-2298
351-23 10
10
138->2232
141-01211 12 10
15/-01111
14 10---55 15
2424 53
171
17]
221 13 12122122212222
122h 512211511111111111 1231312512211 1223 dazzaananna 1a 11312229 1251
1231 51:21 11 131111111 222a 1220
12w.222222222222112222 2212222322222222222222 12113
1251
11)
111:388
11
10]-09
131-11133 51
10|-1335 15
a sample from cfg3h:
22.7
12) =259
10] -48
141 +11 32
151 -11.2
13j-57a
71-81
12
71
11] 1-27
111-8877
141 -11 30
141-100 33 10
15) -1002.31 11
131--12 13
151 29 29133131111 5921 B1 B23 12222
1239
cfg3b
4l-32
71-139
cfg3i
7|o231
111-789
15 33
341-3012
3112158311 131232 1231220 13 131351 1a1. 12111111111111111111111 12125158122
193331133111 1:23 191119319922 992321512288 198111111112233
2102131311 1:51 waw.ss3111111111111
1231 1221111222111333381132222 1ww.
4/-121
qpol 13
12
10/-088
4/-21
7]-00 37
10j-777
15 11
71 11.22
10) 1:77
15 111 11
a sample from cfg3g:
7j-1.31
11/-888
15
11]--9
1121211
cfg3h
pj-213
9/-133
12|-78
121-79
12|-999
71-22
21-11
71-1251
121-797
10/-799
10/-679
11|-57
111-68
11)-477
311 12221 1322 5221 1531 152 581223 222.222222222222222222 155522511111151 1:5251
211 21122111112
231 22 11 11231 53 12221 2222322 222222233333338888 1381131332
351 1231 1231 11 122122 1251
129322991 1331
(22333212311322 132211888 11 3233 122333 13233 1222031 1232
11523311111 323 123231133
1221221122222222
B1--1
12
sample from cfg3f:
R::33:
7/-221
cfg3g
91-233
71:3
1122131223122
9:-25
7/-311
322388123121 112131
12322 1212 1252
9:-11
7/003
29t 12111122 1218812 151131 15 13 1 EISS
IS1ST 1951
35938223121131
1112229111111111122212 1121221 11 121 12333 1233 1121 118513833
351 12383513511 11 153331221 1SS T1ST2 1533252 12 1121
cfg3f
Alo111
213223225322 133221 113221 5222233 1311 13220223221
9/-1111
211 1855311 52222121221222211111
12121131222 3S155122
5221
41-333
213312222222331
9
Figure 13: The context- grammans efg3b, cfg3i, cfg.h...3.....333 cfg3f that we primarily use this paper, together with sample string from each of them. (Follow-up work -Allen-Zhu (025a) has further extended these datasets.)
Observation. Although those CFGs are only of depth 7, they are capable of generating sufficiently long and hard instances; after all, even when the CFG rules are given, the typical way to decide if a string æ belongs to the CFG language x E L(G) may require dynamic programming.
2022) has demonstrated that transformers can significantly improve performance by using attention mech- anisms based on the relative position differences of tokens, as opposed to the absolute positions used in the original GPT2 (Radford et al., 2019) or BERT (Kenton and Toutanova, 2019). There are two main ap- proaches to achieve this. The first is to use "relative positional embedding layer" on |j -i] when caleulating the attention from j to 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 (Su let al., 2021) ) 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-2001 project (along with the default parameters), but downsized it to fit the GPT2 small model. We refer to this architecture as GPT Since could not find standard implementation of GPT using relative attention, we ro-implemented GPT2 using the relative attention framework from DeBERTa (He et al., 2020). (Recall, DeBERTa is variant of BERT that effectively utilizes relative positional embeddings.) We refer to this architecture as GPT
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 erclusively depends on the token positions, and not on the input sequences hidden embeddings. In other words, the attention pattern remains constant for all input sequences.
We implement GPT pos, variant of GPT, that restricts the attention matrix to be computed solely using the
18

---

Published in Transactions on Machine Learning Research (12/2025)
(trainable) relative positional embedding. This can be perceived as GPT variant that mazimizes the use of position-bused allention. We still choose the 12-layer, 12-head, 768-dim structure.
We also implement GPT a 12-layer, 8-head, 1024-dimensional Transformer where the attention matrices are fized. Specifically, for each h E [8]. the h-th head consistently applies a uniform average over the previous 2 1 tokens. This can be viewed as GPT variant. that uses the simplest form of position-bnsed attention. Since GPTuni lacks key and value matrices, its parameter count differs from standard GPT variants. A GPT2- small-sized GPTuni 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 GPTuni.
Remark A.3. It should not be surprising that GPTpcs or GPT perform much worsc 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-initiaaized GPTrel, and use those random features for the purpose of predicting NT ancestors and NT ends. This serves a baseline, and can be viewed as the power of the so-called (fnile-width) neural langent kernel (Allen-Zhu et al., 2019). We call this CPT
A.3 Pre- Training Details
For each sample ~~ L()) 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 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% masked probability, in which 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, use AdamW with 3 = (0.9,0.98) 0.98), weight decay 0.1, learning rate 0.0003, and batch size 96. We pre-train the model for 100k iterations, with a linear learning rate decay|"? 17 For DeBERTa, we use learning rate 0.0001 which is better and 2000 steps of learning rate linear warmup.
Throughout the experiments, for both pre-training and testing, we only use fresh samples from the CFG datasots (thus using 4.9 billion tokens 96 512 x 1008). We have also tested pro-training with a finito training set of 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 4300/3 possibility), there is almost no chance that wruning/testingg 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.
We have slightly tuned the parameters make pre-training go hest. We noticed for training GPTs over our CFG data, warmup learning rate schedule not needed.
19

---

Published in Transactions on Machine Learning Research (12/2025)
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 transformer, implicitly encodes the NT ancestor and NT boundary information for each token position. Since this linear function be of dimension 512 768 when having context length 512 and hidden dimension 768 recall in (4.2), have proposed to use a multi-head attention to construct such linear function for efficient learning purpose. This significantly reduces sample complexily and makes it much easier to find the linear function.
In our implementation, we choose H = 16 heads and hidden dimension d' 1024 when constructing this position-based altention in (4.2) We have also tried other parameters but the NT ancestor/boundaat prediction accuracies are not very sensitive to such architecture change. We again use AdamW with 3 (0.9, 0.98) but this time with learning rate 0.003, weight decay 0.001, batch size 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.
B More Experiments on Results 2-3 (Generation)
Diversity can be estimated through entropy. Given a distribution p over strings and a sampled subset S = (=() Jejay )e(M) from p. for any string z E S, denote by len(z) its length so (Z1...., .,. Men(a))) and denote by [1 = eos. The entropy in bits for can be estimated by
1 [ST Eaes Eie[len(=++a) log2 Prp [Ta [1. (1....,,
11-1]
We compare the entropy of the true CFG distribution and the transformer's output distribution using M = 20000 samples in Figure (middle).
Diversity can also be estimated using the birthday paradox to lower bound the support size of a distribution (Arora and Zhang, 2017). Given a distribution p over strings and a sampled subset $ = {-((1) Jee[ from P, if every pair of samples in S are distinct, then with good probability the support of p is of size at least R(M²). In Appendix B.1, we conducted an experiment with M = 20000. We performed a birthday paradox experiment from every symbol a E NT,, to some other level l > f1, comparing that with the ground truth. For instance, we confirmed for the cfg3f dataset, there are at least S2(M2) distinct sentential forms that can be derived from a symbol in level 1 to level 5, or from level to level 6, etc. not mention from the root in NT, to the leaf level 7. In particular, M² 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 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 ((1), ((.),...,,7""..... (M) (M) E L(),, for every symbol a E NT, and some later level l2 2 & that is closer to the leaves, we wish to define a multii-st Sa-sez that describes all possible generations from a E NT, to NT,, in this sample pool. Formally,
Definition B.1. For E L(g) and E E [L], we use se(i..)) to denote the sequence of NT ancestor symbols on level E [L] from posilion to j with distinct ancestor indices, 18
se(i..) = (se(k) (se(k)) 1... sn. (((R)=De((++))
With the understanding that Pr(0) prelnn(a) + 1) no.
20

---

Published in Transactions on Machine Learning Research (12/2025)
truth
GPT_rel rel
GPT_rot rot
GPT_
diversity pattern for cfg3f
0
000
10
000
0
0.0
10
0
0
00
0
0.0
D
00
10
0.
2
0
0
0
D
0.0
0
10a
10?
101
10"
cuto
cut50
cuto
cut50
cuto
cut50
CUEO
cut50
cuto
cut50
Figure 14: Comparing the generation diversity Sa+t2 and S Sa-ty across different learned GPT models (c= 0 c= 50). Rows correspond NT symbols and columns correspand f2 2. Colors represent the number of distinct. elements Struth and the white numbers represent collision counts (if not present, meaning there are more
than 5 collisions). More experiments in Figure 15 16 and 17
Observation. We use M 20000 samples. The diversity pattern from the pre-trained transformer matches that of the ground-truth. For instance, from the root one generate ((MM) distinct sequences to level &2 = 5 using the CFG rulcs, and from every NT2 can generate R(M+) to level 6 (not say the T-level 7): this is already more than the number parameters in the model. Therefore, conclude that the pro-trained model does not rely on simply memorizing small set of patterns learn the CFGs.
Definition B.2. For symbol NT,, and some layer l2 (61,61 + 1,....,,, L}, define multi-se:
Sa (a) = /2 (1..5) (i,,)) Vi,jiis such that pe, (i - 1) + Pēd (2) = P& (i) pc. + -a s (1.(
and we define the multi-set union Sa-e, Uietan Sa-re (z(61), which is the multiset of all sentential forms that can be derived from NT symbol to depth Ez.
(Above, when x L(g) is generated from the ground-truth CFG, then the ancestor indices and symbols p.s are defined in Section 2.1 If I E L(g) is an output from the transformer F, then we let p.s be computed using dynamic programming, breaking tics lexicographically.)
We use Stuth denote the ground truth Sa-te, when ,..),..., (.. (M) are i.idd sampled from the real distribution L(g), and denote by
and ((al))) Sa-ees (I.e F(x
that from the transformer F. For fair comparison, for each F and p, pick M > M such that M = H E [M'] x F( E L(g) so that F is capable of generating exactly M sentences that nearly-perfectly satisfy the CFG rules.20 20
Intuitively, for z's generated by the transformer model, the larger the number of distinct sequences in S is, the more diverse the set of NTs on level lz (or Ts if lg L) the model can generate starting from NT a. Moreover, in the event that S.P has only distinct sequences (so collision count 0), then we know that the generation from + E2, with good probability, should include at least ((M²) possibilities using a birthday paradox argument. 21
For such reason, can be beneficial if we compare the number of distinct sequences and the collision counts between S and Struth Note we consider all l 2 instead of only lg L, because we want to better capture model's ' diversity at all CFG levels We present our findings in Figure 14 with M 20000 samples for the cfg3f dataset.
Throougottt this paper, use [|I to denote multi-sets that allow multiplicity, such as 2,, This allows us to conveniently talk about its collision count, number of distinct elements, and set average. Plelee note A and M' are roughly the
given
21 A CFG of depth L, even with constant degree and constant size, can generate 2(1)) distinct sequences. 22 model might generate a same NT symbol sequence 81-1: and then generate different Ts randomly from each NT. In this way, the model still generates strings z's with large diversity, but SF - (a) is small. If Sf is large for every &a and a, then the generation from the model truely diverse any level of the CFG.
21

---

Published in Transactions on Machine Learning Research (12/2025)
In Figure 15 we present that for cfg3b, cfg3i, cfg3h, cfg3g, in Figure 16 for cfg3el, and in Figure 17 for cfg3e2. We note that not only for hard, ambignous datasets, also for those less ambignous (cg33el,cfg3e2) datasets, language models are capable of generating very diverse outputs.
22

---

Published in Transactions on Machine Learning Research (12/2025)
truth
GPT
GPT_rel
GPT_rot
GPT_pos
GPT Luni
diversity pattern for cfg3b
0.0
0.0
UT
10
10a
10a
10e
cuto
cut50
CUEO
cutS0
CUI0
cut50
cuto
cut50
cuto
cutSo
(a) cfg3b dataset
truth
GPT
GPT__P
GPT_rot
GPT_
GPT uni
diversity pattern for cfg3i
10*
10a
10e
cut50
cuea
cut50
(b) cfg31 dataset
truth
GPT
GPT_
GPT_rot
_pT_pos
diversity pattern for cfg3h
38
10c
C.C.
10a
10"
rut50
cuto
cut50
EURO
(c) cfg3h dataset
GPT_
GPT_rot
GPT_pos
diversity pattern for cfg3g
10c
2.
1.0
10a
10a
10a
10e
(d) cfg3g dataset
Figure 15: Comparing the generation diversity 50). Rows correspond to NT symbols and columuss correspond to la 2,3, 7. Colors represent the number of distinct elements gtruch and the white numbers represent the collision counts (if present, meaning there
9-74 and SF a across different learned GPT models (and for or
are more than collisions).
23

---

Published in Transactions on Machine Learning Research (12/2025)
APP
fur dapg
Coeenn part
Figure 16: Comparing the generation diversity Struth and SF c= 50). Rows correspond to NT symbols and columns correspond to l2 = 2,3. 7. Colors represent the number of distinct elements in Sa-ty and the white numbers represent the collision counts fif not present, meaning there are more than collisions). This the efg3e1 dataset.
different learned GPT models (and for
24

---

Published in Transactions on Machine Learning Research (12/2025)
truth
GPT
GPT rel
GPT rat
GPT ___pss
GPT_uni Luni
0
30
2.0
10
0.0
0.0
2.0
3
10
1.0 2
0
00
00
00
00
0.
00
00
10
0
0
0
00000
diversity pattern for cfg3e2
10
10
10
10t
10a
cuto
cut50
cuto
cut50
cutD
cut50
cuto
cut50
cuto
cut50
Figure 17: Comparing the generation diversity Struth and SF c 50). Rows correspond to NT symbols and columns correspond to l2 2, 3......7 7. Colors represent the number of distinct elements in Sasty and the white numbers represent the collision counts (if not present, meaning there are more than collisions). This the efg3e2 dataset.
different learned GPT models (and for
25

---

Published in Transactions on Machine Learning Research (12/2025)
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 simple test on the marginal distribu- tions p(a, a), which represent the probability of symbol NT, appearing position (i.e., the probability that se(i) a). We obscrve strong alignment between the generated probabilities and the ground-truth distribution. See Figure 18
BPLAA
MPA
(a) cfg3b datasct; marginal distribution
(b) cfg3b dataset; marginal disttribttion ground truth
cfg3i dataset; marginal distribution
(d) cfg3i datasct; marginal distribution ground truth
(e) efg3h dataset;; marginal distribution
(f) cfg3h dataase;; marginal distribution ground truth
(g) cfg3g dataset; marginal distribution
(h) cfg3g dataset; marginal distribution ground truth
60 000
100
0002 0.55 080
0250
00C
efg3f dataset; marginal distribution
(1) cfg3f dataset; marginal distrihution ground truth
Pigure Marginal distribution a(a, difference between trained model and ground-truth, for an NT/T symbol compare the marginal distribution the ground-truth against cut positions (c 0/c 50). Figures on right showcase marginal
(columm) position i (row). Figures on those generated from models distribution difference between them and the ground-trute It is noticeable from the figures that GPT did not learn ofg3g and efg3f well. This is consistent with the generation accuracies in Figure
26

---

Published in Transactions on Machine Learning Research (12/2025)
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 se(i) for each CFG level & and token position i using a linear transformation. In Figure 19(a) in this section, also demonstrate that the same conclusion applies to the NT-end boundary br()). This completes Result
More importantly, for be(i), we also show that this information is stored locally, very close to position i (such as at + 1). Details can be found in Figure 19 In particular, note as shown in Figure 7, we confirmed that at any NT boundary position where (2) = 1, the transformer has also locally encoded clear information about the NT ancestor symbol sr(i), either exactly
i or i 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)
27

---

Published in Transactions on Machine Learning Research (12/2025)
predict NT-end boundary (%6
GPT
GPT_rel
GPT_rot
GPT_P6S
GPT_uni
baseline (GPT_rand)
<9936
100
100
100
100 100
100
100
100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 96.5 88.0 95 98.5 99.
9993)
99.7
99.8
99. 0
99.5
99.7
99.8
99.1 99.5 99.
99.7 99.8 99.1 99 99.9
99.8 99 99.1 99.6 99,9
99.8 99.8 99.1 99.6
07.5
88.6 94.9 97
99.7
99.3
99.5
99.0
99.9
99.7 99.4 99.5 99.8 99.9
39.7 99.4 99.5 99 99.9
99.7 99.4 99.6 99.9 100
99.7 99.4 99.6 99.9 100
88.1 85.8 94.0 97. 99.4
clg3g
99.0
98.0
98.
99.7
99.8 98.3 98.5 99.4 99. 8
99.0 09.0 98.2 98.5 99 4 99.8
99.7 98.3 99.4
99.8
99.8 98.3 98.6 99.4
92.1
85.6 93.6
97.7 99.3
100 98.3 98. 99.3 99.7
100 96.8 99.0 99.5 99.
1.00 98.8 99.1 99.5 99.8
1.00 98.9 99..999.22 99.6 99.8
100 96.8 99.1 99.5 8
91.7
85.6 94.8
96.1 99.4
01g302
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
71..7 84.2 97.80.97...5
99.5 9 100 100 100 99.6 100 100 1000 100 99.6 100 100 100 100
99.7 100 100 100 100 99.7 1000 100 100 100
73.1 84.6 94 96.0 99.3
NT6 NT5
NT4
MT6
NT3
NTS
NT4 NT3 NT6 NT5
NT2
(a)
Predicting NT boundaries: the column NT; for é 2,3, 4,5, represents the accuracy of predicting by using the multi- head lincar probing function described in (4.2)
predict NT-end boundary (%)
GPT
GPT_rel
GPT_rot
GPT GPT_POS
GPT_umi Luni
baseline (GPT_ (GPT_rand)
<6336
99.5
99.8
95
100
99.6
599.999999933
100 99.6 99.6999599.955.
100 99.5
05.8 100
99.5 59.9 96.5 05.5 99.6
(diagonal masking!
96.5
96.9
96 97.0977.7.8899
97.097.777
98.5
96
97.1
87
94.9
99.3
</33)
91.3
95
035.097.00
99.1
91.5
27
19
6
91 09..99999999989 999.99999999.8. 01..99......3 95.297...99929
91.5
95.2
97.9
99
88
</39
86.7
92.6
95.0
98.0999
95.2
0211885633.9771
99.3
9/g3r
89.1
92.7
98.2
999
96.6
99
93.2
96.
99
01..75.634.88.11
98.2 99.69999999998
99.9
29
99.9 999.8
99..9999.9999999 99.999999999 99..99.........
91..99888...999 99.96 99.9
98.2 99.9
99.8 71.784.29.099.899.
96.0 99.09999999
100 100 99.099.9 100 99.099999
100 100 96.0999.099..
100 96.1 99.0 99.9
100 100 73.1 73.184.694422 98.00999..
NT6 NTS NT4 NT3 NT2 NT6 NTS NT4 NT3 NT2 NT6 NTS NT4 NT3 NT2 NT6 NTS NT4 NT3 NT2 NT6 NT5 NT4 NT3 NT2 NT6 NT5 NT4 NT3 NT2
(b) Predicting NT boundaries with diagonal masking: the column NT, for 8 = 2, 2,3, 3,4,,,66 represents the accuracy of prodicting by using (4.2) but setting Wrii+h O for & k.
predict NT-end boundary (%) (tridiagonal masking)
GPT
GPT_rel
GPT rot
GPT @PT_pos
GPT uni
baseline (GPT_rand) rrand)
<933
99.9
100 99.6 99.699.99999999
99.9 99 100 99.6 99.6999999 999.99999999
100 99.6 99.699.9 100 99.6 99.6 99.9 100 99.6 99. 999 88.0 95 98 99.6
(//33)
97.7 98.99.2990 98. 98.9 99.6
97.8 98. 98 98. 999.6
97.7 99..888888999999 98.999. 97.8 98.2 98.4 98.9
99.0
97.8 98.2 98.4 98. 99.6999..998 69.
88.6 94. 99..3
1633/
98.0 97.097.2290 98.7 99.99999999.
98.1 97.398.8 99 499.
98.1 97.398.8 99. 29..999..88...
97.498.
99.4 99.8
98.1 97.4 98.7 99.8 8 86,8 94.0 97.9 9994
96.7 017766396.33 98.7 99.5
96.7 96.7966.66.88 96..9996766666666
98. 8 99.69996 96.
96.5 96.8 988.8888899999888 96. 96.5 96.8 98.8 99.6
96.7 96.5 96.7 99.8899.66.88.
09996992 62..1 01..188..633..00
799.9.
98.3
99.9999.9499...
98.7 98.4 93.797.6 98. 99..9999999 099.9998.... 95.777.7767 99.999...9....
95.7 97.6 98.8 99.0
98.4 95.7 97.6 98. 99.67 25.634.898.1599
99.9 100 100 100 99.9 100 100 100 99.9 100 100 100 99.9 2..99.1.. 100 100 100 99.9
99.9
99.9 100 100 100 99.9
71.7 71.797.......44448 01.784.294.0978899
98.7 99.7 100 100 100 98.8 99.7 100 100 100 98.8 99.7 100 100 100 98.8 99.7 100 100 100 98.9 99.7 100 100 100 73.1 84.86.66.4222 98.099.3
38.8
NT6 NTS NT4 NT3 NT2 NT6 NTS NT4 MT3 NT2 NT6 NT5 NT4 NT3 NT2 NT6 NTS NT4 NT3 NT2 NT6 NTS NT4 MT3 NT2 NT6 NT5 NT4 NT3 NT2
(c) Predicting NT boundaries with tridiagonal masking: the column NT, for 8 = 2,3,4,5, represents the accuracy of predicting by using (4.2) but setting Wrii+ = 0 for i & >11. 1.
Figure 19: After pre-training, the NT-end boundary information locally near the hidden state at position i + 1, up to linear transformation. This can be compared with the prediction accuracy of the NT ancestor 52( in Figure 5
i.c., be(() for position and NT level e - is largely stored
Observation. This implies, the trausformer actually knows, with a very good accuracy, that "pusition is already the end of NT level f", by just reading all the texts until this position (possibly pocking one more its right). Remark It may be mathematically necessary to peck more than tokens to decide if a position is at NT houndary, due CFG's ambiguity. But, in most cases, that can he decided quite early.
Remark Predicting NT boundary is very biased binary classification task. For levels é that are close to the CFG root, most symbols are not at NT boundary for that level é (see Figure 2). For such reason, in the Keatmop color of the figures above; we have normalized the columns with respect to NTG. differently, to reflect this bias.
28

---

Published in Transactions on Machine Learning Research (12/2025)
C.2 NT Probing Across Transformer's Layers
As one may image, the NT ancestor and boundary information for smaller CFG levels E (i.e., closer to CFG root) are only learned at those deeper transformer layers L. In Figure 20, we present this finding by caleulating the linear encoding accuracies with respect to all the 12 transformer layers in GPT and GP We confirm that generative models discover such information hierarchically.
GPT on ctg3r
GPT_rel rol
ctgst
GPT_rand randd on clgar
GPT
on cfg3i
GPT on ctg31
rand ctgai
predict NT ancestor across layers
'5/0
44.6
59.1
68.0
69.7
44.6
59.1
68.0
69.7
49.2
44.5 59.1 68.7
64.4
66.5
66.2
84.4 71.4
66.5 65.3
64.3
71.3
Jayz
90.9
72.3
48.7
59.5 60.0
94.2
64.2
06.6
59.3
68.0
71.6
69.9
44.0
59.2 68.0
97.3
87.7
79.5
73.0 69.4
96.9
05.3
76.1
71.3 60.5
04.8 71.0 64.6 66.6 65.5
1ay2
99.0
73.6
49.2
59.
6
60.1
99.8
76.6
51.2
59.7
68.0
71.0
50.0
44.6
59.1
68.6
97.5
88.7
81:1
74.0 70.1
97.0
90.6
83.0
74.9 71.3
04.8 71.8
64.7
66.7 65.3
fay3
50.2
59.6
100
58.6
71.8
44.6
59.1 68.6
97.7
90.5
83.8
76.4
98.5 95.5
81.0 80.7
84.8 71.9 66.3 65.5
99.4
78.2
52.1
59.7
68.1
100 93.6
71.2 61.9 68.8
71.7
49.9 44.6
59.1 68.6
98.1
92.4
86.9
79.7 77.1
99.1 98.3 97.0 92.0 92.7
94.7 71.8
64.6
66.5 65.2
lays
54.8
68.3
100 61.6
65.0 69.7
71.6
44.6
59.1 68.6
98.3
89.2
82.1
99.3 99.0
95.6
84.7 71.8
66.4 65.2
laye
1000
87.6
60.7
60.5 5 68.4
100 97,4 69.6
72.7 72.2
71.6
49.9 44.6
59.1 68.6
98.6
95.5
91.9
85.8 62
99.5 99.4 99.3 97.7 97.8
64.7 71.7 64.6 66.6 65.3
fay?
69.2
61.5
93.0
76.3
71.5
66.2
laye
100
95.3
78.7
63. 6 69.5
100 97.7 94.2 88.0 83:2
71.4
49.9 44.6
59.1
68.0
99.2
98.5
97.7
94.6 94.8
99.6 99.6
99.6
99.1 99.6
94.6 71.7 64.7 66.1 65.2
1ey9
100 97.1
87.3
68.3 71.2
100 94.8 91.6 90.3
71.5
44.6
59.1
68.6
99.4
99.3
99.1 97.4 97.8
99.6 99.7
99.2 99.8
84.5 71.7 64.6
06.4 65.0
lazto
100 97.7
92.4 78.3 75.1
100 97.7 95.0 92.8 93.3
71.4 49.9 44.5
59.1 68.0
99.6
99.6
99.5 98.9 99.3
99.6 99.7 29.6 99.3 99.9
94.6 71.7 64.7 66.3 65.2
kyyz
1000 07.8 94.1 86.7 7 82.3
100 97.7 94.9 92.9 93.7
71.3 49.8 44.5
59.1 68.6
00.6 99.7
99.6 99.2 99.7
99.6 99.7 99.6 00.2 99.8
(44.7 71.7 64.6 66.5 65.3
lay12
1.00 97.6 94.3
85.0
100 97.5 94.8 92.9 93.5
71.3 49.9 44.6
59.1 68.6 00.6 99.7 99.6 99.2 99.7 99.6 99.7 99.6 90.2 99.7
[44.6 71.7 66.4 65.2
NT6
NT5 NT4 NT3 NT2 NT6 NTS NT4 NT3 NT2 NT6 NT5 NT4 NT3 NT2 NT6 NTS NT4 NT3 NT2 NT8 NT5 NT4 NT3 NT2 NT6 NTS NT4 NT3 NT2
(a) Predict NT ancestors, comparing against the GaTr baseline
on dggff
GPT_rel cfg3f
GPT_ rand on cfg3
cfg3i
GPT_ on dfg3i
GPT cfg3i
predict NT-end boundary across layers
90.8
05:4 94.0 98.1 1 99.4 90.8 85.4 94.8 98.1 99.4
90.7 05 94.0 98.1 99.4 06. 88.4
94.9 97.9 99.3
86.9 08.4 94,9 97.9 99.3
06 9 88.5 94.8 97.0
fayz
100
92.9
95.0
98.1 1 99.4
99.2 88.9
94.8 90.1
99
91.7
05
94.0 98.1 99.4
97.6
97.3
96.0
98.1
99.3
97.3 96.2
95.6
10.1.. 99.3
87.6 88.7 94.9 97.0 99.3
Jay2
1000
93.4
95.0
98.1
99.4
100 95.1
95.2 98.1
99.4
91.8 85.6 94.8 98.1
99.4
38.0 97.7
96.2
98.2
99.4
98.7 98.2
96.7
98.3 99.4
87.7 88.7 94.9 97.9 99.3
95.1
98.1
99.4
100
35.7
98.1
99.4
91.8
94.8
98.1
99.4
98.4 98.1
98.3
99.1
98.9
98.5 99.4
87.7 88.6 97.9 99.3
Taya
100
95.0
95.2
98.1 1 99.4
100 98.3
96.9 98.2
99.4
911.9
85.6 94.0 98.1 99.4
90.8 98.5
97.2
98.4
99.4
99.4
99.4
90.4 90.8 99.5
67.7 66.7 94.9 97.8 99.3
fays
95.5
91..8 85.6
08.9
98.5
99.6
laya
1000
97.1
95.9 98. 1 99.4
100 98.9 98.8
98.8 99.5
911.8 85.6 94.8 98.1 99.4
00.1 98.9
97.9
98.6 99.5
99.6 99.7 98.9 90.3 99.8
67.7 88.6 94.9 97.9 99.3
lay?
100
96.6
98.2 99.4
100 99.0
99.7
91.88 85.6 94.8 98.1
98.4
99.3
99.1
98.8
99.7 99.8 99.4 98.8
87.7 88.6 94.9 97.9 99.3
Jayg
100
98.2
97.6 98.3 99.4
100 98.9 99.0 99.4 99.8
91.0 83.6 94.0 98.1 99.4
99.4
99.4
98.5 99.0 99.6
99.7 99.8 99.0 99.5 99.9
B7.6 88.6 94.9 97.9 99.3
fay9
1000
98.4
98.4 98.6 6 99.5
100 98.9 90.1 99.5 99.8
91..8 85.6 94.8 98.1 99.4
00.5 99.6
98.8 99.2 99.8
99.7 99.8 99.1 90.6 99.9
(7..6 88..6 94.9 97.9 99.3
Jay20
98.5
98.7 08. 99.6
100 98.9 90.1 99.8
01..8
94.8 98. 99.4
00.6
99.7 99.0 99.4 09.9
99.8 99.8 99.1 00.6 99.9
87.7 88.7 97.8 09.3
100 98.5 98.9 99.3 3 99.7
100 98.9 99.1 99.5 99.8
91.. 05.5 94.0 98.1
98.4
99.7 99.8 99.1 99.5 99.9 99.7 99.8 99.1 99.6 99.9
07.6 88.6 94.9 97.9 99.3
loyi2
98.0 99.7
99.0 99.8
91..7
98.1 99.4
99.7 99.0 99.5 99.9 99.7 99.0 99.5 07.5 88.6
NT6
NTS NT4 NT3 NT2 NT6 NTS NT4 NT3 NT2 NT6 NTS NT4 NT3 NT2 NTS NTS NT4 NT3 NT2 NT6 NTS NT4 NTB NT2 NTS NTS NT4 NT3 NT2
(b) Predict N'T' boundaries, comparing against the GPTrand baseline
Figure 20: Generative models discover NT ancestors and NT boundaries hicrarchically.
29

---

Published in Transactions on Machine Learning Research (12/2025)
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" (Allen-Zhu and Li 2023).
predict NT (GPT)
predict NTend (GPT)
predict NT (GPT_rel)
predict NTeedd (GPT_ (GlT_rel)
5
99.5
84.2
57.2
59.9
68.7
100
96.4
95.6
98.1
99.4
100
96.2 86.8 68.8 70.9
100 98.5 98.5 98.7 99.5
20
100
93.2
71.6
69.1
100
98.0
98.2
99.4
100
96.8 91.7 79.7 75.5
98.6
98.8 99.1 99.6
25
100
95.2
79.7
64.5
69.9
100
98.2
97.9
98.4
99.4
100
97.0
92.7 85.3 80.0
100
98.6
98.8 99.3 99.7
20
100
96.1
83.4
66.1
70.3
100
98.4
98.3
98.5
99.4
100
97,1 93.2 87.5 83.4
100
98.7
98.9
99.4 99.7
R5
100
96.5
86.0
71.1
100
98.4
99.5
100
88.9 86.0
98.7 98.9
100
96.8
87.5
70.5
71.7
100 98.4
98.5
98.7
99.5
100 97.2 93.7 89.7 87.8
100 98.7 98.9
99.4 99.8
35
100
97.0 88.5
71.9 72.6
100
98.4
98.5
98.8
99.5
100 97.4 94.1 90.6 89.3
100 98.7 98.9 99.4 99.8
100
97.1 89.4
73.3 73.1
100
98.5
98.6
98.8
99.5
100 97.3 94.0 90.8 90.1
100 98.7 98.9
99.4 99.8
predict NT incestor/boundar (%) across training epochs
<5
100
97.1 90.1 74.7 73.9
100
98.4
98,9
99.5
100 97.4 94.0 91.1 91.0
100 98.7 98.9
99.4 99.8
$0
100
97.2 90.6
76.3 74.4
100 98.5
98.6
98.9 99.6
100 97.4 94.1 91.3 91.4
100 98.7 98,9 99.4 99.8
-55
100
97.3 91.0 77.6 75.0
100
98.4
98.7
99.0
99.6
100 97.4 94.2 91.5 91.7
100 99.7 99.0 99.5 99.8
100
97.2
78.8 76.0
100
99.6
100
91.6 91.8
98.8 99.0
99.5 99.8
65
100
97.3
91.8
79.8 76.9
100
98.4
98.7
99.0 99.6
100 97.4
94.3 91.7 92.0
100 98.7 99.0
99.5 99.8
70
100
97.4 92.1 80.5 77.2
100
98.4
98.7
99.0
99.6
100 97.5
94.4 91.7 92.3
100 98.8 99.0
99.5 99.8
100
97.4 92.4 81.2 77.9
100
98.4
98.7
99.1 99.6
100 97.4
94.3 91.8 92.5
100 98.8 99.0
99.5 99.8
80
100
97.5 92.7 82.2 78.5
100
98.4
98.7 99.1 99.6
100 97.5 94.4 91.9 92.5
100 98.8 99.0
99.5 99.8
100
97.3 92.7 82.6 79.1
100
98.3
98.7 99.1 99.6
100 97.5 94.5
92.1 92.5
100 98.8 99.0
99.5 99.8
100
97.5
92.9
83.3 79.3
100
98.4
98.7 99.1 99.7
100 97.5
94.5
92.1 92.5
100 98.8
99.0
99.5 99.8
95
100
97.5
93.0
80.3
100
98.4
98.7 99.1 99.7
100 99..4
92.2 93.0
100 98.7 99.0
99.5 99.8
100
100
97.5 93.3
84.4 80.5
100
98.4
98.7 99.2 99.7
100 97.5
94.5
92.3 93.0
100 98.8
99.0
99.5 99.8
105
100
97.5
93.3
84.7
80.8
100
98.4
98.8
99.2 99.7
100 97.5
94.5
92.3 93.0
100 98.8 99.0
99.5 99.8
220
100
97.5
93.3
100
98.3
99.7
100
92.2 92.9
98.7 99.0
99.5 99.8
115
100
97.5
93.4
85.3
81.5
100
98.4
98.8 99.2 99.7
100 97.4
94.4 92.2 92.8
100 98.8 99.0
99.5 99.8
120
100
97.6
93.5
85.6
82.4
100 98.4
98.8
99.2 99.7
100 97.5
94.5 92.2 92.9
100 98.8 99.0
99.5 99.8
125
100
97.6
93.8
86.2
82.8
100 98.4
98.8 99.2 99.7
100 97.6
94.8 92.6 93.3
98.8 99.0
99.5 99.8
130
100
97.5
93.7
86.4 83.1
100
98.4
98.7 99.2 99.7
100 97.4
94.6 92.6 93.1
100 98.7 99.0
99.5 99.8
135
100
97.6
93.8
86.7
83.3
100
98.4
98,8 99.2 99.7
100 97.5 94.7 92.4 93.1
100 98.7 99.0
99.5 99.8
140
100
97.5
93.6
86.5 83.6
100
98.3
98.8 99.2 99.7
100 97.5 94.6 92.6 93.3
100 98.7 99.0
99.5 99.8
145
97.6
100
99.2 99.7
100 94.7 92.9
98.7 99.0
99.5 99.8
250
100
97.6
93.8
87.0
83.8
100
98.4
98.8
99.2 99.7
100 97.5 94.7 92.7 93.4
100 98.8 99.0
99.5 99.8
155
100
97.6
93.9
87.1
84.7
100
98.4
98.8
99.2 99.7
100 97.5
94.6 92.5 93.0
100
98.8 99.0
99.5 99.8
260
100
97.6
84.5
100
98.4
99.3 99.7
100 97.6
92.5 93.0
99.0
99.5
165
100
97.6
94.0
87.8
85.0
100
98.4
98.8 99.3 99.7
100 97.5 94.6 92.7 93.3
100 98.8 99.0 99.5 99.8
170
100
97.5
94.1
87.8
85.3
100
98.4
98.8
99.3 99.7
100 97.4
94.7 92.8 93.5
100 98.7
99.0
99.5 99.8
175
100
97.6
94.1
85.4
100
98.4
99.3 99.7
100 97.5
94.7 92.6 93.2
98.8 99.0
99.5
180
100
97.6
94.1
87.9 85.3
100
98.4
98.8 99.3 99.7
100 97.6
94.7 92.5 93.2
100 98.8 99.0
99.5 99.8
185
100
97.6
94.2
88.1 85.5
100
98.3
98.8
99.3
99.7
100 97.5 94.7 92.7 93.4
100 98.8 99.0
99.5 99.8
190
100
97.6
94.3
88.2 85.6
100
98.4
98.8
99.3 99.7
100 97.5 94,8 92.8 93.6
100 98.8 99,0
99.5 99.8
295
100
97.6 94.2
86.0
100 98.4
99.7
100
92.8
98.8 99.0
99.8
200
100
97.7 94.2
88.2
85.7
100
98.4 98.8
99.3
99.7
100
97.5
94.7 92.7 93.3
100 98.8
99.0
99.5 99.8
NT6 NTS NT4 NT2 NT6
NT2 NT6
NT3 NT2
NT4 NT3
Pigure 21: Generative models discover NT ancestors and NT boundarics gradually across training epochs (here 1 epoch equals 500 trøining stops). CFG levels closer to the leaves are learned faster, and their accuracies continue to increase as deeper levels are being learned, following a principle called "backward feature correction" in deep hierarchical learning (Allen-Zine Zhu and Li 2023).
30

---

Published in Transactions on Machine Learning Research (12/2025)
D More Experiments on Results 6-9 (Attention Patterns)
D.1 Result 6: Dosition-Based Attention Pattern
Recall from Figure we have shown that the attention weights between any two positions - have a strong bias in the relative difference p [j i/. Different heads layers have different dependencies on p. Below in Figure 22, give experiments for this phenomenon in more datascts and for both CPT/GPT,rl.
GPT cfg3b
(b) GPT
cfg3b
datance P S10
on cfg3i
(d) CPTral on cfg3i
discunce
distance p (H]
GPT on cfg3h
GPT on cfg3h
GPT cfg3g
(h) GPT cfg3g
112
299 240 210
140 107 250 290 3M
GPT efg3f
GPT,a on cfg3f
Figure Position- based attention pattern. The rows layer represent heads. Observations. The attention
pattern is multi-scale; different heads or layers have different dependencies on p.
31

---

Published in Transactions on Machine Learning Research (12/2025)
D.2 Result 7: From Anywhere to NT-ends
Recall from Figure 9(a) we showed that after removing the position-bias BI dut A f- (i))))) A1, jii the attention weights have a very strong bias towards tokens i that are at NT ends. In Figure 23 we complement this experiment with more datasets.
a + 2) attention
for GPTrel over cfg3b data
any- (NTend, attention
3i data
4.4
for GPTrel over cfg
-000
6.4
(a) cfg3b dataset
(b) cfg3i dataset
reed2 haa? hack bead headi rescf heeda heach hensirrestll head12
head readt hardi head? beat) maddd beudht medt heuc22
any a = 2) attention for GPTrel over cfg3h data
any (NTend, + 2) attention
for GP over cfg data
111
(c) cfg3h dataset
cfg3g dataset
kwit feat soit leat sod foot leut feam Indttictttiiatt vult
any (NTenn + 2) attention
for GPTrel over cfg3f data
DUM
0.0
40
cfg3f dataset.
Figure 23: Attention weights Br, averaged data and pairs i, such that 6 the N'i-end level / of the CFG. each cell, the four correspond levels 3, 4, 5, and the five columns represent -2, 1,, +2,
Observation. Attention largest when drops rapidly surrounding i.
32

---

Published in Transactions on Machine Learning Research (12/2025)
D.3 Result 8: From NT-ends to NT-ends
As mentioned in Section 5.2 and Figure 9b), not only do tokens generally attend more to NT-ends, but among those attentions, eTdd are also more likely to attend NT-ends. We include this full experiment in Figure 24 for every different level & = 2,3, 4, 5, between any two pairs - i that are both at NT-ends for level e, for the cfg3 datascts.
33

---

Published in Transactions on Machine Learning Research (12/2025)
1
<rpb
cfg3b level f
(b) cfg33b level f
(c) cfg3b level E
(d) cfg33 level &
(erOOd That atterton 41g
attertion
(arost Tha attenton
attuntton
8.82
(1g
(Wrond' Suat OPtet
Derond Suantraoi
(e) cfg3i on level é =
(f) cfg3i on level & =
(g) cfg3i on level E =
(h) cfg3i on level & =
Inficg Wirre altartionn
Imlg Worrd aftention
IiThon 1l-WWor antendiinn
cfg3h on lovel
(j) cfg3h on level l
(k) cfg3h on level
cfg3h on level
(m) cfg3g level &
(n) cfg3g level L
(o) cfg3g level E
cfg3g level E
for ofte 0531 mata
(9) efg3f on level 8
(r) efg3f on level ===
(s) efg3f on level f=
(t) efg3f on level E
Figure 24: Attention pattern (() averaged over data x and pairs i, such that i + 81 and j + 82 are at the NT--end boundaries in level f of the CFG. In each block, the three rows correspond to 61 = 1, 11 and the three columns correspond to d2 1,0 1.
Different transformer layer/head may be in charge of attending NT-ends different levels f. Also, it is noticeable that the attention value drops rapidly from 6i = 11 to 61 0. but less from = 11 82 = 0. This should not be surprising, may still be ambiguous decide if position is at NT-end until one reads few tokens (sce discussions under Figure 19).
Observation.
34

---

Published in Transactions on Machine Learning Research (12/2025)
D.4 Result 9: From NT-ends to Adjacent NT-ends
In Figure 9(c) we have showcased that (x)))-(( has a strong bias towards token pairs i,j that are "adja- cent" NT-ends. We have defined what "adjacency" means in Section 5.2 and introduced notion Bond-oond to capture B(,.)-((x)) averaged
-trr samples and all token pairs i. such that, they deepest. NT-ends levels e, fl respectively (in symbols, (²) LA (²( f"), and of distance based on the ancestor indices level (in symbols, pe(5) pr(1) - r)
Previously, we have only presented by Figure ( for a single dataset, and averaged over all the transformer layers. In the full experiment Figure 25 we show that for more datascts, and Figure 26 we show that for individual layers.
NTend, WTTend-NNTen -NTend, attention pattern GPTrel over cfg3i data
WTend, #'Tend,-NTent -NTend, pattern for GPTrel over cfg3h data
r=4
1=8
r=8
r-
r=12
1=1
(a) cfg3i
(b) cfg3h
NTeed; ~NTend, attention pattern
NTend, -Tend, attention pattern for GPTrel over cfg3f data
r=D
for GPTrel over cfg3g
1-16-
--
(c) cfg3g
(d) cfg3f
Figure 25: Attention pattern gend (ar) averaged over layers heads and data z. The columns represent + and the Le Tows represent "x" means empty entries.
We present this boundary bias looking how close NT boundarics level E' attend any other NT boundary level For distances r, this "distance" that have defined may be non-existing, For instance, when é 2 bius, still a large correlation respect the smallest possible distance r, between every pairs NT levels E, E. This a strong evidence that CFCs are implementing some variant dynamic programming.
Remark.
must have Nevertheless, we that the attention value, after removing the position
35

---

Published in Transactions on Machine Learning Research (12/2025)
hry
*y2
kyd
NyS
layl
laya
Wy30
wyy1
wy22
[w0
[40
r-12
(a) cfg3i
hyy
hy2
Ryd
S
byy
lay?
laya
lays
ky/1
byy1
byy2
140
(b) cfg3h
Sy2
lays
bay31
140
cfg3g
rw16
(d) cfg3f
Figure 26: Attention pattern Bend-tend (x) for each individual transformer layer / [12], averaged heads h and data The rows and columns are in the same format as Figure 25
Observation. Different transformer layers are responsible for learning "NT--und to most adjacent NT-end" at different CFG levels.
36

---

Published in Transactions on Machine Learning Research (12/2025)
E More Experiments on Result 10 (Implicit CFGs)
We study implicit CFGs where each terminal symbol & T is is associated bag of observable tokens OT,- For this task, we study eight different variants of implicit CFGs, all converted from the exact same cfg3i dataset (see Section A.I). Recall cfg3i has three terminal symbols |T] 3:
consider vocabulary size |OT| 90 or |OT| 300; let HeT be either disjoint overlapping: and we let the distribution over OT, be either uniform or non-uniform.
We present the generation accuracies of learning such implicit CFGs with respect to different model architec- tures 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 GPT, model (the correlation will be similar we use other models).
disjoint |vocab -9
disjoint |vocab|-300
overlap |vocab]
overtap |vocab/-300
100.0
100.0
100.0
GPT_rel rel
99.3
99.7
99.0
98.9
100.0
100.0
98.9
99.1
97.8
97.9
92.9
91.9
100.0
100.0
100.0
100.0
GPT rot
99.2
99.5
99.0
98.4
100.0
100.0
98.6
99.0
96.4
95.9
84.9
87.8
100.0
100.0
100.0
100.0
GPT pos
99.2
99.4
98.4
99.2
100.0
100.0
96.6
96.4
90.1
91.3
82.6
83.6
100.0
100.0
100.0
99.7
GPT uni
99.7
99.6
98.4
99.0
100.0
100.0
89.5
92.9
64.4
65.4
100.0
100.0
99.9
100.0
cuto
cut5
cuto
cut50
cuto
cut50
cuto
cut50
cuto
cut50
cuto non-uniorm
cut50
cuto
cu550 curo
cut50
uniform
non-uniorm
uniform
non-uniorm
uniform
uniform
non-uniorm
Figure 27: Generation accuracies on eight implicit CFG variants from pre-trained language models.
37

---

Published in Transactions on Machine Learning Research (12/2025)
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.
pre-training method-....... T-level 0.15 random serturbation
generation (%) for cfg30
NT-level 0.1 random perturbation
NT-level 0.05 deterministic permutation
cuto r-6.1
-100
100
100
100 100 100 300 100
69.8
100
100
100
100
100 100 100 300 100
100
cuto t=0.2
-38.7
100
100
100
100
100
100 100
100 100
99.2
29.9
100
100
100
99.9
100
100
100
120
P8.5
100
150
100
100
100
100 100
100
100
100
cull r-1
65.4
75.5
63.6 92.5
0.0
14.7
26.9
38.5
48.8
00.8
65.5
commpleed y-0.1
78.3
18.9
80.6
78.0
79.1
76.6
79.5
78.6
76,4
77.9
62.6
80.4
90.6
80.4
01.7
82.6
81.4
81.7
90.8
60.8
60.4
58.3
56.5
58.1
60.4
59.1
60.6
57.5
58.9
$6.0
30.4
comupted cut50 t.0.2
27.4
76.4
77.3
14.9
77.9
91.1
80.5
19.5
92.9
$1.4
80.7
50.0
62.4
59.5
57.1
55.9
575
59.4
59.5
59.7
57.8
30.3
corrupted
0.6
0.5
6.6
6.6
6.7
06
0.0
0.3
0.4
04
6.4
0.5
6.9
29.4
ca850 r=0.1
1000
100
100
100
106
100
100
100
100
100
100
100
100
100
100
100
100
100
100
150
99.4
1.0
100
100
100
100
100
100
100
100
100
cut50 k-0.2
out50 y-1
0.0
91.5
95.7
97.1
98.1
98.7
99.2
99.0
68.5
99.4
2.0
92.0
96.2
97.4
98.2
99.1
99.3
99.4
99.5
99.7
0.0
03.4
90.6
96.0
96.2
97.2
98.1
98.7
95.2
99.
99.5
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2 6.1
1.0 0.9 088 0.7 0.6 0.5 0.4
0.3
0.2
0.1
1.0
0.9
0.8
0.7
0.0
0.5
0.4
0.3
0.2
0.1
dean
pre-training data parturbation ratio y OR clean data-
(a) cfg3b dataset
pre-training method T-level 0.15 random perturbation
generation ace (%) for clg31
NTvloval 0.1 random perturbation
NT-lovel n.05 deterministic permutation
cutO
$9.3
98.9
99.8 99.7 100.0 69.7 99.8 $9.3 99.1 99.4
99.4
69.5 99.4 69.6 99.3 48,9 99.3 99.7
99.6
98.4
99.4
99.8
99.4
98.3
$9.6 97.9 99.6 98.5
47.7
cuto T=0.2
-35.0
95.6
99.4
98.7
99.2
58.8
59.2
58.9
58.7 59.4
96.5
98.1
59.2
99.2
59.2
98.7
56.7
58.2
58.8
99.4
98.9
97.8
99.2
99.3
58.8
98.6
58.9
58.2
98.4
982
98.6
T-1
comppted r-0.1
71.9
75.1
13.2
72.9
73.1
14.3
12.5
71.7 70.9
78.6 75.2
77.0
76.
77.6
78.6
78.7
78.2
78.4
78.0
48.2
468
48
465
46.4
47
48.2
25.4
48.2
48.0
36.8
comppted cutso r-0.2-777
76.7
76.4
78.2
76.2
78.2
45.0
46.
48.
469
46.
46.
49.5
48.4
37.0
cornupted cut50 y=1
0.9
0.4
0.0
0.5
0.5
0.3
0.5
0.4
0.5
0.4
0.4
0.0
0.3
0.3
0.4
0.4
0.5
0.6
3.4
0.3
37.1
cusso 1-0.1
29.1
100.0
95.9
59.2
99.3
98.8
99.5
49.
99.8
94.3
99.3
98.8
99.7
95.7
99.2
99.1
99.5
59.2
99
59.7
95.4
99.3
95.0
48.6
36.0
99.4
99.7
99.2 98.8
99.4
99.8
59.5
99.7
99.7
99.2
99.4
99.1
out50 y-1
0.0
90.1
95.4
95.6
9Y.6
98.9
95.8
98.7
79.7 94.4
0.0
23.3
95.8
9h.7
97.5
49.0
94.2
99.2
99.2
99.1
0.0
05:1 90.3 95.5 96.2 97.2
97.5
95.6
95.0
99.3
49.9
1.0
0.7
04
0.5
0.4
0.3
0.2
0.1
1.6
0.9 0.8 0.7 0.6 0.5 0.4
0.3
0.2
0.1
clean
pre-training data perturbation ratio y DR clean data
(b) cfg3i dataset
www.----pe-errrttt pre-training method T-level 0.15 random pertur ba foo
generation ace (%) for cfg.3
NT-level 0.1 random per tertuuraation
NT-level 0.05 deterministic permutation
cuto 81.5
89.0
95.0
97.5
96.9 96.3
98.0
98.4 98.1
P5.2 97.1 99.2 99.3 99.6
99.2 98.2 99.5 99.0 95.2
68.9
98.6
v8.6
99.3
99.0
99.3
29.2 98.6 98.5 95.7
97.2
ruto r-0.2
45.9
98.7
97.9
59.4
98.9
B1.4
97.1
$8.5
98.9
99.2
49.1
$9.1
99.4
58.7 99.1
98.7
99.1
59.1
59.6
59.2
99.1
58.9
99.0
99.0
r=1
46.4
83.6
91.3
0.0
15.2
25.6
40.7
41.5
06.7
74.
64.
50.9
59.6
corrupted cut50 t-0.1
29.6
15.5
41.1
43.5
43.3
19.5
85.4
11.7
41.4
11.8
53.
64.4
49.8
-1.
51.
51.5
56.2
50.1
67.6
15.4
17.
16.3
15.5
15.5
11.4
16.6
16.6
17.0
11.8
18.
comupted cut5o r-0.2-1
27.
29
29
26.5
30.7
30.4
30.1
corrupted cu150 1-1
0.0
1.1
0.3
06
04
0.7
1.0
0.5
0.8
0.5
0.0
0.7
0.2
0.8
0.3
0.7
0.0
1.4
0.1
0.6
0.0
0.5
13
1.0
0.8
0.4
0.9
0.8
0.4
0.7
12.4
cat50 yu0.1
22.3
96.1
95.
29.2
99.0
929
96.6
99.3
99.7
99.3
99.3
19.0
99
99.3
95.
97.6
95.
99.4
99.4
99.5
99.2
98.9
99.5
98.9
99.4
06.3
46.3
91.3
98.5
98.9
99.8
99.7
99.2
99.5
29.5
99.5
99.6
78.9
95.8
99.3
99.1 59.5 99.5
99.5
95.7
99.8
90.3
49.2
cu150 m=1
0.0
54.2
92.1
95.9
97.0
97.4
95.4
19.1
98.8
99.2
2.0
29.3
95.6
95.7
97.4
98.5
99.3
99.4
99.1
99.4
0.0 72.1 64.2 90.5
94.5
97.0
97.4
95.6
98.4
95.9
99.9
08 0.7 0.6
0.5 GA 0.3
6.2
0.1
10
99 0.8 0.7
0.6
0.5 0.4
0.2
cleam
.........-- -pr-ttriiinng data perturbation ratio y OR clean data
(c) cfg3h datasct
Figure 28: Generation accuracies for models pre-trained cleanly VS pre-trained over perturbed data, on clean or corrupted prefixes with cuts c = 0 or c= 50, using generation temperatures T = 0.2, 1.0.
Observation 1. In Rows 4/5, by comparing against the last column, we see it is beneficial to include low-quality data (e.g. grammar mistakes) during pre-training. The amount of low-quality data could be little (? = 0.1 fraction) large (every fraining sentence may have grommer mistake).
Observation 2. In Rows 3/6/9 of Figure 12 we see pre-training teaches the model a mode switch. When given correct prefix it is in the correct mode and completes with correct strings (Row 9); given corrupted prefixes it always completes sentences with grammar mistakes (Row 6); given no prefix it generates corrupted strings with probability 7 (Row 3).
Observation 3. Comparing Rows 4/5 Row 6 in Figure 12 we that high robust accuracy is achieved only when generating using low temperatures т. Using low temperature encourages the model to, for each next token, pick more probable solution. This allows it to achieve good robust accuracy even when the model is trained totally on corrupted data (7 = 1.0).
38

---

Published in Transactions on Machine Learning Research (12/2025)
(a) the real-life CPG derived from Penn Treebank, short and simple
(b) the cfg3 family used in the main body of this paper has rule lengths 2 or 3 (cfg3f in this figure)
(c) the cfg8 family has rule lengths 1, 2, or (efgße this figure)
(d) the cfg9 family has rule lengths 1, 2, (cfg9e this figure)
(e) the cfg0 family has max-depth 11 and rule lengths or 2 (efg0e in this figure)
Figure 29: CFG comparisons: left is a -endium-length sample and right is a 80%6-prrcentile-enngg sample
G Beyond the CFG3 Data Family
The primary focus of this paper is the cfg3 data family, introduced in Section A.1 This paper does not delve into how GPTs parse English other natural languages. In fact, our CFGs are more "difficult" than, for instance, the English CFGs derived from the Penn TreeBank (PTB) (Marcus et al. 1993). 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
0922131281121131222
31119115291933113 38311 5011 111112221111111111121111111
11212199292222222333333 3221322111 1921 22222223333111222 92212222222222222222 12 220.
that is in 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 il.
Generally, the difficulty of CFGs scales with the average length of the strings. For instance, the average length of a CFG in our cfg3 family is over 200, whereas in the English Penn Troebank (PTB), is only 28. However, the difficulty of CFGs may inversely scale with the number of Non-Terminal/ TerrinallTTerrn (NT/T) symbols. Having an excess of NT/T symbols (recall the RB JJ or JJ PP examples mentioned earlier). This is why we mininized the nunber of NT/T symbols per level in our cfg3b, cfg3i, cfg3h, cfg3g, cfg3f construction. For comparison, we also considered cfg3el, cfg3e2, which have many NT/T symbols per level. Figure 4 shows that such CFGs are extremely easy to learn.
simplify the parsing of the string using greedy approach
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 famálies of synthetic CFGs (cfg8, cfg9, cfg0). Examples from these 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 (Marcus et al. 1993). To make experiment run faster, have removed all the CFG rules that have appeared fewer than 50 times in the
39

---

Published in Transactions on Machine Learning Research (12/2025)
Get-1.1 1-1-66
get-4.2 Got-4-2-16
2-16
2pt 16
901-444
401-444-16
Sot-644
6-4-1
991-2-2-2
9ot-42.
4-232
9p
9pt-6.2
33
4-4-2
32
Sph-2
BPh-2-2444
9pt-4-2-4
2-4424444
9PI-444
9p1-440
446-644444
901-6-6-44
8-64
net 12 12-64
gen acc
coto
99.1
09.5
99.7
90.8
CUTIO
98.3
97.5
99.3
98.8
99.8
99.9
(a) generation accuracies for cuts c and c= 10
1941
(b) Kl-divergence
truth
1et11-1-16
9pt-4-2-16
2ot-2-411
9Pt-444
4-1
gPL
6-4-1
901-2.2
2-332
9Pt-4-2.3
901-6-2-32 3-32
901-2.4 32
9pt.444
4432
901 801-6-4.32
90b224-64
9pt-4 64
gpt-24400 64
901-4 901-444-64
9pt 6-4-4
9ot-4-6-4
9pt-6-6-66
9P1-6-864
8pt-12-12644
32
entropy
61.1
62.0
58.7
58.3
59.1
57.8
58.4
57.4
57.3
57.2
56.9
572
model size
12K
68K
135K
235K
335K
135K
235K
335K
468K
864K
13M
468K
864K
17M
3.3M
4.9M
7.3M
10.9M
19.2M
85.5M
(c)
entropy and model size
Figure 30: Real-life PTB CFG learned by GPTrot of different model sizes.
RPH-1.1 9P1-1-1-16
2P1-4-2-16
921-2 921-24411
16
18144411
921
801-4-411
16
720-2-2.32
92h
6-232
921
32
404-444 32
921
484-44411 32
2:444
9o1-4-264
Dot
got
4464
Got 4
44444
Gol 4 6-64
1011-6-0 4-4644
Got 4-2-44-44
Spc 12-12-4
outo
0.0
0.0
0.0
0.4
0.0
0.0
0.4
1.0
01
17
8.7
0.0
1.0
0.2
5.5
34.3
11.3
47.0
56.8
97.8
cut10
0.0
0.0
0.0
2.1
188
0.0
0.4
1.1
0.1
1.7
8.9
0.0
1.0
0.3
5.6
34
1
11.3
47.1
56.7
97,8
Figure 31: By contrast, small GP model sizes cannot learn the cfg3f data (compare to Figure 30
data, 23 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 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 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 implicil CFG and studied it in Section 6.1. short, adding bag of words does not increase the learning difficult a CFG; the (possibly overlapping) vocabulary words will be simply encoded the embodding 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-E-l-d denote an élaayer, h-head, d-dim-per cemn-per-head head GPTrot (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 (with the same pretrain parameters described in Appendix A.3), that is, we compute the generation accuracy, completion accuracy (with cut 10), the output entropy and the KL-divergence. We report the findings in Figure 30. In particular:
Even 135e-sized GPT2 (GPT-2-4-16) can achieve generation accuracy 955% and have KL divergence less than 0.01. (Note the PTB CFG has 30 terminal symbols so its KL divergence may appear larger
23These large set of rare rules, each appearing with probability I 0.2%. We evaluating whether the generated sentence belongs to the CFG, process that requires CPU-intensive dynamic programming. To make the computation time tractable, remove the set of rare rules.
Note that cfg3 does not contain larger transformer and extended training time. also complicates the investigation of transformer's inner workings if these rare rules are perfectly learned.
rules either. Including such rules complicates the CFG learning process, nocessitating
40

---

Published in Transactions on Machine Learning Research (12/2025)
CPT
G71,9)
GPT
JM
GFT.14
-944
59.6
22.8
09. 92.2
29.0
25.3
000 22.
00.3
28.3 09
22.2
00.9
50.0
87.4
$7.5
00.2 28.
002 22.
38.5
generation
29.3
25.2
294 92.4
27.4 29.2
96. 26-5
006 02.3
20.4 90.4
28.5 59
92.5 50.4
20.4 90.5
15.7 59.7
52.3
59.6
90.5 28.7
99
92.5
297 20
22. 15.6
154
923
923
974
936
23.7
24.4
(2.0
98.7
90
p27
10.1
96
28.9
59
22.7
29.8
22.
28.
293
92.
20.8
20.7
cu20 cuto ar2t est ox23 cut cu20 culo cu12
cu0 cu200 ont 5825
an cu00 cuo c.50 out 5210
cat ou23 cue cu20 cut an15 c: ox21 aet 0223
Figure 32: Generation accuracies for c/g8/9/0 data family; suggesting our results also hold for unbalanced frees with len-1 rules.
than that of 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 samples, we estimate the entropy of the ground truth PTB CFG is around 60 bits, and the output entropy of those learned transformer models are also this magnitude.
By contrast, those small model sizes cannot learn the cfg3f data, see Figure 31
G.2 More Synthetic CFGs
Remember that the 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 transformer learning such language. We introduce three new synthetic data families, which we refer to as cfg8/9/0 (cach with five datasets, totaling 15 datascts). These are all "unbalanced" CFGs, which support length-1 rules 21 Specifically, the cfg0 family has a depth of 11 with rules of length 1 or 2, while the cfg8/9 family has depth 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.
For this TCLR submission, we have included all the trees used in the supplementary materials. Below, we provide descriptions of how selected them.
CFG8 family. The cfg8 family consists of five CFGs, namely cfg8a/ fig8a/b/c/d// b/c///e. They are constructed similarly to cfg3b/i/h/g/ with the primary difference being that we sample rule lengths uniformly from {1, 3] instcad of {2,3]. Additionally,
In cfg8a, we set the degree RR(a)] = 2 for every NT a; we also ensure that in any generation rule, consecutive pairs of terminal/ terminal symbols are distinct. The size is (1, 3, 3, 3, 3).).
In cfg8b, we set [a()] 2 for every NT a; we remove the distinctness requirement to make the data more challenging than cfg8a. The size is (1,3, 3,
In cfg8c, set [R(a)] (2,3) for every NT to make the data more challenging than cfg8b. The size is (1,3,3, 3, 3,
In cfg8d, we set [R(a)] = 3 for every NT We change the size to 3,, because otherwise random string would be too close (in editing distance) to this language.
In cfgge, we set [R(a)] E (3, 4) for every NT a. We change the size to (1,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()) 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 perform linear probing this dataset, as the per-symbol NT information is mostly non-unique 25
CFG9 family. Given the ambiguity issues arising from the 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.
When length-1 CFG rule is applied, can merge the two nodes at different levels, resulting in "unbalanced" CFC. 2 contrast, the 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 whole, the NT information per symbol can be uniquely determined with a high probability (if using for instance dynamic programming).
41

---

Published in Transactions on Machine Learning Research (12/2025)
prodict NY ancestor (%a)
GPT
GPT
GPT uni
baswire (GPT) (andd)
100
100
100
1,0
100 100
100
100
100
100
100
100
100
100
63.9
71.8 94.1
64.5
99.9
100 100
99.9
99.9
100
100
1.0
59.9
99.9
100
100
99.9 09.4
100
100 102
19.9 99.9
100 100
100
100
100 100
61. 02.6
62.0 41.0
0/3
$4.6
99.8
99.7 99.6
69.7 98.0
69.7
99.8
1.00
59.7 99.6
7 99.0 100
99.7 99.8
98.0
69.8 100
59.7 99.9 96.
69.9
100
100
99,9 100
66.4
66.6
06.4
69.7
96.7
100 29.7 99.5 99.4
100 MA.7 39.3 09.3 19.
100 99.7 18.5 93.4 90. 130 19.8 99.5 PM.7
100 09.5 99.5 93.5 V9.7
100 99.8
19.5 99.9
62.4
59.6 75.1
94.1
90.5 95.5 95.0 95.9
99.1 MB.5 M5.3 05.2 94.
19.3 98.6 96, 6 95.3 95.0 19.1 95.7 96.1 95.3 94.6
19.2 98.8 96.3 95.5
96.4
96.9 95.9
52.0
54.4 672
NT6 MTS NT4 NT3 N72 NT6 NTS MT4 KTS NT2 NTS NTS NT4 NTB NT2 NTS KTS NT4 MB NTZ NT6 NTS NT4 NT3 K12 NT6 MTS NT4 KTB M72 NT6 NTS
NT4 NT3 NT2
Figure 33: Same as Figure but for the cfg9 family. After pre-training, hidden states of generative models implicitly encode
the NT ancestors information. The NT; column represents the accuracy of predicting 5g, the NT ancestors level E. This suggests our probing technique applies more broadly.
To accomplish this, we first adjust the size to 4,,4,4,444,44444 then we permit only one NT per layer to have a rule of length 1. We construct five CFGs, denoted as cfgga/b/c/d/e,, and their degree configurations (i.e., R(a)) are identical to those of the cfg8 family, We then employ rejection sampling by generating 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 cfg9e are illustrated in Figure 29. We will conduct linear probing experiments on this data family.
CFGO family. Since all the CFGs above support rules of length 3, we have focused on L 7 to prevent the string length from becoming excessively long, 26 In the cfg0 family, we construct five CFGs, denoted as efg0a/b/Ca b/c/d/e. All of them have depth of I, = 11. Their rule lengths are randomly selected from (1, 2] (compared to {2. 3) for cfg3 or {1, 3} for cfg8/9). Their degree configurations (i.e., R(a)) are identical to those of the cfg8 family. We have chosen their sizes as follows, noting that we have enlarged the sizes as herwwse a random string would be too close to this language:
We use size 31, 4, 4, 4, 4, 4, 4, 4, 4] for cfg0a/b.
We use size [1,2, 4, 5, 6, 6, 6, 6, 6 for cfg0c.
We use size 1,, 3, 6, 8, 10, 11] for cfgod/e.
Once again, the CFGs generated in this manner are globally ambiguous like the cfg8 family, so we cannot perform linear probing on them. However, it would be interesting to demonstrate the ability of transformers to Iearn such CFGs.
Additional experiments. We present the generation accuracies (or the complete accuracies for cut. 20) for the three new data families in Figure 32 It is evident that the cfg8/9/0 families can be learned almost perfectly by GPT2-small, especially the relative/rotary embodding ones.
As previously mentioned, the cfg9 data family is not globally ambiguous, making it an excellent synthetic data set for testing the encoding of the NT ricestor/boundaae information, similar to what we did in Section 4. Indeed, we replicated our probing experiments in Figure 33 and Figure 34 for the cfg9 data family. This suggests that our probing technique has broader applicability.
H More on Uniform Attention
In Result 1, we observed that GPTuni (uniform attention) performs surprisingly well signifiaiill outper- forming the original 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 GPT..i lacks query and key matrices, its per-layer parameter count is approximately 10d (for hidden size d), compared to 12d for vanilla GPT. Thus, a parameter-matchen comparison would be GPT(12, 768) (12 heads, 768 dimensions) versus (8, 840) (8 heads, 840 dimensions). For completeness, we also compare with other natural baselines such as GPT(8, 1024) and GPT(12, 936). All experiments are sunmarized in Figure 35
Naturall, larger transformer would be capable of solving such CFG learning tasks when the string length exceeds 1000; have briefly tested this and found it to true. However, conducting comprehensive experiments of this length would be prohibitively expensive, so we have not included them this paper.
42

---

Published in Transactions on Machine Learning Research (12/2025)
(diagonal mosiking)
GFT
p4s
b304 ee (MPT mvvii
66.2 97. 04.8 100 100
44 N7. 4EA 103 L00
16.4
100 100
60 57
10 100 102
66 97
320
100 100 143
Fer 763
66.
0441
00.4 w
V7 06.0
14
00.0000000
10.2
67 06
16. 91 60
004 99.
94 66. 94.
07 69.
100 100
99.4
97
07.4
97.4
80.3 01.5
VTG KT5 KT6
MT
KT
MT
NTS
NEA
MT2
KT6
MTS
MTC
KT M72
NT6
NTS
N76
MT
K72
KT5
K74
MT
N77
NTS
MTS
MT4
KTV
MT2
KT6
KTS
MTs NT N72
(erdllggon (aikking))
50PT
300 15-3 1.00 135 100 59.9
103
103 100
102
93.9
100
150 100 120
33.9 300
100 102 100
200
120
100 300
597
07. 93- 96.
100e 59.1 99.7
130
15.7
303
100
18.199.9
99.7
100 100
06.3
93
598
100 107
251
99.7
300
320
100 300
90.6
988
177 (5 00,0
F 38. 97 28.8 99 28 98.8
97.7
79
91.7
95.7 90.
56.9
26
96.7
97.6
99.
99.9
12. 72,0
MTS
W72
His
Figure 34: Same as Figure 7 but for the cfgè data family. Generative pre-trained transformer encodes NT ancestors almost exactly at NT boundaries. The NT, column represents the accuracy of predicting se(i) at. locations with by(() = 1. This suggests our probing technique applies more broadly.
cfgar
ctyle
(hhaad112240m
(Shead) 4024dim
-000033
GPT_uri (Hhead.10244mm (dim))
96.8%
91.7%
98.7%
93.7
GPT_un| (8 head, 102 458mi
-3.00133
-3.00003
-0.00233
-3.00337
4. 0.00006
GPT
TheaddM6amm
57.6%
67
76.5%
77.15
06.9%
97.
29
56.0%
86.0%
55.2%
98 4%
GPT
[Bneac, F35dmm)
4,09612
10.0632
0.00095
+.00467
0. 0.00149
CPT
122n F3namm)
59.5%
58 9%
51.3
05.05
47.4%
97-476
15.0%
80.0
97.0%
90.15
GPP
122haad 536ddmm
40000
40,00228
-2.00344
4. 0.00172
(Shaad 840din)
96.0%
96.55
40.5%
93.0%
93.5%
93.3%
91.5% 90.0%
(40dmm)
-5. -5.00318
3.00074
-0,00233
-3,00368
00.00091
27.0%
0.00443
0r50
cu150
cul
cuiso cuto cui50
cut0
cu.o
cL00
cu00
cu00
Figure 35: Performance comparison between GPT.ni (uniform attention) and vanilla GPT (absolute positional embedding). Left: generation accuracy; Right: KL divergence against ground truth. Each model is trained with 5 random seeds. We report the median for GPTuni and the beat run for GPT.
At high level, group six 12-layer models by parameter scale:
CPT(12, 768) x GPTuni(8, 840) < (8, 1024) x GPT(12, 936) > GPT(8, 936) << GPT(8, 1024)
Yet, across all settings, Figure 35 consistently shows that uniform attention GPT outperforms vanilla 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 ALiBi Press et al. (2021) and especially H-Alibi Jelassi et al. (2024), which apply hard attention cutoffs-whers each attention head attends only to a fixed-size window. This is structurally similar to our CPTuni, where the window size varies per head.
These findings also motivate our follow-up work (Allen-Zhne 2025a b), where we incorporate short-window uniform attention as a lightweight architectural component to further improve Transformer performance without increasing parameter count significantly.
References
Zeyuan Allen-Zhu. Physics of Language Models: Part 4.1, Architecture Design and the Magic of Canon Layers. In Proceedings of the 39th Conference on Neural Information Processing Systems, NeurIPS 225, 2025a. Full version available at https://ssrn. wtt./ooa///aeeeee abatracttccct020300
Zeyuan Allen-Zhu. Physics Language Models: Part 4.2, Canon Layers at Scale where Synthetic Pretraining Resonates in Reality, 2025b. URL https://ppyyiics allen-zhu aatt:t44rrciiieetturdddssspp/ppp
Code released at
Zeyuan Allen-Zhi and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. In COLT, 2023. Full version available at http://arxiy http:///aariv.oor/ab/////00
arg/ 244100000000001
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, 1CML 2024, 2024. Full version available at https: //tts////aaa.ccoo com/ abstract=5220623
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, TCLR 2025, 2025a. Full version available at
43

---

Published in Transactions on Machine Learning Research (12/2025)
attpss//esrt..cmm//ssrrtttttta comm/absttactt=256611
Zeyuan Allen-Zhu 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 hattp::/ssraa http:///sssn..ccoaaaeeeeeo aonnabbbtractt5506117
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via overpparameterization. In ICML, 2019. Full version available at http://arxiv.orrg hwtgg/abb/8811.... 03962
Sanjeev Arora and Yi Zhang- Do gans actually learn the distribution? an empirical study. arXie preprint arXiv:1766. 08224, 2017.
David Arps, Younes Samih, Laura Kallmeyer, and Hassan Sajjad. Probing for constituency structure in neural language models. erxiv preprint erXiv:2204. 2022.
James K Baker. Trainable grammars for speech recognition. The Journal of the Acoustical Society of America, 65 (S1):S132 S132, 1979.
Sid Black, Stella Biderman, Eric Hallahan, Quentin Authony, 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-200B: An open-source autoregressive language model. In Proceedings of the ACI Workshop on Challenges & Perspectáves in Creating Large Language Models, 2022. URL https: httpss//arxiv..oo www..og///./.../.o......o..a.a/a halaa/2244.066 06745)
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 chomssy hierarchy. In ICLR, 2023.
Brian DuSell and David Chiang, Learning hierarchical structures with differentiable nondeterministic stacks. In ICLR, 2022.
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.
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention. arXiv preprint XxXi:2006600654 2020.
John Hewitt and Christopher D. Manning. A structural probe for finding syntax in word representations. Tn Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Lin- guisties: Human Lenguage Technologies, Volume 1 (Long and Short Papers), pages 4129-4138, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/w1/N19-111 URL https: //aclanthology. org/N19-14/0
Samy Jelassi, David Brandfonbrener, Sham Kakade, and Eran Malach. Repeat after me: Transformers are better than state space models at copying. arXie preprint arXiw:240 01032, 2024.
Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional trans- formers for language understanding. In Proceedings of NAACL-HLT, pages 4171-4186, 2019.
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, (0748)):0046-30055 2020.
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large amnotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313-333 1993. URL BuRLlattss//accaattallggg org/J93- 2004
Rowan Hall Maudslay and Ryan Cotterell. Do syntactic probes probe synlax? experiments with jabberwocky probing. arXiv preprind w=Xi::216600255, 2021.
Milad Moradi and Matthias Samwald. Evaluating the robustness of neural language models to input perturbations. arXiv preprint arXi::2108.1228 2021.
Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher D Manning. Characterizing intrinsic composi- tionality in transformers with tree projections. In ICLR, 2023.
Neel Nanda, Lawrence Chan, Tom Liberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. arXiv preprint arxiv:2301, 05217, 2023.
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.
OpenAL. Gpt-4 technical report, 2023.
Matt Post and Shane Bergsma. Explicit and implicit syntactic features for text classification, In Proceedings of the
44

---

Published in Transactions on Machine Learning Research (12/2025)
51st Annual Meeling of the Associalion for Computational Linguistics (Volume 2: Short Papers), pages 866 872, 2013.
Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. Xiviv preprint 0rX.v:2108.124000 2021.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Tlya Sutskever. Language models are unsu- pervised multitask learners. 2019.
Itiroo Sakai. Syntax in universal translation. In Proceedings of the International Conference on Machine Translation and Applied Language Analysis, 1961.
Hui Shi, Sicun Gao, Yuandong Tian, Xinyun Chen, and Jishen Zhao. Learning bounded context-free-grammar via Istm and the transformer: Difference and the explanations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8267-8276, 2022.
Michael Sipser. Intruduction to the Theory of Compulation. Cengage Learning, 2012.
Jianlin Su, Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position
embedddngg, 2021.
Lifu Tu, Garima Lalwani, Spandana Gella, and He. empirical study on robustness spurious correlations using pre-trained language models. Transactions of the Association for Computational Lénguisties, 8:621 633, 2020.
David Vilares, Michalina Strzyz, Anders Sogaard, and Carlos Gómez-Rodriguez, Parsing as pretraining. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, pages 9114-9121, 2020.
Kevin Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. Interpretability the wild: circuit for indirect object identification in gpt-2 small. arXie preprint 0rXie:2211.00530 2022.
Zhiyong Wu, Yun Chen, Ben Kao, and Qun Liu. Perturbed masking: Parameter-free probing for analyzing and interpreting bert. In Proceedings of the 58th Anaval Meeting of the Association for Compulational Linguistics, pages 11166-1170 2020.
Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of Language Models: Part 2.1, Grade-School Mathi and the Hidden Reasoning Process. In Proceedings of the 13th International Conference on Learning Representa- tions, TCLR 2025, 2025a. Full version available https: //spa:///arn...a http:///aaa..aaaaaaeeee/e/eeeeea 2b55ract==2225069
Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeynan Allen-Zhu. Physics of Language Models: Part 2.2, How to Learn
From Mistakes Grade-School Math Problems. In Proceedings of the 13th International Conference on Learning Representations, ICLR 2025, 2025b. Full version available at https://sstn: com/ mtmm/abbsract622661111
Shizhuo Dylan Zhang, Curt Tigges, Stella Biderman, Maxim Raginsky, and Talia Ringer. Can transformers learn solve problems recursively? arXiv preprint arXie:2905. 14699, 2023.
Haoyu Zhao, Abhishek Panigrahi, Rong Ge, and Sanjeev Arora, Do transformers parse while predicting the masked word? Xiu prepriut ar Xro:2333 0811 2023.
45


Reviews:
[{"review_id": "CPX8Joemdh", "reviewer": "Reviewer_CZQJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors train a number of transformer models on synthetic fixed-depth (non-recursive) context-free grammars (CFGs), and then present some analyses of what features those models have learned. Specifically, they find that\n(1) transformers can be trained to fairly high accuracy on the synthetic CFGs,\n(2) a \"multi-head linear probing\" layer can be trained to recover nonterminal symbols from the learned embeddings (but not from random embeddings),\n(3) attention patterns are consistent with the hypothesis that the models have learned to perform a dynamic-programming-like algorithm,\n(4) the models can be trained to recover from noise in the CFG generation process.\n\nOverall, this provides evidence that sufficiently-powerful transformer models _sometimes_ learn non-recursive dynamic-programming-like algorithms, and can identify regularities of the underlying CFG based only on terminal token sequences.", "claims_and_evidence_yn": "No", "claims_explanation": "Most of the claims made by the paper seem correct and adequately supported by evidence. (I am not sure how much these results should tell us about the behavior of real-world transformer models, but the authors are clear about these limitations, and this work does provide evidence that transformers can learn these kinds of algorithms given the right data.)\n\nHowever, I do have a few questions and concerns related to the correctness and clarity of some of the claims:\n\n## Details and interpretation of multi-head linear probing layer\nSection 4.1 introduces a \"Multi-head linear probing\" layer, which appears to be a per-token linear layer projected through some sort of attention matrix. I found this section confusing and am not sure how to interpret the results, or what claims can reasonably be made about what this probe learns.\n\nAs I understand it, the attention matrix is _fixed_, and is not supposed to depend at all on the input $x$ (since the authors want it to be \"linear\"). However, the attention matrix depends on token position, which depends on the length and content of $x$. Does this mean that the attention matrix is directly optimized to achieve high accuracy for a fixed input $x$?\n\nMy understanding is that (linear) probes are usually trained on a training set, and then subsequently evaluated on a held-out test set, to avoid overfiting and ensure that they are actually probing for a general concept. But this does not seem possible with this probe, making me question what these results are showing. If you allow the linear mapping to be learned separately for each $x$, it seems like there should _always_ be some linear mapping that achieves 100% training accuracy.\n\nIn practice there is clearly _something_ nontrivial happening, since the accuracy for trained transformer models is higher than for untrained ones. However, if the probe is being trained separately for each $x$, it seems plausible to me that this is primarily an artifact of the inductive biases of the specific probe architecture used, rather than being fundamental to the representation learned by the model. It would be good to clarify this.\n\n## Complexity of the synthetic CFGs\nPage 4 states \"Typically, the learning difficulty of CFGs inversely scales with the number of NT/T\nsymbols, assuming other factors remain constant, because having **more** NT/T symbols makes the language less ambiguous and more easily parsed using greedy\". However, page 5 states \"Less ambiguous CFGs (cfg3e1, cfg3e2, as they have **fewer** NT/T symbols) are easier to learn\". These statements seem contradictory. Which is correct? (or am I misunderstanding?)\n\n## Attention diagrams\n\nI found Figure 8 to be quite difficult to interpret. It seems that the cells being visualized represent specific offsets where we might expect a dynamic programming algorithm to attend or not attend, and the diagram is showing whether the model actually attends to these locations?\n\nOverall it was not clear to me what claims were being made in this figure and the associated analysis in section 5. My best guess for Figure 8a and 8b is that we should expect a true DP algorithm to attend at $\\delta = 0$, and we do actually observe this, which is evidence that the attention may be implementing something like a DP algorithm? But this is not obvious from the way section 5 is written. Additionally, I have no idea what Figure 8c is meant to be evidence of, or whether or not the findings are consistent with what one would expect.", "audience_yn": "Yes", "audience_explanation": "These experiments give some interesting insights into how transformers are capable of tracking hierarchically-structured sequences, and I think some members of the community would find them interesting. (I am unsure how representative these tasks are, but I think it is sufficiently interesting for publication in TMLR.)", "requested_changes": "## Clarify how the multi-head linear probing layer is used\nI think the authors should clarify the way that the multi-head probing layer is trained, and in particular whether it is (over)fitting to a specific input or whether it is shared between inputs. This also affects the claims that can be reasonably made based on how well the layer works.\n\nIf it is optimized against a single input, I think the paper should state this clearly, and avoid claiming that this is a linear probe in the same sense that \"linear probe\" is typically used in the literature. (The final transformation being linear is not a meaningful restriction if it is being fit to a specific example; if you include the optimization steps for each example the full extraction process is highly nonlinear.) If it is trained on one set and evaluated on another, the paper should describe this process.\n\n## Explain claims in Section 5 and meaning of figure 8 more clearly\nI think two things that would improve this part would be:\n\n1. Explain more clearly what the hypothesis is that you are testing with each of these experiments; what would we expect to see (and why) if the hypothesis is true, and what would we expect to see (and why) if the hypothesis is false / an alternative hypothesis is true?\n2. Ground the results in an actual sequence, and show what the attention matrices actually look like, rather than just showing very small offset slices of 3- or 5-token windows out of context (which are difficult to interpret on their own).\n\n## Address some issues of how this work is positioned relative to prior work\n\nA few of the references to prior work in this paper are strangely worded, and some of the statements about prior work seem unreasonable relative to the current submission. I think the authors should reword these to better contextualize this work.\n\n- For induction heads:\n  - Why quote \"hypothesized\"?\n  - It also seems inappropriate to quote and emphasize “don’t have a strong framework for mechanistically understanding”, because this work also does not provide such a framework: Olsson et al. (2022) were referring to complex heads learned on real-world data which have more complicated behavior than a simple induction head, and this current work does not have any experiments with real-world data or investigate behavior of any particular heads at all.\n- For \"interpretability in the wild\":\n  - I am unsure about the claim \"there exists very simple rule-based algorithm to achieve the same\" as it relates to the motivation for the rest of the paper. It is not obvious to me that the circuit needed to implement an algorithm for a fixed depth CFG is much more complex than the indirect object identification circuit?\n  - The footnote makes a very strange statement \"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 online six months after Wang et al. (2022).\" Why is this relevant? The current paper tackles a totally different setting than \"interpretability in the wild\", and does not reverse engineer a _natural_ end-to-end behavior (in the sense of being \"in the wild\") because it focuses entirely on toy tasks.\n\n## Fix other smaller issues\n- Please fix inconsistency about how CFG difficulty scales with the number of NT/T symbols.\n- The paper occasionally makes statements like \"A coding grammar (like python) can be parsed using greedy without ambiguity.\" What does it mean to \"use greedy\"? I assume you mean \"using a greedy algorithm\"? Please fix this to be explicit.\n- What do you mean by \"that may not be information-theoretically possible\" in Figure 6?", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "m1U8DE1hsg", "reviewer": "Reviewer_BL2E", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates whether and how autoregressive Transformers, trained solely on terminal tokens without access to parse-tree supervision, can implicitly learn context-free grammars. It shows that GPT-style models can learn to generate from several synthetic, often locally ambiguous and non-trivial CFG families, producing strings with high validity and close distributional match to the target languages. Probing and interpretability analyses—such as linear probes that recover nonterminal structure and attention patterns consistent with dynamic-programming-like information flow—provide strong evidence that the models internalize aspects of the underlying generative process rather than relying on rote memorization or lookup tables.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The core claims are backed by careful measurements and ablations on well-specified synthetic CFG benchmarks. However, a few conclusions (especially the DP interpretation) are suggestive rather than strictly causal, and external validity to natural language is explicitly limited.\n\n* **Evidence of learning:** High completion accuracy across prefix cuts, strong generative diversity (entropy/birthday bound), and low next-token KL indicate generalization beyond memorization.\n* **Internal structure:** Multi-head linear probes (full/diagonal/tridiagonal) nearly perfectly recover nonterminal ancestors and boundaries; encoder baselines fail on deeper NTs.\n* **Attention & DP:** After removing position bias, attention concentrates on adjacent NT-end tokens, aligning with DP-style information flow (alignment, not proof).\n* **Robustness & extensions:** Noisy-prefix pretraining and low temperatures boost robust accuracy; implicit CFGs yield structured embeddings.\n* **Baselines:** Relative/rotary ≥ vanilla; uniform surprisingly strong.", "audience_yn": "Yes", "audience_explanation": "This paper is mostly for readers interested in mechanistic interpretability and algorithmic reasoning in LLMs, best read with familiarity with CFG notation and DP parsing.", "requested_changes": "1. For Result 3, please detail the exact DP used to compute grammar conditionals and consider adding per-prefix likelihood/calibration curves in addition to the KL summary\n\n2. Define NT, “NT boundary,” $s_\\ell(i)$, $b_\\ell(i)$, and the probe $G_i(x)$ in words and symbols before Section 4; many readers won’t infer these from the equation alone. Link each symbol to where it first appears.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OXCLXw4Qfd", "reviewer": "Reviewer_vyuo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to investigate the learning of hierarchical structures in transformers, with the goal of understanding how large language models solve complex tasks with deep reasoning and computation chains. To that end, the work generates a large number of synthetic context-free grammars (CFGs), which are inherently hierarchical in nature. Parsing such CFGs can require long range reasoning and handling local ambiguity, since the next symbol in a CFG-generated string may only be uniquely determined by tokens that occurred hundreds of tokens on the \"past.\" The paper validates, on a GPT2 small architecture, that a set of synthetic CFGs are almost perfectly learnable, and are likely generalizing rather than memorizing. Further experiments suggest that information about the CFG (i.e., parent \"nodes\") are extractable from GPT2's internal representations via linear probing, and further analysis of the attention mechanisms suggest that they are critical to learning CFGs.", "claims_and_evidence_yn": "No", "claims_explanation": "I see design and clarity issues in the current manuscript. First, on the design side, Appendix B.1 shows that the CFGs are non-recursive: a symbol can never expand to itself. This is subtle, but without \"true\" recursion the proposed CFGs reduce to finite languages — a much smaller class of languages and I'd expect this to be easier to learn for models in general (cf. Chomsky hierarchy — all finite languages are regular). However, the significance of this design flaw is unclear without a better sense of why CFGs are the right level of analysis.\n\nOn clarity — it is very difficult to follow Results 6-9, because it's unclear what we expect to see. The results feel more exploratory and I have trouble parsing what the paper is trying to show, especially Figure 8. Results 10-13 seem a little more orthogonal to the main paper as well and I was confused about their placement.", "audience_yn": "No", "audience_explanation": "The relevance/significance of this work to the ML community is unclear. While the motivation in the intro is given as: \"Is there a setting for us to understand how language models perform hard tasks, involving deep logics / reasoning / computation chains?\" It's unclear the extent to which CFG is the correct abstraction for this. In addition, \"hard\" is underdetermined, as is \"deep logic/reasoning,\" so it is hard to follow formally what question the work is really trying to answer. In other words, why is it interesting that a model can or cannot learn to recognize a CFG? In what way does that give us a \"bridge\" into \"interesting\" tasks (as determined by the literature, or other practical justifications)? \n\nThe paper also uses a rather outdated model for experiments (GPT2 small), though this is OK for the purposes of building a mechanistic understanding of how models learn CFGs. \n\nUltimately, without a stronger connection to current LLM problem-solving work it's unclear where this work fits in the ML community.", "requested_changes": "**Critical:** Please answer the following questions and revise such that these explanations are readily available in the text. \n* **MOST CRITICAL:** Why CFGs at all? Why are they an appropriate abstraction for (L)LM problem solving/reasoning, OR why is it interesting that models can recognize CFGs? \n    * I'm looking for something to convince me that a CFG-based abstraction for problem-solving in LLMs is (1) salient/sufficiently faithful, and (2) relevant to understanding problem-solving in LLMs, preferably with concrete examples. It is difficult for me to advocate that this work is relevant to the TMLR community otherwise, so a thorough & convincing answer here could really improve my assessment. \n* Does the non-recursive/finite formulation of the CFG affect the conclusions? \n* Why anchor to a DP based formulation of problem-solving? This is just one problem-solving strategy; what is its relevance to (1) the learnability of CFGs (i.e., must a model use DP to recognize a CFG) and (2) broader (L)LM problem-solving in general? \n* What is an NT \"boundary\" intuitively, and why are those interesting locations to analyze (cf. Results 4-5)?\n* What is the purpose of Results 6-9, and intuitively, what results should I expect to see? \n\n**Important:** It would be nice to get clarity on the following design decisions: \n* What's the motivation for choosing the GPT2 architecture, as opposed to a more recent open-weight model (e.g., Llama3 family, Qwen2.5 or 3)?\n* All of the synthetic CFGs seem to have 3 terminal symbols with 2-3 expansion rules per non-terminal symbol, with the main difference between CFGs being the \"depth\" of the CFG. While that is one possible axis of CFG difficulty, why not consider others? \n    * E.g., more terminals, more complex expansion rules, recursive rules, or heterogeneity in the number of rules per non-terminal (e.g., perhaps a \"3\" usually is generated by a \"5\" but occasionally by a \"4\" — does the model just rely on distributional statistics and predict the parent is a \"5\"?). \n    * Without justification for why this set of CFGs is sufficient, or extensions as described above, the claims seem to apply to a subclass of specific CFG rather than CFGs in general. \n* What's the justification for the noisy CFG experiment? It's unclear why this experiment is central for the main claims of the paper, and I might suggest a move to an Appendix. \n* \"Thus, human languages may be too easy for our interpretability purpose.\" — I think this claim rests on a misspecified CFG for human language. I believe this is true if we're using a CFG over grammatical units (e.g., parts of speech, phrases), but not over *words.* Certain words could appear in a variety of phrases (e.g., \"run\" in an NP or VP) and introduce a similar ambiguity as seen in the synthetic CFGs. \n    * (strictly speaking — perhaps the authors mean that human *grammars* are too easy? Grammar != language, so that is somewhat more believable, but I don't have the expertise to verify.)", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)