@inproceedings{chen-etal-2025-pre3,
    title = "Pre$^3$: Enabling Deterministic Pushdown Automata for Faster Structured {LLM} Generation",
    author = "Chen, Junyi  and
      Bai, Shihao  and
      Wang, Zaijun  and
      Wu, Siyu  and
      Du, Chuheng  and
      Yang, Hailong  and
      Gong, Ruihao  and
      Liu, Shengzhong  and
      Wu, Fan  and
      Chen, Guihai",
    editor = "Che, Wanxiang  and
      Nabende, Joyce  and
      Shutova, Ekaterina  and
      Pilehvar, Mohammad Taher",
    booktitle = "Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)",
    month = jul,
    year = "2025",
    address = "Vienna, Austria",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingestion-acl-25/2025.acl-long.551/",
    pages = "11253--11267",
    ISBN = "979-8-89176-251-0",
    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 $\text{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, $\text{Pre}^3$ enables ahead-of-time edge analysis and thus makes parallel transition processing possible.Futher, leveraging the prefix-conditioned edges, $\text{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.$\text{Pre}^3$ can be seamlessly integrated into standard LLM inference frameworks, improving time per output token (TPOT) by up to 40{\%} and throughput by up to 36{\%} in our experiments. Our code is available at https://github.com/ModelTC/lightllm."
}