Level 24 | SGLang RadixAttention | SGLang 基数注意力

Mission 1 概念练习

最长公共前缀：双重边界内逐位比较，第一次不同就停止

🎯 先猜一猜

缓存是 [1,2,3]，新 prompt 是 [1,9,3]。

最长公共前缀长度是多少？

1 2，因为 1 和 3 都出现 3

先猜一个答案，再对照下面的讲解。可以随时修改选择，猜错会得到解释。

先补的知识

cached_tokens 和 prompt_tokens 都是 Python token_id 序列，本题使用列表，不涉及张量 shape、dtype 或 device。
公共前缀必须从索引 0 连续开始；中间一旦不同，后面即使再次相等也不能计入。
循环条件要同时保护两个序列边界，避免一个短序列已经结束却继续索引。
match_len 同时表示当前比较索引和已经连续匹配的 token 数。

图解原理

LCP 不是统计两列里共有多少 token，而是数“开头连续相同了多久”。因此算法只需要一个从 0 开始的指针：两边都没结束且当前位置相等就加一，遇到第一次不同立刻停。

[1,2,3] 与 [1,2,4]

索引0：1=1索引1：2=2索引2：3≠4

连续命中长度为 2，第三项不同后立即停止。

[7,8] 与 [7,8,9,10]

索引0命中索引1命中缓存序列结束

短序列整体是长序列前缀，返回 2，不会越界。

输入类型两个 Python token 序列match_len 初值0继续条件match_len 同时小于两个序列长度相等match_len += 1不等break 并返回当前 match_len

不要用集合交集。集合会丢掉顺序和连续性，例如 [1,2,3] 与 [1,9,3] 有两个共同元素，但最长公共前缀只有 1。

语法热身：比较两个路径开头连续相同的站点

saved_route = ['A', 'B', 'C']
new_route = ['A', 'B', 'D', 'E']
same = 0

while same < len(saved_route) and same < len(new_route):
    if saved_route[same] == new_route[same]:
        same += 1
    else:
        break

print(same)  # 2

从语法例子迁移到 TODO 1

saved_route：对应 cached_tokens
new_route：对应 prompt_tokens
same：对应 match_len，既是索引也是命中长度
两个 len 条件：分别防止缓存路径或新 prompt 越界
break：对应第一次 token 不同后立即停止

巩固一下

while 条件为什么要同时检查两个序列长度？

任意一个序列结束都不能再访问该索引为了把列表变成张量为了自动排序 token

学完这一段，试着做

用一个小动作确认自己理解了；最后再进入官方题目。

完成 _lcp_len 的 while、相等递增和不等 break；不要使用 set、sort 或 zip 后统计全部相等项。运行两个基础断言：[1,2,3] 与 [1,2,4] 返回 2；[7,8] 与更长的 [7,8,9,10] 也返回 2。额外验证空列表与完全不匹配列表都返回 0；若越界，检查 while 是否缺少任一长度条件。

Mission 2 概念练习

遍历缓存路径：每个 child 算一次 LCP，只保留最大命中

🎯 先猜一猜

第一个 child 与 prompt 命中 4 个 token，第二个 child 命中 5 个。

match_prefix 应返回什么？

5 4，因为先遇到 9，把两次命中相加

先猜一个答案，再对照下面的讲解。可以随时修改选择，猜错会得到解释。

先补的知识

insert(tokens) 会创建 TreeNode(tokens) 并追加到 root.children；当前教学实现只有单层候选路径。
child.key_tokens 是该候选缓存路径的 token 列表。
_lcp_len 已负责比较一个候选与新 prompt；match_prefix 只负责在多个候选结果中取最大值。
best_match_len 从 0 开始，因此没有 child 或完全无命中时会自然返回 0。

图解原理

这是一个标准的“遍历 + 累计最优值”模式：每看一个候选就计算局部分数 match_len，再与当前最好成绩比较。不要在第一次命中时提前返回，因为后面可能有更长的缓存路径。

候选 A[0,1,2,3] → 命中 4 候选 B[0,1,2,3,4] → 命中 5 候选 C[9,9,9] → 命中 0 最终最大值best_match_len = 5

错误：第一次命中就 return

候选 A 命中 4 后立即返回，会错过候选 B 的更长命中 5。

正确：循环结束后 return

每轮只更新 best_match_len，所有 child 都比较完成后再返回。

状态
best_match_len 是 Python int 局部值
match_len 来自 _lcp_len 更新
只在更大时替换 无命中
保持 0

语法热身：从多条历史路线中找最长重合开头

def common_prefix_len(left, right):
    count = 0
    while count < len(left) and count < len(right):
        if left[count] != right[count]:
            break
        count += 1
    return count

history = [['A', 'B'], ['A', 'B', 'C'], ['X']]
current = ['A', 'B', 'C', 'D']
best = 0

for route in history:
    local = common_prefix_len(route, current)
    if local > best:
        best = local

print(best)  # 3

从语法例子迁移到 TODO 2

history：对应 self.root.children
route：对应 child；实际 token 序列在 child.key_tokens
common_prefix_len：对应 self._lcp_len
local：对应当前候选的 match_len
best：对应 best_match_len，循环完成后再返回

巩固一下

为什么完全不匹配 [7,6,5] 时可以返回 0？

因为 root.children 会被删除 best_match_len 初始为 0，所有局部命中都不会让它变大因为 token 会自动补零

学完这一段，试着做

用一个小动作确认自己理解了；最后再进入官方题目。

完成 root.children 遍历、_lcp_len 调用和最大值更新；把 return 放在 for 循环结束之后。运行多候选测试，新 prompt [0,1,2,3,4,5] 必须选择 5，而不是先遇到的 4；无命中返回 0。若返回 4，检查是否提前 return；若返回最后一个候选的 0，检查是否每轮无条件覆盖 best_match_len。

Mission 3 概念练习

把命中长度变成工程动作：前 H 个复用，剩余后缀重算

🎯 先猜一猜

prompt=[0,1,2,3,4,5]，match_prefix 返回 hit_len=5。

split_prompt 应返回什么？

([0,1,2,3,4], [5], 5) ([0,1,2,3,4,5], [], 5) ([5], [0,1,2,3,4], 5)

先猜一个答案，再对照下面的讲解。可以随时修改选择，猜错会得到解释。

先补的知识

match_prefix(prompt_tokens) 返回 Python int H，表示可直接复用的最长前缀 token 数。
Python 切片 prompt_tokens[:H] 取前 H 项，prompt_tokens[H:] 取从 H 开始的剩余项。
H=0 时前缀切片自然是 []，后缀自然是完整 prompt；H 等于 prompt 长度时后缀自然为空。
函数返回顺序必须严格是 hit_prefix、miss_suffix、hit_len，测试会按这个顺序解包。

图解原理

前两步只算出了一个数字 H，这一步才把 H 变成推理系统的工作划分：前 H 个 token 的 KV Cache 可以复用，H 之后的 token 必须送给模型重新计算。切片正好表达这条边界。

命中 H=5

prompt [0,1,2,3,4,5]hit [0,1,2,3,4]miss [5]

前五个 token 复用缓存，只计算最后一个 token。

无命中 H=0

prompt [7,6,5]hit []miss [7,6,5]

没有可复用缓存，完整 prompt 都进入重算后缀。

hit_lenmatch_prefix(prompt_tokens) 的返回值hit_prefixprompt_tokens[:hit_len]miss_suffixprompt_tokens[hit_len:]返回顺序(hit_prefix, miss_suffix, hit_len)系统含义前缀复用 KV，后缀重新执行模型计算

不要从某个 child.key_tokens 直接返回前缀。测试契约要求拆分当前 prompt_tokens；这样返回内容一定保持新请求本身的 token 序列。

语法热身：按已下载长度拆分文件任务

all_parts = ['p0', 'p1', 'p2', 'p3']
cached_count = 3
reused = all_parts[:cached_count]
remaining = all_parts[cached_count:]

result = (reused, remaining, cached_count)
print(result)  # (['p0','p1','p2'], ['p3'], 3)

从语法例子迁移到 TODO 3

all_parts：对应 prompt_tokens
cached_count：对应 hit_len，由 match_prefix 计算
reused：对应 hit_prefix，切片终点不包含 hit_len
remaining：对应 miss_suffix，从 hit_len 开始
result：对应函数的三元组返回顺序

巩固一下

hit_len=0 时为什么不需要额外 if 分支？

因为 0 会自动变成 None 因为 match_prefix 会抛异常 Python 的 [:0] 自动得到空列表，[0:] 自动得到完整列表

学完这一段，试着做

用一个小动作确认自己理解了；最后再进入官方题目。

完成 hit_len 调用、两个切片和三元组返回，严格保持返回顺序。运行命中与无命中测试：H=5 时返回五项前缀和单项后缀；H=0 时返回空前缀和完整后缀。若前缀多一项，检查切片是否误写成 :hit_len+1；若解包内容错位，检查 return 三项顺序。

SGLang 基数注意力

最长公共前缀：双重边界内逐位比较，第一次不同就停止

🎯 先猜一猜

先补的知识

图解原理

[1,2,3] 与 [1,2,4]

[7,8] 与 [7,8,9,10]

语法热身：比较两个路径开头连续相同的站点

从语法例子迁移到 TODO 1

巩固一下

学完这一段，试着做

遍历缓存路径：每个 child 算一次 LCP，只保留最大命中

🎯 先猜一猜

先补的知识

图解原理

错误：第一次命中就 return

正确：循环结束后 return

语法热身：从多条历史路线中找最长重合开头

从语法例子迁移到 TODO 2

巩固一下

学完这一段，试着做

把命中长度变成工程动作：前 H 个复用，剩余后缀重算

🎯 先猜一猜

先补的知识

图解原理

命中 H=5

无命中 H=0

语法热身：按已下载长度拆分文件任务

从语法例子迁移到 TODO 3

巩固一下

学完这一段，试着做

准备好，去官方题目试一试