# PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 28 Apr 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Efficient Attention: Attention with Linear Complexities](https://mlsanity.com/paper/1812.01243/) (2018)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [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)
- [Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Autoencoders](https://mlsanity.com/paper/1904.02142/) (2019)
- [Neural Language Modeling by Jointly Learning Syntax and Lexicon](https://mlsanity.com/paper/1711.02013/) (2017)
- [Fast and Accurate Neural CRF Constituency Parsing](https://mlsanity.com/paper/2008.03736/) (2020)
- [Unsupervised Recurrent Neural Network Grammars](https://mlsanity.com/paper/1904.03746/) (2019)
- [Torch-Struct: Deep Structured Prediction Library](https://mlsanity.com/paper/2002.00876/) (2020)
- [Visually Grounded Compound PCFGs](https://mlsanity.com/paper/2009.12404/) (2020)
- [Unsupervised Parsing via Constituency Tests](https://mlsanity.com/paper/2010.03146/) (2020)
- [Scaling Hidden Markov Language Models](https://mlsanity.com/paper/2011.04640/) (2020)
- [Unsupervised Neural Hidden Markov Models](https://mlsanity.com/paper/1609.09007/) (2016)
- [The Return of Lexical Dependencies: Neural Lexicalized PCFGs](https://mlsanity.com/paper/2007.15135/) (2020)
- [On the Role of Supervision in Unsupervised Constituency Parsing](https://mlsanity.com/paper/2010.02423/) (2020)
- [Unsupervised Learning of Syntactic Structure with Invertible Neural Projections](https://mlsanity.com/paper/1808.09111/) (2018)
- [Benefits of over-parameterization with EM](https://mlsanity.com/paper/1810.11344/) (2018)
- [Second-Order Unsupervised Neural Dependency Parsing](https://mlsanity.com/paper/2010.14720/) (2020)
- [An Empirical Study of Compound PCFGs](https://mlsanity.com/paper/2103.02298/) (2021)
- [Gaussian Mixture Latent Vector Grammars](https://mlsanity.com/paper/1805.04688/) (2018)

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

- [Grammar Prompting for Domain-Specific Language Generation with Large Language Models](https://mlsanity.com/paper/2305.19234/) (2023)
- [GFlowNet-EM for learning compositional latent variable models](https://mlsanity.com/paper/2302.06576/) (2023)
- [Sequence-to-Sequence Learning with Latent Neural Grammars](https://mlsanity.com/paper/2109.01135/) (2021)
- [Neural Bi-Lexicalized PCFG Induction](https://mlsanity.com/paper/2105.15021/) (2021)
- [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)
- [Learning a Grammar Inducer from Massive Uncurated Instructional Videos](https://mlsanity.com/paper/2210.12309/) (2022)
- [Simple Hardware-Efficient PCFGs with Independent Left and Right Productions](https://mlsanity.com/paper/2310.14997/) (2023)
- [Scaling Structured Inference with Randomization](https://mlsanity.com/paper/2112.03638/) (2021)
- [Unsupervised Parsing by Searching for Frequent Word Sequences among Sentences with Equivalent Predicate-Argument Structures](https://mlsanity.com/paper/2404.12059/) (2024)
- [Modeling Label Correlations for Second-Order Semantic Dependency Parsing with Mean-Field Inference](https://mlsanity.com/paper/2204.03619/) (2022)
- [Improving Grammar-based Sequence-to-Sequence Modeling with Decomposition and Constraints](https://mlsanity.com/paper/2306.02671/) (2023)
- [Greedy Grammar Induction with Indirect Negative Evidence](https://mlsanity.com/paper/2312.15321/) (2023)
- [Structural Optimization Ambiguity and Simplicity Bias in Unsupervised Neural Grammar Induction](https://mlsanity.com/paper/2407.16181/) (2024)
- [Improving Unsupervised Constituency Parsing via Maximizing Semantic Information](https://mlsanity.com/paper/2410.02558/) (2024)
- [Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing](https://mlsanity.com/paper/2403.00143/) (2024)
- [On Eliciting Syntax from Language Models via Hashing](https://mlsanity.com/paper/2410.04074/) (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)

Probabilistic context-free grammars (PCFGs) with neural parameterization have been shown to be effective in unsupervised phrase-structure grammar induction. However, due to the cubic computational complexity of PCFG representation and parsing, previous approaches cannot scale up to a relatively large number of (nonterminal and preterminal) symbols. In this work, we present a new parameterization form of PCFGs based on tensor decomposition, which has at most quadratic computational complexity in the symbol number and therefore allows us to use a much larger number of symbols. We further use neural parameterization for the new form to improve unsupervised parsing performance. We evaluate our model across ten languages and empirically demonstrate the effectiveness of using more symbols. Our code: https://github.com/sustcsonglin/TN-PCFG