MIROSTAT: A NEURAL TEXT DECODING ALGORITHM THAT DIRECTLY CONTROLS PERPLEXITY
Authors: Sourya Basu
Govardana Sachitanandam Ramachandran
Nitish Shirish Keskar
Lav R. Varshney
Venue: ICLR 2021 Poster (2021)
Keywords: Neural text decoding
sampling algorithms
cross-entropy
repetitions
incoherence

Abstract: Neural text decoding algorithms strongly influence the quality of texts generated using language models, but popular algorithms like top-k, top-p (nucleus), and temperature-based sampling may yield texts that have objectionable repetition or incoherence. Although these methods generate high-quality text after ad hoc parameter tuning that depends on the language model and the length of generated text, not much is known about the control they provide over the statistics of the output. This is important, however, since recent reports show that humans prefer when perplexity is neither too much nor too little and since we experimentally show that cross-entropy (log of perplexity) has a near-linear relation with repetition. First, we provide a theoretical analysis of perplexity in top-k, top-p, and temperature sampling, under Zipfian statistics. Then, we use this analysis to design a feedback-based adaptive top-k text decoding algorithm called mirostat that generates text (of any length) with a predetermined target value of perplexity without any tuning. Experiments show that for low values of k and p, perplexity drops significantly with generated text length and leads to excessive repetitions (the boredom trap). Contrarily, for large values of k and p, perplexity increases with generated text length and leads to incoherence (confusion trap). Mirostat avoids both traps. Specifically, we show that setting target perplexity value beyond a threshold yields negligible sentence-level repetitions. Experiments with
human raters for fluency, coherence, and quality further verify our findings.

Published as a conference paper at ICLR 2021
MIROSTAT: A NEURAL TEXT DECODING ALGORITHM THAT DIRECTLY CONTROLS PERPLEXITY
Sourya Basu"
Govardana Sachitanandam Ramachandran'
Nitish Shirish Keskarf
Lav R. Varshney"
"Department of Electrical and Computer Engineering, University of Illinois at Urbana-Chamaaign i Salesforce Research
ABSTRACT
Neural text decoding algorithms strongly influence the quality of texts generated using language models, but popular algorithms like top-k; top-p (nucleus), and lemperature-based sampling may yield texts that have objectionable repetition or incoherence. Although these methods generate high-quality text after ad hoc pa- rameter tuning that depends on the language model and the length of generated text, not much is known about the control they provide over the statistics of the output. This is important, however, since recent reports show that humans pre- fer when perplexity is neither too much nor too little and since we experimen- tally show that cross-entropy (log of perplexity) has a near-linear relation with repetition. First we provide a theoretical analysis of perplexity in top-k, top-p. and temperature sampling, under Zipfian statistics. Then, design a feedback- based adaptive top-k text decoding algorithm called mirostat that generates text (of any length) with predetermined target value of perplexity without any tuning. Experiments show that for low values of l and p, perplexity drops significantly with generated text length and leads excessive repetitions (the boredom trap). Contrarily, for large values of k and p. perplexity increases with generated text length and leads to incoherence (confusion trap). Mirostat avoids both traps. Specifically, we show that setting target perplexity value be- yond threshold yields negligible sentence-level repetitions. Experiments with human raters for fluency, coherence, and quality further verify our findings.
this analysis
INTRODUCTION
Large-scale generative language models (LMs) have received recent attention due to their high- quality open-ended text generation ability (Brown al. 2020 Radford et al., 2019). Generating texts from these LMs usually relies on some form of random sampling. Pure sampling often leads to incoherent and low-quality texts (Holtzman al. 2018), whereas greedy decoding leads excessive repetitions, another form of low quality. The right decoding algorithm is needed to generate high- quality texts with controlled attributes (Ippolito al. 2020 Zhang et al., 2220 Ippolito al. 2019).
We introduce mirostat a neural text decoding algorithm that actively controls the generative process maintain the perplexity of generated text a certain desired value. Mirostat uses an adaptive top- k sampling algorithm to actively tune the value of k which helps maintain the overall perplexity of the text; recall that top-k sampling (Holtzman et al.) 2018 Fan al., (0018) is where the next word is sampled from the top A most probable choices|
Top-k sampling and several other recent sampling methods are motivated by suppressing an unre- liable tail in the probability distribution of trained LMs. Another sampling method is top-p, also known as nucleus sampling, where the next word is chosen from the top x probable choices, where
TTee word mirostat is derived from mirum which is Latin for surprise and star meaning control. This work was funded in part by the IBM-Illinoi Center for Cognitive Computing Systems Research (C3SR), research collaboration as part of the IBM AT Horizons Network and the National Science Foundation Grant CCF-1717530.

---

Published as a conference paper at ICLR 2021
is the smallest integer such that their cumulative probability mass is at least p (Holtzman al. 2020). While top-k sampling involves a fixed number of most probable choices, top-p sampling involves a dynamic number of choices based on fixed p value and shows better statistical and human-evaluated performance. For small values of and p. these sampling methods unfortunately repeat phrases in generated text. This can be handled by penalizing repetitions and using appropri- ate temperature values (Keskar et al., (219)) or adding diversity to the generated text (Zhang et al.) 2020 Vijayakumar et al.] 2018). On the other hand, large values of k and p can lead incoherent texts similar to pure sampling. Although choosing appropriate values of p or & can avoid repetition and incoherence, this involves ad hoc tuning of parameters. Even for fixed value of p or k, the generated text can have varying statistical properties.
Intriguingly, as we demonstrate via Example ① in Appendix A small values of a certain perplexity statistic of generated texts called surprise (Def. 1 are closely linked to repetitions and large values statistical metric used to evaluate quality of
of surprise are linked to incoherence. Perplexity neural text generation, and is closely related to average surprise shown in Fig. 7 in Appendix [A]
and formalized in Sec. 2 A large-scale human subject experiment by Zhang et al. (2020) showed quality is closely related to the likelihood of the generated text for fixed number of tokens. In particular, reducing perplexity increases quality upto some point before the quality starts dropping. This implies that good control over perplexity of the generated text would give direct control over the quality of generated text (as evaluated by humans). Generating texts with an appropriately chosen target perplexity value may maximize quality of generated text. Ergo mirostat.
Now we summarize our key contributions. Sec. shows theoretically how cross-entropy and hence perplexity grows in top-k and top-p sampling as a function of and p respectively, which was previ- ously unknown. Sec. introduucss mirostat sampling, which outputs texts with predetermined target perplexity value. Although perplexity may not fully capture the quality of text (Hashimoto et al. 2019), much literature discusses its correlation to quality (Zhang et al. 2020). Hence, our algorithm to control perplexity helps generate high-quality text. fec.js..eexpermmental
shows much fluctua- tion in cross-entropy rates in top-k and top-p sampling as a function of their input parameters, hence unable to control perplexity of output text. Sec. 5.2 shows repetition is closely related to perplexity of the generated texts, mostly independent of the sampling method, but slightly dependent on the LM used. Sec.,3.3)exx experimmiit shows mirostat sampling avoids both boredom and confusion traps for wide range of target perplexity values. Sec. 3.4 provides our own experiments with human raters that demonstrate mirostat efficacy for fluency, coherence, and overall quality.
1.1 RELATED WORK
Sampling from distorted probability distribution Pure sampling from LMs often leads in- coherent text whereas greedy decoding leads to repetitions. Distorting probability distributions, as in top-k; top-p, or temperature sampling help improve quality of generated texts, if parameters are properly tuned (Holtzman et al. 2018: Fan et al., 2018 Holtzman et al.) 2020). Tuning these methods, however, is ad hoc and does not provide good control over the statistics of the output. Our method uses statistics of previously-generan distorting the probability distribution so it helps control the overall statistics of the generated text. This ability control the perplexity of the output is key advantage of our method over previous work. This, when used with the relation between perplexity and human-evaluated quality observed by /Zhang al. (2020), can yield text that has better quality control.
tokens as input to generate the next token, by
Controllable text generation Controllable text generation has oft focused on semantics of the output text, as in LMs like CTRL (Keskar et al. 2019). and sampling algorithms like plug-and-pla LM (Dathathri et al. 2020) and constrained sentence generation by Metropolis-Hastingg (Miao et al.) 2019). Contrarily
approach is purely statistical, guiding the decoder along desired statistical path that addresses issues with pure sampling and greedy decoding.
Quality-diversity tradeoff Top-k, top-p, and oowteempeatture sampling improve the quality of the text, but at the cost of reduced diversity. Applications like quality generation, but open-ended tasks such as story generation demand diversity too. Li et al. (2016); Vijayakumar et al. (2018); Kulikov et al. (2019) propose variants of beam search to induce diversity in generated text. However, /Zhang et al. (2020) observe a tradeoff between quality and
only demand high-
2

---

Published as a conference paper at ICLR 2021
diversity; they further observe diversity is closely related to entropy whereas quality is maximized in a certain range of observed likelihood values for fixed-length sentences. Our algorithm well-controls observed cross-entropy, the observed likelihood per token of generated text. Hence, by maintaining the observed cross-entropy in a certain range, we can ensure high-quality text generation.
Repetitions Greedy decoding from LMs often lead to texts with excessive repetitions both at token- and sentence-levels. Several techniques have been proposed to address this. Token loss dynamic reweighting (TLDR) hypothesizes some tokens are more difficult to learn than others and so reweighting tokens during learning can balance things to reduce repetitions (Jiang et al.] 2020). Keskar et al. 2019) use a repetition penalty in decoding to reduce repetition of tokens. Welleck et al. (2020) suggest the cause for repetitions is flaw in the training objective itself and use new objec- tive that gives less probability to unlikely sequence including texts with high repetitions. Variants of top-k sampling and repetition penalty in (Keskar et al. 2019) were used before by Foster & White (2007) to reduce repetitions. Here, we demonstrate a near-linear relation between repetitions and observed cross-entropy and so we directly control repetitions by controlling observed cross-entropy.
SURPRISE, ENTROPY, AND PERPLEXITY
Here we formally define surprise, cross-entropy, and perplexity. For random variable X E X distributed as P. the surprisal associated with an instance a of X is defined as - log P(#) (Han & Kobayashi 2007). Hence, less probable instances are more surprising than more probable instances. Extending the definition to conditional random variables, we next define the surprise associated with tokens and sentences with respect to generated text for a fixed model distribution Pas.
Definition 1.
The surprise value of a token X with respect to generated text X and model distri- bution PM for some fixed model M is M (X| Xxi) = - log (M
We will soon see this quantity directly related to perplexity. Now we define the average surprise for sentence X with tokens.
Definition 2. For sentence = (X1,... X,)) with tokens, the surprise rate with respect to probability distribution PM for some model M is G M = - log Par(P (x.
The cross-entropy of a discrete random variable X E X' distributed as Pas with respect to discrete random variable Y E Y' distributed Pv such that y C X' is H(PN. PM)) EwEy PN(y) log (y) = Epw [Y,(())). The cross-entropy rate of a stochastic process X = (X.), E X' distributed as PM with respect to a stochastic process y = [Yt). Y, E y dis- tributed as PN and y S X' is defined as H(PN,, PM) lim Epy (Y"),, when the limit exists. Further, if y sampled from PN and if PN stationary ergodic source, then by the Maaioon-MMiilll-----ee
theorem (Cover & Thomas [006] Thm. 16.8.1), we have lim (Y") H(PN, Pas), when the limit exists. Now, the perplexity corresponding to H(PN,, PM)) is simply PPL(PN, PM)) = 2H((N,Par) following (Brwnn et al. (1992); Varshney et al. (2020). For experiments, when the text is generated using PN. we approximate H[PN. PM) by (Y") for a sentence of length of n. This is because natural language shows stationary ergodic property (Manning& & Schutze, 1999). Perplexity denotes how close PN is to PM. The lower the perplexity, the closer the distributions PN and PM-
THEORETICAL ANALYSIS OF SAMPLING METHODS
Here we summarize theoretical results for different sampling methods; details and proofs in App.
Zipf's law states that the frequency of occurrence of any word in the vocabulary is inversely propor- tional to its rank in the frequency table (Zipf) 1965 Powers) 1998). More precisely, for a vocabulary of size N = | the frequency of the ith most probable word is
p(i: N)
(1)
1 is the Nit generalized where s is an exponent characterizing the distribution and H 2 ne harmonic number. Further, for human languages the exponent is very close to 1. Hence, when
3

---

Published as a conference paper at ICLR 2021
Actual velue
Actual veluw
8.0
7.5
HPN Pa)
6.5-
6.0
2000
4000
6000
8000
10000
0.2 0.3
0.4
0.5
0.7
0.8
0.9
1.0
(a)
(b)
Figure 1: Theoretical analysis of cross-entropy in top-k: and top-p sampling: (a) approximation to (PM PMr) obtained in Thm. 2 (b) approximation to H(PM,, PMr) obtained in Thm. for 1.1, N 50, 000. Note that TMee PM) grows sharply for small values of and the growth is negligible for large values of k. whereas HPMM,, PM) grows nearly linearly with
required, we write = +1+ c, for some small e >>> 0. For all of our theoretical analysis, we assume the sampled words follow Zipf's law.
First we summarize results for top-k sampling. Thm. shows that G(k) grows steeply for small values of k. but grows very slowly for large values of Thm. _ computes an approximation for ([MM. PM); Fig. la shows this approximation is very good. Since H(MM. PM) does not grow much beyond 2000, makes sense to tune between to 2000 to get desired cross-entropy.
Now summarize the results for top-p sampling. Thm. 3 proves that 6(p) behaves near-linearly in p. Further, Thm. 4 provides approximate expressions for (PMM, PM) that show (Parr, Pas) grows approximately linearly with p; this approximate lincarity also shown in Fig. [b This is in contrast to top-k sampling where H (PMe PM)) is highly nonlinear. Temperature is used to suitably distort the original distribution in sampling. In particular, lowering the temperature makes the sampling more greedy. For a given temperature T > the frequency of the kth most probable word in (I) is given by s(k; N, 2)) (k( 7 HN.+ +) p( [k; 7. N). Hence the effect of temperature in analysis is captured simply by modifying to s/T.
generate samples that avoid problems associated with pure
CERPLEXITY-CONTROLI TEXT GENERATION
In this section we propose the mirostat algorithm to directly control the cross-entropy rate of the generated text. Mirostat works in two stages for generating each word. First it estimates the value of s assuming words follow Zipf"s law, details of which is given in Appendix C Then, uses top-k sampling where k is function of the estimated and of the target surprise value of the output text.
Alg. details mirostat, which generates texts with predetermined average surprise value. The input target surprise value which in turn initializes variable μ = 2r. Each word is sampled by first estimating from 300p as 8, then using top-k sampling by approximating & as a function of
and μ according H IN 1
(I-N-1)) and using (3) to get, with é å
s-1
k= ((22))((1-
We initialize corresponding to surprise value 27 and not since we are sampling from top-k and not computing the surprise value at k itself. This 27 initialization works well in practice, and the rest taken care of by feedback: An error term e is computed as the difference between the observed surprise G(X) of the sampled word X and 7, which then is used to update μ. Note that we can use an alternate algorithm to tune in Alg. by iterating through the most probable tokens to set
"Code available at httpp//////hthh....o///aaaaaaaar

---

Published as a conference paper at ICLR 2021
corresponding to token that has suitable amount of surprise. More details such algorithm with experimental results are given in Appendix B
Algorithm 1: Mirostat sampling for perplexity control
Target cross-entropy maximum cross-entropy μ 2r, learning rate m 100 while more words are be generated do
Compute & from 30 : = E m- t,b// -
Compute & from p k = (22"
2) (1/8)
Sample the next word X using top-k sampling
Compute error: e = (Xx -
Update J.C. μ μ ne
end
EXPERIMENTAL ANALYSIS
Here we provide experiments for the performance of top-k, top-p, and mirostat sampling. We use the GPT-2 LM with 1 117M parameters for all experiments (Radford et al. 2019) unless mentioned otherwise, and just refer to it as GPT-2. One main takcaway is that unlike other approaches, mirostat indeed provides direct control over the observed cross-entropy of the output text.
5.1 CROSS-ENTROPY RATE FOR DIFFERENT SAMPLING METHODS
Fig. 2 plots observed cross-entropy in generated texts versus several input parameters for different sampling methods. For each plot, we generate four output texts of 200 tokens corresponding to each value of input parameter in each sampling method with same context in each case.
Fig. 2a shows the observed surprise values in generated texts versus l in top-k sampling. Note that cross-entropy has a steep increase for small values of and relatively slow increase in k for high values of k. Thus, for small values of k, cross-entropy is very sensitive to change in the k. but, for large values of k, cross-entropy hardly changes. Even though we can clearly see the increase in cross-entropy with increase in k it is difffccult to control cross-entropy using top-k sampling.
Fig. plots the observed surprise values generated text versus p in top-p sampling. Observe that cross-entropy grow essentially linearly with increase in p unlike top-k sampling.
Fig. 2c plots the observed cross-entropy generated texts versus target cross-entropy mirostat sampling. Alg. Observe that mirostat sampling gives very good control over observed surprise value, with low variance for surprise values less than five. For higher target surprise, Alg. [ satu- rates in controlling observed surprise, since the algorithm truncates low probability words to control surprise value (and the baseline surprise without any truncation is around five). Thus, to get better control over observed surprise values, must truncate some more probable words as well, which would reduce the quality of the generated text, hence not considered here.
The observation on different growth rate of surprise values in top-k and top-p sampling in Fig. is not very intuitive on its own. Our theoretical analysis Sec. [3] helps explain nonlinear growth in cross-entropy rate in top-k sampling and essentially linear growth in cross-entropy rate in top-p sampling. Note that our theoretical analysis in Sec. 3eclls with cross tross-entropy while our experiments deal with cross-entropy rate. However, for practical purposes cross-entropy helps us give an intuition about cross-entropy rate in different sampling methods under stationary ergodic assumption. There not much fluctuation in cross-entropy rate Fig. 2c because we use feedback to control the cross-entropy rate more accurately, which gives accurate results even for small number of tokens.
5.2 PERPLEXITY AND REPETITIONS
Here, present experimental observations for percentage of repeated tokens across different sampling methods and LMs. In Fig. 3 we generate texts with 200 tokens using different sampling methods and models with varying relevant input parameters such kt p, target surprise values, 7.
5

---

Published as a conference paper at ICLR 2021
Oboe casssmmrpppp.
Target cooss-entrapy
(c) Figure 2: Cross-yntropy rate in different sampling methods: (a) top-k, (b) top-p. and (c) mirostat.
(a)
(b)
Note that cross-entropy rate is nonlinear in top-k sampling and nearly linear in top-p sampling. Also note that for a fixed input parameter in top-k and top-p sampling, observed cross-entropy rate
fluctuates much, whereas mirostat shows negligible fluctuation in observed cross-entropy rate.
rampling
Percenta ge reperition
mmaling
Perconta repettioon
To2.7
10
50
Observed cress-entropy rate (a)
Observed cress-entropy rate
Percertage gram repetition
I cram top-
gram top
gamtz Midl um
stx
Percentage repettiion
Large
gram top
gram too
72
cram mirsbe
Observed cross-entropy rate
Observed cross-entropy rate
(c)
(d)
Figure 3: Percentage repetition observed cross-entropy rate for (a) different sampling methods, (b) different temperature values, T, (c) for n-gram tokens and different sampling methods, (d) dif- ferent LMs. Note that repetitions vary heavily with observed cross-entropy rate in the generated text and mostly independent of sampling method used. Further, large LMs like GPT-2-XL with 1558M parameters seem to have slightly less repetitions for the same cross-entropy rate.
We also consider the percentage of n--ram repetitions for different values of n for a fixed sampling method. We define percentage n-gram repetition as number of distinct n-gram tokens
total number of ri-gram tokens x 100, where an
n-gram token simply means concatenation of contiguous tokens. Hence, for = 1, n-gram repe- titions capture word-level repetitions, whereas larger values n capture sentence-level repetitions. For 1, we refer to percentage 1-gram repetition simply percentage repetition.
In Fig. 3a we observe that percentage repetition decreases with increase in tross-entropy and more importantly. y, for fixed GPT-2 model, this relation is independent of the sampling method.
In Fig. [bb we use top-k sampling with varying temperature values. We observe that repetitions for different temperature values and & follow the same curve as in Fig. 3a This implies cross-entropy

---

Published as a conference paper at ICLR 2021
Tep-k Tep-k 2) kapp Tap-k Se
Tep-k gem 3)
Tap-k gow 51
Percentage rapestion
repectiinn
s0-
20-
10-
25
16a
12.5
17.5
200
Observed cro entropy rate
Repetition penally (0)
(a)
(b)
Figure 4: Percentage repetition (a) observed cross-entropy rate for top-k sampling with varying k, top-k sampling with k = 3, 6 and varying repetition penalties, (b) repetition penalties for top-k sampling with 3,
controls the percentage repetitions in generated texts. Moreover, it implies that once the model and cross-entropy are fixed, percentage repetition is not affected by the considered sampling methods.
In Fig. 3c we capture n-gram repetitions for varying cross-entropy rate and different values of n. We note from Fig. [c] that for small values of n, the percentage n-gram repetitions drop almost linearly with increase in cross-entropy, whereas for larger values of n, the percentage r--ramm repeti- tions is very close to zero for cross- cross-entropy greater than 3. This indicates sentence- repetitions disappear after threshold of cross-entrops whereas word-level repetitions continue to appear for larger values of cross-entropy. Also, note that in human- generated text data, there are often com- mon pronouns and conjunctions that are essential and are often repeated, hence we do not expect good sampling algorithm to have absolutely zero 1-gram repetitions. But, we do expect a good sampling algorithm to have minimum sentence-level repetitions, which all the sampling seems to show beyond a threshold of cross-entropy, which seems to be around 2.5 for GPT-2.
Fig. 3d plots percent repetition versus cross-entropy for different LMs using top-p sampling for varying values of p. Larger LMs such as GPT-2-XL with 1558M parameters have slightly less repetitions for a fixed value of cross-entropy than smaller LMs such as GPT-2 with 117M parameters.
We also provide more experimental results showing near-linear relation between observed cross- entropy and percentage repetition in CTRL. (Keskar et al. 2019) in Appendix
Controlling repetitions using repetition penalty Consider a repetition penalty in top-k sampling to reduce percent repetition, where we multiply negative scores of each repeated word in the vocab- ulary of GPT-2 by 0 E {L..... 20} before computing the corresponding probabilities using softmax. See Keskar al. (219) for more details repetition penalty. Essentially, this reduces the prob- ability of repeated words. In Fig. 4a we observe that repetition penalty tends to reduce percent repetition for fixed cross-entropy rates. However, we also note in Fig. 44b percent repetition does not have good relation with 0, which makes it difficult to use it in practice with target percent repetition. Note that the cases where percent repetition close to zero have high-cross entropy rate, which is true for all values of 6. Hence, we conclude that mirostat when used in conjunction with repetition penalty can provide high-quality results. However, we leave this investigation for future work. From these observations, we conclude that to control percentage repetition in generation we must control the cross-entropy of the output text, exactly like in mirostat.
5.3 BOREDOM AND CONFUSION TRAPS
Here we show top-k and top-p sampling cannot control output and therefore get trapped into low- quality generation, for wide range of l and p. We generated 10 samples of 900-token texts on the same context and averaged their observed cross-entropy at various points of generation in Fig. [5] except for the single-sample human generated text (the tokens following the context in the corpus).
Fig. 5a illustrsts that for small values and p. both top-k and top-p sampling methods fall into low cross-entropy regions- boredom traps-which results in increase in repetitions as the length of
7

---

Published as a conference paper at ICLR 2021
Observed crocs entropy rats
km5
1=10
16000
23
24
3.5
5.8
140
320
<02
500
750
600
230
402
730
700
number tokens
number tokens
(a)
(b)
Observed cress poos-e rale
5.0
Humon
4.5
35-
5.-
2.5
1.5
160
203
320
400
500
600
700
500
620
100
202
360
500
6do
700
605
920
number of tokens
number of tokens
(c)
(d)
Figure 5: Cross-entropy rate vs. number of tokens generated for different sampling methods. We
observe (a) boredom trap for small values of ls and p. (b) confusion trap for large values of k and
(c) human-like cross-entropy rate for moderate & and p, (d) mirostat sampling that shows control over cross-entropy over varying lengths of texts.
the generated text increases, as illustrated in Sec. [5.2 Hence, lack of control over output statistics in these methods leads degradation of quality in generated texts for longer texts.
Fig. 5b shows that for high values of and in top-k and top-p sampling methods respectively, the observed cross-entropy of the generated texts increases with the length of generated texts. This leads to increase in incoherence in the text as the token index increases-the confusion trap.
In Fig. [c| we choose certain values of k and p in ad hoc manner and generate texts using top-k and top-p sampling methods respectively to observe that for these values of k and p. the generated texts tend to have cross-entropy that seems converge
limiting value with increase in text length and not fall into either boredom or confusion traps. We also show how the observed cross-entropy varies with increase in length in the human- -uman--eneeated text corresponding context for these experiments. Human- generated text converges to some limiting value of cross- entropy when the generated text long enough and does fall into either boredom or confusion.
the tokens following the
Finally, Fig. 5d shows cross-y for the pirossat--geeerate texts converges to the target cross- entropy within a few tokens and maintains the desired value of cross-entropy for long texts.
5.4 HUMAN EVALUATIONS
We evaluated performance using human raters, which further indicated the importance and necessity of controlling cross-entropy rates for generating high-quality texts. We generated 300 tokens using GPT-2 from a fixed context with average cross-entropy rate 7 {2.5, 3, 4, 5) using both mirostat and top-p sampling. We presented these texts and a human-generated 300 word continuation of the context to 43 participants from the University of Illinois at Urbana-Champala of Technology, Kanpur. Participants were not informed of the generation process and rated each text on 1 to 7 Likert scales for fluency, coherence, and overall quality. Further, the raters guessed if the text was AI- or human- generated... More details of the experiment are in Appendix [D] Fig, 6 shows texts that had cross-entropy
and Indian Institute
3 received the best ratings by human participants for fluency,
8

---

Published as a conference paper at ICLR 2021
Quanity
32-
Otso vod Cross eott--rtooooy rate
Otse vid Cross cons--rttoopy rate
Otserved coiiienntrgg rate
(b)
(c)
0.24
Human
0:14
Human
0:44
06-
0.81
GF12 vo. Human
06-
0.74
067
GP12
0:86
0.56
0.58
0.37
0.19
021
0.1
80 Human
Human
(d)
(c)
Figure 6: Human evaluation of top-p and mirostat sampling for (a) fluency, (b) coherence, and (c) quality. Detecting human generated text from texts generated by GPT-2 under (d) top-p sampling, (c) mirostat sampling. For given observed cross-entropy rate, notice the similarity between human evaluations of top-p and mirostat sampling across all values of observed cross-entropy rate.
coherence, and overall quality, Further, for r more than half of raters mistakenly guessed the Al-generated text to be human generated. These results show that controlling the cross-entropy rate helps generate high-quality human-like like texts. Further, the sensitivity of these human evaluations to change in cross-entropy rates in Fig. and the fluctuations in cross-entropy rates for fixed input parameters top-p and top-k sampling from Fig. 2 show that mirostat produces high-quality texts without much ad hoc tuning of input parameters.
CONCLUSION
We provided theoretical explanation of how perplexity varies function of input parameters in popular top-k and top-p neural text decoding algorithms, showing that log of perplexity varies nearly linearly function of p and highly nonlinearly as function of k. Building on this analysis, developed mirostat, a neural text decoding algorithm that directly controls the perplexity of the generated text over wide range of text length. Notably, for longer texts and certain ranges of input parameters, top-k and top-p sampling fall into boredom and confusion traps which cause low low-quality texts; Mirostat avoids both traps. Further, recent large-scale human evaluation of neural generated text suggests that human-judged text quality is maximized for certain range of perplexity of the output: mirostat provides direct control to stay that perplexity range. There are also implications for data compression given in Appendix A.2 As takeaway, we find that mirostat with target surprise around 3.0, produces varying lengths of high-quality texts with minimal repetitions. This corroborated in
experiments with human raters.
We further analyze the relation between perplexity and repetitions in text: for fixed model, repeti- tions vary linearly with perplexity and are independent of the sampling method. We also find that larger LMs have less repetitions for any fixed perplexity. Future work would include theoretical analysis of repetitions, boredom and confusion traps, and convergence properties of mirostat.

---

Published as a conference paper at ICLR 2021
REFERENCES
Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, Jennifer C. Lai, and Robert L.. Mercer. An estimate of an upper bound for the entropy of English. Comput. Linguist., 18(1):
31-40, 1992.
Tom B. Brown, Benjamin Mann, Nick Ryder. Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Bemner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. 1XXv:20055.4116VV [cs.CL]., June 2020.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, New York, 2 edition, 2006.
Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosin- ski, and Rosanne Liu. Plug and play language models: a simple approach to controlled text generation. In Proc. 9th Int. Conf. Learn. Represent. (ICLR), April 2020.
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Proc. Assoc. Comput, Linguist, Annu. Meet. (AC1. 2018), pp. 889-898, 898, July 2018. doi: 10.18653/v1/P18.. 1082.. baarrg//nnthhnn URL https: / wwww ac web org/ ant antttatthoooooooo ogy 8-10
Mary Ellen Foster and Michael White. Avoiding repetition in generated text. In Proc. Conf. Eleventh European Workshop Natural Language Generation. (ENLG'07) (07), pp. 33-40, June 2007. URL
https: www.///wwww...oom awwweb. org/ anthology N07-2305
Edgar N. Gilbert. Codes based inaccurate source probabilities. IEEE Trans. Inf. Theory, IT-17
(3):304 -14,,,4,4,11 May 1971. doi: 10. 19.1100/TT..1911105550
Te Sun Han and Kingo Kobayashi. Mathematics information and coding. Ann. Math. Stat., 203, March 2007.
Tatsunori Hashimoto. Hugh Zhang, and Percy Liang. Unifying human and statistical evaluation for natural language generation. In Proc. NAACL-HLT 2019, pp. 1689-1701, June 2019.
Ari Holtzman, Jan Buys, Maxwell Forbes, Antoine Bosselut, David Golub, and Yejin Choi. Learning to write with cooperative discriminators. In Proc. Assoc. Comput. Linguist. Annu. Meet. (ACL 2018), pp. (638-1649, July 2018. doi: 10. N0.18633v1/P1185 152. URI.htts::/ //ww://wwwwww//.ooo ac web.
ozg/anthology/P1e 1152
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In Proc. 9th Int. Conf. Learn. Represent. (ICLR), May 2020.
Daphne Ippolito. Reno Kriz, Maria Kustikova, João Sedoc, and Chris Callison-Bureh Compari- son of diverse decoding methods from conditional language models. In Proc. Assoc. Comput. Linguist. Annu. Meet. 2019), pp. 3752-3762, July 2019.
Daphne Ippolito, Daniel Duckworth, Chris Callison-Burch. and Douglas Eck. Automatic detection of generated text is easiest when humans are fooled. In Proc. Assoc. Comput. Linguist. Annu. Meet. (ACL 2020), pp. 1808-1822 1822, July 2020.
Shaojie Jiang, Thomas Wolf, Christof Monz, and Maarten de Rijke. TLDR: Token loss dynamic reweighting for reducing repetitive utterance generation. arXiv:2003.11963 [cs.CL].. April 2020.
Nitish Shirish Keskar, Bryan McCann, Lav R. Varshney, Caiming Xiong, and Richard Socher. CTRL: conditional transformer language model for controllable generation.
arXiv:1909.0585822 [Ls. September 2019.
Ilia Kulikov, Alexander Miller, Kyunghyun Cho, and Jason Weston. Importance of search and evaluation strategies in neural dialogue modeling. In Proc. 12th Int. Conf. Natural Language Generation (ICNLG 2019), pp. 76-87, October 2019.
10

---

Published as a conference paper at ICLR 2021
Sander Lestrade. Unzipping Zipf's law. PloS ONE, 12(8)=0081188,
Jiwei Li, Will Monroe, and Dan Jurafsky. A simple, fast diverse decoding algorithm for neural generation. 1Xiv:1611100850 [cs.CL]. November 2016.
Christopher Manning and Hinrich Schutze. Foundations of Statistical Natural Language PropeeaaaeProesssseee Processing. MIT Press, 1999.
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. CGMH: Constrained sentence generation by metropollis-hattings sampling. In Proc. 33rd AAAI Conf. Artif. Intell., July 2019.
Steven T. Piantadosi. Zipf's word frequency law in natural language: A critical review and future
directions. Psychonomic Bulletin Review, (1(5):1112-1111 2014.
David M. W. Powers. Applications and explanations Zipf"s law. New Meth. Language Process. and Comp. Natural Language Learning, pp. 151-160, 1998.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Lan- guage models are unsupervised multitask learners. Unpublished manuscript, February 2019.
htwp://t.oootooeteeooooooooaaooo URL modelo are Le wtt.aaaeee...speeeeeeeeeeaaaaaaa
pdf
Jorma J. Rissanen and Glen G. Langdon. Arithmetic coding. IBM J. Res. Develop.. 23(2):149-162,
March 1979.
Lav R. Varshney, Nitish Shirish Keskar, and Richard Socher. Limits of detecting text generated by large-scale language models. In Proc. 2020 Inf. Theory Appl. Workshop, February 2020.
Ashwin K. Vijayakumar, Michael Cogswell, Ramprasaath R. Selvaraju, Qing Sun, Stefan Lee, David Crandall, and Dhruv Batra. Diverse beam search for improved description of complex scenes. In Proc. 32nd AAAI Conf. Artif. Intell., April 2018.
Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. Neu- ral text generation with unlikelihood training. In Proc. 9th Int. Conf. Learn. Represent. (ICLR), May 2020.
Ian H. Witten, Radford M. Neal, and John G. Cleary. Arithmetic coding for data compression. Commun. ACM, 30(6):500-540 June 1987.
Hugh Zhang, Daniel Duckworth, Daphne Ippolito, and Arvind Neelakantan. Trading off diversity and quality in natural language generation. Ntw:2000410450v [cs.CL]., April 2020.
George K. Zipf. The Psycho-biology of Language: An Introduction to Dynamic Philology. MIT Press, 1965.
A EXAMPLES
Here describe two examples. The first example demonstrates the relation between surprise, rep- ctitions, and incoherence. The second example demonstrates the relation between text compression and cross-entropy.
A.1 RELATION BETWEEN SURPRISE, REPETITIONS, AND INCOHERENCE
Example 1. We generate four samples of texts with 200 tokens (which are words or subwords that are part of the vocabulary of the model) using GPT-2 model with 117M parameters Radford et al. (201 For the first two samples we top-p sampling with p 0.4, for the third sample use top-p sampling with = 1.0, and for the fourth sample we use our proposed mirostat sampling algorithm. The fifth example is numan-generann
taken from the same corpus the context. The
context used is as follows.
" For months early in 1943, Shannon came into contact with the leading British math- ematician Alan Turing. Turing had been posted to Washington to share with the U.S. Navy 's crypt- analytic service the methods used by the British Government Code and Cypher School Bletchley
Context:
11

---

Published as a conference paper at ICLR 2021
Park to break the ciphers used by the Kriegsmarine U-boats in the north Atlantic Ocean. He was also interested in the encipherment of speech and to this end spent time at Bell Labs." "
1. Observed average surprise value = 1.471
p= 0.4
Generated text: "Turing" work on the cryptographt of the Kriegsmarine was based on the cipher used by the Kriegsmarine's 's famous E-2. The Kriegsmarine code was based on the Cryptographic Algorithm (CAT) of the Royal Navy. was a new method of solving the problem of encryption, which was mathematical problem which was the basis of the cryplanalysis of the Japanese naval cipher.
Turing's work on the cipher was based on the algorithm used by the Kriegsmarine's 's famous E-2. The cipher was based on the algorithm used by the Kriegsmarine's 's famous E-2.
Turing's work on the cipher based the algorithm used by the Kriegsmarine's 's famous E-2.
Turing's work on the cipher was based on the algorithm used by the Kriegsmarine's 's famous E-2,
Turing's work on the cipher was based on"
Observed average surprise value = 1.887,
p p=0.4 0.4
Generated text: "Turing was great mathematician, and he was not professional cryptogra- pher. But he was a very talented cryptographer. He was also highly intelligent man. He was a great man who
very well-versed in the law of probability. He was also very well-versed in the mathematical methods of the United States Army. He was also very well-versed in the math- ematics of the Russian Academy of Sciences. He was also very well-versed in the mathematical methods of the German Academy of Sciences.
In 1943, Shannon traveled Moscow meet with the Director of the NSA. He told that the FBI had obtained information from the NSA about the German secret police. He was told that the FBI had obtained information from the NSA about the German secret police. He was told that the FBI had obtained information about the German secret police.
The NSA, on the other hand, had been unable get information from the NSA about the German secrete"
Observed average surprise value = 6.342 p= 1.0
Generated text: "In January of 1942, in open letter delivered to 8 persons and addressed to Sherwood, Shannon took the opportunity to address skeptics about the little out-of-print $128,00 000 unreported race "cryptanalysis apparatus of extraterrestrial intelligence." His reply was also reprinted in South Carolina publications (Atlanta Press, Fall Publishing. Miami, New House Press, Yorkshire Press, Sydney Press, Weatherby Press, Winter Press, and Thames & Hudson, to name a few), and eventually accepted as the final subscribed FHAT article. (Summary, were whom)
Birmingham City Police concludes that ['Turing' ss][new replace Robert] Symington is not guilty of breach of OKF law. Further, his suggestions for preventing his sentencing Should he reside anywhere near the city he defies extradition to Bavaria closer to dawn minimal? Lylimud Simpson (Ladies& & Gentlemen, Lawrence Livermore University Press, Philadelphia): Jim Gilmore and its wife, Eva Civilsky,"
Observed average surprise value = 1.828
mirostat target surprise = 1.8
Generated text: "In April 1943, Shannon was assigned to the U.S. Naval Intelligence Center at Naval Air Station Norfolk, Virginia, where he was assigned to work on a project to develop a new cipher for the U.S. Navy's cryptanalysis program. The project was to be conducted by the U.S. Navy's cryptanalysis team.
In early April, the U.S. Navy informed that Shannon had been assigned to work encrypted cipher for the Kriegsmarine's U-boat. The project was to be conducted by a group of cryptographers from the U.S. Naval Intelligence Center. The project was to be conducted by a group of cryptographers from the U.S. Naval Intelligence Center in a project that could be executed by the cryptanalysts.
12

---

Published as a conference paper at ICLR 2021
In early April, Shannon was ordered by the U.S. Navy provide the cryptanalysts with informa- tion on a cipher for the U-boat's 's U-boats that could"
5. Observed average surprise value = 5.285
humaan-gnerated
Generated text: "Shannon and Turing met leatime in the cafeteria. Turing showed Shannon his 1936 paper that defined what is now known as the 'Universal Turing machine'. This impressed Shannon, as many of its ideas complemented his own.
In 1945, as the war was coming to an end, the NDRC was issuing summary of technical reports as a last step prior to its eventual closing down. Inside the volume on fire control, a special essay titled Data Smoothing and Prediction in Ralph Beebe Blackman, and Hendrik Wade Bode, formally treated the problem of smoothing the data in fire-control by analogy with 'the problem of separating signal from interfering noise in communications systems'. In other words, it modeled the problem in terms of data and signal processing and thus heralded the coming of the Information Age. Shamnon's work on cryptography was even more closely related to his later publications on communication theory. At the close of the war"
Systems, coauthored by Shannon,
Figure 7 shows plots of surprise values against indices of tokens in each of the samples in Ex. 1 The blue plot corresponds to surprise values of each token, while the red plot corresponds to average surprise values over window of size 10 at each token index. Note that the surprise values drop drastically in Fig. 7a as the repetitions increase in Ex.
Similarly, in Fig. 76 we observe dip in surprise values wherever there repetition in Ex. 72 Clearly, there is a correlation between small average surprise values and repetitions. Further, in Fig. 7a note that the generating model seems to get trapped into small surprise repetition region. We call this region of small surprise as boredom trap. We observe that these models tend to fall into a boredom trap for small values of p. Figure [c corresponds to Ex. 7 where we choose p = 1.0 and illustrate that for large values of p. the average surprise value of the generated text tends to increase with the number of generated tokens, which leads to incoherence. We call this region of large surprise a confusion trap. Figure 7 shows surprise values corresponding to Ex. 7 which is generated using our proposed sampling algorithm, mirostat. We observe in Fig. [7d that mirostat increases the surprise value when when falling into a boredom trap and, thereby maintaining the average surprise value. By doing so, not only helps generate high-quality text with predetermined average surprise value, but also helps avoid small surprise repetition regions and large surprise incoherent regions. In Fig. 7e we show the surprise values in human generated text that followed this context as shown in Ex. 7 We observe that aeman-geeerattd text has average surprise value that is between values using top-p sampling for p = 0.4 and 1.0. More importantly, human-genenn generated text does not fall into either of the traps.
7
A.2 TEXT GENERATION AND COMPRESSION
Here we will look at texts generated for various target surprise values using mirostat sampling with GPT-2 with 117M. We also observe the well-known relation between cross-entropy and data com- pression (Coerr & Thomas 2006] Ch. 5), (Gilbent 197I). In particular, it is known that when the actual probability distribution of the generated text is not known, then the minimum lossless compression rate achievable is equal to the cross-entropy of the assumed distribution, which the LM here, with respect to the actual unknown distribution, which is obtained from adaptive top-k sampling here.
We generate 200 tokens for different values of target surprise values using the GPT-2 model with 1 117M parameters to show the quality of the text generated using Alg. for different target surprise values. We also measure the compression rates obtained using arithmetic coding (Witten) eet al. 1987, Rissanen & Langdon 1979) with the LM the probability distribution. So. in way, mirostat can generate text that has a predetermined minimum lossless compression rate for a given model.
Example 2.
Context: "For For two months early in 1943, Shannon came into contact with the leading British mathematician Alan Turing. Turing had been posted to Washington share with the U.S. Navy's cryptanalytic service the methods used by the British Government Code and Cypher School at Bletchley Park to break the ciphers used by the Kriegsmarine U-boats in the north Atlantic
13

---

Published as a conference paper at ICLR 2021
Sart
75
100
125
150
17%
200
25
75
100
125
150
175
200
Towon indice
Tosan ool
(a)
(b)
Point wiee surpe se valuee
Po no wiie surprise
Window average surper value
Window average supprise
17.5
22.5
7.5
2.5
25
302
300
200
(c)
(d)
surprive
Window average sursrise value
17.5
125
100
5.0
0.0
(e)
Figure 7: Relation between surprise values and attributes of generated text such repetitions and incoherence: (a) top-p sampling with p = 0.4 and average observed surprise 1.471, (b) top-p sampling with 0.4 and average surprise 1.887, (c) top-p sampling with
1.0 and average
observed surprise 6.342, (d) mirostat sampling with target surprise, т = 1.8 and average observed surprise 1.828, (e) human-generated text, average observed surprise 5.301. We observe that repetitions in generated texts are correlated with dips in surprise values, whereas incoherence is correlated with large and increasing surprise values with indices.
14

---

Published as a conference paper at ICLR 2021
Ocean, He was also interested in the encipherment of speech and to this end spent time at Bell Labs."
Target surprise value 1.0
Observed cross-entropy rate 0.759
Average compressed size
(per token) = 0.863 Percentage compression = 97.66%
Generated text: "In April 1943, Shannon was assigned the U.S. Navy's cryptanalytic service, the Naval Intelligence Service. He was assigned to the cryptanalytic service's cryptanalysis unit, the Naval Intelligence Laboratory, He was also assigned the cryptanalytic unit's cryptanalysis unit, the Naval Intelligence Laboratory.
In May 1943, Shamnon was assigned the cryptanalytic unit's cryptanalysis unit, the Naval Intel- ligence Laboratory. He was also assigned to the cryptanalytic unit's cryptanalysis unit, the Naval Intelligence Laboratory.
In June 1943, Shannon was assigned to the cryptanalytic umit's cryptanalysis unit. He was assigned to the cryptanalytic unit's cryptanalysis unit, the Naval Intelligence Laboratory.
In July 1943, Shannon was assigned to the cryptanalytic umit's cryptanalytic unit. He was assigned the cryptanalytic unit's cryptanalytic unit, the Naval Intelligence Laboratory.
In August 1943, Shannon was assigned"
Target surprise value = 2.0 Observed cross-entropy rate = 1.987 Average compressed size (per token)= 2.07 Percentage compression 95.13%
Generated text: "He was member of the British Intelligence Service, and was also member of the British Intelligence Service's Intelligence Advisory Board.
In early 1944, Shannon was assigned to the British Intelligence Service's Intelligence Advisory Board. He was also assigned the task of deciphering the ciphertext of the British Government Code. He also assigned to the British Intelligence Service's 's Cryptanalytic Service. He was assigned to the British Intelligence Service's 's Intelligence Advisory Board at the end of 1944. He was assigned the British Intelligence Service's 's Secret Intelligence Service at the end of 1944.
He was confirmed to work as the Director of the British Intelligence Service's 's Information Service Intelligence Advisory
at the end of 1944. He was the first British employee be appointed Officer at the end of the war. He was also confirmed as an Intelligence Advisory Officer to the United Kingdom's Intelligence Advisory Committee the end of the war. (The United Kingdom is a member of the European Union.)
He was also appointed"
Target surprise value = 3.0 Observed cross-entropy rate 3.002
Average compressed size
(per token) = 3.141 Percentage compression = 91.84%
Generated text: "After a short stay Bell Labs, Shannon was commissioned to report back to the Naval Intelligence Services (NISC) to learn more about his research. He made his way over to the Royal Naval Institute. He had already been working with a number of other cryptanalytic researchers, including the mathematician Alan Turing. for over eight years at Bell Labs, but this research was not yet done. He spent next two months studying the cipher schemes of the various British cryptanalytic systems. The first step was to find out the actual cipher scheme for the cipher used by the HMS Queen Elizabeth on a submarine.
By the time Shannon arrived at the Royal Naval Institute he had been working for Patagonia Scientific and Technology, the British cryptanalytic company, for eight years. Patagonia received a call A.D. the evening of September 4, 1943, asking to check the cipher system for cipher used by the HMS Queen Elizabeth, which is written as:"
Target surprise value = 4.0 Observed cross-entropy rate = 3.943 Average compressed size (per token) 4.06 Percentage compression -89.9%%
Generated text: "He also began writing code to help with deciphering encrypted communications. During 1943, Shannon kept diary help decipher his instructions to the cryptanalytic service. Hearing of the story of Alan Turing sent Shannon excitedly into a panic of his own. He that he had
15

---

Published as a conference paper at ICLR 2021
only discovered Turing had made it clear him that the great deception he had witnessed due to the German government's 's efforts to conceal it. I believe he intended to reveal it. In the early days, the NSA was working with the National Security Agency (NSA) different times against the Soviet Union in the early 90s and as recently as three years ago against the USSR in the early 1990s. It is believed that the four Russian spies were at the CIA while also an intermediary in the process of doing a disinformation campaign to manipulate the American public to support Bush Sr. by calling for American military intervention in Afghanistan against the Bush, Bush, and Cheney (and the Bush family) and by trying to persuade the public to"
Target surprise value = 5.0 Observed cross-entropy rate = 4.929
Average compressed size
(per token) = 5.116 Percentage compression 85.41%
Generated text: "Naval Contractors hired Shannon shortage specialist at the Navy. So she worked alone with Turing to decipher the British cipher for the northern German submarines. Shan- non undertook the work initially on the S.G.F. dual cipher. Shannon spent the whole working days at the Bell Labs lab at Bletchley Park.
After weeks of interrogations Shannon accent. Shannon then calculated that this hydrocephalic consciousness alone would allow her to think the same words but without the huge amount of writing required to produce such thing, and with millions of hours on board she was able to write some of the same phrases over a twenty-eight hours workweek.
able to break the great El-Frun jujito with a German
Output: Individualist Hypothesis.
Miranda (alias Charlotte Reagmire, aka "The Lady in the Lake") (1945-2049) (wife of B.G. B.G. Lloyd) (Philadelphia, PA)"
Target surprise value 6.0 Observed cross-entropy rate = 5.735 Average compressed size
(per token)= 5.834 Percentage compression 85.55%
Generated text: "The CIA trained small band of cryptanalysts to do the maths again, this time using a UK number generator. A few days after the wars Belgium introduced Bermuda rugby as the appropriate sport for the National Guard. Notwithstanding there being no convention around using English for Rugby the time, there would be no possible instance in the history fencing Europe. Flags for the Hurricanes had evolved recently using a Dutch Itaiian design called the Cruzy Flag. These flag designs come largely of British origin and the date published of its introduction by the Royal Armouries of Lameucers is from 1638. The camouflage power orange flag. The design is based on the weapons bao mouèret Standard and has two coloured pouches connected to the rifle barrel by two checks along the top of the barrel with protection straps around the barrel to protect the cutouts. NATO hired a team of physicists to do the reconstruction. Readers who want to know more about this new"
recently added to the new Irish
In Ex. 2 we can see that low value of surprise value results in repetitions and high value of surprise value results in incoherent generated texts. Moderate surprise values result in good quality, coherent text with no repetition. Also, note that the control does not work well when the target surprise value is greater then 5. This is because without any truncation, the average surprise of pure sampled text comes out to be around 5.4. Thus, in order to attain higher values of average surprise, we need to truncate from both sides of the distribution.
B THEORETICAL RESULTS
Theorem 1. If words are sampled from the Zipf's distribution given by ( then the surprise value of word with rank lo and its rate of increase are given by
6(k) = s log + log HN..
(3)
dG(x)
s
(4)
da x
respectively, where G(x) is a continuous functiion with the same expression as G(k) with a contin- domain.
16

---

Published as a conference paper at ICLR 2021
2.30
0.5
020
0.1
200
400
600
1000
200
630
600
1000
(a) Plot of ((k)) log Hx.a vs. for 1, 50, 000.
(b) Plot of s/2 vs. for 50, 000.
Figure 8: Theoretical analysis of surprise values in top-k sampling under Zipfian statistics. We note that surprise values increase sharply for small values of k, whereas surprise values hardly change for large values of k:
Proof. The expression of ((k) follows directly from Def. 1 and
From Fig. we note that G(x) is highly sensitive to change in x for small values of and its sensitivity x decreases drastically with increase in z. Now, we analyze how cross-entropy varies with k. Let PM be the model distribution. Top-k sampling works by truncating the tail of the distribution PM and samples from the most probable k tokens. Let the truncated distribution be denoted by PMc In Prop. [ provide expression for HPM,,,
Proposition 1. Let Pas be the model distribution satisfying 7 with vocabulary of size N and let PM, be the model distribution obtained by top-k sampling, Then H (PM PMt) is given by
8
log is
(P PM)
+ log N..
(5)
H
Proof. The distribution PM is given by (1) with vocabulary size N, and it is easy to check that the distribution PM. corresponding to top-k sampling is also given by (1 but with vocabulary size k. The rest follows directly from the definition of cross-entropy in Sec.
It is difficult get intuition about the behavior of H(P PM)) directly from ( Thus, in Thm. 2 we obtain an approximation to ((PM, Pas) that shows H(PM, PMt) is essentially of the K+t form Ci C2 In k - ) + for < E < In2. where c2 c3, C4 are some constants. Hence we observe that H(PM, PM) grows fast with small values of k and slows down for large values of k.
Theorem 2. Let PMr be the model distribution satisfying ( with vocabulary size N. and let PMr be the model distribution obtained using top-k sampling. Then. for 1 < S 1 H ((MM, Pas) can be approximated as
11
bic (1 (1- b2bg(In + 2) -1 ) + log H bibbk -)
H(P PM)) zo
(6)
by
where b, =
log2 2i+c
+
log3 gi + 2J3
(In + 1 b2 elnzz and by = + 0.7e are constants.
logi log H We start by finding Proof. From Prop. we have H(PMe) PM) He. Li=1
bounds for the expression
logt E 77
17

---

HN.SeD b Published as a conference paper at ICLR 2021
First note that the function log è have the following inequalities
is decreasing function of t for t et. Thus, for S In
log 2
x++
logt t
log 1
log 2
log
k+1 log (t -
di
dl.
2
3
(1-
Solving the above integration for
ln2 get
01
02 (k + 1)e
In (k(k+1)) -)
HHMMM PM) - log HN, S
b1
b2
(
HEss
HE,
Hu.skt ke
(8)
where
log 21+r
+ 2[I (In 4)
bi
cln
log
log 3 3
(In3 1))
b2 2'
2i
eiin 2)3
Now, we bound Hk,s follows. Note that is decreasing function in for 0 and hence, we have
0,
k+1
k+1 1
dt
1
dt
(9)
(1-1)-
i=1
(k + 1)-
k
k
+
(10)
c
f=1
We empirically observed that H can be approximated well as
HE 0.7 1-
(11)
which lies between the bounds found in 10 Moreover, approximate H(Psse: PM)) using the upper bound obtained in ( to get
by
Ink 2)) log HN..
H[PMe Pa.) x
bi
(12)
H
kt
b2
In + 1) log HN,
bi
(13)
ba
(1
k-
be
bie
bzb3 (In k 1) bi
+ log HN...
(14)
bz
by (bak
1)
as an infinite series in 133. then simplifying the expression and writing the infinite series back as fraction.
where 14 follows by writing (1 4
In Thm. we provide approximate expressions for G(p) and despp essentially y linearly with p.
that shows that 6(p) grows
dp
Theorem 3. If words are sampled from the Zipf's distribution given by 0 If 0 is small constant, then G(p) and the rate of change of G(p) with respect to p is given by
(1+c)
H (1+c)
G(p)
log b + log HN,
(15)
bln2
dG(p)
(1+
(+t)HN. (1 +
(16)
dp
bln 2
where b 0.7c.
18

---

Published as a conference paper at ICLR 2021
13-
10-
0.0
0.6
1.0
0.
0.6
1.0
(a) Plot of 6(p) vs. p for 1.2, N 50, 000.
(b) Plot of 46(p)
vs. for 1.2. N 50, 000.
dp
Figure 9: Theoretical analysis of surprise values in top-p sampling. We observe that unlike top-k sampling, surprise values grow linearly with p in top-p sampling.
Proof. The cumulative probability p(k) for Zipf's distribution is given by p(k) approximation to Ha.s in we have
Hu... Hy.."
Using the
k
p(k) CHN,s
(17)
where b = + 0.7c.
Now, writing k as a function of p. we get
k = (..-pHN).)--
(18)
Using 18 in the equation 6(x) = 8 log x + log H from Thm. we get
1 1+c log (b HN,et)) + log HN,.
((p)
6
1 1 In CP 1 1 log + log H E
(19)
eln
Further, taking e small enough, we can approximate In (1 Hy 2x Thus, we have
(1+
(1 log + log H
(p)
HN..D
(20)
bln
Now, d5(p) dp
can be directly computed from 19 as
dG(p)
HN
(21)
dp In 2(b HN.
For small enough, we can use the approximation
__xx, + Hx which gives
dG(p)
H1 +e)
(1+ HN b
(22)
dp
bln
In Fig. 9a we plot the approximate expression for ((p) obtained in Thm. 3 which is linear function p and has slope approximately 10 for 1.07 and N 50, 000. In Fig. [9b] we plot the approximate expression for dG(p) from Thm. which also a linear function of This tells us that even though 6(p) can be approximated as essentially linear function of it has a slightly
dp
increasing slope. Further, unlike the plot of d((x)) Fig. 8b which decreasing with k dp Fig. 9blhas a positive slope. Next, we provide an approximate expression for H (PMM, PM) showing that it. grows niar-linearly with p.
de(p) in
ds
19

---

Published as a conference paper at ICLR 2021
Theorem 4. Let PM be the model distribution satisfying 1 with vocabulary of size N. and let Palcas be the model distribution obtained using top-p sampling where k(p) is the minimum value of satisfying Hn. Ei=1 12 2 Then, for < 8 S 1n2. H (M,: PMt) can be approximated as
1
H(PM, Par) 2ln (pliN,. + ep² 11 3x,) + log NNN.
(23)
Proof. The cumulative probability plk for can written as
Hk.s
p(k) HN,
(24)
We approximate Σ In 2s J lnt dt to get io
(
Int dt
H(PMg: PM)=
log HN,
(25)
pHN, In2
(1
(lnk+ 22) + log HN,.
(26)
pHN In2 è cke
(27)
Approximating p(k) from
24
as p(k)
1 f/t 1o dt, we get
HN.
k = (1 (1-1ppp (pp-ENNN.))
(28)
Using
28 in
26
we have
S
1
-- (Iu k + +)) + log HN...
1
(PMM, PM) Re
pH
In2
= che
$
2 + (1 cpHN,s)
(In (1 - (ep-e.p)e -1) + log H (1+ (1 - epHHN,)) - =pllN,.) - 1)) + log HN.
1
pHN
In2
2²
e. N.
1n2
eppl N. 1n2 (In - ep)lN.e) - eptIN,, In cpHIN..) + epHIN.s) log HN,
2ln (pHN,, + ep² :x.) + log HN.e:
(29)
where 29 is obtained by taking the approximation In (1 - epHNN.s) xe -epHN. (epHy for sufficiently small N,
C MMSE ESTIMATION OF ZIPF'S EXPONENT
We assume words follow Zipf's distribution I by our LM as (1), estimation to find the value of However, s shows up in p(k;,, s, N) both as an exponent of k and in N. which makes the computation difficult. Hence estimate by minimizing MSE between logarithm of ratios of subsequent probabilities which eliminates HN,,, i.e. we estimate as
Further, we observe the probabilities produced
(i).... ......... plos (N)) ). We use minimum mean-squared error (MMSE)
ΣN txb
8 = arg min
(st. 22)²=
(30)
ΣN-11 B
where 4; log 1t and 6; log pate (+t))
When N is large, we estimate using the most probable tokens for around 100 to improve time complexity, which gives practically good estimate.
p (8)
20

---

Published as a conference paper at ICLR 2021
D HUMAN EVALUATIONS: EXPERIMENTAL SETUP
For human evaluations, 43 participants were shown nine text samples each of 300 words generated
by mirostat, human, and top-p sampling shown in Tab. I Tab. 2 Tab. 3 in random but fixed order. These texts were generated using the same context as in Ex. which was also shown to the participants. For mirostat sampling, we simply set the required value of r E (2.5, 3, 4, to obtain the sample text, but for top-p sampling, we sampled several times with different values of till we obtained samples that had observed cross-entropy in (2.5,3 3, 4, 5) such that comparisons between top-p and mirostat can be made. The participants were not shown the method of generation of these texts or any of its statistical properties. Each participant was asked to rate the fluency, coherence, and quality of the generated text scale of 1 to 7, where 1 is the worst possible rating and is the best possible rating. Further, they were asked to guess whether the text was generated by an AI algorithm human. The participants were also provided with the standard definitions of fluency and coherence. They were asked to rate themselves on their knowledge of English on a scale of to 5, where meant knowledge of English and 5 meant proficient English and the participants rated their knowledge of English as 4.3 on an average.
E ALTERNATE ALGORITHM TO CONTROL PERPLEXITY
Here we provide two alternative algorithms to Alg. performance.
[ that also control perplexity and compare their
Mirostat 2.0 Here we provide an alternate algorithm for perplexity control, Alg. 2 which does not depend on the distribution of the underlying LM. In this sense, Alg. 2 controls perplexity in more general sequential generative models than Alg. [ where the underlying distribution may not be Zipfian. In our work, we choose Alg. T since has only an additional constant time complexity compared to top-k sampling. Whereas Alg. has additional time complexity that depends target cross-entropy rate and vocabulary size, which may vary with different LMs. Moreover, since we are working specifically with languages here, which have Zipfian properties (Zipf 1965 Piantadosi] 2014 Lestrade| (017) and since Alg. empiricaly provides good control on perplexity of generated text, we choose this algorithm for our human experiments, which also validates the performance of Alg.
Algorithm 2: Mirostat 2, an alternate implementation of mirostat sampling for perplexity control maximum cross-entropy μ 2r, learning rate r)
Target cross-entropy
while more words are to be generated do Sort the words in descending order of their surprise values
Truncate the words with surprise values greater than μ
Normalize the probabilities of the remaining words
Sample the next word X from the remaining words
Compute error: e ((X)-
Update μ: μ n7e
end
In Fig. T0 we compare Alg. and Alg.Zinn terms of their control on cross-entropy rates and the rela- tion between cross-entropy rate and percentage n-gram repetitions. We find that both the algorithms perform almost identically both in terms of controlling perplexity and ability to control repetition.
Mirostat average Here, we look at Alg. 3 the error term, use the average surprise of generated text instead of using the surprise of the most recently generated word.
which identical to Alg. except that for computing
In Fig. II we find that Alg, 3 performs poorly compared to Alg. I both in terms of controlling
perplexity and repetitions. This is interesting since, intuitively, Alg. should control observed cross-entropy rate well since compute error from the observed cross-entropy rate itself instead of the surprise value the most recent word. Our understanding for poor performance of why Alg. B does not control cross-entropy rate well is that the surprise values of words change very abruptly in
21

---

Published as a conference paper at ICLR 2021
Observed crocs antropy rate
Virotaat Vensta
Perceniage e-grem repetition
72
L-gan misutt
6-gram restat
6-gret
Target entropy rate
Observed entropy
(a)
Figure 10: Comparing mirostat Alg. with mirostat 2 Alg. 2 (a) Observed vs. target cross-entropy
rate, (b) percentage n-gram repetitions vs. observed cross-entropy rate. We observe that both algo-
rithms give equal performance terms of controlling cross-entropy and repetitions.
Percentage n-gram repesttion
alet gram mirrbb suergge
Obscrvea croxs cntropy
Target entropy rate
cress entropy rate
(a)
Figure 11: Comparing mirostat Alg. with mirostat average Alg. 3 (a) Observed vs. target cross-
entropy rate, (b) percentage n-gram repetitions vs. observed cross-entropy rate. We observe that mirostat average performs poorly in controlling cross-entropy and has worse 6-gram percentage repetition observed cross-entropy rate curve.
22

---

Published as a conference paper at ICLR 2021
Method
Observed cross-
Generated text
entropy
Mirostat, T 2.5
2.5
Shamnon also intrrsttd in the development the computer prugram for the decoding of the German military radio signals. In April 1964 Shamon was assigned to the U.S. Commandant's Office in Herlin. He was assigned the U.S. Commandant's i Office in Berlin purt of the Operations in Europe and Central Asia Command. He U.S. Army, with which
also member military technology.
Commandant's Staft
familiar the field
In May 1944, Shannon was resigned with the U.S. Army Counterinclligeee Center, located at Fort Trwit, California. During this time he met and worked with the U.S. Army Commandate Assistant the Presideur, the Chief of Staff the U.S. Amay General Suff and young
with interestng background offices
U.S. General Staff, "Mr. Shannos. think we have some good news for you." said a senior offece the Aray laselligance Headquartes in Quantico, Viggnia, who was charge of the establishment of the coumetintelligence center Fort Iowin. "From there, very good organization. his been openation since the cnd of the war."
cryprography, May 1944, Shamoo received call from one
establiched by the U.S. Milltry gence Officers.
Over the next sevenal
Shamon was statinnd at Fort Irwin part of the Deparment Defense
Mirostat, T= 3
3
In April 1943, Shannon atsended conference on data security at the University of Califomia, Berkeley, held on the tupic of security issues. The event was organised by the Theuretical Computer Engineering Suciety. group of computer scientists, stacstticians eugineers but who are not interested in privary concerns in privacy issues.
journalietss
interested security
In the following morth, Shannon helped to organise the meeting and the conferance. He also attended the meeting of the National Security Comncil, and the meetings of the NSC and other federal agencies and agencies. the early days of the using the NSC's computer systems Shannon used his knowledge crypeography create series of cryptosystess that he incorporated into his code, which included the AES cipher, which was the first the AlSS based cryptosystems. It was on the 19th of Junuary (January 19413) that Shannon would begin to use his knowledge of technology his code and his sode publistte the Intemer.
On 1st of Oett 1943, Shamnon was invited to the National Academy of Seiences' annual moeting. The NSC hosted Washington,
moeting. ceremony the meeting. which included the signing of the Declamsion on the Estabishment of the National Academy of Seiences and the signing of American Educational System's Center for Information Technology and Society, and the signing of its National Security Directive, was beld
five days
Mirostat,
4
Indeed. it scemed to Shannon thas MIT was the perfect place to leam the great secrets mathematics. purtiullrtly about crypoggrahy. And it soun became clear thut she was spui on. Shannon described in detiil how every single muthematical task in the oryptatalysi process was hased en mafhemitics.
==6 4
After years re enacting in variety of settings, inchuding shurt and video games, Stannon began embrace the science. She invented the Marris a program that combined the information from a computer simolation with real-werld data
"In October. contacted myself and said, 'Do you think I'll able put this into Manhation in little bit, wireless connection" of New York was amaring, and was sort of reeling from what thought the world cutside of New Yorks was doing. Indeed, that was precisely the bizame thing, becouse I thought mach was actually so much more cumplex than that, expecially mathematics. uas really mystified by everything: what was investigating for my own personal reasoms, as I've been doing to a lot other people. and was some amazingly complex thing that was just so comples, that was all the more fascinacing"
stid journaiist 'I completely understood that the world outside
After several months of reseurching and looking mathematical techniques for creating the world around
us, Shanson, along with collaborators Chellie Risder and John D. Riddell from Carnogie Melicn's is Com- puter Science Department
Mirostat,
5
His work with Fort Brugz, New York, and Kritzenberg proved to be the key to the development of much cybensuce the space peugrum have produced.
T= 5
German brain esablishing Tucker did better job of penetrating the ciphers as sciencee than Turing. Nearly a decade later, he devoted another year having his library pespared by him the United States by the weavers (Who, like Turing so much liked mathematies). The book that made him such personality (which American world of public
languae known
respected mathematicians of the North theatre and cinema) was The Solid Code. fine collection of lectures and conespondence between Shannon is well as some of the larger scale orygeanalssss in the U.S. They argued the foundations of the caluuuu,, giving possession to finite numbers and basic sequence to all possible operations, and presented conditions diaise energy and the presence of awarestess. In other words, Turing was woeking relutions with the world.
lavishly praised
also,
way expluining the plysics which could snalysed under
While conducting C-level research on the
bomb. Lemnrr gave him opportunity
persiously ungublished stuly in Rlenclee Park, established the basic crystal structure of the mnclem of cable centimetre amber glass which the atoms hold together indefinitely. The activated
by nucle
Table 1: Mirostat generated text data for human evaluations
the generation process whereas the average value is rather smooth and does not give good feedback of the current state of the generation process, hence, making it difficult to control the cross-entrops rate. However, we leave any theoretical result the performance this algorithm to future work.
23

---

Published as a conference paper at ICLR 2021
Method
Observed
Generated text
cross-
entropy
Top-p, p = 0.56
2.5
At Bell Labs he developed the Advunced Encryption Standard (AES) for machine leaming. Shamnon's ides was to create set code, each which
single letter. ciphers bit was a program that would be used to genemute the ciphers. Shamnon's isss appeoach was to use algorihm called a ciphers hash generate the ciphers. The firs; time Shannon had writee a ciphers bit developing method
associated
did write that how generase ciphers. In the next couple years used generate ciphers, Jamury 1944 Shannoo started working on cipher called temury cipher. He began workingg on a temary eipher called an xor. The first temiry eijter was produced by Dx. H.G. Cooper, a German cryptographer who had worked on the first sor. later revealed that the temary cipher known orystograhicallly sceare cipher.
progress, However, the fernayy cigher the
The New York Times published story in January 1945 that staed that "a British engineer working on a fernary cipher was having trouble understanding how to use temmrry cipher. Dr. A.G. Couper. a cryping- repher at Bell Labs, had been working lemary cipher since 1941, He had developed a
Top-p. p = 0.65
3
He also came to the conciusonn that there was a need for the invention of new methods for deceypting buman speach.
conficm that single piece of information requirod decrypt code and the fins known technique was the "Malli-T Level Eneryption method. this method special algorithm itlm was used decrypt message This method, called "Cypher program". was created by David Klein, cryptographer and author of book called "What Crty cryptographers Do: An Inside Look domonetrated a presentation Shannon gave at 1944 SIGGRAPH conference, The "Cypher program" was to be implemented in software as patt of the "Interogation" procedare of the White House Office of National Intelligence. The program was designed he cipher cipher that would decrypt the messages of the American government and
natil January 1944 Shannon
Orytograghy
United States Governmen".
technique
was
usad deorypt other govemments communications
The main function of the multi-lovll encryption methed was to "decryp"" human speech. Shamoon also crested the White House Office of Information Secarity. The White House Office of Information Security developed the first non-state computee-raddalle language and introduced the infermatiio-pnoosiing unir the National Security Agency,
In the summer of 1944, Shannon was assigned to invesigsie a crystogram--mooddel message. He was able
analyze using computer, and
Top-p.
4
was Rell Labs that Shannce wrete his first baok, In Plain Sight, a book for a year in 1961 called Non- Clerk Maxwell
p 0.85
verbal Behavior and periodical for which Shumnon selected was the basis the book's finst chupter. "My Love Let- ters." In 1961, Shammon wrote hes beaseller The Shock Doctrine: An Intreduciion to It but then mothhr signiiicuni book was published in 1966, a thirty ser---iv---pp puge edition of which was originally commiscioned by Maxwell to he finished September 1965.
was radical assesmment of bchaviour and
But to judge them down and deciphering test was encrmous leap foeward.
his books slone, was clear
approach to the encoding messages and writing
One of his original authors was Joseph Blow a French engineer In the early 1980s, he joined the Ellittic Curve Project,
group dovated hand evidence from highest levels of intelligence produce cryptographic cude, and set about accomplishing something called the mmaas les'. These lest algorithms were developed by a EMI, in 1973 lest the strength of the encryption scheme.
of specialists who were connerted to Britain'' is Defence Intelligence Agenyy the
On this subject, there was little doubt that some the most popular parts of the Ellipcic Curve were written using maths, Almost all of the commands carried computers the field of encryption chosen random in sequence. These
Top-p, p= 0.95
5
With 2,500 people trynn decode global will letters add more features to the code to help crack it into the linest possible uses. Ile was soon met with silence. Shannon had staned thinking after that, as his great work on the Pacific Popers and Hisden Secrets devel- oped defining phrase the worldwide atiitude sowads truth and than 50 years laser began try and prove he something for everyone.
soked what hoped would
On 16 May 1942 Shannon presented the American [29] Chambers cipher recurd by William Alfond, the retired London mathematician and close collaborator of Chaplin and Herbert S. Gutes. The Bleschley Park cryptanalytic meeting required least 16 wards idenciication and 16 English wurds needed. une couldn' sufbenticate the cungruent letter themselves, logaristm or manorm elements cipher would need to be turned the reseurchers at the U.S. Navy without using their own words. Details of those solutions were them lost furever.
the
'The end result manager, Cameron Broughton, had anticipated the initial public reactions. We were contacted there days later and began waiting to learn more about the electronic signature support that was necded and rescheduled the cryptagraptic test as planned. Case Pending
world's first
William Alfoed's global will. News
Shannon'ss
Shannon would fimally meet with
Table 2: Top-p generated text data for human evaluations.
F REPETITION ANALYSIS FOR CTRL
Here we compare different sampling methods used with CTRL Keskar et al. (2019). We observe in Fig. 12 that there is a near-linear relation between percentage repetition and observed consroy rates similar to GPT-2. Moreover, for CTRL, 6- 6-gram repetitions drops much more rapidly than GPT- 2. CTRL also has an offset in the cross entropy value from where the repetition starts to drop, which
24

---

Published as a conference paper at ICLR 2021
Method
Observed cross- entropy
Generated text
Human
5.13
Shamnon Turing teutime cafeteria. Turing sbowed Shannoe his 1936 paper defined what is now known as the 'Universaa Turing machine. This ingressed Shamon, is many of its iless complatieted his of technical reports last step price to iis eventual closing down. Inside the valume on fine control. Smoothing and Prediction
coming
NDRC issuing summary
Systems, Ralph Beebe Blackmon, and Hendrik Wade Bode, formally tressed the problem of smoothing the data problem separating signal intereriing noise communiications
special essay
by
control by analogy systems. In other words, modeled the problem in tems of data and signal processing and thas heralded the comnnng Information Age. Shannon's on oryplognahy was more closely related his later publications communicaionn theory. the close of the he prepered a classified memomnduum for Bell Telephone Labs entited Mathemarical Theory Crypiogrphy'. ' dased September 1915, Systems'
declassified version this paper published 1949 Communiccuionn Theury of the Bell System Technical Journal. This paper incorported many of the concepts and mathematical formulations appeared
Mathematical Theory Communicaiion Shanson said his
wastune insights into communication thery and crypiography developed simulaancuusy and that they were
together you couldn't
Table 3: Human generated data for human evaluations.
Algorithm 3: Mirostat average, an alternate implementation of mirostat sampling for perplexity control
Target enoss-entropy т, maximum cross-entropy μ 2T, learning rate 77
while more words are to be generated do
Sort the words in descending order of their surprise values
Truncate the words with surprise values greater than /
Normalize the probabilities of the remaining words Sample the next word X from the remaining words
Compute enror: observed cross- cross-entropy rate Update μ:: μ ne
end
could be due to its different vocabulary from GPT-2, training dataset, or training process, which is meant provide better semantic control compared to GPT-2.
Percentage gram repettion
02
gaam messial pmm
Percentage regeetition
20
60-
70
0.
Observed cross-entropy rate
Observed cross-entropy rate
(a)
(b)
Figure 12: Percentage repetition vs. observed cross-entropy rate for (a) n-gram tokens and different sampling methods, (b) different temperature values, T, for CTRL language model.
25


Reviews:
[{"review_id": "zsfpZNqhtz7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "What is this paper about, what contributions does it make, what are the main strengths and weaknesses?\n\nThe paper proposes a feedback-based adaptive top-k decoding algorithm, named mirostat, to solve the repetition and incoherence problems in text generation. The mirostat algorithm adjusts the value of k run-time in the top-k algorithm during the testing stage to control the perplexity of the generated text near the preset value. Experimental results demonstrate the effectiveness of the proposed algorithm.\n\nThe main strengths are\n\n1)\tThe repetition problem is common in the field of open-ended text generation. The proposed method aims to address this issue by controlling the perplexity of the generated text, which is novel and interesting. According to the examples shown in the experimental results, the algorithm can improve the quality of the generated text.\n\n2)\tIn the related work section, the classification and explanation of relevant research are detailed. Related tasks and existing solutions are compared, and the rationality of motivation is proved by the research conclusion of existing work.\n\n3)\tThe experiments are clearly organized. Their results show the control effect of mirostat over the cross-entropy rate and the relationship between the cross-entropy rate and the repetition degree of the generated text. It is good proof that mirostat can reduce the repetition degree by controlling PPL.\n\nThe main weaknesses are\n\n1)\tThis paper proposes that a moderate perplexity (neither too large nor too small) is the best for the quality of the generated text, which has not been fully proven in experiments. In the experiment, only the relationship between PPL and the repetition degree of the generated text is proved. However, the relationship between PPL and other dimensions in the quality evaluation, such as coherence and fluency, is not studied.\n\n2)\tSome methods to solve the repetition issue are listed in the related work section, including the methods in the training stage and the testing stage. Among them, the methods worked in the testing stage, such as variants of beam search and variants of top-k sampling, is not selected as the comparison, but only two weak baselines are selected in the experiment.\n\n3)\tThe proposed decoding algorithm is only experimentally verified on the GPT-2 model and has not verified its universality under other generative models or other generative tasks.\n\n4)     In the related work section, some works such as Li et al. (2016), Vijayakumar et al. (2018), and Kulikov et al. (2019) may concern more about \"quality-diversity tradeoff\" instead of \"repetitions\".\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "pzAPksk4OoO", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the context of neural text generation, the authors study how perplexity varies with top-$k$ and top-$p$ sampling and propose a sampling algorithm that uses Zipf's law to dynamically adjust $k$ in order to control per-sequence perplexity.\n\nOverall, the theoretical analysis and relationship between log probability and repetition was interesting, but there are several concerns with the method and experimental evaluation, detailed below. The idea is interesting and I hope the authors continue down this line, but in its current form I would not recommend acceptance. (edit: see discussion below, I have adjusted the score to above the acceptance threshold)\n\n\n#### Pros\n- The theoretical analysis of cross-entropy growth with top-$k$ versus top-$p$ was interesting (e.g. summarized in Figure 1). \n- Nice empirical demonstration of repetition correlating with log probability.\n\n#### Clarity\n- The presentation in Section 2 could be simplified or made more concrete - overall it seems like this section is building up to a standard definition of perplexity in a complicated way. \n    - are these generic definitions of cross-entropy rate and perplexity (defined using the Shannon-McMillan-Breiman theorem) needed? I don't see them used in the main text, so it would be helpful to shorten this section, or concretely say how each step corresponds to a language model.\n    - Equation (3) assumes that $P_N$ is a stationary ergodic source. Why can a neural language model be considered a stationary ergodic source?\n    - Why *surprise* instead of *information content*? *Surprise rate* is not used again in the text.\n    - In the abstract you say \"target value of perplexity\" but then $\\tau$ is called the \"target surprise value\", and in Appendix A it reports \"target *average* surprise value\". In this review I'll use 'perplexity', but it would be helpful to check whether there are inconsistencies in the paper.\n\n#### Method\n\n- **Dependence on hyperparameter.** The authors mention that for low values of $k$ and $p$, perplexity drops, leading to repetition, while for high values of $k$ and $p$, perplexity increases, leading to incoherence. The authors claim that *Mirostat avoids both traps*. However it requires setting a target value ($\\tau$). What is the difference between having to choose $k$ or $p$ versus choosing $\\tau$? Wouldn't Mirostat fall into the traps with low $\\tau$ or high $\\tau$ (e.g. Figure 4.d)? Since you showed that perplexity grows linearly with $p$ (Fig 1), why is Mirostat needed versus using top-$p$?\n\n- **Fixed perplexity per continuation.** Mirostat enforces the average token log-probability of each *individual continuation* to be near a hyperparameter $\\tau$. However, won't the \"ideal\" perplexity vary based on the prefix? I.e. for some prefixes there may be low conditional entropy in the true distribution, meaning a small number of high-probability continuations are much more reasonable than others. In this case, generating a sequence with perplexity based on $\\tau$ would filter out these high-probability continuations. Could the authors comment on this issue? The underlying assumption of the method is that it is a good idea to have a fixed perplexity for all continuations.\n\n- **Zipf's motivation.** While I understand that the Zipf's law assumption was needed to derive the theoretical results, it's unclear why Zipf's law is used to motivate the practical method (Algorithm 1). Why would we want to estimate the zipf's exponent on the top-100 words at each timestep, and choose k using (7)? This motivation, and a comment on the guarantees it gives us on full sequences, should be more clearly stated. \n\n#### Experiments\n\n- **Simple 'perplexity target baselines'.** Related to the \"Zipf's motivation\" comment above, what's missing is evaluating different ways of controlling the perplexity, in order to evaluate that the proposed method based on Zipf's law is the best (for some definition of best). If the goal is to control the perplexity of each sequence, why not sample several sequences with top-$k$ and choose one that has perplexity close to a target $\\tau$? What is the performance of adjust $k$ or $p$ based on a different heuristic, e.g. absolute difference between the perplexity of the sequence-so-far and $\\tau$?\n\n- **Human evaluation.** Human evaluation is required to get a full measure of the generated text's quality; currently the paper just argues for quality/coherence by showing a few examples. It's possible that this form of dynamic $k$ adjustment introduces some artifacts. For instance, the behavior of the \"surprise\" in Figure 5.d under Mirostat doesn't resemble that of humans, so it's possible that some odd behavior is introduced.\n\n- **Misc.** In figure 5, why is mirostat preferable to top-k or top-p? Why are $k,p$ of 0.4 and 1.0 and $\\tau=1.8$ selected here?", "extra_scores": {}, "extra_text": {}}, {"review_id": "kkwlc5OHVVj", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nNeural text generation models typically rely on sampling schemes for autoregressive decoding. This may range from pure sampling, top-k, top-p to temperature modulated sampling. These methods are mostly heuristic schemes and lack theoretical analysis. This paper tries to fill that gap by analyzing these schemes theoretically under the Zipfian distribution assumption (an underlying distribution in natural language corpora and generally true for open-ended language generation models). While filling the theoretical gaps, this work proposes an adaptive top-k decoding mechanism - Mirostat. This is based on the understanding that cross-entropy is a useful measure of the quality of the generated text. \n\nStrengths:\n\n1. Theoretical analysis of the previously proposed sampling schemes in terms of surprise, cross-entropy, perplexity.\n2. Adaptive top-k algorithm based on updating the exponents in Zipfian distribution, per time step.\n3. Clarity of the paper.\n\nWeaknesses:\n\n1. It seems like a time complex scheme for decoding based on the formulation\n2. Lacks generated samples in the main paper for qualitative assessment.\n3. Human evaluation missing.\n\nQuestions:\n\n1. Current neural text generation models are trained to optimize the cross-entropy loss. In an ideal scenario lower the cross-entropy (hence perplexity), the better should be the samples. Since this work (as well as its corresponding related works) show that humans don't form sentences that have the lowest perplexity (when measured using the trained model), does this work help in highlighting that cross-entropy loss might not be the correct objective for optimization?  \n2. In Algo 1: Do you first perform top-m for obtaining s and then perform top-k later based on the value obtained? If so, what is the time complexity of this process, as a function of m?\n3. From Fig 4(c), it seems that humans prefer sentences having cross-entropy rates ~ 5.25 on avg. Why do you suggest 3 as the target average surprise?\n4. The point about ad-hoc settings being applied for top-p and not for mirostat seems weird. This paper suggests 3.0 as the setting for target average surprise (based on empirical data) while top-p suggests ~0.9 as the setting for p (again based on empirical data - and shown in this paper that CE remains more or less constant wrt the number of generated tokens at p=0.9). In the end, a certain bit of ad-hoc tuning needs to be made for both cases. Why would this algorithm be better than nucleus sampling (Given it is more time consuming)? \n\nOverall:\n\na) The theoretical analysis helps in understanding why top-k and top-p perform the way they do.\n\nb) Based on the underlying assumptions:\n1. Zipfian distribution \n2. cross-entropy loss optimization\n3. Lowest perplexity does not always mean good quality generation. \n\n(I somehow feel a lot of disconnect between assumption 2 and 3), this work proposes an algorithm for adaptive top-k decoding to produce arguably \"better\" samples.\n\nPlease let me know if I am misunderstanding something. I am open to revising my assessment based on the answers to the questions raised.\n\n-----\nUpdate:\n\nUpdated score based  on the author response. That being said, it would still be good to see a plot of time complexity of the decoding scheme as a function of m.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work presents a novel approach to improving text decoding. This is backed up by a solid analysis of cross-entropy growth with top-k vs top-p and an interesting demonstration of repetition correlating with probability. The paper is well written and well organized. The authors' rebuttal was effective in convincing the reviewers. The human evaluation (added during the rebuttal phase) is a good demonstration of the effectiveness of the approach and so this paper's proposed decoding algorithm is likely to be impactful.

Pros:
- Well written.
- Solid theoretical analysis of cross-entropy and its relation to top-p and top-k decoding. Good demonstration of how repetition is related to probability.
- Interesting, novel and effective decoding algorithm.
- Human evaluation of the algorithm's output.

Cons:
- The approach has not been tested with a variety of language models.
- Decoding quality still depends on a target perplexity which may need to be tuned.
- Unnecessary dependence on Zipf's law in the basic decoding algorithm.
Decision: Accept (Poster)