Flexible-length Text Infilling for Discrete Diffusion Models

Andrew Zhang, Anushka Sivakumar, Chia-Wei Tang, Chris ThomasEMNLP 2025

TL;DR

This paper introduces DDOT, a novel discrete diffusion model that enables flexible-length text infilling by jointly learning to denoise token values and their positions. By employing optimal transport coupling, DDOT overcomes the limitations of previous diffusion models, achieving state-of-the-art performance on text infilling tasks while improving training efficiency.

What Problem Does This Paper Address?

Autoregressive (AR) models, while effective for text generation, suffer from sequential sampling, lack bidirectional context, and are limited to left-to-right completion. Discrete diffusion models offer advantages like parallel generation and bidirectional context, but a significant limitation has been their inability to perform flexible-length or flexible-position text infilling without access to ground-truth positional data. This means they couldn't generate text that differs in length from the masked region or place it precisely without knowing the exact target positions beforehand. This paper addresses this gap by enabling discrete diffusion models to dynamically adjust the positions and lengths of infilled text segments.

Methods

The core innovation of DDOT lies in its ability to diffuse both token values and token positions simultaneously.

  • Token Value Diffusion: This part leverages a Score Entropy Discrete Diffusion (SEDD) framework, which models text as a sequence of discrete states and learns to denoise corrupted sequences.
  • Continuous Position Diffusion: DDOT introduces a diffusion process for token positions. It partitions positions into prompt, response, and pad tokens and models their movement. To ensure stable and predictable position updates, it uses straight, noise-free interpolation for positions.
  • Optimal Transport (OT) Coupling: This is the key to flexible infilling. Instead of naive position diffusion, which can lead to combinatorial explosions and invalid results, DDOT uses sample-level OT coupling. This coupling is applied within the prompt set and within the response set separately. This approach:
  • Reduces Permutation Space: By enforcing order-preserving, non-crossing trajectories within each set, it drastically shrinks the search space for valid permutations.
  • Preserves Supervision Signal: It ensures that the relative ordering of prompt tokens is maintained throughout the diffusion process, providing a stable learning signal.
  • Prevents Invalid Permutations: Crucially, it guarantees that prompt tokens are not reordered, which is essential for valid infilling.
  • Training Objective: DDOT jointly optimizes a token loss (from SEDD) and a position loss (MSE between predicted and target positions), weighted by a hyperparameter $\lambda$.

Datasets

The paper evaluates DDOT on the following datasets:

  • One-Billion-Word: Used for both block and random masking tasks.
  • Yelp: Also used for block and random masking tasks.
  • CodeParrot (Python subset): Used for block masking.

These datasets are standard for lexically constrained generation tasks, where a small number of keywords must be infilled to form coherent sentences.

Key Insights and Ideas

  • Joint Denoising of Values and Positions is Crucial: The paper demonstrates that simply diffusing positions isn't enough; it needs to be coupled with token value diffusion and carefully constrained.
  • Per-Set OT Coupling is a Game-Changer: Applying OT coupling independently to prompt and response sets, rather than globally, significantly simplifies the problem and leads to much more stable and accurate infilling. This is a key algorithmic insight.
  • Order Preservation is Paramount: The success of OT coupling hinges on its ability to maintain the relative order of tokens, which is vital for semantic coherence and preventing invalid outputs.
  • Uniform Position Initialization (DDOT-U) is Better: DDOT-U, which uses uniform grids for terminal positions, consistently outperforms DDOT-R (random initialization), suggesting that structured initialization helps avoid issues like pad token clustering.

Key Results

  • State-of-the-Art Performance: DDOT outperforms naive diffusion baselines and achieves performance on par with state-of-the-art non-autoregressive (NAR) models on text infilling benchmarks like One-Billion-Word and Yelp.
  • Improved Success Rate (SR): DDOT consistently achieves higher SR than diffusion baselines, indicating its ability to generate valid infills that respect prompt token order, especially as the number of prompt tokens increases.
  • Efficiency: DDOT is faster than Left Context (LC) baselines and competitive with Position Prediction (PoP) baselines, while achieving superior BLEU scores. The OT computation is efficient and can be precomputed.
  • Scalability: DDOT scales well to longer sequences and maintains high SR.

Limitations and Future Work

  • Diffusion Model Performance Gap: DDOT, like other discrete diffusion models, still lags behind autoregressive models in overall performance. This is attributed to the field of discrete diffusion for text being relatively new.
  • KV Cache Limitation: Similar to other diffusion models, DDOT cannot use a KV cache for storing previous activations, which is a limitation inherited from the backbone architecture.
  • Future Work: The authors suggest further exploration of the OT coupling mechanism and its application to other discrete diffusion tasks. They also plan to release their code artifacts.

Summary updated

BibTeX
@inproceedings{zhang2025flexible,
  author = {Andrew Zhang and Anushka Sivakumar and Chia-Wei Tang and Chris Thomas},
  title = {{Flexible-length Text Infilling for Discrete Diffusion Models}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure