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

Alexandre Bonlarron, Aurélie Calabrèse, Pierre Kornprobst, Jean-Charles RéginIJCAI 2023 · DOI

TL;DR

This paper introduces a novel approach to generating highly constrained text, specifically for standardized reading tests like MNREAD. By framing sentence generation as a combinatorial optimization problem solved with Multi-valued Decision Diagrams (MDDs) before language modeling, they overcome limitations of traditional methods and generate more diverse, compliant sentences. This work offers a significant breakthrough for creating standardized reading materials and has broader implications for constrained text generation.

What Problem Does This Paper Address?

Generating text that adheres to strict, often complex, constraints is a significant challenge. Traditional methods typically rely on language models (LMs) to generate text and then filter or adjust it to meet constraints. This approach struggles when constraints are "hard" – meaning they are difficult to satisfy and apply to the entire sentence (e.g., length, display rules) rather than just local word choices. For standardized tests like MNREAD, which require sentences to be equivalent in length, display, and linguistic complexity to avoid bias, generating a sufficient number of high-quality, compliant sentences is difficult. Existing methods, like template-based generation, are limited in diversity and difficult to adapt to new languages. The paper aims to address this by prioritizing constraint satisfaction first.

Methods

The core of the proposed method is a "constraints-first" approach using Multi-valued Decision Diagrams (MDDs).

  1. MDD-based Constraint Satisfaction: The authors model sentence generation as a discrete combinatorial optimization problem. They leverage MDDs, a data structure adept at representing and manipulating sets of solutions to constraint satisfaction problems. Specifically, they build an MDD (MDDMNREAD) that encodes the rules of the MNREAD test (grammatical, lexical, length, and display constraints). This MDD allows for the computation of an exhaustive set of valid sentences without explicit search, a key advantage.
  2. MDDtrie for Succession: To handle the sequential nature of sentences, an MDD variant called MDDtrie is used to efficiently store and retrieve n-grams (sequences of words) and their successors, ensuring word order and local coherence.
  3. Language Model for Selection: After generating a large set of constraint-satisfying sentences using MDDs, a pre-trained Language Model (GPT-2) is employed. Instead of using the LM for generation, it acts as an "oracle" to score the generated sentences based on their fluency and naturalness using perplexity. This allows for selecting the "best" sentences from the valid set, ensuring they are not only compliant but also meaningful and well-formed.

Datasets

  • Corpus for N-grams:
    • French: 443 books from the youth category.
  • English: 75 books from the fiction category.
  • The choice of corpus is noted as critical, impacting the style and vocabulary of generated sentences.
  • Language Models:
    • OpenAI GPT-2 for English.
  • A French-trained GPT-2 model for French.

Key Insights and Ideas

  • Constraints First, LM Second: The most significant insight is reversing the traditional generation pipeline. By satisfying hard constraints before using an LM, the method ensures compliance and then uses the LM to refine quality, rather than trying to force compliance onto LM-generated text.
  • MDDs for Exhaustive Solution Generation: MDDs are shown to be a powerful tool for generating all possible solutions to a set of constraints without requiring complex search algorithms, making the process exact and efficient for finding valid sentences.
  • Perplexity as a Quality Oracle: Using GPT-2's perplexity score as a post-generation filter effectively ranks sentences for fluency and meaning, bridging the gap between purely constraint-satisfying sequences and natural language.
  • Genericity of the Approach: The MDD-based framework is presented as highly modular and generic, allowing for the integration of various constraints and potential adaptation to other languages or text generation tasks.

Key Results

  • MNREAD Sentence Generation: The method successfully generated thousands of sentences for the MNREAD test in French and hundreds in English.
  • Efficiency: The generation process, after MDD construction, was remarkably fast, taking only minutes for experiments that previously took hours with less efficient methods.
  • Sentence Quality: Sentences generated and ranked as "good" by the LM (low perplexity) were read at a speed (164 wpm) statistically indistinguishable from original MNREAD sentences (162 wpm). Sentences ranked "bad" (high perplexity) were read significantly slower (151 wpm).
  • Diversity: The approach generates a much larger pool of candidate sentences compared to existing methods (hundreds/thousands vs. dozens), offering a major breakthrough for standardized tests.

Limitations and Future Work

  • MDD Memory Usage: The MDDtrie construction can be memory-intensive (e.g., 30GB for French 5-grams), though this is considered a preprocessing step.
  • Perplexity Valuation Speed: Scoring sentences with GPT-2 can be slow, especially for French (around 1 hour for a set of sentences).
  • Perplexity as a Constraint: Integrating perplexity directly as a constraint within the MDD framework is challenging due to the non-monotonic nature of perplexity with respect to partial assignments.
  • Corpus Choice: The quality and diversity of generated sentences are highly dependent on the input corpus. Careful selection is crucial, and the paper notes that mixing corpora from disparate topics can lead to unusual sentence combinations.
  • Future Work: The authors suggest exploring ways to integrate perplexity as a constraint, further optimizing the MDD construction, and applying the method to other constrained text generation tasks. They also highlight the potential for this approach to make standardized reading tests more valuable and usable across languages.

Summary updated

BibTeX
@inproceedings{bonlarron2023constraints,
  author = {Alexandre Bonlarron and Aurélie Calabrèse and Pierre Kornprobst and Jean-Charles Régin},
  title = {{Constraints First: A New MDD-based Model to Generate Sentences Under Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/210},
}
Figure