Greedy Streaming Decoder with KV Cache
Problem statement
Write a greedy decoder that generates tokens one at a time using a model-managed key/value (KV) cache.
Write greedy_stream(model, prompt_ids, max_new_tokens, eos_id), which returns a Python list of newly generated token ids (the prompt is NOT included). The model exposes two methods that manage the KV cache internally:
model.prefill(prompt_ids): ingests the full prompt, populates the cache, and returns a 1D numpy array of logits over the vocabulary for the position right after the prompt.model.decode_step(token_id): appends a single token to the cache and returns a 1D numpy array of logits for the next position.
Your decoder must:
- Call
prefillexactly once with the entire prompt to obtain the first logits. - Repeat up to
max_new_tokenstimes: take the argmax of the current logits as the next token. If it equalseos_id, stop immediately WITHOUT appending it and WITHOUT callingdecode_step. Otherwise append it to the output and calldecode_step(next_token)to get the next logits. - Never re-run
prefill, and never pass more than one token todecode_step. - Return only the list of newly generated token ids, in order.
Example
Input:
prompt_ids = [1, 2, 3], max_new_tokens = 5, eos_id = 99, model = a toy cached LM with vocab_size = 20
# Its successive logits have argmax ids: 5, 1, 9, 13, 5
Output:
[5, 1, 9, 13, 5]
Reasoning: prefill is called once with [1,2,3] and yields the first logits, whose argmax is 5. Each subsequent token is produced by feeding only the previously generated token to decode_step, never the full sequence. No token equals eos_id=99, so the loop runs the full 5 iterations and returns the list of generated tokens (the prompt itself is not part of the output).
Show hint
Why does a causal model never need to recompute anything for tokens it has already processed?
Relevant roles: LLM Engineer, Gen AI Engineer, ML Engineer, AI Engineer and AI Architect.
Related free problems
- Chunked Prefill Scheduling Alongside DecodeLLMs & GenAIMedium
- Multi-Head AttentionMedium