# Efficient Semiring-Weighted Earley Parsing

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 98 references that are in the map.
- First posted on arXiv 6 Jul 2023.

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

- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Autoencoders](https://mlsanity.com/paper/1904.02142/) (2019)
- [Neural Datalog Through Time: Informed Temporal Modeling via Logical Specification](https://mlsanity.com/paper/2006.16723/) (2020)
- [The Whole Truth and Nothing But the Truth: Faithful and Controllable Dialogue Response Generation with Dataflow Transduction and Constrained Decoding](https://mlsanity.com/paper/2209.07800/) (2022)
- [A Fast Algorithm for Computing Prefix Probabilities](https://mlsanity.com/paper/2306.02303/) (2023)

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

- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMs](https://mlsanity.com/paper/2601.04426/) (2026)
- [Earley-Driven Dynamic Pruning for Efficient Structured Decoding](https://mlsanity.com/paper/2506.01151/) (2025)

## Abstract (arXiv)

This paper provides a reference description, in the form of a deduction system, of Earley's (1970) context-free parsing algorithm with various speed-ups. Our presentation includes a known worst-case runtime improvement from Earley's O (N3|G||R|), which is unworkable for the large grammars that arise in natural language processing, to O (N3|G|), which matches the runtime of CKY on a binarized version of the grammar G. Here N is the length of the sentence, |R| is the number of productions in G, and |G| is the total length of those productions. We also provide a version that achieves runtime of O (N3|M|) with |M| ≤ |G| when the grammar is represented compactly as a single finite-state automaton M (this is partly novel). We carefully treat the generalization to semiring-weighted deduction, preprocessing the grammar like Stolcke (1995) to eliminate deduction cycles, and further generalize Stolcke's method to compute the weights of sentence prefixes. We also provide implementation details for efficient execution, ensuring that on a preprocessed grammar, the semiring-weighted versions of our methods have the same asymptotic runtime and space requirements as the unweighted methods, including sub-cubic runtime on some grammars.