Reuse as a Data Structure: RadixAttention and HiCache

SGLang’s cache design answers a concrete question: when two requests share context, how can the runtime recognize that fact, preserve the right state, and avoid paying for the same work twice? This chapter follows that state from a local radix tree to the three-tier HiCache system. The aim is not to memorize a cache feature, but to understand the conditions under which reuse improves serving—and the points where identity, memory movement, or eviction become the real constraint.

Suppose many users ask questions about the same long document. The document’s tokens are identical across requests, so the model’s KV state for that prefix is also reusable, provided the requests use compatible tokenization, template, adapter context, and cache namespace. Without prefix reuse, each request repeats the document’s prefill work. With reuse, the runtime can start from an existing prefix and spend its compute budget on the part that is genuinely new.

The local cache remembers spans, not strings

RadixAttention represents reusable context as a radix tree. A node corresponds to a consecutive span of logical tokens and points to the KV-cache indices that hold the state for that span. A path from the root represents a prefix. Two requests that share their first several spans can therefore share the corresponding nodes, while diverging requests create different suffixes below the shared path.

The distinction between a node and a string matters. The cache is not merely storing prompt text for comparison later. It is organizing already computed model state so that a future request can refer to the right KV locations. The token sequence is the identity used to find that state; the values associated with the node are the positions in the KV pool. The result of a match is a sequence of device indices for the longest cached prefix, not just a boolean hit.

When a request arrives, SGLang walks the tree from the root. It examines the next child span, compares that span with the incoming token sequence, and continues while the tokens match. If the cache uses pages larger than one token, the match is rounded down to a page boundary. This makes allocation and transfer more regular, but it also means a request may have a matching partial page that cannot be used as a complete cached unit. Page granularity is therefore part of the reuse decision, not a detail hidden below it.

The tree can refine itself during lookup. Imagine that a stored node represents tokens 1 through 100, while a new request matches exactly through token 60 and then diverges. The cache splits the node at the boundary. One node now represents the reusable 1-through-60 prefix, and its child represents the remaining stored suffix. No KV state is duplicated for the purpose of this topology change: the associated values are divided into the corresponding spans. Future requests can now stop at the exact boundary instead of treating the whole 100-token segment as indivisible.

Insertion follows the same logic. SGLang walks through existing matching spans, advances past them, and creates a new node only for the unmatched suffix. Access time and hit metadata are updated along the path. This is why a busy shared prefix can accumulate value without being copied once for every request. The cache’s capacity is consumed by distinct KV spans, while requests refer to those spans through their own mappings.