Source-linked AI summary
Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models
Ashwin K Vijayakumar, Michael Cogswell, Ramprasath R. Selvaraju, Qing Sun, Stefan Lee, David Crandall, Dhruv Batra
TL;DR
Beam search often returns nearly identical outputs, wasting computation and failing to represent ambiguity in tasks with multiple plausible answers. The paper introduces Diverse Beam Search, which combines sequence likelihood with diversity across beam groups through doubly greedy decoding. Across image captioning, visual question generation, and machine translation experiments, DBS consistently outperforms beam search and other baselines with about the same computational and memory requirements.
Problem
Beam search produces highly similar outputs, wasting computation and failing to capture multiple plausible solutions in ambiguous AI tasks.
Method
Diverse Beam Search divides beams into groups and augments sequence likelihood with a dissimilarity term, optimized greedily across time and groups.
Results
DBS consistently outperforms beam search and other baselines across experiments while using about the same time and resources as beam search.
Takeaways & Limitations
Diverse decoding is especially advantageous for complex images and tasks with greater variety in possible visually grounded outputs.
Abstract
from arXiv · showhide
Neural sequence models are widely used to model time-series data. Equally ubiquitous is the usage of beam search (BS) as an approximate inference algorithm to decode output sequences from these models. BS explores the search space in a greedy left-right fashion retaining only the top-B candidates - resulting in sequences that differ only slightly from each other. Producing lists of nearly identical sequences is not only computationally wasteful but also typically fails to capture the inherent ambiguity of complex AI tasks. To overcome this problem, we propose Diverse Beam Search (DBS), an alternative to BS that decodes a list of diverse outputs by optimizing for a diversity-augmented objective. We observe that our method finds better top-1 solutions by controlling for the exploration and exploitation of the search space - implying that DBS is a better search algorithm. Moreover, these gains are achieved with minimal computational or memory over- head as compared to beam search. To demonstrate the broad applicability of our method, we present results on image captioning, machine translation and visual question generation using both standard quantitative metrics and qualitative human studies. Further, we study the role of diversity for image-grounded language generation tasks as the complexity of the image changes. We observe that our method consistently outperforms BS and previously proposed techniques for diverse decoding from neural sequence models.
1 INTRODUCTION
Neural sequence models commonly use beam search for approximate decoding, but beam search often produces near-identical outputs. Diverse Beam Search addresses this by decoding diverse sequences through a diversity-augmented objective.
- Inference in RNNs: Beam search is a common approximate inference method for neural sequence models, which model conditional output probabilities over time.Exact inference is difficult because the sequence space grows exponentially with length.
- Lack of Diversity in BS: Beam search often produces generic, low-diversity solutions whose differences are limited to minor variations near sequence endings.Figure 1 contrasts these near-duplicate captions with more varied human descriptions.
- Lack of Diversity in BS: Near-identical beams repeat essentially the same computation without significant performance gains, making beam search computationally wasteful.The problem arises because multiple beams often share the same search path.
- Lack of Diversity in BS: Loss-evaluation mismatch can lead practitioners to reduce beam widths, producing bland and generic outputs despite treating beam width as an optimization setting.The passage gives always saying “I don’t know” in conversation models as an example.
- Overview and Contributions: Diverse Beam Search divides the beam budget into groups and optimizes likelihood together with a dissimilarity term to decode diverse sequences.The method uses a doubly greedy optimization over time and beam groups.
2 PRELIMINARIES: DECODING RNNS WITH BEAM SEARCH
RNN decoding seeks the most likely output sequence, but exact inference is intractable, so beam search retains only the highest-scoring partial sequences at each time step. Because completions usually descend from one strong beam, the resulting outputs tend to be minor variations of one sequence.
- The Decoding Problem: RNN decoding maximizes the sum of log conditional probabilities over the output sequence.The next-token distribution is conditioned on the input and all preceding output tokens.
- The Decoding Problem: Exact inference is impractical because the sequence space grows as |V|^T, motivating approximate decoding algorithms.The RNN formulation can also require repeatedly forwarding the network to compute factors.
- Beam Search: At each time step, beam search expands the current B candidates with every vocabulary token and retains the B most likely extensions.B denotes the beam width.
- Beam Search: Beam search repeatedly sorts B × |V| extensions by log-probability and finally ranks the retained beams to select the most likely sequence.This procedure greedily progresses from left to right until time T.
- Beam Search: Most beam-search completions stem from one highly valued beam, yielding outputs that are minor perturbations of a single sequence.Parallel exploration therefore does not necessarily produce meaningfully distinct solutions.
3 DIVERSE BEAM SEARCH: FORMULATION AND ALGORITHM
Diverse Beam Search makes beam decoding diverse by partitioning beams into groups and penalizing similarity to earlier groups. It preserves efficient greedy decoding by optimizing each group with diversity-augmented scores.
- Diverse Beam Search: Jointly optimizing all diverse candidates is intractable because the number of possible solution combinations grows as |V|^B.DBS avoids this joint optimization by dividing the beam budget into groups.
- Diverse Beam Search: DBS partitions the B beams into G non-empty groups, each containing B′ = B/G beams under an equal partition.Applying ordinary beam search independently would otherwise produce identical outputs across groups.
- Diverse Beam Search: The DBS objective adds a dissimilarity term measuring how different a candidate is from beams in the current group.The dissimilarity function can be defined in multiple ways.
- Diverse Beam Search: The dissimilarity function may use negative co-occurring n-gram costs or distances between distributed sentence representations.These choices encode different notions of sequence diversity.
- Diverse Beam Search: Each group is extended with a standard beam-search step using log-probabilities augmented by dissimilarity penalties from previously optimized groups.This yields a doubly greedy procedure over time and groups.
1 Perform a diverse beam search with G groups using a beam width of B
DBS divides the beam budget into groups and performs staggered group-wise beam searches that incorporate diversity penalties. This structure supports diverse exploration with little memory or computational overhead while retaining a beam-search quality guarantee.
- Diverse Beam Search: After the first group, each group performs beam search with log-probabilities augmented by a diversity penalty, then all group solutions are returned.The final output is the union of the B solutions from all groups.
- Diverse Beam Search: DBS encourages diversity between beams at each step, rewarding groups for exploring different output-space regions instead of repeatedly pursuing earlier suboptimal beams.
- Diverse Beam Search: DBS incorporates diversity with little memory or computational overhead, and its first group is guaranteed to perform at least as well as beam search of size B/G.
4 RELATED WORK
Prior work generates diverse structured or neural-model outputs through iterative conditioning, heuristics, or modified objectives. DBS instead modifies inference directly, making it applicable to models where beam search already applies and complementary to model-level approaches.
- Diverse M-Best Lists: DivMBest formulates diverse structured-output generation as iterative inference that conditions each solution on previous outputs to induce diversity.
- Diverse M-Best Lists: Gimpel et al. sequentially run beam searches while retaining only one solution per iteration, making the approach extremely wasteful.
- Diverse Decoding for RNNs: Earlier neural-model efforts target diverse decodings for conversation modeling and machine translation, including heuristics that discourage sequences from sharing common roots.
- Diverse Decoding for RNNs: Li et al. penalize generic input-independent sequences by maximizing mutual information with an additional target language model, whereas DBS is a modified inference algorithm applicable to any beam-search-compatible model.
5 EXPERIMENTS
Experiments evaluate DBS against beam search and prior diverse-decoding methods across captioning, translation, and visual question generation. DBS improves diversity and task-specific oracle metrics, with larger gains on more complex images.
- Experimental Setup: DBS is evaluated against beam search and existing diverse-decoding methods across image captioning, machine translation, and visual question generation.The study also examines image complexity and reports quantitative metrics and human preference results.
- Evaluation Metrics: Oracle accuracy measures the best task-specific score in a generated list, while diversity statistics count length-normalized distinct n-grams.Simultaneous improvement in both metrics indicates greater diversity without sacrificing task performance.
- Sensitivity Analysis: Increasing the number of groups increases exploration, whereas increasing λ strengthens diversity but can produce grammatically incorrect outputs when excessive.The experiments generally use G=B and select λ by validation-set grid search; λ values from 0.2 to 0.8 work well across many settings.
- Sensitivity Analysis: Hamming, n-gram, and neural-embedding diversity functions all outperform beam search, with Hamming diversity achieving the best oracle performance.These functions encode different notions of diversity, from token-level differences to semantic similarity.
- Image Captioning: On COCO and PASCAL-50S captioning, DBS outperforms beam search and Li & Jurafsky (2016), including 7.24% and 9.60% Oracle@20 gains on PASCAL-50S.DBS also produces almost 300% more distinct 4-grams than beam search and obtains maximum log-probability -6.53 versus -6.91 for beam search at the same width.
- Image Complexity and Human Evaluation: DBS gains over beam search grow with image complexity: Oracle SPICE@20 improvements are 0.67, 0.91, and 1.13 for simple, average, and complex images.Human annotators preferred DBS captions 60% overall, with preferences of about 50%, 69%, and 83% for simple, average, and difficult images.
- Visual Question Generation: On visual question generation, DBS significantly outperforms baselines on SPICE and diversity metrics, with larger gains than captioning and stronger benefits for complex images.Beam search produces similarly worded questions, whereas DBS asks about multiple image details and generates non-generic questions across types.
6 CONCLUSION
DBS produces diverse decodings across image captioning, question generation, and machine translation while consistently outperforming beam search with comparable runtime and memory. Its gains increase with image complexity in image-grounded language generation.
- DBS is a doubly greedy approximate inference algorithm for decoding diverse sequences across captioning, question generation, and machine translation.
- DBS consistently outperforms beam search and other baselines without extra computation or task-specific overhead.
- DBS uses about the same time and resources as beam search while producing more diverse decodings.
- DBS provides increased gains as image complexity increases in image-grounded language generation tasks.
SENSIVITY STUDIES
Sensitivity studies examine how group count, diversity strength, and diversity-function choice affect DBS. More groups increase exploration and list diversity, while performance remains robust across diversity strengths and function forms.
- Number of Groups: Increasing groups from G = 1 toward G increases exploration and produces more diverse beam lists.G = 1 corresponds to classical beam search, while diversity is enforced only across groups.
- Choice of Diversity Function: Hamming diversity performs best among the evaluated diversity functions, while other forms remain comparable and outperform beam search.
- Diversity Strength: DBS is robust across a wide range of diversity-strength values λ on the PASCAL-50S validation split.
HUMAN STUDIES
Human studies compare beam-search and DBS captions across image difficulty. DBS is preferred more often as difficulty rises, while distribution mismatch can also favor DBS on low-difficulty images.
- The study collects human preferences through a shuffled comparison interface for DBS and beam-search captions.
- Human preferences for DBS captions are positively correlated with image difficulty score.
- For low-difficulty images, beam-search captions are generally preferred, but training–testing distribution mismatch can make DBS perform better.
- For high-difficulty images, human evaluators prefer captions produced by DBS over captions produced by beam search.