# Earley-Driven Dynamic Pruning for Efficient Structured Decoding

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 35 references that are in the map.
- First posted on arXiv 1 Jun 2025.

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [CodeT5: Identifier-aware Unified Pre-trained Encoder-Decoder Models for Code Understanding and Generation](https://mlsanity.com/paper/2109.00859/) (2021)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [Neural Machine Translation with Byte-Level Subwords](https://mlsanity.com/paper/1909.03341/) (2019)
- [Prompting Is Programming: A Query Language for Large Language Models](https://mlsanity.com/paper/2212.06094/) (2022)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [Validating Large Language Models with ReLM](https://mlsanity.com/paper/2211.15458/) (2022)
- [BenchCLAMP: A Benchmark for Evaluating Language Models on Syntactic and Semantic Parsing](https://mlsanity.com/paper/2206.10668/) (2022)
- [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)
- [Efficient Semiring-Weighted Earley Parsing](https://mlsanity.com/paper/2307.02982/) (2023)
- [Sketch: A Toolkit for Streamlining LLM Operations](https://mlsanity.com/paper/2409.03346/) (2024)

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

- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)
- [When Correct Isn't Usable: Improving Structured Output Reliability in Small Language Models](https://mlsanity.com/paper/2605.02363/) (2026)
- [Semantic Prefix Oracles for LLM Decoding: Contracts and Differential Validation](https://mlsanity.com/paper/2609.35425/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have shown remarkable capabilities, yet ensuring their outputs conform to strict structural or grammatical constraints remains challenging, which is critical in function calls and domain-specific language (DSL) generation. Constrained decoding with context-free grammar is a flexible approach to guarantee LLMs' adherence to a specific format by dynamically building a token logits mask. However, creating this mask requires checking the validity of all tokens in the LLM vocabulary at every decoding step, which often incurs significant overheads in existing constrained decoding engines. To address this challenge, we propose ZapFormat, a novel dynamic pruning strategy based on the Earley algorithm that identifies and eliminates invalid or redundant Earley states in real-time, significantly reducing memory occupation of the Earley algorithm's states. This further enables us to use a state cache to speed up structured generations on a large number of queries. We implemented ZapFormat in a new constrained decoding engine called Formatron which also incorporates existing optimizations. Through comprehensive experiments on structured generation tasks, including JSON generation, JSON Schema validation, and semantic parsing, we demonstrate that Formatron not only consistently maintains high-precision compliant outputs but also achieves significant improvements in inference speed up to 2x compared to state-of-the-art implementations. More importantly, Formatron is generally applicable across various LLM architectures. We release Formatron as open source at https://github.com/Dan-wanna-M/formatron.