Greedy, Top-k and Top-p Decoding in NumPy
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.paramanddrawsare ignored.method = "topk"withparam = k($k \ge 1$): keep only the $k$ most probable tokens (all of them if $k \ge V$).method = "topp"withparam = 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:
- Convert logits to probabilities with a softmax that cannot overflow (logits can be around 1000).
- Rank tokens by probability, highest first, breaking exact ties by the lower token id. Truncate this ranked list as described above.
- Renormalize the kept probabilities so they sum to 1.
- 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_tokensfor 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
- Beam Search DecodingMedium
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium