Benchmark: With vs Without Cache

The problem, from first principles

01-kv-cache-autoregressive-generation proved caching and no-caching produce identical results. That leaves the actual practical question unanswered: exactly how much redundant work does skipping the cache cost, and how does that cost grow as generation gets longer? This question answers it with real, closed-form accounting rather than a hard-to-trust wall-clock timing (which plain NumPy on tiny arrays can't demonstrate reliably).

From theory to code

Implement naive_kv_projection_work(prompt_len, num_new_tokens), the total "K/V projection" work generate_without_cache actually performs (reprojecting the entire sequence-so-far at every step), cached_kv_projection_work(...), the equivalent for the real cached implementation, and cache_work_reduction_factor(...), their ratio.

Constraints

• Counting one token's K/V projection as one unit of work: naive_kv_projection_work sums (prompt_len + step) for step from 1 to num_new_tokens — at each step, the entire current sequence gets reprojected.
• cached_kv_projection_work returns prompt_len + num_new_tokens — the prompt once, plus exactly one unit per new token.
• cache_work_reduction_factor returns naive_kv_projection_work / cached_kv_projection_work.
• num_new_tokens = 0 gives naive_kv_projection_work = 0 and cache_work_reduction_factor = 0.0.

Hints

Open one at a time. Each gives away a little more than the last.