TIGS: An Inference Algorithm for Text Infilling with Gradient Search

1 Introduction

• Text infilling has applications including image caption completion, constrained generation, document reconstruction, acrostic poetry, and text representation learning.The examples span both generation and reconstruction settings.Source: §1 · p. 1
• Unidirectional beam search conditions each output on previous outputs, although infilled words must fit both past and future context.The paper identifies this mismatch as a challenge when applying well-trained generative models to text infilling.Source: §1 · p. 1
• Earlier infilling approaches either train models for the task or rely on bidirectional decoders; the latter can make unrealistic assumptions and do not cover unidirectional decoders.The paper notes that trained-to-fill approaches require fill-in-the-blank data, while existing inference methods are limited to bidirectional structures.Source: §1 · pp. 1–2
• TIGS searches for infilled words using gradient information and is presented as applicable to sequence generative models without model modification or training.The authors describe it as the first such broadly applicable inference algorithm, to their knowledge.Source: §1 · p. 2
• TIGS represents each blank with a parameterized vector initialized from a valid token embedding and minimizes the complete sequence’s negative log-likelihood.The search objective is to find the words to infill by minimizing the NLL of the complete sequence.Source: §1 · p. 2
• TIGS alternates gradient optimization of blank vectors with heuristic projection to valid tokens until convergence.The O-step optimizes blank vectors while other model parameters are fixed; the P-step discretizes them.Source: §1 · p. 2
• Comparisons with five state-of-the-art methods across three text-infilling tasks report TIGS as effective and efficient.The introduction summarizes the experimental comparisons as showing effectiveness and efficiency.Source: §1 · p. 2

2 Related Works

• Task-specific infilling models such as NADE, MaskGAN, and Zhu et al.’s self-attention model require fill-in-the-blank training data and are limited to unconditional infilling.The paper contrasts these models with TIGS, which requires no model modification or additional training and supports conditional and unconditional tasks.Source: §2 · pp. 2–3
• TIGS is presented as an inference alternative that needs neither model modification nor training and applies to conditional and unconditional seq2seq infilling.The contrast is with task-specific models that require training and are described as unconditional-only.Source: §2 · pp. 2–3
• Inference methods such as GSN and BiBS use bidirectional RNNs, but their assumptions may fail in practice and they do not apply to unidirectional decoders.The paper says TIGS decouples from these assumptions and can be applied to unidirectional decoders.Source: §2 · p. 3

3 Preliminary

• The paper uses RNN-based models as a showcase, while noting that gradient information could also work with architectures such as Transformers and convolutional sequence models.The authors choose RNN-based models because of their popularity and the RNN focus of related work.Source: §3 · p. 3

3.1 RNN-based Seq2Seq Model

• A seq2seq model encodes the input and uses a decoder with attention to predict each next token from previous outputs and the input.Exact inference is NP-hard because the number of possible sequences grows as |V|^m, so approximate decoding is commonly used.Source: §3.1 · p. 3

3.2 Problem Definition

• The problem definition permits arbitrary numbers and locations of blanks and seeks infilled text that considers sentence-wide structure and the conditioning input.The target sequence yB marks the missing positions, and the task is to fill them given input x.Source: §3.2 · pp. 3–4

4 Methodology

• TIGS treats blanks as parameterized word embeddings, uses gradients to reduce complete-sequence NLL, and projects the vectors into valid words without changing the trained model.The model parameters remain fixed while the blank vectors are optimized.Source: §4 · p. 4
• TIGS updates one blank at a time while holding the others fixed, alternating optimization and projection until convergence or the maximum number of rounds.This avoids potentially incoherent combinations from simultaneous discretization; unknown-length blanks can be handled by trying a range of lengths and ranking the solutions.Source: §4 · pp. 4–5
• An L2 penalty keeps optimized blank vectors close to the embedding space, while an additional penalty toward the nearest word embedding showed no obvious improvement.Direct NLL optimization can produce vectors unlike feasible word embeddings, whose nearest word embeddings may be far away.Source: §4 · p. 5
• Nesterov optimization performed better than other tested optimizers for updating blank vectors, and Euclidean distance performed slightly better than cosine distance for projection.These are reported experimental choices for the update optimizer and distance metric.Source: §4 · p. 5
• Projection forms a shortlist of K nearest word embeddings and selects the candidate with the lowest NLL; setting K to 1% of the vocabulary worked well.The K-nearest shortlist narrows the search before choosing a valid token.Source: §4 · p. 5
• TIGS requires mKT|B| RNN steps, compared with mT|B| BiRNN steps for GSN and 2mKT RNN steps for BiBS.The authors note TIGS can be optimized with GPUs.Source: §4 · p. 5

5.1 Datasets

• The three tasks are DailyDialog replies, Chinese acrostic poetry, and unconditional Amazon product-review infilling, each tested on 5,000 samples.Each task has middle and random masking strategies at 25%, 50%, and 75% removal rates.Source: §5.1 · pp. 5–6

5.2 Baselines

• Baselines include directional and bidirectional inference methods, plus Mask-Seq2Seq and Mask-Self-attn trained on fill-in-the-blank data.Most methods and TIGS use the same well-trained seq2seq model; BiRNN-GSN and BiRNN-BiBS use a BiRNN decoder.Source: §5.2 · p. 6

5.4 Results

• TIGS achieves the lowest NLL in all task cases and the highest BLEU in most conditional cases, with competitive BLEU on unconditional APRC.Table 1 reports BLEU and NLL; TIGS also compares favorably with Mask-Self-attn on APRC.Source: Table 1 · p. 7, §5.4 · p. 8

5.3 Metrics

• Evaluation uses sentence-level BLEU and model-based NLL; BLEU can undervalue reasonable alternatives when only one ground-truth fill is available.This issue is described as more severe for unconditional APRC, where there are fewer restrictions and more possible fills.Source: §5.3 · pp. 7–8

5.5 Human Evaluation

• In human rankings of generations from four methods, TIGS consistently outperforms all baselines.The evaluation uses 50 randomly selected test instances and 10 evaluators; rankings assign scores from 4 to 1.Source: Table 2 · p. 8, §5.5 · p. 8

5.6 Samples and Analysis

• Unidirectional Seq2Seq outputs often lack fluency or clash with surrounding words because they cannot reason about past and future context simultaneously.Forward completions can clash with words after a blank, while backward completions can clash with words before it.Source: §5.6 · p. 8
• BiRNN-BiBS’s product-of-directions assumption can yield non-smooth fills and more <unk> tokens than other methods.The paper illustrates a non-smooth “i, to listen to the music” completion, where the local directional probabilities favor “to.”Source: §5.6 · p. 9
• Mask-Seq2Seq and Mask-Self-attn show limited generalization, especially on conditional tasks; TIGS and BiRNN-GSN reason over both contexts without unrealistic assumptions.In Dialog, beam-search Mask-Self-attn and Mask-Seq2Seq fail to reconstruct the template in 21% and 16% of samples, respectively; TIGS uses gradient-based inference rather than a BiRNN decoder.Source: §5.6 · p. 9

• The proposed method consistently outperforms all baselines on three text-infilling tasks.The comparison covers various mask ratios and different mask strategies.Source: §6 · p. 9
• The inference algorithm requires no modification or training of the model and is broadly applicable to sequence generative models.Source: §6 · p. 9
• The proposed approach is reported to be effective and efficient for fill-in-the-blank tasks.Source: §6 · p. 9