Prefill vs Decode & KV Cache Mechanics
Time-to-first-token and tokens per second split because prefill and decode are different kernels. Prefill burns FLOPs on the prompt. Decode streams the KV cache from memory for one new token. This lesson is the byte math and the autoregressive loop those metrics sit on.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Which phase is the SLO?
Prefer
Split the request into prefill and decode
Time-to-first-token is queue plus prefill, plus any prefix-cache miss. Time per output token is the decode step under the current batch mix. They move different hardware resources.
- More tensor-core FLOPs help a long cold prompt.
- Memory bandwidth and KV footprint help the stream after the first token.
- A single-stream latency number hides multi-tenant KV pressure.
Alternative
One latency number for the whole completion
Optimizing only system tokens per second grows decode batches and misses the first-token SLO. Recomputing full attention every step is a demo, not a server.
- Ignoring dtype and KV-head count underestimates the cache.
- Reserving max context contiguously wastes the pool.
- Speculation does not shrink a cold long prefill.
Overview
Every serving interview reaches this question: why is time-to-first-token different from tokens per second, and where does the KV cache live? This page is the mechanism. Schedulers in SGLang and TensorRT-LLM assume it. The playbook uses the same words at decision level.
Autoregressive loop
- Tokenize the prompt and look up embeddings.
- Prefill. One forward, or a chunked forward, over all prompt positions. Write K and V for every layer and KV head.
- Sample the next token from logits.
- Decode. Append one token. Attend using cached K and V plus the new row. Sample. Repeat until end-of-sequence or the max length.
Attention at decode step t reads K and V up through position t and appends the new position. Without a cache, every step recomputes the whole prefix. That is a teaching toy.
Compute-bound prefill, bandwidth-bound decode
- Prefill. Large GEMMs over prompt length. High FLOPs per byte. Usually compute-bound, until a very long context saturates memory a different way.
- Decode. The GEMM is thin: a batch of sequences times one new token. The kernel still reads prior KV from HBM. Often memory-bandwidth-bound.
- Implication. A GPU with more peak FLOPs helps prefill more than decode. Decode cares about HBM bandwidth and how many KV bytes you touch.
Streaming-multiprocessor utilization can look low while the memory pipes are full. That profile is the interview answer for “the GPU looks idle.”
KV layout
Per layer, store Key and Value. A useful logical shape is batch B, heads H, sequence S, head dim D. With grouped-query or multi-query attention, KV heads are fewer than query heads, so H in the cache is H_kv, not the query-head count. Same formula, smaller H.
GQA and MQA are architecture choices. They are not a runtime switch you flip on a dense model that was trained with one KV head per query head.
Memory math
bytes ≈ 2 · n_layers · n_kv_heads · head_dim · seq_len · dtype_bytesThe factor of two is Key plus Value. FP16 and BF16 use 2 bytes. FP8 or INT8 KV uses 1 byte when the cache itself is quantized. Multiply by concurrent requests.
Worked example, allocator overhead ignored: 32 layers, 8 KV heads, head dim 128, sequence 4096, FP16.
2 · 32 · 8 · 128 · 4096 · 2 = 536870912 bytes ≈ 0.5 GiB per requestSixteen such requests are about 8 GiB of live KV. If each request instead reserves a contiguous 8192 while the live length averages 2048, three quarters of that reservation is empty. Paging is the next lesson because of that hole.
Fragmentation without paging
Static contiguous allocation per request, sized to max_length, leaves holes when sequences finish early. Beam search and parallel samples duplicate nearly identical prefixes unless copy-on-write shares the blocks. PagedAttention & Continuous Batching replaces the slab with a block table, the same idea as virtual memory.
TTFT, TPOT, and TPS
| Metric | Mechanism reading |
|---|---|
| TTFT | Queue wait plus prefill, plus work that a prefix-cache miss still has to do |
| TPOT | Decode step time under the current batch mix |
| TPS | Tokens per second for one user, or across the system |
User-perceived streaming uses both. TTFT is when the first chunk appears. TPOT is how smooth the rest feels. Product targets and dollar math stay in Comparative Playbook — Serving Stack Choice, Metrics & Failure Modes.
The SLO conflict is real: a large decode batch raises system tokens per second and hurts per-user TPOT and sometimes TTFT, because a long prefill blocks the iteration. Prefill/decode disaggregation shows up later in Inference Parallelism — Tensor Parallel, Expert Parallel & Prefill/Decode Disaggregation.
Phase diagram
Linear teaching order. The last edge is the decode loop returning to the cache.
Flow
- 1
1 Prompt tokens
- next2 Embed the prompt
- 2
2 Embed the prompt
- next3 Full-sequence forward
- 3
3 Full-sequence forward
- next4 Write KV for all positions
- 4
4 Write KV for all positions
- next5 Read the KV cache
- 5
5 Read the KV cache
- next6 Attend and FFN, one token
- 6
6 Attend and FFN, one token
- next7 Sample the next token
- 7
7 Sample the next token
- next8 Append the token and KV row
- 8
8 Append the token and KV row
Lesson map
Prefill vs Decode & KV Cache Mechanics
Time-to-first-token and tokens per second split because prefill and decode are different kernels. Prefill burns FLOPs on the prompt. Decode streams the KV cache from memory for one new token. This lesson is the byte math and the autoregressive loop those metrics sit on.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1 Prompt tokens"] b["2 Embed the prompt"] c["3 Full-sequence forward"] d["4 Write KV for all positions"] a -->|1 Prompt tokens to 2 Embed the prompt| b b -->|2 Embed the prompt| c c -->|3 Full-sequence forward| d
What helps which phase
| Knob | Helps | Does not magically fix |
|---|---|---|
| Chunked or split prefill | Bounds TTFT spikes on long prompts | Scheduler complexity |
| KV quantization | More concurrent sequences | Quality if you quantize too hard |
| GQA or MQA models | Smaller KV | It is an architecture, not a server flag |
| Prefix-cache hit | Skips repeated prefill | Tree policy. See the SGLang study |
| Speculative decode | Decode TPOT when acceptance is high | A cold long prompt’s prefill |
Deep dive · Chunked prefill, one paragraph
Chunked prefill splits a long prompt into pieces so decode iterations for other requests can run between chunks. It is a scheduling idea that protects TTFT and keeps the decode pool moving. How TensorRT-LLM folds context and generation into one engine iteration is TensorRT-LLM — Engine Build, In-Flight Batching & Quantization. Do not rebuild that engine here.
Sandbox: KV byte estimator
Press Run. Snippets must be self-contained — no network, files, or native modules.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Pitfalls
Take the 32-layer, dim-128 example. Drop KV heads from 8 to 2 (grouped-query). Then switch dtype from 2 bytes to 1. What is the new per-request GiB at sequence 4096? If you still reserve 8192 for a live length of 2048, what fraction is waste? Waste fraction does not change with heads or dtype. Why?
Interview Q&A
Give the KV byte formula and the units.
Answer
Bytes are about 2 · layers · kv_heads · head_dim · seq · dtype_bytes, times the number of requests. The 2 is Key plus Value. Interviewers want that factor and the reminder that grouped-query attention shrinks kv_heads. This ignores allocator overhead and kernel workspace.
Why can a GPU look idle on FLOPs during decode and still be saturated?
Answer
HBM bandwidth is saturated streaming KV. Streaming multiprocessors wait on memory. The profile is memory-bound, not an empty machine. Buying more peak FLOPs does not move that step much.
How do TTFT and TPOT relate to streaming the user sees?
Answer
TTFT is when the first chunk appears (queue plus prefill, and any prefix miss). TPOT is the gap between later tokens. Both matter. Numeric product targets live in Comparative Playbook — Serving Stack Choice, Metrics & Failure Modes.
What does grouped-query attention change in the cache?
Answer
Fewer KV heads than query heads. The byte formula uses n_kv_heads. Query heads still do the attention math, but you do not store a K and V for every query head. You cannot turn GQA on at serve time if the checkpoint was trained dense.
Why does a contiguous max-length reservation waste so much memory?
Answer
The allocator holds max_seq for every request even when the live length is short, and finished requests leave holes that the next request may not fit. Sixteen requests reserved to 8192 with a live length of 2048 waste 75 percent of that reservation before overhead. Paging fixes the geometry.
Does speculative decoding shrink prefill?
Answer
No. It spends extra compute to advance several decode tokens per target step when the draft is good. A cold 8k prompt still pays prefill. See Speculative Decoding.
What is chunked prefill for?
Answer
It slices a long prompt so one prefill does not monopolize the GPU while other requests need decode steps. You trade scheduler complexity for a tighter TTFT tail. It is not a substitute for a prefix hit on a repeated system prompt.
Where does a prefix-cache hit show up in these metrics?
Answer
It skips repeated prefill, so TTFT drops on the shared prefix. The production tree, eviction, and match rules are SGLang — RadixAttention, Continuous Batching & Structured Generation. This page only names the effect.
Why is measuring one request a bad capacity test?
Answer
KV bytes scale with concurrency. A single stream can look fast while 32 streams OOM or stall on bandwidth. Report live sequence length, dtype, KV heads, and concurrent sequences together.
FP16 versus FP8 KV: what do you say out loud?
Answer
Halving dtype bytes halves the cache, all else equal, and can raise concurrency. Quality risk is real if the KV quantization is too aggressive. State the dtype in the formula instead of quoting a single GiB number with the dtype implied.
Go Deeper
- PagedAttention paper — why contiguous KV wastes memory
- Hugging Face cache strategies
- Hugging Face caching explanation
- NVIDIA TensorRT-LLM on H100 — throughput versus latency, vendor-reported
- Comparative Playbook — Serving Stack Choice, Metrics & Failure Modes
- Next: PagedAttention & Continuous Batching