Pre$^3$: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation
Pre³ transforms LR(1) grammar into DPDA, reducing decoding time by 40% and increasing throughput by 36%.
Key Findings
Methodology
This paper introduces an algorithm to convert LR(1) state transition graphs into deterministic pushdown automata (DPDA). By leveraging precomputed prefix-conditioned edges, the approach enables parallel transition processing and eliminates runtime path exploration. The core mechanism involves augmenting edges with stack-matching conditions to ensure determinism, handling cycles via cycle detection and back-edge modifications, and applying edge merging and aggregation for optimization. The resulting DPDA is integrated into standard LLM inference frameworks, significantly reducing decoding latency and increasing throughput. The method's effectiveness is validated through experiments on Meta-Llama models, demonstrating up to 40% reduction in time per token and 36% throughput increase.
Key Results
- In Meta-Llama-3-8B, TPOT decreased from 11.38ms to 6.84ms (~40%), with a 37.5% latency reduction at batch size 512. Meta-Llama-2-70B showed a 36% improvement. Compared to XGrammar and Outlines, Pre³ consistently outperformed in large-batch scenarios, with notable reductions in decoding overhead.
- Precomputed edges support complex grammars like JSON and chain-of-thought, with ablation studies confirming the contributions of edge merging and cycle handling. The automaton's structure was optimized, reducing states by 20-30%, leading to faster decoding.
- In large-scale inference, Pre³ maintained high scalability, delivering significant latency reductions and throughput gains, making it suitable for industrial deployment where large batch processing is common.
Significance
This work addresses the longstanding bottleneck of non-deterministic path exploration in constrained decoding for large models. By transforming LR(1) grammars into DPDA, it provides a scalable, efficient solution that maintains grammatical correctness. The approach bridges formal language theory and practical inference, enabling real-world applications like code generation, data formatting, and structured AI outputs. It paves the way for deploying structured generation at industrial scales, reducing computational costs and latency, and expanding the usability of constrained decoding in diverse domains.
Technical Contribution
The main technical innovation is the direct conversion of LR(1) automata into DPDA using prefix-conditioned edges, which guarantees determinism and supports parallel transition processing. The method introduces cycle detection and resolution techniques to handle recursive structures efficiently. Additionally, the automatic merging and aggregation of edges optimize the automaton size and speed. These contributions enable seamless integration into existing inference pipelines, significantly improving efficiency and scalability over prior non-deterministic approaches.
Novelty
This is the first work to systematically convert LR(1) state graphs into DPDA with precomputed prefix-conditioned edges, ensuring determinism and enabling parallel transition processing. Unlike previous methods relying on non-deterministic PDA and runtime path exploration, Pre³ precomputes all transitions, drastically reducing runtime overhead. Its cycle handling and edge merging strategies further distinguish it from existing solutions, marking a significant advancement in grammar-constrained decoding.
Limitations
- The approach may face scalability issues with extremely complex or highly recursive grammars, where automaton size could grow exponentially. Handling such cases requires further optimization.
- Currently optimized for LR(1) grammars; extending to higher-order or non-LR(1) grammars remains an open challenge.
- Large batch inference still depends on hardware resources; further hardware-aware optimization is needed for deployment in resource-constrained environments.
Future Work
Future directions include extending the method to broader classes of grammars beyond LR(1), integrating hardware acceleration (GPU/FPGA) for faster automaton construction, and developing adaptive automaton optimization strategies for dynamic grammar updates. Additionally, exploring automatic grammar extraction and automaton learning from data could broaden applicability to more complex, real-world languages and multimodal tasks.
AI Executive Summary
The rapid development of large language models (LLMs) has revolutionized natural language processing, enabling applications from chatbots to code synthesis. However, ensuring that generated outputs adhere to strict structural constraints, such as JSON schemas or programming language syntax, remains computationally challenging. Traditional constrained decoding methods like XGrammar rely on parsing LR(1) grammars into pushdown automata (PDA), but their non-deterministic nature leads to significant runtime overhead, especially under large batch inference scenarios. This bottleneck limits the scalability and practical deployment of structured generation in real-world systems.
To address this, the authors propose Pre³, a novel approach that transforms LR(1) automata into deterministic pushdown automata (DPDA). By precomputing prefix-conditioned edges, Pre³ enables parallel transition processing, eliminating the need for runtime path exploration. The core innovation lies in augmenting edges with stack-matching conditions, ensuring deterministic transitions even in the presence of cycles and recursive structures. The algorithm handles cycles by detecting complete traversal paths and modifying back-edges, preventing infinite loops and ensuring automaton stability.
Experimental results demonstrate that integrating Pre³ into existing inference frameworks reduces per-token decoding time by up to 40% and increases throughput by 36%. These improvements are consistent across different models and complex grammars, including JSON and chain-of-thought. The method's scalability makes it suitable for industrial applications requiring large batch processing, such as automated code generation and structured data synthesis.
Despite its advantages, the approach faces challenges with extremely complex or highly recursive grammars, where automaton size may grow substantially. Extending the framework to broader grammar classes and optimizing for resource-constrained environments are promising directions for future research. Overall, Pre³ provides a significant step forward in efficient, scalable, and reliable structured decoding for large language models, bridging formal language theory and practical AI deployment.
Deep Analysis
Background
近年来，随着GPT、LLaMA等大规模语言模型的崛起，结构化输出成为研究热点。早期方法多依赖规则匹配或正则表达式，但难以应对复杂语法。LR(1)语法的引入极大丰富了表达能力，代表工作包括XGrammar、Outlines等，能保证语法正确性。然而，模型规模扩大带来解码瓶颈，路径探索和状态管理的复杂性导致效率下降。非确定性PDA在处理复杂语法时存在路径回溯和状态爆炸问题，限制了工业应用。本文试图通过自动机转换技术，突破这一瓶颈，提升结构化生成的效率和扩展性。
Core Problem
现有约束解码技术在大规模批处理时效率低下，主要因非确定性PDA路径探索和状态管理复杂。复杂语法（如JSON）导致路径回溯频繁，延迟高、资源消耗大。传统方法难以在保证语法正确的同时实现快速、可扩展的解码，严重制约LLM在自动化数据格式、代码理解等场景的应用。如何在保证语法约束的基础上，减少运行时路径探索，成为核心难题。
Innovation
本文提出Pre³，核心创新包括：1）设计LR(1)状态转移图到DPDA的转换算法，避免路径探索；2）引入前缀条件边，实现边的预计算和平行处理；3）采用边合并和聚合技术，优化自动机结构，减少状态数；4）处理循环结构，避免无限路径爆炸。这些创新确保自动机的确定性和高效性，为大规模结构化解码提供新思路。
Methodology
- �� 构建LR(1)状态转移图，识别状态和转移边。• 利用前缀条件边，将每个转移边增强为包含堆栈匹配条件的边，确保唯一性。• 设计自动机转换算法，处理循环和递归结构，避免无限路径。• 预计算所有边，支持边的平行处理和合并，优化自动机。• 结合边聚合技术，将相似边合并，减少状态数。• 处理循环中的回边，通过检测完整循环路径，避免无限路径爆炸。• 最后，将自动机集成到LLM推理框架中，实现高效约束解码。
Experiments
采用Meta-Llama-3-8B和Meta-Llama-2-70B模型，测试JSON和链式思维语法。基准包括XGrammar、Outlines和Llama.cpp。指标主要为每标记时间（TPOT）和吞吐量。实验在多GPU环境下进行，验证不同批次规模（16-512）下的性能提升。通过消融实验，分析边预计算、边合并和循环处理的贡献，确保方法的鲁棒性和可扩展性。
Results
Pre³在Meta-Llama-3-8B模型上，将TPOT从11.38ms降低至6.84ms（提升约40%），在批次512时延迟降低37.5%；在Meta-Llama-2-70B模型中，TPOT提升36%。与XGrammar和Outlines相比，Pre³在大批次场景中表现优越，显著减少路径探索开销。自动机结构优化后，边数减少20-30%，解码速度显著提升。实验还验证了循环处理机制，有效避免无限路径爆炸，确保自动机的确定性。
Applications
该技术适用于需要严格语法约束的LLM应用，如自动代码生成、结构化数据填充、智能问答系统。通过自动机预处理，减少推理时的计算负担，适合大规模批量处理场景，提升工业部署效率。未来可结合硬件加速，支持更复杂的语法和多模态输入，推动LLM在自动化、工业智能等领域的广泛应用。
Limitations & Outlook
尽管Pre³在多场景表现优异，但在极复杂或含大量循环的语法中，自动机规模可能膨胀，影响构建速度和存储成本。算法目前主要针对LR(1)语法；扩展到更高阶或非LR(1)语法仍需深入研究。大规模批次下，硬件资源成为瓶颈，未来需结合硬件加速方案优化性能。此外，自动机的自动化构建流程仍有优化空间，以适应更复杂的语法和应用需求。
Plain Language Accessible to non-experts
想象你在一家工厂，工厂的任务是把各种原料变成成品。每个工序都必须按照规则操作，比如先分类，再组装，最后包装。传统方法就像工人每次都要反复检查每一步是否正确，效率很低。现在，工厂引入了一个智能机器人，它提前学会所有的规则，知道每个步骤该怎么走，遇到复杂情况也能快速处理。这个机器人用的就是一种叫“自动机”的智能系统，确保每个步骤都按规则进行，不出错，也不用反复检查。这样，工厂的生产速度大大提高，能同时处理更多订单。Pre³就是用这种智能机器人，让模型在生成内容时提前准备好所有规则，从而大幅提升效率。
ELI14 Explained like you're 14
想象你在学校的食堂点餐，菜单上写着各种菜肴，但你只想点健康又快的饭。以前，厨师每次都要确认你点的菜是否符合规则，比如不能点太油炸的，或者要搭配蔬菜。这样就很慢，因为每次都要检查很多规则。现在，食堂设计了一个智能点餐系统，提前把所有的规则都存起来，点餐时只要输入你的选择，它就能马上告诉你是否符合规则，还能帮你安排好菜的顺序。这个系统就像一个聪明的机器人，知道每个菜的规则，能快速帮你点菜，不用每次都重新检查。这样一来，你的点餐速度变快了，吃饭也更顺利。这就像Pre³用自动机提前整理好语法规则，让模型在生成内容时不用每次都重新验证，大大提高了效率。
Abstract
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 Pre$^3$ that exploits deterministic pushdown automata (DPDA) to optimize the constrained LLM decoding efficiency. First, by precomputing prefix-conditioned edges during the preprocessing, Pre$^3$ enables ahead-of-time edge analysis and thus makes parallel transition processing possible. Second, by leveraging the prefix-conditioned edges, Pre$^3$ 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. Pre$^3$ 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.