Mirostat: A Perplexity-Controlled Neural Text Decoding Algorithm

Sourya Basu, Govardana Sachitanandam Ramachandran, Nitish Shirish Keskar, Lav R. Varshney

Introduction

Generating high-quality text from Large Language Models (LLMs) remains a challenge due to the limitations of standard decoding strategies. Traditional methods like top-$k$ (sampling from the $k$ most likely tokens) and top-$p$ (sampling from a nucleus of tokens with cumulative probability $p$) are static. They require manual, ad hoc tuning to avoid two extremes: the "boredom trap," where low perplexity leads to excessive repetition, and the "confusion trap," where high perplexity results in incoherent gibberish. Because the ideal parameters vary by model and sequence length, there is a need for a principled, adaptive approach to maintain output stability.

The Mirostat Algorithm

Mirostat is the first decoding algorithm to employ a feedback-based mechanism to directly control the perplexity (or "surprise") of generated text. The algorithm operates on two key principles:

  1. Zipfian Modeling: It assumes that the probability distribution of tokens follows Zipf’s Law. By estimating the Zipfian exponent ($s$) in real-time, Mirostat can approximate the relationship between the number of tokens considered and the resulting surprise.
  2. Feedback Control: Mirostat takes a target surprise value ($\tau$) as input. It monitors the actual surprise of each generated token and adjusts an internal parameter ($\mu$)—representing the maximum allowable surprise—to correct for deviations from the target.
Mirostat effectively tracks the target cross-entropy rate, ensuring stable output quality across different settings.

By dynamically adjusting the sampling pool (an adaptive top-$k$), Mirostat maintains a consistent statistical quality throughout long-form generation, preventing the "drift" toward repetition often seen in static methods.

A central insight of the Mirostat paper is the mathematical link between cross-entropy and text quality. The authors demonstrate a near-linear relationship between the observed cross-entropy rate and the rate of $n$-gram repetition.

The relationship between $n$-gram repetition and observed cross-entropy rate across different decoding methods, highlighting the "Goldilocks zone" for human-like text.

This relationship suggests a "Goldilocks zone" for perplexity. Human preference follows a U-shaped curve: text that is too predictable is perceived as boring, while text that is too surprising is perceived as nonsensical. Mirostat allows users to target this "sweet spot" (found to be around $\tau = 3.0$ for GPT-2) directly.

Results and Evaluation

The researchers evaluated Mirostat using GPT-2 and CTRL models, complemented by a human subject experiment involving 43 participants. Key findings include:

  • Human-Level Quality: At the optimal setting ($\tau = 3.0$), more than 50% of human raters were unable to distinguish GPT-2 generated text from human-written text.
  • Stability: Unlike top-$k$ and top-$p$, which often drift toward lower perplexity in long sequences (900+ tokens), Mirostat remains perfectly stable, maintaining the target surprise level indefinitely.
  • Zero-Shot Tuning: Mirostat achieves superior fluency and coherence across different models without the trial-and-error parameter tuning required by traditional sampling methods.

Conclusion

Mirostat provides a robust, feedback-driven alternative to traditional decoding. By shifting the focus from fixed probability masses to active perplexity control, it ensures that LLMs generate text that remains engaging and coherent over any sequence length. Future work will explore more complex control mechanisms, such as PID controllers, to further refine the stability of neural text generation.

Summary updated

Abstract

Neural text decoding is important for generating high-quality texts using language models. To generate high-quality text, popular decoding algorithms like top-k, top-p (nucleus), and temperature-based sampling truncate or distort the unreliable low probability tail of the language model. Though these methods generate high-quality text after parameter tuning, they are ad hoc. Not much is known about the control they provide over the statistics of the output, which is important since recent reports show text quality is highest for a specific range of likelihoods. Here, first we provide a theoretical analysis of perplexity in top-k, top-p, and temperature sampling, finding that cross-entropy behaves approximately linearly as a function of p in top-p sampling whereas it is a nonlinear function of k in top-k sampling, under Zipfian statistics. 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 value of perplexity, and thereby high-quality text without any tuning. Experiments show that for low values of k and p in top-k and top-p sampling, perplexity drops significantly with generated text length, which is also correlated with excessive repetitions in the text (the boredom trap). On the other hand, for large values of k and p, we find that perplexity increases with generated text length, which is correlated with incoherence in the text (confusion trap). Mirostat avoids both traps: experiments show that cross-entropy has a near-linear relation with repetition in generated text. This relation is almost independent of the sampling method but slightly dependent on the model used. Hence, for a given language model, control over perplexity also gives control over repetitions. Experiments with human raters for fluency, coherence, and quality further verify our findings.
BibTeX
@misc{basu2020mirostat,
  author = {Sourya Basu and Govardana Sachitanandam Ramachandran and Nitish Shirish Keskar and Lav R. Varshney},
  title = {{Mirostat: A Perplexity-Controlled Neural Text Decoding Algorithm}},
  year = {2020},
  eprint = {2007.14966},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2007.14966},
}
Figure