TIGS: An Inference Algorithm for Text Infilling with Gradient Search

Dayiheng Liu, Jie Fu, Pengfei Liu, Jiancheng Lv

Abstract

Text infilling is defined as a task for filling in the missing part of a sentence or paragraph, which is suitable for many real-world natural language generation scenarios. However, given a well-trained sequential generative model, generating missing symbols conditioned on the context is challenging for existing greedy approximate inference algorithms. In this paper, we propose an iterative inference algorithm based on gradient search, which is the first inference algorithm that can be broadly applied to any neural sequence generative models for text infilling tasks. We compare the proposed method with strong baselines on three text infilling tasks with various mask ratios and different mask strategies. The results show that our proposed method is effective and efficient for fill-in-the-blank tasks, consistently outperforming all baselines.

Introduction: The Challenge of Unidirectional Generation

Text infilling—the task of restoring missing words within a sentence—is a cornerstone of natural language processing, essential for applications ranging from document restoration to dialogue generation. Despite the power of modern neural sequence models like Seq2Seq, they are predominantly "unidirectional," generating text from left to right.

When these models encounter a "blank" in the middle of a sentence, standard inference techniques like Beam Search struggle because they only consider the words preceding the blank. This often leads to "clashing" text, where the generated words are locally coherent with the start of the sentence but grammatically or semantically incompatible with the words that follow.

Comparison of standard inference methods showing how unidirectional models fail to maintain global coherence.

To address this, researchers typically train specialized models on massive "fill-in-the-blank" datasets. TIGS (Text Infilling with Gradient Search) offers a different path: a way to use existing, well-trained models for infilling without the prohibitive cost of retraining.

The TIGS Algorithm: Optimization in Embedding Space

The core innovation of TIGS is shifting the search for the optimal word from a discrete dictionary to a continuous mathematical space. Instead of picking words one by one, TIGS treats the missing words as parameterized vectors in the model's embedding space.

The algorithm employs an iterative two-step process:

  1. The O-step (Optimization): The model's weights remain fixed while the algorithm uses gradient descent to update the vectors representing the blanks. The objective is to minimize the Negative Log-Likelihood (NLL) of the entire sequence. Because the loss is calculated over the whole sentence, the gradient carries information from both the preceding and succeeding context.
  2. The P-step (Projection): Since raw vectors do not correspond to discrete words, the algorithm "projects" them back to the vocabulary. It identifies the $K$ nearest words in the embedding space (typically the top 1% of the vocabulary) and selects the one that minimizes the sequence's NLL.
The O-step: Updating parameterized vectors in the continuous word embedding space using gradients.

This process is iterative, similar to Gibbs sampling: it refines one blank at a time while keeping others fixed, repeating until the sentence converges.

Experimental Evaluation

The researchers evaluated TIGS across three distinct datasets to test its versatility:

  • DailyDialog: Focused on multi-turn dialogue and conversation templates.
  • Chinese Acrostic Poetry: A dataset of four-line poems requiring the model to fill blanks in the final lines.
  • Amazon Product Reviews (APRC): An unconditional infilling task involving the restoration of missing parts of product reviews.

For each dataset, the team tested "Random" masking (scattered words) and "Middle" masking (continuous blocks) at ratios of 25%, 50%, and 75%.

Key Results and Insights

TIGS consistently outperformed both standard inference baselines and specialized "trained-to-fill" models.

  • Quantitative Performance: Across all datasets and mask ratios, TIGS achieved the lowest NLL and the highest BLEU scores. It proved particularly robust at high mask ratios (75%), where context is sparse.
  • Qualitative Human Evaluation: In human preference tests, TIGS was ranked significantly higher than competitors. In the Dialog task, for instance, TIGS received a preference score of 3.226, more than double that of Bidirectional Beam Search (BiBS).
  • Inference-Only Versatility: Because TIGS is an inference algorithm rather than a model architecture, it can be applied to any state-of-the-art model (e.g., for translation or summarization) to enable infilling capabilities immediately.

Limitations and Future Work

While TIGS bridges a significant gap, it introduces certain trade-offs. The iterative nature of gradient search makes it computationally more expensive than a single-pass unidirectional decoder, though this can be mitigated with GPU acceleration. Additionally, the current version assumes the length of the missing segment is known. For unknown lengths, the algorithm must be run across multiple length hypotheses, increasing processing time. Future work may focus on optimizing these computational requirements and refining the projection step for even more complex embedding spaces.

Summary updated

Abstract

Text infilling is defined as a task for filling in the missing part of a sentence or paragraph, which is suitable for many real-world natural language generation scenarios. However, given a well-trained sequential generative model, generating missing symbols conditioned on the context is challenging for existing greedy approximate inference algorithms. In this paper, we propose an iterative inference algorithm based on gradient search, which is the first inference algorithm that can be broadly applied to any neural sequence generative models for text infilling tasks. We compare the proposed method with strong baselines on three text infilling tasks with various mask ratios and different mask strategies. The results show that our proposed method is effective and efficient for fill-in-the-blank tasks, consistently outperforming all baselines.
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