提出未来有效性函数,解决语法约束生成中的采样偏差问题。
Future Validity is the Missing Statistic: From Impossibility to $Φ$-Estimation for Grammar-Faithful Speculative Decoding
- 引入未来有效性函数Φ,修正局部掩码导致的分布偏移
- 在Dyck语法下误差降低至0.996,有限语言接近数值精度
- 适用于需要高语法正确性的生成场景,如代码或结构化数据
语法约束生成常结合局部词表掩码与推测解码,但其采样分布并非用户期望的语法条件分布。我们证明:任何具有局部掩码访问、莱维坦拒绝和回滚保真性的推测解码器均采样自局部投影分布μ^proj,而非语法条件分布μ⋆。这一结果扩展了GAD不可能性定理至推测解码场景;在使用Qwen3-8B模型的Dyck语法上,总变差距离可达0.996。我们识别出未来有效性函数Φ_t(y) = Pr_p[有效完成|y]为缺失的校正统计量。目标分布是基于基础模型的Doob变换,其中h=Φ,而局部掩码对应h=1。若使用精确Φ,我们的最优解码器FVO-Spec可精确采样于μ⋆;若使用近似Φ,可界定总变差误差。由于一般上下文无关语法下精确Φ难以计算,我们在可枚举的Dyck和有限JSON语言上评估了估计层级。OneStep使Dyck的总变差降低14%,吞吐量开销低于1%;精确动态规划降低97%;有限语言校正使JSON误差趋近数值精度。所有保真度声明均限于可枚举语法和词元尝试树。
原文摘要 · Abstract (English)
Grammar-constrained generation is often combined with local vocabulary masking and speculative decoding, but the resulting sampling law is not the grammar-conditional distribution users usually intend. We show that any speculative decoder with local mask access, Leviathan rejection, and rollback soundness samples from the locally projected distribution $μ^{\mathrm{proj}}$ rather than the grammar-conditional distribution $μ^\star$. This extends the GAD impossibility result to speculative decoding; on Dyck grammars with Qwen3-8B, the total-variation gap can reach 0.996. We identify the future-validity function $Φ_t(y)=\Pr_p[\mathrm{valid\ completion}\mid y]$ as the missing correction statistic. The target distribution is a Doob transform of the base model with $h=Φ$, while local masking corresponds to setting $h$ to one. With exact $Φ$, our oracle decoder FVO-Spec samples exactly from $μ^\star$; with approximate $Φ$, we bound the resulting total-variation error. Because exact future validity is hard for general context-free grammars, we evaluate estimator hierarchies on tractable Dyck and finite JSON languages. OneStep reduces Dyck TV by 14% with under 1% throughput overhead, exact dynamic programming reduces it by 97%, and finite-language correction closes JSON gaps to numerical precision. All fidelity claims are scoped to enumerable grammars and token tries.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。