Greedy, Top-k and Top-p Decoding in NumPy

MediumML Coding

Reported in interviews at Cohere

Problem statement

You are handed a toy language model and asked to write its decoding loop in numpy (no PyTorch or other deep-learning framework). The model has a small vocabulary and a forward function that returns next-token logits for the context so far. To keep the toy fully deterministic, its logits depend only on the last token: they are row tokens[-1] of a $V \times V$ table W.

def toy_forward(W, tokens):            # provided, keep as is
    return np.asarray(W[tokens[-1]], dtype=np.float64)

Implement one function covering three decoding methods. Each step calls toy_forward on the current context, picks a token, appends it to the context, and continues.

def decode(W, prompt, num_tokens, method, param, draws) -> list:
    ...
  • method = "greedy": take the argmax of the logits; on an exact tie, the lowest token id wins. param and draws are ignored.
  • method = "topk" with param = k ($k \ge 1$): keep only the $k$ most probable tokens (all of them if $k \ge V$).
  • method = "topp" with param = p ($0 < p \le 1$): nucleus sampling. Keep the smallest set of most probable tokens whose total probability reaches $p$; the token that pushes the running total to $p$ or beyond is kept. If floating-point rounding means the total never reaches $p$, keep everything.

The tests compare exact token sequences, so randomness is replaced by given numbers and the sampling rule is pinned down:

  1. Convert logits to probabilities with a softmax that cannot overflow (logits can be around 1000).
  2. Rank tokens by probability, highest first, breaking exact ties by the lower token id. Truncate this ranked list as described above.
  3. Renormalize the kept probabilities so they sum to 1.
  4. With $u$ = draws[t] (a number in $[0, 1)$ for step $t$), walk the kept tokens in ranked order, accumulating their renormalized probabilities, and return the token id of the first one whose running total exceeds $u$ (the last kept token if none does).

Return only the num_tokens generated ids (not the prompt).

Constraints

  • $2 \le V \le 32$, prompt length 1 to 4, 0 <= num_tokens <= 25, len(draws) == num_tokens for the sampling methods.

Examples (all with the same table)

W = [[0.5, -1.0, 2.0,  1.0],
     [0.0,  1.0, 1.0,  3.0],
     [1.5,  2.5, 0.0, -0.5],
     [1.0,  1.0, 1.0,  1.0]]
prompt = [1], num_tokens = 5, draws = [0.9, 0.3, 0.7, 0.1, 0.6]

decode(W, [1], 5, "greedy", 0, [])     -> [3, 0, 2, 1, 3]
decode(W, [1], 5, "topk", 2, draws)    -> [1, 3, 1, 3, 1]
decode(W, [1], 5, "topp", 0.8, draws)  -> [1, 3, 2, 1, 3]

Greedy reaches the all-equal row 3 and takes token 0 by the tie rule. In the top-p run, the third step starts from row 3, whose four tokens each have probability 0.25; no three of them reach 0.8, so all four are kept, and $u = 0.7$ selects token 2. With top-2 the same step keeps only tokens 0 and 1.

After the code works, be ready to answer two questions out loud: what are the weaknesses of top-k sampling, and how does top-p sampling work and what does it fix?

Show hint

What must be fixed besides the random numbers for a sampled sequence to be exactly reproducible?

Relevant roles: ML Engineer, LLM Engineer and AI Engineer.

Related free problems