I7Hard★ LLM Serving Frontier · SGLang CorePart I · Inference, Decoding & Quantization

RadixAttention Prefix Cache Tree & LRU Eviction

⚡Flashcard Drill➔

Store shared prompt and multi-turn KV prefixes in a compressed radix tree with edge splitting and ref-counted LRU leaf eviction.

⏱️ Time: O(|Prompt|) 前缀匹配与插分边
💾 Space: O(CachedTokens) 基数树压缩节点
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
class RadixNode:
def __init__(self, tokens=()):
self.tokens = tuple(tokens)
self.children = {} # first_token -> RadixNode
self.parent = None
self.lock_ref = 0 # active running requests holding this prefix
self.last_access = 0
class RadixPrefixCache:
"""Prefix-sharing KV radix tree with ref-count protection and LRU leaf eviction."""
def __init__(self, capacity_tokens: int):
self.root = RadixNode()
self.capacity = capacity_tokens
self.cached_tokens = 0
self.tick = 0
def match_prefix(self, prompt_tokens: list) -> tuple:
self.tick += 1
node = self.root
matched_len = 0
path_nodes = [node]
while matched_len < len(prompt_tokens):
tok = prompt_tokens[matched_len]
if tok not in node.children:
break
child = node.children[tok]
# Compare compressed edge tokens
edge_match = 0
while (edge_match < len(child.tokens) and
matched_len + edge_match < len(prompt_tokens) and
child.tokens[edge_match] =
edge_match += 1
if edge_match < len(child.tokens):
# Partial edge hit stops at matched prefix length
matched_len += edge_match
break
node = child
node.last_access = self.tick
path_nodes.append(node)
matched_len += edge_match
return matched_len, path_nodes
def insert(self, tokens: list) -> RadixNode:
self.tick += 1
node = self.root
idx = 0
while idx < len(tokens):
tok = tokens[idx]
if tok not in node.children:
new_leaf = RadixNode(tokens[idx:])
new_leaf.parent = node
new_leaf.last_access = self.tick
node.children[tok] = new_leaf
self.cached_tokens += len(new_leaf.tokens)
self._evict_if_needed(exclude=new_leaf)
return new_leaf
child = node.children[tok]
k = 0
while k < len(child.tokens) and idx + k < len(tokens) and child.tokens[k] == tokens[idx + k]:
k += 1
if k < len(child.tokens):
# Split compressed edge
mid = RadixNode(child.tokens[:k])
mid.parent = node
mid.lock_ref = child.lock_ref
mid.last_access = self.tick
child.tokens = child.tokens[k:]
child.parent = mid
mid.children[child.tokens[0]] = child
node.children[tok] = mid
node = mid
idx += k
else:
child.last_access = self.tick
node = child
idx += k
return node
def _evict_if_needed(self, exclude=None):
while self.cached_tokens > self.capacity:
leaves = []
stack = [self.root]
while stack:
cur = stack.pop()
if not cur.children and cur is not self.root and cur is not exclude and cur.lock_ref == 0:
leaves.append(cur)
stack.extend(cur.children.values())
if not leaves:
break
victim =
del victim.parent.children[victim.tokens[0]]
self.cached_tokens -= len(victim.tokens)
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: How does Cache-Aware Scheduling boost RadixAttention hit rates?
Next: AWQ Activation-Aware Group-Wise INT4 Quantization →
💡

Core Mental Anchor / Mnemonic

Match longest prefix in radix tree, split edges on divergence, evict only unlocked LRU leaves.

📐 Mathematical Derivation & Core Formula

PrefillTokens=∣P∣−LCP(P,Tradix)\text{PrefillTokens} = |P| - \mathrm{LCP}(P, \mathcal{T}_{\mathrm{radix}})
### Prefix Reuse via Compressed Radix Trees
Multi-turn chats, shared system prompts, and tree-of-thought branches repeat large KV prefixes. Storing KV mappings in a radix tree cuts prefill work down to the uncached suffix ∣P∣−LCP(P,T)|P| - \mathrm{LCP}(P, \mathcal{T}).
When requests diverge mid-edge, the node splits cleanly; when cache fills, LRU eviction reclaims only unlocked leaf nodes (lock_ref == 0).

🔄 Tensor Dimensions & Shape Flow

prompt -> LCP match in RadixTree -> compute KV only for uncached suffix -> evict unlocked LRU leaves on overflow

🛡️ Numerical Stability & Pitfalls Checklist

  • Increment lock_ref along active prefix paths during execution so running requests cannot lose cached blocks.
  • Split compressed edges cleanly when a new prompt diverges partway along an existing edge.

💻 Reference Code Implementation

class RadixNode:
    def __init__(self, tokens=()):
        self.tokens = tuple(tokens)
        self.children = {}   # first_token -> RadixNode
        self.parent = None
        self.lock_ref = 0    # active running requests holding this prefix
        self.last_access = 0

class RadixPrefixCache:
    """Prefix-sharing KV radix tree with ref-count protection and LRU leaf eviction."""
    def __init__(self, capacity_tokens: int):
        self.root = RadixNode()
        self.capacity = capacity_tokens
        self.cached_tokens = 0
        self.tick = 0

    def match_prefix(self, prompt_tokens: list) -> tuple:
        self.tick += 1
        node = self.root
        matched_len = 0
        path_nodes = [node]
        while matched_len < len(prompt_tokens):
            tok = prompt_tokens[matched_len]
            if tok not in node.children:
                break
            child = node.children[tok]
            # Compare compressed edge tokens
            edge_match = 0
            while (edge_match < len(child.tokens) and
                   matched_len + edge_match < len(prompt_tokens) and
                   child.tokens[edge_match] == prompt_tokens[matched_len + edge_match]):
                edge_match += 1
            if edge_match < len(child.tokens):
                # Partial edge hit stops at matched prefix length
                matched_len += edge_match
                break
            node = child
            node.last_access = self.tick
            path_nodes.append(node)
            matched_len += edge_match
        return matched_len, path_nodes

    def insert(self, tokens: list) -> RadixNode:
        self.tick += 1
        node = self.root
        idx = 0
        while idx < len(tokens):
            tok = tokens[idx]
            if tok not in node.children:
                new_leaf = RadixNode(tokens[idx:])
                new_leaf.parent = node
                new_leaf.last_access = self.tick
                node.children[tok] = new_leaf
                self.cached_tokens += len(new_leaf.tokens)
                self._evict_if_needed(exclude=new_leaf)
                return new_leaf
            child = node.children[tok]
            k = 0
            while k < len(child.tokens) and idx + k < len(tokens) and child.tokens[k] == tokens[idx + k]:
                k += 1
            if k < len(child.tokens):
                # Split compressed edge
                mid = RadixNode(child.tokens[:k])
                mid.parent = node
                mid.lock_ref = child.lock_ref
                mid.last_access = self.tick
                child.tokens = child.tokens[k:]
                child.parent = mid
                mid.children[child.tokens[0]] = child
                node.children[tok] = mid
                node = mid
                idx += k
            else:
                child.last_access = self.tick
                node = child
                idx += k
        return node

    def _evict_if_needed(self, exclude=None):
        while self.cached_tokens > self.capacity:
            leaves = []
            stack = [self.root]
            while stack:
                cur = stack.pop()
                if not cur.children and cur is not self.root and cur is not exclude and cur.lock_ref == 0:
                    leaves.append(cur)
                stack.extend(cur.children.values())
            if not leaves:
                break
            victim = min(leaves, key=lambda n: n.last_access)
            del victim.parent.children[victim.tokens[0]]
            self.cached_tokens -= len(victim.tokens)

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

cache = RadixPrefixCache(capacity_tokens=10)
n1 = cache.insert([1, 2, 3, 4, 5, 6])
n1.lock_ref = 1  # 6 tokens pinned by active request
n_idle = cache.insert([10, 11, 12, 13])  # 4 idle tokens
assert cache.cached_tokens == 10
matched, _ = cache.match_prefix([1, 2, 3, 99, 100])
assert matched == 3, f"Expected LCP=3, got {matched}"
# Insert 4 new tokens: idle leaf [10..13] must be evicted while pinned [1..6] survives
n2 = cache.insert([20, 21, 22, 23])
assert cache.cached_tokens <= 10, f"Eviction must enforce capacity budget, got {cache.cached_tokens}"
matched_pinned, _ = cache.match_prefix([1, 2, 3, 4, 5, 6])
assert matched_pinned == 6, "Pinned active prefix must not be evicted"
matched_evicted, _ = cache.match_prefix([10, 11, 12, 13])
assert matched_evicted == 0, "Unpinned LRU leaf must be evicted"
print("✓ RadixAttention prefix tree cache assertion passed")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:How does Cache-Aware Scheduling boost RadixAttention hit rates?
Scheduling queued requests in longest-prefix-match priority groups together requests sharing the same cached subtree, reducing cache thrashing under tight KV memory budgets.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: Continuous Batching Iteration-Level SchedulerBack to Part I & All 105Next: AWQ Activation-Aware Group-Wise INT4 Quantization →