Prefill vs decode, KV cache, prefix caching and batching
A GPT-like model generates text autoregressively: it reads the prompt, predicts the next token, appends it to the input, and repeats. Inference therefore has two phases that behave very differently: prefill and decode.
Prefill processes all the prompt tokens in a single forward pass. The tokens are processed in parallel, so the GPU performs large matrix-matrix multiplications and is compute-bound. Prefill ends with the first generated token, so its duration is the time to first token (TTFT).
Decode generates the remaining tokens, one forward pass per token. In the attention layer, the query of a new token attends to the keys and values of all previous tokens, which never change. Therefore, the \(K\) and \(V\) values of previous prefill/decode steps can be stored in a KV cache, and read again at every decode step. The KV cache grows by one token per step. Each pass processes a single new token per sequence, so the GPU performs matrix-vector multiplications (\(Q\) is a vector, \(K\)/\(V\) are matrices), and it reads every weight of the model from HBM to do very little arithmetic with it. Thus, decode is memory-bandwidth-bound, and the duration of each step is the time per output token (TPOT), also called inter-token latency (ITL).
Putting it together, the total runtime, or time to last token (TTLT), of an inference pass is \(\text{TTLT} = \text{TTFT} + \text{TPOT} \times ( n - 1)\), where \(n\) is the number of output tokens.
The following picture illustrates both phases for a prompt of four tokens and four output tokens, with the keys and values that each step writes to the KV cache and reads from it:
The memory bandwidth bottleneck of decode motivates most of this post: almost every decode optimization reads fewer bytes per token, does more useful work per byte read, or removes the overheads around the math.
KV cache
The KV cache divides the cost of generating \(n\) tokens by \(n\). Without a cache, each decode step recomputes the keys and values of the whole sequence. With a cache, each step only computes the query, key and value of the new token, appends the new key and value to the cache, and attends over all the cached ones. Queries are not cached, as the query of a past token was only needed to compute the output at its own position. The following picture illustrates the attention of the \(H\) heads in a decode step, without and with the KV cache:
Without KV cache: generating \(n\) tokens costs \(O(n^2)\) in the projections and the MLP, and \(O(n^3)\) in attention. With KV cache: generating \(n\) tokens costs \(O(n)\) in the projections and the MLP, and \(O(n^2)\) in attention. Here, \(H\) is the number of heads, \(h\) the head size, and \(P = S - 1\) the number of cached tokens.
For every token, every layer stores a key and a value vector per key-value head, so the size of the KV cache is given by:
\[\text{KV cache size} = 2 \times n_\text{layers} \times n_\text{kv heads} \times h \times \text{bytes per value} \times \text{sequence length} \times \text{batch size}\]where the factor 2 counts the key and the value, and \(h\) is the size of each head. Each sequence keeps its own KV cache, so for long contexts and large batches, reading the KV cache dominates the memory traffic and the runtime of each decode step, and its memory, not compute, often limits how many sequences can be batched together.
The following code implements the KV cache in a multi-head attention layer, and runs the prefill of the first tokens and then the decode of the next ones, one per step:
class MHA(nn.Module):
""" Multi-Head Attention with a KV cache """
def __init__(self, input_dim, head_dim, num_heads):
super().__init__()
self.head_dim, self.num_heads = head_dim, num_heads
self.wq = nn.Linear(input_dim, head_dim * num_heads)
self.wk = nn.Linear(input_dim, head_dim * num_heads)
self.wv = nn.Linear(input_dim, head_dim * num_heads)
self.out = nn.Linear(head_dim * num_heads, input_dim)
def forward(self, x, kv_cache=None):
B, S, _ = x.shape # S: any length on prefill, 1 on decode
H, h = self.num_heads, self.head_dim
# queries, keys and values of the new tokens: [B, S, E] -> [B, H, S, h]
q = self.wq(x).view(B, S, H, h).transpose(1, 2)
k = self.wk(x).view(B, S, H, h).transpose(1, 2)
v = self.wv(x).view(B, S, H, h).transpose(1, 2)
# KV cache: append the new keys and values to the P cached ones: [B, H, P+S, h]
P = 0
if kv_cache is not None:
P = kv_cache[0].size(2)
k = torch.cat([kv_cache[0], k], dim=2)
v = torch.cat([kv_cache[1], v], dim=2)
# last S rows of the causal mask, over the P cached tokens and the S new ones: [S, P+S]
mask = torch.ones(S, P + S, dtype=torch.bool, device=x.device).tril(diagonal=P)
scores = (q @ k.transpose(-1, -2) / h ** 0.5).masked_fill(~mask, float('-inf'))
attn = F.softmax(scores, dim=-1) @ v # [B, H, S, P+S] @ [B, H, P+S, h]
attn = attn.transpose(1, 2).reshape(B, S, H * h) # [B, H, S, h] -> [B, S, H*h]
return self.out(attn), (k, v) # [B, S, H*h] -> [B, S, E]
mha = MHA(input_dim=32, head_dim=16, num_heads=8)
x = torch.randn(8, 16, 32) # [B, S, E]
y, kv_cache = mha(x[:, :4]) # prefill: the first 4 tokens at once
for t in range(4, x.size(1)): # decode: the next tokens, one per step
y, kv_cache = mha(x[:, t:t + 1], kv_cache) # the KV cache grows by one token per step
PagedAttention and static shapes
One of the main issues with the KV cache is that it requires dynamic storage, where every step concatenates the new keys and values into a tensor. When that tensor is full, all its data is copied into a new, larger tensor. Serving many requests at once makes memory management hard, because the final length of each sequence is unknown. To overcome that, PagedAttention borrows the idea of virtual memory from operating systems. The KV cache is a preallocated pool of fixed-size blocks (pages), which are assigned to the sequences on demand, and a block table maps the logical blocks of each sequence to physical blocks anywhere in the pool. Almost no memory is wasted, so more sequences fit in a batch: the authors reported 2-4 times higher throughput than previous systems.
An illustration of the block tables of two sequences, with blocks of 4 tokens, is displayed below:
Also, the preallocated pool gives the KV cache a static shape, and static shapes are important on GPUs because they maximize the execution speed: they remove runtime overheads and allow compilers to optimize the memory and compute kernels. With static shapes, memory is allocated in advance, without fragmentation, and each kernel keeps a fixed signature, i.e. one function definition for a given size, without the overhead of managing dynamic shapes. Static shapes also allow loop unrolling and CUDA graphs, which speed up small models by removing the overhead of launching their many small kernels, and they avoid recompilations in just-in-time compilers, such as that of PyTorch.
Finally, blocks of a fixed size also serve other inference methods, presented below: prefix caching, chunked prefill and the sharing of prefixes across requests.
Prefix caching, prompt caching or context caching
Many requests start with the same tokens: a system prompt, tool definitions, a long document that users ask several questions about, or the history of a conversation. Prefix caching keeps the keys and values of these tokens after a request finishes, so that the next request starting with the same tokens skips their prefill and only processes its new part. The first token arrives much sooner, and the GPU is free for other work.
How the lookup works. The KV cache is split into fixed-size blocks (e.g., 16 tokens, as in vLLM), and each block is identified by a hash of its tokens combined with the hash of the previous block. The chain of hashes identifies the whole prefix, so a lookup walks the blocks from the start of the prompt and stops at the first miss.
The following picture illustrates the lookup for three requests whose prompts start with the same tokens:
Automatic prefix caching, with blocks of 4 tokens. The hash of each block chains the hash of the previous block with the tokens of the block. Request 2 reuses the first two blocks of request 1 and prefills 4 tokens. Request 3 reuses only the first block: its last block holds the same tokens as that of request 1, but its hash differs because its second block differs, so request 3 prefills 8 tokens.
Automatic Prefix Caching requires little extra memory: it reuses the physical blocks of PagedAttention through pointers, and only adds a hash table that maps the block hashes to physical blocks.
SGLang’s RadixAttention stores all cached sequences in a radix tree (a compressed prefix tree), finds the longest prefix shared with each new request, and evicts the least recently used leaves when memory runs out. Unlike the hash chain, which reuses only full blocks, the radix tree reuses a shared prefix of any length.
Why the prefix must match exactly. The key and value of token \(i\) depend on all the tokens before it, through every layer of the model. So two prompts that differ in a single early token, even if they mean the same thing, have different keys and values for every token after it, and only a prefix of the same token IDs can be reused. This makes prefix caching lossless: the output is identical to running the model without the cache. Similar prompts can only share whole answers, one level up: that is semantic caching, described below.
What is kept. When a request finishes, its blocks stay in memory until the memory is needed, and the least recently used ones are evicted first. Generated tokens are cached too, which makes multi-turn chat fast: the prompt of the next turn is the previous prompt, plus the previous answer, plus the new message. Thus, the static content goes first in the prompt (system prompt, tools, documents), and the variable content last (the user’s question, timestamps), as anything that changes early in the prompt invalidates the cache for everything after it.
The following code implements the lookup of the cached blocks, and prefix caching on top of the KV cache, which computes the keys and values of a shared prefix once for all the requests, with the same outputs as without prefix caching:
def block_hashes(tokens, block_size=16):
""" Hashes of the full blocks of a list of token ids: each hash combines the tokens of its block with the hash of
the previous block, so it identifies the whole prefix up to the end of its block """
hashes, previous = [], None
for start in range(0, len(tokens) - block_size + 1, block_size):
previous = hash((previous, tuple(tokens[start:start + block_size])))
hashes.append(previous)
return hashes
def cached_prefix_length(tokens, cached_blocks, block_size=16):
""" Number of leading tokens whose KV cache is cached: the lookup walks the blocks from the start of the prompt,
and stops at the first miss. cached_blocks: the hashes of the cached blocks, e.g. a dict from hash to block """
n = 0
for block_hash in block_hashes(tokens, block_size):
if block_hash not in cached_blocks:
break
n += block_size
return n
def prefill_with_prefix_cache(model, prefix, requests):
""" Prefill of each request, [1, S], on top of the KV cache of the prefix, [1, P] """
_, prefix_cache = model(prefix) # computed once; torch.cat never modifies it
return [model(request, prefix_cache) for request in requests]
Semantic caching
A semantic cache sits in front of the model, in the application, and skips the model altogether for a query similar to one that it answered before. For every incoming query, it:
- computes an embedding, a vector that represents the meaning of the query;
- searches a vector index for the most similar past query;
- if the similarity is above a threshold, returns the stored answer without calling the model;
- otherwise, calls the model and stores the new (embedding, answer) pair.
The diagram below illustrates these four steps:
A semantic cache. The vector index finds the past query whose embedding is closest to that of the new query. If their similarity reaches the threshold, as it may for a paraphrase such as “What is the price of corn in Rome?”, the cache returns the stored answer of that query. Otherwise, the LLM answers, and the embedding and the answer are stored.
How embeddings are created. Embeddings come from a separate and much smaller embedding model, typically a transformer encoder trained with the InfoNCE loss so that texts with close meanings have embeddings that point in similar directions. The cosine similarity of two embeddings then measures how close their meanings are.
Risks. Unlike prefix caching, a semantic cache is approximate, so it can return a wrong answer: “how do I delete a file in Python?” and “how do I delete a folder in Python?” are very similar sentences with different answers. Answers also go stale, and the answers of queries that depend on the user or on the conversation should not be shared. In practice, the threshold is tuned on real traffic, the cache is scoped per user, and its entries expire.
The strict version of a semantic cache is the exact-match cache, which maps a hash of the full request (prompt, model and sampling parameters) to the response. It never returns a wrong answer, but only hits identical requests.
Batching improvements
Batching runs several sequences in the same forward pass, and is the most effective way to increase throughput. Because decode is memory-bound, a decode step for a batch of sequences takes almost the same time as for a single sequence: the weights are read once and used by every sequence. Throughput grows almost linearly with the batch size, until the GPU becomes compute-bound, at hundreds of sequences per step, or, more often, runs out of memory for the KV caches. The difficulty is that requests arrive at different times, with prompts of different lengths, and generate different numbers of tokens.
Static and continuous batching
The simplest way to batch requests, static batching, groups \(B\) requests and runs them together until all of them finish. Prompts of different lengths are padded on the right to the same length: with causal attention, real tokens never attend to the padding that follows them, so no padding mask is needed, and each sequence reads its next-token prediction at its own last position. Static batching wastes compute and memory on the padding and on the sequences that finish early, which keep their slot and generate tokens that are thrown away. New requests also wait until the whole batch is done.
Continuous batching, introduced by Orca as iteration-level scheduling, makes the scheduling decision at every decode step instead of once per batch: as soon as a sequence finishes, it leaves the batch, and a waiting request takes its slot. The GPU stays busy, and new requests do not wait for the longest sequence of the previous batch. The implementation keeps the tokens of each running request apart and rebuilds the padded batch at every step, so that a new request never sees the tokens of the previous occupant of its slot.
Chunked prefill
When a new request arrives while others are decoding, its prefill runs before, or in the same step as, their next decode. The prefill of a long prompt can take many times longer than a decode step, and all the other requests wait for it: their text pauses, and their time per output token spikes.
Chunked prefill, introduced by SARATHI, solves this by processing a long prompt in several smaller pieces (chunks), one per step, instead of in one forward pass. Each step processes the decode tokens of the batch and fills the rest of a budget of tokens with prompt tokens, so every step takes about the same time, and the other requests keep generating one token per step. A smaller budget lowers their time per output token, and a larger one the time to first token of the new request.
Each chunk attends to the KV cache of the earlier chunks. Because attention is causal, tokens only attend to earlier tokens, so attention is final after each chunk, and the result is identical to processing the whole prompt at once. With a non-causal mask, the earlier tokens would also attend to the later ones, so every new chunk would change the keys and values of the previous chunks, in every layer after the first. For that reason, chunked prefill is rarely used for non-causal models.
In practice, chunks of a fixed size, a multiple of the block size, also serve PagedAttention and prefix caching: the keys and values of each chunk fill whole blocks, which the prefix cache can hash and reuse as soon as the chunk is prefilled.
The following picture compares static batching, continuous batching, and continuous batching with chunked prefill:
The same 7 requests (R1 to R7) on 4 slots, with static batching, continuous batching, and continuous batching with chunked prefill. P1 to P7 and D1 to D7 are the prefill and the decode of R1 to R7. Each decoded token takes one step, one cell of its decode, and a prefill takes one to three steps, depending on the length of its prompt. Static batching runs the requests in groups of 4 until the longest request of each group finishes, and pads the prompts of a group to the longest one. Continuous batching gives a free slot to the next request at the next step, but the requests that run in the same forward pass as a prefill of two or three steps are padded to its length, and stall until it ends. With chunked prefill, each prompt is processed in chunks of one step, while the other requests continue.
The following code implements static batching, continuous batching and chunked prefill. Static and continuous batching produce the same outputs, but continuous batching needs fewer steps, since its slots spend more time generating useful tokens. To keep the code short, they process the whole sequences at every step, without a KV cache:
def next_tokens(model, sequences, seqlen):
""" Greedy next token of each sequence, a list of 1D tensors of different lengths, in a batch padded on the
right, where each sequence reads its prediction at its own last position """
windows = [seq[-seqlen:] for seq in sequences] # the last seqlen tokens of each sequence
lengths = torch.tensor([len(w) for w in windows], device=windows[0].device)
batch = nn.utils.rnn.pad_sequence(windows, batch_first=True) # [B, S], padded with token 0
logits, _ = model(batch) # [B, S, V]
return logits[torch.arange(len(windows), device=logits.device), lengths - 1].argmax(dim=-1) # [B]
def static_batching(model, requests, batch_size, seqlen):
""" Runs the requests, pairs (prompt, number of tokens to generate), in groups of batch_size, until the longest
request of each group finishes """
outputs, n_steps = [], 0
for start in range(0, len(requests), batch_size):
group = requests[start:start + batch_size]
sequences = [prompt for prompt, _ in group]
for _ in range(max(n_tokens for _, n_tokens in group)):
tokens = next_tokens(model, sequences, seqlen)
sequences = [torch.cat([seq, token[None]]) for seq, token in zip(sequences, tokens)]
n_steps += 1
# the requests that finished early generated extra tokens, which are thrown away
outputs += [seq[:len(prompt) + n_tokens] for seq, (prompt, n_tokens) in zip(sequences, group)]
return outputs, n_steps
def continuous_batching(model, requests, batch_size, seqlen):
""" Keeps batch_size slots busy: as soon as a request finishes, the next waiting request takes its slot """
outputs, n_steps = [None] * len(requests), 0
waiting = list(range(len(requests))) # ids of the requests waiting for a slot
running = [] # (request id, tokens so far) of the requests in the batch
while waiting or running:
while waiting and len(running) < batch_size: # fill the free slots
request_id = waiting.pop(0)
running.append((request_id, requests[request_id][0]))
tokens = next_tokens(model, [seq for _, seq in running], seqlen)
running = [(request_id, torch.cat([seq, token[None]])) for (request_id, seq), token in zip(running, tokens)]
n_steps += 1
still_running = []
for request_id, seq in running: # the finished requests leave the batch
prompt, n_tokens = requests[request_id]
if len(seq) == len(prompt) + n_tokens:
outputs[request_id] = seq
else:
still_running.append((request_id, seq))
running = still_running
return outputs, n_steps
def chunked_prefill(model, prompt, chunk_size, kv_cache=None):
""" Prefill of a prompt: [1, S], in chunks of chunk_size tokens, each on the KV cache of the earlier ones.
Returns the logits of the last token: [1, V], and the KV cache """
for start in range(0, prompt.size(1), chunk_size):
logits, kv_cache = model(prompt[:, start:start + chunk_size], kv_cache)
return logits[:, -1], kv_cache
Sharing prefixes across requests
Several requests that run at the same time often share a prefix, e.g., the same system prompt or the same document. Chunked prefill can then prefill it once for all of them: the prompts form a prefix tree of chunks, a tree of chunked prefills, as the KV cache of ChunkAttention. The chunks of each level can run in the same step, each on the KV cache of the chunks above it: a shared chunk is prefilled once, and each request forks into its own branch at its first different chunk.
Each chunk also keeps a pointer to its parent, and a hash map stores a pointer to each chunk under the hash of the prefix that it ends, i.e., the chained hash of prefix caching. A lookup hashes the prefixes of a new prompt, chunk by chunk, finds the longest one in the hash map, and follows the parent pointers up to the root to load the KV cache of the full prefix. The following picture illustrates a lookup in the tree of the prefix caching example:
The tree holds the chunks of the three requests of the prefix caching example, each labeled with the hash of its prefix. Request 4 starts with the prompt of request 1: its full prompt misses (\(h_7\)), but its first three chunks hit (\(h_4\)). The pointer of \(h_4\) leads to its chunk, and the arrows up to the root give the rest of the recovered prefix. Only the last chunk is prefilled, and it joins the tree as a child of the chunk of \(h_4\).
As with the blocks of prefix caching, only full chunks are shared: the tokens that two requests share before they differ in the middle of a chunk are prefilled once per request.
Ragged/packed batching
With continuous batching and chunked prefill, a step runs the prefill chunks of some requests and the decode of others. Padding these sequences of different lengths into a rectangular batch would waste compute, so they are concatenated instead, and each step is one forward pass over a flat list of tokens from all running sequences: this is ragged/packed batching. The MLP and the projections do not care which sequence a token belongs to, so they run as one large matrix multiplication over all the tokens of the step.
Attention is the only per-sequence operation. Variable-length kernels (FlashAttention’s varlen mode, PagedAttention) use per-token metadata (sequence id, position, KV block table), so that each token attends only to its own sequence: this is a block-diagonal causal mask, whose blocks outside the diagonal the kernels skip. The output layer then computes only the logits of the last token of each sequence, which predict its next token.
The following picture illustrates three sequences in a padded batch and in a ragged batch, with the block-diagonal causal mask of the ragged batch:
The following code packs sequences of different lengths into one flat sequence, with the position of every token, the block-diagonal causal mask, and the indices of the last tokens:
def pack(sequences):
""" Packs a list of 1D tensors into one flat sequence: [1, S]. Returns its tokens, their positions: [S], the
block-diagonal causal mask: [S, S], and the index of the last token of each sequence: [B] """
device = sequences[0].device
lengths = torch.tensor([len(seq) for seq in sequences], device=device)
seq_ids = torch.repeat_interleave(torch.arange(len(sequences), device=device), lengths) # [S]: sequence ids
positions = torch.cat([torch.arange(n, device=device) for n in lengths.tolist()]) # [S]
s = torch.arange(len(seq_ids), device=device)
mask = (seq_ids[:, None] == seq_ids[None, :]) & (s[:, None] >= s[None, :]) # [S, S]
return torch.cat(sequences)[None], positions, mask, lengths.cumsum(0) - 1
# usage: one forward pass for all the sequences, with a model that takes the mask and the positions
# tokens, positions, mask, last = pack(sequences)
# logits = model(tokens, mask=mask, positions=positions) # [1, S, V]
# next_tokens = logits[0, last].argmax(dim=-1) # [B]: the next token of every sequence