Enforcing Meter in Finite-Length Markov Sequences

Pierre Roy, François PachetAAAI 2013 · DOI

Introduction

Generative AI often struggles with the tension between local stylistic consistency and global structural integrity. While Markov processes are highly effective at capturing local transitions—the "bread and butter" of statistical style imitation—they are fundamentally memoryless. This lack of global awareness makes them unsuitable for domains requiring strict structural rules, such as poetry (fixed syllable counts) or music (specific beats per bar).

Standard Markov models frequently "drift," failing to meet these global targets. Previous attempts to bridge this gap via Markov constraints often resulted in exponential search times or failed to find valid solutions for complex arithmetic constraints. This paper, presented at AAAI 2013 by researchers from Sony CSL, introduces the meter constraint: a pseudo-polynomial algorithm that ensures "backtrack-free" generation of sequences that strictly obey complex structural rules while maintaining stylistic consistency.

Methodology: The meter Constraint

The authors frame sequence generation as a Constraint Satisfaction Problem (CSP). Their primary innovation lies in an efficient filtering mechanism that avoids the exponential explosion typically associated with global constraints.

Graph Representation and Arc-Consistency

The Markov model is represented as a multi-partite graph where nodes represent possible values and edges denote valid transitions. To enforce the meter constraint, the authors developed a specialized arc-consistency algorithm. Instead of storing every possible path—which would be computationally prohibitive—the algorithm stores sets of possible costs at each node.

Figure 2: The filtering algorithm stores sets of possible costs at each node to ensure global constraints are met without exponential search.

Mathematical Foundation: Khovanskii’s Theorem

The technical "secret sauce" is the application of Khovanskii’s theorem on sumsets. This theorem demonstrates that the number of possible sums in these sequences grows polynomially rather than exponentially. This insight allows the algorithm to remain pseudo-polynomial, making it fast enough for real-time applications. Once the graph is filtered, any greedy walk through it is guaranteed to produce a valid sequence that satisfies both the Markovian style and the global meter rules, enabling backtrack-free generation.

Key Results and Applications

The approach was evaluated using two distinct corpora: musical melodies from "The Star Spangled Banner" and text from Marcel Proust’s "À la recherche du temps perdu".

Musical Precision and Rare Sequence Discovery

In musical tests, the system successfully generated melodies respecting complex 3-bar structures where standard models failed. In one instance, the algorithm identified 4,467 valid solutions with zero backtracking. Notably, it was able to discover "rare" valid sequences with cumulative probabilities as low as 0.0043—sequences nearly impossible to find through standard sampling or heuristic searches.

Figure 3: A generated melody demonstrating the system's ability to respect rhythmic bar lines and total duration constraints.

Poetic Efficiency

The algorithm also demonstrated significant scalability in the text domain. Using the massive Proust corpus (approx. 50,000 phrases), it generated Alexandrine verses (12-syllable lines) in less than one second. This efficiency highlights the method's potential for interactive computer-aided design tools for writers and composers.

Conclusion and Future Work

The meter constraint provides a robust framework for separating "statistical flavor" from "hard rules." While currently dependent on integer-based costs, the method offers a clear path toward more sophisticated generative tools. Future work aims to extend these constraints to hierarchical structures, such as nested phrases within larger musical sections, as part of the ongoing "Flow Machines" project.

Summary updated

BibTeX
@inproceedings{roy2013enforcing,
  author = {Pierre Roy and François Pachet},
  title = {{Enforcing Meter in Finite-Length Markov Sequences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8661},
}
Figure