Problem. A language model outputs a logit for every token in its vocabulary of V tokens (V ≈ 50,000 to 250,000). Top-k sampling keeps the k tokens with the highest logits, turns their logits into probabilities with a softmax over those k only, and samples the next token from them.
logits = [2.0, -1.0, 0.5, 3.0, 1.0], k = 2
top-2 tokens: 3 (logit 3.0), 0 (logit 2.0)
probabilities: softmax([3.0, 2.0]) = [0.731, 0.269]
This runs once per generated token, for every sequence in the batch. Generating 500 tokens for 64 sequences means 32,000 selections over 50,000+ logits: the per-call cost matters.
Why it matters. Top-k (and its cousin top-p) is how most chat models avoid both the blandness of greedy decoding and the nonsense of sampling from the full long tail. The selection step is a heap or selection problem; the softmax step is a numerical-stability problem. Both are classic interview follow-ups for ML roles.