Prefix Caching in Depth: What the GPU Skips, What It Still Pays For, and How Cached KV Blocks Live and Die in HBM

What prefill costs, and what a hit removes

Prefill is the compute-bound phase of inference. For a dense decoder with P parameters, pushing N prompt tokens through the linear layers costs about 2 × P × N floating-point operations: every weight is multiplied once per token. Attention adds a term that grows with the square of the context. For each layer, computing scores (Q times K transposed) and mixing values (scores times V) costs about 2 × N² × H operations for a full causal prefill, where H is the total query width (number of query heads times head dimension). Processed together, these are large matrix multiplications that run near tensor-core throughput.

A prefix hit of length C on a prompt of length N removes the linear work for C tokens and the attention work those C tokens would have done among themselves. It does not remove the attention the remaining N − C suffix tokens do against the cached keys: each suffix query still reads all C cached keys and values. That suffix attention costs about 4 × (N − C) × N × H per layer, which is small when the suffix is short, but it is never zero. Decode is untouched: once the first token is produced, every later token reads the whole KV cache regardless of where it came from.

So prefix caching converts prefill compute into a lookup plus a short prefill of the suffix. It shortens time to first token and frees tensor cores for other requests; it does nothing for time per output token, and it costs HBM for as long as blocks are retained.

From tokens to blocks: the full-block rule

Engines with a paged KV cache store keys and values in fixed-size blocks; in vLLM a block commonly holds 16 tokens, and a per-request block table maps logical positions to physical blocks, as described in paged KV cache architecture. Prefix caching gives each full block an identity: a hash of the parent block's hash, the block's token ids, and extra keys that change the KV contents, such as a LoRA adapter id, multimodal input hashes, or a per-tenant cache salt. Because each hash folds in its parent, two equal hashes mean two equal prefixes from position zero, not just two equal 16-token windows.

vLLM's design documentation states that only full blocks are cached. Two consequences follow. First, the reusable length is always rounded down to a multiple of the block size: a 1,000-token shared system prompt with 16-token blocks yields 62 full blocks (992 tokens), and the last 8 tokens are recomputed on every request unless the following tokens are also shared. Second, a difference in the very first block invalidates everything, since every later hash depends on it. A timestamp in the system prompt does not reduce reuse; it destroys it. The hash function is set with --prefix-caching-hash-algo (sha256 by default, with sha256_cbor, xxhash and xxhash_cbor as alternatives), trading collision resistance against CPU hashing cost.

Life cycle of a cached block

A physical block is in use (reference count at least one: some running request's block table points at it), free-but-cached (count zero, hash kept, contents valid and findable but reclaimable), or free-and-empty. A new request walks its block hashes in order; every hit increments the block's count and, if the block was sitting in the free queue, pulls it back out. At the first miss, the request allocates fresh blocks from the head of the free queue, and if that head block carries a hash, the hash is dropped from the lookup table: this is eviction.

The order of the free queue is therefore the eviction policy. vLLM uses least-recently-used eviction and, when a request finishes, appends its blocks in reverse order, tail first. A request's last block hashes the longest history and is least likely to be shared, so it goes first; the first blocks, holding the system prompt everyone uses, go last. Because only full, immutable blocks are shared, no request writes into a block another reads, so the prefix needs no copy-on-write. The toy pool below reproduces these rules.

from collections import OrderedDict
import hashlib

BLOCK = 16

class Block:
    def __init__(self, bid):
        self.bid, self.ref, self.hash = bid, 0, None

class BlockPool:
    """Toy paged KV pool with prefix reuse."""
    def __init__(self, n_blocks):
        self.blocks = [Block(i) for i in range(n_blocks)]
        self.free = OrderedDict((b.bid, b) for b in self.blocks)   # head = next victim
        self.by_hash = {}                                            # hash -> Block

    def _hashes(self, tokens, extra=b""):
        parent, out = hashlib.sha256(extra).digest(), []
        full = len(tokens) - len(tokens) % BLOCK
        for s in range(0, full, BLOCK):
            parent = hashlib.sha256(parent + repr(tokens[s:s + BLOCK]).encode()).digest()
            out.append(parent)
        return out

    def _take_free(self):
        _, b = self.free.popitem(last=False)          # head = least recently freed
        if b.hash is not None:
            del self.by_hash[b.hash]                   # eviction
            b.hash = None
        return b

    def allocate(self, tokens, extra=b""):
        hashes = self._hashes(tokens, extra)
        # Never reuse the whole prompt: the last position must run to produce logits.
        max_hit = (len(tokens) - 1) // BLOCK
        table, hit = [], 0
        for h in hashes[:max_hit]:
            b = self.by_hash.get(h)
            if b is None:
                break
            if b.ref == 0:
                self.free.pop(b.bid)                   # revive from free queue
            b.ref += 1
            table.append(b)
            hit += 1
        need = -(-len(tokens) // BLOCK) - hit          # ceil(tokens / BLOCK) - hits
        for i in range(need):
            b = self._take_free()
            b.ref = 1
            table.append(b)
        return table, hit * BLOCK, hashes              # computed tokens = len - hit*BLOCK

    def commit_full_blocks(self, table, hashes):
        """After prefill, publish full blocks for reuse."""
        for b, h in zip(table, hashes):
            if b.hash is None and h not in self.by_hash:
                b.hash, self.by_hash[h] = h, b

    def release(self, table):
        # Reverse order: the tail is evicted first.
        for b in reversed(table):
            b.ref -= 1
            if b.ref == 0:
                self.free[b.bid] = b

Try it: allocate a 1,000-token prompt, commit it, and allocate it again; the second call hits 992 tokens, finished or not. A prompt of exactly 992 tokens hits only 976, for the reason in the next section. Exhaust the pool with distinct prompts and the first victims are the tails of finished requests, not their shared heads.

Why the last token always runs

Even a prompt identical to one already cached cannot skip prefill completely. Prefill must also produce the logits for the next token, which come from the final hidden state of the last prompt position, and cached keys and values do not contain that state. At least one position must go through every layer. Engines therefore cap the reusable length below the full prompt length, and with block-granular caching the cap usually costs up to one block of recomputation when a prompt ends exactly on a boundary.

Retries, deterministic evaluation and best-of-n issued as separate requests therefore still pay a small prefill each time, which is also why a hit rate reported in tokens can never reach 100 percent even for perfectly repeated traffic.

Worked example: questions over one long document

Take an illustrative dense model with 14 billion parameters, 48 layers, 40 query heads and 8 key-value heads of dimension 128 (query width H = 5,120), serving bf16 KV on a GPU that sustains an assumed 400 TFLOP/s on large prefills. These numbers are for arithmetic only; measure your own. A user uploads a 12,000-token contract and asks 20 questions of about 100 tokens each, one after another.

KV size per token is 2 × 48 layers × 8 heads × 128 × 2 bytes = 196,608 bytes, 192 KiB. The contract occupies 750 blocks of 16 tokens and about 2.2 GiB of HBM.

Without caching, each question prefills about 12,100 tokens. Linear work is 2 × 14e9 × 12,100, about 3.4e14 operations; attention adds 2 × 12,100² × 5,120 × 48 layers, about 7.2e13. Roughly 4.1e14 operations is about one second of GPU time per question at the assumed throughput, so 20 questions spend about 20 seconds of prefill and every answer waits at least a second before its first token.

With caching, the first question pays that second. Each later question computes 100 tokens: linear work about 2.8e12, suffix attention about 4 × 100 × 12,100 × 5,120 × 48, roughly 1.2e12. About 4e12 operations is 10 ms of peak throughput, though a prefill this small will not reach peak and lands in the tens of milliseconds in practice. Time to first token drops by more than an order of magnitude, and about 19 seconds of GPU time is returned to the batch. The price is 2.2 GiB of HBM held while the conversation is active, and the risk that other traffic evicts those blocks during the user's think time, turning the next question back into a one-second miss.

In general the prefill saving on a hit is roughly (prefix + suffix) divided by suffix, bounded by suffix attention and fixed overheads. A single speedup factor for prefix caching means nothing without the prefix-to-suffix ratio and the hit rate.

How hits change the scheduler

Continuous-batching schedulers fill each iteration up to a token budget, with chunked prefill splitting long prompts to fit; vLLM's continuous batching and KV management explains the loop. A hit changes the admission arithmetic: a request whose 12,000-token prompt is 99 percent cached consumes about 100 tokens of the step budget instead of spanning many chunks. Hits therefore also smooth decode for everyone else in the batch.

Hits also change memory accounting. A request that hits 750 blocks needs only its tail allocated, so more sequences fit before the pool runs dry. Conversely, free-but-cached blocks count as free for admission; a scheduler that admits aggressively will evict cached prefixes to make room, and under pressure the cache silently becomes a small cache. The PagedAttention design makes both behaviours cheap, but memory still serves two masters.

Measuring it

vLLM exports two counters, vllm:prefix_cache_queries and vllm:prefix_cache_hits, both measured in tokens. Their ratio is the token hit rate, which is the number that predicts prefill savings. Break it down by model and, through your own logging, by prompt template, and chart it next to time to first token for hits and misses separately.

# Token hit rate over 5 minutes, per model (both counters count tokens, not requests)
sum by (model_name) (rate(vllm:prefix_cache_hits[5m]))
  /
sum by (model_name) (rate(vllm:prefix_cache_queries[5m]))

To measure the latency effect directly, replay real prompts with max_tokens set to 1, once with caching enabled and once disabled, each in a fresh engine process so neither run inherits the other's cache.

Trade-offs and failure modes

• Cache versus concurrency. Retained blocks come out of the same pool as running sequences. On a memory-bound deployment, a large cache footprint lowers the batch size you can sustain; watch KV utilisation and preemption counts, and cap concurrency with admission control rather than letting the scheduler evict the prefixes you depend on.
• Near-miss prompts. A per-request field placed before the shared content (date, user name, request id) zeroes the hit rate with no error. Put variable content after the shared prefix and alert on hit rate per template.
• Block-boundary waste. Short shared prefixes lose up to 15 tokens of reuse to rounding. For a 40-token system prompt that is a third of the prefix; for a 12,000-token document it is noise.
• Cross-tenant timing signals. A hit is measurably faster than a miss, so a tenant can probe whether someone else sent a given prefix. Use a per-tenant cache salt where the engine supports one, or disable sharing across trust boundaries.
• Replica scatter. Caches are per engine instance. Round-robin across eight replicas multiplies cold misses by up to eight for session-shaped workloads like the document example.

What to do next

1. Compute KV bytes per token for your model and the HBM a typical shared prefix occupies; decide how much of the pool you are willing to spend on retention.
2. Confirm prefix caching is enabled on your engine version and record which hash algorithm it uses.
3. Add the token hit-rate query to your dashboard and split time to first token by hit and miss.
4. Audit your top prompt templates for variable content in the first block, and move it after the shared prefix.
5. Run the max_tokens=1 A/B on real prompts to measure the actual prefill saving on your hardware.
6. If you run several replicas, route requests with a shared prefix or session to the same replica before tuning anything else.