A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation (2020)

Abstract: This work studies the widely adopted ancestral sampling algorithms for auto-regressive language models. We use the quality-diversity (Q-D) trade-off to investigate three popular sampling methods (top-k, nucleus and tempered sampling). We focus on the task of open-ended language generation, and first show that the existing sampling algorithms have similar performance. By carefully inspecting the transformations defined by different sampling algorithms, we identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. To validate the importance of the identified properties, we design two sets of new sampling methods: one set in which each algorithm satisfies all three properties, and one set in which each algorithm violates at least one of the properties. We compare their performance with existing algorithms, and find that violating the identified properties could lead to drastic performance degradation, as measured by the Q-D trade-off. On the other hand, we find that the set of sampling algorithms that satisfy these properties performs on par with the existing sampling algorithms.

## introduction a language model (lm) is a central module for natural language generation (nlg) tasks @xcite such as machine translation @xcite , dialogue response generation @xcite , image captioning @xcite , and related tasks. given a trained lm, finding the best way to generate a sample from it has been an important challenge for nlg applications. figure 1 : human evaluation (y-axis: quality, x-axis: diversity, both are the bigger the better) shows that the generation performance of existing sampling algorithms are on par with each other. decoding, i.e., finding the most probable output sequence from a trained model, is a natural principle for generation. the beam-search decoding algorithm approximately finds the most likely sequence by performing breadth-first search over a restricted search space. it has achieved success in machine translation, summarization, image captioning, and other subfields. however, in the task of open-ended language generation (which is the focus of this work), a significant degree of diversity is required. for example, conditioned on the prompt "the news says that ...", the lm is expected to be able to generate a wide range of interesting continuations. while the deterministic behavior of decoding algorithms could give high-quality samples, they suffer from a serious lack of diversity. this need for diversity gives rise to a wide adoption of various sampling algorithms. notably, topk sampling @xcite , nucleus sampling @xcite , and tempered sampling @xcite have been used in open-ended generation @xcite , story generation @xcite , and dialogue response generation @xcite . however, the sampling algorithm and the hyperparameter are usually chosen via heuristics, and a comprehensive comparison between existing sampling algorithm is lacking in the literature. more importantly, the underlying reasons behind the success of the existing sampling algorithms still remains poorly understood. in this work, we begin by using the qualitydiversity (q-d) trade-off @xcite to compare the three existing sampling algorithms. for automatic metrics, we use the bleu score for quality and n-gram entropy for diversity. we also correlate these automatic metrics with human judgements. the first observation we draw is that top-k , nucleus and tempered sampling perform on par in the q-d trade-off, as shown in figure 1 . motivated by this result, we extract three key properties by inspecting the transformations defined by the sampling algorithms: (1) entropy reduction, (2) order preservation and (3) slope preservation. we prove all three properties hold for the three existing sampling algorithms. we then set out to systematically validate the importance of the identified properties. to do so, we design two sets of new sampling algorithms in which each algorithm either violates one of the identified properties, or satisfies all properties. using the q-d trade-off, we compare their efficacy against existing algorithms, and find that violating these identified properties could result in significant performance degradation. more interestingly, we find that the set of sampling algorithms that satisfies these properties has generation performance that matches the performance of existing sampling algorithms. ## properties of sampling algorithms as we will show in section 5.1 (also figure 1 ), top-k, nucleus and tempered sampling perform on par with each other under our evaluation. this key observation makes us question: what are the core principles underlying the different algorithms that lead to their similar performance? to answer this question, in this section, we identify three core properties that are provably shared by the existing sampling algorithms. we then design experiments to validate their importance. ## experiment setup in this section, we first establish evaluation protocols, and then describe the model and data we use for the open-ended language generation task. ## empirical results first, we compare existing sampling algorithms, and then move on to validate the necessity and figure 2 : the performance (x-axis: quality, y-axis: diversity, both are the smaller the better) of top-k, nucleus, tempered and tempered top-k sampling are on par on the gigaword dataset, as shown by automatic evaluation. ## related works despite the popularity of sampling algorithms in natural language generation, a rigorous comparison or scrutiny of existing algorithms is lacking in the literature. @xcite provides a comparison between sampling and decoding algorithms. @xcite proposes nucleus sampling, and compare it with top-k sampling @xcite . however, only a few hyperparameter configurations are tested. in @xcite and @xcite , temperature sampling is used and the hyperparameter t is tuned to trade-off between diversity and quality, but it lacks comparisons with other sampling algorithms. @xcite studies the consistency of existing sampling and decoding algorithms, without comparing the generation performance. in this work we mainly use the quality-diversity trade-off @xcite to conduct a compar-ison of different sampling algorithms. parallel to our work, @xcite also uses the qualitydiversity trade-off to compare top-k, nucleus, and tempered sampling. their observation is similar to ours: the performance of the existing algorithms are close with no significant gap. more importantly, the underlying reasons for the success of various sampling algorithms remain poorly understood. @xcite proposes the selective sampling algorithm, which fails to outperform existing approaches. this failed attempt suggests the need for a better understanding of the strengths and weaknesses of existing methods. to the best of our knowledge, our work provides the first systematic characterization of sampling algorithms, where we attribute the success of existing sampling algorithms to a shared set of properties. we show that we can propose novel sampling algorithms based on the identified properties, and reach competitive generation performance as measured by both automatic and human evaluation. ## limitations and future work our core contribution is the three properties of sampling algorithms that we conjecture are crucial for competitive generation performance. while we design a set of experiments to validate their necessity and sufficiency, the observations we make are still empirical. we emphasize that it is completely possible that there exists some crucial property, that is yet to be discovered, and can lead to significantly better generation performance. therefore, the exploration of novel sampling algorithms @xcite should still be encouraged. on the other hand, to provide a comprehensive study, we focus on the open-ended language generation task with the gpt-2 model. as future work, it would be interesting to check whether our observations also hold on other tasks such story generation or dialogue response generation, or with weaker language models in low-resource setting. ## conclusion this work studies sampling algorithms for the openended language generation task. we show that the existing algorithms, namely top-k, nucleus, and tempered sampling, have similar generation performance as measured by the quality-diversity tradeoff evaluation. motivated by this result, we identify three key properties that we prove are shared by the existing algorithms. to validate the importance of these identified properties, we design a set of new sampling algorithms, and compare their performance with the existing sampling algorithms. we find that violation of the identified properties may lead to drastic performance degradation. on the other hand, we propose several novel algorithms, namely random top-k and max entropy sampling, that meet the identified properties. we find that their generation performance is on par with the existing algorithms.