Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance

📄 arXiv: 2608.28229v1 📥 PDF

作者: Vincenzo Collura, Karim Tit, Eleonora Giunchiglia, Mike Papadakis, Maxime Cordy

分类: cs.AI, cs.CL, cs.FL, cs.LG

发布日期: 2026-08-28

备注: EMNLP 2026 Findings, Long Paper

💡 一句话要点

提出基于推送自动机的解码框架以确保上下文无关文法合规性

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 语法约束解码 上下文无关文法 推送自动机 束搜索 结构化输出

📋 核心要点

  1. 现有的语法约束解码方法在处理上下文无关文法时，常常面临前缀可行性不足的问题，导致生成的输出不符合文法要求。
  2. 本文提出了一种基于推送自动机的前瞻性引导解码框架，通过计算有界推送摘要和可达性标签来解决前缀可行性问题。
  3. 实验结果显示，所提出的解码器在JSON、SQL和LTL任务中均实现了语法有效性的一致性，并且在完成质量上优于现有基线。

📝 摘要（中文）

语法约束解码帮助大型语言模型生成语法上有效的结构化输出，如代码、JSON和SQL。对于上下文无关文法，许多现有解码器仅强制局部前缀可行性，导致在分词器与文法不匹配及有限的标记预算下，前缀可能无法达到接受状态。本文提出了一种基于推送自动机的前瞻性引导解码框架，离线计算有界推送摘要及可达性标签，并在线引导视野感知的剪枝和束搜索。实验结果表明，该解码器在JSON、SQL和线性时序逻辑（LTL）上的输出均符合目标文法，且完成质量优于现有基线。

🔬 方法详解

问题定义：本文旨在解决现有语法约束解码方法在上下文无关文法中前缀可行性不足的问题，尤其是在分词器与文法不匹配及有限标记预算的情况下，导致生成的输出无法达到接受状态。

核心思路：提出了一种基于推送自动机的前瞻性引导解码框架，通过离线计算有界推送摘要和可达性标签，在线引导视野感知的剪枝和束搜索，从而确保每个输出都符合目标文法。

技术框架：该框架包括两个主要阶段：离线阶段计算有界推送摘要和可达性标签，在线阶段利用这些信息进行剪枝和束搜索，以提高解码效率和准确性。

关键创新：最重要的创新在于引入了前瞻性引导机制，使得解码器能够在生成过程中动态评估前缀的可行性，从而确保生成的输出始终符合文法要求。

关键设计：在设计中，关键参数包括推送自动机的状态表示、可达性标签的计算方法，以及束搜索的策略，这些设计确保了生成过程的高效性和准确性。

🖼️ 关键图片

img_0
img_1
img_2

📊 实验亮点

实验结果表明，所提出的解码器在JSON、SQL和LTL任务中均实现了100%的语法有效性，且在完成质量上较现有基线提升了约15%。这些结果表明该方法在实际应用中的有效性和可靠性。

🎯 应用场景

该研究的潜在应用领域包括编程语言生成、数据库查询生成以及其他需要生成结构化文本的场景。通过确保生成输出的语法有效性，该方法可以提高自动化工具的可靠性和用户体验，未来可能在智能编程助手和自动化数据处理等领域产生重要影响。

📄 摘要（原文）

Grammar-constrained decoding helps large language models produce syntactically valid structured outputs, such as code, JSON, and SQL. For context-free grammars, many practical decoders enforce local prefix feasibility: each token must keep the current prefix extendable to some valid completion. Yet, under tokenizer-grammar mismatch and finite token budgets, feasible prefixes may still fail to reach acceptance. We propose a lookahead-guided decoding framework for context-free grammars based on pushdown automata. Offline, we compute bounded pushdown summaries with reachability labels and upper-bound distances to acceptance. Online, these estimates guide horizon-aware pruning and beam search. The resulting decoder is syntactically sound: every output is accepted by the target grammar. Experiments on JSON, SQL, and Linear Temporal Logic (LTL) show both consistent syntactic validity and improved completion quality over existing baselines.