Level 24 | SGLang RadixAttention

Mission 1 核心概念

RadixAttention：缓存共同前缀，少算重复 prompt

先补的知识

很多请求可能共享相同系统提示词或长前缀。
KV Cache 可以复用已经计算过的前缀。
Radix Tree 适合按 token 前缀查找。

图解原理

像自动补全目录：多个 prompt 从同一段开头分叉，公共开头只存一份。

[1,2]到 [3]到 [8]另一路到 [4]

语法热身：列表前缀比较

def common_prefix(a, b):
    n = 0
    for x, y in zip(a, b):
        if x != y:
            break
        n += 1
    return n

闯关题

[10, 20, 30] 和 [10, 20, 99] 的最长公共前缀长度是？

2 1 3

回到 notebook 的作业

这里不直接写答案。你已经拿到足够输入，最后用 notebook 的 TODO 做举一反三。

先理解节点里存的是 token 片段而不是单个字符。用公共前缀长度判断是否命中缓存。把匹配到的 KV Cache 长度返回给调用方。

Mission 2 TODO

遍历子节点：找能匹配 prompt 的最长分支

先补的知识

root.children 存放可能的下一段前缀。
匹配时要比较 prompt_tokens 和 child.tokens。
最长匹配优先，因为它能复用更多缓存。

图解原理

在分叉路口先看哪条路的路牌和 prompt 开头对得上，对得越长越值得走。

prompt: A B C Dchild1: A Bchild2: A X走 child1

语法热身：遍历节点找最长匹配

best = None
best_len = 0
for child in self.root.children:
    n = common_prefix(prompt_tokens, child.tokens)
    if n > best_len:
        best = child
        best_len = n

闯关题

查 Radix Tree 时为什么要找最长匹配？

让 batch size 变大复用尽可能多的 KV Cache 避免使用 token id

回到 notebook 的作业

这里不直接写答案。你已经拿到足够输入，最后用 notebook 的 TODO 做举一反三。

遍历 root.children。对每个 child 计算公共前缀长度。返回最长命中的节点和匹配长度。