# A Fast Algorithm for Computing Prefix Probabilities

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2023.

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

- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [Mechanistic evaluation of Transformers and state space models](https://mlsanity.com/paper/2505.15105/) (2025)
- [Understanding Dynamic Compute Allocation in Recurrent Transformers](https://mlsanity.com/paper/2602.08864/) (2026)
- [Efficient Semiring-Weighted Earley Parsing](https://mlsanity.com/paper/2307.02982/) (2023)

## Abstract (arXiv)

Multiple algorithms are known for efficiently calculating the prefix probability of a string under a probabilistic context-free grammar (PCFG). Good algorithms for the problem have a runtime cubic in the length of the input string. However, some proposed algorithms are suboptimal with respect to the size of the grammar. This paper proposes a novel speed-up of Jelinek and Lafferty's (1991) algorithm, whose original runtime is O(n3 |N|3 + |N|4), where n is the input length and |N| is the number of non-terminals in the grammar. In contrast, our speed-up runs in O(n2 |N|3+n3|N|2).