Unraveling Syntax: Language Modeling and the Substructure of Grammars

While language models achieve impressive results, their learning dynamics are far from understood. Many domains of interest – such as natural language syntax, coding languages, arithmetic – are captured by context-free grammars (CFGs). In this work, we extend prior work on neural language modeling of CFGs in a novel direction: how language modeling behaves with respect to CFG substructure, namely subgrammars. We define subgrammars, and prove a set of fundamental theorems connecting language modeling and subgrammars. We show that language modeling loss recurses linearly over its top-level subgrammars; applied recursively, the loss decomposes into losses for "irreducible" subgrammars. Under additional assumptions, and empirically, parametrized models learn subgrammars in parallel, unlike children who first master simple substructures. We find that subgrammar pretraining can improve final performance, but only for tiny models relative to the grammar, while alignment analyses show that pretraining consistently leads to internal representations that better reflect the grammar’s substructure.

Modern language models can produce remarkably fluent language, write code, and solve complex problems, but we still do not understand how they learn these abilities. In this work, we study how language models learn structured languages by training them on simplified artificial languages generated from grammatical rules, like those underlying natural language and programming languages. We focus on the idea that complex grammars are built from smaller reusable pieces, which we call “subgrammars.” We develop a mathematical theory showing that a model’s overall prediction errors can be broken down into errors on these smaller grammars. This then lets us study whether models learn language piece by piece, or whether they learn many structures at the same time. Our experiments show that small transformer models tend to learn these subgrammars in parallel, rather than mastering simpler structures first the way children often do when learning language. We also study whether training models first on simpler substructures can help them learn more effectively. This type of pretraining improves performance for very small models and consistently changes the model’s internal representations so that they better reflect the structure of the language. However, even strong models continue to struggle with deeply nested and recursive patterns. Overall, our work provides new mathematical tools and experiments for understanding how language models acquire structured knowledge, helping bridge the gap between machine learning, linguistics, and human language acquisition.