保持在边界内：基于距离引导解码的保证上下文无关文法合规性
文章背景与核心概要
大语言模型在生成代码、JSON 和 SQL 等语法有效的结构化输出时常常面临挑战。尽管语法约束解码方法通过强制执行局部前缀可行性提供了一定帮助，但在面对分词器与文法不匹配以及有限的 Token 预算时，它们仍然可能失效。本文介绍了一种基于下推自动机（Pushdown Automata）的前瞻引导解码框架（lookahead-guided decoding framework），专门用于处理上下文无关文法（CFG）。
通过离线计算带有可达性标签和上限距离的有界下推摘要，该方法能够在在线解码过程中引导具有视界感知（horizon-aware）的剪枝和束搜索（beam search）。该方法保证了 100% 的语法有效性，并在 JSON、SQL 和线性时序逻辑（LTL）任务中显著提升了补全质量。
摘要 (Abstract)
大型语言模型在生成代码、JSON 和 SQL 等语法有效的结构化输出时，语法约束解码能够提供很大帮助。对于上下文无关文法，许多实际的解码器会强制执行局部前缀可行性：每个 Token 都必须使当前前缀能够扩展为某个有效的完整输出。然而，在分词器与文法不匹配以及 Token 预算有限的情况下，可执行的前缀仍然可能无法到达接受状态。我们提出了一种针对上下文无关文法的、基于下推自动机的ieht瞻引导解码框架。在离线阶段，我们计算带有可达性标签和到达接受状态的上界距离的有界下推摘要。在在线阶段，这些估计值指导视界感知的剪枝与束搜索。由此产生的解码器在语法上是健全的：每个输出都被目标文法所接受。在 JSON、SQL 和线性时序逻辑（LTL）上的实验表明，与现有基线相比，该方法不仅具有持续的语法有效性，还提高了补全质量。
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.