Elamur Research⌕
☰
home / papers / 2023 / Physics of Language Models: Part 1, Learning Hierarchical Language Structures

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

Paper · 2023 · Zeyuan Allen-Zhu and Yuanzhi Li

Summary

The authors study how transformer language models learn to reason over hierarchical recursive structures. Earlier work mostly looked at simpler operations, such as copying or selecting tokens. To keep the experimental conditions controlled, the authors built a family of synthetic context-free grammars (CFGs). These grammars generate very long strings of hundreds of symbols. The strings are locally ambiguous, so parsing them requires dynamic programming. GPT-2 was trained from scratch, with different positional encodings, on corpora generated from these grammars. The authors then checked how correct and diverse its generated continuations are. To look at how the model works internally, they proposed multi-head linear probing of hidden states and methods for quantitative attention analysis. They found that GPT does learn the grammar. Its hidden states encode nonterminal ancestors and subtree boundaries almost perfectly in a linear way, even though the model never saw the tree structure during training. Its attention mechanism passes information the same way a DP algorithm does. The work is valuable because it provides a transparent testbed for mechanistic interpretability. It also yields practical conclusions about model architecture and pretraining data quality.

Key points

  • Relative and rotary positional encodings are much better than absolute ones, especially on hard grammars. Even GPT_uni, with uniform attention and no query/key matrices, outperforms a standard GPT with absolute positions, including at the same parameter count: GPT_uni (8, 840) vs. GPT (12, 768). This result underlies the authors' follow-up work on Canon layers.
  • The encoder models BERT and DeBERTa encode the deep CFG structure noticeably worse than the autoregressive GPT.
  • An English CFG based on the Penn TreeBank proved too easy for this kind of analysis. Its sentences average about 28 tokens and have little local ambiguity, and a tiny GPT2 with about 100K parameters learns it. The authors therefore used synthetic grammars: 7 in the main text (e.g., cfg3f) and 15 more in the appendices.
  • Robustness to errors. A model trained only on correct data recovers poorly from a corrupted prefix in which 15% of the symbols have been randomly changed. Adding about 10% perturbed examples to the training data makes the model noticeably more robust. The model then learns to "switch modes" between grammatically correct and erroneous generation.
  • In an implicit CFG, each terminal is a set of tokens. The model stores which terminal a token belongs to directly in the token embeddings layer.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢MetaMenlo Park · United States224 works · 241,960 citations🎓Mohamed bin Zayed University of Artificial IntelligenceAbu Dhabi · United Arab Emirates145 works · 6,811 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 4,145 works

Cite

Cite as Zeyuan Allen-Zhu and Yuanzhi Li. 2023. Physics of Language Models: Part 1, Learning Hierarchical Language Structures. arXiv:2305.13673.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2305.13673 · arXiv 2305.13673

@misc{allenzhu2023physics,
  title = {{Physics of Language Models: Part 1, Learning Hierarchical Language Structures}},
  author = {Zeyuan Allen-Zhu and Yuanzhi Li},
  year = {2023},
  doi = {10.48550/arxiv.2305.13673},
  eprint = {2305.13673},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2305.13673}
}

References

40 references, 17 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Zeyuan Allen-Zhu. Physics of Language Models: Part 4.1, Architecture Design and the Magic of Canon Layers. SSRN Electronic Journal, May 2025. https://ssrn.com/abstract=5240330. ↗
  2. Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. In COLT, 2023. Full version available at http://arxiv.org/abs/2001.04413. ↗
  3. 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, ICML 2024, 2024. Full version available at https://ssrn.com/abstract=5250633. ↗
  4. 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, ICLR 2025, 2025. Full version available at https://ssrn.com/abstract=5250621. ↗
  5. Zeyuan Allen-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, 2025. Full version available at https://ssrn.com/abstract=5250617. ↗
  6. Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via overparameterization. In ICML, 2019. Full version available at http://arxiv.org/abs/1811.03962. ↗
  7. Sanjeev Arora and Yi Zhang. Do gans actually learn the distribution? an empirical study. arXiv preprint arXiv:1706.08224, 2017. — [arXiv:1706.08224](https://arxiv.org/abs/1706.08224) find
  8. David Arps, Younes Samih, Laura Kallmeyer, and Hassan Sajjad. Probing for constituency structure in neural language models. arXiv preprint arXiv:2204.06201, 2022. find
  9. James K Baker. Trainable grammars for speech recognition. The Journal of the Acoustical Society of America, 65(S1):S132–S132, 1979. find
  10. Sid Black, Stella Biderman, Eric Hallahan, Quentin Anthony, 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-20B: An open-source autoregressive… — GPT-NeoX-20B: An Open-Source Autoregressive Language Model
  11. 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 chomsky hierarchy. In ICLR, 2023.
  12. Brian DuSell and David Chiang. Learning hierarchical structures with differentiable nondeterministic stacks. In ICLR, 2022. find
  13. 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. find
  14. Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention. arXiv preprint arXiv:2006.03654, 2020.
  15. John Hewitt and Christopher D. Manning. A structural probe for finding syntax in word representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association cfg3f -0.00648 -0.00112 -0.00612 -0.00816 -0.00116 -0.00762 cut0 cfg3g -0.00519 -0.00068 -0.00632 -0.00402 -0.…
  16. Samy Jelassi, David Brandfonbrener, Sham M Kakade, and Eran Malach. Repeat after me: Transformers are better than state space models at copying. arXiv preprint arXiv:2402.01032, 2024.
  17. Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT, pages 4171–4186, 2019.
  18. 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, 117(48):30046–30054, 2020. find
  19. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330, 1993. URL https://aclanthology.org/J93-2004. ↗
  20. Rowan Hall Maudslay and Ryan Cotterell. Do syntactic probes probe syntax? experiments with jabberwocky probing. arXiv preprint arXiv:2106.02559, 2021. find
  21. Milad Moradi and Matthias Samwald. Evaluating the robustness of neural language models to input perturbations. arXiv preprint arXiv:2108.12237, 2021. find
  22. Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher D Manning. Characterizing intrinsic compositionality in transformers with tree projections. In ICLR, 2023. find
  23. Neel Nanda, Lawrence Chan, Tom Liberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. arXiv preprint arXiv:2301.05217, 2023.
  24. 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.
  25. OpenAI. Gpt-4 technical report, 2023.
  26. Matt Post and Shane Bergsma. Explicit and implicit syntactic features for text classification. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 866–872, 2013. find
  27. Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108.12409, 2021. find
  28. Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019. find
  29. Itiroo Sakai. Syntax in universal translation. In Proceedings of the International Conference on Machine Translation and Applied Language Analysis, 1961. find
  30. Hui Shi, Sicun Gao, Yuandong Tian, Xinyun Chen, and Jishen Zhao. Learning bounded context-free-grammar via lstm and the transformer: Difference and the explanations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8267–8276, 2022. find
  31. Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 2012. find
  32. Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, 2021.
  33. Lifu Tu, Garima Lalwani, Spandana Gella, and He He. An empirical study on robustness to spurious correlations using pre-trained language models. Transactions of the Association for Computational Linguistics, 8:621–633, 2020. find
  34. David Vilares, Michalina Strzyz, Anders Søgaard, and Carlos Gómez-Rodrı́guez. Parsing as pretraining. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 9114–9121, 2020. find
  35. Kevin Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. Interpretability in the wild: a circuit for indirect object identification in gpt-2 small. arXiv preprint arXiv:2211.00593, 2022. find
  36. Zhiyong Wu, Yun Chen, Ben Kao, and Qun Liu. Perturbed masking: Parameter-free probing for analyzing and interpreting bert. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4166–4176, 2020.
  37. Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process. In Proceedings of the 13th International Conference on Learning Representations, ICLR 2025, 2025. Full version available at https://ssrn.com/abstract=52506… ↗
  38. Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of Language Models: Part 2.2, How to Learn From Mistakes on Grade-School Math Problems. In Proceedings of the 13th International Conference on Learning Representations, ICLR 2025, 2025. Full version available at https://ssrn. com/abstrac…
  39. Shizhuo Dylan Zhang, Curt Tigges, Stella Biderman, Maxim Raginsky, and Talia Ringer. Can transformers learn to solve problems recursively? arXiv preprint arXiv:2305.14699, 2023.
  40. Haoyu Zhao, Abhishek Panigrahi, Rong Ge, and Sanjeev Arora. Do transformers parse while predicting the masked word? arXiv preprint arXiv:2303.08117, 2023. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/allen-zhu-2023-physics-language-models-part-1/