The Latency Wall: Why Prefill Dominates Multi-Turn Serving

In high-throughput Large Language Model (LLM) serving systems, generation latency breaks down into two distinct phases: prefill (processing prompt tokens in parallel to construct initial Key-Value tensors) and decode (generating tokens autoregressively one by one). While decoding is bandwidth-bound—constrained by how fast model weights can be streamed from High Bandwidth Memory (HBM) to compute cores—prefill is strictly compute-bound, scaling quadratically with sequence length $O(N^2)$ in standard multi-head self-attention.

Consider an autonomous agent execution loop or a multi-turn document chat. In each turn, the system resends the entire conversation history, thousands of system instructions, and external tool definitions. Re-running the prefill phase across identical 16,000-token system prompts on every single request wastes GPU FLOPs, creates massive Time-To-First-Token (TTFT) spikes, and bottlenecks server concurrency. Prompt caching avoids this redundancy entirely by preserving the computed Key and Value tensors in GPU memory across requests, turning an $O(N^2)$ matrix multiplication pass into an $O(1)$ memory lookup.

Anatomy of the KV Cache: Memory Layout and PagedAttention

To grasp prompt caching, we must first look at how KV cache tensors live in physical GPU VRAM. For a standard transformer model, every attention layer stores Key ($K$) and Value ($V$) tensors for each token. The raw byte size of the KV cache for a context sequence is calculated as:

Bytes = 2 * n_layers * n_kv_heads * d_head * precision_bytes * seq_len

For Llama-3-70B (80 layers, 8 KV heads with Grouped-Query Attention, head dimension 128, FP16 precision):

Bytes_per_token = 2 * 80 * 8 * 128 * 2 = 327,680 bytes (~320 KB/token)

A 16,000-token context consumes roughly 5.12 GB of VRAM for KV state alone. Historically, naive inference runtimes allocated continuous memory buffers sized to the maximum context length ($L_{max}$), leading to massive internal fragmentation (over 60% memory waste). Systems like vLLM addressed this by introducing PagedAttention, inspired by virtual memory paging in OS kernels. Instead of contiguous physical buffers, the KV cache is divided into fixed-size blocks (typically 16 or 32 tokens). Logical block addresses are mapped dynamically to non-contiguous physical GPU pages through a block table.

Prefix Caching Mechanics: Radix Trees vs. Chunked Hashes

Once KV memory is decoupled into discrete physical blocks, sharing identical prefixes between requests becomes an address-mapping problem. Two dominant architectural approaches exist in production engines:

1. Chunked Boundary Hashing (Commercial APIs)

Proprietary APIs (like Anthropic and OpenAI) partition the prompt into fixed-size token chunks (e.g., blocks of 1,024 tokens). Each chunk is hashed using a rolling cryptographic or non-cryptographic hash (such as xxHash64) that incorporates the hash of all preceding chunks. If an incoming prompt matches the prefix hash up to token boundary $k imes 1024$, the engine reuses the precomputed blocks and runs prefill only for the remaining slice.

2. Token-Level Radix Trees (vLLM, SGLang)

State-of-the-art open-source engines employ a Radix Tree (a space-optimized trie) resident in host RAM to track active and cached KV blocks directly on the GPU. Unlike fixed-size hashing, a Radix Tree dynamically represents prompt token sequences as paths of varying lengths.

  • Nodes represent sequences of tokens and hold pointers to physical KV block allocations on the GPU.
  • Edges represent token transitions.
  • Reference Counters track active requests currently reading from specific nodes.
  • LRU Eviction Queues prioritize reclaiming unreferenced nodes when VRAM runs low.

When a new request arrives with prompt tokens $[t_0, t_1, ..., t_m]$, the engine traverses the Radix Tree from the root node to find the longest matching prefix. It reclaims the matched physical block indices, populates the request's PagedAttention block table, and dispatches only the unmatched suffix $[t_k, ..., t_m]$ to the GPU tensor cores.

A Minimal Radix Cache Controller

Here is an illustrative Python implementation demonstrating how a Radix cache manager indexes token blocks, tracks reference counts, and determines the reusable prefix length:

import time
from typing import Dict, List, Optional, Tuple

class RadixNode:
    def __init__(self, token_ids: List[int], physical_blocks: List[int], parent: Optional['RadixNode'] = None):
        self.token_ids = token_ids
        self.physical_blocks = physical_blocks
        self.children: Dict[int, 'RadixNode'] = {}
        self.parent = parent
        self.ref_count = 0
        self.last_accessed = time.time()

class RadixKVCache:
    def __init__(self, block_size: int = 16):
        self.block_size = block_size
        self.root = RadixNode(token_ids=[], physical_blocks=[])

    def match_prefix(self, tokens: List[int]) -> Tuple[List[int], int]:
        """Traverses the Radix tree to find physical blocks for the longest matching prefix."""
        node = self.root
        matched_blocks = []
        token_offset = 0

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

            child = node.children[first_token]
            edge_len = len(child.token_ids)
            segment = tokens[token_offset : token_offset + edge_len]

            # Check if current tokens match the full edge
            if segment == child.token_ids:
                matched_blocks.extend(child.physical_blocks)
                token_offset += edge_len
                node = child
                node.last_accessed = time.time()
            else:
                # Partial match on the edge: compute common prefix
                match_len = 0
                for a, b in zip(segment, child.token_ids):
                    if a == b:
                        match_len += 1
                    else:
                        break
                
                # Split edge if aligned to block size
                usable_blocks = match_len // self.block_size
                matched_blocks.extend(child.physical_blocks[:usable_blocks])
                token_offset += usable_blocks * self.block_size
                break

        return matched_blocks, token_offset

    def pin_node(self, node: RadixNode):
        curr = node
        while curr:
            curr.ref_count += 1
            curr = curr.parent

    def unpin_node(self, node: RadixNode):
        curr = node
        while curr:
            curr.ref_count = max(0, curr.ref_count - 1)
            curr = curr.parent

Memory Eviction: LRU and Reference Counting

Because physical GPU memory is strictly bounded, the Radix Tree cannot grow indefinitely. When allocating physical blocks for a new request fails due to VRAM exhaustion, the memory manager initiates cache eviction:

  1. Leaf Node Candidate Selection: The eviction manager scans leaves of the Radix Tree where ref_count == 0 (meaning no current batch request is executing against this branch).
  2. Least Recently Used (LRU) Pruning: Nodes with the oldest last_accessed timestamp are excised. Their physical GPU page indices are recycled into the allocator's free list.
  3. Branch Consolidation: If a parent node is left with a single child after eviction, the edge tokens can be merged, preventing tree bloat.
Failure Mode Alert: If an engine experiences heavy concurrent load with diverse prefixes, cache thrashing occurs. The overhead of tree traversal, memory page freeing, and cache fragmentation can cause latency degradation worse than un-cached execution.

Production Pitfalls and Design Rules

To extract actual cost and latency savings from prompt caching, engineers must structure their applications around inference engine memory constraints:

  • Static-Prefix Placement: Place invariant text (system prompts, tool definitions, schema definitions) at the absolute beginning of the prompt array. Even a single dynamic token (such as a changing timestamp or random seed) placed at token index 0 invalidates the entire downstream cache tree.
  • Block Alignment Padding: If using chunk-based caching engines, ensure large context documents align with boundary sizes (e.g., 1024 or 2048 tokens). A mismatch of a few characters can shift subsequent text across chunk boundaries, causing complete cache misses.
  • Deterministic Serialization: Tool parameters and JSON schemas must be serialized with sorted keys. Different key ordering produces distinct token IDs, causing separate branches in the Radix Tree and multiplying GPU memory consumption.

Key Takeaways

  • Prompt caching turns compute-bound prefill operations into memory lookups by preserving Key-Value tensors across API calls.
  • Modern runtimes leverage PagedAttention to eliminate internal fragmentation and use Radix Trees to share variable-length prefixes across requests.
  • Nodes in the Radix Tree map logical token spans directly to non-contiguous physical GPU pages managed by LRU eviction policies.
  • Any non-deterministic prefix variation (timestamps, unsorted JSON schemas) completely invalidates downstream cached blocks.