核心发现
方法论
本文提出一种将LR(1)状态转移图转换为确定性下推自动机(DPDA)的算法，利用预计算的前缀条件边实现边的平行处理，避免运行时路径探索。核心机制包括引入前缀条件边（Prefix-conditioned Edges）以确保转移唯一性，结合边聚合和合并技术优化自动机结构。通过处理循环和非确定性边，确保DPDA的确定性。实验中，将Pre³集成到标准LLM推理框架，显著降低每个输出标记的时间（TPOT）达40%，吞吐量提升36%。
关键结果
- 在Meta-Llama-3-8B模型上，使用JSON语法时，TPOT从11.38ms降低至6.84ms（提升约40%），在大批次（512）时延迟降低约37.5%。在Meta-Llama-2-70B模型中，TPOT提升36%。与XGrammar和Outlines相比，Pre³在大规模批处理下表现优越，显著减少了运行时路径探索的开销。
- 通过预计算边，支持多种复杂语法（如JSON、链式思维），在不同模型和语法下均实现了性能提升。实验还验证了边合并和循环处理的有效性，确保自动机的确定性与高效性。
- 在大批次推理场景中，Pre³展现出优异的扩展性，尤其在超大批量（如512）时，解码延迟和吞吐量改善明显，满足工业级应用需求。
研究意义
该方法突破了传统非确定性PDA在大规模结构化生成中的瓶颈，提供一种高效、可扩展的解码方案。解决了复杂语法约束下的计算瓶颈问题，推动LLM在自动化数据格式生成、代码解析等领域的应用落地。通过引入DPDA，极大简化了路径探索和状态管理，为未来大规模结构化任务提供理论基础和工程实践路径，具有重要的学术和工业价值。
技术贡献
核心贡献在于提出一种将LR(1)语法图转换为DPDA的算法，利用前缀条件边实现边的预计算和平行处理，避免运行时路径探索。引入边聚合与循环处理机制，确保自动机的确定性与高效性。将DPDA无缝集成到LLM推理框架中，显著提升结构化解码速度和吞吐量，为结构化生成提供新范式。
新颖性
首次提出将LR(1)状态转移图直接转换为DPDA的算法，利用前缀条件边实现边的预计算与平行处理，突破了传统非确定性PDA的限制。相较于现有的XGrammar等方法，Pre³在保证语法约束的同时，大幅提升解码效率，具有明显的创新优势。
局限性
- 算法在处理极复杂或含大量循环的语法时，仍可能面临边爆炸和自动机规模膨胀的问题，影响构建速度和存储成本。
- 当前主要针对LR(1)语法，扩展到更高阶或非LR(1)语法仍需进一步研究。
- 在极端大规模批次下，边预计算和自动机优化可能存在硬件资源瓶颈，需结合硬件加速方案。
未来方向
未来将探索自动机的动态适应能力，支持更复杂的语法和多模态输入。结合硬件加速（如GPU、FPGA）进一步提升构建和推理速度。同时，研究自动机的自适应优化策略，以应对多样化的应用场景和更大规模的模型需求。
AI 总览摘要
随着大规模语言模型（LLM）在自然语言处理中的广泛应用，结构化输出的需求不断增长。传统的约束解码方法如XGrammar虽然能保证语法正确，但在大批次推理中存在显著的效率瓶颈，主要源于路径探索和非确定性状态管理。本文提出Pre³，一种基于确定性下推自动机（DPDA）的结构化解码方案，创新性地将LR(1)语法转化为DPDA，利用预计算的前缀条件边实现边的平行处理，极大降低了运行时的路径探索开销。该方法通过引入边聚合和循环处理机制，有效应对复杂语法中的循环结构，确保自动机的确定性和高效性。实验结果显示，集成Pre³后，TPOT（每个输出标记的时间）在Meta-Llama-3-8B模型上降低40%，吞吐量提升36%，在大规模批次（如512）下表现尤为优越。这一突破不仅提升了结构化生成的实用性，也为未来大规模、多模态的语法约束解码提供了理论基础和工程方案。尽管如此，自动机规模和复杂度仍是未来研究的挑战，特别是在处理更复杂语法和极端大批量场景时。总体而言，Pre³为LLM的结构化生成开启了新的可能性，推动其在工业界的落地应用。
深度分析
研究背景
近年来，随着大规模语言模型（如GPT、LLaMA）的快速发展，结构化输出成为重要研究方向。早期方法多依赖规则或正则表达式，但难以处理复杂语法。近年来，基于LR(1)语法的约束解码技术逐渐成熟，代表工作包括XGrammar、Outlines等，它们通过预计算掩码实现高效约束。然而，随着模型规模扩大，解码速度成为瓶颈，尤其在大批次场景下，路径探索带来的计算开销严重制约了实用性。传统方法多依赖非确定性PDA，存在路径回溯和状态管理难题，难以满足工业需求。本文基于LR(1)语法的自动机转换技术，试图突破这一瓶颈，提升结构化生成的效率和规模适应性。
核心问题
当前结构化解码方法在大规模批处理时存在显著瓶颈，主要源于非确定性PDA的路径探索和状态管理复杂性。尤其在处理复杂语法（如JSON）时，路径回溯和边的多重可能性导致延迟和资源浪费。现有技术难以在保证语法正确的同时实现高效、可扩展的解码，限制了LLM在自动化数据格式生成、代码理解等应用中的表现。如何在保证语法约束的前提下，减少运行时路径探索，成为亟待解决的问题。
核心创新
本文提出Pre³，核心创新包括：1）设计一种将LR(1)状态转移图转换为DPDA的算法，避免路径探索；2）引入前缀条件边（Prefix-conditioned Edges），实现边的预计算和平行处理；3）采用边聚合和合并技术，优化自动机结构，减少状态数；4）专门处理循环结构，避免无限路径生成。这些创新使得自动机具有确定性，极大提升解码速度和扩展性，为大规模结构化生成提供了新思路。
方法详解
- �� 构建LR(1)状态转移图，识别状态和转移边。• 利用前缀条件边，将每个转移边增强为包含堆栈匹配条件的边，确保唯一性。• 设计算法将LR(1)图转换为DPDA，处理循环和递归结构，避免无限路径。• 通过预计算所有边，支持边的平行处理和边合并，优化自动机。• 结合边聚合技术，将相似边合并，减少状态数。• 处理循环中的回边，通过检测完整循环路径，避免无限路径爆炸。• 最后，将自动机集成到LLM推理框架中，实现高效约束解码。
实验设计
采用Meta-Llama-3-8B和Meta-Llama-2-70B模型，测试JSON和链式思维语法。基准包括XGrammar、Outlines和Llama.cpp。指标主要为每标记时间（TPOT）和吞吐量。实验在多GPU环境下进行，验证不同批次规模（16-512）下的性能提升。通过消融实验，分析边预计算、边合并和循环处理的贡献，确保方法的鲁棒性和可扩展性。
结果分析
Pre³在Meta-Llama-3-8B模型上，将TPOT从11.38ms降低至6.84ms（提升约40%），在批次512时延迟降低37.5%；在Meta-Llama-2-70B模型中，TPOT提升36%。与XGrammar和Outlines相比，Pre³在大批次场景中表现优越，显著减少路径探索开销。自动机结构优化后，边数减少20-30%，解码速度显著提升。实验还验证了循环处理机制，有效避免无限路径爆炸，确保自动机的确定性。
应用场景
该技术适用于需要严格语法约束的LLM应用，如自动代码生成、结构化数据填充、智能问答系统。通过自动机预处理，减少推理时的计算负担，适合大规模批量处理场景，提升工业部署效率。未来可结合硬件加速，支持更复杂的语法和多模态输入，推动LLM在自动化、工业智能等领域的广泛应用。
局限与展望
尽管Pre³在多场景表现优异，但在极复杂或含大量循环的语法中，自动机规模可能膨胀，影响构建速度和存储成本。算法目前主要针对LR(1)语法，扩展到更高阶或非LR(1)语法仍需深入研究。大规模批次下，硬件资源成为瓶颈，未来需结合硬件加速方案优化性能。此外，自动机的自动化构建流程仍有优化空间，以适应更复杂的语法和应用需求。
通俗解读 非专业人士也能看懂
想象你在一家工厂里，工厂的任务是把各种原料变成成品。每个工序都必须按照一定的规则进行，比如先把原料分类，再组装，最后包装。传统的方法就像工厂里每个工序都要反复检查，确认每一步是否正确，效率很低。现在，Pre³就像给工厂设计了一套智能机器人，它提前把所有的规则都整理好，知道每个步骤该怎么走，遇到复杂的情况也能快速处理。这样一来，工厂的生产速度大大提高，能同时处理更多订单。这个机器人用的就是一种叫“自动机”的智能系统，确保每个步骤都按规则走，不出错，也不用反复检查。它让工厂变得更快、更聪明，也更节省成本。
简单解释 像给14岁少年讲一样
想象你在学校的食堂点餐，菜单上写着各种菜肴，但你只想点健康又快的饭。以前，厨师每次都要确认你点的菜是否符合规则，比如不能点太多油炸的，或者要搭配蔬菜。这样就很慢，因为每次都要检查很多规则。现在，食堂设计了一个智能点餐系统，提前把所有的规则都存起来，点餐时只要输入你的选择，它就能马上告诉你是否符合规则，还能帮你安排好菜的顺序。这个系统就像一个聪明的机器人，知道每个菜的规则，能快速帮你点菜，不用每次都重新检查。这样一来，你的点餐速度变快了，吃饭也更顺利。这就像Pre³用自动机提前整理好语法规则，让模型在生成内容时不用每次都重新验证，大大提高了效率。
原文摘要
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.