Lesson 17.2• 8 min read

Batching and the KV cache

Serving many requests at once, the memory each one keeps, and which limit binds first.

What you will learn

  • Say why serving many requests together multiplies what one GPU produces.
  • Tell static, dynamic and continuous batching apart, and say what each costs a request in waiting.
  • Size the KV cache a request keeps, and check whether a GPU's memory holds the requests its rate puts in flight.
  • Say what changes when a model does not fit one GPU.

Why batch at all

Lesson 17.1 showed that a decode step reads the model's weights from memory to make one token, and leaves the GPU's arithmetic mostly idle. A batch is a group of requests the server runs together: one decode step then makes one token for every request in it. The weights are still read once a step, but now serve every request, so the arithmetic done for each byte read rises, and so do the tokens made a second.

Prefill gains far less: it already processes a whole prompt's tokens at once, and a prompt that is not very short keeps the arithmetic busy by itself.

Batching has a price: each step does more work, so it takes longer, and each request's answer comes more slowly. A server is tuned to batch as much as it can while still meeting its time targets.

Waiting for a full batch

The simplest way to form a batch, static batching, waits until a set number of requests has arrived and then runs them. The first request waits for the last, however late it comes.

Dynamic batching adds a time limit: the batch starts when it is full or when the limit is reached, whichever comes first. A request then waits at most the limit before it starts.

Both still run the batch as one piece: it finishes when its longest request finishes, and a request that arrives meanwhile waits for the next batch. For a model, answers differ greatly in length, so a short answer waits for a long one and the GPU's places in the batch sit empty as answers finish.

Batches that never close

Continuous batching changes the unit of scheduling from a request to a step. Before each step the server decides which requests take part: a request that has finished leaves at once and its answer is returned, and a waiting request takes its place, without waiting for the others. No batch ever has to fill or empty. The Orca paper (2022), which introduced scheduling a step at a time, reported 36.9 times the throughput of the system it was compared with, at the same response time, on its own test with a model of 175 billion weights. vLLM, the software of lesson 17.1's run, batches this way.

What each request keeps in memory

When the model processes a token, it computes at each layer (a model is a stack of them, each passing its results to the next) two lists of numbers for that token, a key and a value, which later tokens look back at. Computing them again for every new token would repeat the same work, so the server keeps them in the GPU's memory for as long as the request runs: the KV cache. It grows by one token's keys and values with every token the request reads or writes.

A layer does its looking back in several calculations side by side, its attention heads, each catching a different kind of relation between tokens. The keys and values are kept per key/value head, each holding a fixed count of numbers for a token, the head size. In the original design every attention head has a key/value head of its own; in grouped-query attention a group of attention heads shares one, which makes the KV cache smaller. One token's KV cache, in bytes, is

bytes a token=2×layers×key/value heads×head size×bytes a value\text{bytes a token} = 2 \times \text{layers} \times \text{key/value heads} \times \text{head size} \times \text{bytes a value}

The 2 counts the key and the value. Llama 3.1 8B has 32 layers, 32 attention heads and 8 key/value heads of 128 numbers each (Meta's model repository): grouped-query attention, four attention heads to each key/value head. At 16 bits, 2 bytes a value:

2×32×8×128×2=131,072 bytes=128 KiB2 \times 32 \times 8 \times 128 \times 2 = 131{,}072 \text{ bytes} = 128 \text{ KiB}

Count the key/value heads, not the attention heads: 32 would give four times the KV cache. For a model with one key/value head to each attention head, such as the Llama 2 7B example in Hands-On LLM Serving and Optimization, the two counts are equal, and the formula is the one the books give for such models.

A request holds one token's KV cache for every token of its prompt and its answer. In the H100 run of lesson 17.1, a prompt averaged 871 tokens and an answer was at most 128, so a request at its longest holds

(871+128)×131,072 bytes≈131 MB(871 + 128) \times 131{,}072 \text{ bytes} \approx 131 \text{ MB}

Memory or speed

How many requests does the GPU hold at once? Little's law (lesson 1.2) gives it: requests in flight = arrival rate × mean time each spends. In the H100 run: 39.56 requests a second × 3.318 s, its mean whole answer, is about 131 requests in flight.

Their KV caches must fit beside the weights. The run gave vLLM 91% of the GPU's 80 GB (Red Hat's published settings), and its weights take 9.08 GB (lesson 17.1), so the room left for the KV cache was about

80×0.91−9.08=63.7 GB80 \times 0.91 - 9.08 = 63.7 \text{ GB}

The lab simplifies this in two ways that pull opposite ways: 80 GB is read as 80×10980 \times 10^9 bytes, the smaller reading of NVIDIA's figure, and the software's own working memory, which comes out of the same share and is not published, is left out. The run left the KV cache's precision to vLLM's default, the model's own data type, which its settings do not state in bits; taking 16 bits, the larger, 131 requests at 131 MB each need 17.2 GB (at 8 bits, half that). The KV cache filled about a quarter of its room, so memory did not limit this run: the room holds 486 such requests.

So two limits stand on a model server, and a design checks both. Speed: how many requests a second the GPU can finish within its time targets, which a benchmark measures. Memory: how many requests in flight their KV caches let it hold, which the formula above computes. When the KV cache runs out, the vLLM documentation says the server pauses some running requests to free room, and computes them again once room frees, which lengthens their answers.

Memory also wasted inside the KV cache counts against the room. Reserving every request's longest possible KV cache in one piece wastes memory, since an answer's length is not known in advance. PagedAttention, from the vLLM paper (2023), keeps the KV cache in small fixed-size blocks placed wherever memory is free, as an operating system pages memory; the paper reports near-zero waste in KV cache memory.

A measured pair where memory is the likely limit: the GH200, one chip sold with 96 GB of GPU memory (up to 4 TB/s) or 144 GB (up to 4.9 TB/s), NVIDIA's figures. In MLPerf Inference 5.0, both ran Llama 2 70B with the same software, its layers' weights at 8 bits and the rest at 16 (NVIDIA's published notes on how it lowers the precision): about 69.5 GB of weights.

96 GB (entry 5.0-0066) 144 GB (entry 5.0-0059)
Requests a second, within the time limits 10.96 14.87
Requests a second, with no time limits 10.79 16.07

The 96 GB chip's p99 first token was 324 ms against a limit of 2,000, and its p99 time per token 72 ms against 200: far from both limits. With no time limits at all it did no better. The larger chip did 1.49 times as much with no limits, on 1.23 times the bandwidth and 1.5 times the memory. That points to memory: with about 69.5 GB of weights, the 96 GB chip has far less room for KV caches. With no time limits a server can hold more requests at once, which is where room for KV caches would bind first. Neither run says so, and the two were submitted by different firms, so this is inferred, not measured.

Long prompts that stall others

With continuous batching, a new request's prefill and the running requests' decode steps share the GPU. A long prompt's prefill takes far longer than a decode step, so the running requests stall behind it and their time per token rises.

Chunked prefill splits a long prefill into pieces of about a decode step's size, run alongside the decode steps, so writing answers no longer stops for a long prompt. The trade, as Hands-On LLM Serving and Optimization describes it: the time per token improves, the new request's first token comes later, and throughput usually rises. Sarathi-Serve (2024) introduced it with schedules that add new requests without pausing running decodes. In vLLM 0.10.0's default engine it is always on, and a setting caps the tokens one step may take.

When one GPU is not enough

A model whose weights do not fit one GPU's memory must be split across several. Lower the precision first: at 8 bits the weights take half the memory they take at 16, and at 4 bits a quarter, if the accuracy holds. A model that then fits one GPU is best kept on one: on an H100, NVIDIA's fast links between GPUs carry 900 GB/s, about a quarter of the 3,350 GB/s it reads its own memory at (NVIDIA's figures), so a second GPU does not double the speed (Hands-On LLM Serving and Optimization).

  • Tensor parallelism splits every layer across the GPUs. Each holds part of each layer, and the GPUs exchange results at every layer.
  • Pipeline parallelism gives each GPU a run of whole layers, so they exchange results only between stages; a slow stage leaves the others waiting.
  • Data parallelism runs whole copies of the model, each serving its own requests. It adds throughput, and each copy needs room for the whole model.

A split copy needs every GPU it is split over, since each holds only part of the model, so losing one GPU stops the whole copy. A system that runs one copy across all its GPUs is lost whole; one that runs two copies, each across half of them, keeps the other copy and half its rate. A model that fits one GPU is still split when one GPU cannot serve it fast enough to meet its time targets. A benchmark run on several GPUs measures that whole system, split as it was split.

What a GPU’s memory holds

The weights first, then a KV cache for every request in flight. Requests whose KV caches do not fit wait.

999
131
Weights KV caches Room Not given to the software
Weights9.1 GB
Room for KV caches63.7 GB
KV cache a request131 MB
Requests that fit486
Waiting for room0

Little’s law for the H100 run: 39.56 requests a second × 3.318 s = 131 in flight.

GPUs and the share of memory each run gave its software: MLPerf Inference 5.1, entries 5.1-0083 and 5.1-0082 (Red Hat, vLLM 0.10.0). Model shapes: Meta’s model repository.

Key takeaways

  • A decode step reads the weights once whether it serves one request or many, so batching multiplies tokens a second; each request's answer gets slower.
  • Static and dynamic batching run a batch as one piece and make short answers wait for long ones; continuous batching lets a request enter or leave at every step.
  • A request's KV cache is 2×layers×key/value heads×head size×bytes2 \times \text{layers} \times \text{key/value heads} \times \text{head size} \times \text{bytes} for each of its tokens: 128 KiB a token for Llama 3.1 8B at 16 bits, about 131 MB for a request of 999 tokens.
  • Check memory against speed: requests in flight (rate × mean time) × each one's KV cache must fit the room the weights leave. The H100 run's 131 requests needed 17.2 GB of 63.7 GB.
  • A model too large for one GPU is first made smaller by a lower precision, then split over several; a split copy needs all of its GPUs, so losing one stops it.
Sources12