Autoregressive models enable tractable sampling from learned probability distributions, but their performance critically depends on the variable ordering used in the factorization via complexities of the resulting conditional distributions. We propose to learn the Markov random field describing the underlying data, and use the inferred graphical model structure to construct optimized variable orderings. We illustrate our approach on two-dimensional image-like models where a structure-aware ordering leads to restricted conditioning sets, thereby reducing model complexity. Numerical experiments on Ising models with discrete data demonstrate that graph-informed orderings yield higher-fidelity generated samples compared to naive variable orderings.
Figures & tables
Figure 1: An example graph for illustrating the Markov property and the reduction of conditioning sets.
Figure 2: Depiction of the three variable order traversals—sequential, checkerboard, and diagonal —on a 5×5 lattice. Node shading indicates the relative selection order, from darker to lighter; identical shading denotes equal preference. Nodes without shading are selected after the shaded nodes and are not distinguished by the ordering. Node labels indicate one specific realization of the traversal.
Figure 3: Number of training data samples Ml versus sampling error ε ( 9 ) for both ferro and spin glass Ising models with conditional order O=6 . The number of generated samples Ms=105 . Error bars are one standard deviation over 20 independent training data sets.
Figure 4: Number of generated samples Ms versus sampling error ε ( 9 ) for a ferromagnetic Ising model with different conditional orders O∈{2,4,6} , where the conditionals are learned from the ground-truth distribution p . Error bars indicate one standard deviation over 50 independently generated sample sets.
Figure 5: Number of training data samples Ml versus sampling error ε ( 9 ) for ferro Ising model with model orders O∈{2,4} . The number of generated samples Ms=105 . Error bars indicate one standard deviation over 20 independent training data sets.
Figure 6: Depiction of two sampling sequences for the D-Wave dataset. The top panel illustrates the sublattice-level selection, while the bottom panel shows the selection order of nodes within each sublattice. Node shading indicates selection order.
Figure 7: Number of generated samples Ms versus sampling error ε ( 9 ) for the D-Wave spin glass Ising model with model order O=3 , where the conditional distributions are learned from Ml=5×105 . Error bars indicate one standard deviation over 20 independently generated sample sets.
Generative modeling of discrete data has two popular paradigms: autoregressive models such as GPT, which factorize a sequence in a left-to-right (L2R) order, and masked diffusion models, which are essentially any-order autoregressive modeling. Rather than competing methods, these are the two extreme points of a single axis -- the generation order. For structured discrete domains without a natural traversal, both extremes may be suboptimal, yet the intermediate choice -- a single well-adapted order -- remains largely unexplored. We introduce OrderGPT, which builds on Any-Order GPT to learn a task-level generation order without canonical-order supervision. Our key observation is that predicting variables from randomly sampled reveal prefixes produces recurring attention patterns in the backbone that provide a model-dependent signal of predictive dependencies. We aggregate this signal into a reciprocal dependency graph and use a spectral teacher to derive continuous generation priorities. A lightweight OrderMLP integrated into the GPT backbone learns to predict these priorities from attention, incorporating order learning into the architecture within a single training run. Training gradually shifts toward the learned order, which is then frozen for subsequent autoregressive training and generation. The same mechanism adapts across modalities: adaptively it recovers near-L2R dependency structure in language, learns anatomically organized factorizations on human pose, and discovers a factorization on tabular data that places statistically and semantically related fields nearby, while improving downstream modeling metrics across all domains. The code is available at https://github.com/Chenhe-yang/OrderGPT/.
Chenhe Yang, Yuhuan Lyu, Tianyang Hu
SAGA Lab, The Chinese University of Hong Kong, Shenzhen
Variable-order Markov models preserve local symbolic syntax by adapting context length, but long continuations can enter recurring high-order "tunnels": repeated suffixes, locally periodic passages, or copied fragments longer than the formal Markov order. This paper introduces signed pattern control for variable-order Markov generation with BP-Regular sampling. A weighted recurrence automaton computes an activation R for a chosen family of target patterns, and belief propagation samples exactly from P_beta(x) proportional to P_0(x) exp(beta R(x)). Negative coupling makes the target patterns costly during sampling; positive coupling rewards the same patterns and turns them into controlled attractors. The target family may be mined online from overactive generated material, supplied by a score or style vocabulary, or designed as an experimental probe. The main experiments use the online homeostatic case, choosing patterns that become overactive in the sampling history. On six duration-bearing monophonic sources, including Bach and Telemann material, the negative branch reduces generated 8-gram self-reuse, increases the effective number of generated 8-grams, and increases coverage of training-supported 4-gram contexts while preserving substantial lower-order support. A pitch-sequence replication on five Weimar Jazz Database solos gives the same anti-reuse signature outside Baroque material. The same signed mechanism also provides a positive branch for probing attractor basins, phase transitions, and hysteresis in the underlying variable-order model.
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.