--- date: '2026-05-27' description: prefix-tree caching of KV pages with LRU eviction, shared request prefixes reuse computed K,V. id: attention-radix modified: 2026-06-06 01:39:05 GMT-04:00 seealso: - '[[thoughts/Attention|Attention]]' - '[[thoughts/Radix tree|Radix tree]]' - '[[thoughts/paged attention|Paged Attention]]' - '[[thoughts/KV compression|KV compression]]' tags: - ml - llm - technical title: Radix Attention created: '2026-05-27' published: '2026-05-27' pageLayout: default slug: thoughts/radix-attention permalink: https://aarnphm.xyz/thoughts/radix-attention.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- RadixAttention \[@zheng2024sglangefficientexecutionstructured\] keeps relevant [[thoughts/KV compression|KV cache]] entries for all requests in a [[thoughts/Radix tree|radix tree]], with LRU eviction for cold leaves. SGLang implements it in [sgl-project/sglang](https://github.com/sgl-project/sglang). Every request has tokens $t_{1:m}$. Let $h$ be the length of the deepest cached prefix. During decoding, the runtime reuses that prefix and computes only the missing tail: $$ \operatorname{KV}(t_{1:m}) = \operatorname{KV}_{\mathrm{cache}}(t_{1:h}) \;\Vert\; \operatorname{KV}_{\mathrm{new}}(t_{h+1:m}). $$ The LRU policy keeps active prefixes resident on the GPU and frees the coldest leaf pages. Host or file backing belongs to SGLang’s optional HiCache layer, not to the base RadixAttention algorithm. > \[!example\] request routing pseudo-code > > ```python > def serve(request): > prefix, suffix = split_prefix_suffix(request.tokens) > node = radix.longest_prefix(prefix) > kv_pages = node.cached_kv() > for token in suffix: > logits, kv_new = transformer.step(token, kv_pages) > kv_pages.push(kv_new) > radix.touch(node) # update lru state > radix.insert(prefix+suffix, kv_pages) > ``` > > Each insert or touch updates the LRU ordering so hot conversations stay resident while cold leaf pages are freed. ```jsx imports={Zoomable,RadixPrefixTree} ``` _dynamic evolution of the radix tree in response to various requests._ ## cache-aware scheduling We define the hit rate as $$ \begin{aligned} \text{hit rate} &= \frac{\sum_{r \in R} \text{number of cached prefill tokens in } r}{\sum_{r \in R} \text{number of prefill tokens in } r} \\[8pt] &=1 - \frac{C}{\sum_{r \in R} \text{number of prefill tokens}} \end{aligned} $$ _in batch settings: sort requests by matching prefix length and prioritise requests with longer matched prefixes instead of FIFO._
"\\begin{algorithm}\n\\caption{Cache-Aware Scheduling}\n\\begin{algorithmic}\n\\State \\textbf{Input:} Radix tree $T$, Memory pool $P$.\n\\State \\textbf{Input:} current running batch $B$, waiting queue $Q$.\n\\State \\textbf{Output:} Finished requests and updated system state.\n\\State // Get all requests from the waiting queue\n\\State requests $\\gets Q.\\text{get\\_all\\_requests}()$\n\\State // Search for prefix matching for all waiting request\n\\For{req $\\in$ requests}\n \\State req.prefix\\_node, req.prefix\\_len $\\gets$ T.match\\_prefix(req.input\\_tokens)\n\\EndFor\n\\State // Sort the request according to matched prefix lengths\n\\State requests.sort()\n\\State // Select requests for the next batch\n\\State available\\_size $\\gets$ T.evictable\\_size() + P.available\\_size()\n\\State current\\_size $\\gets$ 0\n\\State new\\_batch $\\gets$ []\n\\For{req $\\in$ requests}\n \\If{req.size() + current\\_size $\\le$ available\\_size}\n \\State new\\_batch.append(req)\n \\State $\\delta \\gets T.\\text{increase\\_ref\\_counter}(req.\\text{prefix\\_node})$\n \\State available\\_size $\\gets$ available\\_size + $\\delta$\n \\EndIf\n\\EndFor\n\\State Q.remove\\_requests(new\\_batch)\n\\State // Insert requests into the current running batch\n\\State B.merge(new\\_batch)\n\\State // Allocate new memory and do eviction if necessary\n\\State needed\\_size $\\gets$ B.needed\\_size()\n\\State success, buffer $\\gets$ P.alloc(needed\\_size)\n\\If{$\\neg \\text{success}$}\n \\State T.evict(needed\\_size)\n \\State success, buffer $\\gets$ P.alloc(needed\\_size)\n\\EndIf\n\\State B.run(buffer)\n\\State // Process finished requests\n\\State finished\\_requests $\\gets$ B.drop\\_finished\\_requests()\n\\For{req $\\in$ finished\\_requests}\n \\State T.decrease\\_ref\\_counter(req.prefix\\_node)\n \\State T.insert(req)\n\\EndFor\n\\State \\Return finished\\_requests\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 2 Cache-Aware Scheduling

Input: Radix tree TT, Memory pool PP.

Input: current running batch BB, waiting queue QQ.

Output: Finished requests and updated system state.

// Get all requests from the waiting queue

requests ←Q.get_all_requests()\gets Q.\text{get\_all\_requests}()

// Search for prefix matching for all waiting request

for req ∈\in requests do

req.prefix_node, req.prefix_len ←\gets T.match_prefix(req.input_tokens)

end for

// Sort the request according to matched prefix lengths

requests.sort()

// Select requests for the next batch

available_size ←\gets T.evictable_size() + P.available_size()

current_size ←\gets 0

new_batch ←\gets []

for req ∈\in requests do

if req.size() + current_size ≤\le available_size then

new_batch.append(req)

δ←T.increase_ref_counter(req.prefix_node)\delta \gets T.\text{increase\_ref\_counter}(req.\text{prefix\_node})

available_size ←\gets available_size + δ\delta

end if

end for

Q.remove_requests(new_batch)

// Insert requests into the current running batch

B.merge(new_batch)

// Allocate new memory and do eviction if necessary

needed_size ←\gets B.needed_size()

success, buffer ←\gets P.alloc(needed_size)

if ¬success\neg \text{success} then

T.evict(needed_size)

success, buffer ←\gets P.alloc(needed_size)

end if

B.run(buffer)

// Process finished requests

finished_requests ←\gets B.drop_finished_requests()

for req ∈\in finished_requests do

T.decrease_ref_counter(req.prefix_node)

T.insert(req)

end for

return finished_requests

The lower bound for prefill compute is the number of unique token edges in the radix tree: $$ C \ge \sum_{e \in \operatorname{edges}(T)} |e|. $$ A DFS schedule reaches this bound when the cache can hold the longest request path. Once an edge $e$ has been computed, every request in the subtree under $e$ can reuse that prefix while the schedule stays inside the subtree. Descendant edges still need their own first computation; no edge is recomputed. > \[!tip\] cache hit > > with cache size $\ge$ the maximum request length, equal to the longest path in the radix tree, edge $e$ **WILL NOT** be evicted during computation of its subtree > since the common prefix including $e$ of the subtree will be continuously hit. We can show that longest-shared-prefix-first order is equivalent to DFS order by induction [^proof] [^proof]: _base_: a random request correspond to node $x \in T$ will be processed. - All requests correspond to nodes $\{v_{1}, \ldots, v_{n}\}$ on path $x \gets \text{root}$ doesn’t need recomputation. - Thus, computation complexity for requests of nodes $\{v_{1}, \ldots, v_{n}, x\}$ is aligned with DFS _induction_: assume we visit node $y \in T$, and the visited node align with DFS order. Let $P$ denote _path of_ $y \gets \text{root}$. - Each node that has not been visited has the lowest common ancestor with visited nodes on $P$. - Since nodes on $P$ are cached, a node $z$ that has yet to be visited with lowest common ancestor on $P$ will have the _longest shared prefix_ - longest-shared-prefix-first order will select $z$, which is a valid DFS $\boxed{}$