# Pre3: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 4 Jun 2025.

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [RT-2: Vision-Language-Action Models Transfer Web Knowledge to Robotic Control](https://mlsanity.com/paper/2307.15818/) (2023)
- [DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model](https://mlsanity.com/paper/2405.04434/) (2024)
- [BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions](https://mlsanity.com/paper/2406.15877/) (2024)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Large Language Models as Tool Makers](https://mlsanity.com/paper/2305.17126/) (2023)
- [A Survey of Embodied AI: From Simulators to Research Tasks](https://mlsanity.com/paper/2103.04918/) (2021)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Embodied Multi-Modal Agent trained by an LLM from a Parallel TextWorld](https://mlsanity.com/paper/2311.16714/) (2023)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [Formal-LLM: Integrating Formal Language and Natural Language for Controllable LLM-based Agents](https://mlsanity.com/paper/2402.00798/) (2024)
- [Large Language Models as Zero-shot Dialogue State Tracker through Function Calling](https://mlsanity.com/paper/2402.10466/) (2024)
- [Discrete Prompt Optimization via Constrained Generation for Zero-shot Re-ranker](https://mlsanity.com/paper/2305.13729/) (2023)
- [CodePAD: Sequence-based Code Generation with Pushdown Automaton](https://mlsanity.com/paper/2211.00818/) (2022)

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

- [SlimInfer: Accelerating Long-Context LLM Inference via Dynamic Token Pruning](https://mlsanity.com/paper/2508.06447/) (2025)
- [TokenFlow: Responsive LLM Text Streaming Serving under Request Burst via Preemptive Scheduling](https://mlsanity.com/paper/2510.02758/) (2025)
- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)
- [NovBench: Evaluating Large Language Models on Academic Paper Novelty Assessment](https://mlsanity.com/paper/2604.11543/) (2026)
- [SmartThinker: Progressive Chain-of-Thought Length Calibration for Efficient Large Language Model Reasoning](https://mlsanity.com/paper/2603.08000/) (2026)
- [C2KV: Compressed and Composable KV Cache Reuse for Efficient LLM Inference](https://mlsanity.com/paper/2607.17715/) (2026)
- [BubbleSpec: Turning Long-Tail Bubbles into Speculative Rollout Drafts for Synchronous Reinforcement Learning](https://mlsanity.com/paper/2605.08862/) (2026)
- [ExFold: Unified Expert Folding for Training-Free MoE Prefill-Decode Acceleration](https://mlsanity.com/paper/2608.24938/) (2026)
- [PerCache: Predictive Hierarchical Cache for RAG Applications on Mobile Devices](https://mlsanity.com/paper/2601.11553/) (2025)
- [Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding](https://mlsanity.com/paper/2603.05540/) (2026)
- [Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance](https://mlsanity.com/paper/2608.28229/) (2026)

## Abstract (arXiv)

Extensive LLM applications demand efficient structured generations, particularly for LR(1) grammars, to produce outputs in specified formats (e.g., JSON). Existing methods primarily parse LR(1) grammars into a pushdown automaton (PDA), leading to runtime execution overhead for context-dependent token processing, especially inefficient under large inference batches. To address these issues, we propose Pre3 that exploits deterministic pushdown automata (DPDA) to optimize the constrained LLM decoding efficiency. First, by precomputing prefix-conditioned edges during the preprocessing, Pre3 enables ahead-of-time edge analysis and thus makes parallel transition processing possible. Second, by leveraging the prefix-conditioned edges, Pre3 introduces a novel approach that transforms LR(1) transition graphs into DPDA, eliminating the need for runtime path exploration and achieving edge transitions with minimal overhead. Pre3 can be seamlessly integrated into standard LLM inference frameworks, reducing time per output token (TPOT) by up to 40% and increasing throughput by up to 36% in our experiments. Our code is available at https://github.com/ModelTC/lightllm.