Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation

• URL: http://arxiv.org/abs/2605.07839v1
• Date: Fri, 08 May 2026 15:05:58 GMT
• Title: Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation
• Abstract summary: We extend existing exact methods to handle regular constraints with belief propagation for first-order Markov chains.<n>A variable-order extension identifies the state space on which the existing BP-regular machinery must be run when the generator is a variableorder/backoff model.<n>For a fixed trained context graph and automaton inference is linear in the sequence; in general it is sparse in the number of reachable product edges.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• A Compositional Theory of Causally Masked Transformers [50.88598486616582]
  We develop a formalization that derives expressivity directly from the model's implemented dynamics.<n>Each attention head updates its own state independently within a layer.<n>A modified form of soft attention supports irreversible, checklist-like state.
  arXiv  Detail & Related papers  (2026-07-29T14:47:19Z)
• Attractive and Repulsive Pattern Control in Sequence Generation [0.0]
  This paper introduces signed pattern control for variable-order Markov generation with BP-Regular sampling.<n>A weighted recurrence automaton computes an activation R for a chosen family of target patterns.<n>Negative coupling makes the target patterns costly during sampling; positive coupling rewards the same patterns and turns them into controlled attractors.
  arXiv  Detail & Related papers  (2026-06-19T10:20:58Z)
• Variational Learning for Insertion-based Generation [50.15012125719375]
  We introduce a probabilistic framework for learning insertion order in variable-length insertion models.<n>We propose the Insertion Process (IP), a generative model that jointly learns where to insert, what to insert, and when to terminate.
  arXiv  Detail & Related papers  (2026-06-01T11:59:46Z)
• Primal-Dual Guided Decoding for Constrained Discrete Diffusion [5.219025684249083]
  We propose primal-dual guided decoding, an inference-time method that formulates constrained generation as a KL-regularised optimisation problem.<n>At each denoising step, the method modifies token logits through an additive, constraint-dependent bias, with multipliers updated by mirror descent based on constraint violation.<n>We evaluate our approach on topical text generation, molecular design, and music playlist generation, showing that a single algorithm instantiated via domain-specific scoring functions improves constraint satisfaction while preserving relevant domain-specific quality metrics.
  arXiv  Detail & Related papers  (2026-05-10T20:55:19Z)
• LatticeBridge: Rare-Event Sequential Inference for Faithful Structured Sequence Synthesis [0.5729426778193398]
  Structured sequence generation often requires a model to satisfy several input-derived constraints in a single output.<n>LatticeBridge combines a compact prefix language model, instance-compiled surface automata, and a twisted sequential Monte Carlo (SMC) decoder.<n>LatticeBridge improves exact anchor satisfaction and mean anchor coverage over greedy, beam-filtered, and best-of-k ancestral baselines.
  arXiv  Detail & Related papers  (2026-04-22T09:24:25Z)
• Thinking Out of Order: When Output Order Stops Reflecting Reasoning Order in Diffusion Language Models [26.550350205533217]
  Masked diffusion language models (MDLMs) iteratively refine all tokens in parallel to decouple order from output structure.<n>We present evidence that MDLMs achieve order robustness by stabilizing simpler tokens earlier in the diffusion process than complex ones.
  arXiv  Detail & Related papers  (2026-01-29T17:40:58Z)
• Zonkey: A Hierarchical Diffusion Language Model with Differentiable Tokenization and Probabilistic Attention [0.0]
  Zonkey is a hierarchical diffusion model that addresses limitations through a fully trainable pipeline from raw characters to document-level representations.<n>At its core is a differentiable tokenizer that learns probabilistic beginning-of-sequence (BOS) decisions.<n>Zonkey generates coherent, variable-length text from noise, demonstrating emergent hierarchies.
  arXiv  Detail & Related papers  (2026-01-29T14:17:37Z)
• Learning Tractable Distributions Of Language Model Continuations [40.95717348276321]
  We find that tractable surrogates such as hidden Markov models (HMMs) approximate the distribution over continuations and adjust the model's next-token logits at decoding time.<n>We propose Learning to Look Ahead (LTLA), a hybrid approach that pairs the same base language model for rich prefix encoding with a fixed tractable surrogate model that computes exact continuation probabilities.
  arXiv  Detail & Related papers  (2025-11-20T05:17:19Z)
• Higher-order Linear Attention [59.92962330635185]
  quadratic cost of scaled dot-product attention is a central obstacle to scaling autoregressive language models to long contexts.<n>We introduce Higher-order Linear Attention (HLA), a causal, streaming mechanism that realizes higher interactions via compact prefix sufficient statistics.
  arXiv  Detail & Related papers  (2025-10-31T07:54:37Z)
• Bridging Generative and Discriminative Noisy-Label Learning via Direction-Agnostic EM Formulation [26.430145104987982]
  We propose a single-stage, EM-style framework for generative noisy-label learning.<n>Our method achieves state-of-the-art accuracy, lower transition-matrix estimation error, and substantially less training compute than current generative and discriminative baselines.
  arXiv  Detail & Related papers  (2023-08-02T14:48:25Z)
• Sequential Recommendation via Stochastic Self-Attention [68.52192964559829]
  Transformer-based approaches embed items as vectors and use dot-product self-attention to measure the relationship between items. We propose a novel textbfSTOchastic textbfSelf-textbfAttention(STOSA) to overcome these issues. We devise a novel Wasserstein Self-Attention module to characterize item-item position-wise relationships in sequences.
  arXiv  Detail & Related papers  (2022-01-16T12:38:45Z)
• Discovering Non-monotonic Autoregressive Orderings with Variational Inference [67.27561153666211]
  We develop an unsupervised parallelizable learner that discovers high-quality generation orders purely from training data. We implement the encoder as a Transformer with non-causal attention that outputs permutations in one forward pass. Empirical results in language modeling tasks demonstrate that our method is context-aware and discovers orderings that are competitive with or even better than fixed orders.
  arXiv  Detail & Related papers  (2021-10-27T16:08:09Z)
• Structured Reordering for Modeling Latent Alignments in Sequence Transduction [86.94309120789396]
  We present an efficient dynamic programming algorithm performing exact marginal inference of separable permutations. The resulting seq2seq model exhibits better systematic generalization than standard models on synthetic problems and NLP tasks.
  arXiv  Detail & Related papers  (2021-06-06T21:53:54Z)
• Conditional Hybrid GAN for Sequence Generation [56.67961004064029]
  We propose a novel conditional hybrid GAN (C-Hybrid-GAN) to solve this issue. We exploit the Gumbel-Softmax technique to approximate the distribution of discrete-valued sequences. We demonstrate that the proposed C-Hybrid-GAN outperforms the existing methods in context-conditioned discrete-valued sequence generation.
  arXiv  Detail & Related papers  (2020-09-18T03:52:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.