# Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 26 references that are in the map.
- First posted on arXiv 8 May 2026.

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

- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [Maximum entropy models capture melodic styles](https://mlsanity.com/paper/1610.03414/) (2016)

## Built on by (most cited first, 2 of 2)

- [Tonal parsimony in chord-sequence analysis: combining modulation cost and tonal vocabulary](https://mlsanity.com/paper/2606.03459/) (2026)
- [Attractive and Repulsive Pattern Control in Sequence Generation](https://mlsanity.com/paper/2606.24911/) (2026)

## Abstract (arXiv)

Variable-order Markov models generate sequences over a finite alphabet by conditioning each symbol on the longest available suffix of the generated history. Regular constraints, by contrast, describe finite-horizon control requirements by an automaton: fixed positions, forced endings, metrical patterns, and forbidden copied fragments are all special cases. Existing exact methods already handle regular constraints with belief propagation for first-order Markov chains. The contribution here is the variable-order extension: identifying the state space on which the existing BP-regular machinery must be run when the generator is a variable-order/backoff model. A first-order constraint layer can enforce useful support conditions, but it computes future mass after merging histories that a variable-order generator deliberately keeps distinct. We formalize this mismatch and give the sparse construction obtained by replacing the first-order Markov state with the observed context state, then taking the standard product with the regular constraint automaton. For a fixed trained context graph and automaton, inference is linear in the sequence horizon; in general it is polynomial in the number of reachable product edges. This gives the correct variable-order distribution conditioned on regular constraints without expanding to all K-tuples. The same finite-source interface supports reversible data augmentation by inverse count lookup, matching materialized transposition augmentation without storing transformed corpora. We also separate exact BP inference from generation-time backoff policies, such as singleton avoidance, whose stochastic semantics must be made explicit if exactness is claimed.