Markov Constraint as Large Language Model Surrogate

1 Introduction

Language modeling is a fundamental challenge in natural language processing (NLP). Language models (LMs), such as ngrams [Shannon, 1951], recurrent neural networks (RNNs), long short-term memory (LSTM) networks [Hochreiter and Schmidhuber, 1997], and transformers [Vaswani et al., 2017] (LLM), are tools employed to model natural language. Which is to say, computing the probability that a sequence of words belongs to a language. In this paper, LMs are looked at through the lens of a constrained text generation task (i.e., producing an output that satisfies a set of requirements). In this context, using an LM as a major method component is extremely common. (e.g., BeamSearch guided by LM [Lu et al., 2022; Liu et al., 2021; Post and Vilar, 2018]).

In practice, there is a strong relationship between the acceptability of an output and the fact that the same output receives a high probability by the LM. However, this statement must be nuanced, as perfectly acceptable samples may obtain poor probabilities in the LM testing phase. Therefore, in general, human verification cannot be avoided, but LMs are the best tools for text generation to minimize human feedback in the loop and to produce the most human-like content.

Constraint Programming (CP) is a paradigm to compute solutions that satisfy constraints. CP is mainly based on filtering algorithms (also known as propagators), which remove values from variable domains that do not belong to a solution of a constraint. The association of such algorithms with global constraints is one of the main strengths of CP because they exploit the specific structure of each constraint.

Recently, a framework for generating constrained sentences in CP has been proposed [Bonlarron et al., 2023] when common approaches like BeamSearch are ineffective. This constrained text generation task is viewed as a discrete combinatorial optimization problem and can be described as follows: the decision Variables represent individual words, the Domains of the variables represent the permissible lexicon, and the Constraints represent the requirements imposed on the generated text.

It focuses on satisfying strong constraints since they are the core difficulty of the problem and relies on n-grams (i.e., sequences of n words of a corpus) to generate sentences of a language. Then, an LLM computes a Perplexity score for each solution, and the best-rated ones are retained. This approach solves the problem that had not yet been solved. However, it produces lots of poor sentences (more than 90%).

Checking the constraint first and then selecting the best solutions is suited as long as the solutions set is limited (thousands of solutions) because the scoring requires calling an LLM to evaluate each solution, which is costly (≥100 ms per call). Even though this method can be reproduced for other problems, using the LLM at the very end of the method can be a drawback, mainly because sequences leading only to poorly evaluated sentences are not filtered. In this way, the LLM is not involved in controlling the combinatorial explosion. It prevents increasing the corpus size or lowering the order of ngrams, which significantly increases the number of solutions to be evaluated, and scoring and ranking millions of solutions with an LLM is impractical. For example, Bonlarron et al.'s method uses 5-grams and is challenging to use with 4-grams.

Therefore, an LLM-based constraint should be designed to efficiently filter out "poor" solutions during the solving. This task is complex for two reasons:

1. The LLM probability computation depends on the elements in the sequence, so it is difficult to decompose. For a given sequence w0...wn where wi are words, we have PLLM(wn|w0...wn-1). The probability is handled in major part by the attention layers [Vaswani et al., 2017] that are not known for their clear interpretability. Therefore, it is unclear how to obtain from PLLM(xn|x0...xn-1), two sub expressions like PLLM(xi|x0...xi-1) and PLLM(xj|xi+1...xj-1) , where i + j = n. It is consequently difficult to estimate an even finer decomposition as a function of the variables (words) and to define a filtering algorithm.
2. The LLM queries are time-consuming 1 . This prevents systematic interaction with an LLM during the search, since it may produce millions of calls.

To overcome these difficulties, we propose to define the NgramMarkov constraint, a variant of the Markov constraints. This constraint is based on a set of n-grams and uses an LLM.

N-grams provide a natural mechanism for enforcing the linguistic constraints locally by defining the acceptable transitions between words. Specifically, two n-grams can be linked if they share at least n-1 words in common. For instance, in the sentence: "The little boy plays with a balloon", several 2-grams can be found (e.g., "The little","little boy", "boy plays", "plays with", "with a", "a ballon").

The main issue when using n-grams is the linguistic mistakes caused by local decisions. For instance, some transitions do not take into account the whole sentence or some critical words in the past.

This leads to three common linguistic mistakes while chaining n-grams: 1) syntactic errors, 2) grammatical errors, and 3) lack of meaning and coherence. To illustrate, a classical pitfall when dealing with n-gram is an agreement mistake between the subject and another word related to it in the sentence. This arises when the distance (in the number of words) is greater than the size of the history (n-1, where n is the size of a given n-gram). For instance, consider the generated text John sometimes sends letters to himself/herself ). The decision to pick himself instead of herself considering the whole sentence is obvious, but both are possible while considering n-gram with n lesser than 6. Despite these limitations, where n-grams are blind to some mistakes, n-grams help to produce correct and meaningful content.

The n-grams can be seen as particular transition functions between their words. To filter n-grams, we can associate probabilities with n-grams (like the maximum likelihood estimation) and use the constraints ElementaryMarkov [Pachet and Roy, 2011] or MDDMarkovProcess [Perez and R´egin, 2017]. However, the filtering associated with the ElementaryMarkov constraint is weak when used with n-grams as a transition function. Since the text is represented as a succession of k words (k-gram), each value (word) in the domain of the variables keeps its support until a particular k-gram is chosen, so there are almost no future values removed by the ElementaryMarkov constraint.

1 https://docs.nvidia.com/nemo-framework/userguide/latest/performance/gpt.html#inference-performance

The MDDMarkovProcess constraint is more global than the ElementaryMarkov constraint and the associated propagator is based on the costMDD propagator [Perez and R´egin, 2017] and so is more powerful. Unfortunately, as the name suggests, this constraint implies working with a MDD (Multivalued Decision Diagram) that represents all the words in the sentence whose probability we want to control. While this solution may be possible with a small corpus and 5-grams, it is no longer possible with a large corpus or 4-grams. This solution is therefore not generally acceptable. Nevertheless, we will reuse the ideas of the costMDD propagator.

To deal with these issues, the propagator of the NgramMarkov constraint is a natural extension of that of the ElementaryMarkov constraint by incorporating the LLM distribution as a replacement for the maximum likelihood estimation of the n-grams and by adding more filtering criteria.

On the one hand, it addresses two significant issues when dealing with n-gram models: 1) sampling complexity (i.e., the lack of example to estimate the probabilities of high order n-gram, n ≥ 3 ), and thus avoiding all smoothing and interpolating algorithms used as a workaround. 2) Sensitivity control of n-gram-based generation, to control the combinatorial explosion that occurs with small n-grams (some n-grams have a branching factor of 200).

On the other hand, it introduces a gliding threshold to impose global regularity. This threshold guarantees that the data do not deviate locally too much from the statistical distribution of n-grams (e.g., mean or standard deviation). It also uses a "look-a-head" approach to consider only potential successions of a given n-gram over a fixed length horizon in the future. This idea, inspired by the propagator of the MDDMarkovProcess constraint, avoids considering minimum or maximum probabilities that cannot occur in the near future of a given n-gram.

The article is organized as follows: Sec. 2 provides reminders of the Large Language Model (LLM) and n-gram model to ensure a full understanding of the approach. Sec. 3 introduces the NgramMarkov constraint and explains how to obtain an LLM-powered n-gram model. Also, it then details the propagator and, in particular, the various filtering criteria that can be used to filter out n-grams. Sec. 4 demonstrates the effectiveness of the approach by sharing several benchmarks associated to each criterion. Additionally, it compares the different strategies in terms of quantitative (e.g., number of solutions) and qualitative analysis (e.g., Perplexity scoring). Subsequently, Sec. 5 gives some perspectives about this work, and Sec. 6 concludes this paper.

2 Preliminaries

2.1 LMConstraints

The ElementaryMarkov constraint (EMC) [Pachet and Roy, 2011] is the first LM constraint. It was designed to address music generation in CP by leveraging Markov chains. An EMC is a triplet (context, continuation, prob) where prob is the likelihood of the continuation given the context. The EMC is repeated for each variable. In a nutshell, EMC allows a CP formulation of a Markov Process [Morin and Quimper, 2014]. Therefore, this contribution enabled statistical guarantees in the solution based on n-gram models for music generation and other prospects. For instance, it allows the melody of a style of music in CP to be modeled (e.g., blues).

The MDDMarkovProcess constraint [Perez and R´egin, 2017] is a global LM constraint. It utilizes an MDD to ensure a lower Pmin and an upper bound Pmax of probability with respect to a given Markov Process M of any solution. This constraint can be viewed as a summation constraint computed in a Cost-MDD, where the costs are logprob.

2.2 Language Model

Language Models (LMs) assign probabilities to sequences of words. Various techniques have been developed to achieve this goal. The following sections briefly introduce two of the most relevant techniques.

N-gram Model

An n-gram model [Jurafsky and Martin, 2009; Shannon, 1951] estimates the probabilities of sequences of words based on a sliding window of size n. (i.e., a context of n words). This assumption is known as the Markov assumption, which states that the probability of a state can be determined solely based on the previous state. The previous state is referred to as a history H, and the size of the history corresponds to n-1 for a given n-gram size.

For instance, in a bi-grammodel (n = 2), the computation only relies on the previous word to predict the next two words in a sequence of words. As a result, the history length is equal to one. If Y is denoted as the following n-gram, the computation is as follows:

where C is the number of occurrences of the n-gram. This method of calculating probabilities is known as Maximum Likelihood Estimation (MLE) [Jurafsky and Martin, 2009]. Consequently, MLE requires a corpus (a set of sentences) to perform this computation. This is a significant limitation because, in real-world applications, this substantially limits the use of higher-order n-grams (n > 3), because if the corpus is not large enough, a lot of n-grams are present in only one or two sentences and the MLE assigns them a probability of 1 or 1/2.

Nevertheless, despite the difficulty of gathering sufficient data to compute accurate probabilities, n-gram models are computationally efficient and cost-effective.

In general, the use of n-grams as a building block to produce text or music that satisfies some properties has been successful in CP (e.g., style modeling [Pachet and Roy, 2011], virtuoso melodies [Pachet et al., 2011], meter [Roy and Pachet, 2013], plagiarism [Papadopoulos et al., 2014], palindromes generation [Papadopoulos et al., 2015], poetry [Perez and R´egin, 2017], standardized sentences [Bonlarron et al., 2023]).

Large Language Model

Large language models (LLMs) [OpenAI, 2023; Touvron et al., 2023] represent the latest generation of language models, primarily relying on powerful neural network architectures. They are trained on massive amounts of data and usually utilize a specific architecture based on attention called Transformer. Despite these technical considerations, their primary goal remains to compute probabilities for sequences of words based on training data. They manipulate word embedding, and two significant parameters play a role in the generation/prediction of the text of LLM.

• Attention: This mechanism enables LLMs to track relationships between words.
• Position: LLMs can incorporate positional encoding, allowing them to account for the order in which words appear in a sequence.

Note that Attention and Position are two parameters that are not considered in the n-gramModel. The primary drawback of LLMs is their computational cost. Due to their immense size and architecture, they require powerful hardware, typically clusters of GPUs, to operate effectively (several models need more than 80GB of GPU VRAM).

3 Method

Our method is based on word sequence filterings using probabilities derived from the n-gram model.

Given two n-grams N1 and N2 of size n, N2 is a successor of N1 if the n - 1 last words of N1 are the n - 1 first words of N2.

Definition 1. Given

• N a set of n-grams,
• X = {x1, x2, ..., xn} a set of variables whose domain are included in N,
• LLM a large language model,
• Pmax a maximum probability.

The constraint NgramMarkov(X, N , LLM, Pmax) ensures that for every allowed tuple t = (N1,N2, ...N|X|), the ngramNi is a successor of the n-gramNi-1 and t satisfies

where PLLM(Ni) is the probability value given by the LLM for the n-gramNi.

The constraint leverages the Markov assumption to approximate the probability computation of an LLM. Roughly, it is a practical estimation of the sequence likelihood.

More precisely, instead of relying on MLE, the constraint utilizes probability values obtained from the LLM. Namely,

is replaced by

This involves querying the LLM for each n-gram and storing the returned probability in the constraint. This approach mitigates the computational overhead of direct LLM calls, which can reach up to 100 milliseconds per query.

3.1 Filtering Criteria of N-grams

In this section, several filtering criteria of n-grams are presented (See Fig. 1). These filtering algorithms are called only for the assigned variables.

Transition Filtering: Instant Threshold

Consider an n-gram of size n, denoted as

along with its k successors,

The decision to keep Nsi as a potential value for the next variable is based on logPLLM(Nsi ). If the probability of chaining the current n-gramNj with the next n-gramNsi falls below the given threshold T (i.e., log PLLM(Nsi ) ≤ T ), then Nsi is filtered out. The n-gram Nsi is no longer considered for assignment to the next variable. This constitutes a local filtering criterion involving a word-by-word filtering step.

Path Filtering: Final Threshold

A global criterion involving the whole sequence S can be made. Several n-grams (Ni) are chained during the generation to produce the final sequence. Therefore, the probability of S can be expressed as the conditional probability of the n-gram chained. P(S) can be written as

Then check the following filtering criterion:

ensures that any sequences produced have a log probability below a given threshold T. This formulation corresponds to the propagator of the MDDMarkovProcess constraint [Perez and R´egin, 2017] with T replacing Pmax.

Prefix-based Filtering: Gliding Threshold

To control the generation, the instant threshold and the final threshold can be fused. On the one hand, some transitions from a local point of view may be particularly unlikely, even though these still exist in the language 2 [Gehrmann et al., 2019]. On the other hand, the whole sequence must have no valuation with a probability too low. Then, threshold T is expressed as a function of the current number of n-grams appended in the sequence so far. It allows some very unlikely transitions to happen, but at the same time, it ensures a high overall probability. The most straightforward way to define T is to divide it by the number of n-grams needed (i.e., the number of words needed in the output). The main intuition behind the gliding threshold is that it enforces a sort of regularity (i.e., a limited spread between two probability valuations) compared to the Final Threshold.

For each value k from 1 to |X|, there is one inequality derived from:

This expression can be fine-tuned by taking account of the statistic summary extracted from the n-gram distribution. First, by allowing a bit of slacking that the constant Cslack quantifies (it allows to start more often with unlikely n-gram of the start of a sentence).

For each value k from 1 to |X|, there is one inequality derived from:

Then T can be defined, thanks to the Mean µ and the Standard Deviation σ of the n-gram distribution.

For each value k from 1 to |X|, there is one inequality derived from:

Finally, Cslack can be defined as one standard deviation (i.e., Cslack = σ), and λ factor defines how n-grams that do not belong to the right tail of the n-gram distribution are penalized. Its range is [0, 2].

Look-a-head Filtering

Chaining between n-grams is strongly constrained because there must be n - 1 words in common. Also, the number of n-grams that can be reached in the near future from a single given n-gram is quite small compared to the overall n-gram set. As a result, the probabilities for future n-grams are also quite specific. It is therefore advisable to use a filtering algorithm for the n-grams possible for the kth word generated, which can be seen as a shaving algorithm: for each n-gram and for a given depth p (where the depth p defined the horizon in the future), only the n-grams that can be reached up to p are considered in the previous filterings. This enumeration of n-grams could be stored in an MDD of depth p.

2 Some AI-generated text detectors work by following this assumption: if a given text contains unlikely words in several positions, it should be human-made. (see http://gltr.io)

This makes a significant difference to the algorithm that considers all possible n-grams simultaneously, as the n-grams reached may have very different probabilities, and the minimum or maximum probability calculated for each potential future word is no longer necessarily related to the n-gram constraint.

Thus, an n-gram is filtered out if none of its future transitions (in p steps) may lead to a high enough probability sequence.

For each value k from i to i + p, there is one inequality derived from:

Then T |X| is replaced in the same way as for the gliding criterion, i.e. (µ- (λσ)).

The relationship between two n-grams extends as long as the minimum distance between their words is less than n. If the distance between them exceeds n, any n-gram can follow, regardless of its linguistic relation to the first n-gram. This reasoning can be illustrated with the same example from the introduction with the sentence: John sometimes sends letters to himself/herself. With 5-gram, it is possible to use herself. It is not possible with n-gram with n ≥ 6. Therefore the length of the horizon is not greater than n.

4 Results

4.1 Experimental Conditions

The approach described in Sec. 3 is implemented in Java 17. The code is available upon request.

Application: The propagator is evaluated on a standardized sentences generation task [Bonlarron et al., 2023].

Generation: The generation experiments were performed on a machine using an Intel(R) Xeon(R) W-2175 CPU @ 2.50GHz with 256 GB of RAM and running under Ubuntu 18.04.

Inference: The LLM inference experiments were performed on a machine using an AMD EPYC 7313 16-Core CPU @ 3GHz with 512 GB of RAM and an A100 GPU running under Ubuntu 20.04.6 LTS.

Evaluation: The scoring of the solution set is performed by the LLM used by Bonlarron et al. 3 (See [Simoulin and Crabb´e, 2021] for more information).

3 https://huggingface.co/asi/gpt-fr-cased-base

(b) µ = -4.76 , σ = 1.24

Figure 2: This figure draws the distribution of 4-grams (a) and 5grams (b) extracted from french books binded with log-prob computed from a light french GPT model3 (a,b) and their associated Quantile-Quartile plot (QQplot) respectively (a,c) and (b,d).

4.2 Achieving around 10ms N-Gram Scoring

Even though it is offline computation, scoring millions of ngrams can be extremely long. Two ways can be used to reduce as much as possible that time: (1) choosing the lightest possible model (i.e., train on a small corpus). 2) using LLM performance optimization techniques.

Consequently, the model used to score the different ngrams is the lightest French GPT-2 that can be found on Hugging-face Library [Wolf et al., 2020] 4 . Then, a series of optimizations are done before loading and querying it: (i) Model Quantization [Jacob et al., 2018] (Q4) (ii) betterTransformers (iii) fast-attention (Flash Attention [Dao et al., 2022]). It takes, on average, 10 ms to score a n-gram and scoring all 5-grams took less than a day. All the French 4grams took roughly the same. Both n-grams distributions can be seen in Fig. 2

4.3 Statistical Analysis

Once the n-grams extracted from the books have been associated with a probability value calculated by an LLM, the threshold T used as filtering criteria during generation must be defined.

T could be found by trials and errors concerning an expected number of solutions or run time. (e.g., by taking an huge T value and decreasing it each time). However, this method is inaccurate and slow.

It is more interesting to define T from the resulting distribution of the probabilities of the n-grams (see Fig. 2a and Fig. 2b). The two distributions though similar to normal distribution are not. The associated quantile-quantile (QQ) plot, gives an intuition on why both fail normality test. In fact, both distributions are left-skewed (see Fig. 2c and Fig. 2d). A left-skewed QQ-plot indicates that the distribution is not symmetrical, with a longer tail extending towards the lower end of the range. This is illustrated by the concave curvature of the QQ-plot curve relative to the reference line. The imbalance between the mean and median, where the mean is pulled towards the left, further highlights the left-skewed nature of the distribution. Even though, the distributions are not normal, their mean and standard deviation, remains relevant values to describes them. Therefore, they can still be used to define some interesting filtering ranges.

4 https://huggingface.co/ClassCat/gpt2-base-french

In this paper, the threshold T is simply defined as a linear combination of the mean (µ) and the standard deviation (σ) of the n-gram distributions.

4.4 Performance Analysis

For the sake of clarity, Bonlarron et al.'s approach is renamed the "vanilla model". First, the results obtained with the vanilla model are reproduced in Tab.1. 5,052 solutions are generated for 5-grams, and it is not possible to deal with 4-grams. Tables 2, 3, 4 give the results obtained with different filtering criteria of the NgramMarkov constraint.

All of the criteria associated with the new constraint eliminate many sentences from the vanilla model, which is an expected result. The Instant Threshold and Look-ahead criteria successfully compute solutions set with 4-grams. The Gliding Threshold criterion does not have enough memory when λ ≤ 1.25. The Instant Threshold criterion applies a selective filtering. By ensuring that all n-grams in a solution meet a minimum probability threshold, many solutions are filtered.

The Gliding Threshold criterion offers a more nuanced filtering approach. Although it filters less than the Instant Threshold, it captures more information about word sequences. It does not filter sufficiently for λ ≤ 1.25 and fails to prevent an out-of-memory (OOM) error. There is no noticeable overhead in computing solutions compared with Lookahead. In fact, to obtain 56652 solutions in 4-grams with λ = 1.5 for Tab. 3, it takes 330 seconds, whereas to obtain an equivalent number of solutions with look-ahead with λ = 1.25 it takes 576 seconds. This can be explained by the fact that look-ahead explores for each n-gram its future successors on the p horizon in Tab. 4. However, it allows to check strong properties on the future of n-grams, resulting in strong filtering even on permissive values like λ = 1.

The Look-ahead criterion is able to compute the solution set for the most interesting values of λ (i.e. λ ≥ 1). With 5-grams, it tends to remove too many solutions (i.e. λ > 1). However, for λ = 1, it deletes many solutions but retains a large proportion of the best ones.

The vanilla model selects sentences using the perplexity computation. It is, therefore, essential to compare the perplexity-scored sentences of the different approaches.

Fig. 3 compares the PPL distribution of the generated sentences when using 5-grams for the Gliding Threshold criterion, the Look-ahead criterion, and the vanilla model. The perplexity interval of the vanilla model is (7, 292], and the mean is 38. The Gliding Threshold criterion eliminates many outliers, but the statistical range remains large (7, 177] with a mean equals to 29, whereas for Look-ahead criterion the statistical range is greatly reduced (7, 66] with a mean equals to 26. A maximum value for the perplexity in order to help the sentence selection seems to be 27. With this value, the vanilla model keeps 2, 000 sentences, the Gliding Threshold criterion 1, 000, and the Look-ahead criterion 100. Depending on the number of required sentences, a particular criterion and its associated lambda value can be chosen.

4 https://www.deepl.com/translator

4.5 Limitations

In 5-grams: The approach makes the sentence selection parts in the solutions set more manageable despite some good sentences being lost. The loss of some good solutions in the process is a clear drawback. Nevertheless, it empirically removes many poor solutions, so the approach remains useful.

In 4-grams: The novel propagator is essential since the vanilla model made 4-grams computation intractable. However, the mistakes that occur occasionally in 5-grams appear regularly in 4-grams. As a result, the proportion of poor solutions is significantly increased.

5 Discussion

5.1 Perplexity Ranking

During the selection of sentences generated from 4-grams, a new difficulty appears. Tab. 6 shows a short sample of the best-scored 4-gram solutions. They are correct French sentences but are often not self-contained. The three first illustrated it somehow. They are a little later in the night from Saturday to Sunday. The verb be, i.e., are does not sound appropriate here, even though it only makes sentences weird but not incorrect. The sentence would not sound strange in a particular context (e.g., "they" refers to trains). Whereas, the third sentence: He stays a little later in the night from Saturday to Sunday is not the best sentence that one could imagine, but it is context-free. The problem is that the LLM slightly prefers the first sentence (PPL=9) (not context-free) instead of this one (context-free) (PPL=11). This subtle difference is, in practice, substantially increased in other cases. Thus, the sentence selection induced by 4-grams is more intricate, although good sentences can still be found semi-manually (see Tab. 5).

5.2 RelatedWorks

Several constraints based on statistical intelligence, such as the Spread [Pesant and R´egin, 2005] or the Deviation [Schaus et al., 2007] constraints have been designed.

Our work fits into this theme because we are looking for well-balanced solutions in the sense of a statistical distribution. An MDD cannot be used to represent n-grams finely, as it would be too big, but we can ask ourselves whether we could use an automaton to model our problem using the CostRegular Constraint [Demassey et al., 2006] that uses automaton instead of MDD. Recent work shows that it is possible to approximate a probabilistic model (like a RNN) in a weighted finite automaton [Suresh et al., 2021]. This shows that it would certainly be possible to do the same with an LLM. The problem is that the Cost-Regular Constraint works on a Directed Acyclic Graph, which is quite close in size to an MDD.

5.3 Perspectives

Calls Parsimoniously the LLM

The possibility of spending some time querying LLM during the search becomes realistic with the new constraint. The Markov assumption (i.e., Pn-gram) used to approximate sequence probability, while useful, is not without its limitations and can lead to errors. Calling with parsimony, an LLM could eventually correct part of the mistakes made with the n-grammodel. In detail, in the "false positive" filtering where Pn-gram gives an acceptable probability, a computation involving the whole sequence with an LLM may detect a mistake regarding long dependency between words. However, it is difficult to make a decision based on an LLM forecast.

Creativity Assistant

The various works by Pachet and Roy have one thing in common. It is all about interactivity with the user, especially in the context of musical composition. One of their aims was for the system to stimulate the creativity of a musician. Therefore, fast and accurate results are expected. Looking at the results, particularly the number of sentences generated for certain criteria, the constraint filters out a huge number of solutions, which can be a little disappointing when considering the original aim of Bonlarron et al. (to obtain new sentences for application in vision research). However, other applications can be considered, such as the generation of song lyrics. In that case, the proposed propagator has excellent potential in interactive mode, where a user can obtain a few solutions quickly (i.e., almost in real-time).

6 Conclusion

The NgramMarkov constraint has been presented. It surrogates a Large Language Model thanks to an n-gram model. The filtering criteria enforce a limitation over the probability computation of the n-gram of the sentences generated. The Gliding Threshold and Look-ahead criteria demonstrate their effectiveness by computing solutions set with 4-grams and 5-grams. The experimental analysis of the sentences generated shows that the constraint positively affects the sentence selection task performed by the perplexity ranking. Reducing the number of candidate sentences and deleting outlier values (i.e., poorly scored sentences) enforces regularity concerning the mean and the standard deviation of the n-gram distribution. A better control of n-gram-based generation in CP is now possible because it significantly avoids scaling issues caused by the corpus or the n-gram size.

Acknowledgments

We are grateful to Nadjib Lazaar from LIRMM (University of Montpellier, CNRS, France) for his insightful question on how to incorporate learnings from the solution set into future iterations of the work.

This work has been supported by the French government, through the 3IA Cˆote d'Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002.