vLLM vs SGLang Prefix Caching: Hash Blocks vs Radix Tree

How vLLM and SGLang Implement Prefix Caching Differently: Hash vs. Radix Tree Trade-offs

There is no shortage of writing that explains why prefix cache hit rates fall short of theoretical maximums from an operational perspective — eviction policy, request distribution, hash collisions, and so on. But the ceiling on hit rate is determined at a lower level: how cache keys are constructed, and whether the data structure supports partial matching. These choices produce different hit rates on identical workloads. vLLM and SGLang made different implementation choices, and the conditions under which those differences surface in production are equally distinct.

How Cache Keys Are Constructed

vLLM's Automatic Prefix Caching (APC) splits token sequences into fixed-size blocks and computes a hash for each block. The default block size is 16 tokens. Hashes are computed in a chained fashion — the hash input for the current block includes the hash of the previous block, so the same tokens at different positions produce different hashes.

# vllm/v1/core/kv_cache_utils.py
def hash_block_tokens(
    hash_function: Callable[[Any], bytes],
    parent_block_hash: BlockHash | None,
    curr_block_token_ids: Sequence[int],
    extra_keys: tuple[Any, ...] | None = None,
) -> BlockHash:
    if not parent_block_hash:
        parent_block_hash = NONE_HASH
    curr_block_token_ids_tuple = tuple(curr_block_token_ids)
    return BlockHash(
        hash_function((parent_block_hash, curr_block_token_ids_tuple, extra_keys))
    )

extra_keys carries the LoRA ID, multimodal input hash, and cache_salt (for multi-tenancy isolation). Starting with v0.11, the default hash function is SHA-256, with a computation cost on the order of 100–200 ns per token — roughly 6 ms for a 50k-token sequence.

This design introduces a fundamental constraint: vLLM only caches a block when it is completely full. Partial blocks are never cached.

Why Partial Matching Is Impossible

Consider a block size of 16 tokens and a system prompt of 17 tokens. The first block (tokens 1–16) gets cached. The second block contains only token 17 and is not full, so it is never cached. Even if the next request shares the same system prompt, only the first 16 tokens are reused; the 17th token is recomputed every time.

When the prefix length is not a multiple of the block size, the number of tokens lost is prefix_len % block_size. A 49-token prefix caches 48 tokens and discards 1. A 33-token prefix caches 32 and discards 1. These numbers look small, but they mean many requests are redundantly recomputing the tail of the same shared prefix on every call.

The problem becomes material on workloads that mix few-shot examples of varying lengths. If one few-shot set is 37 tokens, the shared prefix is misaligned with block boundaries and the hash matching consistently misses the boundary. Theoretically, 37 tokens could be shared; in practice, only 32 tokens (2 blocks × 16) are matched. This is one of the structural reasons why observed hit rates are lower than theory predicts.

What Radix Tree Solves Differently

SGLang's Radix Attention stores the KV cache in a radix tree (a compressed trie). Each node in the tree represents a common token prefix along its edge. When a new request arrives, match_prefix walks down from the root, comparing tokens one by one, and stops at the first mismatch. The KV cache up to the common prefix is reused; only the remaining tokens are computed from scratch.

When a partial mismatch occurs, _split_node is called. If an existing node and a new request diverge partway through, the common portion becomes a new intermediate node, and the diverging tails become its children.

# sglang/python/sglang/srt/mem_cache/radix_cache.py
def _split_node(self, key, child, split_len):
    new_node = TreeNode(priority=child.priority)
    new_node.key = child.key[:split_len]
    new_node.value = child.value[:split_len].clone()
    child.key = child.key[split_len:]
    child.value = child.value[split_len:].clone()
    # new_node is inserted as the parent of child

In the 49-token example above, the radix tree stores all 49 tokens as a path in the tree and matches all 49 on the next request. Block boundaries do not truncate the shared prefix.

Lookup complexity is O(L/p), where L is the shared prefix length and p is the page size. Internally, exponential search followed by binary search is used to find the mismatch point, reducing the number of comparisons. Insertion is also O(L/p); deletion (LRU eviction) traverses upward from leaves and cleans up parents, so it is O(depth).

The radix tree's advantage is most pronounced on workloads with multiple mixed templates. When one set of requests shares system prompt A-B-C and another shares A-B-D, the tree keeps A-B as a single shared node and branches C and D as separate children. A hash map cannot represent this shared structure.

vLLM's Evolution: What Changed and What Didn't

In the vLLM v1 architecture, the fundamental cache unit remains the block. A KVCacheBlock holds a block_id, ref_cnt, and _block_hash. The block pool is pre-allocated at startup to eliminate runtime Python object creation, and the free block queue is a doubly-linked list supporting O(1) operations.

# vllm/v1/core/kv_cache_utils.py
@dataclass(slots=True)
class KVCacheBlock:
    block_id: int
    ref_cnt: int = 0
    _block_hash: BlockHashWithGroupId | None = None
    _block_hash_num_tokens: int | None = None
    prev_free_block: "KVCacheBlock | None" = None
    next_free_block: "KVCacheBlock | None" = None

The block-level chained hash structure is preserved in v1. The constraint that a block must be completely full before it is cached remains in place. The structural hit-rate loss on workloads where prefix lengths do not align to block boundaries is still present.

The enable-prefix-caching flag makes APC simple to enable operationally.

vllm serve <model> --enable-prefix-caching

Once enabled, vLLM exposes Prometheus metrics including gpu_cache_usage_perc and prefix cache hit rate metrics for monitoring actual cache efficiency. SGLang exposes sglang:cache_hit_rate directly.

Workload Comparison

The SGLang paper (arXiv:2312.07104) reports up to 6.4× throughput improvement and 3.7× latency reduction for Radix Attention on synthetic workloads with a high system prompt sharing ratio. The gap narrows as the sharing ratio decreases.

When the system prompt length is an exact multiple of the block size, a hash-based approach achieves the same hit rate as a radix tree. If you are running vLLM APC and want to improve hit rate, simply padding the system prompt to a multiple of 16 (or whatever block size is configured) can make a meaningful difference — worth checking before switching data structures.

The Cost of Radix Tree

The tree structure carries higher management complexity. LRU eviction must merge parent nodes with only one remaining child while walking up from leaves, and in high-concurrency environments, the global lock on tree insertions, splits, and removals can show up in tail latency. SGLang protects KV cache in active use by excluding nodes where lock_ref > 0 from eviction, but this reduces the pool of evictable nodes as a side effect.

On the memory side, tree node count can grow into the thousands on high-diversity workloads. Each node holds a token key tensor, a KV index tensor, and metadata (access timestamp, hit_count, lock_ref, etc.), so CPU memory overhead accumulates. Even at a few tens of bytes of metadata per node, ten thousand processed requests adds up to several megabytes in aggregate.

In deployments with low request diversity and a single fixed system prompt, a hash-based approach delivers the same hit rate with no overhead. On workloads with complex prefix sharing patterns, multiple system prompt templates, and heavy multi-turn conversation traffic, a radix tree raises the hit-rate ceiling itself by enabling arbitrary-length partial matching.