KV cache, GQA, paging and continuous batching

What it is

Four techniques that together determine how many concurrent users a GPU can serve. They are usually discussed separately and they are one system, because each attacks a different term in the same memory equation.

The KV cache stores the key and value projections for every previous token so that generating token $n+1$ does not recompute attention over tokens $1..n$. It turns generation from quadratic to linear in sequence length, and it is the reason inference is affordable at all.

Grouped-query attention (GQA) shares one key/value head across several query heads, cutting cache size by the sharing factor.

PagedAttention allocates the cache in fixed-size blocks with a page table rather than one contiguous reservation per sequence, eliminating fragmentation.

Continuous batching admits new requests at every decode step rather than waiting for a batch to drain, so the GPU is never idle waiting for the slowest sequence in a batch to finish.

Commonly confused with model size as the capacity constraint. Weights are a fixed cost paid once; KV cache is the per-user cost and it scales with context length. A 7B model serving 128k contexts runs out of memory before a 70B model serving 2k contexts does.

The problem it solves

Without a KV cache, generating a 500-token response over a 2,000-token prompt means recomputing attention over a growing prefix 500 times, which is quadratic work for a linear output. Nobody does this.

With a cache, three new problems appear, and each technique is the answer to one:

The cache is large, and it competes with weights for HBM. GQA shrinks it.
The cache is allocated badly. Reserving the maximum possible sequence length per request wastes most of it. PagedAttention fixes that.
The GPU is idle. In a static batch, every sequence waits for the longest one to finish before the next batch starts. Continuous batching fixes that.

Mechanics

The memory equation

$$\text{cache bytes} = 2 \times L \times H_{kv} \times d_{head} \times S \times B \times b$$

$L$ layers, $H_{kv}$ key/value heads, $d_{head}$ head dimension, $S$ sequence length, $B$ batch, $b$ bytes per element, and the leading 2 for K and V.

The lever is $H_{kv}$, and that is what GQA changes:

Attention scheme	$H_{kv}$	Cache relative to MHA	Quality
Multi-head (MHA)	= query heads	1x	baseline
Grouped-query (GQA)	query heads / G	1/G	near-baseline at G = 8
Multi-query (MQA)	1	1 / query heads	measurable degradation

Worked, for a 70B-class model with 80 layers, 64 query heads, $d_{head} = 128$, fp16:

MHA  (H_kv = 64): 2 x 80 x 64 x 128 x 2 B = 2,621,440 B/token = 2.5 MiB/token
GQA  (H_kv =  8): 2 x 80 x  8 x 128 x 2 B =   327,680 B/token = 320 KiB/token
MQA  (H_kv =  1): 2 x 80 x  1 x 128 x 2 B =    40,960 B/token =  40 KiB/token

At 8,000 tokens of context, per sequence:
  MHA  20 GiB     GQA  2.5 GiB     MQA  0.3 GiB

On 4x80 GB with 140 GB of weights, ~180 GB free for cache:
  MHA:   9 concurrent sequences
  GQA:  72 concurrent sequences
  MQA: 600 concurrent sequences (memory-wise; other limits bind first)

GQA is an 8x capacity multiplier, which is why every recent model ships with it. That is the number to have ready.

PagedAttention: why fragmentation was eating most of the rest

The naive allocator reserves max_seq_len per request up front, because the cache must be contiguous for the attention kernel. If max_seq_len is 4,096 and the average request uses 600 tokens, 85 percent of every reservation is never touched.

PagedAttention borrows virtual memory: the cache lives in fixed-size blocks (typically 16 tokens), a per-sequence block table maps logical positions to physical blocks, and blocks are allocated on demand as the sequence grows.

Sequence A (logical)   block table          physical KV blocks
  tokens   0-15   ---->  block 7      [0] free
  tokens  16-31   ---->  block 3      [3] A:16-31
  tokens  32-40   ---->  block 12     [7] A:0-15
                                      [9] B:0-15   <- shared prefix
                                     [12] A:32-40  <- partially filled, that is
Sequence B (logical)                                  the ONLY internal waste
  tokens   0-15   ---->  block 9

Two consequences. Internal fragmentation drops to at most one partly-filled block per sequence, a few percent instead of most of it. And blocks can be shared: two sequences with a common prefix point at the same physical blocks, copy-on-write at divergence. That is the mechanism behind prefix caching.

The vLLM paper reported that naive allocation wasted 60 to 80 percent of cache memory, and that recovering it raised throughput by 2 to 4 times against the then-current serving systems at equal latency.

Prefix caching: the biggest single lever most teams have

If every request shares a 4,000-token system prompt, blocks for that prefix are computed once and reused across all of them. The effect on a short-query workload is dramatic, because prefill is the compute-bound phase and you have eliminated most of it.

Workload: 4,000-token system prompt, 200-token user query, 300-token answer

Without prefix caching, per request:
  prefill 4,200 tokens (compute bound)  +  decode 300 tokens

With prefix caching:
  prefill    200 tokens                 +  decode 300 tokens
  -> ~95% of prefill work eliminated; TTFT falls accordingly

The design consequence is worth stating because it changes how you write prompts: put stable content first and volatile content last, because caching is a prefix match. A timestamp at the top of the system prompt makes every request a cache miss. This is the same discipline as context budgeting and the same discipline as API-level prompt caching.

Continuous batching

Static batching wastes the GPU in a specific, measurable way:

Static batch of 4. Sequence lengths differ, so three GPUs' worth of slots
sit idle waiting for the longest one.

  seq A  ####################............(idle)........
  seq B  ########....................(idle)............
  seq C  ############################################..
  seq D  ######......................(idle).............
         |------------- one batch ------------------->| next batch starts

Continuous (iteration-level) batching. A finished sequence's slot is
refilled at the next decode step.

  seq A  ####################E  seq E  ###############
  seq B  ########E  seq F  #############  seq H  #####
  seq C  ############################################
  seq D  ######E  seq G  ######################E  seq I

Orca introduced this as iteration-level scheduling, and it is the single largest throughput lever in a serving stack because it removes idle slots entirely. The reason it works well specifically for decode is the amortisation argument: reading the weights once serves the whole batch, so adding a sequence is nearly free until cache reads start to rival weight reads.

The complication is prefill interference. A newly admitted request needs a prefill, which is compute-heavy and stalls every in-flight decode. Chunked prefill splits the prompt into pieces and interleaves them with decode steps, trading a little time-to-first-token for much better tail inter-token latency. This is a configuration flag in modern stacks and it is the first thing to enable when p99 TPOT is bad.

The scheduler, and preemption

# The core of an iteration-level scheduler. Two properties matter:
# admission is bounded by free cache blocks, not by a batch-size constant;
# and running sequences can be preempted when memory runs out.
def step(running, waiting, cache):
    # Admit while blocks allow. A request needing more blocks than exist
    # waits rather than causing an allocation failure mid-generation.
    while waiting and cache.free_blocks() >= waiting[0].blocks_needed():
        running.append(waiting.popleft())

    # Preemption: generation is not sized in advance, so a long-running
    # sequence can exhaust memory. Evict the newest (least work invested)
    # and either recompute its prefill later or swap its blocks to host memory.
    while cache.free_blocks() == 0 and len(running) > 1:
        victim = running.pop()          # newest first
        cache.swap_out(victim)          # or drop and recompute on resume
        waiting.appendleft(victim)

    tokens = model.decode_step(running)  # one token for every running sequence
    for seq, tok in zip(running, tokens):
        seq.append(tok)
        if seq.finished():
            cache.free(seq); running.remove(seq)

Preemption is the part people do not expect: because output length is unknown when a request is admitted, the scheduler can over-commit and must be able to evict. Knowing that a serving stack preempts, and that preemption shows up as a latency outlier rather than an error, is a strong practitioner signal.

A worked example: sizing a deployment

"Serve a 70B model, 500 concurrent users, average 3,000-token context, p99 time-to-first-token under 2 seconds."

Model: 70B fp16 = 140 GB weights. Fits on 2x H100 80GB with tensor parallelism,
       but that leaves ~20 GB for cache. Use 4x for headroom.

Cache per sequence (GQA, 80 layers, 8 KV heads, d_head 128, fp16):
  320 KiB/token x 3,000 tokens = 0.94 GiB

Available on 4x80 GB:
  320 - 140 (weights) - ~20 (activations, fragmentation, framework) = 160 GB
  160 / 0.94 = ~170 concurrent sequences per node

500 concurrent users / 170 = 3 nodes, so 12 GPUs. Round to 4 nodes for
headroom and rolling deploys.

If that is too expensive, the levers in order of return:
  1. KV cache quantisation to fp8: halves cache -> ~340 seq/node -> 2 nodes
  2. Prefix caching, if the 3,000 tokens share a system prompt: cuts prefill
     work sharply, raises throughput per node without touching memory
  3. Shorter contexts: linear in cache
  4. A smaller model: changes quality, so it is a product decision

Two things to say out loud while doing this. The binding constraint is cache, not compute, which is why the arithmetic runs on memory. And 500 concurrent users is not 500 requests per second: with a 6-second average generation, 170 concurrent sequences serve about 28 requests per second, so check which number the requirement actually is. That distinction (Little's Law again) catches people out.

Production evidence

Kwon et al., "Efficient Memory Management for Large Language Model Serving with PagedAttention" (SOSP 2023) is the vLLM paper: the fragmentation measurement, the block-table design, prefix sharing with copy-on-write, and the 2 to 4 times throughput result.

Yu et al., "Orca: A Distributed Serving System for Transformer-Based Generative Models" (OSDI 2022) introduced iteration-level scheduling, now universally implemented as continuous batching.

Ainslie et al., "GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints" (2023) established that grouped-query attention retains quality close to multi-head while cutting cache by the grouping factor, and it is why essentially every frontier model since ships with GQA. Shazeer's multi-query attention (2019) is the more aggressive predecessor.

vLLM, TensorRT-LLM, SGLang and TGI all implement paged cache management, continuous batching, prefix caching and chunked prefill. Four independent implementations converging is the strongest evidence that these are the right primitives.

The debate

The alternative to running any of this yourself is a managed inference endpoint, where all four techniques are somebody else's problem. For most product teams that is the right call: GPU capacity planning is genuinely hard, cold starts are minutes rather than seconds, and the engineering to run vLLM well is not free.

Self-hosting starts to pay at three thresholds. Spend: once token cost exceeds roughly a fully loaded engineer per year, the arithmetic changes. Model access: you need a model or a fine-tune nobody hosts. Prefix caching over a large shared prompt, which is the underrated one, because a workload with a 4,000-token shared system prompt and short queries gets an enormous win from caching that a per-request-priced API may not expose.

Between the techniques there is no real tradeoff to argue: enable all four. The genuine decisions are KV cache quantisation (fp8 or int8 cache halves or quarters memory with small quality cost, and it is the highest-return knob once you are memory-bound) and tensor parallelism degree, where more GPUs cut per-GPU bytes read per decode step but add an all-reduce per layer, so it improves latency sublinearly and does not give linear throughput.

My position: use a managed endpoint until you have a measured reason not to. When you do self-host, the sizing arithmetic runs on KV cache rather than weights, prefix caching is the first optimisation to reach for because it attacks the compute-bound phase, and chunked prefill is the first thing to enable when tail inter-token latency is bad.

This whole area is the wrong focus when the latency problem is not on the GPU at all. A surprising share of "our LLM endpoint is slow" is a synchronous retrieval call, a guardrail model in the path, tokeniser overhead, or JSON serialisation. Measure before optimising the accelerator.

Follow-up Q&A

"What actually limits how many users a GPU can serve?" KV cache memory. Weights are a fixed cost paid once; cache is per-sequence and scales with context length. Compute the per-token cache size from layers, KV heads, head dimension and dtype, multiply by context length, and compare against GPU memory minus weights minus activation workspace. A 7B model at 128k context exhausts memory before a 70B model at 2k does, which is the counterintuitive consequence worth stating.

"How much does GQA buy you?" The grouping factor, directly, because cache size is linear in KV head count. Going from 64 query heads with 64 KV heads to 64 query heads with 8 KV heads is an 8x reduction in cache, which is an 8x increase in concurrent sequences at the same memory. Quality cost is small at that grouping; multi-query attention (one KV head) goes further and does show measurable degradation, which is why GQA became the default rather than MQA.

"What problem does PagedAttention solve?" Fragmentation. The naive allocator reserves the maximum sequence length per request because the attention kernel wants contiguous memory, and most of every reservation goes unused; the vLLM paper measured 60 to 80 percent waste. Paging allocates fixed-size blocks on demand with a per-sequence block table, so internal waste is at most one partly-filled block. The second benefit is that blocks can be shared between sequences with a common prefix, copy-on-write at divergence, which is how prefix caching is implemented.

"Why does batching help decode so much and prefill so little?" Amortisation. In decode the GPU reads every weight from HBM to produce one token per sequence, so reading the weights once serves the whole batch and adding a sequence is nearly free until cache reads start to rival weight reads. In prefill the GPU is already saturated with arithmetic from a single long prompt, so batching two prefills just queues them. That asymmetry is why continuous batching is a decode optimisation.

"Your p99 inter-token latency spikes when users paste long documents. Diagnose." Prefill interference. A long prefill occupies the GPU for hundreds of milliseconds and every other request's decode step waits behind it. Enable chunked prefill, which splits the prompt and interleaves it with decode steps, trading a little TTFT for much better tail TPOT. If that is not enough, cap prompt length or route long-context requests to a separate pool. This is the question that most cleanly separates people who have operated a serving stack from people who have read about one.

Common misconceptions

The most common is that model size determines concurrency. Weights are fixed; cache is per-user and scales with context.

The second is that a larger batch is always better. It is, for decode throughput, until KV cache exhausts memory and the scheduler starts preempting, at which point latency degrades sharply and you have traded p99 for throughput without meaning to.

The third is that prefix caching is a minor optimisation. On a workload with a large shared system prompt and short queries it eliminates most of the compute-bound phase, which is usually the single biggest available win.

Interview delivery note

Say this, and do the arithmetic out loud: "The constraint is KV cache, not weights. Per token it's two, for K and V, times layers, times KV heads, times head dimension, times bytes. For a 70B model with 80 layers, 8 KV heads under GQA and head dimension 128 in fp16, that's 320 kibibytes per token, so 2.5 gibibytes for an 8k context. Weights are 140 gigabytes and fixed; the cache is what scales with users."

Then the four techniques as one system: "GQA shrinks the cache by the grouping factor, so 8x more concurrent sequences. PagedAttention removes the fragmentation that was wasting most of the rest, and gives you prefix sharing for free. Continuous batching keeps the GPU full by admitting requests at every decode step rather than per batch. And chunked prefill stops one long prompt from stalling everyone's decode."

The depth signal is preemption: "because output length isn't known at admission, the scheduler can over-commit and has to evict, which shows up as a latency outlier rather than an error." Very few candidates know a serving stack preempts.

The Staff & Team Lead Interview Reference