arXiv:2504.05410v1 交叉公告类型 摘要：在生成具有某些约束限制的语言时占主导地位的方法是局部约束解码（LCD），在每个时间步骤中逐步采样标记，以确保约束不会被违反。通常，这是通过标记掩码实现的：遍历词汇表并将不符合约束的标记排除在外。这一方法存在两个重要问题。（i）对每个标记评估约束可能是极其昂贵的——语言模型的词汇表通常超过100,000个标记。（ii）LCD可能会扭曲字符串的全局分布，基于仅局部信息采样标记，即使这些标记会导致死胡同路径。本工作引入了一种新的算法，解决了这两个问题。首先，为了避免在生成的每一步评估词汇表的完整约束，我们提出了一种自适应拒绝采样算法，通常只需要对约束进行数量级更少的评估。其次，我们展示了如何以非常小的附加成本扩展该算法以生成低方差、无偏的重要权重估计——这些估计可以在先前提出的序列蒙特卡洛算法内安全使用，以修正局部约束执行的短视行为。通过在文本到SQL、分子合成、目标推理、模式匹配和JSON领域进行广泛的经验评估，我们展示了我们方法优于最先进的基线方法，支持更广泛类型的约束，并提高了运行时间和性能。另外的理论和经验分析表明，我们方法的运行时效率是由其动态使用计算所驱动的，与未约束的和受限的语言模型之间的差异成比例，因此，对于模型越好，运行时改进越显著。