Temperature, Top-k, Top-p and Min-p Sampling from Scratch
Problem statement
A language model has produced a vector of logits for the next token, and you are writing the decoding step that turns those logits into the distribution the sampler draws from. Implement the four standard knobs and apply them in this order:
- Temperature. If
temperature == 0, decoding is greedy: return a one-hot vector on the largest logit (the lowest index wins ties) and ignore the other three settings. Otherwise divide every logit bytemperatureand take a numerically stable softmax. - Top-k. If
0 < top_k < len(logits), keep only thetop_kmost probable tokens, breaking ties by lower index.top_k = 0disables the filter. - Top-p (nucleus). If
top_p < 1, renormalize the surviving tokens, sort them by probability (descending, ties by lower index) and keep the shortest prefix whose cumulative probability is at leasttop_p. - Min-p. If
min_p > 0, keep only the surviving tokens whose probability is at leastmin_ptimes the largest surviving probability.
Finally, set every removed token to 0 and renormalize the survivors so the vector sums to 1.
def sampling_distribution(logits: list[float], temperature: float,
top_k: int, top_p: float, min_p: float) -> list[float]:
...
Constraints
- $1 \le$
len(logits)$\le 1000$; logits can be as large as $\pm 1000$. temperature$\ge 0$,top_k$\ge 0$, $0 <$top_p$\le 1$, $0 \le$min_p$< 1$.- Answers within a relative error of $10^{-6}$ (or absolute $10^{-9}$) are accepted.
Examples
Example 1: logits = [2.0, 1.0, 0.0, -1.0], temperature = 1.0, top_k = 0, top_p = 0.8, min_p = 0.0 returns about [0.7311, 0.2689, 0.0, 0.0]. The softmax is about [0.6439, 0.2369, 0.0871, 0.0321]; the first token alone covers 0.6439 < 0.8, the first two cover 0.8808, so two tokens survive and are renormalized.
Example 2: the same logits with temperature = 0.5, top_k = 0, top_p = 1.0, min_p = 0.2 returns [1.0, 0.0, 0.0, 0.0]. At temperature 0.5 the second token's probability is $e^{-2} \approx 0.135$ times the first's, below the 0.2 cut.
Example 3: logits = [1.0, 1.0, 1.0, 0.0], temperature = 1.0, top_k = 2, top_p = 1.0, min_p = 0.0 returns [0.5, 0.5, 0.0, 0.0] (three tokens tie for the top two slots; the lower indices win).
Show hint
Which step of turning logits into probabilities can blow up numerically for large inputs, and what shift leaves the result unchanged?
Relevant roles: LLM Engineer, Deep Learning Engineer, ML Engineer and Research Scientist.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium