EMNLP Findings2023
Simple Hardware-Efficient PCFGs with Independent Left and Right Productions
Abstract
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 lowrank PCFGs. We further introduce FlashInside, a hardware IO-aware implementation of the inside algorithm for efficiently scaling simple PCFGs.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Probability Distribution Collapse: A Critical Bottleneck to Compact Unsupervised Neural Grammar Induction cites Unsupervised Parsing with S-DIORA: Single Tree Encoding for Deep Inside-Outside Recursive Autoencoders
- Sequence-to-Sequence Learning with Latent Neural Grammars cites Visually Grounded Compound PCFGs
- Improving Unsupervised Constituency Parsing via Maximizing Semantic Information cites Visually Grounded Compound PCFGs
- On Eliciting Syntax from Language Models via Hashing cites Unsupervised Parsing with S-DIORA: Single Tree Encoding for Deep Inside-Outside Recursive Autoencoders
Cited by top-tier papers3
- Probability Distribution Collapse: A Critical Bottleneck to Compact Unsupervised Neural Grammar InductionJinwook Park, Kangil KimEMNLP 2025
- Improving Unsupervised Constituency Parsing via Maximizing Semantic InformationJunjie Chen, Xiangheng He, Yusuke Miyao, Danushka BollegalaICLR 2025
- On Eliciting Syntax from Language Models via HashingYiran Wang, Masao UtiyamaEMNLP 2024
Builds on17
- FlashAttention: Fast and Memory-Efficient Exact Attention with IO-AwarenessTri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra et al.NeurIPS 2022 · 5,493 citations
- Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic CircuitsRobert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner et al.ICML 2020 · 155 citations
- Sequence-to-Sequence Learning with Latent Neural GrammarsYoon KimNeurIPS 2021 · 44 citations
- Visually Grounded Compound PCFGsYanpeng Zhao, Ivan TitovEMNLP 2020 · 35 citations
- Unsupervised Parsing with S-DIORA: Single Tree Encoding for Deep Inside-Outside Recursive AutoencodersAndrew Drozdov, Subendhu Rongali, Yi-Pei Chen, Tim O'Gorman et al.EMNLP 2020 · 27 citations
Related papers
- Do Transformers Parse while Predicting the Masked Word?Haoyu Zhao, Abhishek Panigrahi, Rong Ge, Sanjeev AroraEMNLP 2023 · 5 citations
- Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive GrammarsSonglin Yang, Roger Levy, Yoon KimACL 2023 · 1 citation
- Low-Rank Constraints for Fast Inference in Structured ModelsJustin T. Chiu, Yuntian Deng, Alexander M. RushNeurIPS 2021 · 14 citations
- Deep networks learn to parse uniform-depth context-free languages from local statisticsJack T. Parley, Francesco Cagnetta, Matthieu WyartICML 2026 · 4 citations
- Neural Bi-Lexicalized PCFG InductionSonglin Yang, Yanpeng Zhao, Kewei TuACL 2021
