Variable-Order Markov Generation with Regular Constraints via Sparse BP

A new arXiv paper (2605.07839) extends belief propagation (BP) methods to handle regular constraints in variable-order Markov models. Regular constraints, such as fixed positions, forced endings, metrical patterns, and forbidden copied fragments, are described by automata and previously handled exactly only for first-order Markov chains. The authors identify the state space needed to run BP-regular machinery for variable-order/backoff generators. They formalize a mismatch between first-order constraint layers and variable-order histories, and propose a sparse construction to resolve it.