# Constraints First: A New MDD-based Model to Generate Sentences Under Constraints

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 63 references that are in the map.
- First posted on arXiv 21 Sep 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting](https://mlsanity.com/paper/2012.07436/) (2020)
- [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)
- [Constrained Text Generation with Global Guidance -- Case Study on CommonGen](https://mlsanity.com/paper/2103.07170/) (2021)
- [Most Language Models can be Poets too: An AI Writing Assistant and Constrained Text Generation Studio](https://mlsanity.com/paper/2306.15926/) (2023)
- [Peel-and-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams](https://mlsanity.com/paper/2205.05216/) (2022)

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

- [Combining Constraint Programming Reasoning with Large Language Model Predictions](https://mlsanity.com/paper/2407.13490/) (2024)
- [Markov Constraint as Large Language Model Surrogate](https://mlsanity.com/paper/2406.10269/) (2024)
- [Intertwining CP and NLP: The Generation of Unreasonably Constrained Sentences](https://mlsanity.com/paper/2406.15473/) (2024)
- [Large Language Model Meets Constraint Propagation](https://mlsanity.com/paper/2505.24012/) (2025)

## Abstract (arXiv)

This paper introduces a new approach to generating strongly constrained texts. We consider standardized sentence generation for the typical application of vision screening. To solve this problem, we formalize it as a discrete combinatorial optimization problem and utilize multivalued decision diagrams (MDD), a well-known data structure to deal with constraints. In our context, one key strength of MDD is to compute an exhaustive set of solutions without performing any search. Once the sentences are obtained, we apply a language model (GPT-2) to keep the best ones. We detail this for English and also for French where the agreement and conjugation rules are known to be more complex. Finally, with the help of GPT-2, we get hundreds of bona-fide candidate sentences. When compared with the few dozen sentences usually available in the well-known vision screening test (MNREAD), this brings a major breakthrough in the field of standardized sentence generation. Also, as it can be easily adapted for other languages, it has the potential to make the MNREAD test even more valuable and usable. More generally, this paper highlights MDD as a convincing alternative for constrained text generation, especially when the constraints are hard to satisfy, but also for many other prospects.