RadixAttention: the tree (SGLang)

Run a customer-support agent on an H100 node. Every request opens with the same 512-token system prompt, then a 1,543-token few-shot block, then a per-user conversation. Enable prefix caching on both engines and the hit rates come out close, because on steady-state traffic both find the same shared prefixes. Then the queue backs up, eviction starts firing, and they stop behaving alike — not because one hashes better, but because one knows the shape of what it is caching and the other knows a flat set of 16-token blocks.

Here is the question that separates them. Your cache holds a 512-token system prompt that 400 live conversations share, and a 2,112-token RAG context that exactly one dead request ever used. You need 300 tokens of space. Which do you evict?

vLLM answers with a doubly-linked free queue ordered by the moment each block's reference count last hit zero. SGLang answers with a structural invariant: the system prompt is an interior node and is not in the candidate set at all while anything below it lives. This chapter is about that tree — what it is, what its four operations cost, what the scheduler does with it that vLLM's cannot, and what it costs you in return.

A radix tree is a trie in which every edge carries a sequence of symbols rather than a single one: chains of single-child nodes are collapsed into one edge. That is the only difference from a trie, and it is exactly why it fits KV prefixes. A KV cache does not care about individual tokens; it cares about runs of tokens that are always used together. A run with no divergence inside it is one edge. A divergence point is a node.

The sentence to remember: a node boundary is exactly a point where two requests stopped agreeing. Every token inside one edge is used by precisely the same set of requests. That is not true of a 16-token block, whose boundaries fall at arbitrary positions modulo 16.

Three requests against Llama-3-8B ($L=32$, $h_{kv}=8$, $d_h=128$, bf16), which costs $2 \cdot 32 \cdot 8 \cdot 128 \cdot 2 = 131{,}072$ B = 128 KiB of KV per token (§2.1). R1: 512-token system prompt S, 1,543-token few-shot block F, 96-token query. R2: same S and F, different 80-token query. R3: same S, then a 2,112-token RAG context and query of its own.

The tree stores $512 + 1543 + 96 + 80 + 2112 = 4{,}343$ tokens. Storing the three requests independently would take $2151 + 2135 + 2624 = 6{,}910$ tokens. The saving is 2,567 tokens — 321 MiB of HBM and 2,567 tokens of prefill that never runs. At the ~22,000 tok/s effective Llama-3-8B prefill rate derived in §1.4 (148.7 TFLOP per 8,192 tokens at an assumed 400 TFLOP/s achieved on H100 SXM, against §0.4's 989.4 TFLOP/s peak), that is 117 ms of GPU time avoided. Derived, not measured.

Everything the cache does is four operations on that tree, all in python/sglang/srt/mem_cache/radix_cache.py (863 lines at SHA 7d89325).

The node

class TreeNode:

    counter = 0

    def __init__(self, id: Optional[int] = None, priority: int = 0):
        self.children = defaultdict(TreeNode)
        self.parent: TreeNode = None
        self.key: RadixKey = None
        self.value: Optional[torch.Tensor] = None
        self.lock_ref = 0
        self.last_access_time = time.monotonic()
        self.creation_time = time.monotonic()

        self.hit_count = 0

Three fields carry the design. key is a RadixKey — the token sequence on the edge into this node, not a single token. value is a 1-D int64 tensor of KV slot indices, one per token of key; the KV bytes live in the pools of §2.2 and the tree holds only indices into them. lock_ref keeps in-flight requests' prefixes alive. The two timestamps and hit_count are there so eviction can be pluggable: python/sglang/srt/mem_cache/evict_policy.py:L16-L64 defines seven strategies over exactly those fields plus priority — LRU and MRU on ±last_access_time, FIFO and FILO on ±creation_time, LFU on (hit_count, last_access_time), and SLRU on a hit-count threshold.

RadixKey.child_key (radix_cache.py:L217-L229) keys children by the first page_size tokens of the child's edge, which makes descent an O(1) dict lookup. It also folds extra_key and cache_salt into that key, so identical tokens under different LoRA adapters or salts land in disjoint subtrees — the same idea as vLLM's extra_keys in the block hash, different carrier.

match_prefix — the longest-common-prefix walk

match_prefix (radix_cache.py:L417-L436) page-aligns the key, calls the helper below, and torch.cats the returned per-node index tensors into one. The walk itself is fourteen lines and is the heart of RadixAttention:

    def _match_prefix_helper(self, node: TreeNode, key: RadixKey):
        access_time = time.monotonic()
        node.last_access_time = access_time

        child_key = key.child_key(self.page_size)

        value = []
        while len(key) > 0 and child_key in node.children.keys():
            child = node.children[child_key]
            child.last_access_time = access_time
            prefix_len = child.key.match(key, page_size=self.page_size)
            if prefix_len < len(child.key):
                new_node = self._split_node(child.key, child, prefix_len)
                value.append(new_node.value)
                node = new_node
                break
            else:
                value.append(child.value)
                node = child
                key = key[prefix_len:]

                if len(key):
                    child_key = key.child_key(self.page_size)

Two things. First, child.last_access_time = access_time fires on every node along the path — one lookup refreshes the recency of the whole matched prefix, including interior nodes whose other branches were not touched. Second, and more important: a read mutates the tree. If the query diverges mid-edge, _split_node runs. Matching is not a pure operation. Hold that for the concurrency discussion.

The per-edge comparison is not a Python loop over tokens. RadixKey.match gallops:

    def match(self, other: RadixKey, page_size: int = 1) -> int:
        """Logical-unit prefix length shared with ``other``. Result is rounded down to ``page_size``."""
        self._check_compatible(other)
        t0, t1 = self.token_ids, other.token_ids
        assert type(t0) is type(t1), (type(t0), type(t1))
        n = min(len(t0), len(t1))

        # Exponential search for the first diverging token: gallop in doubling
        # windows (one C-level slice compare each), then binary-search the window
        # holding the divergence -- no per-token Python loop on long shared prefixes.
        matched_tokens = n
        lo = 0
        step = 1
        while lo < n:
            hi = lo + step if lo + step < n else n
            if t0[lo:hi] != t1[lo:hi]:
                while hi - lo > 1:
                    mid = (lo + hi) // 2
                    if t0[lo:mid] == t1[lo:mid]:
                        lo = mid
                    else:
                        hi = mid
                matched_tokens = lo
                break
            lo = hi
            step *= 2
        # ...
        matched_tokens = min(matched_tokens, len(self), len(other))
        if page_size == 1:
            return matched_tokens
        return (matched_tokens // page_size) * page_size

For an edge of m tokens, the galloping/binary search uses O(log m) Python-level slice comparisons. Each slice can copy or compare many elements; this is not O(log m) total byte work, and repeated comparisons can cost O(m log m) in an unfavorable case. Compare end-to-end lookup profiles against hashing, including key construction, allocation, and cache warmth, rather than equating one C-level call with constant work.

_split_node — the operation that makes it a radix tree

    def _split_node(self, key: RadixKey, child: TreeNode, split_len: int):
        # new_node -> child
        # New node inherits child's priority (represents shared prefix)
        new_node = TreeNode(priority=child.priority)
        new_node.hit_count = child.hit_count
        new_node.children = {key[split_len:].child_key(self.page_size): child}
        new_node.parent = child.parent
        new_node.lock_ref = child.lock_ref
        new_node.key = child.key[:split_len]
        new_node.value = child.value[:split_len].clone()
        child.parent = new_node
        child.key = child.key[split_len:]
        child.value = child.value[split_len:].clone()
        new_node.parent.children[key.child_key(self.page_size)] = new_node
        # ...
        return new_node

Twelve lines of pointer surgery plus two tensor clones. new_node.lock_ref = child.lock_ref matters: the new parent inherits the lock count, so a request already standing on the deep node keeps a consistent chain of locks to the root. The clones are of the index tensor (8 B/token), not the KV (131,072 B/token): splitting a 2,151-token edge copies 17 KB, not 269 MiB. No KV is moved, ever — that is what makes the tree affordable.

insert

_insert_helper is _match_prefix_helper with a tail: same walk, same splits, and when the key runs out of matching tree it hangs a fresh node.

        total_prefix_length = 0
        while len(key) > 0 and child_key in node.children.keys():
            node = node.children[child_key]
            node.last_access_time = access_time
            prefix_len = node.key.match(key, page_size=self.page_size)
            total_prefix_length += prefix_len
            key = key[prefix_len:]
            value = value[prefix_len:]

            if prefix_len < len(node.key):
                new_node = self._split_node(node.key, node, prefix_len)
                new_node.priority = max(new_node.priority, priority)
                self._inc_hit_count(new_node, chunked)
                node = new_node
            else:
                node.priority = max(node.priority, priority)
                self._inc_hit_count(node, chunked)
            if len(key):
                child_key = key.child_key(self.page_size)

        if len(key):
            new_node = TreeNode(priority=priority)
            new_node.parent = node
            new_node.key = key
            new_node.value = value.clone()
            self._inc_hit_count(new_node, chunked)
            node.children[child_key] = new_node
            self.evictable_size_ += len(key)
            self._update_leaf_status(node)
            self._update_leaf_status(new_node)
            # Hash will be computed lazily during event emission
            self.kv_events.record_store(new_node)
            node = new_node
        return total_prefix_length, node

insert returns total_prefix_length, which the caller uses to free the slots it just discovered were duplicates: in cache_finished_req the request's freshly written KV indices below prefix_len go straight back to the allocator (radix_cache.py:L491-L509). Deduplication happens at insert time, not allocation time.

Complexity, stated

The row worth staring at is evict: leaves = list(self.evictable_leaves) then heapq.heapify (radix_cache.py:L599-L603) rebuilds the heap from scratch on every call. Under sustained pressure with a wide tree, this is the one operation whose cost grows with the size of the cache rather than the size of the request.

Figure 2 is the same three requests as Figure 1, under a flat block-hash map with $B = 16$.

Both find the shared prefix; the map is not wrong. What it lacks is any representation of the three facts the tree makes free:

Put a number on case 1. A conversation whose context reaches 4,300 tokens by turn 4: turn 5 adds a 300-token reply and a 120-token user message. Assuming the reply KV was retained, the tree matches 4600 and prefills 120; cold it would prefill 4720. Saving: 4,600 $/$ 22,000 tok/s $\approx$ 209 ms per turn (derived). Both engines get this; the tree gets it in one descent.

Where vLLM's ordering actually differs

Be precise, because it is easy to overstate. vLLM's free queue is a genuine LRU: a matched block is removed by touch and re-appended at the back when released, so queue position tracks last use. And free_blocks segregates hashed from unhashed blocks so never-matchable ones are reused first:

        # Identify blocks with hash (LRU cache) and without it (never match APC)
        blocks_to_evict_last = []
        blocks_to_evict_first = []
        for block in ordered_blocks:
            block.ref_cnt -= 1
            if block.ref_cnt == 0 and not block.is_null:
                if block.block_hash is None or not self.enable_caching:
                    # LIFO reuse of non-cached blocks for better GPU locality.
                    blocks_to_evict_first.append(block)
                else:
                    # FIFO reuse of cached blocks for LRU eviction behavior.
                    blocks_to_evict_last.append(block)

        # Blocks to reuse first are prepended to the front of the free queue.
        self.free_block_queue.prepend_n(blocks_to_evict_first)
        # Blocks to reuse last are appended to the end of the free queue.
        self.free_block_queue.append_n(blocks_to_evict_last)

The genuine difference is what happens if that invariant breaks. vLLM's lookup stops dead at the first missing block — the code says so:

        # Phase 1: longest run of cached full blocks from the start. A missing
        # block implies every later block misses too (chained hashes).
        for block_hash in itertools.islice(full_block_hashes, max_length // block_size):
            cached_block = block_pool.get_cached_block(block_hash, kv_cache_group_ids)
            if not cached_block:
                break
            for computed, cached in zip(computed_blocks, cached_block):
                computed.append(cached)

Any resident block whose ancestor was evicted is unreachable: it occupies HBM and can never produce a hit until the ancestor is repopulated. Nothing in BlockPool prevents that state — the free-ordering discipline at the call sites does. In SGLang it is impossible by construction, because _update_leaf_status refuses to put a node in the candidate set while it has a non-evicted child:

    def _update_leaf_status(self, node: TreeNode):
        if node.evicted or node.lock_ref > 0:
            if node in self.evictable_leaves:
                self.evictable_leaves.remove(node)
            return

        for child in node.children.values():
            if not child.evicted:
                if node in self.evictable_leaves:
                    self.evictable_leaves.remove(node)
                return

        if node not in self.evictable_leaves:
            self.evictable_leaves.add(node)

What the tree costs

Four honest costs:

• Pointer chasing and Python objects. A TreeNode carries fourteen attributes plus a defaultdict plus a torch tensor. At page_size=1 with many short branches you accumulate a lot of them. Hundreds of bytes per node against 128 KiB per token of KV is negligible in bytes — but every node is GIL-bound work on the scheduler thread.
• More bookkeeping per token. inc_lock_ref / dec_lock_ref walk to the root on every admission and completion, adjusting evictable_size_, protected_size_ and the leaf set at each hop. vLLM's equivalent is block.ref_cnt += 1 in a loop.
• Split-on-read. match_prefix mutates. There is no lock-free read path, which is why the structure is confined to the single-threaded scheduler loop.
• A harder concurrency story. A hash-map lookup is a pure read and can be sharded; a radix walk with edge splitting cannot. radix_cache_cpp exists partly to move this off the interpreter.

SGLang's tree granularity is page_size, and the default is 1:

def _page_size_default(view: Any) -> dict:
    if view.page_size is not None:
        return {}
    # ...
    if is_hip() and envs.SGLANG_AITER_KV_CACHE_LAYOUT.get().lower() == "vectorized_5d":
        logger.info(
            "Setting page_size=64 as default for "
            "SGLANG_AITER_KV_CACHE_LAYOUT=vectorized_5d."
        )
        return {"page_size": 64}
    if not is_musa():
        return {"page_size": 1}
    return {"page_size": 64}

vLLM's is CacheConfig.DEFAULT_BLOCK_SIZE = 16 (vllm/config/cache.py:L59, applied at L285-L286). Both round the match down: SGLang in RadixKey.match's final (matched_tokens // page_size) * page_size and again in page_aligned (radix_cache.py:L150-L154), vLLM by iterating whole blocks.

So on a CUDA default deployment SGLang matches at token granularity and vLLM at 16-token granularity. The loss is at most $B - 1 = 15$ tokens per divergence point. On our workload the shared prefix is 2,055 tokens; vLLM matches 2,048 and re-prefills 7 — $7/22{,}000 = 0.32$ ms. The worst case, 15 tokens, is 0.68 ms.

The granularity that does matter is eviction granularity. SGLang evicts a whole node — a variable-length run whose boundaries are the divergence points, so every token in it has the same set of dependants. vLLM evicts one 16-token block whose boundaries fall wherever position $\bmod\ 16$ says. Evicting node E in Figure 1 releases 2,112 tokens (264 MiB) in one heap pop and one free_segment; the equivalent in vLLM is 132 separate poplefts, and nothing guarantees they are the 132 the tree would have chosen.

    def evict(self, params: EvictParams) -> EvictResult:
        if self.disable:
            return EvictResult()

        start_time = time.perf_counter()
        num_tokens = params.num_tokens
        leaves = list(self.evictable_leaves)
        eviction_heap = [
            (self.eviction_strategy.get_priority(node), node) for node in leaves
        ]
        heapq.heapify(eviction_heap)

        num_evicted = 0
        while num_evicted < num_tokens and len(eviction_heap):
            _priority, x = heapq.heappop(eviction_heap)

            # Tree values are page-aligned copies of a kv row: page-exact segment.
            self.token_to_kv_pool_allocator.free_segment(x.value, start_pos=0)
            num_evicted += len(x.value)
            self._delete_leaf(x)

            if len(x.parent.children) == 0 and x.parent.lock_ref == 0:
                new_priority = self.eviction_strategy.get_priority(x.parent)
                heapq.heappush(eviction_heap, (new_priority, x.parent))

            self.kv_events.record_remove(x)

Three properties fall out. The candidate set is only leaves. A parent joins the heap the instant it becomes an unlocked leaf, so eviction cascades up a dead branch within one call. And the ordering key is not hard-coded — self.eviction_strategy.get_priority(node) dispatches to one of seven strategies:

class LRUStrategy(EvictionStrategy):
    def get_priority(self, node: TreeNode) -> float:
        return node.last_access_time


class LFUStrategy(EvictionStrategy):
    def get_priority(self, node: TreeNode) -> Tuple[int, float]:
        return (node.hit_count, node.last_access_time)


class FIFOStrategy(EvictionStrategy):
    def get_priority(self, node: TreeNode) -> float:
        return node.creation_time

# ... MRUStrategy and FILOStrategy negate the same two fields ...

class PriorityStrategy(EvictionStrategy):
    """Priority-aware eviction: lower priority values evicted first, then LRU within same priority."""

    def get_priority(self, node: TreeNode) -> Tuple[int, float]:
        # Return (priority, last_access_time) so lower priority nodes are evicted first
        return (node.priority, node.last_access_time)

Plus SLRUStrategy, a segmented LRU protecting nodes with hit_count >= 2. Selected by --radix-eviction-policy, default "lru" (python/sglang/srt/server_args.py:L934-L947). vLLM has one policy and no flag: the free queue's order.

Locking

    def inc_lock_ref(self, node: TreeNode) -> IncLockRefResult:
        if self.disable:
            return IncLockRefResult(delta=0)

        delta = 0
        while node != self.root_node:
            if node.lock_ref == 0:
                self.evictable_size_ -= len(node.key)
                self.protected_size_ += len(node.key)
                delta -= len(node.key)
            node.lock_ref += 1
            self._update_leaf_status(node)
            node = node.parent
        return IncLockRefResult(delta=delta)

One call locks the whole path to the root and moves those tokens from the evictable budget to the protected one, which is what makes the scheduler's admission arithmetic correct: evictable_size() is exactly the memory eviction can still reclaim. The root carries a permanent lock_ref = 1 (radix_cache.py:L360), so the loop always terminates.

The payoff: R2's 2,055-token prefix (257 MiB) is protected by a single inc_lock_ref, and the 400-conversation system prompt from the opening question is node A — an interior node with a live child, therefore not a candidate at any price. vLLM protects the same block by reference counting, which also works; what vLLM cannot express is "this block has cached descendants that would become unreachable".

This is the part with no vLLM counterpart. SGLang's SchedulePolicy holds a reference to the tree and sorts the waiting queue by how much of it each request will hit:

class CacheAwarePolicy(Enum):
    """Scheduling policies that are aware of the tree cache."""

    LPM = "lpm"  # longest prefix match
    DFS_WEIGHT = "dfs-weight"  # depth-first search weighting


class CacheAgnosticPolicy(Enum):
    """Scheduling policies that are not aware of the tree cache."""

    FCFS = "fcfs"  # first come first serve
    LOF = "lof"  # longest output first
    RANDOM = "random"
    ROUTING_KEY = "routing-key"  # prioritize by routing key frequency in running batch

vLLM's complete set, for contrast, is two members:

class SchedulingPolicy(Enum):
    """Enum for scheduling policies."""

    FCFS = "fcfs"
    PRIORITY = "priority"

LPM's sort is trivial once the matches exist:

    @staticmethod
    def _sort_by_longest_prefix(
        waiting_queue: List[Req], temporary_deprioritized: Set[int]
    ) -> None:
        """Sorts the waiting queue based on the longest prefix match."""
        waiting_queue.sort(
            key=lambda r: (
                -r.num_matched_prefix_tokens
                if r.rid not in temporary_deprioritized
                else float("inf")
            )
        )

The interesting machinery is temporary_deprioritized. _compute_prefix_matches builds a second, throwaway radix tree over the waiting queue itself and uses it to detect requests that will collide on a prefix that is not cached yet:

            # NOTE(sang): This logic is for in-batch prefix caching;
            # If there are more than 1 request that have small matching prefix from
            # existing cache, but all those requests share the same prefix, we prefer
            # to schedule only one of them so that we can increase the cache hit rate.
            # ...
            if len(r.prefix_indices) <= IN_BATCH_PREFIX_CACHING_CHECK_THRESHOLD:
                match_result = self.waiting_queue_radix_tree.match_prefix(
                    MatchPrefixParams(
                        key=RadixKey(
                            token_ids=prefix_ids,
                            extra_key=extra_key,
                            cache_salt=cache_salt,
                        )
                    )
                )
                # ...
                in_batch_matching_prefixes = match_result.device_indices
                if (
                    len(in_batch_matching_prefixes)
                    >= IN_BATCH_PREFIX_CACHING_DEPRIORITIZE_THRESHOLD
                ):
                    temporary_deprioritized.add(r.rid)

Work the example. Sixty-four requests arrive together sharing a cold 2,000-token prefix. Admit them all at once and every one prefills 2,000 tokens, because none has finished so none has inserted anything: $64 \times 2000 = 128{,}000$ tokens. Deprioritize 63, let the first populate the tree, and the other 63 hit — saving 126,000 tokens $/$ 22,000 tok/s $\approx$ 5.7 s of H100 prefill (derived). A scratch tree makes this convenient, but a hash-based shared-prefix index can also detect overlap among requests none of which are in the cache yet; the cheapest way is a scratch radix tree, which is exactly what RadixCache.create_simulated() builds (python/sglang/srt/managers/schedule_policy.py:L235).

The coupling is not free, and the code admits it:

    def _determine_active_policy(self, waiting_queue: List[Req]) -> Policy:
        if self.policy == CacheAwarePolicy.LPM and len(waiting_queue) > 128:
            # Turn off the expensive prefix matching and sorting when the #queue is large.
            return CacheAgnosticPolicy.FCFS
        return self.policy

LPM does a full match_prefix for every waiting request on every scheduling round. Past 128 queued requests it disables itself. Note also that the shipped default is schedule_policy = "fcfs" (python/sglang/srt/server_args.py:L843-L858), so LPM is opt-in: --schedule-policy lpm.

§1.4 established this asymmetry; it belongs in the comparison table, so verify it here. On retraction SGLang calls:

    # TODO (csy): for preempted requests, we may want to insert into the tree
    release_kv_cache(req, tree_cache, is_insert=False)
    # NOTE(lsyin): we should use the newly evictable memory instantly.
    num_tokens = remaing_req_count * envs.SGLANG_RETRACT_DECODE_STEPS.get()
    evict_from_tree_cache(tree_cache, num_tokens)

The is_insert=False flag skips insertion of the newly computed suffix. It does not mean existing canonical tree nodes or borrowed shared prefix slots are erased. Release and later eviction must respect ownership and locks. The canonical RadixCache excerpt illustrates the algorithm; the configured default may be UnifiedRadixCache, as the variant table explains.

Neither the quoted release flag nor free-queue ordering proves a 372 ms versus 3.7 ms engine gap. Recompute cost depends on the still-indexed contiguous prefix, victim ownership, eviction pressure, and warm-suffix attention. Measure those quantities on matched workloads before comparing engines.

At SHA 7d89325 there are six tree implementations plus the no-op, and the layout is moving fast: python/sglang/srt/mem_cache/README.md:L40-L45 says the per-model variants "are converging onto the Unified Radix Cache".

ChunkCache is the control: the same BasePrefixCache interface with every operation stubbed to nothing.

    def match_prefix(self, params: MatchPrefixParams) -> MatchResult:
        return MatchResult(
            device_indices=torch.empty((0,), dtype=torch.int64),
            last_device_node=None,
            last_host_node=None,
            best_match_node=None,
        )

    def insert(self, params: InsertParams) -> InsertResult:
        # ChunkCache does not support prefix caching, so insert is a no-op
        return InsertResult(prefix_len=0)

reset, match_prefix, cache_finished_req, cache_unfinished_req, evict, inc_lock_ref, dec_lock_ref are the seven abstract methods of BasePrefixCache (python/sglang/srt/mem_cache/base_prefix_cache.py:L273-L336). Every row of the table above is a different answer to the same seven questions.

R1 has finished; the tree is root -> [S+F+q1: 2151 tokens], one node. R2 arrives with S + F + q2. Follow it through the real call path.

1. SchedulePolicy.calc_priority (schedule_policy.py:L237) → _compute_prefix_matches → match_prefix_for_req (schedule_policy.py:L138-L197), which wraps the token ids in a RadixKey carrying req.extra_key and req.cache_salt.
2. RadixCache.match_prefix → page_aligned(1) is a no-op → _match_prefix_helper(root, key).
3. First hop: R2's first token equals R1's, so the single child is found. child.key.match(key, page_size=1) gallops — the arrays agree for 2,055 tokens (S + F) and diverge at the query. Returns 2055.
4. prefix_len=2055 < len(child.key)=2151, so _split_node runs. A new node takes the first 2,055 indices; the old node keeps the last 96 and becomes its child. Two .clone()s move $2151 \times 8 = 17$ KB of int64. No KV moves.
5. The helper breaks and returns ([new_node.value], new_node); match_prefix torch.cats and returns 2,055 device indices. match_prefix_for_req writes req.prefix_indices, req.last_node, req.num_matched_prefix_tokens = 2055.
6. _sort_by_longest_prefix sorts R2 ahead of anything with a shorter match.
7. Admission: PrefillAdder._req_inc_lock_ref (schedule_policy.py:L957-L963) walks to the root. 2,055 tokens (257 MiB) move from evictable_size_ to protected_size_.
8. Only 80 tokens are prefilled. Derived saving against cold: $2055/22000 = 93$ ms.
9. R2 finishes. release_kv_cache(..., is_insert=True) → cache_finished_req → insert, which walks back down, finds total_prefix_length = 2055, hangs an 80-token node, and preserves the 2,055 already shared slots; duplicate freeing applies only if independently allocated overlapping slots actually exist. dec_lock_ref unwinds the locks; _update_leaf_status adds the new node to evictable_leaves.

The tree is disabled and you did not ask for it. disable_radix_cache is forced to True from at least six places in server_args.py (lines 3877, 3927, 4826, 6023, 6114, 8338) as a side effect of other flags. If your hit rate is flat zero, check the resolved server args first. The tell in code is ChunkCache: is_chunk_cache() returns True and every match returns empty.

LPM silently turns itself off. Past 128 waiting requests _determine_active_policy returns FCFS, with no log line. Hit rate degrades exactly at the load where you most wanted the policy. Deliberate — the sort is $O(Q)$ full matches — but invisible from outside.

cache_salt and extra_key partition the tree. Folded into child_key, so identical tokens under different salts never share a node. Deliberate, and an efficient way to drive your hit rate to zero if a client sets a per-request salt. RadixKey._check_compatible raises ValueError: RadixKey operations require matching extra_key if the two get crossed.

Assertion on index-length mismatch. cache_unfinished_req asserts len(new_indices) == len(radix_key) (radix_cache.py:L555-L557). The comment below it names the trap: at page_size > 1 the partial tail page is in req.prefix_indices but not in the tree, and cache_protected_len exists solely so that tail is freed later. Writing a new cache variant, this is the invariant you break first.

Preemption can lose reusable suffix work. Retraction may release newly computed KV without inserting it, while previously indexed shared prefixes remain. Log the surviving prefix length and recomputed token count; do not assume every retraction starts from zero.

Debugging tool. tree.pretty_print() (radix_cache.py:L586-L588) prints edge length, the first ten token ids, and r=lock_ref per node, and asserts each dict key equals the child's recomputed child_key — a cheap structural check.

The tree runs standalone. radix_cache.py has a __main__ block that builds one with no GPU:

cd ~/Documents/other_git_repos/sglang
python -m sglang.srt.mem_cache.radix_cache

It inserts [1,2,3], [1,2,3], [1,2,4,5], [1,2,4,5,6,7], [8,9,10,11,12], prints the tree, and matches [1,2,3,13,14] (radix_cache.py:L849-L863). Add inserts and watch _split_node fire — inserting [1,2,4,5] is what splits [1,2,3] into [1,2] -> [3].

Then run the server four ways and compare the cache-hit gauge:

# Baseline: FCFS, default page_size=1, LRU
python -m sglang.launch_server --model-path meta-llama/Meta-Llama-3-8B-Instruct --enable-metrics

# Cache-aware admission + segmented LRU
python -m sglang.launch_server --model-path meta-llama/Meta-Llama-3-8B-Instruct \
  --schedule-policy lpm --radix-eviction-policy slru --enable-metrics

# Coarsen the tree to vLLM's granularity and see how little changes
python -m sglang.launch_server --model-path meta-llama/Meta-Llama-3-8B-Instruct \
  --page-size 16 --enable-metrics

# The control: no tree at all (ChunkCache)
python -m sglang.launch_server --model-path meta-llama/Meta-Llama-3-8B-Instruct \
  --disable-radix-cache --enable-metrics

Drive all four with a few-shot workload where many prompts share a long preamble. The prediction from this chapter: --page-size 16 costs you almost nothing, --schedule-policy lpm helps most when many similar requests arrive together, and --disable-radix-cache is the cliff.

• Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs (arXiv:2312.07104) — the paper that introduced RadixAttention. It reports multi-fold end-to-end throughput improvements (up to 6.4× on its own benchmark suite) against the baselines and configurations described there. Published claim, not reproduced here; treat the per-benchmark configuration in the paper as part of the claim.
• sgl-project/sglang#25371 — the issue specifying the current mem_cache/ layout. Read it before navigating the directory.
• sgl-project/sglang#20415 — the Unified Radix Cache convergence tracking issue: where all the variants above are heading.
• python/sglang/srt/mem_cache/README.md and python/sglang/srt/mem_cache/unified_cache/components/README.md — in-tree, and better than most external write-ups.
• Morrison, PATRICIA — Practical Algorithm To Retrieve Information Coded In Alphanumeric, JACM 1968 — the original compressed-trie paper. The structure is 58 years old; the application is new.
• §2.3 for the vLLM half of this pair, §2.6 for HiCache's tiers, and §13.1, which reuses the head-to-head table above.