Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

Overall, 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)


#### Pros
- The theoretical analysis of cross-entropy growth with top-$k$ versus top-$p$ was interesting (e.g. summarized in Figure 1). 
- Nice empirical demonstration of repetition correlating with log probability.

#### Clarity
- 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. 
    - 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.
    - Equation (3) assumes that $P_N$ is a stationary ergodic source. Why can a neural language model be considered a stationary ergodic source?
    - Why *surprise* instead of *information content*? *Surprise rate* is not used again in the text.
    - 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.

#### Method

- **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$?

- **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.

- **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. 

#### Experiments

- **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$?

- **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.

- **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?
review_title: Review: MIROSTAT: A NEURAL TEXT DECODING ALGORITHM THAT DIRECTLY CONTROLS PERPLEXITY

final_score: rating: 6: Marginally above acceptance threshold
review_content: What is this paper about, what contributions does it make, what are the main strengths and weaknesses?

The 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.

The main strengths are

1)	The 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.

2)	In 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.

3)	The 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.

The main weaknesses are

1)	This 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.

2)	Some 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.

3)	The 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.

4)     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".

review_title: Official Blind Review #4

final_score: rating: 7: Good paper, accept
review_content: Summary:

Neural 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. 

Strengths:

1. Theoretical analysis of the previously proposed sampling schemes in terms of surprise, cross-entropy, perplexity.
2. Adaptive top-k algorithm based on updating the exponents in Zipfian distribution, per time step.
3. Clarity of the paper.

Weaknesses:

1. It seems like a time complex scheme for decoding based on the formulation
2. Lacks generated samples in the main paper for qualitative assessment.
3. Human evaluation missing.

Questions:

1. 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?  
2. 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?
3. 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?
4. 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)? 

Overall:

a) The theoretical analysis helps in understanding why top-k and top-p perform the way they do.

b) Based on the underlying assumptions:
1. Zipfian distribution 
2. cross-entropy loss optimization
3. Lowest perplexity does not always mean good quality generation. 

(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.

Please let me know if I am misunderstanding something. I am open to revising my assessment based on the answers to the questions raised.

-----
Update:

Updated 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.
review_title: Official Blind Review #1

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)