AI/ML systems / inference serving deep dive

LLM prefix caching: why reusing a prompt is a block allocator problem

A long system prompt, document, or chat history is repeatedly fed through the same Transformer layers. Prefix caching avoids doing that work again—but the useful implementation is not “put a tensor in a dictionary.” It is a content-addressed memory allocator coupled to a scheduler, an attention kernel, an eviction policy, and a tenant-isolation boundary.

AI/ML systems deep dive · KV-cache mechanics, vLLM block hashing, RadixAttention, allocation and eviction, cache correctness, security, observability, and a CPU-only lab

2026-09-19

The concrete problem

An autoregressive Transformer generates one token at a time. For every new token, each attention layer needs the keys and values of the preceding context. The server therefore stores those tensors in a key-value cache (KV cache). Without a cache, the model repeatedly recomputes the same attention state; with a cache, the next decode step reads the previous state and computes only the new token's contribution.^[4]

Now consider an API serving thousands of requests that all begin with the same 4,000-token policy document and differ only in the final question. The expensive prefill phase—the pass that turns prompt tokens into KV tensors—is repeated for every request. The model weights are unchanged, the prefix tokens are unchanged, and yet the GPU performs the same work again. The result is higher time-to-first-token, lower throughput, and unnecessary GPU-memory traffic.

This is deceptively hard because a request's cache is not one contiguous object. It grows during decoding, requests finish at different times, GPU memory is fragmented, and a cache hit must be inserted into the scheduler's block table without violating the attention kernel's layout. The implementation question is therefore: how do we make reusable GPU pages look like an ordinary cache while active sequences keep appending tokens?

First principles: prefill, decode, and KV blocks

For a token at position i, self-attention computes a query qᵢ, key kᵢ, and value vᵢ. Later positions compare their queries with earlier keys and take weighted sums of earlier values. The keys and values do not change after their position has been processed, so they are exactly the reusable state that the cache stores.

LLM serving has two different shapes:

Instead of reserving one contiguous KV tensor per request, PagedAttention divides the cache into fixed-size blocks. A logical sequence owns a list of block IDs, but the physical blocks may live anywhere in the GPU pool. This avoids the fragmentation and over-allocation problems of contiguous reservation, and it makes block-level sharing possible.^[2]

vLLM's key: hash the chain, not just the block

Suppose the block size is four tokens. Hashing only the current block would be unsafe: the token sequence [E,F,G,H] has different meaning after prefixes [A,B,C,D] and [X,Y,Z,W]. vLLM makes each block identity depend on both the parent block hash and the current block's token IDs:

block_hash = H(parent_hash, block_token_ids, extra_hashes)

The first block has an empty parent. The next block chains to the first block's hash, so a mismatch anywhere in the prefix changes every descendant key. Extra hashes carry facts that alter the resulting KV state, such as a LoRA adapter, multimodal input identity, or an explicit cache salt. vLLM documents this as a hash-based alternative to maintaining a prefix tree.^[1]

Only complete blocks enter the reusable cache. A partial tail cannot safely match a future request unless the implementation defines an exact partial-block protocol; vLLM deliberately keeps the simple invariant that the cache contains complete blocks. This means a prompt with 10 tokens and block size 4 can reuse 8 tokens, not the final 2.

The important state and control flow

The vLLM v1 design describes four cooperating structures:

A simplified KVCacheBlock carries an immutable ID, a hash once full, a reference count, and links for the free queue. The design puts the queue pointers on the block itself so moving a block from the middle of the queue is constant time without allocating wrapper objects.^[1]

For a new request, the scheduler asks the KV-cache manager for computed blocks. The manager walks the tokenized prompt block by block, computes the chained keys, and stops at the first miss. It then “touches” every hit—incrementing its reference count and removing it from the free queue—before allocating new blocks. This ordering matters: if allocation evicts first, the request can evict the very prefix it just discovered.

On free, blocks with reference count zero return to the queue. The vLLM design adds them in reverse request order: deeper blocks contain longer prefixes and are less likely to be reused, so they should become eviction candidates before shallow shared prefixes. When the queue head is a cached block, eviction removes its hash mapping and clears its hash before the physical slot is reused.^[1]

Hash table versus radix tree

There are two influential ways to represent the same prefix-sharing idea. vLLM's hash-chain approach makes each block independently addressable and keeps the physical allocator close to an ordinary cache. Its RFC explicitly models the mapping as logical block table → hash table → physical block table, with reference count, recency, access count, and prefix length available to the eviction policy.^[5]

SGLang's RadixAttention keeps token sequences in a radix tree. Common prefixes become shared tree edges, and the runtime can perform longest-prefix matching, insert continuations, and recursively evict least-recently-used leaves. The tree is attractive when requests naturally branch—multi-turn chat, few-shot batches, self-consistency, or tree-of-thought—because the structure exposes the common prefix directly.^[3]

Neither structure removes the kernel problem. The attention implementation still needs a block table or equivalent indirection to gather keys and values from non-contiguous physical storage. The data structure decides which blocks can be reused; the scheduler and kernel decide how they are safely consumed.

Correctness traps

Token equality is stricter than string equality

Cache keys must be built after the production tokenizer and chat template have run. Different whitespace, special-token insertion, Unicode normalization, tool markers, or model revisions can change token IDs. Two strings that look identical in a log can produce different tensors; two differently serialized inputs can occasionally produce the same tokens. Instrument token IDs, not just prompt text.

Model state belongs in the key

A block computed under one model revision, adapter, quantization layout, rotary-embedding configuration, or multimodal input cannot be silently reused by another. The model identity may be carried outside the per-block hash in a cache namespace, or included as an extra hash. The security rule is the same: every input that changes KV values must change the cache identity.

Shared blocks must be immutable

Once a block is shared by two active requests, an append operation must allocate a new block rather than modifying the shared one. Reference counts are not merely an eviction hint; they protect the copy-on-write boundary. A refcount race can turn one user's continuation into another user's context.

Duplicate blocks are acceptable, stale mappings are not

With an append-only block table, a request may finish a block that is already present elsewhere. Some implementations temporarily retain the duplicate until the request is freed rather than rewriting the table in place. That wastes capacity, but it preserves a simpler scheduler invariant. The dangerous alternative is reusing a physical slot while an old hash map still points at it.

Security and multi-tenant isolation

A prefix cache is a cross-request memory-sharing mechanism. If tenants share a cache namespace, an attacker may infer whether another tenant recently used a known prefix by measuring latency: a cache hit skips prefill and is faster. The attacker does not need to read KV tensors to learn that a secret document or system prompt was probably present.

vLLM supports a per-request cache_salt that is injected into the first block's identity. Requests with different salts cannot share the prefix, allowing reuse within an explicitly trusted group while preventing accidental cross-tenant reuse.^[1] A production deployment should also consider:

• Separate cache namespaces for customers, authorization scopes, or data classifications.
• Never using raw prompt text as a metric label or cache key exposed to operators.
• Constant-time-ish policy where high-sensitivity tenants disable reuse rather than relying only on timing noise.
• Evicting and zeroing physical memory according to the accelerator and threat model; logical eviction alone does not prove the bytes are gone.
• Using a collision-resistant, deterministic serialization when cache keys cross process or language boundaries. vLLM documents SHA-256 as its default in current stable documentation and warns that non-cryptographic hashing changes the collision and privacy risk profile.

Production tradeoffs and failure modes

Measure more than aggregate hit rate. The useful metrics are reusable tokens per request, first-miss position, prefill milliseconds saved, cache lookup latency, free-block watermarks, eviction churn, duplicate-block bytes, and hit/miss latency by isolation domain. A 90% block hit rate can still be disappointing if the hit blocks are short and the remaining suffix is the expensive part.

Compact reproducible lab: build the hash-chain cache

This lab does not require a GPU or model download. It reproduces the identity and lookup rules that make prefix caching safe. The expected result is that two requests share the first two complete blocks, while a one-token difference invalidates the second block and every descendant.

Prerequisites: Python 3.9 or newer. Create a file named prefix_cache_lab.py:

from hashlib import sha256

BLOCK = 4

def key(parent, tokens, salt="tenant-a"):
    payload = f"{parent}|{salt}|{','.join(map(str, tokens))}".encode()
    return sha256(payload).hexdigest()[:16]

def chain(tokens, salt="tenant-a"):
    parent = "ROOT"
    out = []
    for pos in range(0, len(tokens) - BLOCK + 1, BLOCK):
        block = tuple(tokens[pos:pos + BLOCK])
        parent = key(parent, block, salt)
        out.append((parent, block))
    return out

def reusable(a, b, salt_a="tenant-a", salt_b=None):
    if salt_b is None:
        salt_b = salt_a
    left, right = chain(a, salt_a), chain(b, salt_b)
    n = 0
    for x, y in zip(left, right):
        if x[0] != y[0]:
            break
        n += 1
    return n, n * BLOCK

base = list(range(1, 13))
same_prefix = list(range(1, 9)) + [90, 91, 92, 93]
changed_one = [1, 2, 3, 4, 5, 6, 99, 8, 90, 91, 92, 93]

print("same prefix:", reusable(base, same_prefix))
print("one token changed:", reusable(base, changed_one))
print("different salt:", reusable(base, same_prefix, "tenant-a", "tenant-b"))

Run it:

python3 prefix_cache_lab.py

Expected output:

same prefix: (2, 8)
one token changed: (1, 4)
different salt: (0, 0)

The second line is the revealing result: changing token 7 changes the hash for block two, so block three cannot be reused even though its own four token IDs are unchanged. That is the hash-chain equivalent of longest-prefix matching. The third line demonstrates isolation: identical tokens do not imply a shared cache when the namespace differs.

Variation 1: change BLOCK = 4 to BLOCK = 2. The same prefix should report four reusable blocks and eight tokens; the changed token should invalidate from its smaller block onward. Smaller blocks improve reuse granularity but increase metadata and lookup work.

Variation 2: remove salt from payload. The final line becomes a hit. That is functionally faster and operationally unsafe if the two salts represent different trust domains.

This CPU lab intentionally does not model GPU tensor layout, refcounts, or LRU eviction. A full integration test should add concurrent requests, forced eviction, a shared-block append, tokenizer changes, and cache-disabled output comparison.

How to debug a real serving incident

1. Reproduce with cache disabled. If outputs differ, suspect correctness before performance.
2. Capture token IDs at the cache boundary. Compare the exact common prefix, not rendered strings.
3. Log key components, not secrets. Record model namespace, block index, parent-key digest, token count, hit/miss, refcount, and physical block ID; never log raw tenant prompts.
4. Check the first miss. A hit followed by an unexpected miss usually identifies the serialization, special-token, adapter, or multimodal boundary that changed.
5. Stress eviction. Use a tiny cache pool and interleave long and short requests. Assert that no active block is evicted and that every hash map entry points to a block with the same stored hash.
6. Compare timing by namespace. A large hit/miss gap in a shared tenant pool is both a performance fact and a possible side channel.

The durable mental model

Prefix caching is not a prompt cache in the usual HTTP sense. It is a virtual-memory system for intermediate neural-network state. PagedAttention supplies pages and indirection; a hash chain or radix tree supplies identity and sharing; the scheduler supplies lifetime and copy-on-write rules; the eviction policy turns scarce GPU memory into a cache; and tenant salting defines who is allowed to observe reuse.

Once that model is clear, the design decisions stop looking arbitrary. Full blocks simplify identity. Parent hashes prevent context confusion. Reference counts protect active readers. Touch-before-allocate prevents self-eviction. LRU removes cold leaves first. Salts turn a global timing oracle into an explicitly scoped optimization. The speedup is real, but the engineering work is memory management wearing an AI-shaped costume.

Sources

1. vLLM — Automatic Prefix Caching: hash-chain identity, block pool, allocation, reference counts, LRU eviction, multimodal inputs, and cache salts.
2. Kwon et al., “Efficient Memory Management for Large Language Model Serving with PagedAttention”: the original paged KV-cache design and vLLM system.
3. LMSYS — Fast and Expressive LLM Inference with RadixAttention and SGLang: radix-tree reuse, branching workloads, and cache-aware scheduling.
4. Hugging Face Transformers — Cache strategies: KV-cache fundamentals and explicit prefix-cache prefill.
5. vLLM RFC #2614 — Automatic Prefix Caching: the implementation rationale and eviction-policy design notes.