用自动机预计算距离，让大模型生成代码时语法必对。
Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance
- 基于下推自动机构建带距离估计的语法约束解码框架
- 在JSON/SQL/LTL任务中100%语法正确且生成质量更高
- 适合需要严格语法输出的编程、数据库等场景
语法约束解码能帮助大语言模型生成语法正确的结构化输出，如代码、JSON和SQL。针对上下文无关文法，现有方法通常采用局部前缀可行性：每个词元必须保证当前前缀可扩展为有效完成。然而，在分词器与文法不匹配及有限词元预算下，可行前缀仍可能无法达到接受状态。本文提出一种基于下推自动机的前瞻引导解码框架，离线计算带有可达性标签和到达接受状态的上界距离的有界下推摘要。在线推理时，利用这些估计进行视野感知剪枝和束搜索。所提解码器在语法上是严谨的：所有输出均被目标文法接受。在JSON、SQL和线性时序逻辑（LTL）上的实验表明，该方法不仅保持一致的语法正确性，还优于现有基线的完成质量。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。