# Simple Hardware-Efficient PCFGs with Independent Left and Right Productions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 46 references that are in the map.
- First posted on arXiv 23 Oct 2023.

## Builds on (most cited first, 25 of 25)

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks](https://mlsanity.com/paper/1810.09536/) (2018)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Neural Language Modeling by Jointly Learning Syntax and Lexicon](https://mlsanity.com/paper/1711.02013/) (2017)
- [Torch-Struct: Deep Structured Prediction Library](https://mlsanity.com/paper/2002.00876/) (2020)
- [Scaling Up Probabilistic Circuits by Latent Variable Distillation](https://mlsanity.com/paper/2210.04398/) (2022)
- [Visually Grounded Compound PCFGs](https://mlsanity.com/paper/2009.12404/) (2020)
- [StructFormer: Joint Unsupervised Induction of Dependency and Constituency Structure from Masked Language Modeling](https://mlsanity.com/paper/2012.00857/) (2020)
- [Sequence-to-Sequence Learning with Latent Neural Grammars](https://mlsanity.com/paper/2109.01135/) (2021)
- [Unsupervised Parsing via Constituency Tests](https://mlsanity.com/paper/2010.03146/) (2020)
- [PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols](https://mlsanity.com/paper/2104.13727/) (2021)
- [Neural Bi-Lexicalized PCFG Induction](https://mlsanity.com/paper/2105.15021/) (2021)
- [Video-aided Unsupervised Grammar Induction](https://mlsanity.com/paper/2104.04369/) (2021)
- [Fast-R2D2: A Pretrained Recursive Neural Network based on Pruned CKY for Grammar Induction and Text Representation](https://mlsanity.com/paper/2203.00281/) (2022)
- [Finding Dataset Shortcuts with Grammar Induction](https://mlsanity.com/paper/2210.11560/) (2022)
- [Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs](https://mlsanity.com/paper/2205.00484/) (2022)
- [Low-Rank Constraints for Fast Inference in Structured Models](https://mlsanity.com/paper/2201.02715/) (2022)
- [Hierarchical Phrase-based Sequence-to-Sequence Learning](https://mlsanity.com/paper/2211.07906/) (2022)
- [Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars](https://mlsanity.com/paper/2212.09140/) (2022)
- [Contextual Distortion Reveals Constituency: Masked Language Models are Implicit Parsers](https://mlsanity.com/paper/2306.00645/) (2023)
- [Improved Latent Tree Induction with Distant Supervision via Span Constraints](https://mlsanity.com/paper/2109.05112/) (2021)
- [Learning a Grammar Inducer from Massive Uncurated Instructional Videos](https://mlsanity.com/paper/2210.12309/) (2022)
- [Improving Grammar-based Sequence-to-Sequence Modeling with Decomposition and Constraints](https://mlsanity.com/paper/2306.02671/) (2023)

## Built on by (most cited first, 3 of 3)

- [Improving Unsupervised Constituency Parsing via Maximizing Semantic Information](https://mlsanity.com/paper/2410.02558/) (2024)
- [Probability Distribution Collapse: A Critical Bottleneck to Compact Unsupervised Neural Grammar Induction](https://mlsanity.com/paper/2509.20734/) (2025)
- [Holographic Neural PCFG for Unsupervised Parsing](https://mlsanity.com/paper/2607.08063/) (2026)

## Abstract (arXiv)

Scaling dense PCFGs to thousands of nonterminals via a low-rank parameterization of the rule probability tensor has been shown to be beneficial for unsupervised parsing. However, PCFGs scaled this way still perform poorly as a language model, and even underperform similarly-sized HMMs. This work introduces SimplePCFG, a simple PCFG formalism with independent left and right productions. Despite imposing a stronger independence assumption than the low-rank approach, we find that this formalism scales more effectively both as a language model and as an unsupervised parser. As an unsupervised parser, our simple PCFG obtains an average F1 of 65.1 on the English PTB, and as a language model, it obtains a perplexity of 119.0, outperforming similarly-sized low-rank PCFGs. We further introduce FlashInside, a hardware IO-aware implementation of the inside algorithm for efficiently scaling simple PCFGs.