# Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 64 references that are in the map.
- First posted on arXiv 1 May 2022.

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

- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Regularizing and Optimizing LSTM Language Models](https://mlsanity.com/paper/1708.02182/) (2017)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Fast and Accurate Neural CRF Constituency Parsing](https://mlsanity.com/paper/2008.03736/) (2020)
- [Introduction to Tensor Decompositions and their Applications in Machine Learning](https://mlsanity.com/paper/1711.10781/) (2017)
- [Torch-Struct: Deep Structured Prediction Library](https://mlsanity.com/paper/2002.00876/) (2020)
- [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)
- [Scaling Hidden Markov Language Models](https://mlsanity.com/paper/2011.04640/) (2020)
- [PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols](https://mlsanity.com/paper/2104.13727/) (2021)
- [The Return of Lexical Dependencies: Neural Lexicalized PCFGs](https://mlsanity.com/paper/2007.15135/) (2020)
- [Neural Bi-Lexicalized PCFG Induction](https://mlsanity.com/paper/2105.15021/) (2021)
- [Video-aided Unsupervised Grammar Induction](https://mlsanity.com/paper/2104.04369/) (2021)
- [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)
- [Learning higher-order sequential structure with cloned HMMs](https://mlsanity.com/paper/1905.00507/) (2019)
- [Second-Order Unsupervised Neural Dependency Parsing](https://mlsanity.com/paper/2010.14720/) (2020)
- [Low-Rank Constraints for Fast Inference in Structured Models](https://mlsanity.com/paper/2201.02715/) (2022)
- [Improved Latent Tree Induction with Distant Supervision via Span Constraints](https://mlsanity.com/paper/2109.05112/) (2021)
- [Neuralizing Efficient Higher-order Belief Propagation](https://mlsanity.com/paper/2010.09283/) (2020)
- [Factor Graph Grammars](https://mlsanity.com/paper/2010.12048/) (2020)
- [Scaling Structured Inference with Randomization](https://mlsanity.com/paper/2112.03638/) (2021)
- [Low-Rank Approximation of Weighted Tree Automata](https://mlsanity.com/paper/1511.01442/) (2015)
- [An Algebraic Formalization of Forward and Forward-backward Algorithms](https://mlsanity.com/paper/1702.06941/) (2017)
- [Searching for More Efficient Dynamic Programs](https://mlsanity.com/paper/2109.06966/) (2021)
- [Modeling Label Correlations for Second-Order Semantic Dependency Parsing with Mean-Field Inference](https://mlsanity.com/paper/2204.03619/) (2022)

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

- [Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars](https://mlsanity.com/paper/2212.09140/) (2022)
- [Augmenting Transformers with Recursively Composed Multi-grained Representations](https://mlsanity.com/paper/2309.16319/) (2023)
- [Simple Hardware-Efficient PCFGs with Independent Left and Right Productions](https://mlsanity.com/paper/2310.14997/) (2023)
- [SynJax: Structured Probability Distributions for JAX](https://mlsanity.com/paper/2308.03291/) (2023)
- [Improving Grammar-based Sequence-to-Sequence Modeling with Decomposition and Constraints](https://mlsanity.com/paper/2306.02671/) (2023)
- [Structural Optimization Ambiguity and Simplicity Bias in Unsupervised Neural Grammar Induction](https://mlsanity.com/paper/2407.16181/) (2024)
- [Unsupervised Morphological Tree Tokenizer](https://mlsanity.com/paper/2406.15245/) (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)

Hidden Markov Models (HMMs) and Probabilistic Context-Free Grammars (PCFGs) are widely used structured models, both of which can be represented as factor graph grammars (FGGs), a powerful formalism capable of describing a wide range of models. Recent research found it beneficial to use large state spaces for HMMs and PCFGs. However, inference with large state spaces is computationally demanding, especially for PCFGs. To tackle this challenge, we leverage tensor rank decomposition (aka. CPD) to decrease inference computational complexities for a subset of FGGs subsuming HMMs and PCFGs. We apply CPD on the factors of an FGG and then construct a new FGG defined in the rank space. Inference with the new FGG produces the same result but has a lower time complexity when the rank size is smaller than the state size. We conduct experiments on HMM language modeling and unsupervised PCFG parsing, showing better performance than previous work. Our code is publicly available at urlhttps://github.com/VPeterV/RankSpace-Models.