Large Language Model Meets Constraint Propagation

📄 arXiv: 2505.24012v1 📥 PDF

作者: Alexandre Bonlarron, Florian Régin, Elisabetta De Maria, Jean-Charles Régin

分类: cs.CL, cs.AI

发布日期: 2025-05-29

备注: To appear in the Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2025)

💡 一句话要点

GenCP结合掩码语言模型，实现更可靠的约束感知文本生成

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

关键词: 大型语言模型 约束编程 掩码语言模型 文本生成 约束满足问题

📋 核心要点

  1. 大型语言模型在生成文本时难以满足外部约束，因为它们逐个token生成，缺乏明确的控制机制。
  2. GenCP结合LLM和约束编程，将文本生成转化为约束满足问题，通过约束传播来引导生成过程。
  3. 通过集成掩码语言模型，GenCP实现了双向约束传播，显著提升了在严格约束下文本生成的性能。

📝 摘要（中文）

大型语言模型(LLM)擅长生成流畅的文本，但由于它们顺序生成token且缺乏显式控制机制，因此难以强制执行外部约束。GenCP通过结合LLM预测与约束编程(CP)推理来解决此限制，将文本生成形式化为约束满足问题(CSP)。本文通过集成掩码语言模型(MLM)进行领域生成来改进GenCP，从而实现利用过去和未来token的双向约束传播。这种集成弥合了token级预测和结构化约束执行之间的差距，从而实现更可靠和约束感知的文本生成。在COLLIE基准上的评估表明，通过MLM调用合并领域预览显著提高了GenCP的性能。虽然这种方法会产生额外的MLM调用，并且在某些情况下会增加回溯，但总体效果是更有效地利用LLM推理，并增强了生成可行和有意义的解决方案的能力，尤其是在具有严格内容约束的任务中。

🔬 方法详解

问题定义：论文旨在解决大型语言模型在生成文本时难以满足外部约束的问题。现有方法，如直接使用LLM生成，缺乏对约束的显式控制，容易生成不符合约束的文本。GenCP虽然通过约束编程引入了约束，但其领域生成方式仍有改进空间。

核心思路：论文的核心思路是利用掩码语言模型(MLM)进行领域生成，从而实现双向约束传播。MLM能够根据上下文预测被mask的token，这使得GenCP能够同时考虑过去和未来的token，从而更有效地进行约束传播。

技术框架：改进后的GenCP框架包含以下主要模块：1) LLM预测：使用LLM生成初始文本；2) 约束建模：将文本生成问题建模为约束满足问题(CSP)，定义变量（token）和约束（如内容约束）；3) 领域生成：使用MLM为每个变量生成候选值（token），形成变量的领域；4) 约束传播：利用约束编程技术，根据约束缩小变量的领域；5) 选择与赋值：从剩余的领域中选择token并赋值给变量；6) 回溯：如果赋值导致冲突，则进行回溯。

关键创新：最重要的技术创新点是使用MLM进行领域生成，实现了双向约束传播。与传统的单向约束传播相比，双向约束传播能够更早地发现冲突，从而减少回溯次数，提高生成效率。

关键设计：关键设计包括：1) MLM的选择：选择合适的MLM模型，以保证领域生成的质量；2) Mask策略：设计合适的mask策略，以充分利用上下文信息；3) 约束编程求解器：选择高效的约束编程求解器，以保证约束传播的效率；4) 回溯策略：设计合理的回溯策略，以避免陷入局部最优。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果表明，通过集成MLM进行领域预览，GenCP在COLLIE基准测试中取得了显著的性能提升。具体而言，该方法能够更有效地利用LLM推理，并增强了生成可行和有意义的解决方案的能力，尤其是在具有严格内容约束的任务中。虽然引入MLM调用会增加计算成本，但总体上提高了生成效率。

🎯 应用场景

该研究成果可应用于需要严格内容约束的文本生成任务，例如：自动生成符合特定格式的报告、生成满足特定关键词要求的文章、生成符合语法规则的代码等。该方法可以提高生成文本的质量和可靠性，减少人工干预，具有重要的实际应用价值。

📄 摘要（原文）

Large Language Models (LLMs) excel at generating fluent text but struggle to enforce external constraints because they generate tokens sequentially without explicit control mechanisms. GenCP addresses this limitation by combining LLM predictions with Constraint Programming (CP) reasoning, formulating text generation as a Constraint Satisfaction Problem (CSP). In this paper, we improve GenCP by integrating Masked Language Models (MLMs) for domain generation, which allows bidirectional constraint propagation that leverages both past and future tokens. This integration bridges the gap between token-level prediction and structured constraint enforcement, leading to more reliable and constraint-aware text generation. Our evaluation on COLLIE benchmarks demonstrates that incorporating domain preview via MLM calls significantly improves GenCP's performance. Although this approach incurs additional MLM calls and, in some cases, increased backtracking, the overall effect is a more efficient use of LLM inferences and an enhanced ability to generate feasible and meaningful solutions, particularly in tasks with strict content constraints.