Greedy Streaming Decoder with KV Cache

EasyML Coding

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:

  1. Call prefill exactly once with the entire prompt to obtain the first logits.
  2. Repeat up to max_new_tokens times: take the argmax of the current logits as the next token. If it equals eos_id, stop immediately WITHOUT appending it and WITHOUT calling decode_step. Otherwise append it to the output and call decode_step(next_token) to get the next logits.
  3. Never re-run prefill, and never pass more than one token to decode_step.
  4. 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