TIGS: An Inference Algorithm for Text Infilling with Gradient Search

Dayiheng Liu, Jie Fu, Pengfei Liu, Jiancheng Lv

Abstract

Text infilling aims at filling in the missing part of a sentence or paragraph, which has been applied to a variety of real-world natural language generation scenarios. Given a well-trained sequential generative model, it is challenging for its unidirectional decoder to generate missing symbols conditioned on the past and future information around the missing part. In this paper, we propose an iterative inference algorithm based on gradient search, which could be the first inference algorithm that can be broadly applied to any neural sequence generative models for text infilling tasks. Extensive experimental comparisons show the effectiveness and efficiency of the proposed method on three different text infilling tasks with various mask ratios and different mask strategies, comparing with five state-of-the-art methods.

Introduction

Text infilling—the task of predicting missing words within a sentence—is a critical component of many natural language generation (NLG) applications. However, standard language models are typically unidirectional, generating text from left to right. This architecture presents a significant challenge for infilling: the model can account for the preceding context but remains "blind" to the text following the blank.

The Challenge of Unidirectional Infilling

When a unidirectional model encounters a blank, it generates tokens based on the past. However, without a mechanism to "look ahead," the generated segment often contradicts the subsequent fixed text. This leads to "clashing" at the boundaries, where the sentence becomes ungrammatical or logically inconsistent.

Comparison of standard beam search methods against ground truth, demonstrating the "clashing" problem at the boundary of generated text and future context.

As shown in the figure above, standard Seq2seq models using either left-to-right or right-to-left beam search fail to produce the coherent ground truth. The forward model produces a nonsensical "let's for" sequence, while the backward model creates an awkward "that not" transition. These failures highlight the need for an inference method that can harmonize both past and future contexts.

The TIGS Algorithm

To address these limitations without requiring model retraining or architectural changes, we propose TIGS (Text Infilling with Gradient Search). TIGS is a "plug-and-play" inference algorithm that treats word selection as a continuous optimization problem.

The algorithm employs an iterative two-step process:

  1. O-step (Optimization): The model parameters remain frozen. The tokens in the blanks are represented as parameterized vectors in the embedding space. Using Nesterov momentum gradient descent, TIGS updates these vectors to minimize the Negative Log-Likelihood (NLL) of the entire sequence. An L2 penalty ensures these vectors remain near the valid word embedding manifold.
  2. P-step (Projection): The continuous vectors are mapped back to discrete tokens. TIGS identifies the top-K nearest neighbors and selects the candidate that minimizes the global NLL.

This cycle repeats, allowing the "future" context to propagate signals back to the blank via gradients, effectively bridging the gap that unidirectional models cannot cross.

Experimental Evaluation

We evaluated TIGS across three diverse datasets: DailyDialog (multi-turn dialogue), Chinese Poetry (acrostic generation), and Amazon Product Reviews (unconditional infilling). We tested various mask ratios (25%, 50%, and 75%) and strategies.

Key Results

  • Quantitative Performance: TIGS consistently achieved the lowest NLL across all datasets and mask ratios, outperforming baselines like BiRNN-GSN and BiBS in BLEU scores.
  • Qualitative Fluency: Human evaluations confirmed that TIGS produces more fluent and logically consistent sentences compared to unidirectional beam search, which often fails at the "seam" of the infill.
  • Robustness: TIGS maintained high performance even at a 75% mask ratio, where other model-based approaches struggled to reconstruct the underlying template.

Conclusion

TIGS demonstrates that the knowledge required for high-quality text infilling is already present in standard generative models. By using gradient search during inference, we can extract this knowledge to produce contextually aware results without the need for specialized training. While the iterative nature of the algorithm introduces higher computational costs compared to single-pass methods, its versatility and performance make it a powerful tool for complex NLG tasks.

Summary updated

Abstract

Text infilling aims at filling in the missing part of a sentence or paragraph, which has been applied to a variety of real-world natural language generation scenarios. Given a well-trained sequential generative model, it is challenging for its unidirectional decoder to generate missing symbols conditioned on the past and future information around the missing part. In this paper, we propose an iterative inference algorithm based on gradient search, which could be the first inference algorithm that can be broadly applied to any neural sequence generative models for text infilling tasks. Extensive experimental comparisons show the effectiveness and efficiency of the proposed method on three different text infilling tasks with various mask ratios and different mask strategies, comparing with five state-of-the-art methods.
BibTeX
@inproceedings{liu2019tigs,
  author = {Dayiheng Liu and Jie Fu and Pengfei Liu and Jiancheng Lv},
  title = {{TIGS: An Inference Algorithm for Text Infilling with Gradient Search}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  url = {https://openreview.net/forum?id=xyezanpZq2},
}
Figure