PaperlayerView exact revision on arXiv

Source-linked AI summary

Physics of Language Models: Part 1, Learning Hierarchical Language Structures

Zeyuan Allen-Zhu, Yuanzhi Li

arXiv:2305.13673v4cs.CLcs.AIcs.LG

TL;DR

To understand how language models perform deep reasoning over hierarchical structures, the paper studies synthetic CFGs that require global parsing. It finds that GPT learns these grammars and exhibits DP-like internal computations, with perturbing training data improving robustness to corrupted prefixes.

  • Problem

    Mechanistic understanding of language-model reasoning on tasks with clear algorithmic solutions remains limited, despite its importance for studying complex computations.

    Source: §1 · p. 2

  • Method

    The authors train GPT on controlled synthetic CFGs whose hierarchical structures provide a setting for probing DP-like computation.

    Source: §1 · p. 3

  • Results

    GPT learns hierarchical CFG reasoning, and a 10% perturbation to training data significantly improves robustness to corrupted prefixes.

    Source: §1 · p. 4, §7 · p. 17

  • Takeaways & Limitations

    The synthetic CFG setting provides a controlled interpretability framework for studying hierarchical reasoning and valid continuations.

    Source: §7 · p. 16

    Synthetic CFGs do not capture the full diversity of language or intelligence.

    Source: §7 · p. 17

Abstract

from arXiv · show

Transformer-based language models are effective but complex, and understanding their inner workings and reasoning mechanisms is a significant challenge. Previous research has primarily explored how these models handle simple tasks like name copying or selection, and we extend this by investigating how these models 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 lengthy sentences (e.g., hundreds of tokens) that are locally ambiguous and require dynamic programming to parse. Despite this complexity, we demonstrate that generative models like GPT can accurately learn and reason over CFG-defined hierarchies and generate sentences based on it. We explore the model's internals, revealing that its hidden states precisely capture the structure of CFGs, and its attention patterns resemble the information passing in a dynamic programming algorithm. This paper also presents several corollaries, including showing why absolute positional embeddings is inferior to relative and rotary embeddings; uniform attention alone is surprisingly effective (motivating our follow-up work on Canon layers); encoder-only models (e.g., BERT, DeBERTa) struggle with deep structure reasoning on CFGs compared to autoregressive models (e.g., GPT); and injecting structural or syntactic noise into pretraining data markedly improves robustness to corrupted language prompts.

1 Introduction

The paper uses challenging synthetic CFGs to study how transformers reason over long-range, ambiguous hierarchical structures. GPT learns these grammars, while its representations and attention patterns reveal structure and DP-like computation.

1 Introduction

  • GPT learns the synthetic CFGs, with relative or rotary attention crucial for the more complex grammars.The authors use prefixes or a start token to test generated completions.Source: §1 · p. 3
  • Multi-head linear probes find that hidden states encode nonterminal information almost perfectly, unlike encoder models such as BERT.The CFG structure is not exposed during pretraining.Source: §1 · p. 3
  • Attention analyses identify position-based and boundary-based patterns associated with CFG regularity and periodicity.The paper introduces methods to visualize and quantify these patterns.Source: §1 · p. 3
  • Boundary-based attention links tokens to their closest CFG nonterminals across hundreds of tokens, resembling dynamic-programming information flow.The paper presents this as a mechanism for hierarchical structure reasoning.Source: §1 · p. 3
  • For implicit CFGs, GPT encodes terminal-symbol token-bag information directly in token embeddings.The paper describes these grammars as capturing structures such as word categories.Source: §1 · p. 3
  • A 10% training-data perturbation significantly improves robustness, and perturbed training produces a mode switch between grammatical and ungrammatical completions.The mode switch is also observed in Llama and GPT-3 (davinci003).Source: §1 · p. 4
  • The authors isolate and quantify DP-like computation in a setting requiring global parsing decisions where local heuristics fail.They position this as distinct from prior synthetic-grammar interpretability work [11].Source: §1 · p. 4

2 Our Synthetic Context-Free Grammars

The paper defines layered synthetic CFGs and uses them to study hierarchical structure under controlled conditions. Its chosen grammars are designed to be difficult to parse yet interpretable at distinct hierarchical levels.

2 Our Synthetic Context-Free Grammars

  • CFGs are defined by terminal and nonterminal symbols, a root, and production rules that specify a string distribution.The paper denotes a grammar as G = (T, NT, R).Source: §2 · p. 4

2.1 Definition and Notations

  • The seven depth-7 cfg3 grammars use length-2 or length-3 rules and generate sequences up to 729 tokens.Five hard datasets are ordered by increasing difficulty; two additional datasets are designated easy.Source: §2.1 · pp. 4–5

2.2 Why Such CFGs

  • Layered CFGs enable probing nonterminal symbols and attention at distinct depths, while the authors caution that their results do not cover all CFGs.The selected grammars are uniform for simplicity; results extend to distributions that are not heavily unbalanced.Source: §2.2 · pp. 5–6

3 Results 1-3: Transformer Can Learn Such CFGs

After autoregressively pretraining decoder-only transformers on synthetic CFG strings, the authors find that GPT variants other than the original absolute-embedding model can generate CFG-valid completions that are diverse and follow the grammar’s probability distribution. Relative or rotary positional attention performs better on harder CFGs, while vanilla GPT performs worse than GPTuni with uniform attention.

Results 1-3

  • The models are pretrained autoregressively on strings sampled from synthetic CFG languages, then evaluated on how well they learn those languages.Source: §3 · p. 6
  • GPT variants other than the original absolute-embedding model often generated CFG-valid completions that were diverse and closely followed the CFG probability distribution.The evaluation includes generating full sentences and completing prefixes.Source: §3 · pp. 6–7
  • Relative or rotary positional attention performs better on harder CFGs, while vanilla GPT performs worse than GPTuni with fixed uniform attention.The figure compares generation accuracy, entropy, and KL-divergence across CFG datasets.Source: §3 · p. 6, Figure 4 · p. 7
  • Birthday-paradox estimates give cfg3f at least 4 × 10^8 distinct sentential forms from levels 1–5 or 2–6, supporting the conclusion that completions are not merely memorized patterns.Source: §3 · p. 7
  • For distributional fidelity, the authors compare model next-token predictions with the CFG ground truth using KL-divergence estimated from 20,000 true-CFG samples.Source: §3 · p. 7
  • Matching a CFG’s next-token distribution is only a small step toward demonstrating DP-like reasoning; whether AdamW training yields such an algorithm remains an open question here.Source: §3 · pp. 7–8

4 Results 4-5: How Do Transformers Learn CFGs?

Pre-trained GPT hidden states encode CFG nonterminal ancestors and boundaries, while control models fail to recover deep structure. At NT boundaries, nearby hidden states retain ancestor information, linking the learned representations to dynamic-programming structure.

4 Results 4-5: How Do Transformers Learn CFGs?

  • The DP backbone comprises CFG subproblems whose verification certifies that a sentence belongs to the language, and the encoded NT information can support these values.The condition defining the backbone is sufficient, not necessary, for a subproblem to be parsable.Source: §4 · p. 8
  • The paper probes representations against classical CFG dynamic programming, whose straightforward implementation can be reduced from O(len^4) to O(len^3) using auxiliary nodes.The O(len^3) implementation applies to CFGs with maximum rule length 3.Source: §4 · p. 8

4.1 Result 4: Transformer’s Last Layer Encodes NT Ancestors/Boundaries

  • The study uses multi-head linear probes to test whether the final-layer states encode NT ancestors and boundaries.The probe uses several linear functions over hidden states to predict NT symbols; the section relates this structural information to DP-style reasoning.Source: §4 · p. 8, §4.1 · p. 9
  • Pre-training lets GPT hidden states almost perfectly encode NT ancestors and boundaries up to a linear transformation.The result is measured in the final transformer layer; Figure 5 reports ancestor-prediction accuracy by level.Source: §4.1 · p. 9, Figure 5 · p. 9
  • Randomly initialized GPT and DeBERTa fail to recover deep NT structure, especially at deeper levels and NT boundaries.DeBERTa is a BERT-style encoder; its recovery is weaker for levels close to the CFG root.Source: §4.1 · pp. 9–10, §4 · p. 9

4.2 Result 5: NT Ancestors are Encoded At NT Boundaries

  • At NT boundaries, diagonal or tridiagonal probes using hidden states at i or i ± 1 accurately predict NT ancestors.The boundary condition matters: ancestors are predicted at positions where bℓ(i) = 1.Source: §4.2 · p. 10, Figure 7 · p. 10, Figure 6 · p. 10
  • The same local masking is sufficient to predict NT boundaries, extending the local probe beyond ancestor labels.Figure 7 measures ancestor prediction at NT boundaries; boundary prediction is reported separately in Figure 19.Source: §4.2 · p. 10, Figure 7 · p. 10

5 Results 6-9: How Do Transformers Learn NTs?

GPT attention develops both position-sensitive and CFG-boundary patterns; boundary reads align with information flow in dynamic-programming parsing and generation.

5.1 Result 6: Position-Based Attention

  • Attention tracks relative token distance across heads at multiple scales, but position-only GPT variants outperform vanilla GPT without matching GPTrel.The paper also links positional information to learning CFG regularity and periodicity for generation.Source: §5.1 · p. 11

5.2 Result 7-9: Boundary-Based Attention

  • After subtracting distance bias, attention favors NT-end tokens and pairs, especially adjacent NT-end boundaries across hierarchy levels.The strongest weights occur at NT ends themselves, and tokens at one level favor their most adjacent NT ends at every level.Source: §5.2 · pp. 12–13

5.3 Connection to Dynamic Programming (DP)

  • Hidden states store DP parsing states, while attention links adjacent constituents in parsing and prior-constituent information in generation, consistent with DP-like computation.The authors say identifying one specific DP implementation is infeasible; they point instead to shared storage and recurrent-computation patterns.Source: §5.3 · pp. 13–14, Figure 10 · p. 13

6 Results 10-13: Extensions of CFGs

The paper finds that GPT learns implicit CFG terminal information in embeddings and that perturbed-data pretraining improves robustness, with generation behavior depending on prefix condition and temperature.

6.1 Result 10: Implicit CFGs

  • GPT learns implicit CFGs well, grouping embeddings for tokens in the same terminal subset to encode hidden terminal information.The terminal subsets can overlap, and token roles are not supplied to the model in advance.Source: §6.1 · p. 14

6.2 Results 11-13: Robustness on Corrupted CFG

  • ∼79%, 82%, and 60% robust accuracies follow perturbed-data pretraining across three perturbation types, versus ∼30% after clean pretraining.The paper reports that adding corrupted or low-quality pretraining data is beneficial.Source: §6.2 · pp. 15–16
  • Pretraining on corrupted data teaches a mode switch: correct prefixes mostly yield valid completions, corrupted prefixes yield errors, and no-prefix corruption probability is close to γ.Source: §6.2 · p. 16
  • Low generation temperatures yield high robust accuracy that is not sensitive to γ, including when all pretraining data are perturbed.The paper attributes this pattern to lower temperatures favoring more probable next tokens.Source: §6.2 · p. 16

7 Related Work and Conclusion

The conclusion connects GPT’s hidden states and attention patterns to dynamic-programming computations for CFG reasoning, while emphasizing both the controlled setting’s value and its limited scope.

7 Related Work and Conclusion

  • The study analyzes 100M-sized GPT-2 with context length over 300, identifying some head and hidden-state roles correlated with DP without assigning every neuron a function.Earlier interpretability work discussed simpler tasks or smaller architectures, while another study quantified tree-like representations during training.Source: §7 · p. 16
  • GPT-2’s internal states correlate strongly with dynamic-programming computations underlying parsing and generation on challenging synthetic CFGs.The paper presents this as a controlled interpretability setting for studying hierarchical reasoning.Source: §7 · pp. 16–17
  • The paper’s corollaries include relative and rotary embeddings outperforming absolute embeddings, effective uniform attention, encoder-only struggles, and improved robustness from structural or syntactic noise.Uniform attention motivated follow-up work on Canon layers [1].Source: §7 · p. 17
  • Synthetic CFGs provide well-defined compositional and hierarchical benchmarks but do not capture the full diversity of language or intelligence.The paper points to later work on math, reasoning, knowledge, and synthetic-data architectures.Source: §7 · p. 17

A.1 Dataset Details

The appendix details the synthetic CFG datasets, model variants, pretraining setup, and probes used to study learned hierarchical structure.

A.1 Dataset Details

  • The depth-7 CFG family includes five increasingly difficult primary datasets; cfg3f is near GPT2-small’s learning threshold under the stated setup.The authors note that still deeper CFGs would require a larger model and longer training.Source: §A.1 · pp. 17–18

A.2 Model Architecture Details

  • The experiments use 12-layer, 12-head, 768-dimensional GPT and compare relative-position and rotary variants with position-only and uniform-attention variants.The relative-attention and rotary implementations are called GPTrel and GPTrot; GPTpos and GPTuni isolate position-based attention.Source: §A.2 · pp. 18–19

A.3 Pre-Training Details

  • Pretraining uses 512-token windows and fresh CFG samples; the main setup runs 100k iterations, and the authors report similar conclusions with a finite 100-million-token set.They did not repeat each pretraining experiment or plot confidence intervals.Source: §A.3 · pp. 19–20

A.4 Predict NT ancestor and NT boundary

  • A multi-head linear probe predicts nonterminal ancestors and boundaries from hidden states; the pretrained model’s diversity pattern matches the ground truth, arguing against memorizing a small pattern set.The probe uses attention to construct a linear function and is intended to reduce sample complexity.Source: §A.4 · pp. 20–21

B More Experiments on Results 2-3 (Generation)

The generation experiments assess both output diversity and how closely generated symbol probabilities match the ground-truth CFG. Across datasets, GPT generates diverse outputs, and the authors conclude it does not learn CFGs by memorizing only a small set of patterns.

B.1 Generation Diversity via Birthday Paradox

  • The diversity analysis compares generated and ground-truth sample support using entropy estimates and birthday-paradox lower bounds.For the birthday-paradox analysis, the authors examine derivations across levels rather than only at the leaves.Source: B More Experiments on Results 2-3… · p. 21, §B.1 · p. 22

B More Experiments on Results 2-3 (Generation)

  • Birthday-paradox tests with 20,000 samples support at least Ω(M²) distinct derivations from cfg3f symbols across multiple CFG levels.The paper notes that M² already exceeds the model's parameter count.Source: B More Experiments on Results 2-3… · p. 21

B.1 Generation Diversity via Birthday Paradox

  • GPT generates very diverse outputs on both hard, ambiguous CFGs and the less ambiguous cfg3e1 and cfg3e2 datasets.The authors report that pre-trained models do not rely on simply memorizing a small set of patterns to learn CFGs.Source: B More Experiments on Results 2-3… · p. 21, §B.1 · p. 22

B.2 Marginal Distribution Comparison

  • Generated marginal probabilities p(a, i) align strongly with the ground-truth probabilities for nonterminal symbols at positions.The comparison is reported in Appendix B.2 and Figure 18; the caption notes weaker learning on cfg3g and cfg3f.Source: §B.2 · p. 26, Figure 18 · p. 26

C.1 NT Ancestor and NT Boundary Probing

Probing finds that GPT’s hidden states encode nonterminal ancestors and boundaries, with boundary information stored near the corresponding position. Across layers and training, the learned representations and attention patterns show hierarchical organization and concentration around nonterminal ends.

C.1 NT Ancestor and NT Boundary Probing

  • Final-layer hidden states linearly encode nonterminal ancestors and boundaries, with boundary information stored locally near position i, such as at i ± 1.At nonterminal boundaries, ancestor symbols can also be predicted from position i or nearby positions; the authors separately test boundary prediction accuracy.Source: §C.1 · p. 27, Figure 19 · p. 28

C.2 NT Probing Across Transformer’s Layers

  • Nonterminal ancestor and boundary information for levels closer to the CFG root appears in deeper transformer layers, indicating hierarchical discovery.The finding is reported across the 12 layers of GPT and GPTrel.Source: §C.2 · p. 29, Figure 20 · p. 29

C.3 NT Predictions Across Training Epochs

  • Ancestor and boundary information increases across training epochs, while the authors emphasize training all layers together for deep CFG learning.They attribute lower-layer feature correction to deeper layers during joint training, describing this as “backward feature correction” [2].Source: §C.3 · p. 30, Figure 21 · p. 30

D.1 Result 6: Position-Based Attention Pattern

  • Attention weights show a strong bias by relative position, with different heads or layers depending differently on that position.The pattern is examined across additional datasets and in GPT and GPTrel.Source: §D.1 · p. 31, Figure 22 · p. 31

D.2 Result 7: From Anywhere to NT-ends

  • After removing position bias, attention from tokens anywhere in the sequence is strongest at nonterminal ends and drops rapidly to nearby tokens.The reported maximum is at δ = 0.Source: §D.2 · p. 32, Figure 23 · p. 32

D.3 Result 8: From NT-ends to NT-ends

  • Nonterminal ends also attend more to other nonterminal ends, with different layers or heads handling different CFG levels.Attention drops more sharply with δ1 than δ2, consistent with the possibility that identifying a boundary at j requires reading additional tokens.Source: §D.3 · pp. 33–34, Figure 24 · p. 34

D.4 Result 9: From NT-ends to Adjacent NT-ends

Attention between nonterminal boundaries remains correlated with the smallest possible distance between their CFG levels, even after position bias is removed. Different transformer layers are responsible for attending to the most adjacent nonterminal ends at different CFG levels.

D.4 Result 9: From NT-ends to Adjacent NT-ends

  • After removing position bias, attention between nonterminal boundaries remains strongly correlated with the smallest possible CFG-level distance, supporting a dynamic-programming-like interpretation.Different transformer layers attend to the most adjacent nonterminal ends at different CFG levels.Source: §D.4 · pp. 35–36

E More Experiments on Result 10 (Implicit CFGs)

The implicit CFG experiments evaluate generation on eight variants derived from cfg3i, varying observable-token vocabulary size and token distributions. The appendix reports generation accuracies and examines token-embedding correlations.

E More Experiments on Result 10 (Implicit CFGs)

F More Experiments on Results 11-13 (Robustness)

Additional experiments show that low-quality pretraining data improves robustness on CFG tasks, while the paper also explores PTB and other CFG families beyond cfg3. The paper does not investigate GPT parsing English or other natural languages.

F More Experiments on Results 11-13 (Robustness)

  • A 10% perturbation of training data significantly improves robustness; low-temperature generation can also yield high robust accuracy, even after training entirely on corrupted data.Models switch modes based on the prefix: clean prefixes lead to correct completions, corrupted prefixes to grammatically flawed ones, and no-prefix generations reflect the corruption fraction.Source: F More Experiments on Results 11-13… · p. 38

G Beyond the CFG3 Data Family

G.1 The Penn TreeBank CFG

The paper tests its approach on the Penn TreeBank CFG, additional unbalanced synthetic CFGs, and uniform attention. GPT models learn the tested CFGs, and uniform attention outperforms vanilla GPT in the reported comparisons.

G.1 The Penn TreeBank CFG

  • The PTB CFG excludes rules appearing fewer than 50 times; the resulting grammar has 44 terminal and nonterminal symbols and 156 rules.The rare-rule threshold was used to make evaluation tractable.Source: §G.1 · p. 40
  • 135K GPT-2-4-16 reaches ~95% generation accuracy with KL divergence less than 0.01, while 1.3M GPT-6-4-32 reaches 99% generation accuracy and KL divergence on the order of 0.001.The learned models’ output entropy is on the magnitude of the PTB CFG’s estimated 60 bits.Source: §G.1 · p. 41

G.2 More Synthetic CFGs

  • Length-1 rules make cfg8 and cfg0 globally ambiguous, whereas cfg9 was constructed for mostly unique NT information and supports replicated probing.The cfg9 construction uses rejection sampling to retain CFGs with unique dynamic-programming solutions.Source: §G.2 · p. 42
  • GPT2-small learns the unbalanced cfg8/9/0 families almost perfectly, especially with relative or rotary embeddings.These families allow length-1 rules; cfg0 has depth 11, while cfg8/9 have depth 7.Source: §G.2 · pp. 41–42

H More on Uniform Attention

  • Across settings, GPTuni outperforms vanilla GPT, including when vanilla GPT has more trainable parameters.Figure 35 compares generation accuracy and KL divergence; the paper cautions that CFG tasks do not constitute a comprehensive architecture benchmark. The findings motivate follow-up work [1] on short-window uniform attention.Source: H More on Uniform Attention · p. 43, Figure 35 · p. 44
Loading 2305.13673v4…