Insertion Language Models: Sequence Generation with Arbitrary-Position Insertions

Dhruvesh Patel ♢ Aishwarya Sahoo ♢ Avinash Amballa ♢ Tahira Naseem ♡ Tim G. J. Rudner ♠ Andrew McCallum ♢ · 2025

Read Insertion Language Models: Sequence Generation with Arbitrary-Position Insertions by Dhruvesh Patel ♢ Aishwarya Sahoo ♢ Avinash Amballa ♢ Tahira Naseem ♡ Tim G. J. Rudner ♠ Andrew McCallum ♢ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-05755.txt.

Introduction

Most text models write one word at a time, strictly from left to right. Dhruvesh Patel and five co-authors offer a new kind of model in 2025 that builds text by adding words at any spot in a line. Their method, named Insertion Language Models, picks both the place and the word to add at each step.

Writing in any order lets the model keep strong links between words that sit far apart. It can also fill gaps of any length, a task that fixed-order and masked models handle less well. In tests on plan tasks, the new model beat both older kinds. On plain text writing it matched the left-to-right kind, with more freedom in how text takes shape.

Catalog record

CREATORDhruvesh Patel ♢ Aishwarya Sahoo ♢ Avinash Amballa ♢ Tahira Naseem ♡ Tim G. J. Rudner ♠ Andrew McCallum ♢
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-05755

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Insertion Language Models: Sequence Generation with Arbitrary-Position Insertions Dhruvesh Patel ♢ Aishwarya Sahoo ♢ Avinash Amballa ♢ Tahira Naseem ♡ Tim G. J. Rudner ♠ Andrew McCallum ♢ 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. 1 Introduction Autoregressive models (ARMs), which predict subsequent tokens one-by-one in a “left-to-right” fashion, have achieved significant success in modeling natural language [ Bro+20 , GDJ+24 ] . Their simplicity makes them easy to train and has enabled a rapid increase in model sizes [ Kap+20 ] . However, ARMs have several fundamental limitations. For example, they have fallen short on tasks that require complex reasoning and long-horizon planning [ Bub+23 , Val+24 , Dzi+23 ] , and they struggle to accurately model sequences that require satisfying sophisticated constraints [ Sun+23 ] . Recently, Masked Diffusion Models (MDMs) have been shown to perform on par with ARMs while overcoming some of their limitations [ Ye+25 , Sah+24 , LME24 , Nie+24 , Nie+25 ] . However, although MDMs address some of the limitations of ARMs, departing from strictly left-to-right generation introduces new challenges. First, unmasking multiple tokens simultaneously during generation can violate token dependencies. For example, in the sentence “The chef added <mask> to the dessert to make it <mask>.” if both the <mask> tokens are filled simultaneously, it can lead to a sentence that does not make sense, for example, “The chef added sugar to the dessert to make it healthier .” However, if the tokens are filled sequentially, more appropriate sentences are generated, for example, “The chef added sugar to the dessert to make it sweeter .” or “The chef added berries to the dessert to make it healthier .” Second, reliance on the number of masked tokens in the input reduces a model’s usefulness when performing arbitrary infilling. For example, when presented with the sentence “The conference, <mask> was postponed.” the model cannot generate “The conference, originally planned for March , was postponed.” as the input has only one mask. Figure 1 : ARMs (top) generate variable-length sequences in a fixed left-to-right order. MDMs (middle) can add tokens in arbitrary order but require a fixed number of tokens to be masked. ILMs (bottom) generate sequences of arbitrary lengths in arbitrary order by inserting tokens. To overcome these limitations, we introduce Insertion Language Models (ILMs), which use a denoising objective that involves dropping some tokens from the input sequence and learning to predict the missing tokens sequentially, one at a time. Unfortunately, estimates of the naive infilling denoising objective can have extremely high variance, which in turn can make training infeasible. To address this issue and allow efficient training, we introduce an approximate denoising training objective and a tailored parameterization of the denoising network. The key difference between ILMs and MDMs is that in ILMs, the dropped tokens are completely removed from the input sequence and are generated one at a time in reverse, whereas in MDMs, the dropped tokens are replaced by a < mask > token. In our empirical evaluation, using the synthetic task of generating paths on a star graph [ BN24 ] , we find that ILMs can consistently generate the correct path even when ARMs and MDMs struggle—especially when the paths have variable length. We also find that ILMs outperform ARMs and MDMs on the difficult constraint satisfaction task of solving Zebra Puzzles [ Sha+24 ] . By training ILMs on small text corpora such as LM1B and TinyStories, we find that ILMs perform slightly better than MDMs on an unconditional text generation task (measured using generative perplexity under Llama 3.2, and Prometheus LLM judge) and are competitive with ARMs. We also demonstrate the effectiveness of ILMs on infilling arbitrary length sequences in a zero-shot manner. To summarize, our main contributions are as follows: 1. We propose Insertion Language Models (ILMs), which learn to insert tokens at arbitrary positions in a sequence and are able to handle strong dependencies between tokens. 2. We present a neural network parameterization and a simple denoising objective that enable the training of ILMs. 3. We conduct an empirical evaluation of the proposed method and find that ILMs outperform autoregressive and masked diffusion models on common planning tasks and are competitive with ARMs and MDMs on text generation tasks while offering greater flexibility on arbitrary-length text infilling compared to MDMs. 2 Preliminaries Notation. Capital letters are used to denote random variables (e.g. \bm{X} ) and the corresponding lowercase letters are used to denote their values (e.g. \bm{x} ). Boldface is reserved for non-scalars (vectors, matrices, etc.). Double square brackets are used to denote the set of natural numbers up to a specific number, that is, [\![n]\!]=\{1,2,\ldots,n\} . The components of a non-scalar quantity are denoted using superscripts and subscript time index of a stochastic processes whenever applicable. 2.1 Masked Diffusion Models Let {\mathbb{V}} denote the token vocabulary, a finite set, and p_{\textnormal{data}} be probability mass function on the set of sequences {\mathbb{V}}^{L} . Assume that there is an arbitrary and fixed ordering on set {\mathbb{V}} , using which we can use {\bm{e}}_{x} to denote the indicator vector that is one at the index of token x and zero otherwise. Furthermore, assume that the set {\mathbb{V}} contains a special token, whose probability under p_{\textnormal{data}} is 0 , called the mask token denoted as m . The training objective for MDMs [ Shi+24 , Sah+24 ] can be written as the data expectation (i.e., {\bm{x}}_{0}\sim p_{\textnormal{data}} ) of the following loss: \displaystyle\mathcal{L}_{\theta}({\bm{x}}_{0})=\mathop{\mathbb{E}}_{{\bm{x}}_{t}\sim q_{t|0}(\cdot|{\bm{x}}_{0})}\left[\int_{0}^{1}\frac{\alpha_{t}^{\prime}}{1-\alpha_{t}}\sum_{i=1}^{L}\delta(x_{t}^{i},m)\log[\mu^{\textnormal{mdlm}}_{\theta}({\bm{x}}_{t},t)]^{i}_{x_{0}^{i}}\mathop{}\!{d}t\right], where \displaystyle q_{t|0}({\bm{x}}_{t}\;|\;{\bm{x}}_{0})=\prod_{i=1}^{L}\textnormal{Cat}\left(\alpha_{t}{\bm{e}}_{x_{0}^{i}}+(1-\alpha_{t}){\bm{e}}_{m}\right) (1) is the transition probability of the noising process, and \mu^{\textnormal{mdlm}}_{\theta}:{\mathbb{V}}^{L}\times[0,1]\to{(\Delta^{|{\mathbb{V}}|-1})}^{L} is the learned parametric denoiser that takes in the current noisy sequence and produces a categorical probability distribution over the vocabulary at each sequence position. Here \Delta^{|{\mathbb{V}}|-1} denotes a categorical probability distribution over {\mathbb{V}} , and [\mu^{\textnormal{mdlm}}_{\theta}({\bm{x}}_{t},t)]^{i}_{j} denotes the probability of j -th token from the vocabulary at i -th sequence position. Typically, the noising function \alpha_{t} is a monotonically decreasing function defined

Read the complete text