Abstract
Pre-trained language models have been shown to encode linguistic structures, e.g. dependency and constituency parse trees, in their embeddings while being trained on unsupervised loss functions like masked language modeling. Some doubts have been raised whether the models actually are doing parsing or only some computation weakly correlated with it. We study questions: (a) Is it possible to explicitly describe transformers with realistic embedding dimension, number of heads, etc. that are capable of doing parsing -- or even approximate parsing? (b) Why do pre-trained models capture parsing structure? This paper takes a step toward answering these questions in the context of generative modeling with PCFGs. We show that masked language models like BERT or RoBERTa of moderate sizes can approximately execute the Inside-Outside algorithm for the English PCFG [Marcus et al, 1993]. We also show that the Inside-Outside algorithm is optimal for masked language modeling loss on the PCFG-generated data. We also give a construction of transformers with $50$ layers, $15$ attention heads, and $1275$ dimensional embeddings in average such that using its embeddings it is possible to do constituency parsing with $>70\%$ F1 score on PTB dataset. We conduct probing experiments on models pre-trained on PCFG-generated data to show that this not only allows recovery of approximate parse tree, but also recovers marginal span probabilities computed by the Inside-Outside algorithm, which suggests an implicit bias of masked language modeling towards this algorithm.
Introduction
For years, researchers have used "linear probing" to demonstrate that Transformer embeddings contain sophisticated syntactic information, such as constituency parse trees. However, a persistent skepticism remains: are these models truly performing structural parsing, or are the probes simply extracting surface-level statistical correlations or semantic cues?
This research addresses two fundamental questions regarding the relationship between Transformers and syntax. First, is it architecturally feasible for a Transformer with a realistic number of heads and dimensions to implement a complex parsing algorithm? Second, why would a model trained solely on the objective of predicting missing words (Masked Language Modeling, or MLM) develop the machinery for syntactic parsing in the first place?
Theoretical Feasibility: Constructing a Parsing Transformer
Previous theoretical work suggested that Transformers could simulate parsing algorithms, but these constructions often required an impractical number of attention heads—sometimes scaling with the total number of rules in a grammar. For a complex language like English, this would imply thousands of heads, far exceeding the 12 to 16 heads found in models like BERT-base.
To bridge this gap, the authors mathematically constructed a Transformer capable of executing the Inside-Outside algorithm, a dynamic programming method used to calculate the probability of strings within a Probabilistic Context-Free Grammar (PCFG). They achieved "architectural realism" through two primary optimizations:
- Sparsity: By demonstrating that focusing on the most frequent non-terminals in a grammar retains the vast majority of parsing accuracy, they reduced the computational overhead.
- Low-Rank Approximation: By using linear transformations to group correlated non-terminals, they compressed the required operations.
The result is a construction requiring only approximately 15 attention heads and 1,275-dimensional embeddings to achieve a constituency parsing F1 score of over 70% on the Penn Treebank (PTB) dataset. This proves that standard Transformer architectures have more than enough capacity to perform formal parsing.
The Incentive: Why MLM Leads to Parsing
A central contribution of this paper is the mathematical proof that the Inside-Outside algorithm is the optimal strategy for minimizing MLM loss when the underlying data is generated by a PCFG.
In a grammatically structured sentence, the most accurate prediction for a masked word is derived from the marginal probabilities of all possible parse trees that could generate the observed context. Consequently, the MLM objective doesn't just allow for parsing; it actively incentivizes the model to approximate the Inside-Outside algorithm to achieve the lowest possible loss. This suggests an inherent implicit bias in the Transformer architecture toward learning hierarchical structure when trained on language-like data.
Empirical Validation and Probing
To move beyond theoretical proofs, the researchers conducted experiments using RoBERTa models trained on synthetic data generated from a PCFG. This synthetic approach was crucial to isolate syntax from semantic influences, ensuring that any learned structure was purely a result of the grammar and the MLM objective.
Key Findings:
- High Correlation: Probes of the trained models revealed a Pearson correlation of up to 0.93 between the models' internal representations and the theoretical marginal span probabilities calculated by the Inside-Outside algorithm. This indicates that the models are indeed approximating the internal states of the parsing algorithm.
- Early Saturation: Syntactic information appears to be captured early in the model's depth. Probing performance often saturated by the third or fourth layer, suggesting that while the model establishes structural foundations early, subsequent layers may be dedicated to more complex tasks or refining predictions.
- Generalizability: When models trained on synthetic PCFG data were tested on real-world PTB data, the probes still maintained significant performance. This suggests that the models learned generalizable syntactic principles rather than just memorizing synthetic patterns.
Conclusion
This work provides a rigorous foundation for the claim that Transformers "parse" during pre-training. By showing that parsing is both theoretically possible within realistic architectural constraints and mathematically optimal for the MLM objective, the authors clarify why models like BERT and RoBERTa are so effective at capturing linguistic structure. While future work is needed to explore how these findings apply to decoder-only models (like GPT) and more complex, context-sensitive grammars, this study marks a significant step in the mechanistic interpretability of large language models.
Summary updated