--- 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\] maintains an LRU eviction policy to keep relevant [[thoughts/KV compression|KV cache]] entries for all requests within a [[thoughts/Radix tree|radix tree]], implemented in . Every request inserts its prefix tokens $\pi = (t_1,\ldots,t_m)$ along the tree; each node stores a pointer to the KV page that realises that prefix. During decoding the runtime walks the tree to find the deepest cached prefix shared with the new suffix $\sigma$ and reuses the cached $K,V$ tensors before appending freshly computed blocks: $$ \text{reuse}(\pi, \sigma) = \bigoplus_{j=1}^{m} \text{KV}(t_{1:j}) \;\Vert\; \bigoplus_{k=1}^{|\sigma|} \text{attend}(t_{1:m+k}). $$ The LRU policy keeps the union of active prefixes resident on GPU while evicting the coldest leaf pages; evicted prefixes spill to host memory so they can be faulted back in if a later request revisits them. > \[!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/touch updates the LRU ordering so hot conversations stay resident while rarely used prefixes migrate to CPU or disk. ```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 one with longer matched prefixes instead of FIFO schedule._
"\\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

We got lower bound: $$ C \ge \sum_{e \in \text{edges}(T)} \mid e \mid $$ Consider we visit radix tree $T$ in DFS order. For each edge $e$ of $T$, the first time we compute KV cache associated with $e$, then we will compute the whole subtree of $e$. During computation of $e$ subtree, then edge $e$ will be continuously hit, thus no additional computation will happen. > \[!tip\] cache hit > > with cache size $\ge$ maximum request length (which will equals to longest path in 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{}$