Large Language Model Meets Constraint Propagation

• URL: http://arxiv.org/abs/2505.24012v1
• Date: Thu, 29 May 2025 21:18:12 GMT
• Title: Large Language Model Meets Constraint Propagation
• Abstract summary: GenCP combines predictions with Constraint Programming (CP) reasoning to generate fluent text.<n>We improve GenCP by integrating Masked Language Models (MLMs) for domain generation, which allows constraint propagation.<n>Our evaluation on COLLIE benchmarks demonstrates that incorporating domain preview via bidirectional calls significantly improves GenCP's performance.
• Score: 42.54350568915404
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Tractable Hierarchical Control of Autoregressive Language Models [13.930492173862165]
  Constraining the generation of autoregressive large language models (LLMs) is an important component of integrating language models into formal systems.<n>By distilling the LLM to a tractable probabilistic model, its autoregressive generation can be steered and masked to incorporate the probability of satisfying logical constraints.
  arXiv  Detail & Related papers  (2026-06-01T14:57:46Z)
• Learning and Enforcing Context-Sensitive Control for LLMs [48.58004364546273]
  We introduce a framework that automatically learns context-sensitive constraints from Large Language Models interactions.<n>Experiments demonstrate that our method enables even small LLMs (1B parameters) to learn and generate with perfect constraint adherence.
  arXiv  Detail & Related papers  (2026-04-12T14:50:03Z)
• Optimized Algorithms for Text Clustering with LLM-Generated Constraints [9.075693512125042]
  Many researchers have incorporated background knowledge, typically in the form of must-link and cannot-link constraints, to guide the clustering process.<n>With the recent advent of large language models (LLMs), there is growing interest in improving clustering quality.<n>We propose a novel constraint-generation approach that reduces resource consumption by generating constraint sets rather than using traditional pairwise constraints.
  arXiv  Detail & Related papers  (2026-01-16T09:26:37Z)
• Cost-Effective Text Clustering with Large Language Models [15.179854529085544]
  This paper proposes TECL, a cost-effective framework that taps into the feedback from large language models for accurate text clustering.<n>Under the hood, TECL adopts our EdgeLLM or TriangleLLM to construct must-link/cannot-link constraints for text pairs.<n>Our experiments on multiple benchmark datasets exhibit that TECL consistently and considerably outperforms existing solutions in unsupervised text clustering.
  arXiv  Detail & Related papers  (2025-04-22T06:57:49Z)
• Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo [90.78001821963008]
  A wide range of LM applications require generating text that conforms to syntactic or semantic constraints.<n>We develop an architecture for controlled LM generation based on sequential Monte Carlo (SMC)<n>Our system builds on the framework of Lew et al. (2023) and integrates with its language model probabilistic programming language.
  arXiv  Detail & Related papers  (2025-04-17T17:49:40Z)
• Multi-Attribute Constraint Satisfaction via Language Model Rewriting [67.5778646504987]
  Multi-Attribute Constraint Satisfaction (MACS) is a method capable of finetuning language models to satisfy user-specified constraints on multiple external real-value attributes.<n>Our work opens new avenues for generalized and real-value multi-attribute control, with implications for diverse applications spanning NLP and bioinformatics.
  arXiv  Detail & Related papers  (2024-12-26T12:36:39Z)
• Combining Constraint Programming Reasoning with Large Language Model Predictions [44.99833362998488]
  Constraint Programming (CP) and Machine Learning (ML) face challenges in text generation. This paper proposes a solution by combining both approaches and embedding a Large Language Model (LLM) in CP.
  arXiv  Detail & Related papers  (2024-07-18T13:15:55Z)
• Evaluating, Understanding, and Improving Constrained Text Generation for Large Language Models [49.74036826946397]
  This study investigates constrained text generation for large language models (LLMs) Our research mainly focuses on mainstream open-source LLMs, categorizing constraints into lexical, structural, and relation-based types. Results illuminate LLMs' capacity and deficiency to incorporate constraints and provide insights for future developments in constrained text generation.
  arXiv  Detail & Related papers  (2023-10-25T03:58:49Z)
• Tractable Control for Autoregressive Language Generation [82.79160918147852]
  We propose to use tractable probabilistic models (TPMs) to impose lexical constraints in autoregressive text generation models. We show that GeLaTo achieves state-of-the-art performance on challenging benchmarks for constrained text generation. Our work opens up new avenues for controlling large language models and also motivates the development of more expressive TPMs.
  arXiv  Detail & Related papers  (2023-04-15T00:19:44Z)
• Mixture of Soft Prompts for Controllable Data Generation [21.84489422361048]
  Mixture of Soft Prompts (MSP) is proposed as a tool for data augmentation rather than direct prediction. Our method achieves state-of-the-art results on three benchmarks when compared against strong baselines.
  arXiv  Detail & Related papers  (2023-03-02T21:13:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.