# Intertwining CP and NLP: The Generation of Unreasonably Constrained Sentences

arXiv: https://arxiv.org/abs/2406.15473 · HTML: https://mlsanity.com/paper/2406.15473/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 15 Jun 2024.

## Builds on (most cited first, 9 of 9)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [COLLIE: Systematic Construction of Constrained Text Generation Tasks](https://mlsanity.com/paper/2307.08689/) (2023)
- [Why is constrained neural language generation particularly challenging?](https://mlsanity.com/paper/2206.05395/) (2022)
- [Constrained Text Generation with Global Guidance -- Case Study on CommonGen](https://mlsanity.com/paper/2103.07170/) (2021)
- [Peel-and-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams](https://mlsanity.com/paper/2205.05216/) (2022)
- [Constraints First: A New MDD-based Model to Generate Sentences Under Constraints](https://mlsanity.com/paper/2309.12415/) (2023)

## Built on by (most cited first, 3 of 3)

- [Combining Constraint Programming Reasoning with Large Language Model Predictions](https://mlsanity.com/paper/2407.13490/) (2024)
- [Large Language Model Meets Constraint Propagation](https://mlsanity.com/paper/2505.24012/) (2025)
- [Verifier-Guided Twelve-Tone Composition: A Generate-Verify-Repair Harness for Symbolic Music Generation](https://mlsanity.com/paper/2607.11334/) (2026)

## Abstract (arXiv)

Constrained text generation remains a challenging task, particularly when dealing with hard constraints. Traditional NLP approaches prioritize generating meaningful and coherent output. Also, the current state-of-the-art methods often lack the expressiveness and constraint satisfaction capabilities to handle such tasks effectively. Recently, an approach for generating constrained sentences in CP has been proposed in (Bonlarron et al, 2023). This ad-hoc model to solve the sentences generation problem under MNREAD rules proved neithertheless to be computationaly and structuraly unsuitable to deal with other more constrained problems. In this paper, a novel more generic approach is introduced to tackle many of these previously untractable problems, and illustrated here with the quite untractable sentences generation problem following RADNER rules. More precisely, this paper presents the CPTextGen Framework. This framework considers a constrained text generation problem as a discrete combinatorial optimization problem. It is solved by a constraint programming method that combines linguistic properties (e.g., n-grams or language level) with other more classical constraints (e.g., the number of characters, syllables). Eventually, a curation phase allows for selecting the best-generated sentences according to perplexity using an LLM. The effectiveness of this approach is demonstrated by tackling a new, more tediously constrained text generation problem: the iconic RADNER sentences problem. This problem aims to generate sentences respecting a set of quite strict rules defined by their use in vision and clinical research. Thanks to our CP-based approach, many new strongly constrained sentences have been successfully generated. This highlights our approach's potential to handle unreasonably constrained text generation scenarios.