KV Cache Optimization and Prefix Caching in LLM Serving: Comparing RadixAttention, Automatic Prefix Caching, and Static Context Sharing

Serving large language models in multi-turn conversational agents, complex retrieval-augmented generation (RAG) pipelines, and few-shot reasoning workflows presents a fundamental memory and compute asymmetry. During autoregressive decoding, every newly generated token must attend to all previous tokens in the sequence. To avoid recomputing Key and Value projection matrices at each decoding step, inference engines store intermediate activations in high-bandwidth GPU memory (HBM) as the KV cache.

However, the KV cache footprint scales linearly with sequence length and batch size:

Memory_KV = 2 × n_layers × n_heads × d_head × seq_len × precision_bytes

For a 70B parameter model utilizing Grouped-Query Attention (GQA) with 8 KV heads, a hidden dimension of 8192, 80 layers, and 16-bit precision (2 bytes), a single 8,192-token context consumes approximately 1.34 GB of VRAM. Across a batch of 64 concurrent requests, the KV cache alone demands more than 85 GB of HBM, exceeding the entire physical memory capacity of an NVIDIA A100 (80GB) GPU before accounting for base model weights.

When workloads exhibit structural redundancy (such as shared system prompts, tool schemas, retrieved context chunks, or branched conversation histories), recomputing or redundantly allocating the KV cache creates severe latency spikes and limits serving capacity. Prefix caching algorithms mitigate these bottlenecks by identifying common token prefixes across requests and reusing previously computed KV states directly from memory.

The Evolution from PagedAttention to Dynamic Prefix Caching

Early inference runtimes allocated continuous physical memory buffers sized to the maximum theoretical sequence length (max_seq_len), resulting in internal and external memory fragmentation rates between 60% and 80%.

In 2023, the introduction of PagedAttention by Kwon et al. in the vLLM project resolved memory fragmentation by virtualizing KV cache allocation. PagedAttention divides the KV cache into fixed-size physical memory blocks (typically 16 or 32 tokens per block). Logical blocks are mapped to physical memory through an operating-system-style page table. This architecture enabled zero-waste memory allocation and basic static prefix sharing via copy-on-write mechanisms.

Modern production workloads, however, require dynamic, cross-request KV cache reuse across unpredictable branching graphs. The primary modern architectural implementations address this through distinct data structures:

1. RadixAttention in SGLang: Tree-Structured Prefix Caching

Introduced by Zheng et al. in the SGLang framework, RadixAttention models all active and historical KV cache sequences as a dynamic Radix Tree (or compact trie) residing in host memory and GPU memory management layers.

Tree Topology: Edges in the radix tree represent variable-length token sequences rather than single tokens or fixed-size pages. Nodes represent branch points where prompt prefixes diverge (for example, two conversations sharing the same 2,048-token system prompt and tool definitions, but differing in user queries).
Exact Token Matching: Unlike fixed-page lookups, RadixAttention evaluates prefix matching at exact token boundaries. When a new request enters the scheduler, the engine traverses the radix tree to find the longest common prefix match.
Dynamic Mutation and LRU Eviction: When GPU memory is constrained, an LRU (Least Recently Used) eviction policy traverses the tree, evicting leaf nodes first and preserving frequently accessed root and branch prefixes. Node split and merge operations occur dynamically as new requests arrive or cached sequences are pruned.
Branching Support: SGLang natively accelerates multi-candidate decoding (such as Tree-of-Thought search, multi-turn tool calling loops, and parallel speculative branches) by branching child nodes directly from a shared parent KV cache state without data duplication.

2. Automatic Prefix Caching (APC) in vLLM: Chained Block Hashing

The vLLM inference engine implements Automatic Prefix Caching (APC) on top of its underlying PagedAttention block manager.

Chained Block Hashes: Instead of maintaining an explicit tree data structure, vLLM computes a deterministic hash for each physical block of tokens. The hash for block N is computed as a cryptographic or MurmurHash combination of the token IDs within block N and the hash of block N-1. This chaining guarantees that identical token sequences appearing at different positional offsets produce distinct hash keys.
Hash Table Indexing: The block manager maintains a global hash table mapping chained block hashes to physical block IDs. When a new prompt arrives, the tokenizer splits the input into block-sized chunks, computes the incremental chained hashes, and queries the table to identify consecutive cached blocks.
Granularity Constraints: Prefix matching is evaluated at the physical block size boundary (typically 16 or 32 tokens). Tokens trailing beyond the last complete block boundary must be recomputed during the prefill phase.
Reference Counting and Eviction: Cached blocks retain a reference count. Active requests increment the reference count, preventing eviction during generation. Idle cached blocks are maintained in an LRU queue and evicted when new allocations require physical memory.

3. Static Context Caching in TensorRT-LLM and TGI

Frameworks like NVIDIA TensorRT-LLM and Hugging Face Text Generation Inference (TGI) provide static context caching and KV sharing mechanisms designed for structured production deployments.

Explicit Prompt Pinning: System prompts or persistent few-shot demonstration blocks are explicitly compiled, prefilled, and pinned in GPU memory during runtime initialization or through explicit administrative API calls.
Tensor Parallel Consistency: In multi-GPU deployments utilizing tensor parallelism (TP) or pipeline parallelism (PP), static context caching maintains synchronized KV tensors across GPU ranks, eliminating coordination overhead during dynamic tree modifications.
Dynamic Limitations: Static implementations excel at high-throughput serving with fixed, invariant system headers, but lack the adaptive flexibility required for arbitrary conversation history branching and dynamic retrieval contexts.

Prefill-Decode Interference and Chunked Prefill Mechanics

Prefix caching directly impacts the scheduling dynamics between the compute-bound prefill phase and the memory-bandwidth-bound decode phase.

When a full prefix cache hit occurs, the Time to First Token (TTFT) drops drastically because the engine bypasses prompt GEMM (General Matrix Multiply) operations entirely, immediately entering the autoregressive decode phase. However, when partial cache hits occur on long-context prompts (such as a 32,000-token document where only the first 4,000 tokens are cached), the remaining 28,000 tokens must be prefilled.

Running monolithic prefill passes introduces prefill-decode interference: ongoing token generation for active streams stalls while the GPU compute units are saturated with large prefill matrix multiplications.

To resolve this latency jitter, modern engines incorporate chunked prefill techniques, pioneered by Sarathi-Serve (Agrawal et al.) and SARATHI (Agrawal et al.):

Token Budget Slicing: The scheduler divides long prefill sequences into discrete token chunks (typically between 512 and 2,048 tokens per chunk, configured via parameters such as max_num_batched_tokens).
Interleaved Batches: Each scheduling step combines prefill chunks with active decode steps. This maintains sustained GPU compute saturation while keeping inter-token latency (ITL / TPOT) deterministic.
Cache Interaction Nuances: In chunked prefill environments, engines must ensure prefix cache lookups occur before chunk dispatch. In some multi-stage schedulers, if only the initial chunk is checked against the prefix cache, subsequent chunks within a running request may miss potential downstream cache hits if prompt structures diverge mid-stream.

Architectural Tradeoffs and Operational Failure Modes

Deploying prefix caching in production environments introduces specific failure modes that engineering teams must monitor and mitigate:

1. Prefix Hijacking and Tokenizer Boundary Drift

Prefix caching relies on exact sequence equivalence. Subtle changes in upstream prompt construction can invalidate the entire downstream cache hierarchy (an effect known as prefix hijacking):

Whitespace and Formatting Drift: Variations in whitespace, newline encoding (\n vs \r\n), or chat template wrappers (such as changing <|im_start|>user formatting) cause hash mismatches at the root of the tree, forcing complete prefill recomputation.
Token Boundary Inconsistencies: Tokenizers (such as BPE and SentencePiece) merge adjacent characters conditionally based on preceding characters. For example, prepending a space or changing capitalization alters token IDs for subsequent subwords, preventing prefix cache matches even if the raw text appears nearly identical.
Mitigation: Implement prompt canonicalization middleware in API gateway layers to normalize system prompts, strip trailing whitespace, and enforce strict, immutable chat template serialization.

2. Eviction Thrashing Under High Concurrency

When serving high request volumes with diverse context headers, the physical KV cache pool can enter eviction thrashing:

If the working set of unique active prefixes exceeds available HBM capacity, the cache manager continuously evicts and recomputes prefix blocks.
Under heavy load, the overhead of frequent memory reallocation and tree manipulation degrades overall throughput below the non-cached baseline.
Mitigation: Size GPU memory allocations to preserve a dedicated prefix cache buffer (using flags such as gpu_memory_utilization 0.90), or offload long-term prefix states to host CPU DRAM via hierarchical storage layers like LMCache.

Serving Economics and Latency Impact

The economic and latency advantages of prefix caching depend directly on workload prefix overlap ratios:

Time to First Token (TTFT): On workloads with 70% to 90% prefix overlap (typical in customer service agents, structured code extraction, and multi-turn chat), TTFT decreases by 50% to 80%, reducing initial response latency from multiple seconds to sub-second ranges.
Aggregate Throughput: By eliminating redundant prefill computation, aggregate cluster request throughput increases by 2x to 5x on few-shot benchmarks (such as MMLU and GSM8K evaluation harnesses) and multi-step agent pipelines.
Infrastructure TCO: Reusing cached KV states reduces the total number of GPU nodes required to meet stringent P95 and P99 latency SLAs, directly lowering serving infrastructure expenditures.

Summary Checklist for Production Deployment

Choose the Matching Architecture: Select SGLang (RadixAttention) for complex agentic workflows, dynamic conversation trees, and arbitrary prefix lengths. Select vLLM (APC) for high-concurrency standard serving with shared system prompts and fixed block structures. Select TensorRT-LLM for static, high-throughput enterprise pipelines with invariant prompts.
Enforce Prompt Canonicalization: Lock system prompts and tool schemas into deterministic, byte-identical strings upstream to prevent prefix drift.
Pair with Chunked Prefill: Enable chunked prefill alongside prefix caching to prevent large prompt misses from causing tail-latency spikes on concurrent decoding streams.
Monitor Cache Hit Ratios: Track Prometheus metrics for prefix cache hit rates; investigate immediately if cache hit rates on standardized routes drop below 70%.