Skip to content
LearnMLByDoing
Free

6.4 LLM serving: KV cache, batching and speculative decoding

32 minProadvancedvLLMCompendiumGCP-PMLEAIP-C01Spec. decoding

Each generated token rereads the model's weights and a growing cache of keys and values, so LLM serving is mostly memory traffic, and its main techniques (batching, paged caches, speculative decoding) aim to get more tokens out of each byte read.

01Prefill and decode: two different workloads

A request is served in two phases. Prefill runs the whole prompt through the model in one forward pass and produces the first output token. Decode then generates one token per forward pass, each pass conditioned on everything before it. The viewport shows one sequence in 8 of its 32 layers: the amber (keys) and cyan (values) slabs fill in one burst for the 24 prompt tokens, then grow by one thin slice per decoded token while the emerald query reads every earlier slice.

The two phases stress different parts of the GPU. A picture first: the chip can multiply far faster than it can fetch the numbers to multiply. Its memory bandwidth WW is how many bytes per second it can read from its memory (HBM), and its compute rate FF is how many floating-point operations (FLOPs) per second it can do. Every forward pass must read every weight at least once, so a pass that does little arithmetic per weight read waits on memory, and one that does a lot waits on compute.

For a model with NN parameters, two different quantities happen to both equal 2N2N. A forward pass costs about 2N2N FLOPs per token, because each weight is used once in a multiply and once in an add. It also has to stream about 2N2N bytes of weights, because each FP16 number takes 2 bytes. Prefill uses each weight for every prompt token at once; decode uses it for one token per sequence. FLOPs divided by bytes, the arithmetic intensity II, decides which resource runs out first.

Roofline time of one forward pass1/5
  1. 1
    t≈max⁡ ⁣(FLOPsF, bytes movedW),I=FLOPsbytest \approx \max\!\Big(\frac{\text{FLOPs}}{F},\ \frac{\text{bytes moved}}{W}\Big),\qquad I=\frac{\text{FLOPs}}{\text{bytes}}

    F is the GPU's compute rate, W its memory bandwidth. Above the ridge point I = F / W the pass is compute-bound, below it memory-bound.

Loading figure
Drag the cyan decode dot to the right: every extra sequence in the batch reuses the same weight read, so I≈BI \approx B and the attainable FLOP/s climb the amber memory slope until B=150B = 150, the ridge. The emerald prefill dot sits at I≈npI \approx n_p: a 1000-token prompt is far past the ridge and takes about 93 ms of pure compute. Switch to INT4: the weights shrink 4×, so each sequence's intensity quadruples. The decode dot also moves the scene's batch size (up to 32). The widget counts weight bytes only; the HUD adds the KV cache.

Read the HUD: with B=1B = 1 and a 4096-token context the time per output token is 16.116.1 ms, of which about 1414 ms is the weights and the rest is the 2 GiB cache. The two latency metrics of LLM serving follow from the two phases: TTFT\tok{ttft}{\mathrm{TTFT}}, the time to first token, is queueing plus prefill, and TPOT\tok{tpot}{\mathrm{TPOT}}, the time per output token, is one decode step.

Keep one sequence but raise the maximum context to 16,384 tokens.

Maths, CS & AI Compendium, Henry Ndubuaku, Inference and serving

Efficient Memory Management for LLM Serving with PagedAttention, Kwon et al., 2023, Sec. 2.2 (prompt and autoregressive generation phases)

02The KV cache and its memory formula

A reminder of what is being cached: in every layer, attention turns each token into a query (what this token is looking for), a key (what it offers to be matched against) and a value (what it passes on when matched); lessons 4.0 and 4.1 show this. Attention for a new token needs the keys and values of every earlier token, in every layer. Recomputing them from the prefix at each step would make step tt cost O(t)O(t) projections and generation O(n2)O(n^2). Instead the server stores them once: the KV cache. Each decode step then computes one new key and value per layer, appends them (the emerald flash) and reads all the stored ones.

K cache (one layer; V is identical)[,,,]

One such tensor for keys and one for values in each of the L = 32 layers. Only n grows during decoding.

Bytes held by the cache1/4
  1. 1
    kt(ℓ), vt(ℓ)∈RHkv⋅dheadk_t^{(\ell)},\,v_t^{(\ell)} \in \mathbb{R}^{\tok{kv_heads}{H_{kv}}\cdot d_{head}}

    Per layer and token: one key and one value vector for each KV head, so 2 · H_kv · d_head numbers.

The HUD shows exactly that: 512 KiB per token, 2.00 GiB per 4096-token sequence, and 16.00 GiB for B=8B = 8, while only 11 GiB of the 24 GiB GPU is left after 13 GiB of weights. On this GPU the cache, not the weights, limits the batch: at most 5 such sequences fit, so the HUD marks B=8B = 8 as not fitting. Each decode step also rereads the whole cache, so if B=8B = 8 did fit, each step would take 31.131.1 ms.

Loading figure
Build a configuration that fits before reading on. Each chip is one factor of MKVM_{KV} and lights when you change it; sequences that do not fit turn rose past the end of the GPU. The controls are the scene's, so the 3D cache view and its HUD follow.

Keep B=8B = 8 and drop to a single KV head shared by all 32 query heads.

Efficient Memory Management for LLM Serving with PagedAttention, Kwon et al., 2023, Sec. 3 (memory challenges in LLM serving)

Maths, CS & AI Compendium, Henry Ndubuaku, Attention variants: MQA and GQA

03Static, dynamic and continuous batching

Batching is the main lever on decode throughput: one read of the weights serves every sequence in the batch. With the step-time model above and about 1k cached tokens per sequence, one step takes 14.514.5 ms at B=1B = 1 (69 tokens/s) and 18.318.3 ms at B=8B = 8 (438 tokens/s): six times the throughput for 26% more latency per token. The question is how to keep the batch full when requests generate different numbers of tokens.

The viewport schedules 24 requests that need between 3 and 40 decode steps (435 in total) on B=8\tok{batch}{B} = 8 slots. Time runs to the right, slots run in depth; each request starts with an amber prefill cell, emerald and cyan cells are decode steps, and rose cells are idle slots.

Static batching takes requests in groups of BB and runs each group until its longest member finishes; slots whose request ended early sit idle. Dynamic batching is static batching with a smarter trigger: the server waits until BB requests have arrived or a maximum delay expires, trading a little queueing delay for fuller batches. It suits fixed-cost models such as classifiers and embedding encoders. Continuous batching (iteration-level scheduling) decides at every decode step: a finished sequence leaves, and a queued request takes its slot on the next step.

utilisation=∑iℓiB⋅Tsteps:4358⋅108=50% (static),4358⋅77=71% (continuous)\text{utilisation}=\frac{\sum_i \ell_i}{B\cdot T_{\text{steps}}}:\qquad \frac{435}{8\cdot 108}=50\%\ \text{(static)},\qquad \frac{435}{8\cdot 77}=71\%\ \text{(continuous)}
ℓ_i is the number of steps request i needs; the rest of the slot-steps are the rose bubbles. Utilisation here means slot occupancy (how many batch slots hold a running request), not GPU busy time and not the ρ of lesson 6.3.

The HUD for continuous batching reads 77 steps, 71% utilisation, a mean TTFT of 17.0 steps and 332 tokens/s. Switch Batching to static: 108 steps, 50% utilisation, 250 tokens/s, and the mean TTFT doubles to 36.0 steps, because a request that arrives behind a long batch waits for all of it. The dashed marker shows where the other policy finishes. The viewport schedules static and continuous batching only: every request is queued at time 0 here, so dynamic batching's arrival-time trigger would behave exactly like static.

Give static batching 12 slots instead of 8.

Now go the other way: continuous batching with 16 slots.

Two refinements matter at scale. Chunked prefill splits a long prompt into pieces of a few hundred tokens and runs each piece in the same step as the ongoing decodes, so a 4000-token prompt no longer freezes every other user's stream for a whole compute-bound pass. Prefill/decode disaggregation goes further and runs the two phases on different GPUs, since one is compute-bound and the other memory-bound. The operational target that ties these together is goodput: the throughput a server sustains while still meeting its latency targets, for example tokens/s at a p95 TPOT under 50 ms. It is the same idea as the p95 capacity planning of lesson 6.3, measured per token instead of per request.

Efficient Memory Management for LLM Serving with PagedAttention, Kwon et al., 2023, Sec. 2.3 (batching techniques for LLMs)

Professional Machine Learning Engineer exam guide, Google Cloud, Serving and scaling models

The rest of this lesson is in Pro

  • 04Fragmentation, paged KV caches and prefix caching
  • 05Speculative decoding: several tokens per target pass
  • 06Serving metrics and capacity planning
  • Python challenge: Size the cache, schedule the batch
  • Knowledge check, 4 questions

Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.

Compiling scene

The Python challenge and knowledge check for this lesson are part of Pro.

Questions learners ask

What is the KV cache in LLM inference?
It is the stored keys and values of every token a decoder has already processed, kept for every layer so that each new token only computes its own key and value and attends to the stored ones. Its size is 2 times layers times KV heads times head dimension times bytes per element, per token and per sequence, which for a 7B model with full multi-head attention in FP16 is about half a megabyte per token and 2 GiB for a 4096-token sequence.
What is the difference between static and continuous batching?
Static batching starts a group of requests together and keeps the group until its longest request finishes, so slots of short requests sit idle and new requests wait for the whole group. Continuous batching, also called iteration-level scheduling, re-forms the batch at every decode step: finished sequences leave and waiting requests join immediately, which raises GPU utilisation and throughput and lowers time to first token.
Does speculative decoding change the model's output?
No, when it uses the rejection sampling rule from the original papers. A draft token is accepted with probability equal to the ratio of the target's and the draft's probabilities, capped at one, and a rejected position is resampled from the normalised difference between the two distributions, which makes every output token distributed exactly as the target model alone would sample it. Only the speed depends on how often the draft agrees with the target.

Next in Production MLOps and Certification Prep

6.5Responsible AI, fairness and generative AI securityGroup fairness metrics and their trade-offs, explainability, and the prompt-injection and data-exfiltration threats every AI exam now covers.

Sources

  • Efficient Memory Management for LLM Serving with PagedAttention, Kwon et al., 2023
  • Maths, CS & AI Compendium, Henry Ndubuaku
  • Professional Machine Learning Engineer exam guide, Google Cloud
  • AWS Certified Generative AI Developer – Professional exam guide, Amazon Web Services
  • Fast Inference from Transformers via Speculative Decoding, Leviathan, Kalman & Matias, 2023