# Markov Constraint as Large Language Model Surrogate

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference](https://mlsanity.com/paper/1712.05877/) (2017)
- [GLTR: Statistical Detection and Visualization of Generated Text](https://mlsanity.com/paper/1906.04043/) (2019)
- [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)
- [Approximating probabilistic models as weighted finite automata](https://mlsanity.com/paper/1905.08701/) (2019)
- [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)
- [Do Recipes Have Personas? Characterizing and Generating Creator Style in Attributed Procedural Graphs](https://mlsanity.com/paper/2608.24369/) (2026)

## Abstract (arXiv)

This paper presents NgramMarkov, a variant of the Markov constraints. It is dedicated to text generation in constraint programming (CP). It involves a set of n-grams (i.e., sequence of n words) associated with probabilities given by a large language model (LLM). It limits the product of the probabilities of the n-gram of a sentence. The propagator of this constraint can be seen as an extension of the ElementaryMarkov constraint propagator, incorporating the LLM distribution instead of the maximum likelihood estimation of n-grams. It uses a gliding threshold, i.e., it rejects n-grams whose local probabilities are too low, to guarantee balanced solutions. It can also be combined with a "look-ahead" approach to remove n-grams that are very unlikely to lead to acceptable sentences for a fixed-length horizon. This idea is based on the MDDMarkovProcess constraint propagator, but without explicitly using an MDD (Multi-Valued Decision Diagram). The experimental results show that the generated text is valued in a similar way to the LLM perplexity function. Using this new constraint dramatically reduces the number of candidate sentences produced, improves computation times, and allows larger corpora or smaller n-grams to be used. A real-world problem has been solved for the first time using 4-grams instead of 5-grams.