KV-cache, prefill, and decode

Two phases of autoregressive inference

Every completion has:

1. Prefill — process the full prompt; build initial KV; produce first token (TTFT)
2. Decode — emit tokens one-by-one; each step attends using the KV cache (tokens/sec / TPOT)

flowchart LR
  Prompt[Prompt tokens] --> Prefill[Prefill / compute-bound]
  Prefill --> KV[KV cache]
  KV --> Decode[Decode / memory-bound]
  Decode --> Out[Output tokens]

Optimizing the wrong phase wastes money: chat UX cares about TTFT; batch summarization cares about throughput. Product dashboards that only show “tokens/sec” hide TTFT regressions from long agent prompts.

Interview cue: Prefill and decode are different bottlenecks. A change that helps decode (bigger batch) can hurt TTFT (more prefill contention).

End-to-end timeline of one request

sequenceDiagram
  participant C as Client
  participant G as Gateway
  participant E as Engine
  C->>G: POST /chat
  G->>E: enqueue
  Note over E: Queue wait (admission)
  E->>E: Prefill prompt → first token
  E-->>C: TTFT (stream start)
  loop Decode
    E->>E: Read KV + weights → next token
    E-->>C: token
  end

What the KV cache actually stores

Attention needs keys and values for every prior token in the sequence. Rather than recompute them each step, engines cache K/V per layer:

Memory scales roughly linearly with tokens × concurrent sequences. That is why long-context demos destroy multi-tenant concurrency even when FLOPs look fine on paper.

# Order-of-magnitude sketch — not a substitute for engine reports
def kv_bytes(layers, kv_heads, head_dim, tokens, bytes_per=2, sequences=1):
    # K and V → ×2
    return sequences * layers * kv_heads * head_dim * tokens * bytes_per * 2

# Example: 32 layers, 8 KV heads, dim 128, 8192 tokens, FP16, 16 seqs
print(kv_bytes(32, 8, 128, 8192, 2, 16) / 1e9, "GB ballpark")

Why GQA/MQA changes the spreadsheet

Multi-Query / Grouped-Query Attention shares KV across query heads. Same “7B/8B” label can have very different KV footprints. Always use the model’s KV head count, not query heads, when planning VRAM.

Prefill: compute-bound, TTFT-critical

During prefill the model sees many prompt tokens at once (high arithmetic intensity). Character:

• Bound: often GPU compute
• Latency: dominates time-to-first-token
• Risk: one 100k-token PDF ingest starves interactive chat on a shared pool

Mitigations:

• Cap interactive max_input_tokens; send heavy jobs to a batch queue
• Chunk / summarize before the LLM when product allows
• Use prompt caching / prefix reuse when the static prefix is huge (system + tools)
• Stream tokens so users perceive progress even if TTFT is imperfect
• Enable chunked prefill so decode of other users continues

Prefill storms (agent systems)

Agent loops dump tool JSON + retrieved docs into the next prompt. Prefill cost becomes the product bottleneck even when “the model is fast at chat.”

Ship rule: treat “max context” as a product tier decision, not a model brochure feature.

Decode: memory-bandwidth-bound

Each decode step usually processes one new token per sequence, but must read the growing KV (and weights). Character:

• Bound: often HBM bandwidth
• Latency: inter-token latency (TPOT)
• Win condition: keep the GPU fed with many concurrent decode sequences (continuous batching)

This is why batching and PagedAttention (vLLM) matter: they raise utilization during the memory-bound phase.

flowchart TD
  subgraph Prefill
    P1[Many tokens in]
    P2[Build full KV]
    P3[First token out]
  end
  subgraph Decode
    D1[Read KV + weights]
    D2[One token out]
    D3[Append to KV]
    D1 --> D2 --> D3 --> D1
  end
  P3 --> D1

Why bigger batches help decode more than prefill

Decode arithmetic intensity is low: lots of bytes moved per FLOP. Packing many sequences amortizes weight reads. Prefill is already compute-heavy; packing more huge prefills can hurt TTFT for everyone.

Prefix caching / automatic prefix reuse

Shared system prompts, tool schemas, and RAG “header” text can reuse KV for the identical token prefix across requests:

Ship rule: prefix cache keys are token-identity keys, not “semantic similarity.” Bump a version string in the prompt when you intentionally change instructions.

flowchart LR
  Sys[System + tools tokens] --> Cache{Prefix cached?}
  Cache -->|hit| Skip[Skip recomputing KV]
  Cache -->|miss| Build[Prefill + store blocks]
  User[User + retrieved] --> PrefillTail[Prefill only the suffix]
  Skip --> PrefillTail
  Build --> PrefillTail

Engines differ (vLLM prefix caching, SGLang radix trees, provider prompt caching). Measure hit rate and TTFT delta on your traffic — synthetic unique prompts show zero benefit.

App cache vs engine prefix cache

Do not confuse a Redis hit (skip the model) with a prefix-cache hit (skip part of prefill). Both matter; different metrics. See Redis for AI caching.

Scheduling implications

Pair with cost and latency routing at the gateway: cheap model + short context for easy turns; long-context frontier only when needed.

Metrics that separate the phases

Always log prompt tokens and output tokens separately. A TTFT spike with unchanged decode speed is a prefill/queue story, not “the GPU got slower.”

How to read a bad dashboard

Worked comparison (what to measure in the project)

On one model / one engine:

Record TTFT and tokens/sec for each. The diagram you bring to review should show why those numbers moved.

# Shape — time first token vs rest of stream
import time
t0 = time.perf_counter()
first = True
for event in stream:
    if first and event_has_content(event):
        ttft = time.perf_counter() - t0
        first = False
        t_decode = time.perf_counter()
# after stream: tpot ≈ (now - t_decode) / (n_tokens - 1)

Failure modes

• Optimizing throughput while TTFT SLO burns
• Sharing one GPU pool for interactive + offline summarization
• Unbounded context “just in case” → empty concurrency budget
• Prefix cache assumed semantic → silent wrong instructions after prompt edit
• Evaluating only mean latency → blind to p95 prefill storms
• Forgetting GQA/MQA — using wrong head counts in capacity spreadsheets
• Confusing Redis cache hits with engine prefix hits
• Enabling FP8 KV without task evals (tool JSON / faithfulness)

Micro-project

Measure TTFT vs decode speed for short vs long prompts on one model. Plot both; annotate which phase dominates each case. Bonus: repeat with a shared system prompt and report prefix-cache TTFT delta (if your engine supports it).

Related

• Serving and streaming
• vLLM · Continuous batching
• Caching and latency
• Redis for AI caching for application-level caches in front of the engine