# Scaling Hidden Markov Language Models

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2020.

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

- [Why Do Pretrained Language Models Help in Downstream Tasks? An Analysis of Head and Prompt Tuning](https://mlsanity.com/paper/2106.09226/) (2021)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Scaling Up Probabilistic Circuits by Latent Variable Distillation](https://mlsanity.com/paper/2210.04398/) (2022)
- [Sequence-to-Sequence Learning with Latent Neural Grammars](https://mlsanity.com/paper/2109.01135/) (2021)
- [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)
- [Protein Language Models and Structure Prediction: Connection and Progression](https://mlsanity.com/paper/2211.16742/) (2022)
- [BERTifying the Hidden Markov Model for Multi-Source Weakly Supervised Named Entity Recognition](https://mlsanity.com/paper/2105.12848/) (2021)
- [Breaking the Factorization Barrier in Diffusion Language Models](https://mlsanity.com/paper/2603.00045/) (2026)
- [Low-Resource Language Modelling of South African Languages](https://mlsanity.com/paper/2104.00772/) (2021)
- [Revisiting Simple Neural Probabilistic Language Models](https://mlsanity.com/paper/2104.03474/) (2021)
- [Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs](https://mlsanity.com/paper/2205.00484/) (2022)
- [On Limitation of Transformer for Learning HMMs](https://mlsanity.com/paper/2406.04089/) (2024)
- [Low-Rank Constraints for Fast Inference in Structured Models](https://mlsanity.com/paper/2201.02715/) (2022)
- [Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars](https://mlsanity.com/paper/2212.09140/) (2022)
- [MoVEInt: Mixture of Variational Experts for Learning Human-Robot Interactions from Demonstrations](https://mlsanity.com/paper/2407.07636/) (2024)
- [Scaling Structured Inference with Randomization](https://mlsanity.com/paper/2112.03638/) (2021)
- [Learning Dependencies of Discrete Speech Representations with Neural Hidden Markov Models](https://mlsanity.com/paper/2210.16659/) (2022)
- [Information Transfer Rate in BCIs: Towards Tightly Integrated Symbiosis](https://mlsanity.com/paper/2301.00488/) (2023)
- [Improving Grammar-based Sequence-to-Sequence Modeling with Decomposition and Constraints](https://mlsanity.com/paper/2306.02671/) (2023)
- [Investigating the Impact of Model Complexity in Large Language Models](https://mlsanity.com/paper/2410.00699/) (2024)
- [Learning Tractable Distributions Of Language Model Continuations](https://mlsanity.com/paper/2511.16054/) (2025)

## Abstract (arXiv)

The hidden Markov model (HMM) is a fundamental tool for sequence modeling that cleanly separates the hidden state from the emission structure. However, this separation makes it difficult to fit HMMs to large datasets in modern NLP, and they have fallen out of use due to very poor performance compared to fully observed models. This work revisits the challenge of scaling HMMs to language modeling datasets, taking ideas from recent approaches to neural modeling. We propose methods for scaling HMMs to massive state spaces while maintaining efficient exact inference, a compact parameterization, and effective regularization. Experiments show that this approach leads to models that are more accurate than previous HMM and n-gram-based methods, making progress towards the performance of state-of-the-art neural models.