Google

Top-k sampling is a decoding method for selecting the next token in a sequence by sampling from a reduced set of the most likely options. The process consists of several steps:
1.  **Ranking:** All potential next tokens from the vocabulary are ranked according to their predicted probabilities.
2.  **Selection (Top-k):** The vocabulary is truncated to include only the 'k' tokens with the highest probabilities. All other lower-probability tokens are discarded or 'pruned'. For example, if k=3, only the top three candidates are kept.
3.  **Renormalization & Sampling:** The probabilities of the selected top-k tokens are recalculated (renormalized) to sum to 1. A final token is then chosen by sampling from this new, smaller probability distribution. This introduces randomness among the most plausible choices.
For instance, after ranking, the top 3 tokens might be 'cute' (Pr=0.34), 'on' (Pr=0.32), and 'sick' (Pr=0.21). After renormalization, their probabilities might become 'cute' (Pr=0.39), 'on' (Pr=0.36), and 'sick' (Pr=0.25). Sampling from this new distribution might then select 'on' as the final output.

Top-k Sampling Process

This example illustrates the top-k sampling process with k=3. First, five candidate words are ranked by their initial probabilities: 'cute' (Pr=0.34), 'on' (Pr=0.32), 'sick' (Pr=0.21), 'are' (Pr=0.12), and '.' (Pr=0.01). Next, the top k=3 candidates ('cute', 'on', 'sick') are selected, and the rest are pruned. The probabilities of these selected candidates are then renormalized to sum to 1, yielding new probabilities: 'cute' (Pr=0.39), 'on' (Pr=0.36), and 'sick' (Pr=0.25). Finally, a token is chosen by sampling from this new distribution, resulting in 'on' being selected as the final output.

Example of Top-k Sampling with k=3

In top-k sampling, the 'selection pool' is the set of candidate tokens from which the next token is chosen. At a given step $i$, this pool, denoted as $\overline{V}_i$, contains the $k$ tokens with the highest probabilities. It is formally defined as: $$\overline{V}_i = \{y_i^{\text{top1}}, \dots, y_i^{\text{topk}}\}$$

Top-k Selection Pool

In sampling-based decoding methods like top-k or top-p, after a restricted vocabulary $\overline{V}_i$ is selected, the probabilities of the tokens within this set are rescaled to form a new, valid probability distribution. The renormalized probability, $\overline{\text{Pr}}$, of a token $y_i$ is calculated by dividing its original conditional probability by the sum of the original probabilities of all tokens $y_j$ in the restricted set $\overline{V}_i$. This is expressed as:
$$ \overline{\text{Pr}}(y_i|\mathbf{x}, \mathbf{y}_{<i}) = \frac{\text{Pr}(y_i|\mathbf{x}, \mathbf{y}_{<i})}{\sum_{y_j \in \overline{V}_i} \text{Pr}(y_j|\mathbf{x}, \mathbf{y}_{<i})} $$

Probability Renormalization Formula for Restricted Vocabulary Sampling

In top-k sampling, after identifying the pool of the k most probable tokens ($\overline{V}_i$), their probabilities are renormalized to form a new distribution that sums to 1. The renormalized probability of a token $y_i$ from this pool is calculated by dividing its original probability by the sum of the original probabilities of all tokens in the pool: $$\overline{\text{Pr}}(y_i|\mathbf{x}, \mathbf{y}_{<i}) = \frac{\text{Pr}(y_i|\mathbf{x}, \mathbf{y}_{<i})}{\sum_{y_j \in \overline{V}_i} \text{Pr}(y_j|\mathbf{x}, \mathbf{y}_{<i})}$$ This ensures that the new probabilities for the tokens in $\overline{V}_i$ sum to 1.

Probability Renormalization Formula for Top-k Sampling

A language model is generating the next word in a sequence and has calculated the initial probabilities for the five most likely candidates: `the` (0.4), `a` (0.2), `one` (0.1), `his` (0.05), and `her` (0.05). If the model uses a sampling strategy where it only considers the top 3 most likely candidates (k=3), what will be the new, rescaled probability distribution for this reduced set of candidates from which the final word will be sampled?

Arrange the following actions into the correct sequence that describes the process of selecting the next token in a text generation model using the top-k sampling method.

A language model is used to complete the sentence 'The weather today is surprisingly...' using a process where it ranks potential next words by probability, selects a small group of the most likely words, and then randomly samples from that group. The process is run twice with only the size of the candidate group being changed. Analyze the two outputs below and determine which one was likely generated using a smaller group of candidate words. Justify your reasoning.

Learn Before

Related