Pre³: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation¶

会议: ACL 2025
arXiv: 2506.03887
代码: https://github.com/ModelTC/lightllm
领域: 文本生成
关键词: 结构化生成, 约束解码, 确定性下推自动机, JSON生成, LLM推理优化

一句话总结¶

提出 Pre³，将 LR(1) 文法转化为确定性下推自动机（DPDA），通过预计算前缀条件边消除运行时非确定性探索，实现结构化 LLM 生成的显著加速——每 token 耗时降低最高 40%，吞吐提升最高 36%。

研究背景与动机¶

领域现状：结构化生成（如 JSON 输出）在 LLM 应用中需求巨大。约束解码通过在每步对无效 token 进行概率掩码来强制格式合规。现有方法（XGrammar、Outlines 等）将 LR(1) 文法解析为下推自动机（PDA）进行约束。
现有痛点：传统 PDA 的转移边是非确定性的——同一输入符号可能触发多个转移，需要运行时回溯、推测执行和维护持久化栈树结构。随着推理批次增大，这些开销显著增长（batch=512 时 XGrammar 比无约束解码慢 60%）。
核心矛盾：非确定性转移阻碍了预处理优化——因为边在运行时才能确定，无法在预处理阶段做完整分析和优化。
本文要解决什么？ 如何将约束解码的自动机从非确定性 PDA 转为确定性 PDA（DPDA），消除运行时探索开销。
切入角度：LR(1) 文法天然是确定性上下文无关语言（DCFL）的子集，理论上可以被 DPDA 识别。关键是设计从 LR(1) 状态转移图到 DPDA 的高效构造算法。
核心idea一句话：用前缀条件边为每条转移附加栈匹配条件，使所有转移在预处理时完全确定。

方法详解¶

整体框架¶

输入为 LR(1) 文法（如 JSON Schema），经过三阶段处理：(1) 构建 LR(1) 状态转移图；(2) 通过前缀条件边算法转化为 DPDA；(3) 对 DPDA 进行边聚合/合并优化。输出为优化后的 DPDA，可直接用于约束解码。

关键设计¶

前缀条件边（Prefix-conditioned Edge）:
做什么：为每条转移边附加栈匹配条件，消除非确定性
核心思路：每条边包含三个组件——接受符号（触发转移的输入）、栈匹配条件（转移生效所需的栈前缀）、栈操作（push/pop）。通过同时检查输入符号和栈状态，唯一确定目标状态
设计动机：LR(1) 的核心性质是"当前栈配置+一个前瞻符号就能唯一确定下一步动作"。前缀条件边将这一性质编码到边结构中
环感知 DPDA 构造算法:
做什么：从 LR(1) 状态转移图系统地构建 DPDA
核心思路：定义两种边——接受边（对应 shift 操作，直接从原图继承）和归约边（对应 reduce 操作，预计算嵌套归约路径为单步转移）。用递归算法处理循环结构，将多步归约压缩为直接跳转
设计动机：传统 LR(1) 解析需要多步归约（pop 栈 + 查 goto 表），DPDA 将这些步骤预编码为单边转移
边优化（Edge Optimization）:
做什么：在预处理阶段优化 DPDA 结构
核心思路：
- 边聚合: 将相同栈条件和操作但不同接受符号的边合并（如数字 0-9 合为一条边）
- 边合并: 将可连续执行的两条边直接连接，减少 DPDA 状态数
设计动机：这些优化只有在边完全确定性时才可行——非确定性 PDA 无法做此类预处理
并行栈匹配验证:
做什么：并行检查多条前缀条件边的栈匹配条件
核心思路：由于所有边的匹配条件在预处理时已知，可以批量并行验证
设计动机：大批次推理时并行验证显著减少延迟

损失函数 / 训练策略¶

无需训练——纯系统优化方法
预处理一次性成本：复杂 JSON 文法 3-5 秒，简单文法 <0.1 秒，结果可缓存复用
用 Python + C++ 实现，集成到 LightLLM 推理框架

实验关键数据¶

主实验（Llama-3-8B, 2×H800）¶

Batch Size	XGrammar (ms)	Pre³ (ms)	延迟降低
16	15.19	11.77	-22.5%
64	52.07	35.88	-30.1%
256	90.98	64.42	-29.2%
512	147.64	104.46	-29.2%
1024	272.77	201.16	-26.3%

消融实验¶

配置	效果	说明
DeepSeek-V2-Lite, batch=128	-40.78%	在 MoE 模型上改进最大
Qwen2-14B INT8, batch=1024	-18.65%	量化模型也有效
vs Outlines	数量级优势	Outlines 每步开销可达数秒
vs llama.cpp	显著优势	C++ 实现但 PDA 架构受限

关键发现¶

Pre³ 在所有测试的模型和批次大小上一致优于 XGrammar，平均延迟降低 25-30%
改进随批次大小增大而更加明显——大批次场景（生产环境常见）下优势最大
完全消除了持久化栈的维护开销——这是传统 PDA 方法在大批次下的主要瓶颈
不影响生成质量——输出与无约束解码在语义上完全一致
预处理成本极低（3-5秒），且可缓存复用

亮点与洞察¶

从 PDA 到 DPDA 的转换是正确的系统抽象层选择——LR(1) 文法天然支持确定性解析，此前的方法没有利用这一性质。这是一个"用正确的理论工具解决实际问题"的典范。
前缀条件边将运行时计算前移到预处理阶段——"一次编译，反复使用"的思想。
边优化展示了确定性的额外红利——不仅消除运行时开销，还打开了预处理优化的大门。
该方法可直接应用于所有需要结构化输出的 LLM 场景（如 function calling、代码生成、数据库查询）。

局限性 / 可改进方向¶

仅支持 LR(1) 文法（覆盖大部分场景但非全部上下文无关文法）
对于极复杂的嵌套文法，DPDA 的状态数可能爆炸
当前实现仅集成到 LightLLM，其他框架（如 vLLM、TensorRT-LLM）的集成未验证
未与 speculative decoding 等推理加速技术结合

评分¶

新颖性: ⭐⭐⭐⭐ PDA→DPDA 的系统级创新，前缀条件边设计巧妙
实验充分度: ⭐⭐⭐⭐ 多模型多批次多文法对比，延迟和吞吐都有测试
写作质量: ⭐⭐⭐⭐ 形式化定义严谨，算法描述清晰
价值: ⭐⭐⭐⭐⭐ 高实用价值，直接可用于生产环境的LLM结构化输出