RadixAttention and the memory pools, in code

python/sglang/srt/mem_cache/ is 126 Python files and 62,482 lines, forty of them at the directory root. Eleven classes implement BasePrefixCache directly or through RadixCache, two more subclass ChunkCache, and every name sounds like the one you want: RadixCache, HiRadixCache, SWARadixCache, MambaRadixCache, PureSWARadixCache, RadixCacheCpp, LMCRadixCache, FlexKVRadixCache, UnifiedRadixCache.

Three of those are dead at this SHA. grep -rn "HiRadixCache(" --include="*.py" . returns two hits: the class statement at hiradix_cache.py:L77, and one unit test — 2,022 lines nothing in srt/ constructs. MambaRadixCache( and SWARadixCache( are constructed only under test/registered/unit/mem_cache/ and nowhere in srt/: another 2,867 lines. And RadixCache is constructed in exactly one place, which is not the serving path:

    def create_simulated(
        self,
        disable: bool = False,
        mock_allocator: Optional[Any] = None,
        page_size: int = 1,
        enable_kv_cache_events: bool = False,
    ) -> RadixCache:
        """Init a radix cache without memory pools for simulation purpose."""
        params = CacheInitParams(
            disable=disable,
            req_to_token_pool=None,
            token_to_kv_pool_allocator=mock_allocator,
            page_size=page_size,
            enable_kv_cache_events=enable_kv_cache_events,
        )
        return RadixCache(params)

Its one caller in srt/ is python/sglang/srt/managers/schedule_policy.py:L235 — self.waiting_queue_radix_tree = RadixCache.create_simulated(). The earlier implementation survives at this SHA as a pool-free simulator the scheduler uses to sort its waiting queue by longest prefix match. It caches no KV.

So the question this chapter answers is not "how does a radix tree work" — §2.4 owns that, and everything it says about the compressed trie, edge splitting, lock_ref, and tree-aware LRU still holds. The question is which files do I open, in what order, and what is the control flow between them.

The directory has one honest map and it is checked in. mem_cache/README.md states the layering, and — unusually for a README — it is accurate at this SHA:

| Layer | Cares about | In -> Out |
|---|---|---|
| `allocation.py` | per-batch allocation policy | `batch` -> `out_cache_loc` |
| `hybrid_cache/` | per-layer routing across pools | `layer_id` -> pool |
| `allocator/` | which slots are free | `need_size` -> `indices` |
| `pool/` | physical KV / SSM state layout | `(layer_id, indices)` <-> tensor |
| `pool_host/` | host mirror + H2D/D2H | `device_indices` <-> `host_indices` |
| `storage/` | L3 backends (file, NIXL, HF3FS, Mooncake, ...) | hash -> bytes |
| radix cache | what to keep and what to evict | token prefix -> node |

Read the last row twice. The radix cache is not a layer in that stack; it is a separate axis beside it. The stack answers "where are the bytes and who hands out slots"; the tree answers "what is worth keeping". They meet at exactly one type — a tensor of int64 slot indices.

The README states the convergence explicitly at python/sglang/srt/mem_cache/README.md:L38-L45: the per-model variants "are converging onto the Unified Radix Cache", tracked as sglang issue #20415. That is why the dead files are still there — they are the pre-image of a merge that has already landed on the default path.

Four of those must actually be read: registry.py (258 lines, whole), base_prefix_cache.py (437 lines, the class at the bottom), unified_cache/unified_tree_core.py (2,529 lines — match_prefix, the insert walk, _split_node, sanity_check), and ReqToTokenPool (33 lines out of memory_pool.py's 5,059). The rest is on demand.

BasePrefixCache declares 44 methods, of which exactly seven carry @abstractmethod. Those seven are the entire obligation; five of them are here:

    @abstractmethod
    def cache_finished_req(self, req: Req, is_insert: bool = True, **kwargs):
        pass

    @abstractmethod
    def cache_unfinished_req(self, req: Req, **kwargs):
        pass

    @abstractmethod
    def evict(self, params: EvictParams) -> EvictResult:
        pass

    @abstractmethod
    def inc_lock_ref(self, node: Any) -> IncLockRefResult:
        pass

    @abstractmethod
    def dec_lock_ref(
        self, node: Any, params: Optional[DecLockRefParams] = None
    ) -> DecLockRefResult:
        pass

Plus reset and match_prefix at python/sglang/srt/mem_cache/base_prefix_cache.py:L273-L279. Who calls each is the useful half:

Two things there. evict is demand-driven: evict_from_tree_cache at python/sglang/srt/mem_cache/common.py:L114-L138 evicts only num_tokens - available_size, and no background thread evicts anything. And the scheduler never touches a node — it holds opaque handles, which for UnifiedRadixCache are integers (resolve_node_handle and root_node_handle, python/sglang/srt/mem_cache/base_prefix_cache.py:L284-L297, both carrying a TODO to remove the indirection).

The return value of a match is a NamedTuple with eleven fields, and reading it tells you the whole feature surface the tree has grown:

    device_indices: torch.Tensor
    last_device_node: Any
    last_host_node: Any
    best_match_node: Any
    host_hit_length: int = 0
    swa_host_hit_length: int = 0
    mamba_host_hit_length: int = 0
    mamba_branching_seqlen: Optional[int] = None
    cache_protected_len: Optional[int] = None
    full_kv_hit_length: int = 0
    # Actions the Controller applies: CacheActions itself, ComponentActions routed to the owning component.
    cache_actions: Sequence[CacheAction | ComponentAction] = ()

Three node handles, not one. last_device_node is what the scheduler locks and what prefix_indices corresponds to; last_host_node anchors L3 storage prefetch; best_match_node is the deepest node all components agreed on and anchors L2 load-back. Without HiCache all three are the same node; with it they diverge, and confusing them is the commonest way to misread this code.

registry.py is 258 lines and is the most practically useful file in the directory: it is the only place that answers "which cache will my flags produce". Entry is create_tree_cache at python/sglang/srt/mem_cache/registry.py:L199, called once from python/sglang/srt/mem_cache/kv_cache_builder.py:L337. If --radix-cache-backend NAME is set it looks up a registered factory and raises on an unknown name; otherwise it calls default_radix_cache_factory. The chain, first half:

def default_radix_cache_factory(ctx: TreeCacheBuildContext) -> BasePrefixCache:
    """Built-in Radix Cache selection chain."""
    server_args = ctx.server_args
    params = ctx.params

    if (
        ctx.disable_radix_cache
        and get_disagg().disaggregation_decode_retraction_backup == "host_pool"
    ):
        return _create_unified_radix_cache(ctx, server_args, params)

    if ctx.effective_chunked_prefill_size is not None and ctx.disable_radix_cache:
        if not ctx.is_hybrid_swa:
            from sglang.srt.mem_cache.chunk_cache import ChunkCache

            return ChunkCache(params)
        if ctx.full_tokens_per_layer == 0:
            from sglang.srt.mem_cache.chunk_cache import PureSWAChunkCache

            return PureSWAChunkCache(params)
        from sglang.srt.mem_cache.chunk_cache import SWAChunkCache

        return SWAChunkCache(params)

    if envs.SGLANG_EXPERIMENTAL_CPP_RADIX_TREE.get():

Second half, through the fall-through:

    if envs.SGLANG_EXPERIMENTAL_CPP_RADIX_TREE.get():
        # lazy import to avoid JIT overhead
        from sglang.srt.mem_cache.radix_cache_cpp import RadixCacheCpp

        logger.info("Using experimental C++ radix tree implementation.")
        return RadixCacheCpp(params=params, server_args=server_args)

    if ctx.is_hybrid_swa and ctx.full_tokens_per_layer == 0:
        from sglang.srt.mem_cache.pure_swa_radix_cache import PureSWARadixCache

        return PureSWARadixCache(params=params)

    if get_memory().enable_lmcache:
        from sglang.srt.mem_cache.storage.lmcache.lmc_radix_cache import (
            LMCRadixCache,
        )

        return LMCRadixCache(
            params=params,
            model_config=ctx.model_config,
            tp_size=ctx.tp_size,
            rank=ctx.tp_rank,
            tp_group=ctx.tp_group,
        )

    if get_memory().enable_flexkv:
        # Importing the package side-effect registers the explicit
        # ``--radix-cache-backend=flexkv`` factory; we then call the
        # factory directly so --enable-flexkv stands on its own.
        import os

        from sglang.srt.mem_cache.storage.flexkv import _flexkv_factory

        # Honor a CLI --flexkv-config-file by forwarding it via the env
        # var that FlexKV's config loader actually reads.
        if get_memory().flexkv_config_file and not os.environ.get("FLEXKV_CONFIG_PATH"):
            os.environ["FLEXKV_CONFIG_PATH"] = get_memory().flexkv_config_file
        return _flexkv_factory(ctx)

Seven branches, top to bottom, first match wins. Note what is not a branch: nothing tests for a Mamba model, or a hybrid-SWA model with a full-attention layer. Those no longer select a class — they select a component set inside the same class:

    from sglang.srt.mem_cache.unified_radix_cache import UnifiedRadixCache

    tree_components = [ComponentType.FULL]
    if ctx.is_hybrid_swa:
        tree_components.append(ComponentType.SWA)
    if ctx.is_hybrid_ssm:
        tree_components.append(ComponentType.MAMBA)

    if hasattr(params.req_to_token_pool, "req_to_c128_sidecar"):

and HiCache is attached after construction, not selected as a class:

        }
    cache = UnifiedRadixCache(params)
    if (
        ctx.enable_hierarchical_cache
        or get_disagg().disaggregation_decode_retraction_backup == "host_pool"
    ):
        cache.init_hicache(server_args, params)
        ctx.tp_worker.register_hicache_layer_transfer_counter(
            cache.cache_controller.layer_done_counter
        )
    return cache

That is the mechanical form of the convergence §2.4 described. A dimension that used to be a subclass is now a ComponentType:

class ComponentType(int, Enum):
    """Integer enum so that per-node list/tuple storage can be indexed directly."""

    FULL = 0
    SWA = 1
    MAMBA = 2
    C128 = 3

Read it against the flags you type. Plain --model-path meta-llama/Meta-Llama-3-8B-Instruct: every guard false, UnifiedRadixCache with tree_components == (FULL,). Add --enable-hierarchical-cache: same class plus init_hicache. Add --disable-radix-cache (which implies a chunked-prefill size): second branch, ChunkCache, whose disable property is a hard-coded True and whose match_prefix always returns empty (python/sglang/srt/mem_cache/chunk_cache.py:L35-L77). Set SGLANG_EXPERIMENTAL_CPP_RADIX_TREE=1 and you get a Python wrapper over a JIT-compiled C++ tree that no flag can reach — python/sglang/srt/environ.py:L588 is the only door.

After the chain, create_tree_cache runs three post-conditions whose error strings you will actually see (python/sglang/srt/mem_cache/registry.py:L216-L246): --hicache-host-memory-mode buffer_only and --enable-session-radix-cache each raise unless the result is a UnifiedRadixCache, and --enable-streaming-session wraps the cache in StreamingSession. Then it logs "Tree cache initialized: source=%s impl=%s ..." — the fastest runtime confirmation of everything above.

The 2,887-line unified_radix_cache.py is a facade, and reading it as the tree will waste your afternoon. Its __init__ at python/sglang/srt/mem_cache/unified_radix_cache.py:L148-L230 instantiates the components, builds a tree core, and then spends most of the file on HiCache: write-through acks, prefetch, storage backends, retraction backup. The tree itself lives behind self.tree_core, built at L193-L197 via create_tree_core(name=envs.SGLANG_UNIFIED_RADIX_TREE_CORE_BACKEND.get(), ...) — a second, smaller registry in unified_cache/tree_core_registry.py (73 lines).

The node

class UnifiedTreeNode:
    counter = 0

    def __init__(self, tree_components: tuple[ComponentType, ...], priority: int = 0):
        # Plain dict (not defaultdict): a missing-key read must raise, never
        # silently mint an unregistered node outside the TreeCore arena.
        self.children: dict[Any, UnifiedTreeNode] = {}
        self.parent: UnifiedTreeNode | None = None
        self.key: Optional[RadixKey] = None
        self.component_types = tree_components
        # list indexed by ComponentType (int enum 0..N-1)
        self.component_data: list[ComponentData] = [
            ComponentData() for _ in range(_NUM_COMPONENT_TYPES)
        ]
        self.last_access_time = get_and_increase_time_counter()
        self.creation_time = get_and_increase_time_counter()
        self.hash_value = None
        # Namespace-aware hashes used only for external KV events.
        self.event_hash_value: Optional[list[str]] = None
        self.hit_count = 0
        self.priority = priority
        self.lru_prev: list[UnifiedTreeNode | None] = [None] * (
            _NUM_COMPONENT_TYPES * 2
        )
        self.lru_next: list[UnifiedTreeNode | None] = [None] * (
            _NUM_COMPONENT_TYPES * 2
        )
        self.id = UnifiedTreeNode.counter
        UnifiedTreeNode.counter += 1
        self.write_through_pending_id: Optional[int] = None
        # Anchor NodeId of an in-flight H->D load-back reading this node's
        # host slots; such host copies must not be reclaimed until the ack.
        self.load_back_pending_id: Optional[int] = None

Four structural facts. (1) children is keyed by a child key — the first page of the edge, from RadixKey.child_key(page_size) — not a single token, so at page_size > 1 the fan-out is over pages. (2) component_data is a plain list indexed by the int enum, so node.component(ComponentType.SWA) is an array index. (3) lru_prev/lru_next are lists of length 2 × N_components: each node belongs to up to eight intrusive linked lists at once, device and host per component. (4) The comment on children is load-bearing — a plain dict, not a defaultdict, so a missing key raises instead of minting a node outside the arena.

Matching

match_prefix (python/sglang/srt/mem_cache/unified_cache/unified_tree_core.py:L640-L666) page-aligns the key, delegates to _match_prefix_helper, then post-processes. The walk itself:

        while len(key) > 0 and child_key in node.children:
            child = node.children[child_key]

            # HiCache: dead node (evicted + not backuped) — stop traversal
            if child.evicted and not child.backuped:
                break

            prefix_len = child.key.match(key, page_size=self.page_size)
            full_kv_hit_length += prefix_len
            if prefix_len < len(child.key):
                node, action = self._split_node(child.key, child, prefix_len)
                if not node.evicted:
                    value.append(node.component_data[BASE_COMPONENT_TYPE].value)
                _update_best_if_valid(node)
                break

            if not child.evicted:
                value.append(child.component_data[BASE_COMPONENT_TYPE].value)
            node = child
            _update_best_if_valid(node)
            key = key[prefix_len:]
            if len(key):
                child_key = key.child_key(self.page_size)

Descend by dict lookup on child_key, compare the edge with RadixKey.match, split and stop on a mid-edge divergence, otherwise consume the edge and continue. Each hop appends the node's own index tensor to a Python list; concatenation happens once, in _match_post_processor. A 20-node match does one torch.cat, not twenty.

The one piece with no counterpart in the earlier implementation is the validator pair. With HiCache on, the walk keeps two answers: the deepest node all components accept on either tier, and the deepest accepted with match_device_only=True. That is where MatchResult's three node handles come from, and why separate_device_match = self.enable_hicache at L687 changes the shape of the return value.

Splitting

    def _split_node(
        self, key: RadixKey, child: UnifiedTreeNode, split_len: int
    ) -> tuple[UnifiedTreeNode, Optional[CacheAction | ComponentAction]]:
        new_node = self._new_node(priority=child.priority)
        new_node.children = {key[split_len:].child_key(self.page_size): child}
        new_node.parent = child.parent
        new_node.key = child.key[:split_len]
        new_node.hit_count = child.hit_count
        new_node.creation_time = child.creation_time
        # Split fragments stay on the anchor's root path for the ack's walk.
        new_node.load_back_pending_id = child.load_back_pending_id

        self._for_each_component_lru(child, UnifiedLRUList.remove_node)

        child.parent = new_node
        child.key = child.key[split_len:]
        new_node.hash_value, child.hash_value = split_node_hash_value(
            child.hash_value, split_len, self.page_size
        )
        new_node.event_hash_value, child.event_hash_value = split_node_hash_value(
            child.event_hash_value, split_len, self.page_size
        )

        for component in self.components:
            component.redistribute_on_node_split(new_parent=new_node, child=child)
        new_node.parent.children[key.child_key(self.page_size)] = new_node

The mechanic is the textbook one §2.4 describes; what is new is the bookkeeping it must carry. The child leaves every component LRU before re-parenting and both halves re-enter at MRU afterwards (L1113-L1118); hash chains are split; and an in-flight device-to-host write emits ReplaceWriteThroughOnNodeSplit so the ack lands on the right node. A split is not a pointer shuffle, it is a small transaction.

Inserting

Insert is a resumable state machine — the biggest departure from the earlier recursive _insert_helper. begin_insert builds an _InsertWalkState; _advance_insert loops WALK → COMMIT → TAIL and suspends whenever a step emits a non-deferrable action (python/sglang/srt/mem_cache/unified_cache/unified_tree_core.py:L915-L938). The facade pumps it:

    def insert(self, params: InsertParams) -> InsertResult:
        if self.disable:
            return InsertResult(prefix_len=0)
        # Fail fast on re-entrancy without touching the in-flight walk.
        assert not self.tree_core.has_ongoing_insert(), "re-entrant insert"
        # Pump the resumable insert, applying each step's actions at its barrier.
        try:
            step = self.tree_core.begin_insert(params)
            while True:
                self._apply_cache_actions(step.actions)
                if step.result is not None:
                    # Walk actions flow through the steps; the result is action-free.
                    assert not step.result.cache_actions
                    return step.result
                step = self.tree_core.resume_insert()
        finally:
            # Drain still-pending actions so frees reach the allocator on abort.
            self._apply_cache_actions(self.tree_core.end_insert())

The barrier exists because a step can decide "free this node's KV" or "back this node up to host" — side effects the tree must not perform itself, since it does not own the allocator. One walk step:

    def _insert_walk_step(self, state: _InsertWalkState) -> None:
        """Process one walked node, appending its barrier actions to the state."""
        key = state.key
        child_key = key.child_key(self.page_size) if len(key) else None
        if child_key not in state.node.children:
            state.phase = _InsertPhase.COMMIT
            return
        step_actions = state.pending_actions
        node = state.node.children[child_key]
        self._touch_node(node)
        prefix_len = node.key.match(key, page_size=self.page_size)
        if prefix_len < len(node.key):
            node, action = self._split_node(node.key, node, prefix_len)
            if action is not None:
                step_actions.append(action)
        node.priority = max(node.priority, state.priority)

When the walk runs out of matching edges it moves to COMMIT, which creates the tail leaf:

    def _add_new_node(
        self,
        parent: UnifiedTreeNode,
        key: RadixKey,
        value: torch.Tensor,
        priority: int = 0,
    ) -> UnifiedTreeNode:
        new_node = self._new_node(priority=priority)
        new_node.parent = parent
        new_node.key = key
        new_node.component_data[BASE_COMPONENT_TYPE].value = value.clone()
        parent.children[key.child_key(self.page_size)] = new_node
        self.component_evictable_size_[BASE_COMPONENT_TYPE] += len(value)
        if self.enable_storage:
            new_node.hash_value = compute_node_hash_values(new_node, self.page_size)

        self._update_evictable_leaf_sets(new_node)
        self._update_evictable_leaf_sets(parent)
        self.kv_events.record_store(new_node)
        return new_node

Three lines to internalise. value.clone(): the tree owns its index tensor, never a view of the request's row. component_evictable_size_[FULL] += len(value): the accounting is updated at the same statement that creates the value, which is what makes it checkable by recomputation. And _update_evictable_leaf_sets runs on the new node and its parent, because the parent just stopped being a leaf.

Evicting

Eviction is driven per component. UnifiedRadixCache.evict (python/sglang/srt/mem_cache/unified_radix_cache.py:L537-L563) turns an EvictParams into a per-component request count and calls _evict_components, which for each component runs evict_device_start → evict_device_next_node* → evict_device_end. The FULL component's implementation is the tree-aware LRU, in code:

    def _evict_device_start(self, request_cnt: int) -> None:
        self._ensure_eviction_strategy()
        self._evict_device_request_cnt = request_cnt
        self._evict_device_last_node = None
        self._evict_device_heap = [
            (self.session_ref_eviction_strategy(n), n)
            for n in self.tree_core.evictable_device_leaves
        ]
        heapq.heapify(self._evict_device_heap)

    def _evict_device_next_node(
        self,
        tracker: dict[ComponentType, int],
        device_frees: dict[ComponentType, list[torch.Tensor]],
        host_frees: dict[ComponentType, list[torch.Tensor]],
    ) -> Optional[NodeId]:
        ct = self.component_type
        lv = self._evict_device_last_node
        if (
            lv is not None
            and lv.parent is not None
            and lv.parent in self.tree_core.evictable_device_leaves
        ):
            heapq.heappush(
                self._evict_device_heap,
                (self.session_ref_eviction_strategy(lv.parent), lv.parent),
            )
        self._evict_device_last_node = None
        while tracker[ct] < self._evict_device_request_cnt and self._evict_device_heap:
            _, x = heapq.heappop(self._evict_device_heap)
            if x not in self.tree_core.evictable_device_leaves:
                continue
            self._evict_device_last_node = x
            return x.id
        return None

This is the concrete answer to §2.4's "LRU over leaves". evictable_device_leaves is a maintained set, heapified once per eviction pass; the key is (session_ref > 0, session_ref, eviction_strategy.get_priority(node)) from L186-L188. Interior nodes are not in the set, so they cannot be selected — the invariant, not a comparison, is what protects the shared system prompt. And the loop's cadence is what makes it cascading: after a leaf is evicted its parent may become a leaf, so the next call pushes lv.parent back onto the heap before popping. Stale entries are skipped by the if x not in ... evictable_device_leaves: continue guard rather than by removal from the heap.

The priority function is pluggable and the file is 65 lines total. --radix-eviction-policy selects among them; the two least obvious:

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)


class SLRUStrategy(EvictionStrategy):
    def __init__(self, protected_threshold: int = 2):
        self.protected_threshold = protected_threshold

    def get_priority(self, node: TreeNode) -> Tuple[int, float]:
        # Priority Logic:
        # Smaller value = Evicted earlier.
        #
        # Segment 0 (Probationary): hit_count < threshold
        # Segment 1 (Protected): hit_count >= threshold
        #
        # Tuple comparison: (segment, last_access_time)
        # Nodes in segment 0 will always be evicted before segment 1.
        # Inside the same segment, older nodes (smaller time) are evicted first.

        is_protected = 1 if node.hit_count >= self.protected_threshold else 0
        return (is_protected, node.last_access_time)

Now the join. A matched prefix is a tensor of int64 slot indices; three separate structures interpret those integers.

1. ReqToTokenPool — a dense int32 matrix, one row per in-flight request, one column per position:

class ReqToTokenPool:
    """A memory pool that maps a request to its token locations."""

    enable_mamba_extra_buffer_lazy: bool = False

    def __init__(
        self,
        size: int,
        max_context_len: int,
        device: str,
        enable_memory_saver: bool,
    ):
        memory_saver_adapter = TorchMemorySaverAdapter.create(
            enable=enable_memory_saver
        )

        self.size = size
        # +1 padding row at index 0: cuda-graph padded batches default
        # req_pool_indices to 0, so dummy reads/writes land here harmlessly.
        self._alloc_size = size + 1
        self.max_context_len = max_context_len
        self.device = device
        with memory_saver_adapter.region(GPU_MEMORY_TYPE_KV_CACHE):
            self.req_to_token = torch.zeros(
                (self._alloc_size, max_context_len), dtype=torch.int32, device=device
            )
        self.free_slots = list(range(1, self._alloc_size))
        self.req_generation = torch.zeros(self._alloc_size, dtype=torch.int64)

    def write(self, indices, values):
        self.req_to_token[indices] = values

    def available_size(self):

req_to_token[req_pool_idx, pos] is the KV slot holding position pos. For 256 running requests at max_context_len = 8192 that is $(256+1) \times 8192 \times 4\ \mathrm{B} = 8{,}421{,}376$ B $\approx$ 8.03 MiB of HBM — arithmetic, not a measurement. Row 0 is padding, so CUDA-graph-padded batches (whose req_pool_indices default to 0) write somewhere harmless.

2. The KV pool — where the bytes are. MHATokenToKVPool (python/sglang/srt/mem_cache/memory_pool.py:L1759) holds a k_buffer and v_buffer per layer, shaped by:

    def _kv_buffer_shapes(self):
        """(k_shape, v_shape)"""
        if self.use_hnd:
            return (
                (self.num_pages, self.head_num, self.page_size, self.head_dim),
                (self.num_pages, self.head_num, self.page_size, self.v_head_dim),
            )
        rows = self.size + self.page_size
        return (
            (rows, self.head_num, self.head_dim),
            (rows, self.head_num, self.v_head_dim),
        )

An index $i$ addresses row $i$ of a [size + page_size, head_num, head_dim] tensor — unless the layout is HND, where it addresses within a page. MLATokenToKVPool (python/sglang/srt/mem_cache/memory_pool.py:L3949) instead holds one buffer per layer of width kv_lora_rank + qk_rope_head_dim: one latent vector per token, not K and V per head. Same index space, different byte layout; both reserve slot 0 as padding.

3. The allocator — who owns which slots. The token allocator is 84 lines and is a free list of exactly the kind you would write yourself:

    def clear(self):
        # The padded slot 0 is used for writing dummy outputs from padded tokens.
        self.free_pages = torch.arange(
            1, self.size + 1, dtype=torch.int64, device=self.device
        )
        self.is_not_in_free_group = True
        self.free_group = []
        self.release_pages = torch.empty((0,), dtype=torch.int64, device=self.device)

    def available_size(self):
        # To avoid minor "len(free_pages) * 1" overhead
        return len(self.free_pages) + len(self.release_pages)

    def alloc(self, need_size: int):
        if self.need_sort and need_size > len(self.free_pages):
            self.merge_and_sort_free()

        if need_size > len(self.free_pages):
            return None

        select_index = self.free_pages[:need_size]
        self.free_pages = self.free_pages[need_size:]
        return select_index

free_pages is a device tensor, allocation is a slice, free concatenates — no sorting unless need_sort is set, in which case frees queue in release_pages and merge lazily (python/sglang/srt/mem_cache/allocator/base.py:L77-L83). The paged allocator cannot hand out a slice, because a request's slots must be page-contiguous with its existing tail, so it calls a Triton kernel:

            self.merge_and_sort_free()

        out_indices = torch.empty(
            (extend_num_tokens,), dtype=torch.int64, device=self.device
        )

        alloc_extend_kernel[(bs,)](
            prefix_lens,
            seq_lens,
            last_loc,
            self.free_pages,
            out_indices,
            next_power_of_2(bs),
            self.page_size,
        )

        if self.debug_mode:
            assert len(torch.unique(out_indices)) == len(out_indices)

        if num_new_pages is None:
            num_new_pages = get_num_new_pages(
                seq_lens=seq_lens_cpu,
                page_size=self.page_size,
                prefix_lens=prefix_lens_cpu,
            )
        if num_new_pages > len(self.free_pages):
            return None

        self.free_pages = self.free_pages[num_new_pages:]

last_loc is the last slot of the matched prefix — which is to say, the last element of the tensor the tree just returned. That is the join, made explicit at python/sglang/srt/mem_cache/allocation.py:L332-L346, where last_loc is built as t[-1:] over prefix_tensors = [r.prefix_indices for r in batch.reqs]. The tree's output is the paged allocator's input.

Then the row is written:

    # Write to req_to_token_pool
    write_cache_indices(
        out_cache_loc,
        req_pool_indices_device,
        req_pool_indices_cpu,
        prefix_lens_device,
        prefix_lens_cpu,
        batch.seq_lens,
        batch.seq_lens_cpu,
        extend_lens_device,
        extend_lens_cpu,
        prefix_tensors,
        batch.req_to_token_pool,
    )

Positions [0, prefix_len) get the tree's indices verbatim; [prefix_len, seq_len) get the fresh ones. The fast path is a Triton kernel over the whole batch (python/sglang/srt/mem_cache/allocation.py:L69-L85); the loop above is the readable version of the same write.

Two tree nodes and a request row can reference the same physical slot. The free list records allocatability, while locks, reference counts and outstanding GPU holders jointly determine whether recycling is safe. Double free can make two requests share writable rows; missing release can instead leak capacity. An independent oracle must check slot identity, liveness and eventual cleanup, not just allocation/free totals.

There are nineteen assert statements in unified_radix_cache.py, each naming something a contributor must not break. Four groups matter.

Refcount discipline. A lock is taken on a path, not a node. acquire_component_lock walks from the matched node to the root, and the accounting moves token counts between two scalars as each node's refcount crosses zero:

        root = self.tree_core.root_node
        cur = node

        # Skip the bottom evicted segment
        while cur is not root and cur.component_data[ct].value is None:
            result.skip_lock_node_ids.setdefault(ct, set()).add(cur.id)
            cur = cur.parent

        # Lock the device-on segment up to root
        delta = 0
        while cur is not root:
            cd = cur.component_data[ct]
            assert (
                cd.value is not None
            ), f"FULL invariant broken: evicted ancestor {cur.id} above device-on segment"
            if cd.lock_ref == 0:
                key_len = len(cd.value)
                self.tree_core.component_evictable_size_[ct] -= key_len
                self.tree_core.component_protected_size_[ct] += key_len
                delta += key_len
            cd.lock_ref += 1
            self.tree_core.evictable_device_leaves.discard(cur)
            cur = cur.parent
        result.delta = delta
        return result

Read the assert: "FULL invariant broken: evicted ancestor {id} above device-on segment". It encodes the deepest structural rule in the tree — if a node has device KV, every ancestor has device KV; there is no hole in a path. The release path at L303-L342 is the exact mirror, with assert cd.lock_ref > 0 catching an unbalanced dec.

Leaf-set maintenance. The device-leaf set is the eviction candidate set, so anything that changes a node's leaf-ness must update it. The predicate:

    def _is_device_leaf(self, node: UnifiedTreeNode) -> bool:
        """D-leaf: Full device value present, no child with Full KV on device,
        unlocked, not root.

        Only the Full (base) component is required; auxiliary components
        (Mamba, SWA) are not mandatory for D-leaf membership."""
        ct = BASE_COMPONENT_TYPE
        if node is self.root_node or node.evicted:
            return False
        if any(cd.lock_ref > 0 for cd in node.component_data):
            return False
        if any(
            child.component_data[ct].value is not None
            for child in node.children.values()
        ):
            return False
        return True

_update_evictable_leaf_sets is called from _add_new_node, _split_node, _unevict_node_on_insert, and all four lock-ref entry points. Miss one in a patch and the cache silently stops evicting a subtree, surfacing as an out-of-memory hours later.

Size accounting. evictable_size_ and protected_size_ are per-component dicts, and their relationship is a partition, not an ordering: every non-root node with a device value contributes len(value) to exactly one of them, chosen by lock_ref > 0. sanity_check proves it by brute force:

        # ── PART 4: Size Accounting ──
        for ct in self.component_types:
            evictable = 0
            protected = 0
            for n in all_nodes:
                if n is self.root_node:
                    continue
                cd = n.component_data[ct]
                if cd.value is not None:
                    toks = len(cd.value)
                    if cd.lock_ref > 0:
                        protected += toks
                    else:
                        evictable += toks
            if self.component_evictable_size_[ct] != evictable:
                E(
                    f"[Size] {ct} evictable={self.component_evictable_size_[ct]} "
                    f"!= recomputed={evictable}"
                )
            if self.component_protected_size_[ct] != protected:
                E(
                    f"[Size] {ct} protected={self.component_protected_size_[ct]} "
                    f"!= recomputed={protected}"
                )

Their consumer is the scheduler's admission arithmetic: available_and_evictable_str (python/sglang/srt/mem_cache/base_prefix_cache.py:L434-L437) reports available_size() + evictable_size() as the tokens a batch may assume. Drift high and the scheduler admits a batch it cannot allocate; drift low and throughput quietly collapses.

The whole check. UnifiedTreeCore.sanity_check is 256 lines in five parts — tree structure, per-node state machine and leaf qualification, tracking structures, size accounting, ongoing operations — raising AssertionError with every violation listed after a pretty_print(). Its rules are the contributor's checklist: root keeps a Full device value and lock_ref > 0; parent and child pointers agree; aux components require Full data on the same tier; every node keeps Full data on at least one tier ("node {id} dead: no Full device and no Full host"); full_lock >= component_lock; no node in both a device and a host LRU. The catch is its caller (python/sglang/srt/managers/scheduler_components/invariant_checker.py:L453-L459): it runs only for hybrid-SWA or hybrid-SSM models. On a plain Llama-3 deployment nothing checks any of this at runtime.

Search the entire SGLang tree for @rank_consensus and you get three hits outside the decorator's own docstring. All three are in unified_radix_cache.py:

SGLang's own engineers have marked cache bookkeeping and nothing else as the place tensor-parallel ranks silently disagree, and the reason is structural. Every rank runs the same scheduler loop, and the forward is kept in lock-step by collectives — but the radix tree is host-side state, replicated per rank, synchronised by nothing. A dict iteration order, a float comparison, a time.perf_counter() tiebreak, an exception caught on one rank only: any of those and rank 0 believes the prefix hit 2,048 tokens while rank 1 believes 1,536. The forwards then have different sequence lengths, the next collective mismatches, and the process hangs on an all-reduce with no error message.

    @rank_consensus(
        same_params=["params"],
        same_results=["result.full_kv_hit_length", "result.swa_host_hit_length"],
    )
    def match_prefix(self, params: MatchPrefixParams) -> MatchResult:
        result = self.session.try_match_prefix(params)
        if result is not None:
            return result
        if self.disable:
            return self.tree_core.empty_match_result
        result = self.tree_core.match_prefix(params)
        # Apply the walk's actions (e.g. a pending write-through relocation on
        # a split) before the finalizers, which can evict or raise.
        self._apply_cache_actions(result.cache_actions)
        for component in self._components_tuple:
            result = component.finalize_match_result_in_cache(params, result)
        # Finalizers must not emit actions; the walk's were applied above.
        assert not result.cache_actions
        return result

Note what is compared: not the tree, not the index tensors, but result.full_kv_hit_length and result.swa_host_hit_length — two integers the batch shape depends on. Comparing the tensors would be expensive and wrong; slot ids are per-rank by design.

The mechanism is cheap and brutal. The decorator compiles to the identity function unless SGLANG_ENABLE_RANK_CONSENSUS_CHECKER is set — evaluated at import time (python/sglang/srt/utils/rank_consensus_checker.py:L87-L88), so zero cost when off. When on, each call pushes a payload string onto a queue from the scheduler thread; a background thread drains a globally agreed number of events, hashes their concatenation, and all-reduces the digest over a dedicated gloo group:

    min_value = torch.tensor(list(hasher.digest()), dtype=torch.uint8)
    max_value = min_value.clone()
    for group in _sync_groups:
        dist.all_reduce(min_value, op=dist.ReduceOp.MIN, group=group)
        dist.all_reduce(max_value, op=dist.ReduceOp.MAX, group=group)
    if not torch.equal(min_value, max_value):
        # When divergence, all rank should output the following log.
        logger.critical(
            f"Found rank divergence for {len(events)} events(s)! local hash: {value_bytes.hex()}, events = {events}"
        )
        for handler in logger.handlers:
            handler.flush()

        # os._exit instead of sys.exit: this runs in a background thread, where
        # SystemExit would only kill the thread, not the process. os._exit tears
        # down the whole scheduler process so a TP/PP mismatch can never
        # silently keep serving.
        os._exit(1)

A MIN and a MAX all-reduce over the SHA-1 digest: if they differ, some rank disagreed. Then logger.critical, a handler flush, and os._exit(1) — the comment explains that sys.exit would only kill the background thread and leave a diverged server quietly answering requests. Configured at python/sglang/srt/managers/scheduler.py:L2122-L2130 over the attention-CP, attention-TP, TP and PP groups.

The lesson for anyone writing a cache: any decision that changes a tensor shape must be a pure function of replicated inputs — not of wall-clock time, dict order, or exception timing. Hence full_host_duplicates carrying the comment "insertion-ordered dict keeps victims TP-deterministic" (python/sglang/srt/mem_cache/unified_cache/unified_tree_core.py:L472-L474), and the write_back_duplicate_reclaim_digest rolling hash beside it.

Llama-3-8B, one H100 SXM, default flags, so UnifiedRadixCache with tree_components == (FULL,) and no HiCache. A request arrives with a 2,144-token prompt whose first 2,048 tokens are already cached under nodes A (512 tok) and B (1,536 tok), and it will generate 96 tokens.

1. Match. Req.init_next_round_input (python/sglang/srt/managers/schedule_batch.py:L1362-L1372) builds a RadixKey and calls match_prefix: through the @rank_consensus wrapper (unified_radix_cache.py:L495) into UnifiedTreeCore.match_prefix (unified_tree_core.py:L640) → _match_prefix_helper (L667). Two dict hops, no split, value == [tensor(512), tensor(1536)]. _match_post_processor (L754) bumps last_access_time up the root path, concatenates once, and returns NodeIds (L804-L810). The unpack at L1378-L1400 sets req.prefix_indices, req.last_node, req.cache_protected_len = 2048.
2. Lock. PrefillAdder calls inc_lock_ref(req.last_node) (python/sglang/srt/managers/schedule_policy.py:L1059) → unified_radix_cache.py:L683 → unified_tree_core.py:L557 → FullComponent.acquire_component_lock (full_component.py:L259). A and B each go lock_ref = 0 → 1; 2,048 tokens move from component_evictable_size_[FULL] to component_protected_size_[FULL]; B leaves evictable_device_leaves. 256 MiB of KV is now unevictable.
3. Allocate. alloc_for_extend (python/sglang/srt/mem_cache/allocation.py:L281) calls alloc_req_slots → ReqToTokenPool.alloc (memory_pool.py:L291) for the row, then — at page_size == 1 — alloc_token_slots, which evicts first if the allocator is short and then calls TokenToKVPoolAllocator.alloc (allocator/token.py:L55). At page_size > 1 the paged path uses last_loc = prefix_indices[-1:] instead.
4. Write the row. write_cache_indices (allocation.py:L54) writes [0, 2048) from the tree's tensor and [2048, 2144) from out_cache_loc. From here the attention kernel reads req_to_token, never the tree.
5. Decode. The 96-token uncached prompt suffix is processed in the extend forward, which samples output token 1. Then 95 steps of alloc_for_decode (allocation.py:L512), each appending one slot per request. The tree is untouched for the whole decode. At the book's 4.48 ms decode floor for Llama-3-8B at batch 1, that is roughly 426 ms for these subsequent decode forwards in the idealized model; each step reads/writes KV even though the radix tree is not consulted for matching — derived, not measured.
6. Insert. release_kv_cache (mem_cache/common.py:L198-L219) calls cache_finished_req (unified_radix_cache.py:L743), which reads the 2,239 computed slot ids (2,144 prompt tokens plus the first 95 generated tokens) out of req_to_token, page-aligns the key, copies the values with .to(dtype=torch.int64, copy=True), and inserts. The walk re-matches A and B; COMMIT calls _add_new_node with the 191-token computed suffix beyond the shared 2,048-token prefix; leaf C appears. The final sampled output has not been forwarded, so it has no KV entry.
7. Free the tail, unlock. Still in cache_finished_req: free_segments releases the unaligned and truncated tails, then _dec_req_lock (unified_radix_cache.py:L706) walks A and B back to lock_ref = 0 and 2,048 tokens return to evictable_size_. C is now an unlocked device leaf — the first candidate the next eviction pass sees.
8. Evict, later. A future batch is short by N tokens. evict_from_tree_cache (common.py:L114) → evict(EvictParams(num_tokens=N)) → _evict_components (unified_radix_cache.py:L620); _evict_device_start heapifies the leaf set and _evict_device_next_node pops C. evict_device_leaf (unified_tree_core.py:L1245) sees not node.backuped and, in write-through mode, deletes it; device_frees reach the allocator via _free_values (unified_radix_cache.py:L565). B becomes a leaf and joins the heap. A survives as long as anything below it does.

The mid-generation variant: for chunked prefill, cache_unfinished_req does the same insert, then re-matches its own key and repoints the request's row at the tree's canonical slots:

        radix_key = radix_key.page_aligned(self.page_size)
        page_aligned_len = len(radix_key)
        values = kv_indices[:page_aligned_len].to(dtype=torch.int64, copy=True)

        insert_params.key = radix_key
        insert_params.value = values
        result = self.insert(insert_params)

        # Match prefix. SWA insertion retains one extra window before the
        # page-aligned boundary, so the normal match remains safe to repoint.
        match_result = self.match_prefix(MatchPrefixParams(key=radix_key, req=req))
        new_indices = match_result.device_indices
        new_last_node = match_result.last_device_node
        new_prefix_len = result.prefix_len
        assert (
            req.cache_protected_len <= len(new_indices) + self.page_size - 1
        ), f"{req.cache_protected_len=}, {len(new_indices)=}, {page_aligned_len=}"
        assert new_prefix_len <= len(
            new_indices
        ), f"{new_prefix_len=}, {len(new_indices)=}"
        self.req_to_token_pool.write(
            (req.req_pool_idx, slice(req.cache_protected_len, len(new_indices))),
            new_indices[req.cache_protected_len :],
        )

That req_to_token_pool.write is what makes deduplication real: if another request already owned those slots, this row now points at their KV, and its own duplicates were freed by the FreeDeviceKV action the insert walk emitted at unified_tree_core.py:L991-L994.

One subtler trap: evictable_size() on the unified cache is a per-component dict lookup (unified_tree_core.py:L2400-L2426) that returns only the FULL component. On a hybrid-SWA model it and swa_evictable_size() are different numbers over different pools, and using the first where you meant the second can over-admit or unnecessarily restrict work depending on the separate FULL and SWA budgets, per-request growth and other admission limits. There is no universal occupancy multiplier.

Everything below is a repo observation or a log line; none of it needs a GPU except the last.

S=~/Documents/other_git_repos/sglang

# 1. Which caches are dead? Anything whose only hit is its own class statement.
for c in HiRadixCache SWARadixCache MambaRadixCache UnifiedRadixCache; do
  echo "== $c"; grep -rn "$c(" --include="*.py" $S/python/sglang/srt/
done

# 2. The whole selection chain in one screen.
sed -n '80,142p' $S/python/sglang/srt/mem_cache/registry.py

# 3. Every invariant the tree will check for you, as prose.
grep -n 'E(f\?"' $S/python/sglang/srt/mem_cache/unified_cache/unified_tree_core.py

# 4. The three places TP divergence is guarded.
grep -rn "@rank_consensus" --include="*.py" $S | grep -v rank_consensus_checker

# 5. Confirm at runtime which cache you got (needs a GPU).
python -m sglang.launch_server --model-path meta-llama/Meta-Llama-3-8B-Instruct 2>&1 \
  | grep "Tree cache initialized"

Line 5 prints source=, impl=, hybrid_swa=, hybrid_ssm=, hicache_attached= and streaming_wrapped= from registry.py:L248-L256. It is the ground truth for everything Figure 2 claims. Flip --disable-radix-cache, --enable-hierarchical-cache, and SGLANG_EXPERIMENTAL_CPP_RADIX_TREE=1 in turn and watch impl= change.

Two more levers. SGLANG_RADIX_FORCE_MISS (python/sglang/srt/managers/schedule_batch.py:L1367) rewrites every match into a miss via zero_match_result — the cleanest way to measure what prefix caching is buying without changing anything else. SGLANG_DEBUG_MEMORY_POOL (allocator/paged.py:L126) enables assert len(torch.unique(out_indices)) == len(out_indices) inside alloc_extend, the assertion that fires once refcount discipline has already broken upstream.

• sglang issue #20415 — the Unified Radix Cache convergence, named directly in python/sglang/srt/mem_cache/README.md:L43. Read it before proposing anything that adds a ninth cache class.
• sglang issue #25371 — the mem_cache/ layout specification, cited at README.md:L5-L6: why allocator/, pool_host/ and storage/ are separate packages, and why "layers do not import upwards".
• unified_cache/components/README.md — the Full/SWA/Mamba component model, referenced from README.md:L44-L45. The right next file after this chapter.
• sglang PR #20476 — cited in a live comment at memory_pool.py:L295-L304, where a ReqToTokenPool.alloc assertion about chunked requests reusing a req_pool_idx was relaxed. An example of how these invariants actually move.
• Zheng et al., "SGLang: Efficient Execution of Structured Language Model Programs" — the RadixAttention paper. Read it for the idea; read this directory for what shipped.