Exact Regular-Constrained Sampling for Variable-Order Markov Generation

By François Pachet

François Pachet. “Exact Regular-Constrained Sampling for Variable-Order Markov Generation.” NeurIPS 2026, Paris.

About the paper

How can you generate a melody in a learned style and still make sure it ends on a particular note? A variable-order Markov model adapts how much of the recent sequence it uses to predict the next note. This paper shows how to combine that flexibility with rules for the whole melody, such as a required ending or a pattern the melody must avoid.

Abstract in brief

The method follows two states as it generates a sequence: the current context in the Markov model and the current state of an automaton that tracks the rules. A backward calculation finds the probability of completing the sequence in compliance with the rules from each reachable pair of states. Each next token is then weighted by both its original model probability and the probability that it leads to a valid completion. When the constraints have nonzero probability under the model, this gives an exact sample from the model conditioned on satisfying them.

The arXiv version is titled Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation.

Related research

Exact Sampling for Regular and Markov Constraints with Belief Propagation · PDF (CP 2015) introduced exact sampling for regular-constrained Markov chains using belief propagation. The 2026 paper extends this approach to variable-order models.

See the Markov Constraints project and the earlier paper, Markov Constraints: Steerable Generation of Markov Sequences.