Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

📄 arXiv: 2606.01926v1 📥 PDF

作者: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

分类: cs.CL

发布日期: 2026-06-01

备注: 13 pages, 5 figures

💡 一句话要点

提出基于可处理提案的全局约束解码以缓解偏差问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 局部约束解码 全局约束解码 序列蒙特卡洛 有限自动机 隐马尔可夫模型 自然语言生成 生成模型

📋 核心要点

  1. 现有的局部约束解码方法在执行约束时存在偏差，导致生成性能下降。
  2. 提出了一种基于张量化有限自动机的全局约束解码提案，利用序列蒙特卡洛方法进行采样。
  3. 实验表明，所提方法在函数调用、基于关键词的生成和SQL生成任务中表现优越，收敛速度更快。

📝 摘要（中文）

大型语言模型生成的内容常常无法满足特定约束，如JSON模式。现有的局部约束解码方法通过短视地屏蔽下一个token来强制执行约束，导致采样偏差和性能下降。本文提出了一种通用的方法，通过从$p_{ ext{lm}}( ext{constraint})$构建提案和潜在函数，以改进序列蒙特卡洛采样。我们展示了将有限自动机指定的约束进行张量化以便在GPU上高效执行，并利用这一点构建全局约束解码提案。实验结果表明，与局部约束解码提案相比，所提出的方法在相同的采样设置下，收敛速度更快且所需粒子数量显著减少。

🔬 方法详解

问题定义：本文旨在解决大型语言模型生成内容时无法满足特定约束的问题。现有的局部约束解码方法通过屏蔽下一个token来强制执行约束，导致偏差和性能下降。

核心思路：提出了一种通用的方法，通过构建有效的提案和潜在函数来改进序列蒙特卡洛采样，特别是利用张量化有限自动机来实现高效的全局约束解码。

技术框架：整体架构包括将约束表示为有限自动机并进行张量化，以便在GPU上高效执行。通过电路乘法将张量化的有限自动机与隐马尔可夫模型结合，形成概率全局约束解码提案。

关键创新：最重要的创新在于将有限自动机的张量化与隐马尔可夫模型的电路结构结合，形成新的概率全局约束解码提案，显著提高了采样效率。

关键设计：在设计中，采用了张量化的有限自动机以共享电路结构，并通过电路乘法实现逻辑和概率信息的编码，优化了采样过程中的提案分布。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，在相同的序列蒙特卡洛采样设置下，所提出的概率全局约束解码方法相比于局部约束解码方法，收敛速度更快，所需粒子数量显著减少，提升幅度达到了X%（具体数据需根据实验结果填充）。

🎯 应用场景

该研究的潜在应用领域包括自然语言处理中的约束生成任务，如代码生成、对话系统和信息检索等。通过提高生成内容的准确性和符合性，能够在实际应用中提升用户体验和系统性能，具有重要的实际价值和未来影响。

📄 摘要（原文）

Generations from large language models often fail to conform to desired constraints such as JSON schema. Existing locally constrained decoding (LCD) approaches enforce constraints by myopically masking out next tokens, resulting in biased sampling and degradation in performance. Recent work uses sequential Monte Carlo (SMC) methods to mitigate such biases, but designing effective proposal distributions or potential functions remains a key challenge. In this work, we propose a generic approach to construct proposals and potentials for SMC sampling from $p_{\mathrm{lm}}( \cdot \mid \mathrm{constraint})$. First, we show that constraints specified as finite automata can be tensorized for efficient execution on GPUs, which we use to construct globally constrained decoding (GCD) proposals. In addition, leveraging the fact that tensorized finite automata share the same circuit structure as hidden Markov models, we circuit-multiply them to obtain the probabilistic GCD (P-GCD) proposals encoding both logical and probabilistic information about the target distributions. We evaluate (P-)GCD on the tasks of function calling, keyword-based generation, and SQL generation. Experiments show that under the same SMC sampling setup, compared to LCD proposals, (P-)GCD converges faster to the target distribution with significantly fewer particles.