Top-k Sampling in LLMs, explained in 5 lines

Module 06 · LLMs · 22 concepts

In depth / 15 lines

Top-k Sampling, in more detail

Top-k sampling limits the choice to the k most likely tokens.

Everything else is discarded before anything is sampled.

The survivors have their probabilities renormalised so they sum to one again.

With k at 40, the model picks from 40 candidates however unsure it is.

The purpose is to stop the long tail from ever being chosen.

A vocabulary of 100,000 tokens has an enormous tail of nearly-zero probabilities.

Summed together that tail is not negligible, so occasionally a bizarre token wins.

One such token derails the sentence and everything after it.

Cutting the tail removes that failure mode almost entirely.

The weakness is that k is fixed while the model's certainty is not.

When the next word is obvious, 40 candidates is 39 too many.

When the model is genuinely open, 40 may cut off good options.

Top-p solves that by choosing the cut-off from the probabilities themselves.

Top-k is still offered everywhere and is often left at a moderate value alongside top-p.

Setting k to one is greedy decoding by another name.

Deep dive

What is underneath Top-k Sampling

Keep the best k, discard the rest

V_k = \left\{ \text{the } k \text{ tokens with the largest } z_i \right\}

Everything outside that set is removed, and what is left is renormalised so it sums to one again.

p'_i = \begin{cases} \dfrac{\exp(z_i)}{\sum_{j \in V_k} \exp(z_j)} & i \in V_k \\[6pt] 0 & \text{otherwise} \end{cases}

$k$ : how many tokens survive, typically between 20 and 100.

The renormalisation matters: without it the surviving probabilities sum to less than one, and the missing mass has nowhere to go.

What it is protecting against

A vocabulary of 100,000 tokens has a very long tail, and the tail's total mass is not negligible.

If 90,000 tokens each hold a probability of $10^{-6}$ , their combined mass is 0.09.

So nearly one time in eleven, pure sampling picks from the part of the distribution the model considers absurd.

One such token is usually unrecoverable: the model conditions on it and the rest of the sentence follows it into nonsense.

Truncation exists to make that impossible rather than merely unlikely.

Why a fixed k is the wrong shape

The problem is that $k$ does not know how certain the model is.

p = [0.99, \; 0.003, \; \ldots] \qquad p = [0.04, \; 0.038, \; 0.037, \; \ldots]

In the first case the model is sure, and $k = 50$ keeps 49 tokens it gave almost no mass to. Some of them will be sampled.

In the second the model is genuinely uncertain across hundreds of reasonable options, and $k = 50$ cuts off continuations it rated nearly as highly as the ones it kept.

One number cannot be right for both, which is the entire argument for top-p.

One token, in order

Get the logits and apply temperature.
Take the $k$ largest.
Set every other logit to negative infinity.
Softmax what remains.
Draw one token.

Where it still earns its place

$k = 1$ is greedy decoding, written as a special case rather than a separate algorithm.

A modest $k$ is also used as a floor underneath top-p, so that a very peaked distribution cannot collapse the nucleus to a single token when some variety was wanted.

The two compose: apply top-k first as a hard cap, then top-p within it.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What is clumsy about using a fixed k?

LLMs

22 concepts in this module, then a graded test with every answer explained.

Study this module →