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
• Authors: Alexandre Bonlarron, Florian Régin, Elisabetta De Maria, Jean-Charles Régin,
• 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

• 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.