GSD: GENERALIZED STOCHASTIC DECODING
Year: 2021

Abstract:
Although substantial progress has been made in various text generation tasks, there remains a vast gap between current generations and human languages. One reason is that virtually all decoding methods currently developed are pragmatic to address the text degeneration problem, which exists in both deterministic and stochastic decoding algorithms. So, why text generated from these algorithms are degenerated? What is the critical difference between these algorithms? Moreover, is it possible to design a generalized framework where existing decoding algorithms can be naturally connected, uniformly described, and mutually inspired? In this paper, we try to explore answers to these intriguing questions. Correctly, we propose a generalized decoding framework that can be used to describe and connect existing popular decoding algorithms. Based on the framework, we propose a novel implementation with distinctive design from existing decoding algorithms. As far as we know, this is the first work trying to propose a generalized framework to bridge these decoding algorithms using formal theorems and concrete implementations. By setting up different conditions, our framework provides infinite space to develop new decoding algorithms. Experiments show that text produced by our method is closest to the characteristics of human languages. Source code and the generated text can be accessed from https://github.com/ginoailab/gsd.git.

heading: 1 INTRODUCTION
text: Benefiting from large-scale pre-trained language models (Radford et al., 2019; Lewis et al., 2020; Tseng et al., 2020; Sun & Yang, 2020), considerable advances have been observed in many natural language generation (NLG) tasks. Nevertheless, given these pre-trained models, only limited decoding strategies are available to use, such as Greedy, Sampling, Beam Search, Top-k (Fan et al., 2018; Holtzman et al., 2018), and the recently proposed nucleus sampling (i.e., top-p) (Holtzman et al., 2020). These decoding algorithms are essential because virtually all text generation tasks need them to transfer inferred predictions to successive text (Basu et al., 2021). However, few of these decoding algorithms can resist the risk of text degeneration. That is, text produced by these algorithms exhibits quite different characteristics from those used by humans, which contains many generic words, repeated loops, and irrelevant sentences.
This problem has been confirmed by many previous works (Holtzman et al., 2020; Welleck et al., 2020b). Some researchers deem that it is ineluctable because generators do empower high probabilities to the correct words, but locally, the highest probability can only be assigned to the text with generic, repetitive, or meaningless phrases. However, we suppose that this problem is triggered by the distinct manners between humans and the decoding algorithms about how text is produced.
Concretely, it is very odd for humans to be told to utter more diversely or more fluently. Diverse or not, it usually depends on personal habits of language usage. Similarly, fluency or not, it is generally determined by people’s familiarity with that language (patients with language disorders are excluded). For most decoding algorithms that are currently popular and widely used since virtually all of them must be configured with at least one hyper-parameter before being available to use. Then, these hyper-parameters become the only exceptions in the decoding system that are not controlled by the algorithms, which brings many uncertainties to the decoding system.
Based on these observations, we propose a novel decoding algorithm with a hyper-parameter-free design. All behaviors of our decoding method are automatically controlled and dynamically adjusted
by the algorithm itself, which is distinctive from all popular decoding algorithms currently developed. We name this novel method as Intrinsic Decoding. Detailed comparisons between Intrinsic Decoding and existing algorithms will be described in the following sections.
More importantly, we also propose a generalized decoding framework (GSD) to connect these decoding algorithms in formal mathematical theorems, including both existing decoding methods and our proposed Intrinsic Decoding. The relationships between GSD and these algorithms can be vividly expressed in Figure 1.

heading: 2 BACKGROUND

heading: 2.1 PROBLEM STATEMENT
text: Given a vocabulary V and a pre-trained generator G, a general text generation task is to produce a sequence of words x = {xi}, xi ∈ V conditioned on some specific types of context xδ , where δ represents a span containing x. The context can be either text (e.g., in summarization (Shen et al., 2019b; Matsumaru et al., 2020), translation (Chen et al., 2020; Wang et al., 2020), story-telling (Ippolito et al., 2020) tasks), images (e.g., image caption (Alikhani et al., 2020)), or structured input (e.g., AMR-to-text (Liu et al., 2021), tabular-to-text (Li & Rush, 2020)). For open-domain generation tasks (Goldfarb-Tarrant et al., 2019; Prabhumoye et al., 2019), both xδ and x are text tokens. Specifically, G can be pre-trained using any properly configured neural models, such as GRU (Su et al., 2020b; Cho et al., 2014; Shi et al., 2020), Transformer Vaswani et al. (2017); Thapliyal & Soricut (2020), it accepts a span of context xδ , performs inference, and finally gives a batch of predictions indicating the possibility for each word x ∈ V that may appear after each individual x ∈ δ. Formally, we represent such predictions by a distribution P̂ as defined in Equation 1.
P̂ (x|xδ) = softmax(Gxδ) (1)
In the following sections, we refer to P̂ as the inference distribution, which is fully controlled by G. Based on P̂ , the decoding task aims to answer the question of how to get x from P̂ (x|xδ) ? Intuitively, a naive solution is to argument-maximize P̂ iteratively until encountering an End-ofSequence (EOS) token, which is known as Greedy Decoding. Simple as it is, Greedy Decoding is fast to run and straightforward to interpret. While just as implied by its name, Greedy Decoding shares the same weakness as other greedy-based algorithms. That is, locally optimized searching does not make any promise to the global best answer.
Indeed, both Greedy Decoding and Beam Search are approximations of the MAP decoding. To visualize the detailed decoding process of these deterministic algorithms, we plot the probabilities in each step to generate an example. As depicted in Figure 2.1, probabilities assigned by Greedy Decoding and Beam Search are pretty different from probabilities of the samples obtained from data generated by humans.
get x from P̂ (x|xδ) is to sample, instead of to search the solution space defined by V and G. This strategy inspires a batch of new decoding algorithms developed for various NLG tasks. These algorithms are generally referred to as stochastic approaches, which will be detailed in the next section.

heading: 2.2 RELATED WORK
text: In this section, we discuss the properties of some popular decoding algorithms that are widely used (Kang & Hashimoto, 2020; Su et al., 2020a)in both industry and research NLG domains.
For deterministic decoding, many recent works (Murray & Chiang, 2018; Stahlberg & Byrne, 2019; Welleck et al., 2020a) have been proposed to investigate how to better control the quality of generated text. For instance, Murray & Chiang (2018) draws an important conclusion that for beam search, it is not always true that a wider beam will help translation, sometimes it hurts. Stahlberg & Byrne (2019) shows constraining search with a minimum translation length is at the root of the problem of empty translations.
Recently, some works have been proposed to investigate how to explicitly control the property of the generated text by manipulating the decoding hyper-parameters under some specific principles. For example, Pang & He (2020) model generation as an offline reinforcement learning task with reference demonstrations. It aims to maximize quality given model-generated histories. Nadeem et al. (2020) propose to identify key properties that are shared among some decoding algorithms and investigate what will happen if meeting or violating the identified properties. (Basu et al., 2021) propose to design a feedback-based adaptive top-k decoding algorithm that generates text with a predetermined perplexity. However, none of them aim to design a generalized decoding framework that can be used to describe and connect existing popular decoding algorithms, which is just the focus of our paper.
For clarity, we denote the decoding probability assigned by a decoding algorithm by P (x|xδ), while keeping to use P̂ (x|xδ) as in Section 2.1 to represent the generation probability inferred by a pretrained NLG model G. Recall the sub-vocabulary observations about how human communicates introduced in Section 2.1. Surprisingly, we find that these stochastic decoding algorithms are also related to some sub-
vocabulary equivalents or subsets if formally described by mathematical language. To describe these different stochastic decoding methods uniformly, we use Equation 2 to abstract the relationship between P (x|xδ) and P̂ (x|xδ). Different from V , ∆ defined in Equation 2 is exactly the sub-vocabulary equivalent in mathematics containing relevantly important words for the decoding steps. It is also the key difference to discriminate between these stochastic decoding methods.
P (x|xδ) =
{ φ(P̂ (x|xδ)), x ∈ ∆
0, x /∈ ∆ (2)
We briefly introduce the theoretical backgrounds of Sampling Decoding, Top-k Decoding, and Nucleus Decoding (i.e., Top-p), especially how different ∆ is constructed by these stochastic methods.
Among these methods, Sampling Decoding may be the simplest one because of its most flexible hypothesis of ∆: ∆ is free to include any elements in V . In other words, ∆ is V itself. Therefore, there is no algorithm-specific sub-vocabulary. All words in the entire dictionary space are candidates to sample from. This behavior can be formally described by Equation 3.
φ(P̂ ) = P̂ (x|xδ),∆ = V (3)
Sampling Decoding extends the search space to V while maintaining high decoding efficiency compared to the deterministic methods. This is quite different from Beam Search, whose speed is very sensible to the search width parameterw. However, as remained by Holtzman et al. (2020), the problem with Sampling Decoding is that it has a long probability tail, which brings a lot of irrelevant samples in the decoding process.
To alleviate this problem, a ∆-limited decoding method, Top-k sampling, is proposed to decode text from pre-trained generators (Fan et al., 2018; Holtzman et al., 2018; Radford et al., 2019). Unlike Sampling Decoding, Top-k sampling has a limited subset of ∆, which consists of the top-k most promising candidates for the algorithm to consider. Equation 4 formally describes the conditions of how a proper ∆ subset should be constructed.
S = {Ω|min{P̂x∈Ω(x|xδ)} ≥ max{P̂x∈V−Ω(x|xδ)}, |Ω| = k, x ∈ V } (4)
Given Equation 4, Top-k sampling can be precisely defined by Equation 5. Notably, S is defined as a super-set containing all valid ∆ sets that can be used by Top-k. A benefit of defining ∆ in such a way is that it takes into account all special and general cases of P̂ . This definition holds even if there exist identical elements in P̂ .
φ(P̂ ) = P̂ (x|xδ)/ ∑ x∈∆ P̂ (x|xδ),∆ ∈ S (5)
Top-k sampling has a similar subset ∆ to integrate the relevantly significant words for a given context. Promising as it is, the challenge for top-k is that the hyper-parameter of k is hard to specify (Holtzman et al., 2020): large k is problematic for flat P̂ , while small k is precarious for peaked P̂ .
Based on the observation, Holtzman et al. (2020) proposes a novel method to define ∆, the size of which is dynamically changed for different shapes of P̂ . As described by Equation 6, the limitation for ∆ is relaxed to the aggregated mass of the probabilities, instead of the size of ∆ containing these probabilities. This method is known as Nucleus Sampling or Top-P Decoding, the definition of which is formally described by Equation 7.
S = {Ω| ∑ x∈Ω P̂ (x|xδ) ≥ p, x ∈ V } (6)
φ(P̂ ) = P̂ (x|xδ)/ ∑ x∈∆ P̂ (x|xδ),∆ ∈ S, |∆| = min{|Ω|,∀Ω ∈ S} (7)
Despite the relatively complex form of definition, Equation 7 can be efficiently executed by filtering the accumulated sum of P̂ ).
Given the lesson learned from Top-k, an akin question for Top-p sampling is how the hyperparameter p is determined? General answer for this question is that small p values force the decoding algorithm to generate fluent expressions, while large p values encourage diverse generations. Then, what if p is small because we want fluent terms while P̂ is flat? Or what will happen if P̂ is peaked, but p has been set to a large value to favor our diverse demand?
Indeed, similar questions could be endless as long as there is a hyper-parameter affecting the performance of the decoding algorithm. Except for Sampling Decoding and Greedy Search, all decoding algorithms discussed so far involve at least one hyper-parameter managing specific properties of that method. Unfortunately, the two exceptions both have known issues that stop them from being considered as potential alternatives. These are the key observations inspiring our work.

heading: 3 METHOD
text: In this paper, we propose a novel decoding algorithm where no hyper-parameter is needed to manage the properties of the decoding performance. All behaviors are dynamically balanced and intrinsically adjusted, just like humans. Before introducing it, we will first introduce a more generalized decoding framework, referred to as GSD in this paper, to connect the decoding algorithms discussed above, including our proposed hyper-parameter-free decoding method that will be introduced later.
Since there is no oracle to consult, the only resource that can be referenced during a decoding process is the pre-trained generator G. Therefore, we plan to hand over all hyper-parametric controlling tasks to G, hoping it to automatically remind the decoding process of how flat or peaked the current inference is.
We first need a metric to quantify the flat/peaked degree of current inference. A natural choice is variance. While we prefer to use entropy since variance is relatively harder to control because of its unlimited value range. Entropy is an indicator to determine the uncertainty of a system. Formally, we use γ defined in Equation 8 to quantify the degree of uncertainty.
Then, we need an activation gate to control how γ will be engaged in the decoding system. More generic mappings, such as neural networks or linear combinations of basic functions, can also be used if efficiency is not a sensible factor in some NLG systems. In this paper, we use tanh to manage γ, whose mathematical properties have been well studied. The gated result of γ is defined by Equation 9.
Finally, we can define the proposed GSD via Equation 10. S is a super-set of our focus ∆, each element Ω in S is a proper candidate for ∆. In practice, we prefer the ones with minimized size.
One may question Equation 9 because of τ , which has not been described currently. It seems like a hyper-parameter. While this is not true. We design τ in Equation 9 for three intentions. Firstly, it is a bridge for GSD to connect other decoding algorithms. By applying different restrictions on τ , GSD can be concretized to different decoding algorithms. Secondly, it is the key to our hyperparameter-free decoding algorithm that will be introduced later. Thirdly, the presence of τ provides infinite space to design new stochastic decoding algorithms.
γ(P̂ ) = − ∑ P̂ log(P̂ ) (8)
ρ(P̂ ) = tanh(γ/τ) = eγ/τ − e−γ/τ
eγ/τ + e−γ/τ (9)
S = {Ω| ∑ x∈Ω P̂ (x|xδ) ≥ ρ, x ∈ V } (10)
For the first intention, we detail the restrictions by four theorems formally describing how exactly GSD concretizes to existing decoding algorithms by different restrictions applied on τ . Specifically,
Theorem 3.1 3.4 characterizes the conditions under which GSD will become Sampling Decoding, Greedy Decoding, Top-k Sampling, and Nucleus Sampling, respectively.
Theorem 3.1 GSD has the same effect as Sampling Decoding if τ = holds, where 1 > 0 is a tiny value close to 0.
Proof 3.1 τ = will force γ/τ → inf . As a result, the value of ρ(P̂ ) = tanh(γ/τ) will approach 1. Since the maximized value of ∑ x∈Ω P̂ (x|xδ) is limited to 1, Ω in Equation 10 has to include as many elements as possible to exceeds τ . Extremely, it can only be equal to |V | at most, that is, sampling from the whole vocabulary set. This is just the definition of Sampling Decoding (see Equation 3).
Theorem 3.2 GSD will degenerate to Greedy Decoding when the value range of τ is limited by Inequality 11, where |V | is the vocabulary size.
log(|V |) τ ≤ γ arctanh(maxP̂ )
(11)
See Appendix A.1 for the proof of Theorem 3.2.
Theorem 3.3 GSD becomes Top-k Decoding if τ is limited by Inequality 12, where |∆| = k.
γ min{arctanh(P̂x∈∆(x|xδ))} ≤ τ ≤ γ max{arctanh(P̂x∈(V−∆)(x|xδ))} (12)
Proof 3.2 Given the fact the both tanh and arctanh are monotone increasing functions, we can rewrite Inequality 12 by Inequality 13, which is the equivalent way to define S as in Equation 4.
max{P̂x∈(V−∆)(x|xδ)} ≤ tanh( γ
τ ) ≤ min{P̂x∈∆(x|xδ)} (13)
Theorem 3.4 GSD is equivalent to Nucleus Sampling by limiting τ using Inequality 14, where p is the nucleus size.
0 < τ ≤ 2γ log( 1+p1−p )
(14)
Proof 3.3 τ ≤ 2γ log( 1+p1−p ) ⇒ ρ ≥ p
Given these theorems and proofs, it can be clearly understood that these algorithms are indeed related and our proposed decoding framework does have the ability to describe and connect them.
For the second intention, ensuring hyper-parameters are intrinsically managed is an important property to imitate human language generation habits. This is reasonable because it is very odd for humans to be told to utter more diversely or more fluently. Diverse or not, it usually depends on personal habits of language usage. Similarly, fluency or not is generally determined by people’s familiarity with that language. Neither diversity nor fluency is a pre-specified hyper-parameter for routine communications. Both are automatically controlled by the person himself who is producing the oral utterances or written text. Therefore, the decoding algorithm should automatically define the hyper-parameters it will use in the decoding process.
Based on the observation, we define τ by Equation 15, where |B| is the batch size of each inference action. Equation 15 is reasonable because in all formulations we have introduced above, batch information has not yet been considered or modeled. Actually, besides the horizontal direction along which the vocabulary items are inferred, information in the vertical batches is also vital since different samples in the same batch may observe quite distinct contexts.
Equation 16 formally defines the border of how the ∆ subset of our hyper-parameter-free decoding algorithm should be restricted. We refer to the decoding method defined by Equation 16 as Intrinsic Decoding. Like other decoding algorithms discussed in this paper, it is also a special case of our proposed decoding framework. While different from all the other methods, Intrinsic Decoding is hyper-parameter-free. Neither deterministic search nor unlimited sampling strategies are involved in Intrinsic Decoding, which is the critical difference between Intrinsic Decoding and other hyperparameter-free methods (e.g., Greedy and Sampling).
τ = µ(P̂ ) = 1 |B| ∑ xδ∈B γ(P̂ ) (15)
ρ(P̂ ) = eγ/µ − e−γ/µ
eγ/µ + e−γ/µ (16)
Notably, the parameters ρ and µ are automatically controlled and dynamically adjusted. Thus, both ρ and µ are not hyper-parameters specified by users.
Finally, for the third intention, the presence of τ provides an extensive way to discover and design new decoding algorithms. By setting up different conditions, our framework provides infinite space for new decoding approaches.
To summarize, we first propose GSD, a generalized decoding framework that can be concretized to other decoding algorithms introduced in Section 2.1. Then, we detail the connections between GSD and these decoding algorithms using formal theorems. Finally, we propose Intrinsic Decoding, the first hyper-parameter-free stochastic decoding algorithm that is not designed under deterministic search or unlimited sampling strategies.

heading: 4 EVALUATION
text: In this section, we describe the setups of all experiments and report the corresponding results.

heading: 4.1 SETUPS
text: We use GPT-2 (Radford et al., 2019) as the pre-trained generator to assign inference probabilities for all the decoding algorithms. GPT-2 is a popular generator that has been used in many generation tasks (Lawrence et al., 2019). For the corpus, we use the same testing datasets as GPT-2, which is released by OpenAI at 1. Each decoding algorithm is executed under the same contexts built from this testing corpus. Concretely, the default batch size is 50. All generations are limited to a maximized length 200. For Beam Search, we run it under different search width w = (2, 4, 6, 8, 10). For top-k decoding, k = (20, 40, 60, 80, 100) are used as the size of ∆ containing the top probabilities. While for Nucleus Sampling (Top-p Decoding), we use p = (0.15, 0.35, 0.55, 0.75, 0.95) as the nucleus size of ∆. Also, we compare the performance of the decoding algorithms under different temperatures t = (0.1, 0.3, 0.5, 0.7, 0.9).
We use perplexity (PPL) (Li et al., 2020) as the metric to evaluate the fluency of the generations. Perplexity closest to human generations is considered as the best indicator of fluent generations. Self-BLEU (Shen et al., 2019a) and distinct ratio (Welleck et al., 2020b; Wu et al., 2020) are two popular metrics to measure the diversity aspect of the generated text. Similar to perplexity, the gap between human generations and the decoding algorithms should be minimized if text generated by that algorithm is considered the most diverse. Following Holtzman et al. (2020), we include the Zipf coefficient as another measurement to test the statistical behavior of these decoding algorithms.

heading: 4.2 RESULTS
text: First, we compare the fluency performance by perplexity for different decode algorithms. As depicted in Figure 3, our proposed Intrinsic Decoding is the most promising algorithm to generate
1https://github.com/openai/gpt-2-output-dataset

heading: Method PPL Self-BLEU Zipf Distinct Rate
text: fluent text as compared to humans. A distinctive line of our method can be observed in all three sub-figures, which is closest to humans’ perplexity line.
Concretely, the perplexity of Beam Search is relatively more minor than other algorithms. Therefore, we plot a separated figure to contain it and embed it in the upper space of the left sub-figure. For the other two figures, the lines are relatively clear to read. From the embedded figure of Beam Search, it can be observed that increasing the search width helps to obtain more fluent generations. However, this benefit is traded by a costed search of the magnified paths inside the entire solution space. Thus, it is not sustainable with large w values if efficiency is sensible in practical systems.
Also, it can be observed from Figure 3 that increasing the size of top-k probabilities (k) or nucleus set (p) has a negative impact on the perplexity metric. This is because that enlarged ∆ set for these algorithms improves the possibility to sample diverse words. However, the long tail problem of Sampling Decoding also comes alongside the benefit. Our method addressed this problem by transferring control of all hyper-parameters to the decoding algorithm itself, such that the hyperparameter selection process can be completely avoided, making the decoding process be an intrinsic system just like how human communicates: no oracle is needed to configure ourselves before we can speak or write.
In Table 1, we report results for all the generation metrics. From the table, it can be clearly observed that our proposed method is competitive among all deterministic and stochastic decoding algorithms with only a few exceptions. Even for the Distinct Rate metric, where our method is not the optimized solution, however, it is still the second-best alternative.

heading: 5 CONCLUSION
text: In this paper, we proposed a generalized stochastic decoding framework. By proofing four mathematical theorems, we demonstrated that Greedy Search, Sampling, Top-k Decoding, and Top-p Sampling are special cases of our proposed framework. We also designed a novel decoding algorithm, Intrinsic Decoding, as an implementation of this framework. All parameters in Intrinsic Decoding
are automatically controlled and dynamically adjusted. Thus, there is no need to be configured with hard-specified hyper-parameters. To the best of our knowledge, this is the first work developing a unified method to bridge existing decoding algorithms using formal theorems and concrete implementations. By setting up different conditions, our framework is capable to provide infinite space for new decoding approaches.

heading: A APPENDIX

heading: A.1 PROOFS OF THEOREMS
text: Proof A.1 (For Theorem 3.2) We first determine the value range of γ(P̂ ) defined by Equation 8.
1) For the maximized value of γ, the problem is a standard convex optimization process that can be defined by Equation 17:
minf(x) = |V |∑ i=1 xilog(xi), xi = P̂i
s.t. |V |∑ i=1 xi = 1
(17)
The Lagrangian dual form of Equation 17 can be represented by Equation 18:
L(f(x), λ) = |V |∑ i=1 xilog(xi) + λ( |V |∑ i=1 xi − 1) (18)
Take the first-order partial derivative of L to any element of x. We can get
∂L(f(x), λ)
∂xi =
∂
∂xi  |V |∑ i=1 xilog(xi) + λ( |V |∑ i=1 xi − 1)  = 0 (19) The solution of Equation 19 is λ = −log(xi)− 1ln2 . Therefore, x1 = x2 = ... = xi,= x|V . By ∑|V | i=1 xi = 1, we can get xi = 1 |V .
Given the solutions of xi, we can finally get the maximized value of γ(P̂ ) = minf(xi) = log(|V )
2) For the minimized value of γ, the problem can be directly solved by observing derivative function figures of Equation 20:
f(y) = −ylog(y) (20)
By observing the figures of f(y)’s first and second order derivative functions, the minimized value can be obtained: minf(y) = f(1) = 0.
Given 1) and 2), the range of γ can be determined: γ ∈ [0, log(|V |)].
However, for a general NLG model G, it rarely assigns full 0 or 1 probabilities for a batch of input contexts.
Therefore, the actual value range for γ is γ ∈ (0, log(|V |)] ⊂ [0, log(|V |)].
Let τ log(|V |), it will force γ/τ → 0. As a result, the value of ρ(P̂ ) = tanh(γ/τ) will approach 0. However, it will never be 0, which enables much more flexibility for Ω than in Theorem 3.1 because it only needs to include a tiny set of elements.
Recall the condition for Theorem 3.2: τ ≤ γ(P̂ ) arctanh(maxP̂ )
, it ensures ∑
∆ P̂ ≥ maxP̂ . This condition forces the tiny set to include the top probability element in V , which is equal to Greedy Decoding.

heading: A.2 EXAMPLE GENERATIONS

heading: Shared Context
text: Tokenized Ids = [9060, 8305, 1644, 1043, 5445, 4324, 290, 5445, 5405, 319, 300, 1192, 1603, 2975] Text = Image caption Police found broken window and broken glass on Lancaster Road

heading: Human
text: There have been raids on homes in Blackburn homes after a Wexford-based developer a llegedly forged a fraudulent loan and offered thousands of dollars in new loans to people without any experience in the business. According to police reports the owners of some homes were encouraged to move in in order to avoid debt risk. ...

heading: Greedy Decoding
text: A man was arrested on suspicion of burglary and possession of a stolen vehicle. The man was taken
to hospital with serious injuries. He was taken to hospital with serious injuries. The man was taken to hospital with serious injuries. The man was taken to hospital with serious injuries. The man was taken to hospital with serious injuries. The man was taken to hospital with serious injuries. ...
Beam Search with width = 2 A police spokesman said: Ẅe are investigating the incident.Ẅe are appealing to anyone who witnessed the incident to contact us.T̈he lancaster road is a popular route for cyclists and pedestrians on the north-west side of the city.”
Beam Search with width = 10 Police said they were called to the scene at around 11.30pm on Sunday after reports of a disturbance. They said they were called to the scene at around 11.30pm on Sunday after reports of a disturbance. They said they were called to the scene at around 11.30pm on Sunday after reports of a disturbance.

heading: Sampling without temperature
text: A bystander suffered non-life threatening injuries after workers and emergency workers had to make an emergency stop while conducting routine traffic stop on lancaster road outside Athill in Cork last night. Lyte Snelling was up and about as the cops stopped, before continuing with their routine traffic stop. ...

heading: Sampling with temperature = 0.9
text: A bystander suffered non-life threatening injuries after workers and emergency workers had to make an emergency stop while conducting routine traffic stop on lancaster road. The cause of the incident in Scarborough came as a separate report by the MCHA said a lancaster road basal had been broken in Scarborough. The report said a light on lancaster side side c̈aught fire and required immediate emergency crews to get it to safetÿ. Baker said as more details came in it was completely öut of platformäs to what was happening to the lancaster. Mr Baker said: T̈he lancaster is now getting into complete crisis mode.N̈o one’s money is being wasted trying to stop our project from proceeding properly.”̈
Top-k with k = 40, no temperature applied A motorist suffered extensive bruises after he crashed his car into the lancaster on the Lilliana Drive, an isolated intersection, just after 5.30pm this week. Inspector George Cocker was called by a motorist, who said the driver’s car had broken into the road, possibly because it had been parked on neighbouring roads. ...

heading: Top-k with k = 40, temperature = 0.9
text: A motorist suffered extensive injuries after he crashed his car into a lancaster on the Lusitania Highway. No-one was arrested and no injuries were reported. In a statement issued by the Lusitania Police, officials said the driver was carrying a vehicle with an estimated weight of over 500kg weighing over 100kg. ...
Top-k with k = 100, no temperature applied A motorist suffered extensive bruises after he crashed his car into the lancaster on the Lulles Street side of the intersection, just after 5.30pm this week. Dr Neil Wilson with CTA was treating the driver as if he had been beaten with a hammer and after being treated for cuts later, told the Liverpool Echo his car had been used to ”cock it up”. ...
Top-p with p = 0.15, no temperature applied A man was arrested on suspicion of burglary and attempted burglary after he was found in a lancaster road. The man was taken to hospital with serious injuries. Police said the man was taken to hospital with serious injuries. Image copyright PA Image caption Police said the man was taken to hospital with serious injuries Image copyright PA Image caption Police said the man was taken to hospital with serious injuries Image copyright PA Image caption Police said the man was taken to hospital with serious injuries ...
Top-p with p = 0.95, no temperature applied Alex Jones and five other co-defendants spoke on Monday about the discovery. They said they had been going by the name ”Mike Jackson” in cars and a recording had been made, and that the investigation was finished when police finally announced they had found ”evidence.” ...

heading: Top-p with p = 0.95, temperature = 0.3
text: A man who was driving a lancaster on the road in the city’s north-east was arrested on suspicion of
driving under the influence of alcohol. The man, who was not named, was arrested at about 10:30 GMT on suspicion of driving under the influence of alcohol. He was taken to hospital with serious injuries. ...
Intrinsic Decoding without temperature (Ours) A spokesman for Norwich City said: ”The case is being investigated by the council’s Financial Conduct Authority and the public has been informed.” No further details have been given at this stage.” Tops said the window had been returned to the club, but no break was found. Despite the police being called to the scene, Norwich City’s President Dave O’Dwyer said he could not discuss the investigation. ...
Intrinsic Decoding with temperature = 0.9 (Ours) A spokesman for Northern Ireland’s National Police Chiefs’ Council said: ”We have located broken windows and broken glass in the areas of Carmarthen and Kilbride. ”We are continuing to investigate and are working with the police to identify the perpetrators.” Police in Carmarthen, Cumbria, said at least seven people had been taken to hospital with non-life threatening injuries. ...
More generation examples can be downloaded from 2
A.3 ILLUSTRATION OF DECODING PROBABILITY
2https://github.com/ginoailab/gsd/blob/master/dumps/result.zip

Review summaries:
This work introduces the generalized stochastic decoding (GSD) framework and the subsequent Intrinsic Decoding algorithm. They formally show how several existing stochastic decoding algorithms can be viewed as special cases of GSD. Further they perform empirical comparison of sequence completions between their Intrinsic Decoding and other algorithms paired with GPT-2 using automatic metrics. They suggest that the GSD can be seen as a platform for future research around stochastic based decoding strategies.

The paper deals with decoding algorithms for neural text generation. The paper proposes a way to connect greedy decoding, beam search, (ancestral) sampling, top-k sampling, top-p (nucleus) sampling. The proposed GSD is on page 6 (specifically, equations 8, 9, 10). The visualization for how equations 8-10 tie the decoding algorithms together is in Figure 1. The authors claim that this generalization can provide an “infinite space” for designing more decoding algorithms. Empirical results show that open-domain text generation from GPT-2 using GSD results in a perplexity that’s closer to the human perplexity, and a self-BLEU that’s closer to the human self-BLEU.  

This paper proposes a fairly general approach to generating from language models: words are sampled from a renormalized distribution consisting of the smallest set of words in the vocabulary which together have probability at least $\rho$, where $\rho$ is a function of the entropy of the distribution. The authors show that several standard decoding algorithms arise from particular choices of $\rho$. The authors then propose to use a particular $\rho$, essentially $\tanh(\text{entropy}/\text{average batch entropy})$, which they argue is attractive because it has no hyperparameters. The authors evaluate the generations obtained from decoding with their approach by comparing them to baseline generations in terms of perplexity assigned to generations by GPT-2, self-BLEU, and other recent automatic metrics.