Week 7 • Day 5Week 7

Day 5:Week 7, Day 5: Inference Optimization — `KV-Cache` Mechanics, VRAM Math & Grouped-Query Attention

Battle-tested daily lesson note • 100% runnable code, interview Q&A, test suite & interactive quiz

Week 7, Day 5: Inference Optimization — KV-Cache Mechanics, VRAM Math & Grouped-Query Attention (GQA)


1. Why Naive Autoregressive Decoding is O(T3)O(T^3)

When generating a 1,000-token response one token at a time, at step tt we only need the logits for the newest token xtx_t:

Attentiont(qt,K1:t,V1:t)=softmax(qtK1:tTdk)V1:t\text{Attention}_t(q_t, K_{1:t}, V_{1:t}) = \text{softmax}\left(\frac{q_t K_{1:t}^T}{\sqrt{d_k}}\right) V_{1:t}

Notice two crucial facts because of causal masking:

  1. Earlier Keys k1,…,kt−1k_1, \dots, k_{t-1} and Values v1,…,vt−1v_1, \dots, v_{t-1} never change when token tt is appended!
  2. If we recompute K1:tK_{1:t} and V1:tV_{1:t} from scratch at every step, generating TT tokens costs ∑t=1TO(t2)=O(T3)\sum_{t=1}^T O(t^2) = O(T^3) FLOPs!

The Solution: KV-Cache

By caching the past Key and Value tensors (Kcache,Vcache)∈RB×Hkv×(t−1)×dk(K_{\text{cache}}, V_{\text{cache}}) \in \mathbb{R}^{B \times H_{kv} \times (t-1) \times d_k} in GPU VRAM:

  • At step tt, we only pass the single new token xt∈RB×1×dx_t \in \mathbb{R}^{B \times 1 \times d} into the model!
  • We compute qt,kt,vtq_t, k_t, v_t, append kt,vtk_t, v_t to the cache, and compute qtK1:tTq_t K_{1:t}^T in O(t)O(t) time instead of O(t2)O(t^2)!

2. Exact KV-Cache GPU VRAM Formula (Staff Interview Classic)

For each token, at each layer, we store 2 tensors (KK and VV) across HkvH_{kv} Key-Value heads of dimension dheadd_{\text{head}}:

KV Cache Bytes=2×L×Hkv×dhead×T×B×bytes_per_param\text{KV Cache Bytes} = 2 \times L \times H_{kv} \times d_{\text{head}} \times T \times B \times \text{bytes\_per\_param}

Concrete Calculation: Llama-2-70B (MHA) vs Llama-3-70B (GQA)

Suppose L=80L = 80 layers, dmodel=8192d_{\text{model}} = 8192 (Hq=64H_q = 64 query heads, dhead=128d_{\text{head}} = 128), BF16 (2 bytes), batch size B=1B = 1, context T=32,768T = 32,768:

  • Standard MHA (Hkv=64H_{kv} = 64): $2 \times 80 \times 64 \times 128 \times 32768 \times 1 \times 2 = \mathbf{80.0\text{ GiB of VRAM!}}$
  • Grouped-Query Attention (GQA with Hkv=8H_{kv} = 8, 8:1 ratio): $2 \times 80 \times 8 \times 128 \times 32768 \times 1 \times 2 = \mathbf{10.0\text{ GiB of VRAM! (8x reduction!)}}$

In Simple English: KV Cache = Not Re-Reading the Whole Book for Every New Word

Suppose you ask an LLM to write a 100-word essay:

  • Without KV Cache: To write word #99, it re-reads words #1..98 and recomputes all their Key (KK) and Value (VV) vectors from scratch. Writing word #100 repeats everything AGAIN (O(N2)O(N^2) wasted work)!
  • With KV Cache: Save the KK and VV vectors of words #1..99 inside GPU VRAM! Now generating word #100 computes ONLY the 1 new Query vector and looks up the saved history in a single pass!
  • Catch (VRAM Formula): Every extra active user in a batch needs gigabytes of saved K,VK,V vectors. Grouped-Query Attention (GQA) lets e.g. 4 Query heads share 1 Key/Value head — cutting KV-Cache VRAM usage by 4x–8x so servers handle far more concurrent users!