# Do Transformers Parse while Predicting the Masked Word?

arXiv: https://arxiv.org/abs/2303.08117 · HTML: https://mlsanity.com/paper/2303.08117/

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 59 references that are in the map.
- First posted on arXiv 14 Mar 2023.

## Builds on (most cited first, 30 of 32)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Understanding intermediate layers using linear classifier probes](https://mlsanity.com/paper/1610.01644/) (2016)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [A Primer in BERTology: What we know about how BERT works](https://mlsanity.com/paper/2002.12327/) (2020)
- [Designing and Interpreting Probes with Control Tasks](https://mlsanity.com/paper/1909.03368/) (2019)
- [What you can cram into a single vector: Probing sentence embeddings for linguistic properties](https://mlsanity.com/paper/1805.01070/) (2018)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Visualizing and Measuring the Geometry of BERT](https://mlsanity.com/paper/1906.02715/) (2019)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What do Neural Machine Translation Models Learn about Morphology?](https://mlsanity.com/paper/1704.03471/) (2017)
- [Probing Pretrained Language Models for Lexical Semantics](https://mlsanity.com/paper/2010.05731/) (2020)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Should You Mask 15% in Masked Language Modeling?](https://mlsanity.com/paper/2202.08005/) (2022)
- [Perturbed Masking: Parameter-free Probing for Analyzing and Interpreting BERT](https://mlsanity.com/paper/2004.14786/) (2020)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [How to Train BERT with an Academic Budget](https://mlsanity.com/paper/2104.07705/) (2021)
- [Probing Natural Language Inference Models through Semantic Fragments](https://mlsanity.com/paper/1909.07521/) (2019)
- [Syntax-BERT: Improving Pre-trained Transformers with Syntax Trees](https://mlsanity.com/paper/2103.04350/) (2021)
- [Probing BERT in Hyperbolic Spaces](https://mlsanity.com/paper/2104.03869/) (2021)
- [Are Pre-trained Language Models Aware of Phrases? Simple but Strong Baselines for Grammar Induction](https://mlsanity.com/paper/2002.00737/) (2020)
- [A Tale of a Probe and a Parser](https://mlsanity.com/paper/2005.01641/) (2020)
- [Syntax-Enhanced Pre-trained Model](https://mlsanity.com/paper/2012.14116/) (2020)
- [Do Syntactic Probes Probe Syntax? Experiments with Jabberwocky Probing](https://mlsanity.com/paper/2106.02559/) (2021)

## Built on by (most cited first, 30 of 48)

- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Transformers learn to implement preconditioned gradient descent for in-context learning](https://mlsanity.com/paper/2306.00297/) (2023)
- [Mechanistically analyzing the effects of fine-tuning on procedurally defined tasks](https://mlsanity.com/paper/2311.12786/) (2023)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [Exposing Attention Glitches with Flip-Flop Language Modeling](https://mlsanity.com/paper/2306.00946/) (2023)
- [JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attention](https://mlsanity.com/paper/2310.00535/) (2023)
- [The Closeness of In-Context Learning and Weight Shifting for Softmax Regression](https://mlsanity.com/paper/2304.13276/) (2023)
- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammars](https://mlsanity.com/paper/2312.01429/) (2023)
- [Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics](https://mlsanity.com/paper/2405.04669/) (2024)
- [When can transformers reason with abstract symbols?](https://mlsanity.com/paper/2310.09753/) (2023)
- [Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot](https://mlsanity.com/paper/2406.06893/) (2024)
- [Looped ReLU MLPs May Be All You Need as Practical Programmable Computers](https://mlsanity.com/paper/2410.09375/) (2024)
- [How transformers learn structured data: insights from hierarchical filtering](https://mlsanity.com/paper/2408.15138/) (2024)
- [Learning curves theory for hierarchically compositional data with power-law distributed features](https://mlsanity.com/paper/2505.07067/) (2025)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [Progressive distillation induces an implicit curriculum](https://mlsanity.com/paper/2410.05464/) (2024)
- [Is the Reversal Curse a Binding Problem? Uncovering Limitations of Transformers from a Basic Generalization Failure](https://mlsanity.com/paper/2504.01928/) (2025)
- [On the Query Complexity of Verifier-Assisted Language Generation](https://mlsanity.com/paper/2502.12123/) (2025)
- [Sample Complexity and Representation Ability of Test-time Scaling Paradigms](https://mlsanity.com/paper/2506.05295/) (2025)
- [Transparency at the Source: Evaluating and Interpreting Language Models With Access to the True Distribution](https://mlsanity.com/paper/2310.14840/) (2023)
- [Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regression](https://mlsanity.com/paper/2311.15390/) (2023)
- [Training Dynamics of Transformers to Recognize Word Co-occurrence via Gradient Flow Analysis](https://mlsanity.com/paper/2410.09605/) (2024)
- [Solving Tensor Low Cycle Rank Approximation](https://mlsanity.com/paper/2304.06594/) (2023)
- [The Expressibility of Polynomial based Attention Scheme](https://mlsanity.com/paper/2310.20051/) (2023)
- [How Well Do Large Language Models Understand Syntax? An Evaluation by Asking Natural Language Questions](https://mlsanity.com/paper/2311.08287/) (2023)
- [Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelines](https://mlsanity.com/paper/2407.21046/) (2024)

## Abstract (arXiv)

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.