Exact Regular-Constrained Variable-Order Markov Gen... | AI Research

Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation
This paper addresses a fundamental challenge in sequence generation: how to combine the local statistical accuracy of variable-order Markov models with the global requirements of regular constraints. While variable-order models are excellent at preserving stylistic patterns by conditioning on the longest available history, they often struggle when forced to satisfy specific constraints—such as fixed endings or forbidden patterns—that require knowledge of the future. The author introduces a method to perform exact, constrained generation by identifying the correct "sparse" state space for these models, ensuring that the generator respects both the learned style and the desired constraints without the computational burden of dense, high-order state spaces.

The Problem of Mismatched Memory

Variable-order models are designed to "back off" from long, specific contexts to shorter, more general ones when data is sparse. However, existing methods for enforcing constraints often rely on first-order Markov chains, which only look at the most recent symbol. This creates a mismatch: the constraint system merges histories that the variable-order generator treats as distinct. As a result, simple "feasibility masks" or first-order projections often fail to produce the correct probability distribution, leading to sequences that may satisfy constraints but lose the intended stylistic nuance or statistical validity of the original model.

Sparse Context-State Construction

The core contribution of this work is a sparse construction that aligns the inference process with the model’s actual memory. Instead of expanding the state space to include every possible combination of symbols (which is computationally expensive), the author proposes using the "observed context state"—the specific suffixes actually present in the trained model. By taking the product of this sparse context graph with the regular constraint automaton, the system can perform belief propagation (BP) efficiently. This approach ensures that the model computes future probability mass using the same variable-order logic it uses for generation, resulting in an exact constrained distribution.

Inference and Practical Application

For a fixed trained model and constraint automaton, this method is linear in the sequence horizon, making it efficient for real-time applications. The paper also addresses the practical need for data augmentation, such as pitch transpositions in music. By using an "inverse count lookup" interface, the system can apply transformations to the training data without the need to store or materialize massive, transformed corpora. This allows for flexible, constrained generation while maintaining the data efficiency that makes variable-order models attractive for creative tasks.

Distinguishing Inference from Policy

The author emphasizes a clear separation between exact belief propagation and generation-time backoff policies. Policies like "singleton avoidance"—which prevents the model from simply repeating a unique, deterministic fragment from the training data—are treated as distinct from the underlying inference mechanism. By explicitly defining the stochastic semantics of these policies, the paper ensures that the claim of "exactness" remains rigorous, providing a clear framework for developers to implement constrained, style-aware sequence generation.