Dynamic Threshold Adjustment in Mirostat Text Sampling

This article provides a direct breakdown of how the Mirostat sampling algorithm dynamically modifies its vocabulary truncation threshold at every token generation step to maintain a target perplexity surprise level. By continuously measuring the difference between expected surprise and actual token surprise, Mirostat utilizes an active feedback loop to prevent artificial intelligence text from becoming either overly repetitive or entirely incoherent. The following sections detail the exact mathematical and algorithmic processes that occur during each step of this adaptive generation method.

Defining Target Surprise and Error Tracking

Unlike static decoding methods such as Top-K or Top-P (nucleus) sampling, which apply fixed cutoffs to token probability distributions, Mirostat approaches text generation as a control theory problem. It establishes a user-defined target surprise value, denoted as \(\tau\) (tau). Surprise—measured in bits or nats—is the negative logarithm of a token's probability. A low-probability token yields high surprise, while a high-probability token yields low surprise.

To maintain this target, the algorithm initializes a variable called \(\mu\) (mu), which represents the maximum allowable surprise threshold for the current step. Typically, \(\mu\) is initialized to \(2\tau\). Throughout the generation process, Mirostat tracks the error between the actual surprise of the generated tokens and the target \(\tau\), adjusting \(\mu\) up or down to keep the average perplexity stable.

Estimating Zipf's Exponent at Each Step

Before selecting a token, the language model outputs a probability distribution over the entire vocabulary, sorted in descending order of likelihood. Because natural language probabilities approximately follow a Zipfian distribution, Mirostat first estimates the shape of the current token distribution.

At each token step, the algorithm calculates the Zipf exponent, denoted as \(s\), by analyzing the slope of the probabilities of the top most likely tokens. Estimating \(s\) allows the algorithm to mathematically relate the current surprise threshold (\(\mu\)) to a specific number of tokens (\(k\)).

Calculating the Truncation Threshold (\(k\))

Once the distribution's slope (\(s\)) is known, Mirostat calculates the exact truncation threshold \(k\)—the number of top tokens to keep for the current step. Using the current value of the adaptive threshold \(\mu\) and the estimated Zipf exponent \(s\), the algorithm computes \(k\) so that the tokens included in the truncated pool will, on average, produce a surprise level close to \(\tau\).

All tokens ranked below \(k\) have their probabilities set to zero. The remaining top \(k\) tokens have their probabilities renormalized so they sum to one, and the next token is sampled randomly from this restricted pool.

The Feedback Loop: Updating the Threshold

The core of Mirostat's active adjustment happens immediately after the new token is sampled. The algorithm executes the following feedback steps before moving to the next token:

  1. Measure Observed Surprise: The algorithm calculates the actual surprise of the chosen token using its original (pre-truncation) probability \(P(x)\) via the formula \(-\log_2(P(x))\).
  2. Calculate the Error: It determines the error (\(e\)) by subtracting the target surprise from the observed surprise: \(e = \text{Observed Surprise} - \tau\).
  3. Adjust the State Variable: Using a learning rate \(\eta\) (eta), Mirostat updates the maximum surprise threshold for the next token step using the formula: \(\mu_{next} = \mu_{current} - \eta \times e\).

How the Adjustment Regulates Perplexity

This simple subtraction drives the self-correcting behavior of the algorithm at every step:

  • When a token is too surprising: If the sampled token had a very low probability, the observed surprise will be higher than \(\tau\), resulting in a positive error (\(e > 0\)). The update formula subtracts a positive value from \(\mu\), lowering it. On the next token step, a lower \(\mu\) forces the algorithm to calculate a smaller \(k\), tightening the truncation pool to only the most predictable words to bring overall perplexity back down.
  • When a token is too predictable: If the sampled token had a very high probability, the observed surprise will be lower than \(\tau\), resulting in a negative error (\(e < 0\)). Subtracting a negative value increases \(\mu\). On the next token step, a higher \(\mu\) translates to a larger \(k\), expanding the truncation pool to allow more diverse and surprising words into the sampling candidates, thus preventing the model from falling into a repetitive loop.

Mirostat 2.0 Simplification

A widely used variation of this algorithm, Mirostat 2.0, streamlines this process by removing the Zipfian distribution estimation entirely. Instead of calculating \(k\) via the exponent \(s\), Mirostat 2.0 directly truncates the vocabulary by discarding all tokens whose individual surprise \(-\log_2(P(x))\) is greater than the current threshold \(\mu\). After sampling from the remaining tokens, it executes the exact same error calculation and \(\mu\) update step, achieving the same dynamic perplexity control with less computational overhead.