PaperlayerView exact revision on arXiv

Source-linked AI summary

Comparison of Diverse Decoding Methods from Conditional Language Models

Daphne Ippolito, Reno Kriz, Maria Kustikova, João Sedoc, Chris Callison-Burch

arXiv:1906.06362v1cs.CL

TL;DR

Diverse candidates can serve open-ended generation and reranking, but decoding methods have had limited direct comparison. This paper surveys diverse decoding strategies and proposes over-sampling followed by clustering; relative effectiveness varies by task and tolerance for lower-quality outputs.

  • Problem

    Diverse candidates can benefit open-ended generation and reranking, but existing diversity-enhancing strategies have rarely been compared directly on a single task.

    Source: §1 · pp. 1–2

  • Method

    The paper surveys decoding-time strategies for diversity and proposes over-sampling outputs followed by post-decoding clustering to remove similar sequences.

    Source: §1 · p. 2

  • Results

    Across the two tasks considered, decoding strategies differ in relative effectiveness, making the optimal choice task-specific and dependent on tolerance for lower-quality outputs.

    Source: §8 · p. 9

  • Takeaways & Limitations

    Over-sampling outputs and filtering to the desired number is an easy way to increase diversity, and the authors recommend random sampling for over-sampling because large beam searches are computationally expensive.

    Source: §8 · p. 9

    Observed quality and diversity differences may reflect the hyperparameters selected by the original studies, so further work is needed to assess this possibility.

    Source: §8 · p. 9

Abstract

from arXiv · show

While conditional language models have greatly improved in their ability to output high-quality natural language, many NLP applications benefit from being able to generate a diverse set of candidate sequences. Diverse decoding strategies aim to, within a given-sized candidate list, cover as much of the space of high-quality outputs as possible, leading to improvements for tasks that re-rank and combine candidate outputs. Standard decoding methods, such as beam search, optimize for generating high likelihood sequences rather than diverse ones, though recent work has focused on increasing diversity in these methods. In this work, we perform an extensive survey of decoding-time strategies for generating diverse outputs from conditional language models. We also show how diversity can be improved without sacrificing quality by over-sampling additional candidates, then filtering to the desired number.

1 Introduction

The introduction frames diverse candidate generation as valuable for open-ended language tasks, but notes that existing diversity-enhancing methods have rarely been compared directly. The paper surveys those methods and proposes over-sampling followed by clustering to remove similar outputs.

1 Introduction

  • Figure 1 contrasts beam search’s repetitive bus captions with more varied random samples, which are lower quality.The beam outputs often differ only in punctuation or minor morphological variations.Source: Figure 1 · p. 1, §1 · p. 1
  • Here, diversity means producing valid outputs for an input that vary widely in word choice, topic, and meaning.The introduction contrasts this definition with uses of diversity to mean interestingness or unlikeliness.Source: §1 · p. 1
  • Diverse candidates can benefit story suggestions, image-caption-based descriptions, and reranking, which is more effective when its inputs are diverse.The introduction notes that reranking diverse candidates has improved results in open dialog and machine translation.Source: §1 · pp. 1–2
  • Prior diverse decoding methods often improve diversity over beam search, but few studies have compared them against each other on a single task.The paper also examines over-sampling followed by post-decoding clustering to remove similar sequences.Source: §1 · p. 2
  • The paper compares diverse decoding strategies on open-ended dialog and image captioning, recommends a strategy, and proposes clustering to improve quality and diversity across decoding methods.Its survey examines the relationship between output diversity and perceived quality.Source: §1 · p. 2

2 Standard Decoding Methods

Conditional language models predict output tokens based on the input and preceding tokens, and decoding methods approximate the search for a likely output sequence. This section describes greedy arg-max, random sampling, and beam search, along with sampling controls.

2 Standard Decoding Methods

  • Conditional language models use an encoder to represent the input and a decoder to generate output, predicting each next token from the input and preceding tokens.The next-token distribution is computed with a softmax over model outputs.Source: §2 · p. 2
  • Greedy arg-max decoding selects the highest-probability word at each timestep, but typically produces repetitive, short outputs and cannot generate multiple samples.The paper notes that this deterministic approach is rarely used in language modeling.Source: §2 · p. 2
  • Random sampling draws from the model’s next-token distribution, while temperature adjusts its entropy and top-s sampling restricts choices to the s most likely tokens.The paper reports that top-s’s hard restriction on low-probability words controls stochasticity more effectively than temperature.Source: §2 · pp. 2–3
  • Beam search expands b partial hypotheses at each step and keeps the b highest-scoring, commonly highest-log-likelihood, candidates, but tends to return near-duplicate sequences.Because it explores only a limited part of the search space, its outputs may differ mainly in punctuation or minor morphology.Source: §2 · p. 3

3 Extensions to Beam Search

The section describes decoding-time methods that diversify candidates through hidden-state noise, restrictions on beam expansion, diversity-aware scoring, repeated search, or clustering. It also notes a domain-specific learned method that the paper does not evaluate.

Noisy Parallel Approximate Decoding

  • NPAD adds annealed Gaussian noise to decoder hidden states, and the authors report results using it with beam search.Noise variance decreases from an initial σ0 to 0 as decoding progresses.Source: §3 · p. 3

Extensions to NPAD

  • The paper does not evaluate learned hidden-state manipulation using arbitrary decoding objectives because those objectives can be highly domain-specific.The passage describes these extensions as related work and gives Gu et al. (2017) as an example.Source: §3 · p. 3

Top-g Capping

  • Top-g capping limits each parent hypothesis to its top g candidates before globally selecting the next b hypotheses.Candidate hypotheses are grouped by parent, leaving b × g candidates to rank.Source: §3 · p. 3

Hamming Diversity Reward

  • Hamming Diversity Reward adds a tunable diversity term to log-likelihood, with negative Hamming distance used to favor candidates unlike previously selected partial hypotheses.The cited work found Hamming distance more effective than embedding or n-gram diversity definitions.Source: §3 · p. 3

Iterative Beam Search

  • Iterative beam search reruns beam search while restricting later iterations from exploring partial hypotheses found in earlier searches.The implementation excludes exact matches; a soft exclusion of states within ϵ Hamming distance was not beneficial in Kulikov et al. (2018).Source: §3 · pp. 3–4

Clustered Beam Search

  • Clustered beam search embeds the top 2∗b candidates, clusters them with K-means, and selects candidates from the clusters, with a fallback for undersized clusters.The implementation uses averaged GloVe embeddings; when a cluster has fewer than b/c candidates, it includes the highest-ranked candidates not already selected.Source: §3 · p. 4

4 Clustering Post-Decoding (PDC)

The paper extends post-decoding clustering by changing how candidates are embedded and selected, then adjusts cluster sampling to favor larger clusters.

Post-decoding clustering

  • The method builds on post-decoding clustering previously used to increase the variety of sentence simplifications after beam-size-100 decoding.The earlier approach used Paragraph Vector document embeddings with K-means.Source: §4 · p. 4

Changes to clustering

  • The authors use BERT-based sentence-level embeddings and select each cluster’s highest-log-likelihood candidate instead of its centroid-nearest sentence.This is intended to retain the best candidates according to log-likelihood.Source: §4 · p. 4
  • The implementation removes clusters containing two or fewer sentences, then samples a second candidate from remaining clusters, prioritizing larger clusters.The passage motivates this adjustment by noting that cluster sizes and candidate quality can vary.Source: §4 · pp. 4–5

5 Experimental Setup

The experiments compare decoding strategies on open-ended dialog and image captioning, evaluating candidate-set quality and diversity. The setup specifies task-specific data and metrics, including Dist-k and Ent-k for diversity.

5 Experimental Setup

  • The setup uses published hyperparameters and compares random sampling and beam-search variants, including methods that generate 100 candidates before filtering to 10.Beam-based methods generate 10 outputs with beam size 10; oversampled sets use beam size 100 or 100 random samples, then post-decoding clustering or likelihood ranking.Source: §5 · p. 5

5.1 Open-ended Dialog Task

  • Dialog evaluation uses 100 Cornell Movie Dialog Corpus prompts and assesses response perplexity plus human fluency, adequacy, and interestingness ratings.Annotators gave binary ratings; the study collected three judgments for each of the top ten responses per method.Source: §5.1 · p. 5

5.2 Image Captioning Task

  • Image captioning uses a released MSCOCO-trained model and 5,000 test images, with SPICE@1, Oracle SPICE@10, and mean SPICE measuring different aspects of candidate quality.SPICE@1 scores the top-scoring caption, SPICE@10 the maximum across ten candidates, and mean SPICE averages all ten.Source: §5.2 · p. 5, Table 3 · p. 6

5.3 Evaluating Diversity

  • Dist-k measures distinct k-grams per generated token, while Ent-k weights k-grams by frequency in the candidate responses.The paper reports Dist-2 and Dist-4; it notes that Dist-k weights every observed k-gram equally, unlike entropy, which reflects frequency.Source: §5.3 · pp. 5–6
  • The dialog results table organizes methods by direct 10-output decoding and 100-output sampling or beam search filtered to 10 candidates.It marks statistical ties with †.Source: Table 2 · p. 6

6 Results

Across dialog and image captioning, random sampling yielded more diverse but lower-quality outputs than beam search, while oversampling and filtering increased quality while retaining high diversity. The results also reveal a marked trade-off between diversity and perceived quality.

6 Results

  • Random sampling yielded more diverse but lower-quality outputs than beam search, while oversampling then filtering increased quality while retaining high diversity.Source: §6 · p. 6

6.1 The Quality Diversity Tradeoff

  • -0.83 with Ent-4 and -0.84 with Dist-2 link mean SPICE to diversity in image captioning; dialog fluency and adequacy are also strongly negatively correlated with diversity.Interestingness also was not positively correlated with diversity, suggesting existing diversity statistics do not capture what humans find interesting.Source: §6.1 · p. 7, Figure 2 · p. 7
  • Dialog's sum-of-ranks leaders were clustered beam search and standard beam search (beam size 100, PDC), while random sampling (temperature 1.0, top-10 capping, PDC) led image captioning.Clustered beam search with beam size 10 followed the two dialog leaders; standard beam search, Hamming Diversity beam search, and Top-g capping beam search (beam size 10) tied for second in image captioning.Source: §6.1 · p. 8

6.2 Random Sampling-based Methods

  • Higher sampling temperature increased diversity but reduced quality; in dialog, top-10 sampling balanced quality and diversity better than temperature adjustment, unlike image captioning, where it underperformed temperature 0.7.Top-10 sampling had the highest dialog fluency, coherence, and interestingness, with significantly lower perplexity than other random-sampling methods.Source: §6.2 · p. 8

6.3 Beam Search-based Methods

  • Cluster5 BS led beam methods on dialog interestingness and image SPICE@10; Iter5 BS yielded the greatest diversity but the lowest coherence among beam methods.Top3Cap BS had the highest mean SPICE for image captioning, indicating it best ensured all outputs were reasonable quality.Source: §6.3 · p. 8

6.4 Effect of Over-sampling

  • In dialog, beam-size-100 search followed by filtering matched beam-size-10 human quality with considerably higher diversity; PDC favored diversity and interestingness, while likelihood reranking favored fluency and adequacy.For random sampling, both filtering methods improved fluency and adequacy over sampling only 10 outputs, but interestingness declined.Source: §6.4 · p. 8
  • In image captioning, oversampling and reranking did not consistently improve quality: SPICE@1 worsened for both sampling and decoding, while random-sampling diversity fell and beam-search diversity rose.Mean SPICE improved for random sampling but not beam search; SPICE@10 improved for random sampling and for beam search when PDC was applied.Source: §6.4 · pp. 8–9
  • Oversampling generally improved the diversity-quality trade-off but increased computation, particularly with beam search; PDC also required embeddings for every output.Source: §6.4 · p. 9

7 Additional Related Work

This section reviews training-time diversity objectives and explains the paper’s decoding-time focus. It also discusses quality-evaluation choices and related methods.

7 Additional Related Work

  • Concurrent work proposed nucleus sampling as an improvement to the sampling strategies discussed in this paper.Source: §7 · p. 9
  • Training-time diversity objectives replace standard log-likelihood with diversity-promoting losses, including mutual-information and adversarial approaches [Li et al. (2016a); Zhang et al. (2018); Xu et al. (2018)].The paper does not evaluate these methods because they tend to be task-specific and difficult to implement.Source: §7 · p. 9
  • The evaluated decoding strategies are architecture- and input-type-agnostic when the model outputs a token probability distribution.This contrasts with training-time methods, which the paper excludes as task-specific and difficult to implement.Source: §7 · p. 9
  • For dialog, the paper reports human scores and perplexity, and for image captioning it reports SPICE, while omitting some measures used elsewhere.SPICE has higher correlation with human judgments, whereas single-reference dialog BLEU has little correlation with human-judged quality.Source: §7 · p. 9

8 Conclusion

The paper concludes that over-sampling and filtering can increase diversity, with random sampling recommended to limit computational expense. Which decoding strategy works best varies by task and tolerance for lower-quality outputs, while hyperparameter effects remain unresolved.

8 Conclusion

  • Over-sampling outputs and filtering to the desired number is an easy way to increase diversity, and random sampling is recommended to reduce computational expense.Source: §8 · p. 9
  • The relative effectiveness of decoding strategies differs across the two tasks, making the optimal choice task-specific and dependent on tolerance for lower-quality outputs.Source: §8 · p. 9
  • Further work is needed to determine whether observed quality and diversity differences reflect the methods or their original hyperparameter choices.Source: §8 · p. 9

Related papers

Loading 1906.06362v1…