KV-Cache for Autoregressive Generation (Reuses the Inference Section Directly)
The problem, from first principles
06-inference/02-kv-cache-and-decoding already built a real, working KV-cache: it computes K/V for the prompt once during prefill, then for every new generated token, projects only that one new token's K/V and appends them to a running cache — it never recomputes K/V for tokens that were already processed. This question makes the reason that matters concrete: implement the naive alternative (recompute everything, every step) and prove the two produce numerically identical results, which is exactly what makes caching a pure optimization rather than an approximation.
From theory to code
Implement generate_without_cache(X_prompt, W_Q, W_K, W_V, new_tokens), the same autoregressive generation task with no cache at all, and outputs_match(...), which verifies it against 06-inference's real autoregressive_decode_with_cache directly.
Constraints
generate_without_cachereturns the exact same dict shape asautoregressive_decode_with_cache:{"prefill_output", "generated_outputs", "final_cache_len"}.- At every new token,
generate_without_cacherecomputesQ,K,Vfor the entire sequence-so-far from scratch (no incremental reuse of any previous computation). outputs_matchreturnsTrueiff both implementations agree, within floating-point tolerance, on bothprefill_outputandgenerated_outputs.
Hints
Open one at a time. Each gives away a little more than the last.
Hint 1
Write one helper — a plain, full causal-attention forward pass over an arbitrary-length sequence — and call it fresh, on the whole growing sequence, at every single step. Nothing from a previous call should be reused.
Hint 2
After appending each new token and re-running the full forward pass over the now-longer sequence, only the last row of that pass's output is this step's actual generated output — every earlier row is being needlessly recomputed, which is exactly the point.
Keywords
No results yet
Run your code to check it against the examples, or submit to run every test.