Exact Regular-Constrained Sampling for Variable-Order Markov Generation

Variable-order Markov models generate by backing off to the longest usable suffix of the generated history, while regular constraints describe finite horizon controls such as fixed endings, metrical patterns, and anti-copy rules. Existing belief-propagation methods give exact regular-constrained sampling for first-order Markov chains, but a first-order state merges histories that a variable-order generator deliberately keeps distinct. We give the corresponding variable-order construction: replace the Markov state by the sparse observed context state and compose this context graph with the regular constraint automaton. For a fixed context graph and automaton, inference is linear in the horizon and in the number of reachable product edges, without expanding to all $|\mathcal{V}|^K$ histories; the same source-row interface handles reversible augmentation by inverse count lookup, without materializing transformed corpora. Tiny enumerated examples verify exact partition functions and conditional probabilities; Bach Prelude experiments show sparse regular-constrained sampling at $K=6$ and 12-key virtual transposition semantics from $592$ stored events.