Variational Learning for Insertion-based Generation
This work addresses the problem of non-monotonic sequence generation for domains without a canonical left-to-right structure, offering a method that learns insertion order adaptively.
The paper introduces the Insertion Process (IP), a probabilistic framework for learning insertion order in variable-length generation, which jointly learns where to insert, what to insert, and when to terminate. Experiments on goal-conditioned planning and molecular string generation show that learning insertion order improves modeling quality and generalization.
Non-monotonic sequence generation methods, such as masked diffusion models, provide a flexible alternative to left-to-right autoregressive modeling by allowing tokens to be generated in non-fixed and prescribed orders. Despite their practical advantages, most existing non-monotonic models are order-agnostic and rely on a fixed-length grid, limiting their ability to support variable-length generation and adaptive insertion order. In this work, we introduce a probabilistic framework for learning insertion order in variable-length insertion models. We formalize a bijective correspondence between insertion trajectories and permutations, which enables an exact reparameterization of the data likelihood as a sum over permutations. Building on this result, we propose the Insertion Process (IP), a stochastic generative model that jointly learns where to insert, what to insert, and when to terminate, trained via permutation-based variational inference. Unlike prior fixed-canvas approaches, IP natively supports variable-length generation and learns data-driven preferences over insertion orders. Experiments on goal-conditioned planning and molecular string generation demonstrate that learning insertion order improves both modeling quality and generalization in domains without a canonical left-to-right structure.