用确定性下推自动机加速大模型结构化生成，提速超40%
Pre$^3$: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation
- 预计算前缀条件边，实现提前分析与并行转移
- 将LR(1)转换为确定性自动机，减少运行时路径搜索开销
- 可无缝接入主流推理框架，适合需要格式化输出的场景
大量大模型应用需要高效生成结构化输出，特别是针对LR(1)文法以生成指定格式（如JSON）的内容。现有方法通常将LR(1)文法解析为下推自动机（PDA），导致上下文相关词元处理存在运行时开销，尤其在大规模推理批次下效率低下。为此，我们提出Pre$^3$，利用确定性下推自动机（DPDA）优化约束型大模型解码效率。首先，在预处理阶段预先计算前缀条件边，实现提前分析，支持并行转移处理。其次，基于前缀条件边，提出新方法将LR(1)转移图转化为DPDA，消除运行时路径探索需求，实现极低开销的边转移。Pre$^3$可无缝集成至标准大模型推理框架，在实验中使每输出词元耗时（TPOT）降低最高达40%，吞吐量提升最高达36%。代码已开源：https://github.com/ModelTC/lightllm。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。