Decoding Strategies: How LLMs Choose The Next Word

Large Language Models are trained to guess the next word. But when generating text, the combination of their probability estimates with algorithms known as decoding strategies is what determines how they actually choose words. Learn how decoding strategies work in this article.

Next-word Predictors vs. Text Generators

Before diving into the technical details, let’s recall the important distinction between two phases of language models design:

  • Modeling phase: How language models learn during training.
  • Decoding phase: How they generate text–the focus of this article.

During modeling, LLMs are trained to minimize an objective function (a measure of prediction error) to estimate the probability of the next word in a text sequence. This process results in a statistical model of language.

As a consequence, LLMs are often described as “next-word predictors” in non-scientific literature. This description, however, can lead to misconceptions about how LLMs generate text in practice: in the decoding phase, LLMs don’t always output the most probable next word iteratively. They actually employ various strategies that utilize their internal statistical models of language for text generation.

Decoding strategies (or sampling/ token-selection strategies) are the decision rules used to extract coherent text strings from a model’s probability estimates.

What is language model decoding?

Language Model Decoding is the process by which an LLM generates text.

For open-ended text generation, the goal of this process can be abstractly described as follows: given an input sequence of tokens s=x1,…,xm, the goal is to choose a continuation of n additional tokens y1,…,yn that form the completed sequence s’=x1,…,xm,y1,…,yn. This continuation should be coherent and contextually appropriate as an extension of the given input.

Steps of a decoding strategy

  1. Given the current context sequence s, sample a token x from the distribution conditioned on s.
  2. Update the context sequence to s' = s, x.
  3. Repeat steps 1 and 2 until a termination condition is met.

The method by which we sample x from the distribution (step 1) is precisely what distinguishes different decoding strategies.

Deterministic methods

Greedy Search

The simplest decoding strategy for language models is known as greedy search. It is the most straightforward approach: at each step, choose x as the most likely token given the context sequence s and repeat this for a specified number of steps or until a termination condition is met.

Beam Search

Beam Search is the natural generalization of greedy search, offering a way to explore multiple branches in the probability tree.

The algorithm works as follows:

  1. Consider the top K most probable next tokens for each sequence in the current beam.
  2. Expand each sequence with these K tokens.
  3. Update the current beam by selecting the top K sequences among these candidates.
  4. Repeat until a termination condition is met.

Stochastic methods

Top-k Sampling

Top-k sampling is a stochastic decoding strategy that introduces randomness by sampling the next token from the top k most probable choices, where k is a fixed value.

Top-p Sampling (Nucleus Sampling)

Top-p sampling represents an improvement over top-k sampling by offering a more dynamic approach to token selection. With p being a fixed probability threshold, it works as follows:

  1. Select the minimum number of tokens whose cumulative probability meets or exceeds the threshold p.
  2. Normalize their probabilities to sum to 1, creating a new, truncated distribution.
  3. Randomly sample a token from this new distribution and append it to the current sequence.

Temperature Sampling

The idea behind temperature sampling is to adjust the "sharpness" of the probability distribution. This is achieved by introducing a parameter t (temperature) in the softmax function.

  • Low Temperature (0 < t < 1): The probability distribution becomes more concentrated or "peaky" around the most likely tokens.
  • High Temperature (t > 1): Temperatures above 1 flatten the probability distribution, increasing randomness.

Optimizing Information-Content via Typical Sampling

Typical sampling proposes generating sentences with the expected information content given prior context, in order to produce text that is informative enough to be engaging, yet not so complex that it overwhelms the reader.

Boosting inference speed via Speculative Sampling

Speculative Sampling is a decoding strategy that yields 2-3x speedups by generating multiple tokens per model pass and without changes to the final output. The process can be summarized as:

  1. Drafting: A draft model generates a fixed number K of tokens starting from the given context.
  2. Verification: A target model evaluates the whole sequence with a single forward pass.
  3. Correction: Following a technique called rejection sampling, the draft tokens are approved or rejected based on the probability comparison between the target and draft models.

Final Words

In this blog post, we took a deep dive into decoding strategies, exploring how both deterministic and stochastic methods shape the word choices of an LLM for open-ended text generation.