Source-linked AI summary
A Simple, Fast Diverse Decoding Algorithm for Neural Generation
Jiwei Li, Will Monroe, Dan Jurafsky
TL;DR
Neural beam search can produce insufficiently diverse candidates, limiting exploration and weakening reranking. The paper modifies beam search with an inter-sibling penalty and adds reinforcement learning to adapt diversity rates per input. Across dialogue, summarization, and translation, diverse decoding helps, especially when reranking is needed, while adaptive diversity provides an additional boost.
Problem
Beam search often produces similar candidates, limiting exploration and reducing the impact of reranking when global or expensive features are applied afterward.
Method
The paper adds an intra-sibling ranking penalty to standard beam search and uses reinforcement learning to select input-specific diversity rates.
Results
Diverse decoding helps across dialogue response generation, abstractive summarization, and machine translation, especially when reranking is needed; DiverseRL yields better generation quality than standard beam search or basic diverse decoding.
Takeaways & Limitations
Diverse decoding is most useful for tasks with highly diverse ground-truth outputs or tasks requiring reranking, while adaptive rates improve the basic approach.
Takeaways & Limitations
Adaptive diversity improves quality at the expense of greater model complexity and training time, and excessive diversity can move decoding too far from beam-search scores.
Abstract
from arXiv · showhide
In this paper, we propose a simple, fast decoding algorithm that fosters diversity in neural generation. The algorithm modifies the standard beam search algorithm by adding an inter-sibling ranking penalty, favoring choosing hypotheses from diverse parents. We evaluate the proposed model on the tasks of dialogue response generation, abstractive summarization and machine translation. We find that diverse decoding helps across all tasks, especially those for which reranking is needed. We further propose a variation that is capable of automatically adjusting its diversity decoding rates for different inputs using reinforcement learning (RL). We observe a further performance boost from this RL technique. This paper includes material from the unpublished script "Mutual Information and Diverse Decoding Improve Neural Machine Translation" (Li and Jurafsky, 2016).
1 Introduction
Beam search often produces insufficiently diverse candidates, limiting exploration and weakening reranking. The paper proposes a simple, fast modification that penalizes sibling hypotheses and favors diverse parent paths.
- Beam-search candidates often differ only by punctuation or minor morphology, with most words overlapping.
- Limited diversity hinders generation when multiple valid outputs exist because the decoder must explore different paths.
- Limited N-best diversity significantly reduces reranking impact when global or expensive features are applied after decoding.
- The proposed decoder adds a sibling-ranking penalty to standard beam search, favoring hypotheses descended from diverse parents.
- The method is designed as a simple, fast change that can support batched GPU decoding.
- Across dialogue response generation, abstractive summarization, and machine translation, diverse decoding is reported to produce better outputs, while reinforcement learning further adjusts diversity rates by input.
2 Related Work
Prior diversity methods address phrase-based translation or use alternative neural decoding strategies. The paper positions its approach as a neural-generation method compatible with batched computation.
- Earlier diversity-promoting methods for translation include lattices, hypergraphs, translation traits, ensemble techniques, and probability-based sampling.
- Existing phrase-based methods are not easily transplanted to neural machine translation because neural decoding requires batched computation.
- Recent neural-generation work explores noisy parallel decoding, diversity-augmented objectives, and stochastic segment-level reranking.
- The paper's reinforcement-learning variant is related to reinforcement-learning approaches applied across several NLP tasks.
3 Diverse Beam Decoding
Standard beam search retains the highest-scoring hypotheses, but this can yield similar N-best lists. Diverse beam decoding changes hypothesis scoring to favor lower-ranked siblings from different parents.
- 3.1 Basics: Neural decoding seeks the target sequence Y* that maximizes its probability given source input X.
- 3.2 Standard Beam Search for N-best lists: Beam search maintains K hypotheses with log-probability scores and expands each parent to construct K × K candidate hypotheses.
- 3.2 Standard Beam Search for N-best lists: Standard beam search selects the top K candidates by score and discards the remainder at each time step.
- 3.2 Standard Beam Search for N-best lists: Because the search retains only a small proportion of candidates, standard N-best lists are often similar and poorly represent the search space.
- 3.3 Generating a Diverse N-best List: Diverse decoding adds γk′ to the score, penalizing lower-ranked hypotheses among siblings descended from the same parent.
- 3.3 Generating a Diverse N-best List: The revised scoring gives more credit to top hypotheses from different ancestors, thereby favoring diverse parents during selection.
4 Automatically Learning Diversity Rate
The paper addresses the limitation of a fixed diversity rate by learning an input-dependent policy that selects diversity rates using reinforcement learning. The selected rate guides diverse decoding, and the policy is trained from final evaluation rewards.
- A fixed diversity rate γ may be suboptimal because the best rate can vary across inputs and excessive diversity can hurt.The paper gives differing sequence-length and image-complexity conditions as examples of when standard or diverse decoding may work better.
- diverseRL learns different γ values for different inputs by automatically adjusting the diversity rate.The policy network maps each input X to a distribution over a discrete set Γ of candidate diversity rates.
- For each input, the policy selects a diversity rate, which is used to produce an N-best list through the proposed diverse decoding algorithm.The final output is chosen by the largest reranking score when reranking is used, or by the largest probability otherwise.
- The policy is optimized with REINFORCE so that diversity-rate choices leading to higher final rewards become more likely.The reward is an evaluation score such as BLEU, and the gradient uses a likelihood-ratio estimate with a baseline.
- Training keeps the pretrained encoder-decoder parameters fixed while sampling diversity rates and decoding each training example, making training extremely time-consuming.For feature-based reranking, feature weights are recalibrated on the development set after every 10,000 instances; training takes roughly 1 day.
5 Experiments
The experiments evaluate diverse decoding across conversational response generation, abstractive summarization, and machine translation. The paper describes the details of these three sequence-generation tasks separately.
- The experiments cover three sequence-generation tasks: conversational response generation, abstractive summarization, and machine translation.
- Conversational response generation is included as one of the evaluated neural generation tasks.
- Abstractive summarization and machine translation are also evaluated as distinct experimental tasks.
5.1 Conversational Response Generation
The conversational response experiments compare standard and diversity-promoting beam search, with and without reranking, across reference-length splits. Diverse decoding improves performance and diversity, with larger reranking gains for long responses; diverseRL wins 62 percent of human comparisons.
- Experimental Setup: The experiments use OpenSubtitles dialogue histories and evaluate natural, short, and long reference-length splits of roughly 2,000 instances each.The natural split is randomly sampled; short references have length no greater than 6, and long references exceed 16.
- Decoding and Reranking: The study compares non-reranking selection by output probability with reranking of N-best lists using likelihood, backward likelihood, length, and language-model features.The reranking feature weights are optimized with MERT, while BLEU and scaled distinct unigram and bigram counts provide automatic evaluations.
- Results: Diverse decoding boosts performance across all settings, with larger improvements in reranking than non-reranking conditions and especially large gains for longer responses.The authors associate the long-response effect with nearly identical standard-beam hypotheses that reduce reranking’s impact.
- Results: The diverseRL model improves performance on the natural split by dynamically adjusting diversity, while its gains are less significant on the short and long splits.The authors suggest the short and long datasets contain examples more similar to each other in length after preprocessing.
- Results: Sampling can produce diversity but is usually incoherent for long sequences because decoding errors accumulate over time.This provides a contrast with the proposed diversity-promoting beam-search approach.
- Evaluation: In human evaluation, diverseRL responses win 62 percent of pairwise comparisons against standard beam search.Crowdsourced judges evaluated 200 items, with three judges ranking each output pair and preferring responses more specific to context.
5.2 Abstractive Summarization
The summarization experiments compare single-sentence and multi-sentence inputs, with diverse decoding helping both settings more in reranking than non-reranking. Multi-sentence summarization remains difficult, but diverse decoding provides a large boost there.
- Training and Dataset: The study evaluates abstractive summarization with single-sentence inputs using a word-level attention model trained on 800K pairs.
- Training and Dataset: A second setting uses up to 10 input sentences and a hierarchical model with sentence-level attention for long-document summarization.
- Results: Diverse reranking helps both reranking and non-reranking settings, with a larger benefit when reranking incorporates global features beyond the encoder-decoder model.
- Results: Multi-sentence summarization performs significantly worse than single-sentence summarization, illustrating current difficulty with long documents.
- Results: Diverse decoding produces a huge performance boost in the multi setting, while diverseRL adds around 0.3 ROUGE score over standard diverse decoding.
5.3 Machine Translation
The machine-translation experiments evaluate diverse beam search and DiverseRL on WMT’14 English-German translation, including standard and reranking settings. Gains are limited without reranking but larger with reranking, while overall improvements trail those in summarization and response generation.
- Training and Dataset: The translation models use 4.5 million English-German training pairs, a 50K vocabulary, and BLEU evaluation on WMT’14 newstest2014.
- Decoding and Reranking: Reranking generates a large N-best list with beam search before applying backward probability, language-model probability, bilingual symmetry, and target-length features.
- Results: The proposed diverse beam search produces no significant improvement in the non-reranking setting, whereas DiverseRL yields a +0.25 performance boost.
- Results: In the reranking setting, diverse beam search improves performance by +0.6 and DiverseRL by +0.9.
- Results: Overall, diverse decoding helps machine translation less than summarization and response generation, possibly because the target distribution has perplexity below 6.
6 Discussion
The paper presents diversity-promoting decoding as a simple, fast modification to beam search and adds an RL variant that adapts diversity rates by input. Benefits are greatest when outputs are diverse or reranking requires varied candidates.
- Discussion: The general algorithm adds an intra-sibling ranking term to beam search, favoring hypotheses from diverse parent nodes.
- Discussion: The RL variant automatically adjusts diversity rates for different inputs and yields better generation quality than standard beam search or basic diverse decoding.
- Discussion: Diverse decoding contributes most when ground-truth outputs are highly diverse or when reranking must incorporate features absent from the first decoding pass.