Unraveling Syntax: How Language Models Learn Context-Free Grammars

## Abstract

Abstract We introduce a new framework for understanding how language models acquire syntax. While large models achieve impressive results, little is known about their learning dynamics. Our approach starts with the observation that most domains of interest – such as natural language syntax, coding languages, arithmetic problems – are captured by probabilistic context-free grammars (PCFGs). We study the learning dynamics of small models trained on synthetic languages generated from PCFGs, enabling precise control over grammar complexity, recursion depth, and subgrammar structure. We prove several general, recursive formulae for the training loss and Kullback-Leibler divergence over the subgrammar structure of a PCFG. Empirically, we find that unlike children– who first master simple substructures before progressing to more complex constructions– transformers reduce loss across all subgrammars in parallel. We further show that subgrammar pretraining can improve the final loss for smaller models, and that pretrained models develop internal representations more aligned with the grammar’s substructure.
Finally, we demonstrate that models struggle with deeper recursive structures (a limitation even of large language models), revealing fundamental challenges in how neural networks represent hierarchical syntax. Overall, our work initiates the study of the learning dynamics of transformers on PCFGs as a versatile testbed for probing learning in language models, opening a research direction with many open questions.

## 1 Introduction

Large language models (LLMs) have stunned the world by achieving sophisticated language abilities in the past few years, yet we still do not know *how* they reach such high levels of performance.

A field of research has emerged that aims to reveal the dynamics of deep neural network training by restricting attention to well-understood hypothesis classes such as polynomials, XOR, or modular counting. In these domains experiments are feasible and theory is tractable and well understood analytically, unlike the space of all images, or even the English language. Language modeling, by contrast, remains poorly understood. Mainly because training high-quality LLMs require hundreds of billions of parameters and billions of dollars to train (Grattafiori et al., 2024; Cottier et al., 2024). Training “own’s one" state-of-the-art LLM simply to study its training dynamics is unfeasible. While prior work has analyzed the static behavior of trained models (probing internal representations, in-context learning, etc.), little is known about the process of language acquisition. Do LLMs, for example, master simpler substructures before progressing to more complex syntax, as children do?

Because natural language syntax is largely governed by *context-free grammars* (CFGs), we propose a novel surrogate approach: study how small neural models acquire synthetic CFGs.
In addition to feasibility, we can precisely control the complexity of such grammars, including the vocabulary size, sentence length, and arguably most interestingly, the amount or depth of embedding and recursive structure. With this approach, we can ask a stylized version of our question above regarding whether a language model trained on a CFG $G$ first achieves competence on a simpler subgrammar $H\subset G$.

Our contributions are threefold. In Section [4](https://arxiv.org/html/2510.02524v1#S4), we establish several fundamental theoretical properties of the CFG substructure and their relationship to learning. We prove that the KL Divergence between a CFG and a trained model decomposes into a sum over its *subgrammars* – a concept we define and explore rigorously in the same section. This implies that models learn all subgrammars in parallel rather than through stages, a prediction confirmed empirically.
In Section [5](https://arxiv.org/html/2510.02524v1#S5), show that pretraining on subgrammars can improve final loss for small architectures, while larger models perform similarly with or without pretraining. However, in both cases, we present evidence using Centered Kernel Alignment (CKA) that pretrained models have a more structured representation of subgrammar structure than directly trained models.
Finally, in Section [6](https://arxiv.org/html/2510.02524v1#S6), we examine generalization to deeper recursion, finding that models handle long contexts at fixed depth but fail sharply when recursion depth increases. We observe a similar behavior in state-of-the art models, which reliably solve long but shallow arithmetic chains yet fail on deeply nested arithmetic expressions. A final contribution will be an open source library for training models on CFGs.

More broadly, this work initiates the theoretical and empirical study of training dynamics over CFGs – a natural, structured, and fundamental class—towards a theory of language learning in neural networks, analogous to those developed for Boolean and arithmetic function families.

## 2 Related Work

Transformers (Vaswani et al., 2017), and language models more broadly, have been studied in two predominant research directions: improving training methods (Bubeck et al., 2023; Jaech et al., 2024; Guo et al., 2025) and probing trained models to analyze how knowledge is stored and activated during inference (Meng et al., 2022; Geva et al., 2021; Dar et al., 2022; Ferrando & Voita, 2024).
Much less is known about how such models acquire language. However, one remarkable study Evanson et al. (2023) showed that GPT-2 displayed developmental stages *reminiscent* of child language learning, from simple subject–verb constructions to wh-questions and relative clauses.

Our work initiates the theoretical and empirical study of the learning dynamics of neural networks on CFGs, a highly structured mathematical formalism, intending to grow a subfield analogous to those for Boolean and arithmetic functions. We approach this problem via the surrogate (and theoretically significant in its own right) approach of studying the dynamics of *language models acquiring formal languages*. Prior families such as juntas, parities, and modular counting have highlighted optimization challenges ranging from variable selection to hierarchical dependencies (Klivans & Kothari, 2014; Telgarsky, 2016; Abbe et al., 2024; Daniely & Malach, 2020). CFGs provide a linguistically motivated setting where recursive structure is explicit, and formal language theory offers a well-developed foundation (e.g. see (Cotterell et al., 2023) for a survey).

Formal languages have been used to test neural models, with mixed success. RNNs and LSTMs often fail to learn subregular grammars despite theoretical capacity (Avcu et al., 2017), and transformers perform well on many formal languages but struggle with recursion and counter-based mechanisms (Bhattamishra et al., 2020). Other studies confirm that transformers often fail on deeply nested grammatical structures (Lampinen, 2024). Results consistently show that gradient descent, rather than model expressivity, is the limiting factor. Similar findings arise for LSTMs, where data distribution and length generalization strongly affect performance (Suzgun et al., 2018).

On the theoretical side, Hahn (2020) established limitations of self-attention in capturing long-range dependencies, even though transformers are known to be Turing-complete (Pérez et al., 2021) and universal approximators of sequence functions (Yun et al., 2019); see Strobl et al. (2024) for a survey. Probing studies have also revealed internal stack-like representations in models trained on counter languages (Tiwari et al., 2025).

## 3 Preliminaries and Definitions

### 3.1 Formal Languages

###### Definition 3.1 (CFG) .

A Context-Free Grammar (CFG) is a tuple $G=(\Sigma,\mathcal{N},\mathcal{S},\mathcal{P})$ where $\Sigma$ is a finite set of terminal symbols, $\mathcal{N}$ is a finite set of non-terminal symbols (disjoint from $\Sigma$), $S\in\mathcal{N}$ is the designated start symbol, and $\mathcal{P}$ is a finite set of production rules of the form

$$ $A\rightarrow\alpha$ $$

where $A\in\mathcal{N}$ and $\alpha\in(\mathcal{N}\cup\Sigma)^{*}$ is a string of terminals and non-terminals ($\alpha$ can be the empty string which we designate with $\epsilon$).

The language $L_{G}\subseteq\Sigma^{*}$ associated with a CFG $G$ is the set of all strings over the terminals that can be derived from $S$ via successive applications of rules in $\mathcal{P}$. A language generated by a CFG is a *Context-Free Language* (CFL).

###### Definition 3.2 (PCFG) .

A Probabilistic Context-Free Grammar (PCFG) is a context-free grammar $G=(\Sigma,\mathcal{N},\mathcal{S},\mathcal{P})$ augmented with a probability function $\mathcal{W}$ that assigns to each rule $(A\rightarrow\alpha)\in\mathcal{P}$ a non-negative probability $\mathcal{W}(A\rightarrow\alpha)$ such that for each $A\in\mathcal{N}$, $\sum_{\{(A\rightarrow\alpha)~\in~\mathcal{P}\}}\mathcal{W}(A\rightarrow\alpha)=1$.

###### Definition 3.1 (CFG) .

###### Definition 3.2 (PCFG) .

#### Brief history.

CFGs were originally defined in the context of linguistics (Chomsky, 1956), as the vast majority of the syntax of natural languages, as well as the syntax of programming languages and mathematics, can be formulated as CFGs (Shieber, 1985; Pullum & Gazdar, 1982). CFGs occupy a position of intermediate complexity in the "Chomsky hierarchy" of computational models, strictly stronger than the finite-state automata which compute the regular languages, and weaker than the Turing machine, which can compute (or recognize) any language that is computable(^1^11If one accepts the Church-Turing thesis, which states that any physically-realizable computational system can be simulated by a Turing Machine.). Since CFGs capture languages with recursion and embedded structure, there intuitively exists a notion of a *sub*grammar within a grammar. However, several subtleties crop up when attempting to define a subgrammar. There are at least two interesting definitions: one of *substrings* of CFG sentences that can be generated from a non-terminal, and the other as a subset of the CFG language generated by a subset of the rules. We term these *inner* and *outer* subgrammars respectively. We will sometimes say *supergrammar* for a bigger grammar containing a subgrammar.

###### Definition 3.3 (Inner Subgrammar) .

An inner subgrammar of a PCFG $G=(\Sigma,\mathcal{N},\mathcal{S},\mathcal{P},\mathcal{W})$ is itself a PCFG $G^{\prime}=(\Sigma^{\prime},\mathcal{N}^{\prime},\mathcal{S}^{\prime},\mathcal{P}^{\prime},\mathcal{W}^{\prime})$ such that $\Sigma^{\prime}\subseteq\Sigma$, $\mathcal{N}^{\prime}\subseteq\mathcal{N}$, $\mathcal{S}^{\prime}\in\mathcal{N}^{\prime}$ is the start symbol of the subgrammar, and $\mathcal{P}^{\prime}$ is the set of all rules with non-terminals in $\mathcal{N}^{\prime}$.
Finally, $W^{\prime}$ is the restriction of $\mathcal{W}$ to $\mathcal{P}^{\prime}$, renormalized so that for every $A\in\mathcal{N}^{\prime}$,
$\sum_{\{(A\rightarrow\alpha)\in\mathcal{P}^{\prime}\}}\mathcal{W}^{\prime}(A\rightarrow\alpha)=1$ .

###### Definition 3.4 (Proper Subgrammar) .

A *proper* subgrammar is an inner subgrammar $G^{\prime}$ of a CFG $G$ which does not contain $G$ itself.

###### Definition 3.5 (Outer Subgrammar) .

An outer subgrammar of a PCFG $(\Sigma,\mathcal{N},\mathcal{S},\mathcal{P},\mathcal{W})$ is a PCFG $G^{\prime}=(\Sigma^{\prime},\mathcal{N}^{\prime},\mathcal{S},\mathcal{P}^{\prime},\mathcal{W}^{\prime}$), with $\Sigma^{\prime}\subseteq\Sigma$, $\mathcal{N}^{\prime}\subseteq\mathcal{N}$, $\mathcal{P}^{\prime}\subseteq\mathcal{P}$, and $W^{\prime}$ is the renormalized restriction of $\mathcal{W}$ to $\mathcal{P}^{\prime}$. In particular, to be a valid outer subgrammar, $\mathcal{P^{\prime}}$ must contain at least one rule from $\mathcal{P}$ where the left-hand side is $S$, and for each of its non-terminals.

An outer subgrammar captures the notion of a subset of the *language* generated by a PCFG obtained by keeping a subset of expansions of various non-terminals (starting from $S$). Every string generated by an outer subgrammar is a valid string of the supergrammar. An outer subgrammar more closely corresponds to the notion of a “simple" version of a language– for instance, how children produce language during acquisition, whereas inner subgrammars are the inherent *compositional* substructures of a CFG.

###### Definition 3.3 (Inner Subgrammar) .

###### Definition 3.4 (Proper Subgrammar) .

###### Definition 3.5 (Outer Subgrammar) .

### 3.2 Language Modeling

In this work, all distributions are assumed to be over strings of a finite alphabet $\Sigma$, although many of the definitions apply to arbitrary domains.

###### Definition 3.6 (Kullback-Leibler Divergence) .

Given distributions $P$ and $Q$ over $\Sigma^{*}$, the Kullback-Leibler (KL) Divergence of $Q$ from $P$ is

$$ $\mathrm{KL}(P\;\|\;Q)=\sum_{s\in\Sigma^{*}}P(s)\log\frac{P(s)}{Q(s)}$ $$

A *language model* $Q_{\theta}$ is a function family parametrized by $\theta$, such that $Q_{\theta}(x)$ yields a probability distribution over $x\in\Sigma^{*}$. In this work one can think of all $Q_{\theta}$ as auto-regressive (though for several theoretical results this is not strictly necessary), meaning $Q_{\theta}$ explicitly models the next token distribution, and $Q_{\theta}(x_{1},\ldots,x_{n})=\Pi_{i=1}^{n}Q_{\theta}(x_{i}|x_{1},\ldots,x_{i-1})$.

In Language Modeling, $Q_{\theta}$ is optimized with Maximum Likelihood Estimation:

###### Definition 3.7 (Maximum Likelihood Estimation) .

Given a model family $Q_{\theta}$ and target distribution $P$, the Maximum Likelihood Estimator $Q_{\hat{\theta}}$ is parametrized by

$$ $\hat{\theta}=\operatorname*{arg\,max}_{\theta}\mathcal{L}(\theta)$ $$

where

$$ $\mathcal{L}(\theta)=\mathbb{E}_{s\sim P}~[-\log Q_{\theta}(s)]$ $$

Practically, this is done by maximizing the combined likelihood under $Q_{\theta}$ of a set of samples, or equivalently (by monotonicity of $\log$) minimizing the sum of negative log-likelihoods; in the limit, this exactly approaches $\mathcal{L}(\theta)$.

###### Definition 3.8 (Shannon Entropy) .

The Shannon Entropy of a probability distribution is

$$ $H(P)=\mathbb{E}_{s\sim P}~[\log P(s)]$ $$

###### Proposition 3.9 .

Given a true distribution $P$ and model $Q_{\theta}$ parametrized by $\theta$,

$$ $\mathcal{L}(\theta)=D_{\mathrm{KL}}(P~\|~Q_{\theta})+H(P)$ $$

The proof (given in the Appendix [A](https://arxiv.org/html/2510.02524v1#A1)) is a straightforward application of the linearity of expectation. The theorem states that loss of a model equals its KL-divergence from the true distribution, plus an entropy term that depends only on the underlying distribution (i.e. is independent of $\theta$). In particular this implies that $\hat{\theta}$ minimizes $\mathcal{\theta}$ if and only if it minimizes $D_{\mathrm{KL}}(P~\|~Q_{\theta})$.

###### Definition 3.6 (Kullback-Leibler Divergence) .

###### Definition 3.7 (Maximum Likelihood Estimation) .

###### Definition 3.8 (Shannon Entropy) .

###### Proposition 3.9 .

## 4 Loss and the Compositionality of Context-Free Grammars

### 4.1 Decomposition of PCFG into subgrammars

###### Theorem 4.1 (Unique decomposition of PCFG into inner subgrammars) .

Every (probabilistic) context-free grammar $G$ can be uniquely decomposed into a hierarchy of its inner subgrammars.

This hierarchical structure can be represented as a directed acyclic graph (DAG) with self-loops (that is, the graph is acyclic *except* that edges from a node $v$ to itself are permitted). Each node is labeled by the set of non-terminals that generate the corresponding subgrammar.

The proof recursively constructs the DAG by first identifying the “top-level" subgrammars of $G$; see Appendix [A](https://arxiv.org/html/2510.02524v1#A1). While to our knowledge, the theorem in this particular formulation is our own, the nodes of the DAG decomposition correspond to the “grammatical levels" of a CFG in Gruska’s classical work on CFG theory (Gruska, 1971).

###### Theorem 4.1 (Unique decomposition of PCFG into inner subgrammars) .

### 4.2 Subgrammar structure and Language Modeling

We now study the connection between the subgrammar structure of CFGs and training language models on the corresponding CFL. Let $G=(\Sigma,\mathcal{N},S,\mathcal{P},\mathcal{W})$ be a PCFG that induces a distribution $P_{G}$ over $\Sigma^{*}$, and $Q_{\theta}$ an autoregressive language model trained to approximate $P_{G}$ (that is, given a partial sentence over $\Sigma^{*}$ it outputs a terminal, or EOS).

We first consider a very simple case, where the only expansion of $S$ is $S\rightarrow\alpha A\beta$, where $A$ is some proper subgrammar (does not generate $S$), and $\alpha,\beta\in\Sigma^{*}$ are strings of terminals:

$$ $\displaystyle D_{\mathrm{KL}}(P~\|~Q)$ $\displaystyle=\sum_{a\in\Sigma^{*}}P_{G}(\alpha a\beta)\log\frac{P_{G}(\alpha a\beta)}{Q_{\theta}(\alpha a\beta)}$ $\displaystyle=\sum_{a\in\Sigma^{*}}P_{G}(\alpha a\beta)[\log P_{G}(\alpha|\epsilon)+\log P_{G}(a|\alpha)+\log P_{G}(\beta|a\alpha)-\log Q_{\theta}(\alpha|\epsilon)$ $\displaystyle\qquad\qquad-\log Q_{\theta}(a|\alpha)-\log Q_{\theta}(\beta|a\alpha)]$ $\displaystyle=\frac{\log P_{G}(\alpha|\epsilon)}{\log Q_{\theta}(\alpha|\epsilon)}+\sum_{a}P_{A}(a)\frac{\log P_{A}(a)}{\log Q_{\theta}(a|\alpha)}+\sum_{a}P(a)\frac{\log P_{G}(\beta|\alpha a)}{\log Q_{\theta}(\beta|\alpha a)}$ $$

In an abuse of notation, above $P_{G}(\alpha|\epsilon)$ denotes the probability of a partial sequence beginning with $\alpha$, $P_{G}(a|\alpha)$ the probability of $a$ following $\alpha$ (in a partial sequence), and so on; similarly $Q_{\theta}(\alpha|\epsilon)$ is the $Q_{\theta}$ outputs the prefix $\alpha$ (starting with the empty context), etc. The decomposition of $P_{G}$ and $Q_{\theta}$ in the second line follows from the subgrammar structure of $G$ in the case of $P_{G}$, and from the fact that $Q_{\theta}$ is an autoregressive model (generating from left to right) for the $Q_{\theta}$ terms. In short, *the KL-divergence evaluates to a sum of conditioned KL-divergences* corresponding to the subgrammar $A$, of prefix $\alpha$, and suffix $\beta$. The latter can themselves be thought of as simple subgrammars; indeed, we can rewrite $G$ to include two new non-terminals that evaluate to $\alpha$ and $\beta$ respectively (with prob. 1), and we would then have a sum over three “sub"-divergences.

###### Definition 4.2 .

Given PCFG distribution $P_{G}$ and arbitrary distribution $Q$ over $\Sigma^{*}$, and top-level subgrammar $A$ of $G$, we denote by

$$ $\displaystyle D_{\mathrm{KL}}(P_{G}~\|~Q)_{A}$ $\displaystyle=\sum_{s\in\Sigma^{*}}P(s|\epsilon)P_{G}(A|s)\sum_{a\in\Sigma^{*}}D_{\mathrm{KL}}(P_{A}~\|~Q(\cdot|s))$ $$

That is, $D_{\mathrm{KL}}(R~\|~Q)_{A}$ can be seen as the “restriction" of the KL-divergence to substrings from the subgrammar $A$ (by summing over all contexts that can begin $A$). In the case of a fixed string $\alpha\in\Sigma^{*}$ we will write $D_{\mathrm{KL}}(P_{G}~\|~Q)_{\alpha}$ where the second sum is replaced with a single term for $\alpha$ (equiv. one can view $\alpha$ as a subgrammar of one string).

Then we have, from our previous example

$$ $D_{\mathrm{KL}}(P~\|~Q)=D_{\mathrm{KL}}(P~\|~Q)_{\alpha}+D_{\mathrm{KL}}(P~\|~Q)_{A}+D_{\mathrm{KL}}(P~\|~Q)_{\beta}$ $$

The same decomposition holds more generally. Let the *top-level* subgrammars denote the children of the root node in a CFG’s subgrammar decomposition.

###### Theorem 4.3 (KL loss as a recursive function over subgrammars) .

Let $G$ be a PCFG with top-level subgrammars $A_{1},\ldots,A_{k}$. Let $C\subset\Sigma^{*}$ be the set of (fixed) substrings of terminals that occur between non-terminals of $G$. Then

$$ $D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})=\sum_{i=1}^{k}D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})_{A_{i}}~+\sum_{\alpha\in C}D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})_{\alpha}$ $$

###### Corollary 4.4 .

If we rewrite $G$ as an equivalent PCFG with additional non-terminals such that $S$ maps to strings only non-terminals (correpsonding to subgrammars $A_{1},\ldots,A_{k})$; then the right sum of Theorem [4.3](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem3) can be removed:

$$ $D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})=\sum_{i=1}^{k}D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})_{A_{i}}$ $$

The full proof of Theorem [4.3](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem3) and Corollary [4.4](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem4) are in Appendix [A](https://arxiv.org/html/2510.02524v1#A1). Upon closer inspection, the recursive formula actually applies to any *subgrammar*; that is, for subgrammar $A$ with subgrammars $B_{1},\ldots,B_{l}$, $D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})_{A}=\sum_{j}D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})_{B_{j}}$ (indeed, we could have states Theorem [4.3](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem3) with respect to subgrammars, as $D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})=D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})_{G}$). Hence, this formula can be expanded recursively over each of the *subgrammars* $A_{i}$ by repeated applications of the same theorem, resulting in a sum over all the *leaves* of the DAG decomposition of $G$ into its subgrammars; see Corollary [A.1](https://arxiv.org/html/2510.02524v1#A1.Thmtheorem1) in the Appendix for the precise statement.

Now, suppose each top-level subgrammar $A_{i}$ occurs with probability $p_{i}$ over the top-level rules that expand $S$; it is tempting to conclude that the recursive formula simplifies to $KL(P_{G}~\|~Q_{\theta})=\sum_{i=1}^{k}p_{i}D_{\mathrm{KL}}(P_{A}~\|~Q_{\theta})$ (where the KL terms are no longer restrictions, but bona-fide divergences between the distribution $P_{A}$ and $Q_{\theta}$ as a language model for $A$). However, this works only if $Q_{\theta}$ is excellent and models $P_{A}$ identically under any context where the subgrammar $A$ can occur, which may not be the case!

###### Corollary 4.5 .

Let $G$ be a PCFG where $S$ evaluates to rules with only non-terminals (correspondingly, subgrammars) $A_{1},\ldots,A_{k}$ each of which occurs with prob. $p_{i}$.

Assume $Q_{\theta}$ “*understands composition*": for any subgrammar $A_{i}$ and two contexts $s,s^{\prime}$ for which $P_{G}(A|s)P_{G}(A|s^{\prime})>0$, $Q_{\theta}(A_{i}|s)=Q_{\theta}(A_{i}|s^{\prime})$ (the restrictions of $Q_{\theta}$ to strings from $A_{i}$ given possible contexts $s$ or $s^{\prime}$, are identical).
Then

$$ $D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})=\sum_{i=1}^{k}p_{i}D_{\mathrm{KL}}(P_{A_{i}}~\|~Q_{\theta}(A_{i}))$ $$

Where $Q_{\theta}(A_{i})=Q_{\theta}(A_{i}|s)$ for arbitrary context $s$ s.t. $P_{G}(A_{i}|s)>0$.

The condition that the language model ”understands composition" is strong, but yields a particularly elegant decomposition for the case of a very good language model that models a subgrammar identically wherever it can occur (hence the condition that $P_{G}(A|s)$ and $P_{G}(A|s^{\prime})$ are both positive). In this case, we can say even more about the recurrent structure of KL-divergence. In Theorem [4.3](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem3) and its corollaries, any of the top-level subgrammars $A_{i}$ could have been the grammar $G$ itself (if $G$ has a self-loop). For a language model that understands recursion, we can say even more about the KL-divergence as a function of the *degree* of “self-loopiness", or recursion.

###### Theorem 4.6 (KL-divergence with expected recurrence) .

Let $G$ have *proper* top-level subgrammars $A_{1},\ldots,A_{k}$, each occurring with probability $p_{k}$ over the rules expanding $S$, and let $Q_{\theta}$ be a language model for $P_{G}$ that understands composition.

Let the *recursion* R be the number of times $S$ occurs in the top-level rule chosen to expand $S$. Then,

$$ $D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})=\frac{\sum_{i=1}^{k}D_{\mathrm{KL}}(P_{A}~\|~Q_{\theta}(A_{i}))}{1-\mathbb{E}[R]}$ $$

If $1-\mathbb{E}[R]<0$, then the KL-divergence is *unbounded* if $D_{\mathrm{KL}}(P_{A}~\|~Q_{\theta}(A_{i}))>0$ for any $A_{i}$.

See [4.5](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem5) for a full proof. Theorem [4.6](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem6) can be seen as the equation for the “base case" in the recursive formula for KL-divergence, since an irreducible (leaf) subgrammar evaluates only to strings of terminals and itself. This equation shows that the expected recursion in such a (sub)grammar must be less than 1 (and the closer it is to 1, the greater the “blow-up" of its divergence to a language model); indeed, if the expected recursion is 1 or greater, the PCFG sampling process that recursively expands the root symbol will in expectation never terminate.

Finally, Theorem [A.2](https://arxiv.org/html/2510.02524v1#A1.Thmtheorem2) in the Appendix gives a similar additive decomposition for *outer* subgrammars.

To visualize these recurrence relations, we train a small transformer on several synthetic CFGs with varied subgrammar structure, and plot the KL-divergence over training in Figure [1](https://arxiv.org/html/2510.02524v1#S4.F1). These plots show visually how, throughout all stages of learning, the KL divergence (loss) is the sum over the corresponding loss for each subgrammar.

Figure: (a) A grammar with inner subgrammars, each occurs with 100% probability. Overhead refers to constant strings in between subgrammar roots.
Refer to caption: Figures/kl_divergence_plot_TwoLayer_KL_decomposition_example3.png

To illustrate Theorem [4.6](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem6), consider a simple CFG with two rules:

$$ $S\rightarrow x\;\;(p),\quad S\rightarrow(S~\text{and}~S)\;\;(1-p)$ $$

The expected recursion is $\mathbb{E}[R]=2(1-p)$. Assuming the language model understands composition, we then have that the KL-divergence is $C/(2p-1)$ where $C$ is some constant. We train a small transformer over this language with increasing $p\in(0.5,1]$, demonstrating qualitatively the non-linear (inverse proportional) growth of KL-divergence as $p$ (the probability of *not* recursing) approaches $0.5$). A visual representation can be found in Appendix [4](https://arxiv.org/html/2510.02524v1#A2.F4).

###### Definition 4.2 .

###### Theorem 4.3 (KL loss as a recursive function over subgrammars) .

###### Corollary 4.4 .

###### Corollary 4.5 .

###### Theorem 4.6 (KL-divergence with expected recurrence) .

### 4.3 How Language Models learn

This framework enables the construction of explicitly hierarchical grammars, where one might intuitively expect a model to first master a simpler subgrammar before progressing to the encompassing supergrammar. Surprisingly, our experiments reveal the opposite: all subgrammars exhibit simultaneous decreases in loss, even when they are large or shared across many supergrammars and hence central to the grammar as a whole.

Figure: (a) Deeper Recursion: a language with an inner subgrammar DAG of depth 4.
Refer to caption: Figures/kl_divergence_plot_TwoLayer_Deeper_Recursion.png

## 5 Impact of Pretraining With Subgrammars

While the previous section establishes a mathematical relationship between training loss and subgrammar structure, it is natural to consider whether the structure of CFGs could be exploited in training; e.g. is pretraining on a subgrammar helpful? Perhaps mastering simpler components first facilitates learning of more complex structures later. Such approaches are studied in *curriculum learning* (Bengio et al., 2009; Wang et al., 2021) and modular pretraining strategies (Andreas et al., 2016; Kaiser et al., 2017).

### 5.1 Robustness to Subgrammar Location

One might expect the choice of subgrammar to influence learning, given the autoregressive nature of transformers. In particular, a *prefix subgrammar*, an inner subgrammar always occurring at the beginning of sequences of G, might be easier to retain, whereas the results from pretraining on a *suffix subgrammar* or an *infix subgrammar* (appearing in the middle and disconnected from sentence endpoints) might be overwritten when training on the full grammar begins. However, our results show this is not the case: the model reliably retains modeling performance on *any* subgrammar, regardless of its position. This robustness is illustrated in Figure [5](https://arxiv.org/html/2510.02524v1#A2.F5). As the experiments of the following section suggest, it appears that training on a subgrammar ferries the model into a distinct area of weight space in which the subgrammar is internally represented, and further optimization (on the whole language) remains in this subspace.

### 5.2 Activation-space analysis

We examine how subgrammar pretraining affects internal representations by comparing models trained from scratch to those pretrained on a subgrammar and then continued on the full grammar. Similarity is measured with Centered Kernel Alignment (CKA) (Kornblith et al., 2019) across 30 random seeds.

Much to our surprise, we also found that for smaller models, subgrammar pretraining can even help achieve a *lower final loss* (Figure [6](https://arxiv.org/html/2510.02524v1#A2.F6)). This effect diminishes as the model size and representational complexity increase (for instance, this occurs for 2-layer transformers but not 4-layers). As expected, larger models consistently reach lower losses regardless of pretraining.

CKA analysis reveals that *pretrained models exhibit higher alignment across attention layers than models trained from scratch*, both when computed over full-grammar sequences, and (less surprisingly) subgrammar sequences (Table [1](https://arxiv.org/html/2510.02524v1#S5.T1)). A longer pretraining phase *further increases alignment*, although excessive pretraining can eventually reduce gains in final loss (see same Table).

Why are the pretrained models more “aligned" to one another (that is, represent sequences more similarly)? To probe this, we compare the representational similarity of the top quantile of seeds via cosine similarity of embeddings of three types of sequences: (i) sequences consisting solely of the subgrammar, (ii) sequences with no occurrence of the subgrammar, and (iii) sequences with both the subgrammar and other subsequences. We also compute (iv) the similarity between embedded pairs of a subgrammar sequence and a subgrammar-free sequence. For (i) and (ii), the attention-layers of pretrained models cluster subgrammar sequences (resp. no subgrammar sequences) significantly closer together than directly-trained models. This suggests that substructures learned during pretraining are retained after exposure to the full grammar. Finally, the gap between (iv) and (i), and between (iv) and (ii) is greater in pretrained models, suggesting pretrained models are better at internally segregating sequences with and without subgrammar subsequences (Table [2](https://arxiv.org/html/2510.02524v1#A2.T2)).

Our experiments are not exhaustive, and we leave open the question of *how to train a model to consistently converge to the best optima*, given the rather strong prior of the subgrammar structure of the target CFG. Too little pretraining may not provide a strong enough inductive bias, while too much may over-specialize the model to the subgrammar and hinder transfer. This trade-off mirrors classical insights from curriculum learning, where an optimal “window” of pretraining exposure exists (Bengio et al., 2009; Weinshall et al., 2018).

**Table 1: Average CKA similarity (0–1) across attention and MLP layers of a different Transformers when pretraining for 10 vs. 20 epochs. *Percentage change* indicates the relative difference between models trained from scratch and with pretraining.**
|  | Two-layer Transformer | Four-layer Transformer |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | Pretraining 10 epochs | Pretraining 20 epochs | Pretraining 10 epochs |  |  |  |
|  | Attention | MLP | Attention | MLP | Attention | MLP |
| Full grammar sequences |  |  |  |  |  |  |
| From Scratch | 0.258 | 0.535 | 0.249 | 0.535 | 0.249 | 0.469 |
| With Pretraining | 0.281 | 0.534 | 0.303 | 0.511 | 0.323 | 0.491 |
| *Percentage change (%)* | *+8.9* | *-0.2* | *+21.7* | *-4.7* | *+8.3* | *+1.0* |
| Subgrammar sequences |  |  |  |  |  |  |
| From Scratch | 0.298 | 0.561 | 0.288 | 0.558 | 0.295 | 0.513 |
| With Pretraining | 0.339 | 0.566 | 0.348 | 0.544 | 0.347 | 0.525 |
| *Percentage change (%)* | *+13.8* | *-0.1* | *+20.8* | *-2.6* | *+10.7* | *+1.9* |
| Subgrammar pretraining only | 0.288 | 0.558 | 0.288 | 0.558 | 0.295 | 0.523 |

## 6 Generalization: Do LMs “Know Syntax"?

With language models achieving low training loss, it is natural to ask whether they genuinely internalize and can generalize the rules of the PCFG. This question connects to the broader debate about whether language models exhibit intelligence in terms of structure and composition, or whether they are best understood as extraordinarily powerful pattern-matchers.

To probe this, we evaluate a small transformer trained on an especially simple PCFG: Nested Parentheses (Appendix [C](https://arxiv.org/html/2510.02524v1#A3)). The model achieves very low loss statistically. We test generalization to probabilistically unlikely (but grammatically valid) sequences with increasing length in two ways: (i) extending the context at the same depth of recursion, feeding in $(a)^{i}$, and (ii) growing sequences through repeatedly applying the recursive rule, resulting in contexts at increasingly deeper depths of recursion, of the form $)^{i}$. We then compare the model’s output logits (its output distribution) against the ground-truth next-token distribution. The next-token distribution is identical for all test contexts, even between cases (i) and (ii).

Figure [3](https://arxiv.org/html/2510.02524v1#S6.F3) shows a striking contrast. For case (i), the prediction error remains low throughout, while for case (ii) it grows similarly to an inverse log curve. While the model appears to master the rules of the PCFG at shallow depth, this does not translate into robust handling of deeper recursive dependencies.

We also evaluate the effect of prepending different valid prefixes to the sequence of increasing depth. The results remain largely unchanged— even when using a faulty (non-grammatical) prefix. This suggests that the model’s primary difficulty lies in handling the depth of the subsequence it must complete, while it pays relatively little attention to the completed prefix.

Figure: (a) Contexts of the form $(a)^{i}$ (depth 0)
Refer to caption: Figures/logit_differences_case_1_.png

Anecdotally, we find similar behavior even in state-of-the-art frontier models. We test ChatGPT-5-Instant model on arithmetic expressions generated by a PCFG, presenting two kinds of long expressions: a chain composed of non-deep arithmetic operations, and a single deep arithmetic expression (depth 7)(^2^22We do not find the same discrepancies for ChatGPT-5-Thinking, which solves all of our examples within 3-4 minutes for each expression. The Thinking model may pass arithmetic expressions to a calculator or program, and/or uses an externally prompted or engineered chain-of-thought process; in any case, this departs from language modeling in the strict sense, and as considered in this work.). These experiments show that even LLMs, similar to our small LMs, struggle with depth and not length, correctly answering 5/5 non-deep arithmetic expressions but only 2/5 for a deep arithmetic expression. Note that for the not-deep arithmetic expressions (type 1), the LM in fact has to solve more terms than with the deeper recursion, but still solves them correctly.

## 7 Discussion

With this work, we initiate the study of the learning dynamics of language models on probabilistic CFGs, both in their own right as a theoretical formalism of interest, and as a testbed for probing the learning dynamics of natural language. Here, we propose several open problems and future directions. First, we conjecture that despite the results of Section [6](https://arxiv.org/html/2510.02524v1#S6) *there exists* a setting of the weights of, say, a 2-layer, 2-head transformer (as in our experiments) that *does* correctly model the PCFG (at least up to some very high bound on depth).
This would show that gradient descent is not able to find such ideal solutions, analogous to work showing that while neural networks can in principle represent functions like parity, modular counting, or compositional rules, gradient descent often fails to find these solutions without strong inductive bias or curricula (Telgarsky, 2016; Abbe et al., 2024).
Just as we considered CFGs, a theory of deep learning dynamics can be developed for other classes in the Chomsky hierarchy, including regular languages, mildly context-sensitive languages, etc. As a first step, how much harder is it for a fixed model architecture to learn synthetic languages from these classes (controlled for average sentence length, vocabulary size, etc)? How does “difficulty of depth" compare to other kinds of dependent structure? Finally, our work does not explore the question of *grammar induction*, the learning task of determining the CFG underlying the input data.

## References

- Abbe et al. (2024)
Emmanuel Abbe, Elisabetta Cornacchia, Jan Hązła, and Donald Kougang-Yombi.
Learning high-degree parities: The crucial role of the initialization.
*arXiv preprint arXiv:2412.04910*, 2024.
- Andreas et al. (2016)
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein.
Neural module networks.
In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pp. 39–48, 2016.
- Avcu et al. (2017)
Enes Avcu, Chihiro Shibata, and Jeffrey Heinz.
Subregular complexity and deep learning.
*arXiv preprint arXiv:1705.05940*, 2017.
- Bengio et al. (2009)
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston.
Curriculum learning.
In *Proceedings of the 26th Annual International Conference on Machine Learning*, ICML ’09, pp. 41–48, New York, NY, USA, 2009. Association for Computing Machinery.
ISBN 9781605585161.
doi: 10.1145/1553374.1553380.
URL [https://doi.org/10.1145/1553374.1553380](https://doi.org/10.1145/1553374.1553380).
- Bhattamishra et al. (2020)
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal.
On the ability and limitations of transformers to recognize formal languages.
*arXiv preprint arXiv:2009.11264*, 2020.
- Bubeck et al. (2023)
Sébastien Bubeck, Varun Chadrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al.
Sparks of artificial general intelligence: Early experiments with gpt-4, 2023.
- Chomsky (1956)
N. Chomsky.
Three models for the description of language.
*IRE Transactions on Information Theory*, 2(3):113–124, 1956.
doi: 10.1109/TIT.1956.1056813.
- Cotterell et al. (2023)
Ryan Cotterell, Anej Svete, Clara Meister, Tianyu Liu, and Li Du.
Formal aspects of language modeling.
*arXiv preprint arXiv:2311.04329*, 2023.
- Cottier et al. (2024)
Ben Cottier, Robi Rahman, Loredana Fattorini, Nestor Maslej, Tamay Besiroglu, and David Owen.
The rising costs of training frontier ai models.
*arXiv preprint arXiv:2405.21015*, 2024.
- Daniely & Malach (2020)
Amit Daniely and Eran Malach.
Learning parities with neural networks.
*Advances in Neural Information Processing Systems*, 33:20356–20365, 2020.
- Dar et al. (2022)
Guy Dar, Mor Geva, Ankit Gupta, and Jonathan Berant.
Analyzing transformers in embedding space.
*arXiv preprint arXiv:2209.02535*, 2022.
- Evanson et al. (2023)
Linnea Evanson, Yair Lakretz, and Jean-Rémi King.
Language acquisition: do children and language models follow similar learning stages?
*arXiv preprint arXiv:2306.03586*, 2023.
- Ferrando & Voita (2024)
Javier Ferrando and Elena Voita.
Information flow routes: Automatically interpreting language models at scale.
*arXiv preprint arXiv:2403.00824*, 2024.
- Geva et al. (2021)
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant.
Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies.
*Transactions of the Association for Computational Linguistics*, 9:346–361, 2021.
- Grattafiori et al. (2024)
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al.
The llama 3 herd of models.
*arXiv preprint arXiv:2407.21783*, 2024.
- Gruska (1971)
J. Gruska.
Complexity and unambiguity of context-free grammars and languages.
*Information and Control*, 18(5):502–519, 1971.
ISSN 0019-9958.
doi: 10.1016/S0019-9958(71)90519-5.
URL [https://www.sciencedirect.com/science/article/pii/S0019995871905195](https://www.sciencedirect.com/science/article/pii/S0019995871905195).
- Guo et al. (2025)
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al.
Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning.
*arXiv preprint arXiv:2501.12948*, 2025.
- Hahn (2020)
Michael Hahn.
Theoretical limitations of self-attention in neural sequence models.
*Transactions of the Association for Computational Linguistics*, 8:156–171, 2020.
- Jaech et al. (2024)
Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al.
Openai o1 system card.
*arXiv preprint arXiv:2412.16720*, 2024.
- Kaiser et al. (2017)
Lukasz Kaiser, Aidan N Gomez, Noam Shazeer, Ashish Vaswani, Niki Parmar, Llion Jones, and Jakob Uszkoreit.
One model to learn them all.
*arXiv preprint arXiv:1706.05137*, 2017.
- Klivans & Kothari (2014)
Adam Klivans and Pravesh Kothari.
Embedding Hard Learning Problems Into Gaussian Space.
In Klaus Jansen, José Rolim, Nikhil R. Devanur, and Cristopher Moore (eds.), *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)*, volume 28 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pp. 793–809, Dagstuhl, Germany, 2014. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
ISBN 978-3-939897-74-3.
doi: 10.4230/LIPIcs.APPROX-RANDOM.2014.793.
URL [https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.793](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.793).
- Kornblith et al. (2019)
Simon Kornblith, Mohammad Norouzi, Honglak Lee, and Geoffrey Hinton.
Similarity of neural network representations revisited.
In *International conference on machine learning*, pp. 3519–3529. PMlR, 2019.
- Lampinen (2024)
Andrew Lampinen.
Can language models handle recursively nested grammatical structures? a case study on comparing models and humans.
*Computational Linguistics*, 50(4):1441–1476, 2024.
- Meng et al. (2022)
Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov.
Locating and editing factual associations in gpt.
*Advances in neural information processing systems*, 35:17359–17372, 2022.
- Pullum & Gazdar (1982)
Geoffrey K. Pullum and Gerald Gazdar.
Natural languages and context-free languages.
*Linguistics and Philosophy*, 4(4):471–504, 1982.
ISSN 01650157, 15730549.
URL [http://www.jstor.org/stable/25001071](http://www.jstor.org/stable/25001071).
- Pérez et al. (2021)
Jorge Pérez, Pablo Barceló, and Javier Marinkovic.
Attention is turing-complete.
*Journal of Machine Learning Research*, 22(75):1–35, 2021.
URL [http://jmlr.org/papers/v22/20-302.html](http://jmlr.org/papers/v22/20-302.html).
- Shieber (1985)
Stuart M. Shieber.
Evidence against the context-freeness of natural language.
*Linguistics and Philosophy*, 8(3):333–343, 1985.
ISSN 01650157, 15730549.
URL [http://www.jstor.org/stable/25001210](http://www.jstor.org/stable/25001210).
- Strobl et al. (2024)
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin.
What formal languages can transformers express? a survey.
*Transactions of the Association for Computational Linguistics*, 12:543–561, 2024.
- Suzgun et al. (2018)
Mirac Suzgun, Yonatan Belinkov, and Stuart M Shieber.
On evaluating the generalization of lstm models in formal languages.
*arXiv preprint arXiv:1811.01001*, 2018.
- Telgarsky (2016)
Matus Telgarsky.
Benefits of depth in neural networks.
In *Conference on learning theory*, pp. 1517–1539. PMLR, 2016.
- Tiwari et al. (2025)
Utkarsh Tiwari, Aviral Gupta, and Michael Hahn.
Emergent stack representations in modeling counter languages using transformers.
*arXiv preprint arXiv:2502.01432*, 2025.
- Vaswani et al. (2017)
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.
Attention is all you need.
*Advances in neural information processing systems*, 30, 2017.
- Wang et al. (2021)
Xin Wang, Yudong Chen, and Wenwu Zhu.
A survey on curriculum learning.
*IEEE transactions on pattern analysis and machine intelligence*, 44(9):4555–4576, 2021.
- Weinshall et al. (2018)
Daphna Weinshall, Gad Cohen, and Dan Amir.
Curriculum learning by transfer learning: Theory and experiments with deep networks.
In *International conference on machine learning*, pp. 5238–5246. PMLR, 2018.
- Yun et al. (2019)
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar.
Are transformers universal approximators of sequence-to-sequence functions?
*arXiv preprint arXiv:1912.10077*, 2019.

## Appendix A Additional Proofs and Theorems

###### Proof of Proposition 3.9 .

$$ $\displaystyle\mathcal{L}(\theta)$ $\displaystyle=\sum_{x\in\Sigma^{*}}P(x)(-\log Q_{\theta}(x))$ $\displaystyle=\sum_{x\in\Sigma^{*}}P(x)(\log P(x)-\log P(x)-\log Q_{\theta}(x))$ $\displaystyle=\sum_{x\in\Sigma^{*}}P(x)\log\frac{P(x)}{Q_{\theta}(x)}-\sum_{x\in\Sigma^{*}}P(x)\log P(x)$ $\displaystyle=D_{\mathrm{KL}}(P~\|~Q_{\theta})-H(P)$ $$

∎

###### Proof of Theorem 4.1 .

The decomposition can be constructed recursively. Given CFG $G=(\Sigma,\mathcal{N},\mathcal{S},\mathcal{P},\mathcal{W})$, the root node of the DAG – initially labelled with only $S$ – represents the entire grammar. If $S$ can generate itself through successive applications of rules of $G$, we add a self-loop from $S$ to itself.

Let $X\subseteq N$ be the subset of non-terminals on the right-hand side of any rule $S\rightarrow\alpha$. For each $A\in N$, let $G_{A}$ be the inner subgrammar generated by taking the closure of $A$ in $\mathcal{P}$ – that is, all the expansions $A\rightarrow\alpha$, all expansions of those non-terminals on the right-hand side of those rules, and so on. In the case that the result subgrammar is all of $G$, we can add $A$ as an additional label to the root node. Otherwise, $G_{A}$ is a proper inner subgrammar, in which case we assign it a node as a child of $S$. Inductively, this procedure is applied to each new subgrammar node (which by construction has strictly fewer non-terminals than its supergrammar).
∎

###### Proof of Theorem 4.3 .

Theorems [4.3](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem3) and Corollary [4.4](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem4) are equivalent, for simplicity we directly prove Corollary [4.4](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem4).

Let $A_{1},\ldots,A_{k}$ be the top-level subgrammars of $G$. Let $S\rightarrow A_{i_{1,1},\ldots,i_{1,l_{1}}}$, …, $S\rightarrow A_{i_{r,1},\ldots,i_{r,l_{r}}}$ be all rules expanding $S$ in $\mathcal{P}$, with probabilities $p_{1},\ldots,p_{r}$ respectively. As we are directly proving Corollary [4.4](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem4), we assume $S$ expands only to non-terminals (by which we will also denote the top-level subgrammars; note that some of these may be $S$ itself if they are not proper subgrammars).

Denoting $P=P_{G}$ and $Q=Q_{\theta}$,

$$ $\displaystyle D_{\mathrm{KL}}(P~\|~Q)$ $\displaystyle=\sum_{s\in\Sigma^{*}}P(s)\log\frac{P(s)}{Q(s)}$ $\displaystyle=\sum_{j=1}^{r}p_{j}\sum_{a_{j,1},\ldots,a_{j,l_{j}}}P(a_{j,1}\cdots a_{j,l_{j}})\log\frac{P(a_{j,1}\cdots a_{j,l_{j}})}{Q(a_{j,1}\cdots a_{j,l_{j}})}$ $\displaystyle=\sum_{j=1}^{r}p_{j}\sum_{a_{j,1},\ldots,a_{j,l_{j}}}P_{A_{j,1}}(a_{j,1})\cdots P_{A_{j,l_{j}}}(a_{j,l_{j}})\sum_{i=1}^{l_{j}}\log\frac{P_{A_{j,i}}(a_{j,i})}{Q(a_{j,i}|a_{j,1}\cdots a_{j,i-1})}$ $\displaystyle=\Big[\sum_{j=1}^{r}p_{j}\sum_{i=1}^{l_{j}}\sum_{a_{j,1},\ldots,a_{j,i-1}}P_{A_{j,1}}(a_{j,1})\cdots P_{A_{j,i-1}}(a_{j,i-1})\Big]\sum_{a}P_{A_{j,i}}(a)\log\frac{P_{A_{j,i}}(a)}{Q(a|a_{j,1}\cdots a_{j,i-1})}$ $\displaystyle=\sum_{i=1}^{k}\sum_{s}P_{G}(s|\epsilon)P_{G}(A|s)\sum_{a}P_{A_{i}}\log\frac{P_{A_{i}}(a)}{Q(a|s)}$ $$

∎

###### Corollary A.1 .

Suppose $G$ has subgrammars $Z_{1},\ldots,Z_{l}$ as irreducible “leaf" subgrammars in its DAG subgrammar decomposition, and all rules evaluate to strings of only non-terminals, or only-terminals. Then

$$ $D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})=\sum_{i=1}^{l}D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})_{Z_{i}}$ $$

###### Proof of Theorem 4.6 .

Let $G$ be a PCFG with top-level, proper subgrammars $A_{1},\ldots,A_{k}$. Summing over the top-level rules (expansions of $S$), suppose $S$ maps to a rule with $i$ recursive $S$’s with probability $p_{i}$ ($\sum_{i=0}^{N}p_{i}=1$ for some $N<\infty$). Then, $\mathbb{E}[R]=\sum_{i=1}^{N}p_{i}\cdot i$. Then by Corollary [4.5](https://arxiv.org/html/2510.02524v1#S4.Thmtheorem5) (treating both proper subgrammars and recursive $S$ as top-level subgrammars), we have

$$ $\displaystyle D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})$ $\displaystyle=\sum_{i=1}^{k}D_{\mathrm{KL}}(P_{A_{i}}~\|~Q_{\theta}(A_{i}))+\sum_{i=1}^{N}p_{i}\cdot iD_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})$ $\displaystyle=\sum_{i=1}^{k}D_{\mathrm{KL}}(P_{A_{i}}~\|~Q_{\theta}(A_{i}))+\mathbb{E}[R]D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})$ $\displaystyle\implies~D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})$ $\displaystyle=\frac{\sum_{i=1}^{k}D_{\mathrm{KL}}(P_{A}~\|~Q_{\theta}(A_{i}))}{1-\mathbb{E}[R]}$ $$

∎

###### Theorem A.2 .

For $G$ with outer subgrammar $A$, let $\bar{A}$ be its complement. The KL-divergence splits as a weighted sum:

$$ $D_{\mathrm{KL}}(P_{G}~\|~Q_{\theta})=P_{G}(A)D_{\mathrm{KL}}(P_{A}~\|~Q_{\theta}|_{A})+P_{G}(\bar{A})D_{\mathrm{KL}}(P_{G}|_{\bar{A}}~\|~Q_{\theta}|_{\bar{A}})+D_{\mathrm{KL}}(P_{G}^{*}~\|~Q_{\theta}^{*})$ $$

Where $D^{*}$, for $D\in\{P_{G},Q_{\theta}\}$ is the 2 valued distribution of whether $D$ outputs a string in $A$ or $\bar{A}$, $P_{A}$ is the language from CFG $A$, and $D|_{B}$ indicates the marginal distrubution of $D$ over strings of $B\in\{A,\bar{A}\}$.

###### Proof.

Writing $P$ for $P_{G}$ and $Q$ for $Q_{\theta}$ for legibility,

$$ $\displaystyle D_{\mathrm{KL}}(P~\|~Q)$ $\displaystyle=\sum_{s\in A}P(s)\log\frac{P(s)}{Q(s)}+\sum_{s\in\bar{A}}P(s)\log\frac{P(s)}{Q(s)}$ $\displaystyle=P(A)\sum_{s\in A}P_{A}(s)[\log P(A)+\log P|_{A}(s)-\log Q^{*}(A)-\log Q|_{A}(s)]$ $\displaystyle+P(\bar{A})\sum_{s\in\bar{A}}P|_{\bar{A}}(s)[\log P(\bar{A})+\log P|_{\bar{A}}(s)-\log Q^{*}(\bar{A})-\log Q|_{\bar{A}}(s)]$ $$

From which the final decomposition follows quite immediately by rearranging terms.
∎

###### Proof of Proposition 3.9 .

###### Proof of Theorem 4.1 .

###### Proof of Theorem 4.3 .

###### Corollary A.1 .

###### Proof of Theorem 4.6 .

###### Theorem A.2 .

###### Proof.

## Appendix B Additional Experimental results

### B.1 ChatGPT-5 Instant Arithmetic Stress Test

We generate arithmetic expressions using integers uniformly sampled from 0–9 and the operators {+, -, *, / } are generated. Expression depth is defined as the maximum level of nested parentheses. *Non-deep chains* consist of 50 expressions of depth at most 2, concatenated by addition. *Deep chains* consist of single expressions with recursive nesting up to depth 7. Below are an example each:

Non-deep arithmetic expression:
$((4*4)*(1-9))+((6/3)*(5/1))+((2-8)*(8/5))+((5/9)*(7*7))+((7-4)+(8/7))+((9-6)+(1-0))+((0/1)+(9-9))+((4/1)+(0+5))+((6+6)/(2/5))+((4/5)+(0-2))+((3*1)+(5+3))+((1-0)-(7-6))+((2*5)*(5/3))+((6+9)-(6/1))+((1+4)/(6+9))+((9/7)-(6+2))+((6-7)/9)+((4+1)+(7-3))+((5-3)-(1*3))+((5+6)+4)+((5*2)+(0-0))+((6*7)*8)+((5/2)+(4+6))+((5/5)*(9/6))+((4-3)*(8*7))+((7/3)*(9+3))+((7-0)+(5/9))+((6/8)-(2+0))+((0+6)/4)+((9-5)-(3-9))+((0+1)+(9-4))+((7-7)*(1-8))+((7-1)+9)+((4-0)+(0*8))+((6/9)*(2-2))+((5-6)-(8/4))+((3*5)/(4+2))+((3*4)-(5+2))+((7-1)+(8/8))+((4*0)-(9+7))+((3/6)-(4/3))+((0-2)-(1/9))+((0-8)*(8*0))+((0/1)*(2/8))+((9+5)*(8/3))+((1+8)/(4-9))+((0*6)*(2+4))+((5/6)+(2+0))+((2*7)-(2/2))+((8+8)*2)$
Result: $\frac{707449}{1260}$

Deep arithmetic expression:
$(((((((3+8)+(5-1))-((1-6)+(5+3)))+(((8-2)-(3-8))+((2*9)*(4+5))))*((((1/7)-(6*4))*((7+3)*(6+6)))-(((8*3)*(1+8))+((5-9)+(7/1)))))+(((((8*6)/(5-3))*((8*0)-(8-0)))+(((8-9)+(3-6))-((9/8)/(7*8))))/((((7-4)*(2+2))-((3-5)/(9-2)))/(((6/8)+(5*5))*((4-1)-(8+8))))))-((((((4-0)/(4-8))*((8-0)-(3-1)))+(((7*7)*(4/7))*((7*0)-(0/7))))-((((8*6)/(8+7))-((8/8)+(8/4)))-(((5+5)*(9*8))-((9/2)/(3-9)))))+(((((9-8)+(2*1))-((4+3)/(9-5)))/(((2*2)*(4*3))-((6-6)-(6+9))))*((((8/8)-(3*3))/((8+0)+(9/1)))*(((2*1)*6)*((1+5)/8))))))$
Result: $\frac{892410719}{448320600}$

### B.2 Recursive Decomposition Experiments

Figure: Figure 4: Two-layer Transformer showing the impact of the probability of recursion.
Refer to caption: Figures/kl_over_epochs_TwoLayer.png

### B.3 Pretraining Results

This appendix provides the detailed results referenced in the main text. All experiments compare transformers trained from scratch against those pretrained on a subgrammar before continuing on the full grammar.
Figure [5](https://arxiv.org/html/2510.02524v1#A2.F5) shows that no matter which subgrammar is chosen, when later training on the full grammar, it is not forgotten.

Figure: (a) Pretraining on an infix subgrammar
Refer to caption: Figures/kl_divergence_plot_TwoLayer_SMALL_ABC_grammar2_L1b.png

Figure [6](https://arxiv.org/html/2510.02524v1#A2.F6) illustrates the distribution of KL-divergences across 30 seeds when training directly versus with 10 epochs of subgrammar pretraining. Pretraining consistently shifts the distribution toward lower KL.

Figure: (a) Two-layer Transformer
Refer to caption: Figures/kl_comparison_boxplot_TwoLayer_SMALL_pretrain10.png

Table [2](https://arxiv.org/html/2510.02524v1#A2.T2) reports average cosine similarity across attention and MLP layers, on three types of test sequences: (i) sequences consisting solely of subgrammar subsequences, (ii) sequences with no subgrammar subsequences, and (iii) sequences mixing subgrammar and other subsequences.

**Table 2: Average cosine similarity [-1, +1] across attention and MLP layers of a two-layer Transformer when pretraining for 10 epochs. *Percentage change* indicates the relative difference between models trained from scratch and with pretraining.**
|  | Attention | MLP |
| --- | --- | --- |
| Sequences with subgrammar only |  |  |
| From Scratch | 0.660 | 0.635 |
| With Pretraining | 0.743 | 0.611 |
| *Percentage change (%)* | *+12.6* | *-3.9* |
| Sequences without subgrammar |  |  |
| From Scratch | 0.835 | 0.837 |
| With Pretraining | 0.876 | 0.841 |
| *Percentage change (%)* | *+4.9* | *+0.5* |
| Sequences with subgrammar |  |  |
| From Scratch | 0.726 | 0.501 |
| With Pretraining | 0.687 | 0.543 |
| *Percentage change (%)* | *-5.7* | *+8.4* |

### B.4 Generalization and Prefix Experimentsn

This appendix provides the detailed figures referenced in the main text. They compare how different valid prefixes (shallow vs. deeply recursive) and malformed prefixes affect model stability, showing that deeply recursive but valid prefixes can degrade performance even more than ungrammatical ones.

Figure: (a) Prefix = $(a)(a)(a)(a)(a)(a)$
Refer to caption: Figures/logit_differences_case_3_shallow_recursion.png

## Appendix C Definition of Grammars used for Experiments

In this section we properly introduce the PCFGs used for running the experiments.

### KL decomposition example 1

$$ $\displaystyle L1\;\to$ $\displaystyle\texttt{sL2_2}\;L2_2\;\texttt{eL2_2}\;\texttt{sL2_1}\;L2_1\;\texttt{eL2_1}\;\texttt{sL2_3}\;L2_3\;\texttt{eL2_3}\;[0]$ $\displaystyle L2_1\;\to$ $\displaystyle NUM\;[4]\;\mid\;L2_1\;\texttt{*}\;L2_1\;[15]\;\mid\;L2_1\;\texttt{+}\;L2_1\;[15]\;\mid\;NUM\;NUM\;[3]$ $\displaystyle L2_2\;\to$ $\displaystyle\texttt{a}\;L2_2\;\texttt{b}\;[6]\;\mid\;\texttt{c}\;[4]$ $\displaystyle L2_3\;\to$ $\displaystyle\texttt{x}\;L2_3\;[8]\;\mid\;\texttt{x}\;[2]$ $\displaystyle NUM\;\to$ $\displaystyle\texttt{0}\;[2]\;\mid\;\texttt{1}\;[2]\;\mid\;\texttt{2}\;[2]\;\mid\;\texttt{3}\;[2]\;\mid\;\texttt{4}\;[1]\;\mid\;\texttt{5}\;[1]$ $$

### KL decomposition example 2

$$ $\displaystyle L1\;\to$ $\displaystyle\texttt{sL2_1}\;L2_1\;\texttt{eL2_1}\;\;[3]\;\mid\;\texttt{sL2_2}\;L2_2\;\texttt{eL2_2}\;\;[3]\;\mid\;\texttt{sL2_3}\;L2_3\;\texttt{eL2_3}\;\;[4]$ $\displaystyle L2_1\;\to$ $\displaystyle NUM\;\;[4]\;\mid\;L2_1\;\texttt{*}\;L2_1\;\;[15]\;\mid\;L2_1\;\texttt{+}\;L2_1\;\;[15]\;\mid\;NUM\;NUM\;\;[3]$ $\displaystyle L2_2\;\to$ $\displaystyle\texttt{a}\;L2_2\;\texttt{b}\;\;[6]\;\mid\;\texttt{c}\;\;[4]$ $\displaystyle L2_3\;\to$ $\displaystyle\texttt{x}\;L2_3\;\;[8]\;\mid\;\texttt{x}\;\;[2]$ $\displaystyle NUM\;\to$ $\displaystyle\texttt{0}\;\;[2]\;\mid\;\texttt{1}\;\;[2]\;\mid\;\texttt{2}\;\;[2]\;\mid\;\texttt{3}\;\;[2]\;\mid\;\texttt{4}\;\;[1]\;\mid\;\texttt{5}\;\;[1]$ $$

### Deeper Recursion

$$ $\displaystyle L0\;\to$ $\displaystyle\texttt{sL1}\;L1\;\texttt{eL1}\;\;[7]\;\mid\;L0\;L0\;\;[3]$ $\displaystyle L1\;\to$ $\displaystyle\texttt{sL2}\;L2\;\texttt{eL2a}\;\;[6]\;\mid\;L1\;L1\;\;[3]\;\mid\;V\;\;[1]$ $\displaystyle L2\;\to$ $\displaystyle\texttt{sL3}\;L3\;\texttt{eL3}\;\;[6]\;\mid\;L2\;L2\;\;[3]\;\mid\;V\;\;[1]$ $\displaystyle L3\;\to$ $\displaystyle\texttt{sL4}\;L4\;\texttt{eL4}\;\;[6]\;\mid\;L3\;L3\;\;[3]\;\mid\;V\;\;[1]$ $\displaystyle L4\;\to$ $\displaystyle\texttt{(}\;V\;\texttt{)}\;\;[7]\;\mid\;V\;\;[3]$ $\displaystyle V\;\to$ $\displaystyle\texttt{a}\;\;[04]\;\mid\;\texttt{b}\;\;[04]\;\mid\;\texttt{c}\;\;[04]\;\mid\;\texttt{d}\;\;[04]\;\mid\;\texttt{e}\;\;[04]\;\mid\;\texttt{f}\;\;[04]\;\mid\;\texttt{g}\;\;[04]$ $\displaystyle\texttt{h}\;\;[04]\;\mid\;\texttt{i}\;\;[04]\;\mid\;\texttt{j}\;\;[04]\;\mid\;\texttt{k}\;\;[04]\;\mid\;\texttt{l}\;\;[04]\;\mid\;\texttt{m}\;\;[04]\;\mid\;\texttt{n}\;\;[04]$ $\displaystyle\texttt{o}\;\;[04]\;\mid\;\texttt{p}\;\;[04]\;\mid\;\texttt{q}\;\;[04]\;\mid\;\texttt{r}\;\;[04]\;\mid\;\texttt{s}\;\;[04]\;\mid\;\texttt{t}\;\;[04]\;\mid\;\texttt{u}\;\;[04]$ $\displaystyle\texttt{v}\;\;[04]\;\mid\;\texttt{w}\;\;[04]\;\mid\;\texttt{x}\;\;[04]\;\mid\;\texttt{y}\;\;[04]$ $$

### Unified Subgrammar Example

$$ $\displaystyle START\;\to$ $\displaystyle\texttt{sSUBJ}\;SUBJ\;\texttt{eSUBJ}\;\texttt{sVERB}\;VERB\;\texttt{eVERB}\;\texttt{sOBJ}\;OBJ\;\texttt{eOBJ}\;\;[0]$ $\displaystyle SUBJ\;\to$ $\displaystyle\mathbf{NOUN}\;\;[2]\;\mid\;\texttt{a}\;NOUN\;\;[4]\;\mid\;\texttt{the}\;NOUN\;\;[4]$ $\displaystyle NOUN\;\to$ $\displaystyle\mathbf{N}\;\;[7]\;\mid\;ADJ\;NOUN\;\;[3]$ $\displaystyle VERB\;\to$ $\displaystyle\mathbf{V}\;\;[3]\;\mid\;V\;ADV\;\;[7]$ $\displaystyle OBJ\;\to$ $\displaystyle\mathbf{blank}\;\;[5]\;\mid\;\texttt{with}\;SUBJ\;\;[5]$ $\displaystyle N\;\to$ $\displaystyle\texttt{dog}[2]\mid\texttt{cat}[2]\mid\texttt{fox}[1]\mid\texttt{parrot}[1]\mid\texttt{hamster}[1]\mid\texttt{turtle}[1]\mid$ $\displaystyle\texttt{horse}[1]\mid\texttt{pig}[1]$ $\displaystyle ADJ\;\to$ $\displaystyle\texttt{big}[2]\mid\texttt{poisonous}[2]\mid\texttt{cute}[2]\mid\texttt{lazy}[2]\mid\texttt{quick}[2]$ $\displaystyle V\;\to$ $\displaystyle\texttt{eats}[15]\mid\texttt{runs}[4]\mid\texttt{sleeps}[15]\mid\texttt{talks}[15]\mid\texttt{cleans itself}[15]$ $\displaystyle ADV\;\to$ $\displaystyle\texttt{quickly}[2]\mid\texttt{slowly}[3]\mid\texttt{happily}[3]\mid\texttt{excitedly}[1]\mid\texttt{lazily}[1]$ $$

where the rules that are used for the unified subgrammar are highlighted in bold.

### ABC Grammar

$$ $\displaystyle L0\;\to$ $\displaystyle\texttt{sL1a}\;L1a\;\texttt{eL1a}\;\texttt{sL1b}\;L1b\;\texttt{eL1b}\;\texttt{sL1c}\;L1c\;\texttt{eL1c}\;\;[0]$ $\displaystyle L1a\;\to$ $\displaystyle\texttt{sL2a}\;L2a\;\texttt{eL2a}\;L1a\;\texttt{sL2_2a}\;L2_2a\;\texttt{eL2_2a}\;\;[4]\;\mid\;\texttt{sL2a}\;L2a\;\texttt{eL2a}\;L1a\;\;[2]\;\mid\;$ $\displaystyle\texttt{action}\;\;[4]$ $\displaystyle L1b\;\to$ $\displaystyle L1b\;\texttt{+}\;\texttt{sL2b}\;L2b\;\texttt{eL2b}\;\;[25]\;\mid\;\texttt{sL2b}\;L2b\;\texttt{eL2b}\;\;[75]$ $\displaystyle L1c\;\to$ $\displaystyle\texttt{xy}\;L1c\;\;[3]\;\mid\;\texttt{x}\;L1c\;\;[3]\;\mid\;\texttt{sL2c}\;L2c\;\texttt{eL2c}\;\;[4]$ $\displaystyle L2a\;\to$ $\displaystyle\texttt{sL3}\;L3\;\texttt{eL3}\;\;[5]\;\mid\;\texttt{not}\;L2a\;\;[25]\;\mid\;L2a\;\texttt{and}\;L2a\;\;[1]\;\mid\;L2a\;\texttt{or}\;L2a\;\;[15]$ $\displaystyle L2_2a\;\to$ $\displaystyle\texttt{a}\;L2_2a\;\;[8]\;\mid\;\texttt{a}\;\;[2]$ $\displaystyle L2b\;\to$ $\displaystyle\texttt{a}\;L2b\;\texttt{b}\;\;[6]\;\mid\;\texttt{c}\;\;[4]$ $\displaystyle L2c\;\to$ $\displaystyle\texttt{c}\;L2_2ac\;\;[7]\;\mid\;\texttt{c}\;\;[6]$ $\displaystyle L3\;\to$ $\displaystyle\texttt{==}\;\;[2]\;\mid\;\texttt{<=}\;\;[2]\;\mid\;\texttt{<}\;\;[2]\;\mid\;\texttt{>=}\;\;[2]\;\mid\;\texttt{>}\;\;[2]$ $$

### Nested Parentheses

$$ $\displaystyle L0\;\to$ $\displaystyle\texttt{(}\;L1\;\texttt{)}\;[7]\;\mid\;L0\;L0\;[3]$ $\displaystyle L1\;\to$ $\displaystyle\texttt{(}\;L1\;\texttt{)}\;[8]\;\mid\;\texttt{a}\;[2]$ $$

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 2
presentation: 1
questions: None.
soundness: 2
strengths: It is important to understand how transformers learn CFGs. Although previous work (Allen-Zhu et. al. 2023) has studied in detail of the mechanism on how transformers implement CFGs, the dynamic analysis remains blank. The paper studies this important problem. They reveal an interesting phenomenon that transformers lean all subgrammars simultaneously.
summary: The paper investigates how transformers learn probabilistic context-free grammars (PCFGs). It first derives several theoretical properties describing how the KL divergence of PCFGs decomposes over subgrammars. Using this framework, the authors show that transformers learn all grammatical components in parallel, unlike humans who acquire syntax hierarchically. Experiments with small transformers confirm these findings and demonstrate that pretraining on subgrammars improves performance and yields more structured internal representations, though the benefit decreases for larger models. Finally, the study shows that models can manage long but shallow dependencies yet struggle with deeply recursive syntax, a limitation also observed in large language models.
weaknesses: Although the topic is important, the results feel incomplete and lack depth.  

1. The theoretical part at the beginning is quite trivial and unnecessary for understanding the dynamics. The first main result only appears at the end of page 6, making the presentation hard to follow.  

2. Regarding how transformers implement CFGs, Allen-Zhu et al. (2023) have already provided detailed and insightful analysis that largely covers the results here. The paper does not clearly explain its own contribution beyond that work.  

3. The only genuinely new finding seems to be that transformers learn all subgrammars simultaneously, but the analysis is shallow. I would like to see more detailed investigations and ablations to uncover the mechanisms behind this behavior.

---

confidence: 3
contribution: 2
initial_rating: 2
presentation: 2
questions: See weaknesses section.
soundness: 2
strengths: This is an ambitious and relevant topic, and I do believe that studying how language models acquire simplified formal languages is the path towards a predictive theory of large language models.
summary: The paper aims to study how transformers learn context-free grammars as a step toward a theory of language modelling. The authors claim that transformer training on context-free grammars can be understood by decomposing the cross-entropy loss into contributions from subgrammars. Under the assumption that a language model "understands composition", the authors derive a decomposition of the loss that elucidates the role of subgrammars and their recursive occurrence. This is an interesting and timely direction, but the contribution is unclear to me. Due to this lack of clarity, it's impossible for me to properly judge this contribution unless some of my doubts are addressed first (see below).
weaknesses: ### Relation to previous literature

First, the claim that the authors' work "initiates the study of the learning dynamics of transformers trained on PCFGs" is wrong. There are at least two groups contributing in this direction: https://arxiv.org/abs/2406.00048 (see also https://journals.aps.org/prx/abstract/10.1103/PhysRevX.14.031001?__cf_chl_rt_tk=UOc8KN3VOXQLYip1DgN1hgH_sgm85mQO4KFwHUmz38A-1761924271-1.0.1.1-05csO._aVplfQKTVpNHOiSYCZ.oTz8qXQePSbQqMnLE, https://arxiv.org/abs/2505.07070, ) and https://arxiv.org/abs/2305.13673v4 (one iteration https://openreview.net/forum?id=qnbLGV9oFL also shares a portion of the title with the present submission). These contributions should be acknowledged and their relation to the present paper discussed.

---

### Clarification of the exact contribution

If I understand correctly, the main technical contribution is the proposed loss decomposition. What is the intended consequence of this result? For instance, the authors claim that the decomposition implies that the model learns all subgrammars in parallel. However, a decomposition of the population loss can only constrain the location of the final optimum, not the dynamics of optimisation. In particular, it has no direct implications for convergence rates, sample complexities, or learning order. What additional assumptions would be required to justify the claim of “parallel learning”?

---

### Technical claims

1. **Inconsistent notation (pp. 4–5).** Symbols change mid-derivation (e.g., (P(\alpha\dots)) vs (P(\alpha\mid\varepsilon))), and in *Definition 4.2* the dependence of the summand on (a) is unclear. Please fix the notation globally and clarify how (a) enters the RHS of Def. 4.2/

2. **Application of Definition 4.2.** When (A) is a fixed string (as in (D_{\mathrm{KL}}(P\Vert Q)_{\alpha})), I cannot reproduce the final equation on p. 4. An explicit worked example would help verify the derivation.

3. **KL decomposition  of Theorem 4.3. from Definition 4.2.** Please show the full derivation of the KL decomposition.

4. **“Understanding compositionality.”** This assumption is too vague. Does it hold before, during, or after training, and what measurable property defines it?

6. **Implications of Theorem 4.6.**  Specify whether the result concerns the population optimum or predicts learning dynamics (rates, ordering, or sample complexity). If the latter, state the additional assumptions required for “parallel learning.”

---

### Empirical validation

The empirical section does not clearly test the theoretical claims. If the main statement is that the overall loss equals the sum of the losses over subgrammars, this should be explicitly validated in a figure, rather than requiring the reader to infer it by visually summing multiple curves. Moreover, the role of Figure 2 is unclear relative to Figure 1---what new information does it convey? Finally, the dependence on the recursion number (R, or rather its expected value), is never systematically explored or quantified.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: In the activation space analysis you show that pretraining on in-domain data helps. How would you take this further, i.e. do you see some options for using more complex/gradual curricula?

The deeper recursion experiment is interesting, do you see a way to connect it to the curricula approach?
soundness: 3
strengths: The idea of studying the learnability of sub-grammars is sound and interesting. And using formal languages is a, by now, common approach to study learnability. Using hierarchical subgrammars is a natural, and the decomposition of the KL is as expected.

The pedagogical approach of the paper, laying out standard definitions and derivations is welcome. And giving "worked examples” of e.g. the KL decomposition at the bottom of page 4.

The three kinds of analysis are nice (albeit a bit shallow individually)
summary: The work analyses the language models’ learnability of PCFGs. They introduce a subrammar-based framework for probing an architectures learnability. A subgrammar decomposed KL is derived. The authors find that the loss decreases in parallel over the subgrammars. The work also considers the impact of pre-training and depth of the grammars.
weaknesses: The work overstates the novelty of using CFGs to probe language models' learnability, e.g. in the introduction “this work initiates the theoretical and empirical study of training dynamics over CFGs” but this is repeated in many places. See for instance Sennhauser and Berwick 2018 (Evaluating the Ability of LSTMs to Learn Context-Free Grammars), or Allen-Zhu et al 2023 (How Language Models Learn Context-Free Grammars).

Another drawback is that the grammars are tiny, and the model sizes not ablated with grooving grammars. I understand a framework is being suggested, but to justify the framework it would be good to do some kind of scaling. It doesn't have to be for very large models, or CFGs with thousands of rules. But sampling grammars (and averaging over them) and doing so for grammar sizes of e.g. 10,100,200,400,800 rules would indicate whether the findings are due to the simplicity of the languages or not. Especially in a section titled “How Language Models Learn”

In line 301 you say you train on several synthetic CFGs on transformers, but the settings are missing or not referenced. I.e. architecture and training parameters, grammars sizes.

In line 379 you make a claim about an effect that diminishes as models size and complexity increase but it seems to be backed by a single example.

The ChatGPT-5-Instant experiment is unclear, what is the setup? It is also missing a citation or description. 

I recommend the authors fix the overly bold claims and smoothen the writing a bit, consider the related literature a bit better and strengthening the empirical study when revising their work. Ensuring full reproducibility is also important, make sure hyperparameters and configurations are reported and referenced.

Minor:
In the introduction you state that training an LLM for studying its training dynamics is unfeasible. Even so, there is plenty of room to study their learnability without reaching SOTA and no reason to believe the findings don't apply to the top models.

You could condense the standard definitions (kl, entropy, mle etc) a bit as prose, but im ok with the definition environment.

Please use numbers by equations (the equation or align environments), it’s hard to refer to them otherwise.

---

confidence: 3
contribution: 3
initial_rating: 4
presentation: 2
questions: 1. There appears to be two minor typo in the derivation in Section 4.2 (lines 211-213, page 4). In the second line of the equation.

The correct expansion of - log Q_\theta(\alpha a\beta) should be [ - log Q_\theta(\alpha ...) - log Q_\theta(a|\alpha) - log Q_\theta(\beta|\alpha a)]

The current text incorrectly uses positive signs for the second and third components. Additionally, the conditioning context for the final term appears as \beta|a\alpha, which seems to be a notational typo for the correct \beta|\alpha a.

In the third term of the equation on line 214, the probability $P(a)$ should likely be written as $P_A(a)$.

2. ChatGPT-5-Instant and ChatGPT-5-Thinking seems not formal name of these two models.
soundness: 3
strengths: 1. The paper provides an elegant theoretical derivation (Theorem 4.6) that helps explain why Transformers perform poorly on deeply nested grammatical structures . The recursive formula for KL divergence based on expected recurrence is a strong conceptual contribution.

2. The experiments show that Transformer models reduce loss across all subgrammars simultaneously, which contrasts with the developmental stages observed in human language acquisition.

3. The work includes a clear set of experiments on small models demonstrating that subgrammar pretraining can improve final performance , offering a practical insight for training on structured data.
summary: This paper investigates how Transformer-based autoregressive models learn languages generated by Probabilistic Context-Free Grammars (PCFGs). The authors provide a theoretical framework showing that the Kullback-Leibler (KL) divergence loss decomposes across the PCFG's subgrammar structure. Empirically, using small Transformer models, they demonstrate that models reduce loss across all subgrammars in parallel, rather than mastering simple structures first. Their experiments also reveal that these models perform poorly on deeply recursive structures and that pretraining on subgrammars can improve the final loss for these smaller models.
weaknesses: 1. The key "understands composition" assumption, which forms the basis for Corollary 4.5 and Theorem 4.6, is very strong. The paper does not provide sufficient empirical validation to determine to what extent this assumption holds for practical, trained models, which limits the applicability of these specific theorems.

2. The experiments on Large Language Models (LLMs) are limited to anecdotal tests on "ChatGPT-5-Instant". This experiment may conflates two different tasks: calculating the result of an arithmetic expression and modeling the grammar of that expression. The task of calculating a result is not equivalent to the task of generating an expression from a grammar, especially from a model training perspective. Therefore, the difficulty an already-trained model shows in calculating a deeply recursive arithmetic expression is not direct evidence that a Transformer-based model would struggle to be trained on a deeply recursive PCFG (the paper's primary claim).

3. The comparison in Section 5 between pretrained models and those trained from scratch seems unfair. Pretraining on a subgrammar essentially gives the model a strong hint, or an "inductive bias," about the PCFG's correct structure. The baseline model, however, gets no such hints and must discover this hidden structure all on its own. Therefore, the finding that pretraining improves the final loss for smaller models might primarily demonstrate the benefit of curriculum learning and injecting this strong structural prior.


Decision: Reject