Insertion Language Models: Sequence Generation with Arbitrary-Position Insertions

Dhruvesh Patel, Aishwarya Sahoo, Avinash Amballa, Tahira Naseem, Tim G. J. Rudner, Andrew McCallum

UMass Amherst · IBM Research · New York University

Paper arXiv Code

ARMs generate variable-length sequences left to right. MDMs can add tokens in arbitrary order but require a fixed number of masks. ILMs generate sequences of arbitrary lengths in arbitrary order by inserting tokens.

Abstract

Autoregressive models (ARMs), which predict subsequent tokens one-by-one "from left to right," have achieved significant success across a wide range of sequence generation tasks. However, they struggle to accurately represent sequences that require satisfying sophisticated constraints or whose sequential dependencies are better addressed by out-of-order generation. Masked Diffusion Models (MDMs) address some of these limitations, but the process of unmasking multiple tokens simultaneously in MDMs can introduce incoherences, and MDMs cannot handle arbitrary infilling constraints when the number of tokens to be filled in is not known in advance. In this work, we introduce Insertion Language Models (ILMs), which learn to insert tokens at arbitrary positions in a sequence—that is, they select jointly both the position and the vocabulary element to be inserted. By inserting tokens one at a time, ILMs can represent strong dependencies between tokens, and their ability to generate sequences in arbitrary order allows them to accurately model sequences where token dependencies do not follow a left-to-right sequential structure. To train ILMs, we propose a tailored network parameterization and use a simple denoising objective. Our empirical evaluation demonstrates that ILMs outperform both ARMs and MDMs on common planning tasks. Furthermore, we show that ILMs outperform MDMs and perform on par with ARMs in an unconditional text generation task while offering greater flexibility than MDMs in arbitrary-length text infilling.

Cite

@misc{patel2025insertion,
  title={Insertion Language Models: Sequence Generation with Arbitrary-Position Insertions},
  author={Dhruvesh Patel and Aishwarya Sahoo and Avinash Amballa and Tahira Naseem and Tim G. J. Rudner and Andrew McCallum},
  year={2025},
  eprint={2505.05755},
  archivePrefix={arXiv},
  primaryClass={cs.CL}
}