Guardado en:
| Autores principales: | , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2506.03887 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915531463852032 |
|---|---|
| author | Chen, Junyi Bai, Shihao Wang, Zaijun Wu, Siyu Du, Chuheng Yang, Hailong Gong, Ruihao Liu, Shengzhong Wu, Fan Chen, Guihai |
| author_facet | Chen, Junyi Bai, Shihao Wang, Zaijun Wu, Siyu Du, Chuheng Yang, Hailong Gong, Ruihao Liu, Shengzhong Wu, Fan Chen, Guihai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03887 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pre$^3$: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation Chen, Junyi Bai, Shihao Wang, Zaijun Wu, Siyu Du, Chuheng Yang, Hailong Gong, Ruihao Liu, Shengzhong Wu, Fan Chen, Guihai Computation and Language 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. |
| title | Pre$^3$: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation |
| topic | Computation and Language |
| url | https://arxiv.org/abs/2506.03887 |