Large Language Model Meets Constraint Propagation

Alexandre Bonlarron, Florian Régin, Elisabetta De Maria, Jean-Charles RéginIJCAI 2025 · DOI

TL;DR

This paper introduces a novel approach that combines the fluency of Large Language Models (LLMs) with the rigorous reasoning of Constraint Programming (CP) to generate text that strictly adheres to user-defined rules. By leveraging Masked Language Models (MLMs) for "domain preview," the system can anticipate future token possibilities, significantly improving constraint satisfaction and generating more meaningful, less generic outputs.

What Problem Does This Paper Address?

Large Language Models (LLMs) are incredibly adept at generating human-like text, but they often falter when it comes to enforcing specific, external constraints. This limitation stems from their sequential, token-by-token generation process, which lacks built-in mechanisms to guarantee adherence to rules. Imagine asking an LLM to write a story that must not contain the letter "e" – it's a task that often proves surprisingly difficult for standard LLMs. This unreliability poses a significant hurdle for applications requiring confident and safe text generation, such as legal document drafting, code generation, or creative writing with specific stylistic requirements. While existing methods like retrieval augmentation or chain-of-thought prompting offer partial solutions, they don't fully address the core problem of generating text that mandatorily meets requirements.

Methods

The paper builds upon a framework called GenCP (Generative Constraint Programming), which treats text generation as a Constraint Satisfaction Problem (CSP). Here's how they enhance it:

  • Meta-Variables: LLMs operate on tokens (which can be parts of words), while traditional CP often works with whole words. To bridge this gap, they introduce "meta-variables" that can represent one or more tokens, allowing for a more flexible mapping between LLM outputs and CP variables. For example, the word "using" could be represented by meta-variables "Us" and "ing".
  • MLM for Domain Preview (The Core Innovation): The key limitation of standard autoregressive LLMs is their unidirectional nature – they only "see" past tokens. This makes it hard for CP solvers to predict future constraints effectively. The authors propose using Masked Language Models (MLMs), like BERT, which can process text bidirectionally. When the CP solver needs to determine possible values (domains) for future tokens, it queries an MLM. This "domain preview" allows the MLM to predict candidate tokens based on both preceding and following context, providing richer information to the CP solver.
  • Constraint Integration and Propagation: The CP solver then uses this enriched domain information to filter possibilities and ensure that assignments satisfy task-specific constraints (e.g., length, forbidden words). This process is iterative, with the CP solver guiding the LLM and MLM to generate text that is both fluent and compliant.

Datasets

The paper evaluates their approach on benchmarks inspired by the COLLIE Benchmark [Yao et al., 2024]. These include:

  • sent-1: A single sentence generation task.
  • para-2 to para-6: Five paragraph generation tasks.

These tasks integrate various constraints, such as specific keyword usage, word counts, character counts, and the exclusion of certain words. The authors note that these tasks are designed to expose the limitations of LLMs in handling constrained generation.

Key Insights and Ideas

  • Bidirectional Context is Crucial for Constraints: The unidirectional nature of standard LLMs is a bottleneck for constraint satisfaction. MLMs, with their ability to understand context from both directions, offer a powerful way to overcome this.
  • Domain Preview Reduces Search Space: By using MLMs to predict potential future tokens, the CP solver gets a "heads-up" on what might come next. This allows it to prune inconsistent paths earlier, leading to more efficient search and fewer backtracks.
  • Balancing Fluency and Rigor: The approach effectively bridges the gap between the "fast, intuitive" reasoning of LLMs (System 1) and the "slow, deliberate" reasoning of CP (System 2), creating a more robust generation system.
  • Meta-Variables Enhance Text Quality: While using meta-variables can increase the search space, it significantly improves the diversity and quality of generated text by allowing the model to explore a broader vocabulary beyond just common short tokens.

Key Results

The proposed "previewMLM" approach demonstrated significant improvements over baseline GenCP variants:

  • Reduced LLM Calls: For the single-sentence task (sent-1), previewMLM reduced LLM calls from 444 (vanilla) to 359, while also decreasing backtracks from 375 to 170.
  • Increased Solutions: Crucially, previewMLM generated 10 solutions for sent-1, compared to 3 for the vanilla approach.
  • Paragraph Generation Improvements: Similar trends were observed in paragraph tasks. For instance, in para-2, previewMLM doubled the number of solutions (from 3 to 6) while reducing LLM calls.
  • Effectiveness on Strict Constraints: The results highlight that the domain preview strategy is particularly effective for tasks with strict content constraints, leading to more feasible and meaningful outputs.

Limitations and Future Work

  • MLM Depth Limitation: The paper notes that the depth of the MLM preview (how many future tokens it looks ahead) was primarily tested on the last two variables of a sentence. While deeper previews were explored, they didn't consistently yield better results and sometimes decreased the number of solutions. The authors suggest that the preview is most effective for propagating sums over the last few variables.
  • Potential for Suboptimal Solutions: While backtracking helps ensure constraint satisfaction, there's a risk that the search might explore low-likelihood regions of the LLM's output space, potentially leading to semantically or stylistically "suboptimal" but valid outputs. The authors suggest mitigation strategies like search restarts and likelihood tracking.
  • Future Work: The authors aim to further refine the interplay between CP and LLM decoding to broaden the potential for generating text where both language fluency and constraint satisfaction are paramount. This could involve exploring more advanced MLM models or different strategies for integrating CP and LLM reasoning.

Summary updated

BibTeX
@inproceedings{bonlarron2025large,
  author = {Alexandre Bonlarron and Florian Régin and Elisabetta De Maria and Jean-Charles Régin},
  title = {{Large Language Model Meets Constraint Propagation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/1115},
}
Figure