Problem. Given a row of logits over a vocabulary of V tokens, a temperature T, and either k (top-k) or p (top-p), draw one token:
- divide the logits by T and apply softmax;
- top-k: keep the k most likely tokens; top-p: keep the smallest set of most-likely tokens whose probabilities sum to at least p (always including the token that crosses p);
- renormalise the kept probabilities and sample one token from them.
probs (after temperature) = [0.50, 0.20, 0.15, 0.10, 0.05] (tokens 0..4)
top-k, k = 2 → sample from {0: 0.714, 1: 0.286}
top-p, p = 0.8 → 0.50 + 0.20 = 0.70 < 0.8, + 0.15 = 0.85 ≥ 0.8 → sample from {0, 1, 2}, renormalised
V is 32,000 to 250,000 and this runs once per generated token, for every sequence in the batch. Sorting the entire vocabulary per token, then walking a Python loop to sample, is the brute force. The optimisations: select instead of sort, sort only what's left, and draw the sample with one binary search.
ML context. This is the decoding step of every LLM sampling API: temperature, top_k and top_p are the knobs. Getting the edge
cases right matters in production: the token that crosses p must be kept (or top-p can return nothing), temperature 0 must mean greedy,
and sampling must be reproducible from a seed for evaluation.