提出新解码算法，让大模型生成更高效且无偏差。
Efficient and Asymptotically Unbiased Constrained Decoding for Large Language Models
- 用动态重要性采样替代传统前缀树，提升解码效率。
- 在多个数据集上生成速度更快，且输出分布更公平。
- 适合需要严格合规或格式控制的生成场景。
在大语言模型的实际应用中，输出常需受限：从预定义的产品或文档集合中选择条目、生成符合安全标准的短语，或遵循特定格式。为控制生成内容，约束解码被广泛采用。然而，现有基于前缀树的约束解码在基于GPU的推理范式下效率低下，并引入了非预期的偏差。本文提出动态重要性采样约束解码（DISC）与基于GPU的并行前缀验证（PPV），利用动态重要性采样实现理论保证的渐近无偏性，克服前缀树效率瓶颈。大量实验表明，该方法在效率与输出质量上均优于现有方法。结果表明，该方法在需要严格遵守特定约束的应用中具有显著潜力。
原文摘要 · Abstract (English)
In real-world applications of large language models, outputs are often required to be confined: selecting items from predefined product or document sets, generating phrases that comply with safety standards, or conforming to specialized formatting styles. To control the generation, constrained decoding has been widely adopted. However, existing prefix-tree-based constrained decoding is inefficient under GPU-based model inference paradigms, and it introduces unintended biases into the output distribution. This paper introduces Dynamic Importance Sampling for Constrained Decoding (DISC) with GPU-based Parallel Prefix-Verification (PPV), a novel algorithm that leverages dynamic importance sampling to achieve theoretically guaranteed asymptotic unbiasedness and overcomes the inefficiency of prefix-tree. Extensive experiments demonstrate the superiority of our method over existing methods in both efficiency and output quality. These results highlight the potential of our methods to improve constrained generation in applications where adherence to specific constraints is essential.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。