Pre 3 : Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation
Junyi Chen, Shihao Bai, Zaijun Wang, Siyu Wu, Chuheng Du, Hailong Yang, Ruihao Gong, Shengzhong Liu, Fan Wu, Guihai Chen · 2025
Read Pre 3 : Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation by Junyi Chen, Shihao Bai, Zaijun Wang, Siyu Wu, Chuheng Du, Hailong Yang, Ruihao Gong, Shengzhong Liu, Fan Wu, Guihai Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-03887.txt.
Introduction
Junyi Chen and co-authors speed up format-bound text generation from language models in this 2025 paper. Many programs need model output in strict shapes, such as JSON, governed by grammars that a pushdown automaton can check. Checking token by token at run time gets costly, above all when many requests run at once.
Their system, Pre3, swaps the checker for a deterministic version built ahead of time. By precomputing edges tied to each prefix, it can judge many transitions in parallel and skip run-time path hunting. The design plugs into standard serving frameworks without fuss. In tests it cut the time per output token by up to forty percent and raised throughput by up to thirty-six percent. The code is public for others to use.
Catalog record
| CREATOR | Junyi Chen, Shihao Bai, Zaijun Wang, Siyu Wu, Chuheng Du, Hailong Yang, Ruihao Gong, Shengzhong Liu, Fan Wu, Guihai Chen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-03887
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pre 3 : Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation Junyi Chen, Shihao Bai, Zaijun Wang, Siyu Wu, Chuheng Du, Hailong Yang, Ruihao Gong, Shengzhong Liu, Fan Wu, Guihai Chen 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 pre computing pre fix-conditioned edges during the pre processing, 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 . 1 Introduction The recent remarkable development of Large Language Models (LLM) has ushered in new opportunities for a wide array of intelligent applications such as automated external tool invocations through function calls Cai et al. 2023 ; Li et al. 2024a ; Zhuo et al. 2024 , chain of thoughts Wei et al. 2022 ; Wang et al. 2022 ; OpenAI 2024 ; Guo et al. 2025 , embodied AI Duan et al. 2022 ; Brohan et al. 2023 ; Yang et al. 2024b et al. These applications created substantial demand for LLM systems to perform structured generation and produce outputs adhering to specific formats, such as JSON or other structures. Notably, major LLM API providers such as OpenAI and Alibaba Cloud now support JSON mode output to ensure deterministic schema compliance. Downstream applications can accordingly utilize these structured outputs to engage in downstream system interactions Cho et al. 2023 . Constrained decoding Hu et al. 2019 ; Scholak et al. 2021 is a widely used method in structured generation tasks Willard and Louf 2023b ; Dong et al. 2023 ; Rückstieß et al. 2024 that excludes invalid tokens at each step by applying a probability mask to zero out their sample possibility. Flexible mechanisms like LR(1) grammars Francis 1961 ; Knuth 1965a are often employed to handle diverse and complex structural constraints, as they allow recursive rule definitions that surpass the limitations of regular expressions. However, this flexibility comes at the cost of degraded efficiency: Each decoding step requires parsing the grammar for all candidate tokens in a potentially large vocabulary. Additionally, tokens generated by LLM may consist of multiple characters that span across grammar rule boundaries, further complicating the generation process and demanding dedicated execution stack management. Both of them lead to significant computational overhead. These challenges raise the need to optimize constrained decoding efficiency without affecting LLM generation fidelity, making it more applicable in real-world applications. Current state-of-the-art (SOTA) methods for constrained decoding acceleration, such as XGrammar Dong et al. 2024 , primarily focus on parsing LR(1) grammars into a pushdown automaton (PDA) Nederhof and Satta 1996 . A PDA consists of multiple finite state automata (FSA), each representing a grammar rule, with the stack handling recursive rule expansions. These methods achieve substantial speedups by precomputing masks while managing transitions through pushdown automata. However, they overlook the inherent properties of LR(1) grammars, which can be equivalently transformed into a deterministic pushdown automaton (DPDA) Valiant 1973 ; Valiant 1975 . The primary issue with traditional PDA-based approaches Koo et al. 2024 ; Park et al. 2025a ; Dong et al. 2022 ; Willard and Louf 2023a ; Li et al. 2024b stems from the non-deterministic nature of the PDA’s edges. Although these methods precompute masks based on the PDA structure, this design introduces two critical limitations. First, the non-deterministic edges depend on runtime contextual information to resolve transitions, resulting in incomplete precomputed masks for context-dependent tokens . The computation of context-dependent tokens necessitates backtracking, speculative operations, and the maintenance of a persistent stack (merges all past stacks into a tree, with each stack as a root-to-node path) during runtime. As batch sizes increase, the overhead from these runtime computations grows significantly, severely degrading decoding efficiency. Second, previous methods cannot effectively optimize non-deterministic transitions during preprocessing because they will dynamically change during runtime. This limitation hinders their ability to fully exploit the potential of the parsing method, leading to suboptimal performance. To address these challenges, we propose Pre 3 , a constrained LLM decoding approach based on a deterministic pushdown automaton (DPDA). Unlike traditional methods, we design an algorithm to directly build a DPDA from the LR(1) grammar. Leveraging the deterministic nature of the DPDA’s edges, our approach resolves the aforementioned limitations. First, the determined transitions in the DPDA eliminate the context-dependent tokens, further entirely eliminating the need for backtracking, speculative exploration, and the maintenance of a persistent stack. This fundamentally reduces the runtime computational overhead associated with transitions. Second, since all transition edges in the DPDA are available during preprocessing, we can perform comprehensive optimizations on the automaton in advance. Additionally, for the stack-matched transition mechanism of the DPDA, we design a parallel verification method for transitions, which accelerates inference. Together, these innovations result in a more efficient and scalable constrained decoding framework. In summary, the paper’s main contributions are: • We first propose an algorithm to transform LR(1) state transition graphs into DPDA, eliminating runtime exploration and enabling edge transitions with minimal overhead. • We enable additional optimizations for edges and support parallel transition processing by precomputing prefix-conditioned edges. • We integrate Pre 3 into mainstream LLM inference systems and achieve up to 40% improvement in time per output token (TPOT) and increase throughput by up to 36% with high scalability into large batch sizes. 2 Preliminaries and Background 2.1 LLM Constrained Decoding Constrained decoding Hu et al. 2019 enforces strict grammatical adherence by dynamically pruning invalid tokens during generation. While effective for structural compliance, existing methods face two key challenges: (1) handling diverse grammars, large vocabularies, and complex token-to-text mappings, and (2) computational inefficiency at scale, especially under large batch processing where dynamic validation creates sequential bottlenecks. Our empirical analysis reveals this critical limitation. When evaluating XGrammar on Meta-Llama-3-8B (2×H800 GPUs), constrained decoding exhibits up to 37.5% higher latency (147.64 ms vs. 92.23 ms) at batch size 512 compared to unconstrained decoding (Table 1 ). The performance gap grows with batch size due to non-parallelizable validation steps, which is a fundamental constraint in current approaches. Table 1: Per token latency comparison (in milliseconds) across different batch sizes. Batch Size 16 32 64 128 256 512 Baseline 11.38 21.87 25.74 30.08 56.29 92.23 XGrammar 15.19 43.69 52.07 65.21 90.98 147.64 These findings motivate the need for a new constrained decoding approach that maintains grammatical correctness while achieving better computational efficiency at scale. 2.2 LR(1) Grammar and State Transition Graphs In constrained decoding scenarios, most grammars can be classified as LR(1) grammars, which are fundamental to bottom-up parsing and align naturally with