7.7 Prefix Caching & KV-Cache Reuse¶

Every token the decoder emits costs one full forward pass through the model’s attention layers — but only for the new key and value vectors produced by that token. The key-value (KV) tensors for tokens the model has already processed are immutable: they are a deterministic function of the token IDs and model weights. That mathematical fact is the entire foundation of KV-cache reuse: if two requests share a common prefix, the KV tensors for those shared tokens need only be computed once, and every subsequent request that begins with the same prefix can skip straight to the first token that differs.

At small scale this is a pleasant micro-optimization. At production scale — where a system-prompt of 2,000 tokens is prepended to every conversation, or where a 64-shot RAG document forms the head of every retrieval request — prefix caching is a first-order economic lever. It can reduce time-to-first-token (TTFT) for subsequent requests by 80–95 % and cut total GPU compute proportionally.

This chapter develops prefix caching from first principles: the algebra of KV materialization, hash-based block identification, the two major implementations (SGLang’s RadixAttention and vLLM’s Automatic Prefix Caching), the cascade attention kernels that turn a shared prefix into shared bandwidth, eviction policy, cross-request sharing and tenant-isolation semantics, and the concrete deployment patterns where shared prefixes appear at scale. We close with a worked numerical cost model and practical configuration guidance — including how to get prefix reuse with nothing but transformers and a single GPU.

For the low-level anatomy of the KV cache itself and the paged memory allocator that makes per-request caching tractable, first read PagedAttention & KV-Cache Memory Management and The Anatomy of LLM Inference: Prefill, Decode & The KV Cache.

7.7.1 Why KV Tensors Are Reusable¶

During the prefill phase for a sequence of tokens \(x_1, x_2, \dots, x_T\), every transformer layer \(\ell\) computes

where \(x_t\) is the hidden state of token \(t\) at layer \(\ell\) and \(W_K^{(\ell)}, W_V^{(\ell)}\) are learned weight matrices. Because the model is autoregressive and deterministic, \(K^{(\ell)}_t\) and \(V^{(\ell)}_t\) depend only on the input tokens \(x_1, \dots, x_t\) and the (fixed) weights. More precisely, they depend on the exact byte sequence of the token IDs up to position \(t\), concatenated with any position encoding applied at that layer.

This gives us a strong guarantee: if two requests share the token-level prefix \(x_1, \dots, x_P\) byte-for-byte, they produce identical KV tensors for all positions \(1 \leq t \leq P\) in every layer. No stochastic element exists in key or value computation (unlike, say, the generation step which may involve temperature sampling). This means the KV tensors are a pure function of the prefix and can be safely cached and reused across any number of requests.

The same logic extends to the sequence of positions. Most modern models use relative or rotary (RoPE) positional encodings (see Positional Encodings: Sinusoidal, Learned, RoPE & ALiBi), which embed position information into the key and query vectors. Because both the token IDs and the positions are deterministic from the prefix, the KV cache is still reusable as long as the prefix always occupies positions \(1 \dots P\) — which is the common case for system prompts that sit at the start of a context.

7.7.2 Block-Level Identification: Content-Based Hashing¶

The challenge for a serving system is identifying, at request-dispatch time, which portions of the incoming context are already cached without comparing raw tensor data. The standard approach is content-based hashing of token-ID blocks.

The KV cache is managed in pages (also called blocks) of a fixed size, typically 16 or 32 tokens. Each page stores the K and V tensors for exactly those tokens at all transformer layers. To identify a page, the server computes a hash of its content — specifically, the token IDs contained in that page concatenated with the hash of the immediately preceding page:

where \(B\) is the block size and \(\|\) denotes concatenation. This chained hash construction ensures that two blocks with identical token IDs but different preceding context get different hashes — a block containing "the dog" at position 16 is semantically different from the same tokens at position 48 because the model’s hidden states (and thus the KV tensors) depend on all prior context.

The serving engine maintains a prefix hash table: a map from block hash to a reference-counted pointer to the physical GPU memory block holding the pre-computed KV tensors. On receiving a new request, the scheduler:

1. Tokenizes the prompt and segments it into blocks of size \(B\).
2. Walks the block chain (recomputing hashes incrementally from the front) and looks each hash up in the table.
3. Identifies the longest matching cached prefix — a contiguous run of cache hits from position 0.
4. Schedules prefill only for the uncached suffix.

The engine then runs prefill only for blocks 2 and 3 (32 tokens), using the cached KV blocks for blocks 0 and 1 as “prior context” passed into the attention kernel.

Hash collision risk¶

SHA-256 truncated to 64 bits provides ample collision resistance for any realistic serving workload. However, engines default to cheaper hashes for speed: vLLM V1 keys blocks with Python’s built-in hash() over a tuple of (prev_hash, token_ids, extra_keys), and exposes --prefix-caching-hash-algo so you can switch to SHA-256 (or a canonical CBOR-serialised SHA-256 variant) when you want a deterministic, cross-process-stable digest. A hash collision would cause a request to receive incorrect KV tensors, producing subtly wrong output. In practice, the probability of a collision in a fleet serving billions of requests is negligible, but safety-critical deployments may want to add a lightweight token-ID equality check on hash hits.

Note the extra_keys slot in that tuple. A block hash must cover everything that the KV tensors depend on, not just token IDs: a multimodal request’s image embeddings, the LoRA adapter ID a request is routed to (see Multi-Tenant LoRA & Adapter Serving at Scale), and any per-tenant cache salt all become part of the key. Forgetting one of these is the classic way to build a prefix cache that silently returns another request’s activations.

7.7.3 RadixAttention: SGLang’s Tree-Based Prefix Store¶

SGLang (Zheng et al., “Efficiently Programming Large Language Models using SGLang,” 2024) introduced RadixAttention, which reframes the prefix cache as a radix tree (trie) of token sequences. Rather than maintaining a flat hash table keyed on individual block hashes, RadixAttention organizes cached prefixes as a tree where:

• Each edge is labeled with a sequence of tokens.
• Each node stores the KV tensors corresponding to the edge’s token segment.
• Shared prefixes correspond to common root-to-node paths.

This representation has several advantages over a flat hash table:

Automatic longest-prefix matching. A single trie lookup finds the longest cached prefix in \(O(P)\) time, where \(P\) is the number of tokens in the prefix, rather than hashing individual blocks separately.

Prefix sharing across partial matches. Two requests sharing only the first 1,000 tokens of a 2,000-token context can still reuse the first 1,000 tokens without either having previously generated the full 2,000-token prefix. The trie naturally captures this partial overlap.

Multi-turn conversation chains. Each turn in a conversation appends to the previous turn’s path in the trie. If a user sends messages A, B, C in one session, the path root → A → A+B → A+B+C is built incrementally. A second session that shares message A automatically benefits from the first session’s computation.

from __future__ import annotations
import hashlib
from dataclasses import dataclass, field
from typing import Optional

@dataclass
class RadixNode:
    """
    A node in the RadixAttention trie.

    In a real implementation, kv_ptr would be a reference to a GPU
    memory block. Here we use a placeholder bytes object to represent
    the serialised KV tensors.
    """
    token_ids: list[int]      # edge label (tokens along this edge)
    kv_data: Optional[bytes]  # cached KV tensors (None if not yet materialized)
    children: dict[int, "RadixNode"] = field(default_factory=dict)
    ref_count: int = 0        # how many active requests are using this node
    last_access_time: float = 0.0

    def is_leaf(self) -> bool:
        return len(self.children) == 0


class RadixTree:
    """
    Minimal RadixAttention trie for prefix caching.
    Supports insert, longest-prefix lookup, and LRU eviction.
    """

    def __init__(self):
        self.root = RadixNode(token_ids=[], kv_data=None)
        self._clock = 0.0

    def _tick(self) -> float:
        self._clock += 1.0
        return self._clock

    def insert(self, token_ids: list[int], kv_data: bytes) -> None:
        """
        Insert a fully prefilled sequence into the trie.
        Splits existing edges as needed (standard radix tree insertion).
        """
        node = self.root
        idx = 0  # position in token_ids

        while idx < len(token_ids):
            first_token = token_ids[idx]

            if first_token not in node.children:
                # No matching child — create a new leaf.
                new_node = RadixNode(
                    token_ids=token_ids[idx:],
                    kv_data=kv_data,  # store full KV data at leaf
                    last_access_time=self._tick(),
                )
                node.children[first_token] = new_node
                return

            child = node.children[first_token]
            # Find longest common prefix between token_ids[idx:] and child.token_ids.
            lcp = 0
            while (lcp < len(child.token_ids) and
                   idx + lcp < len(token_ids) and
                   child.token_ids[lcp] == token_ids[idx + lcp]):
                lcp += 1

            if lcp == len(child.token_ids):
                # Fully matched the existing edge — descend.
                idx += lcp
                node = child
            else:
                # Partial match — split the edge.
                # Create an intermediate node with the common prefix.
                split_node = RadixNode(
                    token_ids=child.token_ids[:lcp],
                    kv_data=None,  # split node has no KV data of its own
                    last_access_time=self._tick(),
                )
                # Old child gets the suffix as its new edge label.
                child.token_ids = child.token_ids[lcp:]
                split_node.children[child.token_ids[0]] = child
                # New leaf gets the remaining tokens.
                remainder_node = RadixNode(
                    token_ids=token_ids[idx + lcp:],
                    kv_data=kv_data,
                    last_access_time=self._tick(),
                )
                split_node.children[token_ids[idx + lcp]] = remainder_node
                # Attach split_node to parent.
                node.children[first_token] = split_node
                return

    def match_prefix(self, token_ids: list[int]) -> tuple[int, Optional[bytes]]:
        """
        Find the longest cached prefix of token_ids.
        Returns (length_matched, kv_data_of_deepest_matched_node).
        """
        node = self.root
        idx = 0
        best_len = 0
        best_kv = None

        while idx < len(token_ids):
            first_token = token_ids[idx]
            if first_token not in node.children:
                break

            child = node.children[first_token]
            child.last_access_time = self._tick()  # update LRU stamp

            lcp = 0
            while (lcp < len(child.token_ids) and
                   idx + lcp < len(token_ids) and
                   child.token_ids[lcp] == token_ids[idx + lcp]):
                lcp += 1

            idx += lcp

            if child.kv_data is not None:
                best_len = idx
                best_kv = child.kv_data

            if lcp < len(child.token_ids):
                break  # partial match — descent stops here

            node = child

        return best_len, best_kv

The implementation above shows the essential structure. In production (e.g., the SGLang codebase), kv_data is replaced by a list of physical GPU memory block IDs, and the tree nodes carry reference counts so the memory manager knows which blocks are actively being read by running requests.

7.7.4 vLLM Automatic Prefix Caching (APC)¶

vLLM’s Automatic Prefix Caching (APC), introduced in vLLM 0.4, takes a simpler but highly effective approach: it reuses the existing PagedAttention block table and adds a global evictor hash table on top. In the V1 engine (the default since 2025), APC was redesigned for constant-time eviction and near-zero overhead — under 1 % throughput cost even at a 0 % hit rate — and is now enabled by default, so you opt out with --no-enable-prefix-caching rather than opting in. See vLLM: Architecture, PagedAttention & Internals for the block allocator background.

In vLLM’s model:

• Every physical block of 16 tokens has a block hash computed as in Section 7.7.2.
• A global prefix_cache: dict[BlockHash, PhysicalBlock] is maintained alongside the normal free list.
• When a request completes (or when a block is fully written), the block is inserted into prefix_cache keyed by its hash. The block is not freed; instead it enters an LRU evictor.
• When a new request arrives, the scheduler computes the first \(k\) block hashes and checks prefix_cache. If a hit occurs, the corresponding physical block is mapped into the new request’s block table without any GPU computation.
• The LRU evictor runs when memory pressure requires freeing blocks: the least-recently-used cached blocks are evicted first, before any block that is actively referenced by a running request.

# Pseudo-code: vLLM APC block-allocation logic (simplified from vLLM source)

class APCBlockAllocator:
    def __init__(self, num_blocks: int, block_size: int):
        self.block_size = block_size
        self.free_blocks: list[int] = list(range(num_blocks))
        # Map from content hash -> physical block id
        self.prefix_cache: dict[int, int] = {}
        # LRU ordering: (timestamp, block_id) — use a sortedcontainer in practice
        self.lru_order: list[tuple[float, int]] = []
        self._time = 0

    def _compute_block_hash(self, prev_hash: int, token_ids: list[int]) -> int:
        """Chain the previous block hash with current token IDs."""
        import hashlib
        # Encode each token id in 4 bytes. (`bytes(token_ids)` would raise for
        # any id > 255, and real vocabularies run to 32k-256k entries.)
        packed = b"".join(t.to_bytes(4, 'little') for t in token_ids)
        data = prev_hash.to_bytes(8, 'little') + packed
        return int.from_bytes(hashlib.sha256(data).digest()[:8], 'little')

    def allocate_or_reuse(
        self,
        token_ids_blocks: list[list[int]]
    ) -> tuple[list[int], int]:
        """
        Given a list of blocks (each a list of token IDs), return:
          - block_ids: physical block IDs for the full context
          - num_cached: how many leading blocks came from cache
        """
        block_ids = []
        prev_hash = 0
        num_cached = 0

        for i, block_tokens in enumerate(token_ids_blocks):
            h = self._compute_block_hash(prev_hash, block_tokens)

            if h in self.prefix_cache:
                # Cache hit: reuse this physical block.
                phys_id = self.prefix_cache[h]
                block_ids.append(phys_id)
                num_cached += 1
                self._touch(phys_id)
            else:
                # Cache miss: allocate a fresh physical block.
                # Evict if necessary.
                if not self.free_blocks:
                    self._evict_lru()
                phys_id = self.free_blocks.pop()
                # We will compute KV for this block during prefill.
                # After prefill completes, insert into cache.
                self.prefix_cache[h] = phys_id
                self._touch(phys_id)
                block_ids.append(phys_id)

            prev_hash = h

        return block_ids, num_cached

    def _touch(self, block_id: int):
        """Update LRU timestamp for a block."""
        self._time += 1
        self.lru_order.append((self._time, block_id))

    def _evict_lru(self):
        """Remove the least-recently-used cached block."""
        self.lru_order.sort()
        while self.lru_order:
            _, block_id = self.lru_order.pop(0)
            # Remove from prefix cache if it's still there and not pinned.
            for k, v in list(self.prefix_cache.items()):
                if v == block_id:
                    del self.prefix_cache[k]
                    self.free_blocks.append(block_id)
                    return

RadixAttention vs vLLM APC: a comparison¶

Both systems share the same fundamental guarantee: only complete blocks that are fully written (all token IDs fixed) are eligible for caching. A partially-filled block at the trailing edge of a prefix cannot be placed in the cache because its hash would change as more tokens are appended.

The kernel side: cascade (shared-prefix) attention¶

Everything above is memory-management work: the block table now points many requests at the same physical pages. But the attention kernel still does redundant work. During decode, each of the \(N\) requests in a batch issues its own paged-attention pass, and each pass streams the entire shared prefix’s K and V out of HBM — so the same physical pages are read \(N\) times per step. Decode is memory-bandwidth bound (see The Anatomy of LLM Inference), so with a long shared prefix this re-reading, not the prefill you saved, becomes the dominant cost.

Cascade attention removes it. Split the attention for each query into two disjoint key ranges — the shared prefix and the request’s private suffix — compute each separately, and merge. The shared-prefix pass is run once for the whole batch as a multi-query kernel (all \(N\) queries against one contiguous KV region, so the prefix is read from HBM exactly once), while the suffix pass stays per-request and paged. Merging is exact, not an approximation, because softmax decomposes over a partition of the keys. If pass \(i\) returns partial output \(O_i\) and its log-sum-exp \(s_i = \log \sum_{j \in \mathcal{K}_i} e^{q \cdot k_j / \sqrt{d}}\), then

which is precisely the online-softmax rescaling FlashAttention already performs across tiles (FlashAttention I: IO-Awareness & The Online Softmax) — cascade attention just exposes it as a public operation over separately-computed partials.

The library that implements this is FlashInfer: MultiLevelCascadeAttentionWrapper takes a radix-tree-shaped set of shared levels (a global system prompt, then a per-tenant few-shot header, then per-request tokens) and merges them level by level with its merge_state primitive. vLLM’s FlashInfer and FlashAttention backends enable cascade attention automatically when the scheduler observes a long-enough prefix shared by enough requests in the current batch (it is a throughput heuristic — with only two or three sharers the extra kernel launch is not worth it); SGLang applies the same trick for its radix-tree hits. ChunkAttention (Ye et al., 2024) is the same idea with a different data layout.

7.7.5 Cache Eviction and Memory Pressure¶

A prefix cache competes for the same GPU DRAM as the KV memory needed by actively running requests. This creates a fundamental tension: holding too many cached prefixes starves new requests of memory; holding too few means cache misses.

LRU eviction¶

Both major systems use Least-Recently-Used (LRU) eviction at block granularity. The LRU policy is a good fit because:

1. System prompts and few-shot headers are re-used many times and thus have high recency at any given moment.
2. Completed responses from long-ago requests are unlikely to be needed again.

The eviction trigger is memory pressure: the allocator attempts to satisfy a new allocation from free blocks first, then from the LRU tail of the cache.

Priority tiers¶

Some deployments add priority annotations to cached blocks:

• Pinned: never evicted (reserved for very high-frequency system prompts).
• Normal: evicted LRU.
• Ephemeral: evicted immediately after the owning request completes.

On the vLLM V1 engine, APC runs with normal-priority LRU eviction by default (disable it with --no-enable-prefix-caching); the legacy V0 engine instead required opting in with --enable-prefix-caching. SGLang exposes finer-grained control through its CacheEngine API.

Cache sizing heuristics¶

A rough rule of thumb: allocate 15–25 % of the KV cache budget to “warm” cached blocks for a production system that uses a static system prompt. If you have a 40 GB GPU KV budget and a 2,000-token system prompt that accounts for 80 % of traffic, the warm portion for that prompt is tiny (a few MB; see the worked example below). The budget concern arises with many distinct prefixes (e.g., per-user system prompts or a large set of few-shot demonstrations), where the aggregate footprint can run into gigabytes.

7.7.6 Cross-Request Sharing and Concurrency¶

A subtle but important aspect of prefix caching is concurrent access to shared blocks. When two requests simultaneously benefit from the same cached prefix, they must not interfere with each other. The key insight is that cached KV blocks are read-only: once a block is finalized and inserted into the cache, no running request ever modifies it (new tokens are written into fresh, unshared blocks appended after the cached prefix). This makes concurrent reading safe without locks.

The reference count on each block tracks how many active requests are currently using it. A block with ref_count > 0 cannot be evicted, even if it is the LRU candidate.

This design is sometimes called copy-on-write semantics: the cached prefix is shared as read-only, and any divergence (the user-specific suffix) is written to fresh blocks that belong exclusively to each request.

Cross-session versus within-session caching¶

Most implementations cache across sessions — two entirely separate HTTP requests from different users share blocks if they have the same prefix. Within a single multi-turn conversation, caching is even simpler because the serving framework can explicitly pin the turn history in the cache.

The security implication is real, and it is a timing channel more than a memory channel: because a cache hit is dramatically faster than a miss, an attacker who can measure TTFT can test guesses about another tenant’s prefix one block at a time, learning whether their guessed 16 tokens were already in the cache. In practice, a system prompt is usually visible to anyone who can query the endpoint anyway, so this rarely matters — but it does matter when the prefix contains retrieved documents or user PII.

The standard mitigation is cache salting: mix a per-tenant secret into the seed of the hash chain, so tenant A’s blocks can never collide with tenant B’s even for identical tokens. vLLM exposes this as a per-request cache_salt field (the salt is folded into the first block’s hash, and the chain carries it forward), which gives you tenant isolation without the cost of running separate model replicas. Reuse within a tenant is preserved; reuse across tenants is made impossible by construction.

7.7.7 The Economics of Shared Prefixes¶

Prefix caching produces the largest gains precisely when it is needed most: when a large, repeated prefix dominates request cost. Let us quantify this carefully.

Cost model¶

For a request with prefix length \(P\) (tokens) and new suffix length \(S\) (tokens):

• Without caching: prefill cost \(\propto (P + S)^2 / 2\) attention operations (rough \(O(N^2)\) scaling) plus \(P + S\) weight projections.
• With a warm cache hit on the full prefix: prefill cost \(\propto S \cdot P + S^2/2\) (the suffix attends to the cached prefix) plus \(S\) weight projections.

The ratio of cached to uncached prefill work is approximately

For \(P = 2000\), \(S = 50\) (a 2,000-token system prompt with a short user query): speedup \(\approx 41\times\) in prefill attention FLOPs. Real TTFT improvements are smaller due to weight-loading overhead that is shared regardless of cache state, but 5–15× TTFT improvements are commonly observed in practice.

Where shared prefixes arise in practice¶

The agent use case (see The Agentic Loop: ReAct, Plan-Execute & Reflection) deserves particular attention. In a ReAct loop, each new turn prepends the entire conversation history. After \(k\) turns with average turn length \(L\), the prefix is \(k \cdot L\) tokens. Without prefix caching, total prefill cost scales as \(O(k^2 L)\); with caching and a warm trie, each new turn costs only \(O(L)\) for the suffix, so total cost scales as \(O(kL)\) — a qualitative improvement in long-horizon agent tasks. This is also why a “context compaction” step that rewrites earlier turns is so expensive: it invalidates the whole trie path from the edit point onward, forcing a full re-prefill. Prefer appending over editing, and when you must compact, do it rarely and at a block boundary. The narrow research agent in A Narrow Auto-Research Agent: ReAct, Tool-Use & Retrieval by Distillation is built on exactly this append-only discipline.

7.7.8 Enabling and Tuning Prefix Caching in Production¶

vLLM configuration¶

# Enable APC in vLLM (the flag is per-engine startup)
python -m vllm.entrypoints.openai.api_server \
    --model meta-llama/Llama-3-70b-instruct \
    --enable-prefix-caching \
    --max-model-len 32768 \
    --gpu-memory-utilization 0.90 \
    --block-size 16

The --block-size parameter controls the hashing granularity. Larger blocks mean fewer hash lookups but coarser prefix alignment — a prompt that is one token short of a full block boundary gets no cache benefit for that trailing block. On the current V1 engine --enable-prefix-caching is redundant (APC is already on); pass --no-enable-prefix-caching only when you need it off — for example to force a full recomputation for debugging or benchmarking. (Requesting prompt logprobs does not require disabling APC on V1: the engine keeps caching on but transparently recomputes the full-prompt prefill for that request rather than returning cached logprobs.)

# Verify APC is active via vLLM metrics endpoint
import requests

stats = requests.get("http://localhost:8000/metrics").text
# Look for: vllm:gpu_prefix_cache_hit_rate
# and:      vllm:gpu_cache_usage_perc

for line in stats.splitlines():
    if "prefix_cache" in line or "cache_usage" in line:
        print(line)

SGLang configuration¶

# SGLang enables RadixAttention by default; disable with --disable-radix-cache
python -m sglang.launch_server \
    --model-path meta-llama/Llama-3-70b-instruct \
    --tp 4 \
    --context-length 32768 \
    --mem-fraction-static 0.85
# Metrics available at http://localhost:30000/get_server_info

Prefix reuse without a serving engine¶

You do not need vLLM to get the benefit — and for a ~100M model served on one GPU or a laptop, you probably should not run vLLM at all. The mechanism is available directly in transformers through past_key_values: prefill the shared prefix once, keep the resulting Cache object, and hand a copy of it to every request. This is exactly the pattern used to serve Stack-100M in Evaluation & Serving: Honest Benchmarks, int4 Quantization, and Running on a Laptop.

# Minimal prefix cache with plain HF transformers: the mechanism vLLM/SGLang
# industrialise, in ~15 lines. Good enough for a single-GPU 100M-class model.
import copy
import torch
from transformers import AutoModelForCausalLM, AutoTokenizer

MODEL = "HuggingFaceTB/SmolLM2-135M-Instruct"  # stand-in for your own 100M model
tok = AutoTokenizer.from_pretrained(MODEL)
model = AutoModelForCausalLM.from_pretrained(
    MODEL, torch_dtype=torch.bfloat16, device_map="auto").eval()

SYSTEM = "You are a terse research assistant. Answer in one sentence.\n\n"
sys_ids = tok(SYSTEM, return_tensors="pt").input_ids.to(model.device)

with torch.no_grad():
    # ONE prefill of the shared prefix. `past_key_values` is a Cache object
    # holding K and V for every layer at every prefix position.
    PREFIX_CACHE = model(sys_ids, use_cache=True).past_key_values

def answer(user_text: str, max_new_tokens: int = 48) -> str:
    # deepcopy is mandatory: generation APPENDS the new tokens' KV in place,
    # so a shared cache would be corrupted by the first request that used it.
    past = copy.deepcopy(PREFIX_CACHE)
    full = torch.cat(
        [sys_ids, tok(user_text, return_tensors="pt").input_ids.to(model.device)],
        dim=1)
    # Pass the FULL prompt plus the warm cache: generate() sees that the cache
    # already covers the first sys_ids.shape[1] positions and prefills only the
    # remaining suffix.
    out = model.generate(full, past_key_values=past, use_cache=True,
                         max_new_tokens=max_new_tokens, do_sample=False)
    return tok.decode(out[0, full.shape[1]:], skip_special_tokens=True)

print(answer("What is a radix tree?"))

The deepcopy is the whole reason paged allocators exist: it costs a full copy of the prefix KV per concurrent request, which is precisely the \(O(N \cdot P)\) memory blow-up that PagedAttention’s shared read-only pages eliminate. For a handful of concurrent requests against a 100M model this is fine; past a few dozen it is not, and that is your cue to move to vLLM or SGLang.

At the GGUF end of the stack, llama.cpp’s llama-server does the same thing per slot: it keeps the previous prompt for each slot and reuses their longest common prefix (the cache_prompt request option, on by default in recent builds), and --slot-save-path lets you save and restore a slot’s KV state to disk so a long system prompt survives a restart — the KV cache being stored in whatever --cache-type-k/-v format you chose (see Quantization II: INT4/INT8/FP8, GGUF, bitsandbytes & QAT).

Maximising hit rate: best practices¶

# Example: structuring prompts for maximum cache reuse
# The STABLE part of the prompt must come FIRST.

SYSTEM_PROMPT = """
You are a senior software engineer reviewing code for correctness,
performance, and security. For each issue found:
1. Describe the issue clearly.
2. Explain the impact.
3. Suggest a fix with example code.
""".strip()

def build_prompt(user_code: str) -> str:
    """
    Always place the system prompt at position 0.
    The user-specific code comes last, ensuring the shared prefix
    can be cached and reused across all requests.
    """
    return f"{SYSTEM_PROMPT}\n\n---\n\nCode to review:\n```python\n{user_code}\n```"

# ANTI-PATTERN: injecting dynamic content into the shared prefix
def build_prompt_bad(user_code: str, timestamp: str) -> str:
    """
    DO NOT embed timestamps or request IDs into the system prompt.
    This makes every prompt unique and destroys the shared prefix.
    """
    return (
        f"Current time: {timestamp}\n"   # ← defeats prefix caching
        f"{SYSTEM_PROMPT}\n\n"
        f"Code:\n{user_code}"
    )

Alignment to block boundaries. Because the cache operates on full blocks, prompts that are aligned to multiples of block_size tokens get the best coverage. If your system prompt is 1,020 tokens and block_size=16, the last partial block (4 tokens) will never be cached. Pad the system prompt to 1,024 tokens to get full coverage.

def pad_to_block_boundary(token_ids: list[int],
                           block_size: int,
                           pad_token_id: int = 0) -> list[int]:
    """
    Pad a prefix to the next block boundary so that no tokens are
    left in an uncacheable partial block.
    """
    remainder = len(token_ids) % block_size
    if remainder == 0:
        return token_ids
    padding = block_size - remainder
    return token_ids + [pad_token_id] * padding

Interaction with chunked prefill¶

When chunked prefill is enabled (see Disaggregated Prefill/Decode & Chunked Prefill), a long prompt is split into multiple “chunks” and processed across several scheduler iterations. Prefix caching interacts cleanly: cached blocks are consumed in the first chunk without any compute; only uncached blocks are fed into the chunked prefill pipeline.

Interaction with speculative decoding¶

Speculative decoding (see Speculative Decoding: Draft Models, Medusa, EAGLE & Lookahead) accelerates the decode phase; prefix caching primarily accelerates prefill (and, via cascade attention, the HBM traffic of decode). They are largely orthogonal and can be combined: enable both for workloads that have a large shared prefix followed by a multi-token generation step. One interaction to know: rejected speculative tokens must not be committed to the prefix cache, since their KV blocks correspond to token IDs that were never actually accepted into the sequence — engines handle this by only hashing and publishing blocks after the accepted-length is known.

7.7.9 Advanced Topics and Open Problems¶

Disk-level prefix caching¶

For extremely long, rarely-changing prefixes — such as entire codebases embedded as context (the “repository-level code completion” use case) — it is possible to store pre-computed KV tensors on NVMe SSDs and load them into GPU VRAM on demand. This is sometimes called persistent KV caching or offline prefix materialisation. The GPU-NVMe bandwidth of modern PCIe 5.0 systems (on the order of 12–14 GB/s) is fast enough to load a 10,000-token prefix in well under a second.

The engineering challenge is cache invalidation: if the model weights change (e.g., after a fine-tuning update), all persistent KV caches become stale and must be regenerated. Some serving systems track a model-version hash alongside each on-disk KV file.

Multi-model and cross-layer caching¶

All the caching described so far applies to a single model instance. In a serving cluster running multiple replicas of the same model, caching can be extended across replicas: one node holds the “canonical” KV cache for a popular system prompt, and other nodes pull the cache over the network (RDMA or NVLink) rather than recomputing it. This is sometimes called distributed prefix caching or remote KV caching.

The arithmetic favours transfer more than intuition suggests. Take the 1,024-token, 335 MB prefix from the worked example above: moving it over a 200 Gb/s RDMA link (≈25 GB/s achieved) takes on the order of 13 ms, whereas recomputing it costs roughly \(2 \times (70 \times 10^9) \times 1024 \approx 1.4 \times 10^{14}\) FLOPs — several hundred milliseconds on one accelerator at realistic prefill efficiency. Fetching wins by an order of magnitude whenever the link is fast, which is why “KV-cache-centric” cluster designs have become mainstream: LMCache layers GPU/CPU/disk/S3 tiers under vLLM and SGLang, and Moonshot’s Mooncake architecture makes a disaggregated, cluster-wide KV store the primary scheduling object (see Disaggregated Prefill/Decode & Chunked Prefill). The design question shifts from “should we transfer?” to “is the KV store’s hit rate high enough to justify the extra tier of memory,” and to cache-aware routing — a load balancer that sends a request to the replica already holding its prefix (SGLang’s router and vLLM’s production stack both support this) converts a cluster-wide miss into a local hit for free.

Quantized KV caches¶

Storing KV caches in INT8 or FP8 reduces their memory footprint by 2–4× (see Quantization I: Post-Training Quantization (GPTQ, AWQ, SmoothQuant)), which directly increases the number of distinct prefixes that can be held warm simultaneously. The tradeoff is a small accuracy loss in the attention computation for the cached tokens. Both SGLang and vLLM support quantized KV caches via the --kv-cache-dtype flag.

Semantic prefix caching¶

Content-based hashing is exact-match only: two prompts that differ by a single space produce different hashes even if the resulting KV tensors are nearly identical. Research directions include semantic prefix caching, where nearby prompts (in embedding space) can share cache entries via approximate nearest-neighbour lookup. This is an active research area as of 2025–2026 and not yet deployed in mainstream serving stacks.

Further Reading¶

• Zheng, L. et al. “Efficiently Programming Large Language Models using SGLang.” arXiv:2312.07104, 2023. — Introduces RadixAttention and the SGLang serving framework.
• Kwon, W. et al. “Efficient Memory Management for Large Language Model Serving with PagedAttention.” SOSP 2023. — The PagedAttention paper that underpins block-level KV management in vLLM.
• Pope, R. et al. “Efficiently Scaling Transformer Inference.” MLSys 2023. — Analysis of attention arithmetic, prefill/decode separation, and the case for batched serving.
• vLLM blog: “Automatic Prefix Caching in vLLM.” Official vLLM documentation and blog posts at the vLLM GitHub repository — release notes for v0.4 describe APC implementation details.
• Dao, T. et al. “FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.” NeurIPS 2022. — The kernel that makes prefix-aware attention fast enough to matter; see also FlashAttention I: IO-Awareness & The Online Softmax.
• Gim, I. et al. “Prompt Cache: Modular Attention Reuse for Low-Latency Inference.” MLSys 2024. — Formalises the idea of caching attention states for reusable prompt modules.

Exercises¶

1. (Conceptual.) The chapter states that KV tensors are “a pure function of the token IDs and model weights.” Use that fact to answer two questions. (a) A well-meaning engineer prepends f"Current time: {timestamp}\n" to the front of a shared system prompt so the model “knows the current time.” The prefix_cache_hit_rate metric collapses to near zero. Explain precisely why, referring to the chained block-hash construction of Section 7.7.2. (b) The engineer moves the timestamp to after the system prompt instead. Explain why this restores the hit rate for the system-prompt blocks, and state exactly which blocks now hit and which still miss.

2. (Quantitative.) A serving engine uses block_size = 16. A system prompt tokenizes to 1,020 tokens. (a) How many complete, cacheable blocks does the system prompt occupy, and how many tokens are stranded in an uncacheable partial block? (b) Using the chapter’s pad_to_block_boundary helper, to what length is the prompt padded, how many pad tokens are added, and how many cacheable blocks result? © Briefly: what is the downside of padding, and why is it usually worth it here?

3. (Quantitative.) A model has 80 layers, uses GQA with 8 KV heads, head dimension 128, and stores the KV cache in bfloat16 (2 bytes). A shared prefix is 512 tokens long. (a) Compute the bytes of KV per token per layer, then the total KV footprint of the cached prefix. (b) The endpoint receives 300 requests/second, all sharing this prefix. Without prefix caching, how many tokens of prefix prefill are recomputed per second, and how many bytes of redundant KV are produced per second? © With caching, how many copies of the prefix KV are stored in GPU memory, regardless of concurrency?

4. (Quantitative.) The chapter models uncached prefill attention cost as \(\propto (P+S)^2/2\) and cached prefill cost as \(\propto S\cdot P + S^2/2\) (the suffix attends to the cached prefix). Take \(P = 1500\) (prefix) and \(S = 100\) (suffix). (a) Compute the exact attention-op speedup ratio. (b) Compute the chapter’s large-\(P/S\) approximation \((P+S)/S\) and explain why it overestimates the true ratio here. © The chapter says real TTFT gains are typically 5-15x rather than the raw FLOP ratio. Give one reason from the chapter.

5. (Implementation.) Section 7.7.4 shows vLLM-style APC using a flat prefix_cache: dict[hash, block] with a chained block hash. Implement a standalone function

longest_cached_prefix(token_ids, block_size, prefix_cache) -> int

that returns the number of leading tokens already cached, by segmenting token_ids into block_size blocks, chaining hashes exactly as _compute_block_hash in the chapter does (seed prev_hash = 0), and stopping at the first block miss (a cache hit after a miss must not count — the prefix must be contiguous from position 0, per Section 7.7.2 step 3). Only complete blocks are eligible; a trailing partial block never counts. Include a short test.

import hashlib

def _compute_block_hash(prev_hash: int, token_ids: list[int]) -> int:
    """Chain the previous block hash with current token IDs (as in the chapter)."""
    packed = b"".join(t.to_bytes(4, "little") for t in token_ids)
    data = prev_hash.to_bytes(8, "little") + packed
    return int.from_bytes(hashlib.sha256(data).digest()[:8], "little")

def longest_cached_prefix(
    token_ids: list[int],
    block_size: int,
    prefix_cache: dict[int, int],
) -> int:
    """
    Return the number of leading tokens whose (complete) blocks are all
    present in prefix_cache, walking from position 0 and stopping at the
    first miss. A trailing partial block is never counted.
    """
    num_full_blocks = len(token_ids) // block_size  # ignore partial tail
    prev_hash = 0
    cached_tokens = 0
    for i in range(num_full_blocks):
        block = token_ids[i * block_size:(i + 1) * block_size]
        h = _compute_block_hash(prev_hash, block)
        if h not in prefix_cache:
            break                      # contiguity: stop at first miss
        cached_tokens += block_size
        prev_hash = h                  # advance the chain only on a hit
    return cached_tokens

# --- test ---
if __name__ == "__main__":
    B = 4
    # Warm the cache with a 12-token prefix (3 full blocks).
    warm = [10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33]
    cache: dict[int, int] = {}
    ph = 0
    for i in range(len(warm) // B):
        ph = _compute_block_hash(ph, warm[i * B:(i + 1) * B])
        cache[ph] = i  # value = physical block id (arbitrary here)

    # Request sharing the first 2 blocks (8 tokens), then diverging,
    # plus a trailing partial block that must not count.
    req = [10, 11, 12, 13, 20, 21, 22, 23, 99, 98, 97, 96, 5, 5]
    assert longest_cached_prefix(req, B, cache) == 8

    # A request whose block 0 differs gets zero, even if a later
    # block would independently hash into the cache (non-contiguous).
    req2 = [0, 0, 0, 0, 30, 31, 32, 33]
    assert longest_cached_prefix(req2, B, cache) == 0

    # Exact full-prefix hit.
    assert longest_cached_prefix(warm, B, cache) == 12
    print("all tests passed")