研究语法约束解码的结构等价性，揭示不同语法对推理效率的影响。
Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding
- 通过可达性预言机分析语法约束下的生成路径，发现等价语法产生相同可选词元集
- 提出结构歧义成本（SAC）度量，证明右递归语法每步开销为常数，连接语法为二次增长
- 证明任何高效解码引擎在特定语法下每步至少需二次时间，为算法设计提供理论边界
我们研究语法约束解码（GCD），将其视为自回归下一个词分布与由上下文无关文法（CFG）编译的下推系统可达性预言机之间的耦合。证明了预言机不变定理：语言等价的语法对每个前缀产生相同的可接受词元集合和日志掩码，但可能导致不同的编译状态空间和在线歧义成本。针对冗余非终结符委派下的经典 $a^n b^n$ 语言，给出精确的状态空间爆炸计数，并引入从左到右的结构歧义成本（SAC），衡量每令牌增量的打包解析森林增长。对于所有有限字符串等价的两种语法，右递归下 SAC 为每令牌 $O(1)$，而连接语法下为每令牌 $Θ(t^2)$ 且累计 $Θ(n^3)$。建立引擎无关的下界：任何满足声音性、检索效率和解析保持性的在线掩码引擎，在特定常数大小的 CFG 家族上必须每令牌承受 $Ω(t^2)$ 的工作量。定义语法的解码成本等价类，并证明在有界重写家族中存在最小 SAC 代表。最后，通过 Doob $h$-变换刻画真实条件采样器，推导硬掩码解码的一步 KL 和总变差偏差的紧界，基于可接受词元的存活概率分布。将这些结果与 Transformer 及混合专家架构结合，以词汇量、活跃状态集和束宽表示延迟上限，并将 SAC 与基于仪器的预测性能模型及自动语法优化相连接。
原文摘要 · Abstract (English)
We study grammar-constrained decoding (GCD) as a coupling between an autoregressive next-token distribution and a reachability oracle over a pushdown system compiled from a context-free grammar (CFG). We prove an oracle invariance theorem: language-equivalent grammars induce identical admissible next-token sets for every prefix, hence identical logit masks, yet can yield provably different compiled state spaces and online ambiguity costs. We give exact control-state blowup counts for the canonical $a^n b^n$ language under redundant nonterminal delegation, and introduce a left-to-right structural ambiguity cost (SAC) measuring incremental packed-parse-forest growth per token. For two equivalent grammars over all finite strings, SAC is $O(1)$ per token under right-recursion but $Θ(t^2)$ per token and $Θ(n^3)$ cumulatively under concatenation. We establish engine-independent lower bounds: any sound, retrieval-efficient, parse-preserving online masking engine must incur $Ω(t^2)$ work per token on a specific constant-size CFG family, unconditionally within this model. We define decoding-cost equivalence classes of grammars and prove existence of minimal-SAC representatives within bounded rewrite families. Finally, we characterize the true conditional sampler via a Doob $h$-transform and derive sharp one-step KL and total-variation distortion bounds for hard-masked decoding in terms of survival-probability spread among admissible next tokens. We integrate these results with Transformer and Mixture-of-Experts architectures, derive latency envelopes in terms of vocabulary size, active state sets, and beam width, and connect SAC to instrumentation-based predictive performance models and automated grammar optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。