Markov Constraint as Large Language Model Surrogate

Alexandre Bonlarron, Jean-Charles RéginIJCAI 2024

Introduction

Generating text that satisfies rigid, hard constraints—such as specific word inclusions, exact lengths, or rhythmic meters—remains a significant challenge in natural language processing. Traditional approaches often struggle with the combinatorial explosion of the search space. Large Language Models (LLMs) are typically used either via BeamSearch, which can be slow and brittle under rigid constraints, or as a final ranker for millions of candidate sequences generated by Constraint Programming (CP). The latter "vanilla" approach often leads to system crashes (Out-of-Memory) when the search space becomes too large, particularly when moving from 5-grams to more flexible 4-grams.

This paper introduces NgramMarkov, a novel constraint that allows CP to use LLMs as efficient "surrogates." By integrating LLM-derived statistical knowledge directly into the CP filtering process, the researchers successfully generated high-quality text using 4-grams, a task previously considered computationally intractable.

Methodology: The NgramMarkov Constraint

The core innovation lies in the pre-calculation of n-gram probabilities using a lightweight, quantized LLM (e.g., a 4-bit French GPT-2). These probabilities are then used to prune the search tree in real-time through several filtering layers:

  1. Instant Thresholding: A local filter that immediately rejects word transitions with individual probabilities below a certain floor.
  2. Gliding Threshold: A prefix-based filter that ensures the cumulative probability of a sentence does not deviate too far from a statistically expected mean at any step. This prevents the model from entering "dead-end" sequences that cannot result in a high-quality conclusion.
  3. Look-ahead Filtering: A "shaving" algorithm that explores a horizon of p future words to verify that the current choice leads to viable, high-probability paths.
Visualization of the NgramMarkov filtering process, illustrating local thresholds and cumulative gliding constraints.

Statistical Grounding

Rather than relying on arbitrary probability cutoffs, the authors define thresholds based on the actual distribution of the n-gram corpus. By calculating the Mean ($\mu$) and Standard Deviation ($\sigma$) of the n-gram log-probabilities, the filters are grounded in the statistical reality of human language.

Distribution of n-gram log-probabilities (μ = -5.26, σ = 1.43) used to establish statistically grounded filtering thresholds.

Key Results and Insights

The 4-gram Breakthrough

In constrained text generation, lower "n" values provide more flexibility but exponentially increase the search space. While previous CP methods were limited to 5-grams, NgramMarkov makes 4-gram generation feasible. The vanilla model crashed on 4-gram tasks, whereas the NgramMarkov model produced tens of thousands of valid solutions efficiently.

Quality and Efficiency

The "Look-ahead" criterion significantly enhanced text quality. Mean Perplexity (PPL) dropped from 38 in the vanilla model to 26, with a much tighter statistical range (7 to 66, compared to 7 to 292). Efficiency was maintained through 4-bit quantization and Flash Attention, reducing n-gram scoring time to approximately 10ms. Generating ~56,000 solutions took only 330 seconds with the Gliding Threshold and 576 seconds with the more rigorous Look-ahead filter.

Limitations and Future Work

Despite the breakthrough, 4-grams can occasionally produce "contextually blind" results—sentences that are grammatically correct but logically odd due to a lack of long-distance dependencies (e.g., ambiguous pronoun references).

Future research aims to implement "parsimonious LLM calling," where the full LLM is invoked only when the n-gram surrogate is uncertain. This hybrid approach could correct long-distance dependency errors in real-time while maintaining the speed and constraint-satisfaction strengths of the NgramMarkov model.

Summary updated

BibTeX
@inproceedings{bonlarron2024markov,
  author = {Alexandre Bonlarron and Jean-Charles Régin},
  title = {{Markov Constraint as Large Language Model Surrogate}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure