Prefix-Tree KV Cache Management in Production: RadixAttention, Tree-Structured LRU Eviction, and Token-Level Sharing in SGLang and vLLM

Autoregressive large language model inference is heavily constrained by memory bandwidth and the computational overhead of the prefill phase. For workloads such as multi-turn conversations, autonomous agent tool loops, few-shot prompt evaluations, and tree-search decoding, consecutive requests often share substantial token prefixes. In a standard multi-turn session or agentic pipeline, 70% to 90% of prompt tokens may represent immutable system instructions, tool schemas, or historical turns that have already been processed in previous iterations.

Recomputing Key-Value (KV) cache tensors for identical token sequences on every turn wastes GPU compute cycles and degrades Time to First Token (TTFT). However, naive caching schemes that rely on static prompt hashing or flat buffers fail when prefixes branch dynamically. Modern serving engines address this challenge by treating KV cache memory as a dynamic radix tree. Pioneered by SGLang through RadixAttention and adapted across production engines including vLLM and distributed systems like Mooncake, prefix-tree cache management enables token-level sharing, automatic branch management, and deterministic tree-structured eviction.

The Limitation of Flat and Hash-Based Prefix Caching

Before prefix-tree architectures, serving runtimes managed KV caches using two primary approaches:

Request-bound allocation: The engine creates a fresh KV cache for each request and frees the allocated GPU memory immediately upon request completion. This design avoids cache management overhead but completely ignores cross-request and inter-turn token overlap.
Static prefix hashing: The engine computes a hash (such as SHA-256) over fixed prompt templates or system prompts. If a request begins with an exact match to a registered template, the pre-allocated KV buffer is copied or mapped.

Static hashing breaks down in interactive workloads. In multi-agent systems, few-shot evaluations, and multi-turn dialogues, prefixes are dynamic:

Dynamic branching: In agent self-consistency or beam search, multiple generation paths diverge from a shared reasoning trajectory.
Interleaved execution: In multi-turn chat, each turn extends the previous sequence, turning what was once output generation into prefix context for subsequent steps.
Variable-length prefixes: Tool definitions and contextual documents are composed dynamically, preventing rigid hash pre-registration.

Without a tree-structured index, serving engines suffer from high memory fragmentation, frequent cache misses on branched sub-sequences, and redundant prefill computations.

Radix Tree Memory Organization and Longest Common Prefix Matching

A radix tree (also known as a compact prefix tree or Patricia trie) is a space-efficient data structure where edges are labeled with variable-length sequences rather than single elements. In SGLang's RadixAttention design, the serving runtime maintains a global radix tree on the host CPU that indexes all KV cache tensors residing in GPU memory.

Each node in the radix tree represents a discrete sequence of token IDs and stores references to non-contiguous physical memory pages allocated on the GPU (managed via PagedAttention memory blocks).

1. Longest Common Prefix Search

When an incoming request arrives with a sequence of prompt tokens, the engine executes a Longest Common Prefix (LCP) search:

Traversal begins at the root node.
The engine matches prompt token IDs against node edge labels.
Traversal continues down the tree until reaching a token where the prompt diverges from all existing child edges, or until all prompt tokens are matched.
The matched path yields the cached KV cache pages, allowing the GPU to skip prefill computation for the entire matched prefix.

2. Node Splitting and Insertion

When a prompt partially matches an existing edge label before diverging, the runtime performs an in-place node split:

The existing edge node is divided into two parts: the shared prefix sub-sequence and the original suffix sub-sequence.
The shared prefix becomes a parent node pointing to the corresponding subset of GPU KV pages.
The original suffix becomes one child branch.
A new child branch is created to hold the newly requested divergent token sequence.

During token generation (decode phase), newly generated tokens are appended to the active leaf node's memory pages. Once generation completes, the final sequence remains preserved in the radix tree for future requests to reuse.

Radix Tree KV Cache State:

         [Root: System Prompt (Tokens 1..512)]
                       |
        +--------------+--------------+
        |                             |
[User Query A (513..600)]    [User Query B (513..580)]
        |                             |
 [Response A (601..750)]       +------+------+
                               |             |
                         [Branch 1]     [Branch 2]

Tree-Structured Memory Management and LRU Eviction

Because GPU high-bandwidth memory (HBM) is finite, a prefix tree cannot grow indefinitely. However, applying standard flat Least Recently Used (LRU) eviction to a tree structure introduces a critical architectural challenge: topological dependency.

The Topological Invariant

In transformer autoregressive attention, the Key and Value representations at position N depend on the causal context of all preceding positions 1 through N-1. In a radix tree, child nodes are mathematically invalid without the KV tensors of all ancestor nodes along the root-to-leaf path.

If an eviction routine removes a parent node while retaining its children, the remaining child nodes become orphaned and unusable.

Reference Counting and State Locking

To maintain integrity while supporting concurrent requests, RadixAttention assigns two state tracking variables to every node:

ref_count: The number of currently executing requests whose active inference context includes this node.
last_accessed_time: A monotonic timestamp updated whenever a request traverses or appends to the node.

Nodes with ref_count > 0 are locked in GPU memory. They cannot be evicted, split, or modified by external workers. Nodes with ref_count == 0 represent completed requests whose KV caches remain in GPU memory speculatively, awaiting future prefix hits.

Leaf-First Cascading Eviction

When the GPU memory pool falls below a target headroom threshold, the cache manager executes tree-aware eviction:

The runtime maintains an eviction priority queue containing only unreferenced leaf nodes (ref_count == 0 and children_count == 0), keyed by last_accessed_time.
The oldest leaf node is popped, and its corresponding physical GPU pages are returned to the free memory allocator.
Once the leaf node is removed, its parent node is inspected. If the parent's ref_count is 0 and it now has zero remaining child nodes, the parent is promoted to the leaf eviction queue.
This leaf-first pruning ensures that root nodes (such as common system prompts or foundational few-shot contexts) remain cached the longest, as their high access frequency consistently updates their access timestamps.

Eviction Routine Lifecycle:

Active Request:   [Parent (ref=1)] ---> [Leaf A (ref=1)]   (Locked in VRAM)
Request Finished: [Parent (ref=0)] ---> [Leaf A (ref=0)]   (Eligible for eviction)
Memory Pressure:  Evict Leaf A first   ---> Parent becomes childless leaf
Next Cycle:       Evict Parent only if unreferenced and older than other leaves

Cache-Aware Request Scheduling

Even with an optimal radix tree data structure, cache hit rates in high-throughput serving systems depend heavily on the request scheduling policy. Under standard First-In-First-Out (FIFO) queueing, requests sharing a common prefix may arrive scattered across time. If the runtime processes disparate requests between them, the shared prefix may be evicted before subsequent matching requests reach the prefill phase.

To maximize locality, engines implement cache-aware scheduling algorithms:

Prefix Affinity Sorting: When continuous batching iterations select candidate requests from the waiting queue, the scheduler evaluates the LCP match length against current radix tree nodes.
Longest Shared Prefix First: Requests that match existing resident prefix nodes in GPU memory receive higher scheduling priority over requests requiring cold prefills, minimizing unnecessary evictions and maximize token throughput.
Batch Prefix Merging: If multiple incoming requests share an identical new prefix that is not yet in the cache, the scheduler groups them into the same prefill batch so the prefix is computed exactly once and branched simultaneously.

Architectural Comparison: RadixAttention vs. Hash-Based Block Caching

Production engines approach prefix caching through differing architectural trade-offs. The two dominant paradigms are SGLang's RadixAttention and vLLM's hash-based block prefix caching.

SGLang RadixAttention

Index Structure: Explicit CPU-side Radix Tree maintaining full hierarchical prefix paths.
Matching Granularity: Token-level exact sequence matching; node boundaries adapt dynamically via splitting.
Eviction Mechanism: Tree-structured cascading leaf-first LRU eviction.
Memory Overhead: Small CPU memory footprint for tree pointers and metadata; zero GPU memory waste from fixed-block padding.
Best Suited For: Complex multi-turn dialogues, agentic execution graphs, tree search algorithms, and structured JSON generation pipelines.

vLLM Hash-Based Block Prefix Caching

Index Structure: Flat hash table mapping hash digests of fixed-size token blocks (e.g., 16 or 32 tokens) to physical GPU block IDs.
Matching Granularity: Block-level matching. Tokens must fill an entire block before that block's hash can be matched or reused.
Eviction Mechanism: Reference-counted LRU queue over individual memory blocks.
Memory Overhead: Fixed hash table entries per block; sub-block tails cannot be cached until they cross the block boundary.
Best Suited For: Standard high-throughput HTTP serving endpoints with repetitive system prompts or static document context.

Distributed Extensions: Cluster-Level Radix Caching

In disaggregated and multi-node architectures like Mooncake, radix tree indexing is extended across host DRAM, local NVMe drives, and remote storage pools. The master coordinator uses a distributed prefix index to route requests to specific GPU worker nodes that already host the required prefix layers, avoiding costly network transfers of multi-gigabyte KV tensors.

Production Pitfalls and Mitigation Strategies

Deploying prefix-tree KV cache management in production environments requires handling several subtle operational pitfalls:

1. Tokenizer Boundary Inconsistencies

Byte-Pair Encoding (BPE) tokenizers can produce distinct token IDs for identical text substrings depending on leading whitespace or preceding punctuation. For example, " system" and "system" produce different token sequences. If prompt formatting templates introduce inconsistent whitespace, the radix tree cannot match the prefix.

Mitigation: Standardize prompt formatting pipelines upstream to ensure deterministic tokenization across all API clients.

2. Cache Thrashing Under Mixed Workloads

When a serving instance handles a mixture of long-context multi-turn chats and high-volume single-turn queries, single-turn requests can rapidly evict valuable multi-turn prefixes.

Mitigation: Configure dedicated memory pools or distinct worker pools for short stateless requests versus long-context agentic workloads. Alternatively, enforce minimum retention periods on high-priority system prefixes.

3. Multi-Tenant Privacy and Cache Isolation

In shared enterprise environments, caching KV activations across distinct tenants poses security and data isolation risks if prompts contain sensitive contextual data.

Mitigation: Tag radix tree nodes with cryptographic tenant identifiers (tenant_id). Enforce strict partition boundaries during LCP tree traversal so tenant A cannot match or execute against tenant B's cached activations.